数值分析课件第四章_线性方程组的迭代解法Word

　　第四

　　章性线方程组的代解迭法

　　四章 第

　　线方程组的迭性解代法向和量阵矩的数范Ja obic迭代法Ga ussSei-del迭法 代代法的迭敛收性 松弛代法迭(基G于-S加的收速方法) 误敛差析分

　　言引

　　点：特方该法具有对计算机存贮的元需单少，求程序设 简计单原始系数、阵矩计在算过程不中等变优点 ，求解大是型疏矩稀阵方程的重要方组.

　　法.1 向量4和矩阵的范数

　　量的范数向矩的范阵数

　　阵基矩础识回知顾

　　向

　　量的数

　　范

　　证

　　(1明:

　　)|| x||1 x1|| |x2 | xn |m|ax |x k | || x| | n 1 axm| x k | 1k n 1 kn所 以明(2证:)|| x| | || x| 1 | n | |x || || ||x 2x x 2 nx 21 22 ma x| x|1 k n k 2

　　|| x |2| n amx| k |x 1k n

　　2

　　所

　　以|| x| | | |x || 2 n|| x |

　　|明(证):3

　　|| |x| 1 x| |1 |x 2 | | n x|| x ||2| x x2 nx 21 2 2| |x| | 2|| x || | x |||2 | x|| |12 122

　　n | | ||2x | | x| | ( x 12x ) (x 1 xn ) ( x2 x3 )2 2 2

　　12 (x2 xn ) ( xn 1 xn ) 0 2

　　所2以

　　|| |x|2 | |x || 1 n || x||

　　2矩阵的范数

　　基础

　　知回识顾矩特征阵值 A是n阶方阵，设果存如在常 数λn和非零维 向量列使下式x成立1.

　　Ax x 则λ 称矩为阵A的特征值，称x为对应A特 征于值λ特征向的，上式量可写为还。 A ( )I x 0 关这个于n维其次性线方组程非零有解的充 必分要件是

　　A条 I 0

　　.2矩 求逆 阵(等初变换法)

　　行

　　.2矩阵求逆 (伴 随矩法)阵

　　A 11 A其A*中为A代数的子余式 A

　　一每代数余项子的符号式-1为^(+ji)

　　迭代的基本法思：想：例解方求组程 8 x1 3x 22 x3 2 0 4x1 11 x2 x3 33 6x 3x 2x 1 362 3 1现将原程方改组为写 1 x1 8 ( 3 x 2 2 x 3 20) 1 x 2 4(x 1 3 33x) 11 1 x 3 1 2 ( 6x 1 3 x 2 3 6 )其确精是解*x=3,(2,)T。 1简写x=为Bx+0,f中3其2 0 88 1 4 B 0 101 113 6 0 12 1 2 20 8 3 3 f 11 3 6 12

　　任

　　取始初值，取x(0如)(0=0,,)0,T代x入B=0+x右f边 ，等式若立则求得方程组成的，解则否得，新值x( 1=()x11(),x(12,x)31()T)=2.(,53,3),T再将(1x)代，反入 计算复，一得向序量{列xk)}(一般的计算公式 和迭代公式():1 简写为(k+1x)B=0(kx+) kf=,1,2,0……迭 代到1第次0有时 (3x 2 x 2) 0 x8 ( k ) 11(k (k ) ) x ( 4 x x 2 13 3 3) 11 k( 1)1 k( )(k )

　　(6 x 1 3x 2 6)3 x 321 k )( 2k ) (3( k ) 1

　　1x1(0=)3.(0000321.9,9938,08.99983)T ||1ε10()||∞= |x(10)|x–||*=0.001870

　　定

　　:义(1)对给于方定程x=Bx+组，用f代公式 迭(kx+)1Bx(k=+) fk=(,10,,…2)逐…步代入近似解求 方法的迭称法；代 (2)若 ∞时klmix k)(在(存记x为*,称此 )代迭法敛收显，然x就*方是组程的解，则称否 迭法代散发 (;3)B为迭代称阵。矩 问： 题如 建立何代迭格式？ 量序向的列敛收件条？ 敛收速？ 度 差估计？误

　　42 .Jcoab迭i代法若A奇异，且对非角不元为，零将原程组改方写 为

　　.34Ga us-Seisdel迭法代

　　44. 迭法代的收性敛设求线解方性组的迭程格代式为x

　　(k )1 B x

　　( )k

　　f

　　方程组而的精确为x*,则

　　x* 解B * x f将上面式相减两,

　　得x(k 1) *x (Bx ( k)(k )

　　*x)令 (k )

　　x

　　x *k ,01,2,

　　则 (k 1) B ( k) B 2 ( k1) B k1 0( )意 注 (0 ) x 0) x(* 为非零常向量数取范 k 数 k B ( 0 ) B当 即 k k

　　(0 )

　　B 1 lim k 0 lmi xk *kx 且 B越小， k x x*的 速度越就快。

　　定理：x*为方设程 A组x= 的解b,若||B||1则 ,对迭代式 格xk+1)( =B x k()+ f , 有 () || x1( k)

　　|| B| |k ) ( k 1() x |*| | x| x ||1 | | B|

　　(2| )||x (k

　　)||B || ( 1)(0) * ||x || x x| | 1|| B ||

　　k

　　证 |由||B1|有,lm xik k( )

　　*xxk(1)–x* +=Bx(()+k ) – (fBx+*f) = B(x(k )– * x)|| (kx1+)– * ||x ≤|B|| |||x(k) – x* | |所以

　　|x(|) –kx * || =||x(k)– x(k(+1)) (+x( +k1)–* x)||≤|x|()k –(xk1+|) +||| xk(+)1x*|– | ≤||x()– xk(+1)|| +k|B|| ||x| – x*(k|| = )||xk+(1–)x( k||) ||+B| ||| (k)–x*x ||

　　所以

　　|

　　|x

　　(k )1 ( k ) (1 k x) *|| ||x x | |1 ||B ||

　　(kx+1–x(k)) =(x(B)k–f) –B((x-k1)–f) =(xBk)( –(xk1) -)|x(k|1)–+(kx|)| |≤| B| ||| (x)k –x (-1)k| |故 可误差估得计:式| |xk( )| |B | | x * | || |x (k ) x(k ) 1|| |1| B|

　　k| | |B || ||x k() x* | | || x 1() x ( 0 ) ||1 | B| |

　　|

　　注 ：| | ||B k() ( 1) 式|| x x *| || x ( k| ) x ( k1)|| 1 ||B ||说 ，明只要|B|||是很不接近，1x(k当+1)和 x( k 很)接时近 x,(k) 也越接近x*故，可 用|| x(k1) -+ (k) x|中|止迭。代 (2式)k|| B || || x (k ) x *| ||| x() 1x( 0 )|| 1 | B|| |说明|,B||越小|, x(k 收)越敛快可作误，差估计 式。

　　定理：代格迭式x (k )1 B x ( k ) 收敛的f要条充件为 代迭阵的谱矩半径 ()B。 证: 对任何1 n矩阵B,都存在非阶奇矩异阵，使P B = P1 –JP其中 ，J 为B的 J roda 标n型。准 J1 J J2

　　rJ n

　　n中其 J, 为iJodarn 块 iiJ 1 i ni in 1

　　其

　　λi 是矩中B阵特的值征， 由B =P –1J PB k =P –1(J P )( P– J1P ) (P –1 J )= P P1 J– Pk迭代法x(+k)1k B=k

　　x(k)B 0 f +敛 =ilmk k

　　li Jm

　　lm i i0k k

　　| i | 1半径谱 ( )B 1amx | i| 11 i r注:(B ≤ ||B|)|, 且B为对当阵称，时AT即=, A ()=B||B |2。

　　|3. 判例下列别程组方J用cobi法a和Gaus-sSiedl 法求解是否收敛:e 1 1 2 2 12 2x 1 1 1 x 2 1 x 1 1 3 10解:(1) 求acJob法i迭代的阵 1 矩B J 1 D ( L U ) 0 0 0 0 01 2 0 1 0 2 2

　　0 1 2 2 1 0

　　2 0 2

　　2 1 0

　　显

　　BJ然几种常用的算子数|范|J|B1,故|用特 征值其断。判 d et( I B J ) ed t 1 2 22

　　2 1 03

　　所以 0 ( BJ) m x(a ||) 0 1

　　Ja即obic迭法代收敛。(2) 求 Gasu-Seisdl法的迭代矩e阵：1 1B G ( D L ) U 1 2 0 1 0 2 0 1 1

　　0 0 0 020 2 1 0

　　BG故 0 0 0 2 0

　　22 3 2

　　可 得 0 2

　　(BG ) max( |) | 2 1所以Guas-Ssidee迭l法代散发。注 本：说明Gauss-Se例dei迭l法发代散时而Ja cbi迭代法o却敛收，此，不因说能auGsSseiedl迭法代J比acbi迭o法更好代

　　。迭代

　　法收的敛他结其论：

　　定义 A设=(ija n)n

　　nRn a a i i ji 若 ， j0ji n

　　i(=1,2,,…n),则称为对A角优矩占，阵若等不 严式成立，格则称为严A对角占优格阵矩。定理 若Ax=中Ab为严对格角占矩优阵， Jac则obi代迭Ga和us-seSdile代迭均收。敛证明 因为：系数矩阵严A格对占角，所优以| iai | |a j ij i|i 12,,, , n3 i ,2,31 ,,

　　n1| aj |i 1 | iai| j i

　　1 B

　　D(L ) (1)对UJ于acob迭i代，法其迭矩阵代 为

　　J 0 a 2 1J B a2 2 a n1 a nnJB

　　1a a21 0 1 na a2 nn

　　a1 an1 a21n a2

　　2 0

　　1 mx | aaji | 1 i ai|i j | i

　　J故coaib代迭法收敛且 :()B ≤||||

　　B2)对于(-SG代法迭，其迭矩阵为代B G (D L )分U析要证：GS迭-代收法敛即，其迭代证阵矩的谱半径 (B) ,只1证要明其征值λ特 1即.B可的G特值λ征满 det足 I( BG ) 0 即de[ tI ( D )L U] 0 1 1从而 ed(Dt L)1 d e[t D(

　　) L ]U 0 因此 det [ ( DL) U ] 0

　　以下用反证 由于|a ii| | a j i| j i可得

　　| | | a ii| | | | a j | |i | |aij| j 1 j i 1

　　i1

　　n| | | aj i| j

　　i1

　　1j i 1

　　|a

　　nji| ( | | 1) j i 1 a

　　n|ij|

　　如|果 | 1 ,则有| | | aii | || | iaj| j1 i 1j i 1 a|n

　　ij

　　|

　　则 [(D L )U ] 为严对角格占矩阵优

　　而de从[ t (D )L U ] 0

　　盾

　　矛以所 | | ,1即 ( G ) 1B由前述定,理， G知S-代迭法收。 敛定 理若A对为称定阵正则G,aus-sSieeld迭代收敛。

　　45. 松弛代法迭

　　ω=1时，S当R法化O为x (k 1 ) ( D L) 1U x( ) k D ()L1 b G-S代法

　　G迭S-法SOR为的法特例 ,SRO法G为S-的法加。速例1. 用GS法-和SO法求R列下方程组解的取 : .451 4 2 1 x 1 0 2 42 x 2 2 3 1 2 3 x 3 要求精度e16-

　　解

　　:(1G)-迭S法B代G S 0 0 4 1 ( D L) U 2 40 1 2 3 1

　　021 0 2 0 0 00

　　00 5.0 25 . 0 .02 0.625 5 0 /1 3 0 .5 fG S0 0 4 1 (D L )b 420 1 3 2 1

　　0 0 2 0. 5 3 2/ 3

　　取值 初xx1( 0)

　　(,1,11)

　　Tx

　　2x

　　3 1 1 满1精足度的 0.7解50000 003.507000 1.0000500 x=0 5.62500 00.5132005 .14566671 .09999590 6510.1740 .5635924 1.16543380.9 99949 .701082920 .582036 1.162774131.99 9995… …………………………………. 0….999993 039.999239 .99919269迭 代次为71数次0. 99994390 9.9993951 9.99997 30.999995 0.9299994 41.999996 4 k= 17

　　(

　　)2OR迭S代 取法 14.5 x( 1k () D ) 1 (L1( )D U ) x( k ) (D L )1 b 11 1 0.675300 0.0102817 5.1319906 302.00274 00.717532 7131.2820 0565.035530 .5430191 .192268480. 05874680 .773301 1.7477932 ………1………………………………. .0999999. 0.909997691. 999999 0199.999840 99.9999 1.99999893 09.99998 9.9099999 1.499999890 9.99996 9.9099998 199.99997 9k= 24x1

　　2xx

　　3足满度的解x= 1精.00000 01.0000002 .000000

　　迭次数为2代次4选取适当的，ωOSR法的收速度比敛GS-法 要快多得

　　。

　　4

　　6 误.分差析

　　1 1 x 2 1 x 2 例方程记(组1 ) 11000. 1 2 A为xb,其精确解=:为x*=12x2,=*

　　01 x 1 2 1现 考方程组察(2 ) 1 1 0.001 x2 2 00.0 1将可表其示为A:x(

　　+ x=b+ b)其中 =b( 00.,0001)T设x为(1 )的，显然解2()解为的：x x+=(1 , )T1

　　论结(1):常数项的b的第个分量二只1有/1000 微的变小化，程方的组解化却变大很

　　定义 若矩。阵A常数或b项的微变化引小方起组程Ax =的b解巨大的化，则称变方此组程为病态 方程组A为，病态矩阵相(对程组而言)方否则；称 方组程良态方为程，组为良态A矩。阵

　　究方程研组A或b中的小误差微对解影响的的 析称“扰动分分析。”设 Ax=的b扰方动组为(A+ A程(x) x)=+b +b ,中 A其叫的A扰矩阵动 ,和x 叫b和x的b 扰动量向。

　　设A=xb的动方扰程为(组A+A) (+ xx)= + bb, 下进行面动分扰：析 ( )1 A0,=A (x+则 x=) b +,减去bx=Ab, A 得 x= b , 故 x A=- 1b, 即 || x|| | |-1A| ||| b || , 由Ax又=,b有|||b |||A || | x|| |, 所 以2(

　　)x x A

　　1

　　A

　　bb b=,则(A0 +A )(+xx)= b,理可同得x A 1 A A x Ax

　　义 定设A非奇，异称 数ond(c)=A |A-1 ||| |A|||为 矩A阵的件条。数说:明(1 )件条数小，动引起的解的相对误差一扰定 小；条 件数大，动扰起引解的误的差可很大。(能条数件与取所的范有数关最，用常的||是 ||∞和|| ||)2(2)于由cod(A)=n||A | ||A|-1| ≥||A| A1-| |=|I|||=1 故，条件是一放大数倍数，且的以1为下总界。(3当)为正交A阵(A矩-=A1)时，有T ocn(d)2=A,1所以交正矩阵的程方组是态的。良

　　:已知Hi例lbet矩阵r1 1 2 11 nH 32 1 1 n n 1 1 n 1 n1 1 2n 1 cnd(oH)3=74 8计可得 算oncd(H)62.9=017 cod(Hn7)9=8.5108n越，Hn的大条件数越大 故Hi,belt矩阵是一r个典的型病 矩态。阵

　　11 / 1 2/3 如 A /1 12 3 / / 14 1 /3 1 / 4 1 / 5

　　1 b 2 3

　　1 b b 2 3.1

　　得可x=(2 70.000- 92100.0 02100.00)0Tx x= (+3.0000 0-1020.00 208.0020)0T

　　残差

　　量：向rb-=Ax( 为xxA=b的似解近) r很小时，当是否xA为x=的一个b较好近似解的？呢 定 理事(误后估计差)设非A异，x奇和*x分别 A是x=的b确精解近和似，解=br-Ax残差为 向，则量x * x rco dn( ) A x b 证明* :由x*A ,br b xAx * x A 1 r x* x 1Ar

　　b 又 Ax* Ax *

　　x* x得 rr 1 A A ondc A( )x *bb

　　本章作业P73 习四题：,425