第3章 线性方程组的迭代解法

用迭代法阶线性方程组

第4章 解线性方程组的迭代法直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是n3 数量级，存储量为n2量级，这在n比较小的时候还比较合适(n<400),但是对于现 在的很多实际问题，往往要我们求解很大的n的矩阵，而且这些矩阵往往是系数矩阵 就是这些矩阵含有大量的0元素。对于这类的矩阵，在用直接法时就会耗费大量的时 间和存储单元。因此我们有必要引入一类新的方法：迭代法。 迭代法具有的特点是速度快。与非线性方程的迭代方法一样，需要我们构造一 个等价的方程，从而构造一个收敛序列，序列的极限值就是方程组的根

用迭代法阶线性方程组

对方程组 如：令

Ax = b

做等价变换

x = Gx + g

A = M N ,则 Ax = b ( M N ) x = b Mx = b + Nx x = M 1 Nx + M 1b则，我们可以构造序列 若 同时：

x ( k +1) = G x ( k ) + g

x ( k ) → x * x* = G x * + g Ax* = b

x ( k +1) x* = Gx ( k ) Gx* = G ( x ( k ) x*) = = G k +1 ( x ( 0 ) x*)

所以，序列收敛

Gk → 0

与初值的选取无关

用迭代法阶线性方程组

定义6.1:(收敛矩阵) 定理： 由

Gk → 0矩阵G为收敛矩阵，当且仅当G的谱半径<1

G k → 0 ρ (G ) < 1知，若有某种范数

ρ (G ) < G

G

p

<1

则，迭代收敛

用迭代法阶线性方程组

6.1 Jacobi迭代 迭代

a11 x1 + + a1n xn = b1 a x + + a x = b nn n n n1 1 x1 = x = 2 xn = 1 (a12 x2 + + a1n xn b1 ) a11 1 (a21 x1 + a23 x3 + + a1n xn b2 ) a22 1 (an1 x1 + + an n 1 xn 1 bn ) ann

用迭代法阶线性方程组

( k +1) x1 x ( k +1) 2 ∴ ( k +1) xn 格式很简单：

1 (k ) (k ) (a12 x2 + + a1n xn b1 ) = a11 1 (k ) (k ) (k ) (a21 x1 + a23 x3 + + a1n xn b2 ) = a22 1 (k ) (k ) = (an1 x1 + + an n 1 xn 1 bn ) ann

xi

( k +1)

n 1 i 1 (k ) (k ) = (∑ aij x j + ∑ aij x j bi ) aii j =1 j =i +1

用迭代法阶线性方程组

Jacobi迭代算法 1、输入系数矩阵A和向量b,和误差控制eps 2、x1={0,0,…..,0} , x2={1,1,…..,1} //赋初值 3、while( ||A*x2-b||>eps) { x1=x2; for(i=0;i<n;i++) { x2[i]=0; for(j=0;j<i;j++) { x2[i] += A[i][j]*x1[j] } for(j=i+1;j<n;j++) { x2[i] += A[i][j]*x1[j] } x2[i]=-(x2[i]-b[i])/A[i][i] } } 4、输出解x2

用迭代法阶线性方程组

迭代矩阵 记

A = D L U

0 a11 D= 0 ann 0 0 a21 0 L= 0 a ann 1 0 n1

a1n 0 a12 0 U = 0 an 1n 0 0

用迭代法阶线性方程组

易知，Jacobi迭代有

(D L U ) x = b Dx = ( L + U ) x + bx = D 1 ( L + U ) x + D 1b ∴ G = D 1 ( L + U ) = I D 1 A , g = D 1b

用迭代法阶线性方程组

收敛条件 迭代格式收敛的充要条件是G的谱半径<1。对于Jac

obi迭代，我们有一些保证收敛 的充分条件 定理：若A满足下列条件之一，则Jacobi迭代收敛。 ① A为行对角占优阵 ② A为列对角占优阵 ③ A满足

aii > ∑ aij a jj > ∑ aiji≠ j j ≠i

∑ai≠ j

aijii

<1

用迭代法阶线性方程组

证明：

G = D 1 ( L + U ) aij G ∞ = max ∑ < 1 ∑ aij < aii i j ≠ i aii j ≠iG 1 = max ∑i i≠ j

aij aii

<1

② A为列对角占优阵，则AT为行对角占优阵，有

ρ ( I D 1 AT ) < 1∴ ρ ( I D 1 A) = ρ ( I D 1 AT ) < 1#证毕

用迭代法阶线性方程组

6.2 Gauss-Seidel迭代 - 迭代在Jacobi迭代中，使用最新计算出的分量值

( k +1) x1 x ( k +1) ∴ 2 ( k +1) xn xi( k +1)

1 (k ) (k ) = (a12 x2 + + a1n xn b1 ) a11 1 ( k +1) (k ) (k ) (a21 x1 = + a23 x3 + + a1n xn b2 ) a22 1 ( k +1) ( k +1) (an1 x1 = + + an n 1 xn 1 bn ) ann

n 1 i 1 ( k +1) (k ) = (∑ aij x j + ∑ aij x j bi ) aii j =1 j =i +1

用迭代法阶线性方程组

Gauss-Siedel迭代算法

1、输入系数矩阵A和向量b,和误差控制eps 2、x2={1,1,…..,1} //赋初值 3、while( ||A*x2-b||>eps) { for(i=0;i<n;i++) { for(j=0;j<i;j++) { x2[i] += A[i][j]*x2[j] } for(j=i+1;j<n;j++) { x2[i] += A[i][j]*x2[j] } x2[i]=-(x2[i]-b[i])/A[i][i] } } 4、输出解x2

用迭代法阶线性方程组

迭代矩阵

x ( k +1) = D 1 ( Lx ( k +1) + Ux ( k ) + b) ( I D 1 L) x ( k +1) = D 1Ux ( k ) + D 1b x ( k +1) = ( I D 1 L) 1 D 1Ux ( k ) + ( I D 1 L) 1 D 1b x ( k +1) = ( D L) 1Ux ( k ) + ( D L) 1 b ∴ G = ( D L) 1U , g = ( D L) 1 b是否是原来的方程的解？

A=(D-L)-U

用迭代法阶线性方程组

收敛条件 迭代格式收敛的充要条件是G的谱半径<1。我们看一些充分条件 定理：若A满足下列条件之一，则Jacobi迭代收敛。 ① A为行或列对角占优阵 ② A对称正定阵

用迭代法阶线性方程组

证明：

设G的特征多项式为

Ps (λ )

,则

Ps (λ ) = λI G = λI ( D L) 1U = ( D L) 1 λ ( D L) U

A = D L U∴ λ <1

为对角占优阵，则 即

∴ λ ( D L) U ≠ 0即

Ps (λ ) ≠ 0

λ ≥ 1 时 λ ( D L) U#证毕

为对角占优阵

ρ (G ) < 1

注：二种方法都存在收敛性问题。 二种方法都存在收敛性问题。 收敛性问题 有例子表明： 法收敛时， 有例子表明：Gauss-Seidel法收敛时，Jacobi法可能 法收敛时 法可能 不收敛； 法收敛时， 不收敛；而Jacobi法收敛时， Gauss-Seidel法也可能 法收敛时 法也可能 不收敛。 不收敛。

用迭代法阶线性方程组

1 8 0 7 A = 1 0 9 , b = 8 , x (0) = (0, 0, 0) ' 9 1 1 7 1、预处理

9 1 1 7 A = 1 8 0 , b = 7 1 0 9 8 ( ( x1( k +1) = 1/ 9( x2k ) + x3k ) + 7) ( k +1) x1 = 1/ 8( x1( k +1) + 7) x ( k +1) = 1/ 9( x ( k +1) + 8) 1

1

2、格式

用迭代法阶线性方程组

3、结果

x (1) = (0.7778, 0.9722, 0.9753) ' x (2) = (0.9942, 0.9993, 0.9994) ' x (3) = (0.9999, 0.9999, 0.9999) ' x (4) = (1.0000,1.0000,1.0000) '

用迭代法阶线性方程组

2 1 1 A = 1 1 1 1 1 2 1、Jacobi迭代

0 1/ 2 1/ 2 B = D 1 ( L + U ) = 1 0 1 1/ 2 1/ 2 0

特征值为< …… 此处隐藏：2552字，全部文档内容请下载后查看。喜欢就下载吧 ……