第四章-解AX=b的迭代法.ppt

1、第四章 解線性代數(shù)方程組的迭代法,三種基本的迭代方法及收斂條件 4.1 雅可比迭代 4.2 高斯-賽德爾(Gauss-Seidel)迭代 4.3 超松弛迭代,求解線性方程組 Ax = y，可用直接法。當(dāng) A 為稀疏矩陣時(shí)，直接法將破壞矩陣 A 的稀疏性。,我們可以對(duì)線性方程組進(jìn)行等價(jià)變換，構(gòu)造出等價(jià)方程 組 x = Mx+g,由此構(gòu)造迭代關(guān)系式 例如，分解A=N-P，則,迭代法： 構(gòu)造一個(gè)向量序列 x(k) ，使其收斂到某個(gè)極限向量 x*，即 則 x* 就是線性方程組的解。,常用迭代方法： 雅可比迭代，高斯-賽德爾迭代，松弛迭代等。,4.1 雅可比迭代 迭代格式 線性方程組 Ax = y，即,

2、若aii0, i = 1,2,n ,（6.1）可變?yōu)?記 則,寫成矩陣形式,或簡記為 對(duì)任意初始向量 構(gòu)造迭代格式： (4.2)是稱為簡單迭代或雅可比迭代。,雅可比迭代矩陣 記,所以 稱為雅可比迭代矩陣， 是常數(shù)項(xiàng)向量。,如果通過(4.2)構(gòu)造的迭代序列x(k)收斂，即,則 x*為 Ax = y的解，即 Ax*= y。事實(shí)上，對(duì)(4.2)取極限得,迭代格式的收斂性,引理4.1 (線性代數(shù)定理) 設(shè)矩陣序列 則 （證明見關(guān)治和陳景良編數(shù)值計(jì)算方法P410-412） 定理4.1 設(shè)迭代格式為 由初始向量x(0)產(chǎn)生的向量序列x(k)收斂的充分必要條件是 證明 必要性（）設(shè) 則由（4.3）得,(4.

3、3)-(4.4)得,設(shè)第k次迭代的誤差記為 充分性（）設(shè)(M)1,證x(k)收斂。 如果(M)1 ，則I-M為非奇異矩陣。事實(shí)上，因 為(M)1，i1，因此=1不是M的特征值，即,所以方程組 (I-M)x = f 有惟一解x*,滿足(I-M)x* = f ，即,x*=Mx* + f 。于是 由引理4.1知，,例4.1 設(shè)系數(shù)矩陣為,判定雅可比迭代格式的收斂性。 解 雅可比迭代矩陣為 特征方程為,實(shí)際計(jì)算中，M的特征值難于計(jì)算，因此 也難于判斷。由于 可用 作為判斷收斂的條件。,定理4.2 若 則由迭代格式 確定的迭代序列x(k)收斂，且有誤差估計(jì)式,證明,又因?yàn)?分別把（c）和（d）代入（e）

4、即得證（a）,（b）。 注： 是 收斂的充分條件，但不是必要條件。 因?yàn)?收斂，不能推出 。例如,定義4.1 如果A的元素滿足,并且至少有一個(gè)不等式嚴(yán)格成立，則稱A為行對(duì)角占優(yōu)矩陣； 如果A的元素滿足 則稱A為嚴(yán)格行對(duì)角占優(yōu)矩陣。 同樣可以定義列對(duì)角占優(yōu)矩陣和嚴(yán)格列對(duì)角占優(yōu)矩陣。 引理 4.2 （對(duì)角優(yōu)勢(shì)定理） 若A為嚴(yán)格對(duì)角占優(yōu)矩陣，則A非奇異，且aii0,i=1,2,n.,證明 由線性代數(shù)知識(shí)知，det(A)0 Ax=0只有零解。,反證法 假定 det(A)=0 ，則Ax=0有非零解，記為,當(dāng)方程組的系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)時(shí)，關(guān)于雅可比迭代我們有下面的定理。,定理 4.3 當(dāng)系數(shù)矩陣為嚴(yán)格

5、對(duì)角占優(yōu)時(shí)，雅可比迭代收斂。 證明 方法一：根據(jù)嚴(yán)格對(duì)角占優(yōu)矩陣的定義。 雅可比迭代矩陣：,方法二：反證法。,因?yàn)锳為嚴(yán)格對(duì)角占優(yōu)矩陣，由引理4.2知，aii0.,雅可比迭代算法,算法描述： 1. 輸入系數(shù)矩陣A和常數(shù)項(xiàng)向量y； 2. 形成雅可比迭代矩陣B和向量g,4.2 高斯-塞德爾(Gauss-Seidel)迭代,高斯-塞德爾迭代的計(jì)算 在雅可比迭代(4.4)的迭代過程中，可用新求出的x(k+1)的分量來代替x(k)的分量參與計(jì)算，直到用x(k+1)的前n-1分量代替x(k) 的前n-1個(gè)分量求出 為止，即可由（4.5）得到高斯-塞德爾迭代：,令B=L+U，其中,則高斯-賽德爾迭代可寫成矩

6、陣形式 或?qū)懗?其中， 為高斯-塞德爾迭代矩陣，,高斯-塞德爾迭代的收斂性,由定理4.1知，高斯-塞德爾迭代收斂的充分必要條件為 也可以利用條件 來判斷高斯-塞德爾迭代收斂。 定理 4.4 當(dāng)系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)時(shí)，高斯-塞德爾迭代收斂。 證明 類似于定理4.3的證明。反證法。,定理 4.5 當(dāng)系數(shù)矩陣A為正定矩陣，高斯-塞德爾迭代收斂。,證明,例4.2 設(shè)系數(shù)矩陣為,判定高斯-塞德爾迭代格式的收斂性。 解 高斯-塞德爾迭代矩陣為 其中，,4.3 超松弛迭代,高斯-塞德爾迭代為 松弛迭代法是高斯-塞德爾迭代法的一種變化形式。令,其中，參數(shù)0稱為松弛因子。將(4.9)變形為,(4.9)或(4.10)稱為松弛迭代法。迭代矩陣為 當(dāng)01時(shí)，稱為低松弛迭代； 當(dāng)12時(shí)，稱為超松弛迭代； 當(dāng)=1時(shí)， 即為高斯-塞德爾迭代。,實(shí)際用計(jì)算機(jī)計(jì)算時(shí)，采用(4.9)的分量形式，即,雅可比迭代、高斯-塞德爾迭代和松弛迭代均為單步線性迭代。,松弛迭代的收斂性,定理 4.6 松弛迭代收斂的必要條件是02。即若松弛迭代收斂，則必有02。 證明 松弛迭代矩陣 其中，,如果松弛迭代收斂，由定理4.1知， 即S的所有特征值的絕對(duì)值均小于1。由特征方程的性質(zhì)得 由（1）和（2）兩式得,定理 4.7 如果系數(shù)矩陣A為嚴(yán)格對(duì)角占優(yōu)，當(dāng)松弛因子 時(shí)，則松弛迭代收斂。,證明類似于定理