4.2 LU分解
4.2.1 高斯消去法
例1. 用高斯消去法求解：\(\begin{bmatrix}2&-4&6\\4&-9&2\\1&-1&3 \end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix}3\\5\\4 \end{bmatrix}\)
首先写出增广矩阵 \(\begin{bmatrix}2&-4&6&3\\4&-9&2&5\\1&-1&3&4\end{bmatrix}\)
然后对第二行第三行首元进行处理 \(\begin{bmatrix}2&-4&6&3\\0&-1&-10&-1\\0&1&0&\frac{5}{2}\end{bmatrix}\)
再处理得到上三角 \(\begin{bmatrix}2&-4&6&3\\0&-1&-10&-1\\0&0&-10&\frac{3}{2}\end{bmatrix}\)
最终解出\(x_3,x_2,x_1\)
4.2.2 基本消去矩阵
定义：设有一\(n\)维列向量\(\begin{pmatrix}a_1,\cdots,a_k,a_{k+1},\cdots,a_n\end{pmatrix}^T\)，其中\(a_k\ne0\)，把它作为主元，令\(m_i=\frac{a_i}{a_k}\)称他们为消去因子，矩阵
\(M_k=\begin{bmatrix}1&\cdots&0&0&\cdots&0\\ \vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\0&\cdots&1&0&\cdots&0\\0&\cdots&-m_{k+1}&1&\cdots&0\\\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&\cdots&-m_{n}&0&\cdots&1\end{bmatrix}\)
称为基本消去矩阵，满足
\(\begin{bmatrix}1&\cdots&0&0&\cdots&0\\ \vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\0&\cdots&1&0&\cdots&0\\0&\cdots&-m_{k+1}&1&\cdots&0\\\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\ 0&\cdots&-m_{n}&0&\cdots&1\end{bmatrix}\begin{bmatrix}a_1\\\vdots \\a_k\\a_{k+1}\\\vdots\\a_n\end{bmatrix}=\begin{bmatrix}a_1\\\vdots \\a_k\\0\\\vdots\\0\end{bmatrix}\)
小指标在前，大指标在后，可以并起来，如
\(M_1=\begin{bmatrix}1&0&0\\-2&1&0\\1&0&1 \end{bmatrix}\) \(M_2=\begin{bmatrix}1&0&0\\0&1&0\\0&\frac{1}{2}&1 \end{bmatrix}\)
\(M_1M_2=\begin{bmatrix}1&0&0\\-2&1&0\\1&\frac{1}{2}&1 \end{bmatrix}\)
4.2.3 LU分解
借助基本消去矩阵，高斯消去法可以按照如下方式描述：
\(M_{n-1}\cdots M_2M_1Ax=Ux=M_{n-1}\cdots M_2M_1b\)，其中\(U\)是一个上三角矩阵。
由于大指标在前，\(M_{n-1}\cdots M_2M_1\)无法直接计算，因此令\(M=M_{n-1}\cdots M_2M_1\)
则\(MA=U,A=M^{-1}U=M_1^{-1}M_2^{-1}\cdots M_{n-1}^{-1}U=L_1L_{2}\cdots L_{n-1}U=LU\)
\(U=M_{n-1}\cdots M_2M_1A\) \(L=L_1L_{2}\cdots L_{n-1}\)
例3. 写出矩阵\(A=\begin{bmatrix}1&3&2&1\\2&4&7&4\\4&8&3&1\\9&9&6&4 \end{bmatrix}\)的\(LU\)分解。
\(M_1=\begin{bmatrix}1&0&0&0\\-2&1&0&0\\-4&0&1&0\\-9&0&0&1 \end{bmatrix},M_1A=\begin{bmatrix}1&3&2&1\\0&-2&3&2\\0&-4&-5&-3\\0&-18&-12&-5 \end{bmatrix}\)
\(M_2=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&-2&1&0\\0&-9&0&1 \end{bmatrix},M_2M_1A=\begin{bmatrix}1&3&2&1\\0&-2&3&2\\0&0&-11&-7\\0&0&-39&-23 \end{bmatrix}\)
\(M_3=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&-\frac{39}{11}&1 \end{bmatrix},M_3M_2M_1A=\begin{bmatrix}1&3&2&1\\0&-2&3&2\\0&0&-11&-7\\0&0&0&\frac{20}{11} \end{bmatrix}\)
\(L=\begin{bmatrix}1&0&0&0\\2&1&0&0\\4&2&1&0\\9&9&\frac{39}{11}&1 \end{bmatrix},U=\begin{bmatrix}1&3&2&1\\0&-2&3&2\\0&0&-11&-7\\0&0&0&\frac{20}{11} \end{bmatrix}\)
4.3 列主元高斯消去法
考察第1列，将绝对值最大的元素换到\(a_{11}\)的位置，
考察第2列，将绝对值最大的元素换到\(a_{22}\)的位置，\(\cdots\)
最后得到\(M_{n-1}P_{n-1}\cdots M_1P_1Ax=Ux=M_{n-1}P_{n-1}\cdots M_1P_1b\)
令\(M=M_{n-1}P_{n-1}\cdots M_1P_1\)，则\(MA=U\Rightarrow A=\widetilde{L}U,\widetilde{L}=M^{-1}\)
其中\(\widetilde{L}\)不一定是下三角矩阵
若令\(P=P_{n-1}\cdots P_1\)，则\(PA=PM^{-1}U=LU\)
\(L=PM^{-1}\)，此时\(L\)是一个下三角矩阵。
这种分解称为\(PLU\)分解。
例5. 写出求解\(\begin{bmatrix}2&-4&6\\4&-9&2\\1&-1&3 \end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix}3\\5\\4 \end{bmatrix}\)时的\(P,L,U\)
\(P_1=\begin{bmatrix}0&1&0\\1&0&0\\0&0&1 \end{bmatrix}\)
\(P_1Ax=\begin{bmatrix}4&-9&2\\2&-4&6\\1&-1&3 \end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix}5\\3\\4 \end{bmatrix}=P_1b\)
\(M_1=\begin{bmatrix}1&0&0\\-\frac{1}{2}&1&0\\-\frac{1}{4}&0&1 \end{bmatrix}\)
\(M_1P_1Ax=\begin{bmatrix}4&-9&2\\0&\frac{1}{2}&5\\0&\frac{5}{4}&\frac{5}{2} \end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix}5\\\frac{1}{2}\\ \frac{11}{4} \end{bmatrix}\)
\(P_2=\begin{bmatrix}1&0&0\\0&0&1\\0&1&0 \end{bmatrix}\)
\(P_2M_1P_1Ax=\begin{bmatrix}4&-9&2\\0&\frac{5}{4}&\frac{5}{2}\\0&\frac{1}{2}&5 \end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix}5\\\frac{11}{4}\\\frac{1}{2} \end{bmatrix}\)
\(M_2=\begin{bmatrix}1&0&0\\0&1&0\\0&-\frac{2}{5}&1 \end{bmatrix}\)
\(M_2P_2M_1P_1Ax=\begin{bmatrix}4&-9&2\\0&\frac{5}{4}&\frac{5}{2}\\0&0&4 \end{bmatrix}\begin{bmatrix}x_1\\x_2\\x_3 \end{bmatrix}=\begin{bmatrix}5\\\frac{11}{4}\\-\frac{3}{5} \end{bmatrix}\)
\(M=M_2P_2M_1P_1=\begin{bmatrix}0&1&0\\0&-\frac{1}{4}&1\\1&-\frac{2}{5}&-\frac{2}{5} \end{bmatrix}\) \(M^{-1}=\begin{bmatrix}\frac{1}{2}&\frac{2}{5}&1\\1&0&0\\\frac{1}{4}&1&0\end{bmatrix}\)
\(P=P_2P_1=\begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix}\begin{bmatrix}0&1&0\\1&0&0\\0&0&1\end{bmatrix}=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}\)
\(L=PM^{-1}=\begin{bmatrix}1&0&0\\\frac{1}{4}&1&0\\\frac{1}{2}&\frac{2}{5}&1\end{bmatrix}\) \(U=\begin{bmatrix}4&-9&2\\0&\frac{5}{4}&\frac{5}{2}\\0&0&4 \end{bmatrix}\)
4.3.7 无需选主元的系统
1）对角占优矩阵
如果矩阵A的元素满足\(\sum\limits_{i=1,i\ne j}^{n}|a_{ij}|<|a_{jj}|,j=1,2,\cdots,n\)称矩阵A是严格对角占优。
严格对角占优矩阵一定是非奇异的。
2）对称正定矩阵
满足下列条件的矩阵是对称正定矩阵(SPD)：\(A=A^T,x^TAx>0,\forall x\)
一个矩阵是正定的，当且仅当它的顺序主子式都大于0。
如果矩阵\(A\)是严格对角占优或者对称正定矩阵，则对\(Ax=b\)使用高斯消去法使无需选主元，算法本身就是数值稳定的。
4.4.2 三对角矩阵与追赶法
假设三对角系统为
\(\begin{bmatrix}b_1&c_1\\a_2&b_2&c_2\\&a_3&b_3&c_3\\&&\ddots&\ddots&\ddots\\&&&a_{n-1}&b_{n-1}&c_{n-1}\\&&&&a_{n}&b_{n}\end{bmatrix}\)
若不需要选主元来保证数值稳定性，此时的高斯消去法非常简单。
A的LU分解为
\(L=\begin{bmatrix}1&0&\cdots&\cdots&0\\m_2&1&\ddots&\ddots&\vdots\\0&\ddots&\ddots&\ddots&\vdots\\\vdots&\ddots& m_{n-1}&1&0\\0&\cdots&0&m_n&1\end{bmatrix}\) \(U=\begin{bmatrix}d_1&c_1&\cdots&\cdots&0\\0&d_2&c_2&\ddots&\vdots\\0&\ddots&\ddots&\ddots&\vdots\\\vdots&\ddots&\ddots&d_{n-1}&c_{n-1}\\0&\cdots&0&0&d_n\end{bmatrix}\)
又\(Ly=b,Ux=y\)，消去时下标从小到大，回代求解时下标从大到小，因此形象地称此时的高斯消去法为追赶法。
4.5 逆矩阵相关
4.5.1
一般情况下，不推荐直接使用\(A^{-1}\)进行计算。
几乎所有需要\(A^{-1}\)的运算都可以通过间接法来实现，比如：
\(A^{-1}b\rightarrow x=A^{-1}b,Ax=b\)
1）三角阵的逆矩阵
2）利用LU分解求一般矩阵的逆
方法一、 通过解线性方程组实现，计算流程如下
- \(A=LU\)
- \(LUX=I_n,LUx_{j}=e_j,j=1:n\)
- \(Ly_j=e_j,j=1:n\)
- \(Ux_j=y_j\)
方法二、通过逆矩阵的乘积实现，计算流程如下
- \(A=LU\)
- \(L^{-1}\)
- \(U^{-1}\)
- \(A^{-1}=(LU)^{-1}=U^{-1}L^{-1}\)
4.6 误差分析
4.6.2 向量范数
现代数学中最重要的概念非极限莫属，而极限描述的关键则是距离。
所谓的向量范数，就是为了把三维空间中距离的概念推广到n维空间。
在向量空间\(R^n\)中，定义映射
\(f=||\cdot||:R^n\rightarrow R\)
如果该映射满足：
- \(||x||\ge0,||x||=0\Leftrightarrow x=0\)
- \(||\alpha x||=|\alpha|\cdot ||x||,\alpha\in R\)
- \(||x+y||\le||x||+||y||\)
这个映射就称为\(R^n\) 空间的向量范数。
1）常用范数
- 1-范数：\(||x||_1=\sum\limits_{i=1}^{n}|x_i|\)
- 2-范数：\(||x||_2=(\sum\limits_{i=1}^{n}|x_i|^2)^\frac{1}{2}\)
- \(\infty\)-范数：\(||x||_{\infty}=\max\limits_{i}|x_i|\)
2）常用范数间的大小关系
简单的不等关系，如\(||x||_1>||x||_2>||x||_\infty\)
几个反向的不等关系：
- \(||x||_1\le\sqrt{n}||x||_2\)
- \(||x||_2\le\sqrt{n}||x||_\infty\)
- \(||x||_1\le n||x||_\infty\)
给定线性空间\(X\)上的范数\(||\cdot||_p,||\cdot||_q\)，他们等价当且仅当\(\exist c_1,c_2>0\)，使得\(c_1||x||_q\le||x||_p\le c_2||x||_q\)成立。
4.6.3 矩阵范数
1）矩阵的诱导范数
矩阵A的诱导范数\(||A||\)定义为
\(||A||=\max\limits_{x\ne0}\frac{||Ax||}{||x||}=\max\limits_{||x||=1}||Ax||\)
矩阵范数度量的是矩阵对向量的最大拉伸。
- \(||Ax||\le||A||\cdot||x||\)
- \(||AB||\le||A||\cdot||B||\)
2）矩阵的常见诱导范数及其计算
(1) 1-范数的计算公式
\(||A||_1=\max\limits_{j}\sum\limits_{i=1}^{n}|a_{ij}|\) 它是一个列范数。
(2) \(\infty\)-范数的计算公式
\(||A||_{\infty}=\max\limits_{j}\sum\limits_{i=1}^{n}|a_{ij}|\) 它是一个行范数。
(3) 2-范数的计算公式
\(||A||_{2}=\max\limits_{x\ne0}\frac{||Ax||_2}{||x||_2}=\sqrt{\rho(A^TA)}\)
\(\rho(A)\)是矩阵A的谱半径，其定义为\(\rho(A)=\max\limits_{\lambda\in\sigma(A)}|\lambda|\)，其中\(\sigma(A)\)表示A的特征值全体。由于特征值可能是复数，因此\(|\cdot|\)指的是模。
4.6.5 条件数
称\(\mbox{cond}(A)=||A||\cdot||A^{-1}||\)为矩阵A的条件数，若A是奇异矩阵，则令\(\mbox{cond}(A)=\infty\)
条件数刻画了矩阵的奇异程度。
- 对恒等矩阵，\(\mbox{cond}(I_n)=1\)
- 对任意矩阵A，\(\mbox{cond}(A)\ge1\)
- 对任意常数\(\gamma\ne0\)，\(\mbox{cond}(\gamma A)=\mbox{cond}(A)\)
- 对对角阵\(D=\mbox{diag}(d_1,d_2,\cdots,d_n)\)，条件数计算公式为\(\mbox{cond}(D)=\frac{\max\limits_{1\le i\le n}|d_i|}{\min\limits_{1\le i\le n}|d_i|}\)
- 2-范数条件数计算公式为\(\mbox{cond}(A)_2=\sqrt{\frac{\lambda_{\max}(A^TA)}{\lambda_{\min}(A^TA)}}\)
- 如果A是对称矩阵，则2-范数条件数计算公式为\(\mbox{cond}(A)_2=\frac{\lambda_{\max}}{\lambda_{\min}}\)
如果条件数太大，就称矩阵是病态矩阵，病态矩阵对应的线性系统在求解时会放大这些误差。
希尔伯特矩阵是著名的病态矩阵，其条件数大概是\(e^{3.5n}\)
\(\begin{bmatrix}1&\frac{1}{2}&\cdots&\frac{1}{n}\\\frac{1}{2}&\frac{1}{3}&\cdots&\frac{1}{n+1}\\\vdots&\vdots&\ddots&\vdots\\\frac{1}{n}&\frac{1}{n+1}&\cdots&\frac{1}{2n-1}\end{bmatrix}\)
方程组近似解可靠性的判例
方程组近似解的相对误差估计式的实用方法是将方程组\(Ax=b\)的一个近似解\(\tilde{x}\)回代到原方程组去求余量r
\(r=b-Ax\)
定理：\(\frac{||x^*-\tilde{x}||}{||x^*||}\le\mbox{cond}(A)\frac{||r||}{||b||}\)
由定理可知，使用余量r的大小来检验近似解的准确程度的办法仅对良态方程组适用。
几个常见的迭代格式
(1) Jacobi迭代格式
将线性方程组\(Ax=b\)写成分量的形式
\(\begin{cases}a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1,\\a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n=b_2,\\\vdots\\a_{n1}x_1+a_{n2}x_2+\cdots+a_{nn}x_n=b_n,\end{cases}\)
建立相应迭代格式
\(\begin{cases}x_{1}^{(k+1)}=(b_1-a_{12}x_2^{(k)}-a_{13}x_3^{(k)}-\cdots-a_{1n}x_n^{(k)})/a_{11}\\x_{2}^{(k+1)}=(b_2-a_{21}x_1^{(k)}-a_{23}x_3^{(k)}-\cdots-a_{2n}x_n^{(k)})/a_{22}\\\vdots\\x_{n}^{(k+1)}=(b_n-a_{n1}x_1^{(k)}-a_{n2}x_2^{(k)}-\cdots-a_{nn-1}x_{n-1}^{(k)})/a_{nn}\end{cases}\)
\(J=-D^{-1}(L+U)\)，称J为Jacobi迭代矩阵。
Jacobi迭代格式收敛的充要条件是\(\rho(J)<1\)。
严格对角占优矩阵Jacobi迭代格式收敛。
(2) Gauss-Seidel迭代格式
\(\begin{cases}x_{1}^{(k+1)}=(b_1-a_{12}x_2^{(k)}-a_{13}x_3^{(k)}-\cdots-a_{1n}x_n^{(k)})/a_{11}\\x_{2}^{(k+1)}=(b_2-a_{21}x_1^{(k+1)}-a_{23}x_3^{(k)}-\cdots-a_{2n}x_n^{(k)})/a_{22}\\\vdots\\x_{n}^{(k+1)}=(b_n-a_{n1}x_1^{(k+1)}-a_{n2}x_2^{(k+1)}-\cdots-a_{nn-1}x_{n-1}^{(k+1)})/a_{nn}\end{cases}\)
\(G=-(D+L)^{-1}U\)，称G为Gauss-Seidel迭代矩阵。
Gauss-Seidel迭代格式收敛的充要条件是\(\rho(G)<1\)。
严格对角占优矩阵Gauss-Seidel迭代格式收敛。
(3) 逐次超松弛法(SOR方法)
\(\begin{cases}x_{1}^{(k+1)}=(1-\omega)x_1^{(k)}+\omega(b_1-a_{12}x_2^{(k)}-a_{13}x_3^{(k)}-\cdots-a_{1n}x_n^{(k)})/a_{11}\\x_{2}^{(k+1)}=(1-\omega)x_2^{(k)}+\omega(b_2-a_{21}x_1^{(k+1)}-a_{23}x_3^{(k)}-\cdots-a_{2n}x_n^{(k)})/a_{22}\\\vdots\\x_{n}^{(k+1)}=(1-\omega)x_n^{k}+\omega(b_n-a_{n1}x_1^{(k+1)}-a_{n2}x_2^{(k+1)}-\cdots-a_{nn-1}x_{n-1}^{(k+1)})/a_{nn}\end{cases}\)
\(S_\omega=(D+\omega L)^{-1}[(1-\omega)D-\omega U]\)
Gauss-Seidel迭代格式收敛的充要条件是\(\rho(S_\omega)<1\)。
若A是对称正定矩阵，且\(\omega\in(0,2)\)，则SOR方法收敛。
标签：begin,end,线性方程组,cdots,bmatrix,frac,直接,&-,第四章 From： https://www.cnblogs.com/tseyublog/p/16938923.html