Mengzelev's Blog

算法导论学习笔记-矩阵运算

Word count: 724 / Reading time: 3 min
2018/12/18 Share

求解线性方程组

$$Ax=b$$
欠定的(underdetermined):方程的数目少于未知变量数目$n$,则该线性方程组为欠定的
超定的(overdetermined):方程数目超过未知变量数目$n$
非奇异矩阵:$A$的秩等于未知变量的个数$n$

LUP分解

思想:找出3个$n\times n$矩阵$L,U,P$,满足$PA=LU$,其中
$L$是一个单位下三角矩阵
$U$是一个上三角矩阵
$P$是一个置换矩阵
每一个非奇异矩阵$A$都会有这样一种分解
$$Ax=b$$
$$PAx=Pb$$
$$LUx=Pbx$$
求解两个三角线性系统
下三角系统$Ly=Pb$
上三角系统$Ux=y$

正向替换与方向替换

可在$\Theta(n^2)$时间内求解下三角系统

置换阵$P$可以用数组$\pi[1..n]$表示
$$P_{i,j}=
\begin{cases}
1 & (j == \pi[i])\
0 & (j\neq\pi[i])
\end{cases}
$$
从第一个式子开始正向替换,可以得到
$$y_i=b_{\pi[i]}-\sum\limits_{j=1}^{i-1}l_{ij}y_i$$

反向替换同理,最终可以得到
$$x_i=(y_i-\sum\limits_{j=i+1}^{n}u_{ij}x_j)/u_{ii}$$

LU分解计算

Gauss消元法:

  • 行消元得到的行梯阵即$U$
  • $L$由消去变量所用的行的乘数组成


可以看成$$a_{ij}=a_{ij}-\frac{a_{ik}a_{kj}}{a_{kk}}$$

运行时间$\Theta(n^3)$

LUP分解计算

在LU分解的基础上,为了保证除数不为0和减少数值不稳定,每次选择该列中具有最大绝对值的元素,交换到对角元的位置

运行时间$\Theta(n^3)$

矩阵求逆

LUP分解可以用于计算逆矩阵(废话,高斯消元可以,LUP当然可以)$$AX_{i}=e_i$$

矩阵乘法和矩阵求逆具有相同的时间复杂度

证明时间复杂度相同:两个问题都能在O(另一个问题算法的时间复杂度)时间内解决

  • 证明的时候可能会用到分块阵的思想来转化问题

对称正定阵

引理28.3:任何对称正定矩阵都是非奇异矩阵
任何对称正定矩阵都有逆矩阵。

引理28.4:如果$A$是一个对称正定矩阵,那么$A$的每一个主子矩阵都是对称正定的。

舒尔补:矩阵$A$关于主子矩阵$A_k$的舒尔补为$S=C-B{A_k}^{-1}B^T$。其中,$A$为对称正定阵且
$$A=\left[
\begin{matrix}
A_k & B^T \
B & C
\end{matrix}
\right]$$

舒尔补定理:如果$A$是一个对称正定矩阵,$A_k$是$A$的$k\times k$主子矩阵,那么$A$关于$A_k$的舒尔补是对称正定的。

推论28.6:一个对称正定矩阵的LU分解永远不会出现除数为0的情形

最小二乘逼近

就是看上去很厉害实际上真的很厉害的曲线拟合

CATALOG
  1. 1. 求解线性方程组
    1. 1.1. LUP分解
    2. 1.2. 正向替换与方向替换
    3. 1.3. LU分解计算
    4. 1.4. LUP分解计算
  2. 2. 矩阵求逆
  3. 3. 对称正定阵
  4. 4. 最小二乘逼近