特征值与特征向量

(实)正定矩阵 $M$:$\forall \vec{x} \ne \vec{0},s.t.\vec{x}^TM\vec{x}>0$

考虑几何意义:$\vec{x}^TM\vec{x}=\vec{x}^T\vec{x’}>0$

也就是 $\vec{x}$ 在经过 $M$ 进行线性变化后,得到了与 $\vec{x}$ 夹角小于 $\frac{\pi}{2}$ 的向量 $\vec{x’}$
也就是说 $M$ 是把 $\vec{x}$ 往以 $\vec{x}$ 为法向量确定的半超空间进行映射
也就是说 $M$ 是将 $\vec{x}$ 沿着 $\vec{x}$ 的正方向进行映射

考虑矩阵 $M$ 的特征值:

矩阵 $M$ 的一组特征对 $(\lambda,\vec{v})$,表示某个向量会沿着特征向量 $\vec{v}$ 的方向进行映射,缩放比例由特征值 $\lambda$ 决定
$$
M\vec{v}_k=\lambda_k\vec{v}_k \Rightarrow M\vec{x}=M\sum a_k\vec{v}_k=\sum a_k\lambda_k\vec{v}_k
$$
也就是说,$\vec{x}$ 的 $\vec{v}_k$ 方向会缩放为原先的 $\lambda_k$ 倍

由于 $\vec{x}$ 和 $\vec{x}’$ 的夹角是小于 $\frac{\pi}{2}$,这实际上是意味着 $\lambda_k>0$(这里有点小问题)

但:$\forall(\lambda,\vec{v}),s.t.\vec{v}^TM\vec{v}>0 \Rightarrow \vec{v}^T\lambda \vec{v}=\lambda \Vert \vec{v} \Vert >0 \Rightarrow \lambda>0$

那么“正定”实际上指的是线性变换后,像与原像在方向上大体一致

所以,“特征”指的是方向特征,也就是说 $\vec{v}$ 在 $M$ 映射后只会进行伸缩而不会进行旋转!

对角化和谱分解

  • 谱分解
    • $\exists X,\det(X) \ne 0, s.t. X^{-1}AX=\Lambda=\mathrm{diag}(\vec{\lambda})$
    • 称 $X$ 对角化 $A$
    • 称分解 $A=X\Lambda X^{-1}$ 为 $A$ 的谱分解
  • 对 $n$ 阶方阵 $A$,有:$A$ 可对角化,当且仅当 $A$ 有 $n$ 个线性无关的特征向量
    • 如果方阵 $A$ 可对角化
      • $A$ 存在谱分解 $A=X\Lambda X^{-1}$
      • $\Lambda$ 的对角元素是 $A$ 的特征值
      • $X$ 的第 $i$ 列就是 $A$ 的属于 $\Lambda$ 的第 $i$ 个对角元素的特征向量
  • 方阵的属于不同特征值的特征向量线性无关
  • 几何重数:$\dim \mathcal{N}(\lambda_0I_n-A)$
    • $1 \le \text{几何重数} \le \text{代数重数}$
    • 特征值至少对应一个特征向量
  • 特征值
    • 特征值:$\text{代数重数}=1$
    • 半单特征值:$\text{代数重数}=\text{几何重数}$
    • 亏损特征值:$\text{代数重数} > \text{几何重数}$
  • 矩阵可对角化
    • $n$ 阶方阵 $A$ 在 $\mathbb{C}$ 上可对角化,当且仅当其特征值都半单
    • $n$ 阶方阵 $A$ 在 $\mathbb{R}$ 上可对角化,当且仅当其特征值多项式都是实根,且其特征值都半单
  • 对于分块对角矩阵 $A=\begin{bmatrix}A_1 & \\ & A_2 \end{bmatrix}$,有:$A$ 可对角化当且仅当 $A_1,A_2$ 都可对角化

行列式

长度?面积?体积?

在 $\mathbb{R}$ 中,可以通过比较长度来对比两条线段的“大小”

在 $\mathbb{R}^2$ 中,可以通过比较面积来对比两个矩形的“大小”

在 $\mathbb{R}^3$ 中,可以通过比较体积来对比两个长方体的“大小”

自然而然地,引入一个函数来表达 $\mathbb{R}^n$ 中的 $n$ 维超立方体的“大小”是很有必要的

不妨考虑一下 $\mathbb{R}^2$ 中面积(这里以由 $\vec{a}_1,\vec{a}_2$ 构成的平行四边形为例)的性质(记 $S=\delta(\vec{a}_1,\vec{a}_2)$):

  • 邻边共线则面积为 $0$
    • 如果 $\vec{a}_1,\vec{a}_2$ 平行(也就是共线),那么构成的平行四边形面积为 $0$
  • 一条边的边长变为原来的 $k$ 倍,则面积变为原来的 $k$ 倍
    • 也就是 $S’=\delta(\vec{a}_1,k\vec{a}_2)=kS=k\delta(\vec{a}_1,\vec{a}_2)$
    • 实际上就是 $S=w \times h$,然后 $h \to kh$,所以 $S \to kS$
  • 两个图形的面积和为各自面积和的和(*这里说法有点不太准确)
    • 也就是 $\delta(\vec{a}_1,\vec{a}_2+\vec{a}_3)=\delta(\vec{a}_1,\vec{a}_2)+\delta(\vec{a}_1,\vec{a}_3)$
  • 单位正方形的面积为 $1$
    • 实际上是初始条件: $\delta(\vec{e}_1,\vec{e}_2)=1$

现在来回顾一下这几条性质

第一条意味着,这里的面积的定义是有向面积

  • 面积 $S>0$ 的时候,$\vec{a}_2$ 在 $\vec{a}_1$ 的左侧 $180^\circ$ 内

  • 考虑:$0=\delta(\vec{a}_1+\vec{a}_2,\vec{a}_1+\vec{a}_2)=\delta(\vec{a}_1,\vec{a}_1)+\delta(\vec{a}_1,\vec{a}_2)+\delta(\vec{a}_2,\vec{a_1})+\delta(\vec{a}_2,\vec{a}_2)=\delta(\vec{a}_1,\vec{a}_2)+\delta(\vec{a}_2,\vec{a}_1)$

  • 也就是 $\delta(\vec{a}_1,\vec{a}_2)=-\delta(\vec{a}_2,\vec{a}_1)$

第二、三条意味着“有向面积”满足列多线性性“

  • 也就是 $\delta(p\vec{a}_1+q\vec{a}_2,\vec{a}_3)=\delta(p\vec{a}_1,\vec{a}_3)+\delta(q\vec{a}_2,\vec{a}_3)=p\delta(\vec{a}_1,\vec{a}_3)+q\delta(\vec{a}_2,\vec{a}_3)$
  • 也就是说,可以把向量 $\vec{a}$ 分解成 $\vec{a_1}+\vec{a}_2$,然后把括号内的加号提出到括号外
  • 或者把 $k\vec{a}$ 的系数 $k$ 提出到括号外

第四条就是定义了”递归边界“

  • 因为对于任意一个向量 $\vec{a}$ 可以用 $\mathbb{R}^n$ 的一组基 $\vec{e}_k$ 唯一分解
  • $\delta(\vec{a},\vec{a}’)=\delta(k_1\vec{e}_1+k_2\vec{e}_2,\vec{a}’)=k_1\delta(\vec{e}_1,\vec{a}’)+k_2\delta(\vec{e}_2,\vec{a}’)$

有向面积?行列式函数!

那么将”有向面积“推广到 $\mathbb{R}^n$,就得到了行列式函数 $\delta : \mathbb{R}^{n \times n} \mapsto \mathbb{R}$

不妨用 $\det(A)$ 表示 $\delta(\vec{a}_1,\cdots,\vec{a}_n)$

可以证明,满足以下条件的行列式函数唯一:

  • 列多线性性
    • $\delta(\cdots,p\vec{a}_i+q\vec{a}_j,\cdots)=p\delta(\cdots,\vec{a}_i,\cdots)+q\delta(\cdots,\vec{a}_j,\cdots)$
    • $\det(AE_{ii;k})=k\det (A)$
    • $\det(AE_{ji;k})=\det(A)$
  • 列反对称性(等价于共线为 $0$)
    • $\delta(\cdots,\vec{a}_i,\cdots,\vec{a}_j,\cdots)=-\delta(\cdots,\vec{a}_j,\cdots,\vec{a}_i,\cdots)$
    • $\det(AP_{ij})=-\det(A)$
  • 单位化条件
    • $\delta(I_n)=1$

实际上,对于初等矩阵有:

  • $\det(P_{ij})=-1$
  • $\det(E_{ii;k})=k$
  • $\det(E_{ji;k})=1$

因此,如果 $\mathrm{rank}(A) < n$,则 $\det(A)=0$

如果 $\mathrm{rank}(A)=n$,则 $A$ 可以分解成若干初等矩阵的乘积,即 $A=\prod_{k} E_k$

所以 $\det(A)=\det(\prod_{k}E_k)=\prod_k \det(E_k)$

所以 $\det(AB)=\det(A)\det(B)=\det(BA)$

以及 $\det(A^T)=\det(\prod^kE_{k}^T)=\prod^k\det(E_k^T)=\prod_{k}\det(E_k)=\det(A)$

行列式的展开式

有空再写

行列式的完全展开:$\det(A)=\sum_{\sigma} \mathrm{sign}(\sigma) \prod_{k}a_{\sigma_kk}$

斜率方程

朴素直线与椭圆联立

$$
\begin{equation}
\begin{cases}
y=kx+m \\
\frac{x^2}{a^2}+\frac{y^2}{b^2}=1
\end{cases}
\end{equation}
\Rightarrow
(b^2+a^2k^2)x^2+2a^2kmx+a^2m^2-a^2b^2=0
$$

平移坐标系下的斜率方程

设不过点 $O(x_0,y_0)$ 的直线 $l:m(x-x_0)+n(y-y_0)=1$ 于椭圆 $\Gamma: \frac{x^2}{a^2}+\frac{y^2}{b^2}=1$ 交于 $A(x_1,y_1),B(x_2,y_2)$ 两点,则 $k_{OA},k_{OB}$ 是某二次方程的两个根

$$
\begin{equation}
\begin{cases}
m(x-x_0)+n(y-y_0)=1 \\
\frac{x^2}{a^2}+\frac{y^2}{b^2}=1 \\
k=\frac{y-y_0}{x-x_0}
\end{cases}
\end{equation} \\
\Rightarrow
\frac{1+2y_0n}{b^2}k^2+(\frac{2x_0n}{a^2}+\frac{2y_0m}{b^2})k+\frac{1+2x_0m}{a^2}=(1-\frac{x_0^2}{a^2}-\frac{y_0^2}{b^2})(m^2+n^2k^2+2mnk)
$$

特殊的,如果 $O(0,0)$,则原方程可特殊化为:
$$
\begin{equation}
\begin{cases}
mx+ny=1 \\
\frac{x^2}{a^2}+\frac{y^2}{b^2}=1 \\
k=\frac{y}{x}
\end{cases}
\end{equation}
\Rightarrow
\frac{1}{b^2}k^2+\frac{1}{a^2}=m^2+n^2k^2+2mnk
$$

考虑椭圆 $\Gamma:\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$,在平面内有一点 $P(x_0,y_0)$,同时设直线 $l:m(x-x_0)+n(y-y_0)=1$ 与 $\Gamma$ 相交于点 $A(x_1,y_1),B(x_2,y_2)$

联立 $\Gamma,l$ 可得:
$$
\frac{1+2y_0n}{b^2}k^2+\left(\frac{2x_0n}{a^2}+\frac{2y_0m}{b^2}\right)k+\frac{1+2x_0m}{a^2}=\left(1-\frac{x_0^2}{a^2}-\frac{y_0^2}{b^2}\right)\left(m^2+n^2k^2+2mnk\right)
$$
其中 $k=\frac{y-y_0}{x-x_0}$

下面考虑 $P$ 在 $\Gamma$ 上的情况

斜率之和为定值

$$
\begin{aligned}
&k_1+k_2=\lambda \\
&-\frac{\frac{2x_0n}{a^2}+\frac{2y_0m}{b^2}}{\frac{1+2y_0n}{b^2}}=\lambda \\
&\frac{2x_0n}{a^2}+\frac{2y_0m}{b^2}+\lambda\frac{1+2y_0n}{b^2}=0 \\
&m=-\left(\frac{2x_0n}{a^2}+\lambda\frac{1+2y_0n}{b^2}\right) \frac{b^2}{ 2 y _ 0} \\
&m=-n\left(\lambda+\frac{b^2x_0}{a^2y_0}\right)-\frac{\lambda}{ 2 y _ 0} \\
&l:\left[-n\left(\lambda+\frac{b^2x_0}{a^2y_0}\right)-\frac{\lambda}{ 2 y _ 0}\right](x-x _ 0)+n(y-y_0)=1 \\
&l:n\left[\left(\lambda+\frac{b^2x_0}{a^2y_0}\right)(x_0-x)+(y-y_0)\right]+\frac{\lambda}{ 2 y _ 0}(x _ 0-x)=1
\end{aligned}
$$

故过定点 $\left(x_0-y_0\cdot\frac{2}{\lambda},y_0-y_0\cdot\frac{2}{\lambda}\right)$

特别的,当 $\lambda=0$ 时,有 $l:n\left[\frac{b^2x_0}{a^2y_0}(x_0-x)+(y-y_0)\right]=1,k_l=\frac{b^2x_0}{a^2y_0}$

斜率之积是定值

斜率之比是定值

稀疏矩阵分解

稀疏因子

$$
\delta(A)=\frac{\sum_{i,j}[A_{i,j} \ne 0]}{n\cdot m}
$$

当 $\delta \le 0.05$ 时,认为矩阵是稀疏的

稀疏矩阵存储

行优先存储(CSR)

列优先存储(CSC)

填入元(fill-in)

高斯消元中的新增位置

$$
\begin{bmatrix}
\color{red}X & \color{red}X & \color{red}X \\
X & & X \\
X & X &
\end{bmatrix}
\Rightarrow
\begin{bmatrix}
\color{red}X & \color{red}X & \color{red}X \\
\color{green}X & \color{blue}X & \color{green}X \\
\color{green}X & \color{green}X & \color{blue}X
\end{bmatrix}
$$

Cholesky分解中的update矩阵

$$
B \Rightarrow B-\frac{\boldsymbol{v}\boldsymbol{v}^T}{x}
$$

求解方阵方程

$$
\begin{cases}
A\boldsymbol{x}=\boldsymbol{b} \\
A=LU
\end{cases}
\Rightarrow
LU\boldsymbol{x}=\boldsymbol{b}
\Rightarrow
\begin{cases}
L\boldsymbol{y}=\boldsymbol{b} \\
U\boldsymbol{x}=\boldsymbol{y}
\end{cases}
$$

只需要解决两个问题

  • $A=LU$
  • $\boldsymbol{y}=L^{-1}\boldsymbol{b}$

重排序

$$
A\boldsymbol{x}=\boldsymbol {b} \Leftrightarrow PAP^TP\boldsymbol{x}=P\boldsymbol{b} \\
PAP^T=LU
$$

消去图中按照度数从小到大排序

Markowitz积,按照度数平方排序,即fill-in个数

嵌套割集(Nested dissection)

每次取当前图的平均割集,并放到最后

$$
A - S - B
\Rightarrow
\begin{bmatrix}
A & & X \\
&B& X\\
X &X& S \\
\end{bmatrix}
$$

近似最小度(Appr. min. degree, AMD)

带宽缩小排序(Reverse Cuthill-McKee, Sloan, …)

非零元向对角线居中

Lsolve算法

用于解决 $\boldsymbol{y}=L^{-1}\boldsymbol{b}$

$$
y(j)=\frac{b(j)-\sum_{i=1}^{j-1}L(j,i) \cdot y(i)}{L(j,j)}
$$

1
2
3
4
5
6
7
y = b
forall(i = 1:n, y(i) /= 0)
y(i) = y(i) / L(i, i)    ! 如果没有单位对角化L
forall(j = i+1:n, L(j, i) /= 0)
y(j) = y(j) - L(j, i) * y(i)
end
end

重排序?若 $L(j, i) \ne 0$,则先遍历 $j$ 后遍历 $i$

若 $L(j,i) \ne 0$,连边 $j \to i$,由于 $j \ge i$,所以得到一张DAG,找拓扑序即可

假设 $L$ 已经进行主对角线单位化,则 $y(j)=b(j)-\sum_{i=1}^{j-1}L(j,i) \cdot y(i)$

考虑fill-in的关系:

$$
\begin{cases}
b(j) \ne 0 \Rightarrow y(j) \ne 0 \\
y(i) \ne 0 \land L(j,i) \ne 0 \Rightarrow y(j) \ne 0
\end{cases}
$$

2022-01-30-16-40-11-image.png

只需要计算:$\mathcal{B}={i \mid b(i) \ne 0},\mathcal{Y}={i \mid y(i) \ne 0}$

其中 $\mathcal{Y}=\mathrm{Reach}_{G(L)}(\mathcal{B})$

这一部分的时间复杂度是 $O(|\mathcal{B}|+f)$

Left-looking算法

用于解决 $A=LU$

考虑从左到右依次确定 $L,U$ 的前 $k$ 列的值

$$
\begin{bmatrix}
A_{11} & a_{12} & A_{13} \\
a_{21} & a_{22} & a_{23} \\
A_{31} & a_{32} & A_{33}
\end{bmatrix}
=
\begin{bmatrix}
L_{11} & & \\
l_{21} & 1 & \\
L_{31} & l_{32} & L_{33}
\end{bmatrix}
\begin{bmatrix}
U_{11} & u_{12} & U_{13} \\
& u_{22} & U_{23} \\
& & U_{33}
\end{bmatrix}
$$

归纳性的,假设已经计算完前 $k-1$ 列的LU分解,考虑计算第 $k$ 列

$$
\begin{bmatrix}
a_{12} \\
a_{22} \\
a_{32}
\end{bmatrix}
=
\begin{bmatrix}
L_{11} & & \\
l_{21} & 1 & \\
L_{31}& l_{32} & L_{33} \\
\end{bmatrix}
\begin{bmatrix}
u_{12} \\
u_{22} \\
0 \\
\end{bmatrix}
$$

这里 $l_{32},L_{33},u_{12},u_{22}$ 都是未知的,同时要求求出 $l_{32},u_{12},u_{22}$

考虑到 $a_{32}=L_{31} \cdot u_{12}+l_{32} \cdot u_{22}$,所以只需要用 $l_{32}=\frac{a_{32}-L_{31}\cdot u_{12}}{u_{22}}$ 计算 $l_{32}$ 即可

即解方程:

$$
\begin{bmatrix}
a_{12} \\
a_{22} \\
a_{32}
\end{bmatrix}
=
\begin{bmatrix}
L_{11} & & \\
l_{21} & 1 & \\
L_{31}& 0 & I \\
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
\end{bmatrix}
$$

其中:

$$
\begin{cases}
u_{11}=x_1 \\
u_{22}=x_2 \\
l_{32}=\frac{x_3}{x_2}
\end{cases}
$$

初始情况:$\boldsymbol{a} _ 1=\boldsymbol{l} _ 1 \cdot u _ {11}$,其中 $L _ {11}=1,u _ {11}=A _ {11},L _ {k1}=\frac{A _ {k1}}{A _ {11}}$

Up-looking算法

用于解决实对称矩阵Cholesky分解

由对称性可知,只需要沿主对角线依次求 $L$ 的 $k$ 阶顺序主子阵 $L_k$

$$
L _ {k-1}\hat{\boldsymbol{l}} _ k=\boldsymbol{a} _ k(1:k-1) \\
\left\Vert\begin{bmatrix}
\hat{\boldsymbol{l}} _ k \\
L_{kk}
\end{bmatrix}\right\Vert^2
=a_{kk}
\Rightarrow
L _ {kk}=\sqrt{a _ {kk}-\hat{\boldsymbol{l}} _ k^T \cdot \hat{\boldsymbol{l}} _ k} \\
\hat{\mathcal{L}} _ k=\mathrm{Reach} _ {G_{k-1}}(\mathcal{A} _ k)
$$

实对称矩阵Cholesky分解

$$
A=A^T \Rightarrow A=LL^T
$$

考虑:

$$
A=\begin{bmatrix}
x & \boldsymbol{v}^T \\
\boldsymbol{v} & B
\end{bmatrix}=
\begin{bmatrix}
1 & \\
\frac{\boldsymbol{v}}{x} & I
\end{bmatrix}
\begin{bmatrix}
x & \boldsymbol{v}^T \\
& B-\frac{\boldsymbol{v}\boldsymbol{v}^T}{x}
\end{bmatrix}
=
\begin{bmatrix}
1 & \\
\frac{\boldsymbol{v}}{x} & I
\end{bmatrix}
\begin{bmatrix}
x & \\
& B-\frac{\boldsymbol{v}\boldsymbol{v}^T}{x}
\end{bmatrix}
\begin{bmatrix}
1 & \frac{\boldsymbol{v}^T}{x} \\
& I
\end{bmatrix}
$$

参考文献

并行计算

Cholesky 分解(一) - Jinyu Li

SVD(奇异值分解)小结 - EndlessCoding - 博客园

https://xuzhongxing.github.io/multifrontal.pdf

第十一章 霍夫曼排序 · FPGA并行编程

稀疏矩阵的存储格式 | Xiang的博客

数据结构之多维数组及特殊矩阵的压缩存储 | 千里之行 始于足下

稀疏矩阵压缩存储之十字链表 | 千里之行 始于足下

稀疏矩阵压缩存储之三元组 | 千里之行 始于足下

- 稀疏矩阵直接解法(补充内容1) - 喻文健.pdf