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

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

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

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

，使其收斂到某個(gè)極限向

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

雅可比迭代，高斯-賽德?tīng)柕沙诘取?/p>

第三頁(yè)，共四十七頁(yè)，2022年，8月28日6.1

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

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

雅可比迭代矩陣

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

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

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

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

第十二頁(yè)，共四十七頁(yè)，2022年，8月28日

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

則由迭代格式

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

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

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

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

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

反證法假定det(A)=0

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

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

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

第十九頁(yè)，共四十七頁(yè)，2022年，8月28日第二十頁(yè)，共四十七頁(yè)，2022年，8月28日

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

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

高斯-塞德?tīng)?Gauss-Seidel)迭代高斯-塞德?tīng)柕挠?jì)算在雅可比迭代(6.4)的迭代過(guò)程中，可用新求出的x(k+1)的分量來(lái)代替x(k)的分量參與計(jì)算，直到用x(k+1)的前n-1分量代替x(k)

的前n-1個(gè)分量求出為止，即可由（6.5）得到高斯-塞德?tīng)柕核惴ǖ诙捻?yè)，共四十七頁(yè)，2022年，8月28日令B=L+U，其中則高斯-賽德?tīng)柕蓪?xiě)成矩陣形式或?qū)懗善渲?，為高?塞德?tīng)柕仃嚕诙屙?yè)，共四十七頁(yè)，2022年，8月28日

高斯-塞德?tīng)柕氖諗啃?/p>

由定理6.1知，高斯-塞德?tīng)柕諗康某浞直匾獥l件為也可以利用條件來(lái)判斷高斯-塞德?tīng)柕諗俊６ɡ?.4當(dāng)系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)時(shí)，高斯-塞德?tīng)柕諗俊?/p>

證明類(lèi)似于定理6.3的證明。反證法。第二十六頁(yè)，共四十七頁(yè)，2022年，8月28日第二十七頁(yè)，共四十七頁(yè)，2022年，8月28日第二十八頁(yè)，共四十七頁(yè)，2022年，8月28日定理6.5當(dāng)系數(shù)矩陣A為正定矩陣，高斯-塞德?tīng)柕諗?。證明第二十九頁(yè)，共四十七頁(yè)，2022年，8月28日第三十頁(yè)，共四十七頁(yè)，2022年，8月28日例6.2

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

判定高斯-塞德?tīng)柕袷降氖諗啃?。解高?塞德?tīng)柕仃嚍槠渲校?/p>

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

高斯-塞德?tīng)柕惴?/p>

根據(jù)(6.6)，可以寫(xiě)出高斯-塞德?tīng)柕暮诵牟糠郑河浀谌?yè)，共四十七頁(yè)，2022年，8月28日第三十四頁(yè)，共四十七頁(yè)，2022年，8月28日6.3

松弛迭代

高斯-塞德?tīng)柕鸀樗沙诘ㄊ歉咚?塞德?tīng)柕ǖ囊环N變化形式。令第三十五頁(yè)，共四十七頁(yè)，2022年，8月28日其中，參數(shù)ω>0稱(chēng)為松弛因子。將(6.9)變形為(6.9)或(6.10)稱(chēng)為松弛迭代法。迭代矩陣為當(dāng)0<ω<1時(shí)，稱(chēng)為低松弛迭代；當(dāng)1<ω<2時(shí)，稱(chēng)為超松弛迭代；當(dāng)ω=1時(shí)，即為高斯-塞德?tīng)柕５谌?yè)，共四十七頁(yè)，2022年，8月28日

實(shí)際用計(jì)算機(jī)計(jì)算時(shí)，采用(6.9)的分量形式，即雅可比迭代、高斯-塞德?tīng)柕退沙诘鶠閱尾骄€性迭代。第三十七頁(yè)，共四十七頁(yè)，2022年，8月28日

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

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

時(shí)，則松弛迭代收斂。

證明類(lèi)似于定理6.4。定理6.8

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

松弛迭代算法

基本上與高斯-塞德?tīng)柕惴ㄏ嗤?。第四十一?yè)，共四十七頁(yè)，2022年，8月28日6.4

逆矩陣的計(jì)算1