数值分析笔记(五)线性方程组解法

admin2024-07-09  6

三角分解法
数值分析笔记(五)线性方程组解法,在这里插入图片描述,第1张

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=akjm=1k1lbmumjakj(j=k,k+1,,n),lik=(aikm=1k1linumk)/ukkakk(i=k+1,k+2,,n)(k=2,3,,n).

楚列斯基分解

对于n阶(n>1)对称正定矩阵,楚列斯基分解 A = L ∗ L T A=L*L^T A=LLT,是唯一的,即
( 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}, a11a21an1a12a22an2a1na2nam = l11l21ln1l22ln2lm l11l21l22ln1ln2lm ,

{ 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=akkm=1k1lkm2 ,=(aikm=1k1limlkm)/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} x1=i=1nxi,x2=i=1nxi2 ,x=1inmaxxi,
矩阵范数
∥ 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} A1=1jnmaxi=1naij,列范数A=1inmaxj=1naij,行函数A2=λmax(ATA) ,谱范数AF=i=1nj=1naij2 .F范数
矩阵A的条件数
C o n d ( A ) = ∥ A − 1 ∥ ∥ A ∥ \mathrm{Cond}(A)=\parallel A^{-1}\parallel\parallel A\parallel Cond(A)=∥A1∥∥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 i1个分量用最新的 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)} xi1(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)} xi1(k),则是简单迭代法对应的高斯-赛德尔迭代法。

当简单迭代法的迭代矩阵 B B B满足 ∥ B ∥ 1 < 1 \parallel B\parallel_{1} < 1 B1<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= 0a21an10an20 + a11a22ann + 0a120a1na2n0 ,
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=D1(L+U)x+D1b
B J = − D − 1 ( L + U ) , g = D − 1 b B_J=-D^{-1}\left(L+U\right),g=D^{-1}b BJ=D1(L+U),g=D1b,则构造公式
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=D1(L+U)= 0a22a21annan1a11a120annan2a11a1na22a2n0
为雅可比矩阵。

雅可比迭代法关于任意初始向量 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)收敛。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!