計算方法引論：數(shù)值代數(shù)解線性方程組的直接法解線性方程組最小二乘問題解線性方程組的迭代法矩陣特征值和特征向量的計算非線性方程及非線性方程組解法計算方法引論(第三版)第八章解線性方程組的迭代法大稀疏方程組適用迭代法常用迭代法迭代法收斂性誤差估計收斂速率共軛斜量法計算方法引論(第三版)大稀疏方程組線性方程組Ax=b大稀疏矩陣:非零元素極少大稀疏方程組:非零系數(shù)極少微分方程離散化結(jié)構(gòu)分析電力傳輸網(wǎng)絡大稀疏方程組更適用迭代法求解直接法:用有限步計算得到準確解

迭代法:給出一個近似解序列

計算方法引論(第三版)迭代法線性方程組

(1)Ax=b迭代法給出一個近似解序列

收斂性誤差估計收斂速率計算方法引論(第三版)Jacobi迭代法算例用Jacobi迭代法解線性方程組

計算方法引論(第三版)Jacobi迭代法算例(續(xù))計算結(jié)果

計算方法引論(第三版)Jacobi迭代法線性方程組(1) Ax=b化成(2) x=Bx+g迭代計算方法引論(第三版)Jacobi迭代法矩陣關(guān)系線性方程組 (1)Ax=b化成 (2)x=Bx+g迭代

迭代矩陣:B計算方法引論(第三版)Gauss-Seidel迭代法算例用G-S迭代法解線性方程組

計算方法引論(第三版)Gauss-Seidel迭代法算例(續(xù))計算結(jié)果

計算方法引論(第三版)Gauss-Seidel迭代法線性方程組(1)Ax=b化成(2) x=Bx+g迭代計算方法引論(第三版)G-S迭代法矩陣關(guān)系線性方程組 (1)Ax=b化成 (2)x=Bx+g,B=L+U迭代

迭代矩陣:B1=(I-L)-1U計算方法引論(第三版)SOR迭代法線性方程組(1)Ax=b化成(2) x=Bx+g(同J法,G-S法)迭代(這是G-S法改進與推廣.ω=1即G-S法)

矩陣表示 x(k+1)=(1-ω)

x(k)+ω(Lx(k+1)+Ux(k)+g)迭代矩陣:Bω=(I-

ωL)-1(1-ω)I+ωU)計算方法引論(第三版)SOR迭代法算例用G-S迭代法解線性方程組

計算方法引論(第三版)SOR迭代法算例(續(xù))計算結(jié)果

計算方法引論(第三版)迭代矩陣一階線性定常迭代兩次近似有關(guān)系x(k+1)=Mx(k)+f稱M為迭代矩陣Jacobi迭代法x(k+1)=Bx(k)+g

迭代矩陣B=L+UGauss-Seidel迭代法x(k+1)=(I-L)-1Ux(k)+

(I-L)-1g迭代矩陣B1=(I-

L

)-1USOR迭代法x(k+1)=(I-

ωL

)-1(((1-ω)I+ωU)x(k)+ωg)迭代矩陣Bω=(I-

ωL)-1((1-ω)I+ωU)計算方法引論(第三版)迭代收斂性收斂充要條件對任何初值x(0),迭代格式x(k+1)=Mx(k)+f確定的序列{x(k)}收斂並且極限與初值無關(guān)的充分必要條件是迭代矩陣的譜半徑小于1,ρ(M)<1.三個算例皆收斂ρ(B)=0.337…

ρ(B1)=0.125…ρ(Bω)=0.086…計算方法引論(第三版)收斂性判定計算迭代矩陣特征值并確定譜半徑 例1.-0.10.33722813232690-0.23722813232690例200.12579720807237-0.03179720807237例3-0.086…0.020…±0.032…idet(λI-Bω)=計算方法引論(第三版)誤差估計定理常用前一不等式估計當前近似的誤差計算方法引論(第三版)對角占優(yōu)陣嚴格對角優(yōu)勢矩陣可逆

J法收斂G-S法收斂

不可約對角優(yōu)勢陣可逆J法收斂SOR法(0<ω≤1)收斂計算方法引論(第三版)SOR收斂性松弛法收斂的必要條件是0<ω<2若A是實對稱矩陣或Hermite矩陣,對角元為正,則當0<ω<2時松弛法收斂的充分必要條件是A正定某些矩陣,例如對角塊為對角線子陣的塊三對角陣有最優(yōu)松弛因子ωopt,此時對應的迭代矩陣譜半徑最小,為ωopt-1計算方法引論(第三版)收斂速率平均收斂因子:║Mk║1/k漸近收斂因子:平均收斂速率:漸近收斂速率:

關(guān)系式:計算方法引論(第三版)共軛斜量法A實對稱正定時等價問題解方程組Ax?=?b求二次函數(shù)最小值點共軛斜量法理論上至多n步能得到準確解實際上只是用作迭代法;結(jié)合預善技術(shù)作為加速方法極為有效每步剩余向量與搜索方向正交,新搜索方向

與原搜索方向A正交算法簡述:計算方法引論(第三版)算法與各量關(guān)系共軛斜量法算法定理8.8注:算法中rk+1=0則停止，此時b–Axk?=?0，xk為準確解.8.24)(8.25)(8.26)(8.27)計算方法引論(第三版)定理證明定理證明計算方法引論(第三版)共軛斜量法算例改進算法算例(對照J,GS,SOR例)

計算用高精度進行，

665計算方法引論(第三版)共軛斜量法極小性質(zhì)定理8.9設(shè)Ax*?=?b，A是實對稱正定矩陣，則共軛斜量法迭代序列x0,x1,…有下述極小性質(zhì)這兒范數(shù)

證計算方法引論(第三版)極小性質(zhì)注記又一極小性質(zhì)共軛斜量法另一種描述共軛斜量法的計算過程實際上是求上E(x)最小也就是求H(x)最小的過程.從x0,V1(由r0?=?p0構(gòu)成)開始，沿著p0方向求最小值點.該點剩余r1為零則解已得，否則與V1正交形成V2.將其A正交化得p1.再沿著p1方向求最小值點，它也是x0+V2上的最小值點.該點剩余r2為零則已得解，否則它與V2正交，形成V3.將其A正交化得p2.接著重復以前的做法，再沿著p2方向求最小值點，也是x0+V3上的最小值點.計算方法引論(第三版)共軛斜量法誤差估計定理8.10

推論共軛斜量法迭代序列

計算方法引論(第三版)共軛斜量法誤差估計(續(xù)一)定理證明計算方法引論(第三版)共軛斜量法誤差估計(續(xù)二)定理證明(續(xù))計算方法引論(第三版)共軛斜量法誤差估計(續(xù)三)推論證明當計算方法引論(第三版)幾點注記關(guān)于誤差估計的注記估計是保守的，對于特征值的不同情況，可以得到更好的估計.實際計算結(jié)果可能比估計的要好得多.為達到預定誤差所需迭代次數(shù)與條件數(shù)的平方根成正比.改善收斂性的途徑--預善技術(shù)構(gòu)造矩陣M，使同解方程組條件數(shù)變小.將A分裂:A=M-N

JG-SSOR

得到迭代格式J法算例取MJ預善,共軛斜量法解之A,M皆對稱正定共軛斜量法解之計算方法引論(第三版)預善共軛斜量法預善共軛斜量法算法一預善共軛斜量法算法二計算方法引論(第三版)說明預善共軛斜量法算法說明算法一是共軛斜量法