《线性方程组迭代解法51 基本迭代方法》由会员分享，可在线阅读，更多相关《线性方程组迭代解法51 基本迭代方法（12页珍藏版）》请在金锄头文库上搜索。
1、第五章线性方程组迭代解法5.1基本迭代方法5.1.1 迭代公式的构造5.1.2Jacobi 迭代法和 Gauss-Seidel迭代法第五章线性方程组迭代解法第五章 线性方程组的迭代解法教学目的1. 掌握Jacobi迭代法，G-S迭代法解大型线性方程组的方法及其收敛性的判别方法；2. 掌握SOR迭代法及收敛的必要条件(02 )；3. 了解三种迭代法之间的改进关系从而掌握该思想方法；4. 理解迭代法基本定理。教学重点及难点重点是三种迭代法及收敛性的判别方法；难点是迭代法基本定理及三种迭代法收敛定理的证明。第五章线性方程组迭代解法第5章线性方程组的迭代解法首先看一个形成大型方程组的例子。考虑下面的P
2、oisson方程u xx+u xx=0 , 0x 1 , 0 y 1 ,的离散逼近，其边界条件为：u ( 0 , y ) = y 2 , u ( 1 , y ) = 1 , 0 y 1 , u ( x , 0 ) = x 2 , u ( x ,1 ) = 1 , 0 x 1 .取 x = y = 0 .25 进行网格剖分,用二阶导数,按逐行自左至右和自下而上的自然次序离散华可得下列线性方程组第五章线性方程组迭代解法4 1 1 1 14 1 1 14 14 1 1 1 14 1 1 1 14 14 1 1 14 1 1u10.1250.25u2u31.56250.25u40u5= 1u611.5
3、625u7 11u842u9其中 ui + 3 j 3 (i, j = 1,2,3) 是 u ( i x , j y ) 的近似值。这是一种特殊形状的稀疏矩阵。随着 x 和 y 的减少，所得到的方程组的阶数将增大。对于大型线形代数方程组，常用迭代解法。它是从某些初始向量出第五章线性方程组迭代解法发，用设计好的步骤逐次算出近似解向量 x(k ) ，从而得到向量序列 x(k)。一般 x( k +1) 的计算公式是x(k+1) = Fk (x(k ) , x(k1) ,L, x(km) ),k = 0,1,L.称之为多步迭代法若 x( k +1) 只与 x( k )有关，且 Fk 是线性的，即x (
4、 k + 1 ) = B k x ( k ) + f k , k = 0 ,1 L ,其中B k R( n n )，称为单步线性迭代法，Bk 称为迭代距阵。若 Bk 和 fk都与k 无关，即x ( k + 1 ) = Bx ( k ) + f , k = 0,1L ,称为单步定常线性迭代法。本章主要讨论具有这种形式的各种迭代方法。第五章线性方程组迭代解法5.1基本迭代方法5.1.1迭代公式的构造设A Rnn，n ，A非奇异，n 满足方程组b Rx RAx=b。（5.1.1）如果能找到距阵 B Rnn，向量f Rn，使 I B 可逆，而且方程组x=Bx+f(5.1.2)的唯一解就是方程组（5.1
5、.1）的解，则可从（5.1.2）式构造一个定常的线性迭代公式x ( k +1) = Bx( k ) + f。（5.1.3）给定初始向量 x(0) Rn , 由(5.1.3)可以产生序列 x k ,若它有极限 x*, 显然x* 就是(5.1.1)和(5.1.2)的解。第五章线性方程组迭代解法定义 5.1 若对任意初始向量 x(0) Rn ，迭代公式（5.1.3）产生的序列x( k ) 都有lim x(k ) = x*,k则称迭代法（5.1.3）是收敛的。从（5.1.1）出发，可以由不同的途径得到各种不同的等价方程组（5.1.2），从而得到不同的迭代法（5.1.3）。例如，设A可以分解为 A =
6、M N ，其中M非奇异，则由（5.1.1）可得x = M 1Nx + M 1b.令 B = M 1Nx = M 1b, 就可以得到（5.1.2）的形式。不同的分解方式A = M N ，可的不同的 B 和 f , 下面给出对应不同分解方式的常用迭代计算公式。第五章线性方程组迭代解法5.1.2Jacobi 迭代法和 Gauss-Seidel迭代法1. Jacobi 迭代法记 A = (aij ) ，可以把 A 分解为A = D L U ,（5.1.4）其中 D = diag(a11 , a22 ,L, ann ),00a12La1n00OMa21L = MOO,U = .O an1,nL an,n
7、100an1现设D非奇异，即aii 0, i = 1,2,L, n 。方程组（5.1.1）等价于x = D 1 ( L + U ) x + D 1 b .第五章线性方程组迭代解法由此构造迭代公式：x(k +1)= BJ x(k ) + fJ , k = 0,1,L,（5.1.5）其中迭代距阵BJ 和向量 fJ 为BJ= D1 (L +U ) = I D1 A,（5.1.6）fJ = D1b.（5.1.7）称（5.1.5）为解（5.1.1）的Jacobi 迭代法，简称 J 法。用 J 法计算向量序列x(k ) ，要用两组单元存放向量 x( k ) 和 x(k +1) 。迭代法可以写成分量形式i1
8、nxi(k +1) = (bi aij x(jk ) aij x(jk ) ) / aii , i = 1,2,L, n. （5.1.8）j=1j=i+12. Gauss-Seidel 迭代法在J 法中，计算xi(k +1) 时，分量x1( k +1) , L, xi(k1+1) 已经算出，所以可考虑第五章线性方程组迭代解法对J 法进行修改。在每个分量计算出来之后，下一个分量的计算就利用最新的计算结果。这样，在整个迭代过程中只要使用一组单元存放迭代向量，其分量形式的计算结果为i1nxi(k +1) = (bi aii x(jk +1) aij x(jk ) ) / aii , i = 1,2,
9、L, n. （5.1.9）j=1j=i+1这就是Gauss-Seidel 迭代法，简称 GS 法将（5.1.9）写成距阵形式x(k +1) = D1 (Lx(k +1) +Ux(k ) + b),经整理有x(k +1) = BGS x(k ) + fGS , k = 0,1,L,（5.1.10）其中迭代距阵BGS和向量 fGS 为BGS = (D L)1U ,(5.1.11)第五章线性方程组迭代解法fGS = (D L)1 b.(5.1.12)Jacobi 迭代法和 Gauss-Seidel 迭代法的分量形式供计算编程用，它们的距阵形式供研究迭代序列是否收敛等理论分析用。例.用法和法分别求解方
10、程组1031x14210 31x2= 5 ,1310x143其准确解为 x* = (1,1,1)T。解用 J 法计算，按（5.1.8）有x1( k +1) x2(k +1) x3(k +1)= (- 3x( k ) x( k )+ 14) /10,23= (2x( k )+ 3x( k ) + 5)/10,13= (x( k ) 3x( k )+ 14)/10.12第五章线性方程组迭代解法用 GS 法计算，按（5.1.9）有( k +1)= ( k )( k )+ 14)/10,x1- 3x2 x3x2(k +1)= (2x1( k +1)+ 3x3(k ) + 5)/10,x( k +1)= (x( k +1) 3x( k +1)+ 14) /10.312取 x(0) = (0,0,0)T，J 法迭代4次的计算结果是x ( 4) = (0.9906,0.9645,0.9906)T , x( 4) x* = 0.0356.GS 法迭代4次的计算结果是x( 4) = (0.99154,0.99578,1.0021)T , x( 4) x* = 0.0085.从计算结果看，本例用 GS 法显然比用 J 法收敛快。
