應(yīng)用數(shù)值分析（三）

線性方程組的數(shù)值解法線性方程組Ax=b的一般數(shù)值解法：適用于低階稠密方程組非零元素較多，零元素較少適用于大型稀疏方程組上萬階，零元素很多，非零元素很少評(píng)價(jià)求解Ax=b數(shù)值方法好壞的標(biāo)準(zhǔn)：§5.2線性方程組的性態(tài)及條件數(shù)

矩陣的基本運(yùn)算(5)單位矩陣(1)矩陣加法(2)矩陣與標(biāo)量的乘法(3)矩陣與矩陣乘法(4)轉(zhuǎn)置矩陣(6)非奇異矩陣

稱為非奇異矩陣.

如果均為非奇異矩陣，

設(shè)如果則稱是的逆矩陣，記為且則(7)矩陣的行列式

設(shè)則的行列式可按任一行(或列)展開，其中為的代數(shù)余子式，即

的余子式.為元素行列式性質(zhì)矩陣的特征值與譜半徑設(shè)若存在數(shù)（實(shí)數(shù)或復(fù)數(shù)）和非零向量，使（1）則稱為的特征值，為對(duì)應(yīng)的特征向量，稱為矩陣的譜半徑.（2）有非零解，

由(1)知可使齊次線性方程組

的全體特征值記為的譜，記作，即故系數(shù)行列式，記

為矩陣的特征多項(xiàng)式，方程(3)稱為矩陣的特征方程.（3）記行列式展開

因?yàn)榇未鷶?shù)方程復(fù)數(shù)域中有個(gè)根故故矩陣個(gè)特征值是它的特征方程(3)的個(gè)根.且（4）記（5）稱為的跡.

的特征值和特征向量的其他性質(zhì)：(1)與有相同的特征值.(2)若非奇異，則的特征值為，特征向量為.(3)相似矩陣有相同的特征多項(xiàng)式.矩陣的特征方程為故特征值為2,2，-7

例

求的特征值及譜半徑

的譜半徑為解

設(shè)(1)對(duì)角矩陣

(2)三對(duì)角矩陣(3)上三角矩陣(4)海森伯格（Hessenberg）陣(5)對(duì)稱矩陣

(6)埃爾米特矩陣(7)對(duì)稱正定矩陣

特殊矩陣(12)設(shè)矩陣，若且至少有一個(gè)不等式嚴(yán)格成立，則稱矩陣為弱對(duì)角占優(yōu)陣，對(duì)所有不等式嚴(yán)格成立，則稱矩陣

為嚴(yán)格對(duì)角占優(yōu)陣。若(8)正交矩陣(9)酉矩陣(10)初等置換陣單位矩陣交換第行與第行(或交換第列與第列)(11)置換陣

（為交換第行與第行得到的矩陣）；（為交換第列與第列得到的矩陣）；由初等置換陣的乘積得到的矩陣.

定理1

設(shè)則下述命題等價(jià)：(1)對(duì)任何方程組有唯一解.(2)齊次方程組只有唯一解.(4)存在.(5)的秩(3)或的特征值定理2

設(shè)為對(duì)稱矩陣.如果則為對(duì)稱正定陣.定理3

設(shè)為對(duì)稱正定陣，則(1)

為非奇異矩陣，且亦是對(duì)稱正定陣.(2)

記為的順序主子陣，則亦是對(duì)稱正定矩陣，其中(3)

的特征值(4)

的順序主子式都大于零，即

定理4(若爾當(dāng)（Jordan）標(biāo)準(zhǔn)型)設(shè)為階矩陣，則存在一個(gè)非奇異矩陣使得其中為若爾當(dāng)塊.(1)

當(dāng)?shù)娜舢?dāng)標(biāo)準(zhǔn)型中所有若爾當(dāng)塊均為一階時(shí)，此標(biāo)準(zhǔn)型變成對(duì)角矩陣.

(2)

如果的特征值各不相同，則其若爾當(dāng)標(biāo)準(zhǔn)型必為對(duì)角陣線性方程組的數(shù)值解法§5.3Gauss消元法

用消元法解方程組

第2步.解

第1步.得等價(jià)的三角形方程組解為上述過程相當(dāng)于例1

其中表示矩陣的第行.1)消元過程2023/10/27線性方程組的直接解法45Gauss消去法算法消元計(jì)算forforfor回代求解for2023/10/27線性方程組的直接解法46計(jì)算量/*AmountofComputation*/由于計(jì)算機(jī)中乘除/*multiplications/divisions*/

運(yùn)算的時(shí)間遠(yuǎn)遠(yuǎn)超過加減/*additions/subtractions*/

運(yùn)算的時(shí)間，故估計(jì)某種算法的運(yùn)算量時(shí)，往往只估計(jì)乘除的次數(shù)，而且通常以乘除次數(shù)的最高次冪為運(yùn)算量的數(shù)量級(jí)。

GaussianElimination:Stepk：設(shè)，計(jì)算因子且計(jì)算共進(jìn)行n

1步(n

k)次(n

k)2

次(n

k)次(n

k)(n

k+2)次消元乘除次數(shù)：1次(n

i+1)次回代乘除次數(shù)：2023/10/27線性方程組的直接解法47計(jì)算量/*AmountofComputation*/由于計(jì)算機(jī)中乘除/*multiplications/divisions*/

運(yùn)算的時(shí)間遠(yuǎn)遠(yuǎn)超過加減/*additions/subtractions*/

運(yùn)算的時(shí)間，故估計(jì)某種算法的運(yùn)算量時(shí)，往往只估計(jì)乘除的次數(shù)，而且通常以乘除次數(shù)的最高次冪為運(yùn)算量的數(shù)量級(jí)。

GaussianElimination:Stepk：設(shè)，計(jì)算因子且計(jì)算共進(jìn)行n

1步(n

k)(n

k+2)次消元乘除次數(shù)：回代乘除次數(shù)：GaussianElimination的總乘除次數(shù)為，運(yùn)算量為級(jí)。n=20時(shí),順序Gauss消去法需3060次乘除法運(yùn)算.

定理1

設(shè)其中

(1)

如果將約化為等價(jià)的三角形方程組則可通過高斯消去法

(2)如果為非奇異矩陣，則可通過高斯消去法(及交換兩行的初等變換)將方程組約化為？矩陣在什么條件下才能保證歸納法當(dāng)時(shí)，成立.設(shè)時(shí)結(jié)論成立，即證明:充分性.且有可用高斯消去法將約化到，有即定理2

約化的主元素的充要條件是矩陣的順序主子式即

由假設(shè)推出必要性.

例2

求解方程組用4位浮點(diǎn)數(shù)進(jìn)行計(jì)算.精確解舍入到4位有效數(shù)字為

解法1

用高斯消去法計(jì)算解顯然計(jì)算解是一個(gè)很壞的結(jié)果，不能作為方程組的近似解.原因：

在消元計(jì)算時(shí)用了小主元0.001，使得約化后的方程組元素?cái)?shù)量級(jí)大大增長，經(jīng)再舍入使得計(jì)算時(shí)發(fā)生了嚴(yán)重的相消情況，因此經(jīng)消元后得到的三角形方程組就不準(zhǔn)確了.解法2計(jì)算解為交換行，避免絕對(duì)值小的主元作除數(shù).每一步選取系數(shù)矩陣(或消元后的低階矩陣)中絕對(duì)值最大的元素作為主元素，以使高斯消去法具有較好的數(shù)值穩(wěn)定性.線性方程組的數(shù)值解法§5.4

基于矩陣三角分解的方法5.4.1

矩陣的三角分解第1步消元其中第2步消元其中

一般第K步消元其中70條件:矩陣A經(jīng)Gauss消元法后得到的上三角矩陣.

Gauss消元法的矩陣表示上三角陣單位下三角求矩陣的LU分解。取變換矩陣則有再取變換矩陣?yán)猓?/p>

Doolittle分解中LU

元素的求解次序

A=LU三角分解的緊湊格式78對(duì)r=2,3,…,n,

矩陣三角分解的緊湊格式

例5

用直接三角分解法即Doolittle分解法解解從而求解得求解得直接LU分解元素的存儲(chǔ)81解解84練2用直接三角分解法解解85

先求Ly=b得y

再求Ux=y

得x5.4.2

平方根法和改進(jìn)的平方根法上三角陣單位下三角實(shí)對(duì)稱正定矩陣的平方根法93對(duì)稱

A為3階對(duì)稱正定陣,A=LLT,怎樣求L?對(duì)稱94例對(duì)下列矩陣進(jìn)行Cholesky分解95

A為n階對(duì)稱正定陣,A=LLT

L中元素的求解次序

依次求L的第一列,第二列,…,第n列.元素仍然存放在矩陣的相應(yīng)位置上97

求L的第一列

求L的第二列

對(duì)稱正定陣A=LLT,求L的計(jì)算公式

設(shè)已求得L的前k－1列,現(xiàn)求L的第k列(k=3,…,n)101例9求的Cholesky分解.解102解

對(duì)稱正定陣的LDLT分解中L,D的計(jì)算公式1(避免重復(fù)計(jì)算，便于編程)

對(duì)稱正定陣的LDLT分解中L,D的計(jì)算公式2Step1Step2Step3Stepn儲(chǔ)存比消去法節(jié)省一半，但比平方根法多用一個(gè)單元內(nèi)存

對(duì)稱正定陣的LDLT分解緊湊格式及存儲(chǔ)

對(duì)稱正定陣的LDLT分解求方程組（改進(jìn)平方根法）例10用LDLT解方程組解例10用LDLT解方程組或緊湊格式112

對(duì)稱正定陣的LDLT分解本質(zhì)上是對(duì)A作Doolittle分解,即LU分解.LDLT分解中的D

即LU分解中的U的對(duì)角部分LDLT分解中的L

即LU分解中的L113

對(duì)稱正定矩陣A的LU分解,計(jì)算量可以節(jié)省一半

求U的第1行

求L的第1列

對(duì)稱正定陣的LDLT分解中L,D的計(jì)算

先對(duì)對(duì)稱正定陣A作LU分解114

求U的第k行(k=2,3,…,n)

求L的第k列(k=2,3,…,n)

對(duì)稱正定陣的LDLT分解中L,D的計(jì)算節(jié)省了計(jì)算量

求D5.4.3

三對(duì)角線性方程組的追趕法119例四階三對(duì)角矩陣的三角分解（Gauss消去法）120例四階三對(duì)角矩陣的三角分解單位下二對(duì)角陣上二對(duì)角陣122

三對(duì)角矩陣三角分解中LU的求解次序123對(duì)k=3,…,n

三對(duì)角矩陣三角分解中LU的求解

右端用矩陣乘法展開,比較兩邊元素得追趕法追的過程:n-1趕的過程:2n-1乘除運(yùn)算量2n－2

系數(shù)矩陣為嚴(yán)格對(duì)角占優(yōu)陣時(shí),追趕法數(shù)值穩(wěn)定

計(jì)算過程中撇開系數(shù)中大量的零,使計(jì)算公式大大簡(jiǎn)化,減少了計(jì)算量.追趕法總的乘除運(yùn)算量5n－4.線性方程組的直接法小結(jié)三角分解的計(jì)算過程Step1Step2Step3Step4Step5Step6Step2n-1Step2(n-1)依次交替進(jìn)行再計(jì)算的列先計(jì)算的行存儲(chǔ)杜利特爾分解/*DoolittleFactorization*/：對(duì)方程組求解,只要得到了系數(shù)矩陣的三角分解形式,再利用前代算法和回代算法解兩個(gè)三角方程組即得.線性方程組的數(shù)值解法對(duì)線性方程組要求尋找更經(jīng)濟(jì)、適用的數(shù)值解法.其中A為非奇異矩陣,當(dāng)A為低階稠密矩陣時(shí),選主元消去法(直接法)是有效的.但對(duì)于大型稀疏矩陣方程組(A的階數(shù)n很大

104，但零元素較多),方程組的階數(shù)很高,則運(yùn)算量將會(huì)很大并且大量占用計(jì)算機(jī)資源.利用迭代法求解是合適的.§5.5

雅可比迭代法和高斯-賽德爾迭代法

將介紹迭代法的一些基本理論及雅可比迭代法，高斯-賽德爾迭代法，超松弛迭代法，而超松弛迭代法應(yīng)用很廣泛。

則(1)式和(2)式同解,稱(1)與(2)等價(jià).

例1求解方程組記為Ax=b，其中此方程組的精確解是x*=(3,2,1)T.現(xiàn)將(1.2)改寫為迭代法的基本概念

下面舉簡(jiǎn)例，以便了解迭代法的思想.或?qū)憺閤=B0x+f，其中取x(0)=(0,0,0)T.將這些值代入(1.3)式右邊(若(1.3)式為等式即求得方程組的解，但一般不滿足)，得到新的值x(1)=(x1(1),x2(1),x3(1))T

=(3.5,3,3)T

，再將x(1)分量代入(1.3)式右邊得到x(2)，反復(fù)利用這個(gè)計(jì)算程序，得到一向量序列簡(jiǎn)寫為x(k+1)=B0x(k)+f，其中k表示迭代次數(shù)(k=0,1,2,

).

迭代到第10次有一般的計(jì)算公式(迭代公式)

從此例看出，由迭代法產(chǎn)生的向量序列x(k)逐步逼近方程組的精確解是x*=(3,2,1)T.即有

對(duì)于任何一個(gè)方程組x=Bx+f(由Ax=b變形得到的等價(jià)方程組)，由迭代法產(chǎn)生的向量序列x(k)是否一定逐步逼近方程組的解x*呢？回答是不一定.請(qǐng)考慮用迭代法解下述方程組但x(k)并不是所有的都收斂到解x*！x*=(-3,-4)T

這種方式就稱為迭代法.以上過程稱為迭代過程.迭代法產(chǎn)生一個(gè)序列則稱迭代法收斂,否則稱為發(fā)散.(3)

如果對(duì)于任意其極限存在,即

對(duì)線性方程組(2),采用以下迭代步驟:

迭代法的基本思想是通過構(gòu)造迭代格式產(chǎn)生迭代序列，由迭代序列來逼近原方程組的解，因此，要解決的基本問題有：1.如何構(gòu)造迭代格式

2.迭代序列是否收斂設(shè)線性方程組(1)的一般形式為Jacobi迭代G-S迭代SOR迭代法(4)5.5.1

Jacobi迭代法由(4)建立Jacobi迭代公式為(5)將(5)式轉(zhuǎn)化為矩陣形式矩陣形式為稱(5)、(6)式為解線性方程組(1)的Jacobi迭代法(J法)(6)(5)用Jacobi迭代法求解方程組,誤差不超過1e-4解:例2依此類推,得方程組滿足精度的解為x12迭代次數(shù)為12次x4=3.02411.94780.9205d=0.1573x5=3.00031.98401.0010d=0.0914x6=2.99382.00001.0038d=0.0175x7=2.99902.00261.0031d=0.0059x8=3.00022.00060.9998d=0.0040x9=3.00031.99990.9997d=7.3612e-004x10=3.00001.99990.9999d=2.8918e-004x11=3.00002.00001.0000d=1.7669e-004x12=3.00002.00001.0000d=3.0647e-0055.5.2Gauss-Seidel迭代法分析Jacobi迭代法(5)的迭代過程稱(7)、(8)式為解線性方程組(1)的Gauss-Seidel迭代法(G-S法)

雅可比迭代法不使用變量的最新信息計(jì)算xi(k+1)，而由高斯-塞德爾迭代公式可知，計(jì)算x(k+1)的第i個(gè)分量xi(k+1)時(shí)，利用了已經(jīng)計(jì)算出的最新分量xj(k+1)(j=1,2,

,i-1).

可看作雅可比迭代法的一種改進(jìn).高斯—塞德爾迭代公式每迭代一次只需計(jì)算一次矩陣與向量的乘法.G-S迭代法有一個(gè)明顯的優(yōu)點(diǎn)是：在計(jì)算時(shí)，只需一組工作單元，以便存放近似解.而J迭代法需要兩組工作單元，分別存放

和

.例3解:用Gauss-Seidel迭代法求解方程組,誤差不超過1e-4x1=2.50002.09091.2273d=3.4825x2=2.97732.02891.0041d=0.5305x3=3.00981.99680.9959d=0.0465x4=2.99981.99971.0002d=0.0112x5=2.99982.00011.0001d=3.9735e-004x6=3.00002.00001.0000d=1.9555e-004x7=3.00002.00001.0000d=1.1576e-005通過迭代,至第7步得到滿足精度的解x7Jacobi迭代法和Gauss-Seidel迭代法均為簡(jiǎn)單迭代法后面我們會(huì)看到，甚至有這樣的方程組，Jacobi迭代收斂，而Gauss-Seidel迭代卻是發(fā)散的.不能說G-S法比J法更好.從例2和例3看出,Gauss-Seidel迭代法的收斂速度比Jacobi迭代法要快（達(dá)到同樣的精度所需迭代次數(shù)較少).但這個(gè)結(jié)論，在一定條件下才是對(duì)的.

練習(xí)

用Jacobi和Gauss-Seidel迭代法解方程組

Jacobi迭代

Gauss-Seidel迭代解：

kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取x(0)=(0,0,0)T計(jì)算結(jié)果如下：kx1(k)

x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.3

Jacobi迭代Gauss-Seidel迭代5.5.3迭代法的收斂性設(shè)解線性方程組的迭代格式(10)(11)將(10)與(11)相減,得因此迭代法收斂的充要條件可轉(zhuǎn)變?yōu)閯t定理(迭代法收斂的充要條件)

迭代格式收斂的充要條件為(12)

設(shè)Ax=b，其中A=D+L+U為非奇異矩陣,且對(duì)角矩陣D也奇異，則

(1)解線性方程組的雅可比迭代法收斂的充要條件是

(J)<1，其中J=-D-1(L+U).

(2)解線性方程組的高斯-塞德爾迭代法收斂的充要條件是

(G)<1，其中G=-(D+L)-1U.

(3)雅可比迭代法收斂的充分條件是||J||<1.(4)高斯-塞德爾迭代法收斂的充分條件是||G||<1.

由定理5.5.1和定理5.5.2可知解：方程組的迭代格式為取，問雅可比迭代法是否收斂？若收斂，需要迭代多少次，才能保證各分量的誤差絕對(duì)值小于10-6？例4：用雅可比方法解下列方程組迭代陣所以要保證各分量的誤差絕對(duì)值小于10-6，需要迭代14次

求迭代矩陣的譜半徑，需要求迭代矩陣的特征值，對(duì)高階矩陣是比較麻煩的。利用定理5.5.1去判別比較方便一些。但在科學(xué)及工程計(jì)算中，要求解的線性方程組Ax=b,其矩陣A常常具有某些特性.例如，A具有對(duì)角占優(yōu)性質(zhì)或A是對(duì)稱正定矩陣等，根據(jù)這些矩陣的性質(zhì)，可以比較方便地判別這些迭代法的收斂性。兩種特殊情況1.A為嚴(yán)格(按行)對(duì)角占優(yōu)陣2.A是對(duì)稱正定矩陣

定義5.5.3(對(duì)角占優(yōu)陣)設(shè)A=(aij)n×n.如果A的元素滿足稱A為嚴(yán)格(按行)對(duì)角占優(yōu)陣.矩陣A的每一行對(duì)角元素的絕對(duì)值都嚴(yán)格大于非對(duì)角元素絕對(duì)值之和

定理5.5.3(對(duì)角占優(yōu)定理)

如果A=(aij)n×n為嚴(yán)格對(duì)角占優(yōu)矩陣，則A為非奇異矩陣.

定理5.5.4設(shè)方程組Ax=b，如果A為嚴(yán)格對(duì)角占優(yōu)陣，則解Ax=b的Jacobi迭代法,Gauss-Seidel迭代法均收斂.證:(1)對(duì)于Jacobi迭代法,其迭代矩陣為根據(jù)定理5.5.1Jacobi迭代法收斂(2)對(duì)于G—S迭代法,其迭代矩陣為不能使用定理5.5.1,而用定理5.5.2.即從而因此由于可得矛盾由定理5.5.2知G—S迭代法收斂。定理5.5.5設(shè)矩陣A對(duì)稱,且所有對(duì)角元素aii>0,則解線性方程組Ax=b的Jacobi迭代法收斂的充要條件是A及2D-A均為正定矩陣,其中D=(a11,…,ann).(2)解線性方程組Ax=b的Gauss-Seidel迭代法收斂的充分條件是A正定.

如果線性方程組系數(shù)矩陣A對(duì)稱正定，則有以下的收斂定理.

例5已知方程組判斷雅可比迭代法和高斯—塞德爾法的斂散性？

解

因?yàn)橄禂?shù)矩陣A的順序主子式所以A是正定矩陣.也是正定矩陣，故Jacobi迭代法收斂.

再由A是對(duì)稱正定矩陣，故

Gauss—Seidel迭代法也收斂.又由于

例6

在線性方程組Ax=b中，證明：當(dāng)-1/2<a<1時(shí)高斯-塞德爾法收斂，而雅可比法只在-1/2<a<1/2時(shí)才收斂.即A正定，所以當(dāng)-1/2<a<1時(shí)高斯-賽德爾法收斂.

證明

因?yàn)楫?dāng)-1/2<a<1時(shí)，得A的順序主子式

對(duì)雅可比法迭代矩陣故只在

(J)=|2a|<1，即|a|<1/2時(shí)雅可比法收斂.當(dāng)a=0.8時(shí),G-S法收斂，

(J)=1.6>1，J法不收斂.Ax=b，例8判別下列方程組用J法和G-S法求解是否收斂因此不能用定理5.5.1，只能用定理5.5.2判斷(1)Jacobi法的迭代矩陣解:即Jacobi迭代法收斂(2)Gauss-Seidel法的迭代矩陣同樣用定理5.5.2判斷即Gauss-Seidel迭代法發(fā)散該例說明G-S法發(fā)散時(shí)而J法卻收斂！例9

討論用Jacobi迭代法和Gauss-Seidel迭代法求解方程組Ax=b時(shí)的收斂性，如果收斂，并比較哪種方法收斂較快，其中解:(1)對(duì)Jacobi方法，迭代矩陣

(2)對(duì)Gaus