数盘算 第六章逐次逼近法 §62线性方程组的迭代法
第六章 逐次逼近法 §6.2 线性方程组的迭代法
§62线性方程组的迭代法 在用直接法解线性方程组时要对系数矩阵不断变换 如果方程组的阶数很高,则运算量将会很大 并且大量占用计算机资源 因此对线性方程组 Ax= 6 要求找寻更经济、适用的数值解法 设A∈Rn,b∈R",x∈Rn
§6.2 线性方程组的迭代法 在用直接法解线性方程组时要对系数矩阵不断变换 如果方程组的阶数很高,则运算量将会很大 并且大量占用计算机资源 因此对线性方程组 Ax = b 要求找寻更经济、适用的数值解法 n n n n A Î R b Î R x Î R ´ 设 , , --------(1)
如果能将线性方程组(1)变换为 x= Bx+ -(2) 其中B∈R"x,f∈R",x∈R 显然(1)式和(2)式同解,我们称(1)(2)等价 对线性方程组(2),采用以下步骤: 取初始向量x0,代入(2),可得 x(1)=Bx)+f 依此类推
如果能将线性方程组(1)变换为 x = Bx + f --------(2) n n n n B Î R f Î R x Î R ´ 其中 , , 显然,(1)式和(2)式同解, 我们称(1)(2)等价 对线性方程组(2),采用以下步骤: 取初始向量 x (0 ) ,代入(2),可得 x = Bx + f (1) (0 ) 依此类推
(2)=Bx X f d+1 k Bx)+ f -(3) (k=01,2, 这种方式就称为迭代法,以上过程称为迭代过程 迭代法产生一个序列{x 如果其极限存在,即limx()=x k→ 则称迭代法收敛,否则称为发散
x = Bx + f (2 ) (1) x Bx f k k = + ( +1) ( ) M (k = 0,1,2,L) --------(3) 这种方式就称为迭代法 ,以上过程称为迭代过程 迭代法产生一个序列 ¥ 0 ( ) { } k x 如果其极限存在,即 ( ) * lim x x k k = ®¥ 则称迭代法收敛, 否则称为发散
、简单迭代法(基本迭代法) 设线性方程组(1)的一般形式为 C1X14122+a1nxn,= a2x+q2x2+…+a2nxn=b2 ax tax t b nn n 设an≠0(=1,2…,n),则可从上式解出x 1 x+……+a1nx
一、简单迭代法(基本迭代法) 设线性方程组(1)的一般形式为 11 1 12 2 1 1 a x a x a x b + +L + n n = 21 1 22 2 2 2 a x a x a x b + +L + n n = n n nn n n a x + a x +L + a x = b 1 1 2 2 KKKK ï ï î ï ï í ì a 0 (i 1,2, , n) 设 ii ¹ = L i ,则可从上式解出 x [ ( )] 1 1 12 2 1 11 1 n n b a x a x a x = - +L +
1 21 十an2X2+∷十anx m) 2 依此类推,线性方程组(1)可化为 (b1-∑ x1十 11 11 (b2-∑a2x x+ 2 2 WX (b-∑ 1 ny x+ n (b,-∑anx) ≠n
[ ( )] 1 2 21 1 23 3 2 22 2 n n b a x a x a x a x = - + +L + ( ) 1 1 1 1 1 11 1 å ¹ = = - n j j j j b a x a x 依此类推,线性方程组(1)可化为 ( ) 1 2 1 2 2 22 2 å ¹ = = - n j j j j b a x a x ( ) 1 1 å ¹ = = - n j i j i ij j ii i b a x a x ( ) 1 1 å ¹ = = - n j n j n nj j nn n b a x a x KKKK KKKK ï ï î ï ï í ì -----(4) ( ) 1 1 1 1 11 1 å= = + - n j j j b a x a x ( ) 1 1 2 2 22 2 å= = + - n j j j b a x a x ( ) 1 1 å= = + - n j i ij j ii i b a x a x ( ) 1 1 å= = + - n j n nj j nn n b a x a x
对(4作迭代过程 (k+1) (k) 1 x b °°J (=1,2,…,m;k=0,1,2,…) 设D=aig(a1 1122 丿nn 则(5)式转化为矩阵形式 x(6+1)=x(6)+D(b-Ax( x(k+1)=x()-D-1Ax()+D-1b (k+1) D1(D-4)x()+D-b
--------(5) ( ) 1 1 ( 1 ) ( ) ( ) å= + = + - n j k i ij j ii k i k i b a x a x x 对(4)作迭代过程 (i = 1,2,L,n; k = 0,1,2,L) ( , , , ) 11 22 nn 设 D = diag a a L a 则(5)式转化为矩阵形式 ( ) ( k 1 ) ( k ) 1 ( k ) x = x + D b - Ax + - x x D Ax D b ( k + 1 ) ( k ) -1 ( k ) -1 = - + x D D A x D b ( k 1 ) 1 ( k ) 1 ( ) + - - = - + --------(6)
令 0 0 0 21 0 0 A的下三角部分 L 的负矩阵 0 12 In U=/0 A的上三角部分 的负矩阵 00 0 A=D-L-U d-A=l+U
令 ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ - - - = 0 0 0 0 0 0 1 2 21 L M O O M L L n n a a a L ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ - - - = 0 0 0 0 0 0 2 12 1 L M O O M L L n n a a a U A = D - L - U D - A = L + U 的负矩阵 A的下三角部分 的负矩阵 A的上三角部分
故迭代过程(6)化为 x(+1)=D-(L+U)x()+Db 令B=D(L+U)f=Db,于是 XX (k+1) Bx )+ f -(7) (k=0,1,2,…) 等价线性方程组为x=Bx+f←Ax=b 称(5式和(7)式为解线性方程组(1)的 jAcobi迭代法(J法) B,为 Jacobi迭代法的迭代矩阵
故迭代过程(6)化为 x D L U x D b ( k 1 ) 1 ( k ) 1 ( ) + - - = + + 令BJ = D -1 ( L + U ), f = D -1 b ,于是 x B x f k J k = + ( + 1 ) ( ) (k = 0,1,2,L) 等价线性方程组为 x B x f = J + Ax = b --------(7) 称(5)式和(7)式为解线性方程组(1)的Jacobi迭代法(J法) BJ为Jacobi 迭代法的迭代矩阵
例1.用 Jacobi迭代法求解方程组,误差不超过1e-4 842 32x 20 11 1 33 14x 12 解 8-3 A=411 1 4300 2 00 D 800 004 000 L 40 2-1 000
例1. 用Jacobi迭代法求解方程组,误差不超过1e-4 ÷ ÷ ÷ ø ö ç ç ç è æ = ÷ ÷ ÷ ø ö ç ç ç è æ ÷ ÷ ÷ ø ö ç ç ç è æ - - 12 33 20 2 1 4 4 11 1 8 3 2 3 2 1 x x x 解: ÷ ÷ ÷ ø ö ç ç ç è æ - - = 2 1 4 4 11 1 8 3 2 A ÷ ÷ ÷ ø ö ç ç ç è æ = 0 0 4 0 11 0 8 0 0 D ÷ ÷ ÷ ø ö ç ç ç è æ - = 0 0 0 0 0 1 0 3 2 U ÷ ÷ ÷ ø ö ç ç ç è æ - - = - 2 1 0 4 0 0 0 0 0 L