Spectral Radius$\rho$
矩阵谱半径=特征值中最大的一个的绝对值

性质：对于n,n矩阵，$\rho <||A||$

A收敛：A的k次是0矩阵，。

求解线性方程组

Jacobi Iterative Method

递推关系是根据原方程，

用x2,x3,…xn表示x1，得到x1的递推式

用x1,x3,…xn表示x2，得到x2的递推式
。。。。。

最后给一个初始的矩阵 X 0 X_0 X0​，然后迭代。

用前一次x1,…xi-1,xi+1,…xn算后一次的xi

直到 ∣ ∣ X i − X i − 1 ∣ ∣ ∞ < T O L ||X_i-X_{i-1}||_\infty∣∣Xi​−Xi−1​∣∣∞​<TOL，就是误差最大的xi也小于给定的误差。

Gauss - Seidel Iterative Method

递推式和 Jacobi Iterative Method的一样。输入的初始矩阵 X 0 X_0 X0​也一样。

不同的在于对x2,…xn迭代的时候，带的x1,…xn是这一次已经算出来的，而非上一次的。

x i ( k ) = 1 a i i ( − a i 1 x 1 ( k ) − . . . a i , i − 1 x i − 1 ( k ) − a i , i + 1 x i + 1 ( k − 1 ) − . . . a i , n x n ( k − 1 ) + b i ) x_i^{(k)}=\frac{1}{a_{ii}}(-a_{i1}x_1^{(k)}-...a_{i,i-1}x_{i-1}^{(k)}-a_{i,i+1}x_{i+1}^{(k-1)}-...a_{i,n}x_n^{(k-1)}+b_i) xi(k)​=aii​1​(−ai1​x1(k)​−...ai,i−1​xi−1(k)​−ai,i+1​xi+1(k−1)​−...ai,n​xn(k−1)​+bi​)

而jacobi法：

x i ( k ) = 1 a i i ( − a i 1 x 1 ( k − 1 ) − . . . a i , i − 1 x i − 1 ( k − 1 ) − a i , i + 1 x i + 1 ( k − 1 ) − . . . a i , n x n ( k − 1 ) + b i ) x_i^{(k)}=\frac{1}{a_{ii}}(-a_{i1}x_1^{(k-1)}-...a_{i,i-1}x_{i-1}^{(k-1)}-a_{i,i+1}x_{i+1}^{(k-1)}-...a_{i,n}x_n^{(k-1)}+b_i) xi(k)​=aii​1​(−ai1​x1(k−1)​−...ai,i−1​xi−1(k−1)​−ai,i+1​xi+1(k−1)​−...ai,n​xn(k−1)​+bi​)

Relaxation Methods

对Gauss-Seidel法进一步变形。

x i ( k ) = 1 a i i ( − a i 1 x 1 ( k − 1 ) − . . . a i , i − 1 x i − 1 ( k − 1 ) − a i , i + 1 x i + 1 ( k − 1 ) − . . . a i , n x n ( k − 1 ) + b i ) x_i^{(k)}=\frac{1}{a_{ii}}(-a_{i1}x_1^{(k-1)}-...a_{i,i-1}x_{i-1}^{(k-1)}-a_{i,i+1}x_{i+1}^{(k-1)}-...a_{i,n}x_n^{(k-1)}+b_i) xi(k)​=aii​1​(−ai1​x1(k−1)​−...ai,i−1​xi−1(k−1)​−ai,i+1​xi+1(k−1)​−...ai,n​xn(k−1)​+bi​)

x i ( k ) − x i ( k − 1 ) = 1 a i i ( − a i 1 x 1 ( k − 1 ) − . . . a i , i − 1 x i − 1 ( k − 1 ) − a i , i x i ( k − 1 ) − a i , i + 1 x i + 1 ( k − 1 ) − . . . a i , n x n ( k − 1 ) + b i ) x_i^{(k)}-x_i^{(k-1)}=\frac{1}{a_{ii}}(-a_{i1}x_1^{(k-1)}-...a_{i,i-1}x_{i-1}^{(k-1)}-a_{i,i}x_{i}^{(k-1)}-a_{i,i+1}x_{i+1}^{(k-1)}-...a_{i,n}x_n^{(k-1)}+b_i) xi(k)​−xi(k−1)​=aii​1​(−ai1​x1(k−1)​−...ai,i−1​xi−1(k−1)​−ai,i​xi(k−1)​−ai,i+1​xi+1(k−1)​−...ai,n​xn(k−1)​+bi​)

然后迭代式为
x i ( k ) = x i ( k − 1 ) + w a i i ( − a i 1 x 1 ( k − 1 ) − . . . a i , i − 1 x i − 1 ( k − 1 ) − a i , i x i ( k − 1 ) − a i , i + 1 x i + 1 ( k − 1 ) − . . . a i , n x n ( k − 1 ) + b i ) x_i^{(k)}=x_i^{(k-1)}+\frac{w}{a_{ii}}(-a_{i1}x_1^{(k-1)}-...a_{i,i-1}x_{i-1}^{(k-1)}-a_{i,i}x_{i}^{(k-1)}-a_{i,i+1}x_{i+1}^{(k-1)}-...a_{i,n}x_n^{(k-1)}+b_i) xi(k)​=xi(k−1)​+aii​w​(−ai1​x1(k−1)​−...ai,i−1​xi−1(k−1)​−ai,i​xi(k−1)​−ai,i+1​xi+1(k−1)​−...ai,n​xn(k−1)​+bi​)

收敛更快。

w<1,Under- Relaxation methods

w=1,Guass-Seidel法

w>1,SOR methods

根收敛问题

比较常见的判断是否收敛的方法：

1.谱半径<1。

证明的话： T x = λ x , T k = λ k x Tx=\lambda x,T^k=\lambda^kx Tx=λx,Tk=λkx

x ( k ) = T x ( k − 1 ) + c = T ( T x ( k − 1 ) + c ) + c = . . . = T k x 0 + ( T k − 1 + . . . T + I ) c x^{(k)}=Tx^{(k-1)}+c=T(Tx^{(k-1)}+c)+c=...=T^kx_0+(T^{k-1}+...T+I)c x(k)=Tx(k−1)+c=T(Tx(k−1)+c)+c=...=Tkx0​+(Tk−1+...T+I)c

将T换成$\lambda$，求和发现小于1才收敛。

所以特征值的绝对值小于1

2. A ∞ = 0 A^\infty=0 A∞=0

证明的话：x-x*=Tx+c-(Tx*+c)=T(x-x*)

迭代一次就乘一个T,因此要收敛只能A->0

收敛速度和精度的判断

略

3.Relax法中0$0<\rho <1$时收敛

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！