1、第3章 線性方程組迭代解法 Iterative Techniques for Solving Linear Systems,(2.1),直接法是通過有限步運(yùn)算后得到線性方程組的解，解線性方程組還有另一種解法，稱為迭代法 迭代法：不是用有限步運(yùn)算求精確解，通過迭代產(chǎn)生近似解逼近精確解 基本思想是將線性方程組 AXB 化為XBX+F,再由此構(gòu)造一個(gè)向量序列X(k) X(k+1)=BX (k)+F 若X(k)收斂在某個(gè)極限向量X*，則可得X*就是(2.1)式的準(zhǔn)確解,線性方程組的迭代法主要有Jocobi迭代法、 Gauss Seidel迭代法和超松弛(SOR)迭代法 Jacobi迭代和Seidel迭

2、代由于收斂速度較慢，已經(jīng)越來越不適應(yīng)當(dāng)前信息時(shí)代人們對(duì)計(jì)算速度和精度的要求，所以在實(shí)際應(yīng)用中使用的并不多。但是，他們體現(xiàn)了迭代法的最基本的思想，是學(xué)習(xí)其它迭代法的基礎(chǔ),如何構(gòu)造迭代序列X(n)? X(n)在什么條件下收斂? 收斂速率如何? 誤差估計(jì).,若在求解過程中 X(k) X*(k)，由 X(k+1)=(X(k)產(chǎn)生的迭代X(k)向X*的逼近 ，在數(shù)次迭代求解之后，由于機(jī)器跳動(dòng)產(chǎn)生的X(k)值誤差或是有效數(shù)字產(chǎn)生的舍入誤差，都會(huì)在第k+1次迭代計(jì)算中自動(dòng)彌補(bǔ)過來或逐步糾正過來。因此，在迭代求解過程中產(chǎn)生的各種誤差是可以忽略的，即迭代求解無累積誤差，實(shí)際上，X(k)只是解的一個(gè)近似，機(jī)器的舍

3、入誤差并不改變它的性質(zhì)。,迭代過程中經(jīng)常要遇到向量范數(shù)，矩陣范數(shù)以及序列極限的概念。,3.1 向量和矩陣的范數(shù)Norms of Vectors and Matrices,數(shù)值分析中,經(jīng)常要用向量和矩陣,為了應(yīng)用的需要(誤差分析), 引入衡量向量和矩陣大小的度量范數(shù).,對(duì)于實(shí)數(shù)xR,我們定義了絕對(duì)值,滿足 |x|0 非負(fù)性 |x|=|x| 齊次性 |x+y|x|+|y| 三角不等式 類似地,定義向量范數(shù),Def3.1 在實(shí)n維線性空間Rn中定義一個(gè)映射,它使任意X Rn 有一個(gè)非負(fù)實(shí)數(shù)與之對(duì)應(yīng),記為|X|,且該映射滿足: 正定性 任意XRn,|X|0,if and only if X=0時(shí), |

4、X| =0 齊次性 任意XRn, R,有 |X|=|X| 三角不等式 任意X,Y Rn,有 |X+Y|X| + |Y| 則稱該映射在Rn中定義了一個(gè)向量范數(shù).,注: Rn中的范數(shù)不唯一.,常用的向量范數(shù)有三種: 設(shè)X=(x1, x2, xn)TRn.則,注: (1) 用范數(shù)的定義可驗(yàn)證上述皆為向量范數(shù) (2) p=1,2, |X|p 即為 |X|1 ,|X|2. (3) 任意xRn:,定理3.2 設(shè)|和|是Rn上任意兩種范數(shù)，則存在正常數(shù)C1和C2，使得對(duì)一切X Rn 有 C1|X|X| C2|X|,注: Rn中范數(shù)的等價(jià)性表明,雖范數(shù)值不同,但考慮到向量序列收斂性時(shí),卻有明顯的一致性.,De

5、f3.3 Rn中X(x1, x2, xn)T和Y(y1, y2, yn)T則有,有解 (x1, x2, x3)T(1,1,1)T，用Gauss消去法得到近似解,Def3.4 Rn中的向量序列X(k), 即X0, X1, XK,其中XK(x1(k), x2(k), xn(k)T.若對(duì)任意i（i=1,2,n）都有,注：向量序列收斂實(shí)際上是按分量收斂（數(shù)列收斂） 利用向量范數(shù)，也可以說明向量序列收斂的概念。,定理3.5 向量序列X(k)依分量收斂于X* 的充要條件是,則向量X*(x1*, x2*, xn*)T稱為X(k)的極限，記做,類似于向量范數(shù)，給出矩陣范數(shù)的定義。,Def3.6 在線性空間Rn

6、n中定義一個(gè)映射，使任意ARnn對(duì)應(yīng)一個(gè)非負(fù)實(shí)數(shù)，記做| A |.如果該映射滿足：,1.正定性：,（4.是矩陣乘法的需要，而1. 2. 3.為向量范數(shù)的推廣。）,2.齊次性：,3.三角不等性：,4.相容性：,在Rnn中可定義多種范數(shù)。,有 A=(aij)nnRnn 稱為frobenius范數(shù),稱為列范數(shù),稱為行范數(shù),3.2 Jacobi迭代法,(3.1),設(shè)有方程組,用矩陣表示,(3.1),其中A是系數(shù)矩陣，非奇異，X是解向量，B是右端項(xiàng)。,(3.2),(3.3),若令,則有 B=D-1(D-A)=I- D-1A, G= D-1B 方程(3.3)可記為 X=BX+G,方程(3.3)可記為 X=

7、BX+G 選取初始向量X0(x10, x20, xn0)T，代入方程(3.3)右端，可得到一個(gè)新向量，記為X1(x11, x21, xn1)T，一直進(jìn)行下去，迭代格式 X(n+1)=BX (n) +G n=0,1,2,以上過程產(chǎn)生向量序列X (k),若收斂于X* ，則有 X*=BX*+G (I-B)X*=G=D-1B AX*=B 即X*是方程(3.1)的解,(3.4),Jacobi 迭代公式,唯一解X(1,2,-1,1)T,(3.5),簡單迭代法用X(k)計(jì)算X(k+1)時(shí),需要同時(shí)保留X(k)和X(k+1)。為了加快收斂速度，同時(shí)為了節(jié)省計(jì)算機(jī)的內(nèi)存，我們作如下的改進(jìn)：每算出一個(gè)分量的近似值

8、，立即用到下一個(gè)分量的計(jì)算中去,迭代格式為,這樣所得的迭代法就稱為Gauss-Seidel迭代法，也稱為“異步迭代法”，簡稱為GS迭代法。,若令,則(3.5)式可寫成 X(k+1)=LX(k+1) + UX(k)+ G k=0,1,2, 也可記為 X(k+1)=(I-L)-1UX(k)+ (I-L)-1G 稱(I-L)-1U為Seidel迭代法的迭代矩陣,(3.6),(3.7),例3.4 用Seidel迭代法求解方程組,解：,取初始向量,要求,時(shí)迭代終止。,Seidel迭代格式為,計(jì)算結(jié)果可列表如下,注意：未必Seidel方法一定比Jacobi方法好。,3.3 收斂性和誤差估計(jì),設(shè) nn 階矩

9、陣A的特征值為 i(i=1,2,3n),則稱,為矩陣A的譜半徑。,例：用GS迭代法求解例3.3,相關(guān)程序設(shè)計(jì) 原始數(shù)據(jù)（A,b)可用一個(gè)二維數(shù)組存儲(chǔ)，也可將A用一個(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ì)算公式為：,請(qǐng)給出用C語言或其他語言求解下面方程組的程序及結(jié)果

10、：,方法優(yōu)缺點(diǎn)討論 由以上例題的求解過程可明顯看出GS迭代法的收斂速度比簡單迭代法快，但對(duì)于任意給定的一個(gè)方程組分別用簡單迭代法和GS迭代法求解時(shí)，兩種迭代法可能都收斂，也可能都不收斂。也有可能是GS迭代法收斂而J迭代法不收斂。但亦有相反情況，即簡單迭代法收斂而GS迭代法不收斂。而且交換方程組中的方程和未知數(shù)的次序都會(huì)影響GS迭代法的計(jì)算結(jié)果，但這種交換對(duì)簡單迭代法是沒有影響的。,3.4 松弛法,當(dāng)使用Jacobi迭代法或Seidel迭代法解線性方程組時(shí)，可能會(huì)出現(xiàn)收斂極慢的情況，為了提高迭代收斂速度，我們?cè)俳o出時(shí)SOR法，此方法又稱為超松弛法（Successive Over Relaxati

11、on Method），它具有提高迭代收斂速度的功能。SOR法由Seidel迭代法演變而來，其基本思想是利用原迭代的第次迭代值及由產(chǎn)生的下一步Seidel迭代值的加權(quán)平均構(gòu)成新的迭代格式。,松弛法可認(rèn)為是Seidel法的加速,Seidel法 X(k+1)=LX(k+1) + UX(k)+ G k=0,1,2, 令 X=X(k+1) X(k) =LX(k+1) + UX(k)+ G X(k) X(k+1) = X(k) X 松弛法思想 X(k+1) = X(k) X,松弛法 X(k+1)= (1- )X(k) (LX(k+1) + UX(k)+ G) k=0,1,2, 其中，稱為松弛因子，當(dāng)1時(shí)叫超松弛，當(dāng)1時(shí)叫低松弛,也可記為 X(k+1)=(I-L)-1(1-)I+ U)X(k)+ (I-L)-1G 稱(I-L)-1(1-)I+ U)為松弛法的迭代矩陣,(3.8),(3.9),(3.10),唯一解X(3,4,-5)T,Seidel法,SOR法 =1.25,3.5 迭代法的特點(diǎn),方法簡單，每次迭代都是簡單的重復(fù)運(yùn)