數(shù)值計算方法與算法

關(guān)于數(shù)值計算方法與算法第一頁，共四十七頁，2022年，8月28日

求解線性方程組Ax=y，可用直接法。當(dāng)A為稀疏矩陣時，直接法將破壞矩陣A的稀疏性。

我們可以對線性方程組進(jìn)行等價變換，構(gòu)造出等價方程組x=Mx+g,由此構(gòu)造迭代關(guān)系式例如，分解A=N-P，則第二頁，共四十七頁，2022年，8月28日迭代法：構(gòu)造一個向量序列{x(k)}

，使其收斂到某個極限向

量x*，即則x*就是線性方程組的解。常用迭代方法：

雅可比迭代，高斯-賽德爾迭代，松弛迭代等。

第三頁，共四十七頁，2022年，8月28日6.1

雅可比迭代6.1.1雅可比迭代格式迭代格式線性方程組Ax=y，即

第四頁，共四十七頁，2022年，8月28日若aii≠0,i=1,2,…,n,（6.1）可變?yōu)橛泟t第五頁，共四十七頁，2022年，8月28日寫成矩陣形式或簡記為對任意初始向量構(gòu)造迭代格式：(6.2)是稱為簡單迭代或雅可比迭代。第六頁，共四十七頁，2022年，8月28日

雅可比迭代矩陣

記所以稱為雅可比迭代矩陣，是常數(shù)項向量。第七頁，共四十七頁，2022年，8月28日如果通過(6.2)構(gòu)造的迭代序列{x(k)}收斂，即則x*為Ax=y的解，即Ax*=y。事實上，對(6.2)取極限得第八頁，共四十七頁，2022年，8月28日迭代格式的收斂性引理6.1(線性代數(shù)定理)

設(shè)矩陣序列則（證明見關(guān)治和陳景良編《數(shù)值計算方法》P410~412）定理6.1設(shè)迭代格式為由初始向量x(0)產(chǎn)生的向量序列{x(k)}收斂的充分必要條件是證明必要性（）設(shè)則由（6.3）得第九頁，共四十七頁，2022年，8月28日(6.3)-(6.4)得設(shè)第k次迭代的誤差記為充分性（）設(shè)ρ(M)<1,證{x(k)}收斂。如果ρ(M)<1，則I-M為非奇異矩陣。事實上，因為ρ(M)<1，λi<1，因此λ=1不是M的特征值，即第十頁，共四十七頁，2022年，8月28日所以方程組(I-M)x=f有惟一解x*,滿足(I-M)x*=f，即x*=Mx*+f。于是由引理6.1知，第十一頁，共四十七頁，2022年，8月28日例6.1

設(shè)系數(shù)矩陣為

判定雅可比迭代格式的收斂性。解雅可比迭代矩陣為特征方程為

第十二頁，共四十七頁，2022年，8月28日

實際計算中，M的特征值難于計算，因此也難于判斷。由于可用作為判斷收斂的條件。定理6.2若

則由迭代格式

確定的迭代序列{x(k)}收斂，且有誤差估計式第十三頁，共四十七頁，2022年，8月28日證明又因為第十四頁，共四十七頁，2022年，8月28日分別把（c）和（d）代入（e）即得證（a）（b）。注：是收斂的充分條件，但不是必要條件。因為收斂，不能推出。例如第十五頁，共四十七頁，2022年，8月28日定義6.1

如果A的元素滿足并且至少有一個不等式嚴(yán)格成立，則稱A為行對角占優(yōu)矩陣；如果A的元素滿足則稱A為嚴(yán)格行對角占優(yōu)矩陣。同樣可以定義列對角占優(yōu)矩陣和嚴(yán)格列對角占優(yōu)矩陣。引理6.2

（對角優(yōu)勢定理）(3)

若A為嚴(yán)格對角占優(yōu)矩陣，則A非奇異，且aii≠0,i=1,2,…,n.第十六頁，共四十七頁，2022年，8月28日證明

由線性代數(shù)知識知，det(A)≠0Ax=0只有零解。

反證法假定det(A)=0

，則Ax=0有非零解，記為第十七頁，共四十七頁，2022年，8月28日

當(dāng)方程組的系數(shù)矩陣為嚴(yán)格對角占優(yōu)時，關(guān)于雅可比迭代我們有下面的定理。定理6.3當(dāng)系數(shù)矩陣為嚴(yán)格對角占優(yōu)時，雅可比迭代收斂。證明方法一：根據(jù)嚴(yán)格對角占優(yōu)矩陣的定義。雅可比迭代矩陣：第十八頁，共四十七頁，2022年，8月28日方法二：反證法。

因為A為嚴(yán)格對角占優(yōu)矩陣，由引理6.2知，aii≠0.

第十九頁，共四十七頁，2022年，8月28日第二十頁，共四十七頁，2022年，8月28日

雅可比迭代算法算法描述：1.輸入系數(shù)矩陣A和常數(shù)項向量y；2.形成雅可比迭代矩陣B和向量g第二十一頁，共四十七頁，2022年，8月28日3.賦初始值

第二十二頁，共四十七頁，2022年，8月28日4.實現(xiàn)迭代5.輸出方程組的解x2[i]，i=1,2,…,n.第二十三頁，共四十七頁，2022年，8月28日6.2

高斯-塞德爾(Gauss-Seidel)迭代高斯-塞德爾迭代的計算在雅可比迭代(6.4)的迭代過程中，可用新求出的x(k+1)的分量來代替x(k)的分量參與計算，直到用x(k+1)的前n-1分量代替x(k)

的前n-1個分量求出為止，即可由（6.5）得到高斯-塞德爾迭代：算法第二十四頁，共四十七頁，2022年，8月28日令B=L+U，其中則高斯-賽德爾迭代可寫成矩陣形式或?qū)懗善渲?，為高?塞德爾迭代矩陣，第二十五頁，共四十七頁，2022年，8月28日

高斯-塞德爾迭代的收斂性

由定理6.1知，高斯-塞德爾迭代收斂的充分必要條件為也可以利用條件來判斷高斯-塞德爾迭代收斂。定理6.4當(dāng)系數(shù)矩陣為嚴(yán)格對角占優(yōu)時，高斯-塞德爾迭代收斂。

證明類似于定理6.3的證明。反證法。第二十六頁，共四十七頁，2022年，8月28日第二十七頁，共四十七頁，2022年，8月28日第二十八頁，共四十七頁，2022年，8月28日定理6.5當(dāng)系數(shù)矩陣A為正定矩陣，高斯-塞德爾迭代收斂。證明第二十九頁，共四十七頁，2022年，8月28日第三十頁，共四十七頁，2022年，8月28日例6.2

設(shè)系數(shù)矩陣為

判定高斯-塞德爾迭代格式的收斂性。解高斯-塞德爾迭代矩陣為其中，

第三十一頁，共四十七頁，2022年，8月28日第三十二頁，共四十七頁，2022年，8月28日

高斯-塞德爾迭代算法

根據(jù)(6.6)，可以寫出高斯-塞德爾迭代的核心部分：記第三十三頁，共四十七頁，2022年，8月28日第三十四頁，共四十七頁，2022年，8月28日6.3

松弛迭代

高斯-塞德爾迭代為松弛迭代法是高斯-塞德爾迭代法的一種變化形式。令第三十五頁，共四十七頁，2022年，8月28日其中，參數(shù)ω>0稱為松弛因子。將(6.9)變形為(6.9)或(6.10)稱為松弛迭代法。迭代矩陣為當(dāng)0<ω<1時，稱為低松弛迭代；當(dāng)1<ω<2時，稱為超松弛迭代；當(dāng)ω=1時，即為高斯-塞德爾迭代。第三十六頁，共四十七頁，2022年，8月28日

實際用計算機(jī)計算時，采用(6.9)的分量形式，即雅可比迭代、高斯-塞德爾迭代和松弛迭代均為單步線性迭代。第三十七頁，共四十七頁，2022年，8月28日

松弛迭代的收斂性定理6.6松弛迭代收斂的必要條件是0<ω<2。即若松弛迭代收斂，則必有0<ω<2。證明松弛迭代矩陣其中，第三十八頁，共四十七頁，2022年，8月28日

如果松弛迭代收斂，由定理6.1知，即Sω的所有特征值的絕對值均小于1。由特征方程的性質(zhì)得由（1）和（2）兩式得第三十九頁，共四十七頁，2022年，8月28日定理6.7如果系數(shù)矩陣A為嚴(yán)格對角占優(yōu)，當(dāng)松弛因子

時，則松弛迭代收斂。

證明類似于定理6.4。定理6.8

若A為對稱正定矩陣時，則當(dāng)時，松弛迭代收斂。第四十頁，共四十七頁，2022年，8月28日

松弛迭代算法

基本上與高斯-塞德爾迭代算法相同。第四十一頁，共四十七頁，2022年，8月28日6.4

逆矩陣的計算1