數(shù)值分析課件第四章線性方程組的迭代解法向量和矩陣的范數(shù)Jacobi迭代法Gauss－Seidel迭代法迭代法的收斂性松弛迭代法（基于G-S的加速收斂方法）誤差分析第四章線性方程組的迭代解法引言特點(diǎn)：該方法具有對(duì)計(jì)算機(jī)的存貯單元需求少，程序設(shè)計(jì)簡(jiǎn)單、原始系數(shù)矩陣在計(jì)算過程中不變等優(yōu)點(diǎn)，是求解大型稀疏矩陣方程組的重要方法．4.1向量和矩陣的范數(shù)向量的范數(shù)矩陣的范數(shù)矩陣基礎(chǔ)知識(shí)回顧向量的范數(shù)證明（2）:所以證明（1）:所以所以證明（3）:矩陣的范數(shù)矩陣特征值

設(shè)A是n階方陣，如果存在常數(shù)λ和n維非零列向量x使下式成立基礎(chǔ)知識(shí)回顧則?λ稱為矩陣A的特征值，x稱為A對(duì)應(yīng)于特征值λ的特征向量，上式還可寫為。關(guān)于這個(gè)n維其次線性方程組有非零解的充分必要條件是2.矩陣求逆

（初等行變換法）2.矩陣求逆

（伴隨矩陣法）其中A*為A的代數(shù)余子式每一項(xiàng)代數(shù)余子式的符號(hào)為-1^(i+j)迭代法的基本思想：例：求解方程組其精確解是x*=(3,2,1)T?，F(xiàn)將原方程組改寫為簡(jiǎn)寫為x=B0x+f，其中任取初始值，如取x(0)=(0,0,0)T，代入x=B0x+f右邊，若等式成立則求得方程組的解，否則，得新值x(1)=(x1(1),x2(1),x3(1))T=(2.5,3,3)T，再將x(1)代入，反復(fù)計(jì)算，得一向量序列{x(k)}和一般的計(jì)算公式（迭代公式）：簡(jiǎn)寫為x(k+1)=B0x(k)+f

k=0,1,2,……x(10)=(3.000032,1.999838,0.999813)T迭代到第10次時(shí)有||ε(10)||

∞=||x(10)–x*||=0.000187定義：（1）對(duì)于給定方程組x=Bx+f，用迭代公式x(k+1)=Bx(k)+f

(k=0,1,2,……)逐步代入求近似解的方法稱迭代法；（2）若k∞時(shí)limx(k)存在（記為x*），稱此迭代法收斂，顯然x*就是方程組的解，否則稱迭代法發(fā)散；（3）B稱為迭代矩陣。問題：

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

誤差估計(jì)？若A非奇異，且對(duì)角元不為零，將原方程組改寫為4.2Jacobi迭代法4.3Gauss－Seidel迭代法4.4迭代法的收斂性設(shè)求解線性方程組的迭代格式為將上面兩式相減,得而方程組的精確解為x*，則則取范數(shù)當(dāng)即且越小，的速度就越快。定理：設(shè)x*為方程組Ax=b的解，若||B||<1,則 對(duì)迭代格式x(k+1)=Bx(k)+f

，有（1）（2）證由||B||<1,有所以||x(k+1)–x*||≤||B||||x(k)–x*||x(k+1)–x*=(Bx(k)+f)–(Bx*+f)=B(x(k)–x*

)||x(k)–x*||=||(x(k)–x(k+1))+(x(k+1)–x*)||≤||x(k)–x(k+1)||+||x(k+1)–x*||≤||x(k)–x(k+1)||+||B||||x*–

x(k)||

=

||x(k+1)–x(k)||+||B||||x(k)–x*||所以x(k+1)–x(k)=(Bx(k)–f)–(Bx(k-1)–f)=B(x(k)–x(k-1)

)||x(k+1)–x(k)||≤||B||||x(k)–x(k-1)||故可得誤差估計(jì)式:注：

（1）式說明，只要||B||不是很接近1，當(dāng)x(k+1)

和x(k)

很接近時(shí)，x(k)

也越接近x*，故可用||

x(k+1)

-x(k)

||中止迭代。（2）式說明，||B||越小，x(k)

收斂越快，可作誤差估計(jì)式。定理：迭代格式收斂的充要條件為迭代矩陣的譜半徑(B)<1。證:對(duì)任何n階矩陣B，都存在非奇異矩陣P，使

B=P–1JP其中，J為B的Jordan標(biāo)準(zhǔn)型。其中,Ji

為Jordan塊其中λi

是矩陣B的特征值，由B=P–1JPBk=(P–1JP)(P–1JP)···(P–1JP)=P–1JkP迭代法x(k+1)=Bx(k)+f

收斂<=>譜半徑(B)<1注：(B)≤||B||，且當(dāng)B為對(duì)稱陣時(shí)，即AT=A，(B)=||B||2。例3.判別下列方程組用Jacobi法和Gauss-Seidel法求解是否收斂:解:(1)求Jacobi法的迭代矩陣所以即Jacobi迭代法收斂。(2)求Gauss-Seidel法的迭代矩陣：顯然BJ的幾種常用算子范數(shù)||BJ||>1，故用其特征值判斷。所以Gauss-Seidel迭代法發(fā)散。注：本例說明Gauss-Seidel迭代法發(fā)散時(shí)而Jacobi迭代法卻收斂，因此，不能說Gauss-Seidel迭代法比Jacobi迭代法更好。可得故定義設(shè)A=(aij

)n×n

Rn×n

，若

(i=1,2,…,n)，則稱A為對(duì)角占優(yōu)矩陣，若不等式嚴(yán)格成立，則稱A為嚴(yán)格對(duì)角占優(yōu)矩陣。迭代法收斂的其他結(jié)論：定理若Ax=b中A為嚴(yán)格對(duì)角占優(yōu)矩陣，則Jacobi迭代和Gauss－Seidel迭代均收斂。證明：因?yàn)橄禂?shù)矩陣A嚴(yán)格對(duì)角占優(yōu)，所以故Jacobi迭代法收斂(1)對(duì)于Jacobi迭代法，其迭代矩陣為且：(B)≤||B||即從而因此(2)對(duì)于G－S迭代法，其迭代矩陣為BG的特征值λ滿足分析：要證G－S迭代法收斂，即證其迭代矩陣的譜半徑(B)<1，只要證明其特征值λ

<1即可.由于可得<以下用反證法>矛盾由前述定理知，G－S迭代法收斂。定理若A為對(duì)稱正定陣，則Gauss－Seidel迭代收斂。4.5松弛迭代法當(dāng)ω＝1時(shí)，SOR法化為G－S迭代法G－S法為SOR法的特例,SOR法為G-S法的加速。例1.用G－S法和SOR法求下列方程組的解:要求精度1e-6解:(1)G-S迭代法

x1 x2 x3

1110.75000000.37500001.50000000.56250000.53125001.54166670.65104170.59635421.61458330.70182290.65820311.6727431……….0.99999330.99999231.99999260.99999430.99999351.99999370.99999520.99999441.9999946

k=71x=0.9999950.9999941.999995滿足精度的解迭代次數(shù)為71次(2)SOR迭代法

x1 x2 x31110.63750000.01218751.31990630.20042700.37175721.31228050.65503350.53401191.69228480.70584680.77334011.7771932………..0.99999900.99999761.99999910.99999840.99999931.99999890.99999980.99999941.99999980.99999960.99999981.9999997k=24x=1.0000001.0000002.000000滿足精度的解迭代次數(shù)為24次選取適當(dāng)?shù)摩?，SOR法的收斂速度比G-S法要快得多。4.6誤差分析結(jié)論：（1）的常數(shù)項(xiàng)b的第二個(gè)分量只有1/1000的微小變化，方程組的解變化卻很大。例記方程組（1）為Ax＝b，其精確解為：x1*=2，x2*=0現(xiàn)考察方程組（2）可將其表示為：A(x+x)=b+b其中 b=(0,0.0001)T設(shè)x為(1)的解，顯然(2)的解為：x+x=(1,1)T

設(shè)Ax＝b的擾動(dòng)方程組為(A+A)(x+x)=b+b，其中A叫A的擾動(dòng)矩陣，x和b叫x和b的擾動(dòng)向量。定義若矩陣A或常數(shù)項(xiàng)b的微小變化引起方程組Ax＝b的解的巨大變化，則稱此方程組為病態(tài)方程組，A為病態(tài)矩陣（相對(duì)方程組而言）；否則稱方程組為良態(tài)方程組，A為良態(tài)矩陣。研究方程組中A或b的微小誤差對(duì)解的影響的分析稱“擾動(dòng)分析”。(1)A=0，則A

(x+x)=b+b，減去Ax=b，得設(shè)Ax=b的擾動(dòng)方程組為(A+A)(x+x)=b+b，下面進(jìn)行擾動(dòng)分析：(2)b=0，則(A+A)(x+x)=b，同理可得Ax=b，故x=A-1

b，即||x||||A-1||

||

b

||，又由Ax=b，有||b||||A

||

||

x

||

，所以定義設(shè)A非奇異，稱數(shù)cond(A)=||A