数值分析笔记（五）线性方程组解法
三角分解法
A的杜利特分解公式如下：
u 1 j = a 1 j ( j = 1 , 2 , ⋯ , n ) , l i 1 = a i 1 / u 11 ( i = 2 , 3 , ⋯ , n ) , u k j = a k j − ∑ m = 1 k − 1 l b m u m j ⇒ a k j ( j = k , k + 1 , ⋯ , n ) , l i k = ( a i k − ∑ m = 1 k − 1 l i n u m k ) / u k k ⇒ a k k ( i = k + 1 , k + 2 , ⋯ , n ) ( k = 2 , 3 , ⋯ , n ) . \begin{aligned}&u_{1j}=a_{1j}\quad(j=1,2,\cdots,n),\\&l_{i1}=a_{i1}/u_{11}\quad(i=2,3,\cdots,n) ,\\&u_{kj}=a_{kj}-\sum_{m=1}^{k-1}l_{bm}u_{mj}\Rightarrow a_{kj}\quad(j=k,k+1,\cdots,n) ,\\&l_{ik}=\left(a_{ik}-\sum_{m=1}^{k-1}l_{in}u_{mk}\right)\Big/u_{kk}\Rightarrow a_{kk}\quad(i=k+1,k+2,\cdots,n)\\&(k=2,3,\cdots,n).\end{aligned} u1j=a1j(j=1,2,⋯,n),li1=ai1/u11(i=2,3,⋯,n),ukj=akj−m=1∑k−1lbmumj⇒akj(j=k,k+1,⋯,n),lik=(aik−m=1∑k−1linumk)/ukk⇒akk(i=k+1,k+2,⋯,n)(k=2,3,⋯,n).
楚列斯基分解
对于n阶（n>1）对称正定矩阵，楚列斯基分解 A = L ∗ L T A=L*L^T A=L∗LT，是唯一的，即
( a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋮ a n 1 a n 2 ⋯ a m ) = ( l 11 l 21 l 22 ⋮ ⋮ ⋱ l n 1 l n 2 ⋯ l m ) ( l 11 l 21 ⋯ l n 1 l 22 ⋯ l n 2 ⋱ ⋮ l m ) , \begin{pmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&&\vdots\\a_{n1}&a_{n2}&\cdots&a_{m}\end{pmatrix}=\begin{pmatrix}l_{11}\\l_{21}&l_{22}\\\vdots&\vdots&\ddots\\l_{n1}&l_{n2}&\cdots&l_{m}\end{pmatrix}\begin{pmatrix}l_{11}&l_{21}&\cdots&l_{n1}\\&l_{22}&\cdots&l_{n2}\\&&\ddots&\vdots\\&&&l_{m}\end{pmatrix}, a11a21⋮an1a12a22⋮an2⋯⋯⋯a1na2n⋮am = l11l21⋮ln1l22⋮ln2⋱⋯lm l11l21l22⋯⋯⋱ln1ln2⋮lm ,
且
{ l k k = a k k − ∑ m = 1 k − 1 l k m 2 , l i k = ( a i k − ∑ m = 1 k − 1 l i m l k m ) / l k k ( i = k + 1 , k + 2 , ⋯ , n ) \begin{aligned}&\begin{cases}l_{kk}&=\sqrt{a_{kk}-\sum_{m=1}^{k-1}l_{km}^2} ,\\l_{ik}&=\left(a_{ik}-\sum_{m=1}^{k-1}l_{im}l_{km}\right)/l_{kk}&(i=k+1,k+2,\cdots,n)\end{cases}\end{aligned} ⎩ ⎨ ⎧lkklik=akk−∑m=1k−1lkm2,=(aik−∑m=1k−1limlkm)/lkk(i=k+1,k+2,⋯,n)
向量范数
∥ x ∥ 1 = ∑ i = 1 n ∣ x i ∣ , ∥ x ∥ 2 = ∑ i = 1 n x i 2 , ∥ x ∥ ∞ = max 1 ⩽ i ⩽ n ∣ x i ∣ , \begin{gathered} \parallel x\parallel_1=\sum_{i=1}^n\mid x_i\mid, \\ \parallel x\parallel_2=\sqrt{\sum_{i=1}^nx_i^2} , \\ \parallel x\parallel_\infty=\max_{1\leqslant i\leqslant n}\mid x_i\mid, \end{gathered} ∥x∥1=i=1∑n∣xi∣,∥x∥2=i=1∑nxi2,∥x∥∞=1⩽i⩽nmax∣xi∣,
矩阵范数
∥ A ∥ 1 = max 1 ⩽ j ⩽ n ∑ i = 1 n ∣ a i j ∣ , 列范数 ∥ A ∥ ∞ = max 1 ⩽ i ⩽ n ∑ j = 1 n ∣ a i j ∣ , 行函数 ∥ A ∥ 2 = λ max ( A T A ) , 谱范数 ∥ A ∥ F = ∑ i = 1 n ∑ j = 1 n a i j 2 . F − 范数 \begin{gathered} \parallel A\parallel_{1}=\max_{1\leqslant j\leqslant n}\sum_{i=1}^{n}\mid a_{ij}\mid, 列范数\\ \parallel A\parallel_{\infty}=\max_{1\leqslant i\leqslant n}\sum_{j=1}^{n}\mid a_{ij}\mid , 行函数\\ \parallel A\parallel_{2}=\sqrt{\lambda_{\max}(A^{\mathrm{T}}A)} , 谱范数\\ \parallel A\parallel_F=\sqrt{\sum_{i=1}^n\sum_{j=1}^na_{ij}^2}. F-范数 \end{gathered} ∥A∥1=1⩽j⩽nmaxi=1∑n∣aij∣,列范数∥A∥∞=1⩽i⩽nmaxj=1∑n∣aij∣,行函数∥A∥2=λmax(ATA),谱范数∥A∥F=i=1∑nj=1∑naij2.F−范数
矩阵A的条件数
C o n d ( A ) = ∥ A − 1 ∥ ∥ A ∥ \mathrm{Cond}(A)=\parallel A^{-1}\parallel\parallel A\parallel Cond(A)=∥A−1∥∥A∥
简单迭代法
设有n阶线性方程组 A x = b Ax=b Ax=b， A A A为n阶非奇异矩阵， A x = b Ax=b Ax=b等价变形为 x = B x + g x=Bx+g x=Bx+g，给定初始向量 x ( 0 ) x^{(0)} x(0)可得到
x ( k + 1 ) = B x ( k ) + g ( k = 0 , 1 , ⋯ ) x^{(k+1)}=Bx^{(k)}+g\quad(k=0,1,\cdots) x(k+1)=Bx(k)+g(k=0,1,⋯)
若向量序列收敛，其收敛的向量为原方程组的解。其收敛的充要条件是谱半径 ρ ( B ) < 1 \rho(B) < 1 ρ(B)<1.
如果在计算第 i i i个分量 x i ( k + 1 ) x_i^{(k+1)} xi(k+1)，前面的 i − 1 i-1 i−1个分量用最新的 x 1 ( k + 1 ) x_1^{(k+1)} x1(k+1)， x 2 ( k + 1 ) x_2^{(k+1)} x2(k+1)…， x i − 1 ( k + 1 ) x_{i-1}^{(k+1)} xi−1(k+1)
而不是 x 1 ( k ) x_1^{(k)} x1(k)， x 2 ( k ) x_2^{(k)} x2(k)，…， x i − 1 ( k ) x_{i-1}^{(k)} xi−1(k)，则是简单迭代法对应的高斯-赛德尔迭代法。
当简单迭代法的迭代矩阵 B B B满足 ∥ B ∥ 1 < 1 \parallel B\parallel_{1} < 1 ∥B∥1<1或 ∥ B ∥ ∞ < 1 \parallel B\parallel_{\infty} < 1 ∥B∥∞<1，对应的对应的高斯-赛德尔迭代法关于任意初始向量收敛。
雅可比迭代法
设有n阶线性方程组 A x = b Ax=b Ax=b， A A A为n阶非奇异矩阵，且对角元 a i i ≠ 0 ( i = 1 , 2 , 3 , . . . , n ) a_{ii} \neq 0 (i=1,2,3,...,n) aii=0(i=1,2,3,...,n)
将A如下分解，A=L+D+U，即
A = ( 0 a 21 0 ⋮ ⋮ ⋱ a n 1 a n 2 ⋯ 0 ) + ( a 11 a 22 ⋱ a n n ) + ( 0 a 12 ⋯ a 1 n 0 ⋯ a 2 n ⋱ ⋮ 0 ) , A=\begin{pmatrix}0\\a_{21}&0\\\vdots&\vdots&\ddots\\a_{n1}&a_{n2}&\cdots&0\end{pmatrix}+\begin{pmatrix}a_{11}\\&a_{22}\\&&\ddots\\&&&a_{nn}\end{pmatrix}+\begin{pmatrix}0&a_{12}&\cdots&a_{1n}\\&0&\cdots&a_{2n}\\&&\ddots&\vdots\\&&&0\end{pmatrix}, A= 0a21⋮an10⋮an2⋱⋯0 + a11a22⋱ann + 0a120⋯⋯⋱a1na2n⋮0 ,
A x = b Ax=b Ax=b等价于 ( L + D + U ) x = b (L+D+U)x=b (L+D+U)x=b,
整理得，
x = − D − 1 ( L + U ) x + D − 1 b x=-D^{-1}\left(L+U\right)x+D^{-1}b x=−D−1(L+U)x+D−1b
记 B J = − D − 1 ( L + U ) , g = D − 1 b B_J=-D^{-1}\left(L+U\right),g=D^{-1}b BJ=−D−1(L+U),g=D−1b，则构造公式
x ( k + 1 ) = B J x ( k ) + g ( k = 0 , 1 , ⋅ ⋅ ⋅ ) x^{(k+1)}=B_Jx^{(k)}+g\quad(k=0,1,\cdotp\cdotp\cdotp) x(k+1)=BJx(k)+g(k=0,1,⋅⋅⋅)
为雅可比迭代法，称
B J = − D − 1 ( L + U ) = ( 0 − a 12 a 11 ⋯ − a 1 n a 11 − a 21 a 22 0 ⋯ − a 2 n a 22 ⋮ ⋮ ⋱ ⋮ − a n 1 a n n − a n 2 a n n ⋯ 0 ) B_J=-D^{-1}(L+U)=\begin{pmatrix}0&-\frac{a_{12}}{a_{11}}&\cdots&-\frac{a_{1n}}{a_{11}}\\\\-\frac{a_{21}}{a_{22}}&0&\cdots&-\frac{a_{2n}}{a_{22}}\\\vdots&\vdots&\ddots&\vdots\\\\-\frac{a_{n1}}{a_{nn}}&-\frac{a_{n2}}{a_{nn}}&\cdots&0\end{pmatrix} BJ=−D−1(L+U)= 0−a22a21⋮−annan1−a11a120⋮−annan2⋯⋯⋱⋯−a11a1n−a22a2n⋮0
为雅可比矩阵。
雅可比迭代法关于任意初始向量 x ( 0 ) x^{(0)} x(0)收敛的充要条件是 ρ ( B j ) < 1 \rho(B_{j}) < 1 ρ(Bj)<1.
其对应的高斯-赛德尔迭代法为
x ( k + 1 ) = − ( D + L ) − 1 U x ( k ) + ( D + L ) − 1 b x^{(k+1)}=- (D+L)^{-1}Ux^{(k)}+(D+L)^{-1}b x(k+1)=−(D+L)−1Ux(k)+(D+L)−1b
若系数矩阵A严格对角占优，高斯-赛德尔迭代法对于任意初始向量 x ( 0 ) x^{(0)} x(0)收敛。
若系数矩阵A对称正定，高斯-赛德尔迭代法对于任意初始向量 x ( 0 ) x^{(0)} x(0)收敛。