數(shù)值分析課件第四章線性方程組的迭代解法

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

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

（初等行變換法）第16頁，共75頁，2023年，2月20日，星期五2.矩陣求逆

（伴隨矩陣法）其中A*為A的代數(shù)余子式每一項(xiàng)代數(shù)余子式的符號為-1^(i+j)第17頁，共75頁，2023年，2月20日，星期五迭代法的基本思想：例：求解方程組其精確解是x*=(3,2,1)T。現(xiàn)將原方程組改寫為簡寫為x=B0x+f，其中第18頁，共75頁，2023年，2月20日，星期五任取初始值，如取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ì)算公式（迭代公式）：簡寫為x(k+1)=B0x(k)+f

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

∞=||x(10)–x*||=0.000187第19頁，共75頁，2023年，2月20日，星期五定義：（1）對于給定方程組x=Bx+f，用迭代公式x(k+1)=Bx(k)+f

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

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

誤差估計(jì)？第20頁，共75頁，2023年，2月20日，星期五若A非奇異，且對角元不為零，將原方程組改寫為4.2Jacobi迭代法第21頁，共75頁，2023年，2月20日，星期五第22頁，共75頁，2023年，2月20日，星期五第23頁，共75頁，2023年，2月20日，星期五第24頁，共75頁，2023年，2月20日，星期五第25頁，共75頁，2023年，2月20日，星期五第26頁，共75頁，2023年，2月20日，星期五第27頁，共75頁，2023年，2月20日，星期五第28頁，共75頁，2023年，2月20日，星期五第29頁，共75頁，2023年，2月20日，星期五第30頁，共75頁，2023年，2月20日，星期五第31頁，共75頁，2023年，2月20日，星期五第32頁，共75頁，2023年，2月20日，星期五4.3Gauss－Seidel迭代法第33頁，共75頁，2023年，2月20日，星期五第34頁，共75頁，2023年，2月20日，星期五第35頁，共75頁，2023年，2月20日，星期五第36頁，共75頁，2023年，2月20日，星期五第37頁，共75頁，2023年，2月20日，星期五第38頁，共75頁，2023年，2月20日，星期五第39頁，共75頁，2023年，2月20日，星期五第40頁，共75頁，2023年，2月20日，星期五第41頁，共75頁，2023年，2月20日，星期五第42頁，共75頁，2023年，2月20日，星期五第43頁，共75頁，2023年，2月20日，星期五4.4迭代法的收斂性設(shè)求解線性方程組的迭代格式為將上面兩式相減,得而方程組的精確解為x*，則第44頁，共75頁，2023年，2月20日，星期五則取范數(shù)當(dāng)即且越小，的速度就越快。第45頁，共75頁，2023年，2月20日，星期五定理：設(shè)x*為方程組Ax=b的解，若||B||<1,則 對迭代格式x(k+1)=Bx(k)+f

，有（1）（2）第46頁，共75頁，2023年，2月20日，星期五證由||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*||第47頁，共75頁，2023年，2月20日，星期五所以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ì)式:第48頁，共75頁，2023年，2月20日，星期五注：

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

和x(k)

很接近時，x(k)

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

x(k+1)

-x(k)

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

收斂越快，可作誤差估計(jì)式。第49頁，共75頁，2023年，2月20日，星期五定理：迭代格式收斂的充要條件為迭代矩陣的譜半徑(B)<1。證:對任何n階矩陣B，都存在非奇異矩陣P，使

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

為Jordan塊第50頁，共75頁，2023年，2月20日，星期五其中λ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為對稱陣時，即AT=A，(B)=||B||2。第51頁，共75頁，2023年，2月20日，星期五例3.判別下列方程組用Jacobi法和Gauss-Seidel法求解是否收斂:解:(1)求Jacobi法的迭代矩陣第52頁，共75頁，2023年，2月20日，星期五所以即Jacobi迭代法收斂。(2)求Gauss-Seidel法的迭代矩陣：顯然BJ的幾種常用算子范數(shù)||BJ||>1，故用其特征值判斷。第53頁，共75頁，2023年，2月20日，星期五所以Gauss-Seidel迭代法發(fā)散。注：本例說明Gauss-Seidel迭代法發(fā)散時而Jacobi迭代法卻收斂，因此，不能說Gauss-Seidel迭代法比Jacobi迭代法更好?？傻霉实?4頁，共75頁，2023年，2月20日，星期五定義設(shè)A=(aij

)n×n

Rn×n

，若

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

<1即可.第57頁，共75頁，2023年，2月20日，星期五由于可得<以下用反證法>第58頁，共75頁，2023年，2月20日，星期五矛盾由前述定理知，G－S迭代法收斂。定理若A為對稱正定陣，則Gauss－Seidel迭代收斂。第59頁，共75頁，2023年，2月20日，星期五4.5松弛迭代法第60頁，共75頁，2023年，2月20日，星期五第61頁，共75頁，2023年，2月20日，星期五第62頁，共75頁，2023年，2月20日，星期五第63頁，共75頁，2023年，2月20日，星期五當(dāng)ω＝1時，SOR法化為G－S迭代法G－S法為SOR法的特例,SOR法為G-S法的加速。例1.用G－S法和SOR法求下列方程組的解:要求精度1e-6第64頁，共75頁，2023年，2月20日，星期五解:(1)G-S迭代法第65頁，共75頁，2023年，2月20日，星期五

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次第66頁，共75頁，2023年，2月20日，星期五(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法要快得多。第67頁，共75頁，2023年，2月20日，星期五第68頁，共75頁，2023年，2月20日，星期五第69頁，共75頁，2023年，2月20日，星期五第70頁，共75頁，2023年，2月20日，星期五第71頁，共75頁，2023年，2月20日，星期五4.6誤差分析結(jié)論：（1）的常數(shù)項(xiàng)b的第二個分量只有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

第72頁，共75頁，2023年，2月20日，星期五設(shè)Ax＝b的擾動方程組為(A+A)(x+x)=b+b，其中A叫A的擾動矩陣，x和b叫x和b的擾動向量。定義若矩陣A或常數(shù)項(xiàng)b的微小變化引起方程組Ax＝b的解的巨大變化，則稱此方程組為病態(tài)方程組，A為病態(tài)矩陣（相對方程組而言）；否