計(jì)算方法(方程組的迭代法)

1、1,北京科技大學(xué)應(yīng)用學(xué)院數(shù)力系 衛(wèi)鴻儒 W,計(jì)算方法,2,課程性質(zhì)和計(jì)劃（續(xù),計(jì)算方法,概論,泛函分析中若干概念,矩陣特征值與特征向量的計(jì)算,最佳平方逼近,數(shù)值逼近方法,方程組及非線性方程的數(shù)值解法,常微分方程初值問題的數(shù)值解法,3,二、用迭代法解線性方程組,Jacobi迭代和Seidel迭代由于收斂速度較慢，已經(jīng)越來越不適應(yīng)當(dāng)前信息時(shí)代人們對(duì)計(jì)算速度和精度的要求，所以在實(shí)際應(yīng)用中使用的并不多。但是，他們體現(xiàn)了迭代法的最基本的思想，是學(xué)習(xí)其它迭代法的基礎(chǔ),4,一）引言,直接法是通過有限步運(yùn)算后得到線性方程組的解，解線性方程組還有另一種解法，稱為迭代法，它的基本思想是將線性方程組 Ax=b 化為

2、 x=Bx+f 再由此構(gòu)造向量序列x (k): x(k+1)=Bx (k)+f 若x (k)收斂至某個(gè)向量x *，則可得向量x *就是所求方程組 AX=b 的準(zhǔn)確解。 線性方程組的迭代法主要有Jocobi迭代法、Seidel迭代法和超松弛(Sor)迭代法,5,若在求解過程中 xkx*(k)，由 xk+1=(xk)產(chǎn)生的迭代 xk向x*的逼近 ，在數(shù)次迭代求解之后，由于機(jī)器跳動(dòng)產(chǎn)生的xk值誤差或是有效數(shù)字產(chǎn)生的舍入誤差，都會(huì)在第k+1次迭代計(jì)算中自動(dòng)彌補(bǔ)過來或逐步糾正過來。因此，在迭代求解過程中產(chǎn)生的各種誤差是可以忽略的，即迭代求解無累積誤差，實(shí)際上，xk只是解的一個(gè)近似，機(jī)器的舍入誤差并不改變

3、它的此性質(zhì),迭代過程中經(jīng)常要遇到向量范數(shù)，矩陣范數(shù)以及序列極限的概念。（前面已作介紹,6,二）、Jacobi 迭代,一： 設(shè)有方程組 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 . . . . . . . . . . . . an1x1+an2x2+annxn=bn 用矩陣表示：Ax =b （A 為系數(shù)矩陣，非奇異；b為右端列向量，x為解向量,7,假設(shè) aii0 令 cij = -aij /aii (ij) gi= bi /aij , i=1,2,3,n 則 x1(k+1)= c12x2(k)+c13x3(k)+ +c1nxn(k)+g1 x2(k+1)

4、=c21x1(k) +c23x3(k)+ +c2nxn(k)+g2 。 xn(k+1)=cn1x1(k) +cn2x2(k)+ +cn(n-1)xn-1(k) + gn Jacobi迭代格式 若令 0 c12 c13 c1n x1 c21 0 c23 c2n x2 BJ= x= . cn1 cn3 cn4 0 xn a11 g1 a22 g= g2 易看出:BJ =D-1(D-A)=I-D-1A D= . . ann gn,把方程組寫成容易迭代的形式,8,Jacobi迭代公式,9,三）、Seidel迭代法 為了加快收斂速度，同時(shí)為了節(jié)省計(jì)算機(jī)的內(nèi)存，我們作如下的改進(jìn)：每算出一個(gè)分量的近似值，立

5、即用到下一個(gè)分量的計(jì)算中去，即用迭代格式： 這樣所得的迭代法就稱為Gauss-Seidel迭代法，也稱為“異步迭代法”，簡(jiǎn)稱為GS迭代法利用Ax=b 及A=L+D+U,其中D為對(duì)角矩陣,L,U分別為嚴(yán)格下，上三角矩陣則有，GS迭代法的矩陣形式為,10,Seidel迭代法的具體形式,Seidel迭代格式 x1(k+1)= c12x2(k)+c13x3(k)+ +c1nxn(k)+g1 x2(k+1)=c21x1(k+1) +c23x3(k)+ +c2nxn(k)+g2 。 xn(k+1)=cn1x1(k+1) +cn2x2(k+1)+ +cn(n-1)xn-1(k+1) + gn 假設(shè) aii0

6、 令 cij = -aij /aii (ij) gi= bi /aij , i=1,2,3,n,11,四）、收斂性及誤差估計(jì),12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,五）、例題及求解 例：用迭代法解方程組AX=b,其中 已知該方程的解為 解：本題分別用簡(jiǎn)單迭代法（Jacobi迭代法）和GS迭代法來解 (1)簡(jiǎn)單迭代法,41,42,表,43,44,45,表2,46,47,48,49,50,51,六）、相關(guān)程序設(shè)計(jì) 原始數(shù)據(jù)（A,b)可用一個(gè)二維數(shù)組存儲(chǔ)，也可將A用

7、一個(gè)二維數(shù)組，b用一個(gè)一維數(shù)組分別存儲(chǔ)，存儲(chǔ)需要一個(gè)一維數(shù)組。程序中應(yīng)方便地對(duì)迭代方法和終止條件的選擇以及對(duì)初始向量和值的設(shè)置。在迭代過程中，為反映迭代情況，可設(shè)置一些中間數(shù)據(jù)的輸出，如迭帶次數(shù)，迭代向量，迭代殘向量等。當(dāng)然不需要每迭代一次都作輸出，這可作為收斂情況或不收斂情況的分析。作為不收斂的判定，可設(shè)置一個(gè)大的整數(shù)，當(dāng)?shù)螖?shù)超過該數(shù)時(shí)作為不收斂處理。 GS 迭代法的計(jì)算公式為,52,53,開始,T,F,T,F,T,54,請(qǐng)給出用C語(yǔ)言或其他語(yǔ)言求解下面方程組的程序及結(jié)果,55,七）、方法優(yōu)缺點(diǎn)討論 由以上例題的求解過程可明顯看出GS迭代法的收斂速度比簡(jiǎn)單迭代法快，但對(duì)于任意給定的一個(gè)方程組分別用簡(jiǎn)單迭代法和GS迭代法求解時(shí)，兩種迭代法可能都收斂，也可能都不收斂。也有可能是GS迭代法收斂而J迭代法不收斂。但亦有相反情況，即簡(jiǎn)單迭代法收斂而GS迭代法不收斂。而且交換方程組中的方程和未知數(shù)的次序都會(huì)影響GS迭代法的計(jì)算結(jié)果，但這種交換對(duì)簡(jiǎn)單迭代法是沒有影響的,56,八）、SOR法介紹,57,58,59,60,九）、迭代法的特點(diǎn),1）方法簡(jiǎn)單，每次迭代都是簡(jiǎn)單的重復(fù)運(yùn)算，易于編制程序；與求解線性方程的精確法相比，簡(jiǎn)單迭代法對(duì)于字長(zhǎng)位數(shù)較少的計(jì)算機(jī)更為適用，它可以用增加迭代次數(shù)來彌補(bǔ)字長(zhǎng)位數(shù)少的不