《計(jì)算方法》課件1第2章

第二章線性代數(shù)方程組求解方法2.1向量與矩陣基本知識(shí)2.2高斯消去法2.3矩陣的三角分解2.4矩陣的條件數(shù)與方程組的性態(tài)2.5解線性代數(shù)方程組的迭代法2.6基本迭代法2.7迭代法的收斂性習(xí)題2

2.1向量與矩陣基本知識(shí)

2.1.1引言

在自然科學(xué)和工程技術(shù)中,很多問(wèn)題的解決常常歸結(jié)為求解線性代數(shù)方程組:例如電學(xué)中的網(wǎng)絡(luò)問(wèn)題、船體數(shù)學(xué)放樣中建立三次樣條函數(shù)問(wèn)題、用最小二乘法求實(shí)驗(yàn)數(shù)據(jù)的曲線擬合問(wèn)題、解非線性方程組以及用差分法或有限元法求解偏微分方程等。這些線性代數(shù)方程組的系數(shù)矩陣大致分為兩種：一種是低階稠密矩陣；另一種是大型稀疏矩陣(即矩陣階數(shù)高且零元素較多)。

線性代數(shù)方程組的解法從理論上可分為兩類：直接法和迭代法。

1.直接法

直接法就是不考慮計(jì)算過(guò)程中的舍入誤差，經(jīng)過(guò)有限次的運(yùn)算得到方程組精確解的方法。本章將闡述這類算法中最基本的高斯順序消去法及其某些變形，這類方法是解低階稠密線性代數(shù)方程組及某些大型稀疏線性代數(shù)方程組(例如大型帶狀線性代數(shù)方程組)的有效方法。

2.迭代法

迭代法就是采用某種極限過(guò)程，用線性代數(shù)方程組的近似解逐步逼近精確解的方法。迭代法具有需要計(jì)算機(jī)的存儲(chǔ)單元較少、程序設(shè)計(jì)簡(jiǎn)單、原始系數(shù)矩陣在計(jì)算過(guò)程中始終不變等優(yōu)點(diǎn)，但存在收斂性及收斂速度問(wèn)題。迭代法是求解大型稀疏矩陣對(duì)應(yīng)的線性代數(shù)方程組(尤其是由微分方程離散化后得到的大型稀疏線性代數(shù)方程組)的重要方法。應(yīng)當(dāng)注意的是，這兩種方法的使用并沒(méi)有嚴(yán)格的界限，有時(shí)在解某一個(gè)問(wèn)題時(shí)會(huì)將兩種方法混合使用。用直接法求解線性代數(shù)方程組時(shí)，由于在模型建立過(guò)程及求解過(guò)程中存在誤差的影響，得到的解也不精確，因此在某些精度要求較高的問(wèn)題中，經(jīng)常把用直接法得到的解再用迭代法進(jìn)行若干步迭代，以達(dá)到更高精度的要求。有關(guān)解線性代數(shù)方程組的迭代方法，我們將在第三章介紹。2.1.2向量和矩陣

下面給出一些本書(shū)要用到的定義和基本運(yùn)算。

用Rm×n表示全體m×n階實(shí)矩陣在實(shí)數(shù)域上所構(gòu)成的向量空間，Cm×n表示全體m×n階復(fù)矩陣在復(fù)數(shù)域上所構(gòu)成的向量空間。

其中,ai為A的第i(i=1,2,…，n)列，bTj為A

的第j(j=1，2，

…，m)行。

(1)矩陣加法：

(2)矩陣與標(biāo)量的乘法：

(3)矩陣與矩陣乘法:

(4)矩陣的轉(zhuǎn)置:

(5)單位矩陣:

其中,

(6)非奇異矩陣:設(shè)A,B∈Rn×n,若AB=BA=I，則稱B是A的逆矩陣，記為A-1。若A-1存在，則稱A為可逆矩陣，也稱A為非奇異矩陣。

注意，(A-1)T=(AT)-1，且如果AB均為非奇異矩陣，則有(AB)-1=B-1A-1。

(7)方陣的行列式：設(shè)A∈Rn×n，則A的行列式可按任一行(列)展開(kāi)，即

(i=1，2，…，n)

其中，Aij為矩陣元素aij的代數(shù)余子式，Aij=(-1)i+jMij，而Mij為aij

的余子式。矩陣行列式的性質(zhì)：2.1.3特殊矩陣

設(shè)A=(aij)∈Rn×n，i，j=1，2，…，n，有下列特殊矩陣：

(1)若i≠j時(shí)，有aij=0，則A為對(duì)角矩陣。

(2)若當(dāng)|i-j|>1時(shí)，有aij=0，則A為三對(duì)角矩陣。

(3)若當(dāng)j>i(i>j)時(shí)，有aij=0，則A為上(下)三角矩陣。

(4)若當(dāng)i>j+1時(shí)，有aij=0，則A為上海森伯格(Hessenberg)矩陣。

(5)若AT=A，則A為對(duì)稱矩陣。

(6)設(shè)A∈Cn×n，若AH=A(即A的元素取共軛后再轉(zhuǎn)置等于A)，則A為埃爾米(Hermit)矩陣或H－矩陣。

(7)若①AT=A；②對(duì)任意非零向量x∈Rn，有xTAx>0，則A為實(shí)對(duì)稱正定矩陣。

(8)若A-1=AT，則A為正交矩陣。

(9)設(shè)A∈Cn×n，若A-1=AH，則A為酉矩陣。

(10)對(duì)單位矩陣I交換其第i行與第j(j≥i)行(或交換第i列與第j(j≥i)列)，得到的矩陣記為Iij，它稱為初等置換矩陣，顯然:

①I(mǎi)ijA=A1,A1為交換A中第i行與第j行得到的矩陣；

②AIij=A2,A2為交換A中第i列與第j列得到的矩陣。

(11)由有限個(gè)初等置換矩陣的乘積得到的矩陣稱為置換矩陣。

定理2.1設(shè)A∈Rn×n，則下述命題等價(jià)：

(1)對(duì)任何b∈Rn×n，方程組Ax=b若有解，則只有唯一解；

(2)齊次線性方程組Ax=0只有唯一零解x=0；

(3)det(A)≠0；

(4)A-1存在；

(5)A為滿秩，即rank(A)=n。

定理2.2設(shè)A∈Rn×n為實(shí)對(duì)稱正定矩陣，則:

(1)A為非奇異矩陣，且A-1亦是對(duì)稱正定矩陣；

(2)記Ak為A的順序主子矩陣，則Ak也是對(duì)稱正定矩陣，其中，

(3)A的特征值λi>0(i=1,2,…，n)；

(4)A的順序主子式都大于零，即det(Ak)>0(k=1,2,…，n)。

定理2.3設(shè)A∈Rn×n為對(duì)稱矩陣，若det(Ak)>0(k=1,2,…，n)，或A的特征值λi>0(i=1,2,…，n)，則A為對(duì)稱正定矩陣。

定理2.4(Jordan(若當(dāng))標(biāo)準(zhǔn)型)設(shè)A為n

階矩陣，若存在一個(gè)非奇異矩陣P，使得其中,λ1，λ2,…，λr為A的互不相同的特征值，為若當(dāng)塊，ni≥1(i=1,2,…，r)，且，這就是矩陣A的若當(dāng)標(biāo)準(zhǔn)型。

(1)當(dāng)A的若當(dāng)標(biāo)準(zhǔn)型中所有若當(dāng)塊Ji均為一階塊時(shí)，此標(biāo)準(zhǔn)型變?yōu)閷?duì)角型矩陣；

(2)若A的特征值各不相同，則若當(dāng)標(biāo)準(zhǔn)型必為對(duì)角陣diag(λ1，λ2，…，λn)。2.1.4向量與矩陣的范數(shù)

首先給出向量范數(shù)定義。

定義2.1對(duì)任意向量x∈Rn，若對(duì)應(yīng)一個(gè)非負(fù)實(shí)值函數(shù)‖x‖，滿足下列3條時(shí)，則稱‖x‖為向量x的范數(shù)：

(1)非負(fù)性：‖x‖≥0，‖x‖=0當(dāng)且僅當(dāng)x=0；

(2)齊次性：對(duì)任意實(shí)數(shù)α，有‖αx‖=|α|‖x‖；

(3)三角不等式性：對(duì)任意x,y∈Rn，有

‖x+y‖≤‖x‖+‖y‖。常用的范數(shù)有：

此處0<p<∞，顯然,當(dāng)p=1,2及p→+∞時(shí)，由p－范數(shù)可得到上面的1－范數(shù)、2－范數(shù)和∞－范數(shù)。

例2.1計(jì)算向量x=(1，-2，3)T的各種范數(shù)。

解

向量范數(shù)有如下一些性質(zhì)。

定理2.5(連續(xù)性定理)設(shè)‖x‖是x∈Rn的某種向量范數(shù)，則‖x‖是分量x1，x2，…，xn的連續(xù)函數(shù)。

證明令εi=(0，…，0，1，0，…，0)T，它是Rn空間中第i(i=1，2，…，n)個(gè)單位向量，則對(duì)任何x=(x1，x2，

…，xn)T和y=(y1，y2，…，yn)T，有：根據(jù)向量范數(shù)的齊次性和三角不等式性質(zhì)，有

所以當(dāng)|xi-yi|→0(i=1，2，…，n)時(shí)，有‖x‖→‖y‖。

定理2.6(等價(jià)性定理)設(shè)‖·‖p以及‖·‖q是Rn上兩種向量范數(shù)，則存在正常數(shù)c1，c2使得

c1‖x‖p≤‖x‖q≤c2‖x‖p

對(duì)任何x∈Rn成立。

證明當(dāng)x=0時(shí)結(jié)論顯然成立。下證x≠0時(shí)結(jié)論也成立。記

它是Rn中在范數(shù)‖·‖∞意義下的單位球面。由定理2.5可知，范數(shù)‖·‖p是有界閉集Ω上的連續(xù)函數(shù)，故它在Ω上有最大值M1和最小值m1。

而在Ω內(nèi)，于是有：

故類似地，‖x‖q也是有界閉集Ω上的連續(xù)函數(shù)，它在Ω上也有最大值M2和最小值m2，即有：

因此或

令，，則范數(shù)的等價(jià)性說(shuō)明，一種范數(shù)可由另一種范數(shù)所控制，因而一般地有，Rn上所有范數(shù)是等價(jià)的。

下面給出矩陣范數(shù)定義。

設(shè)Rn×n是n階實(shí)矩陣集合按照實(shí)數(shù)域上矩陣的線性運(yùn)算構(gòu)成的線性空間。

定義2.2對(duì)任意A∈Rn×n，若對(duì)應(yīng)一個(gè)非負(fù)實(shí)數(shù)函數(shù)

‖A‖，滿足以下4條，則稱‖A‖為矩陣A的范數(shù)：

(1)非負(fù)性，即‖A‖≥0，‖A‖=0當(dāng)且僅當(dāng)A=0；

(2)齊次性，即對(duì)任意實(shí)數(shù)α∈R，有

‖αA‖=|α|‖A‖；

(3)三角不等式性，即對(duì)任意A，B∈Rn×n，有

‖A+B‖≤‖A‖+‖B‖；

(4)對(duì)任意A，B∈Rn×n，有‖AB‖≤‖A‖‖B‖。進(jìn)一步，若對(duì)給定的矩陣范數(shù)‖·‖M，它與某個(gè)向量范數(shù)‖·‖V滿足條件(5)，則稱矩陣范數(shù)‖·‖M與向量范數(shù)‖·‖V相容。

(5)對(duì)任意A∈Rn×n，x∈Rn，有

‖Ax‖V≤‖A‖M‖x‖V成立。

設(shè)A=(aij)n×n∈Rn×n，常用的矩陣范數(shù)有：

在矩陣范數(shù)中還有一種由向量范數(shù)導(dǎo)出的矩陣范數(shù)。

定義2.3設(shè)x∈Rn，A∈Rn×n，‖x‖p為向量x的某種向量范數(shù)，定義矩陣A的非負(fù)函數(shù)為

可以驗(yàn)證它滿足矩陣范數(shù)的條件，稱它為從屬于向量范數(shù)‖·‖p的矩陣范數(shù)，簡(jiǎn)稱為從屬范數(shù)，

有時(shí)也稱為算子范數(shù)。

顯然，由向量范數(shù)‖x‖p所導(dǎo)出的矩陣范數(shù)‖A‖p與該向量范數(shù)‖x‖p是相容的。

關(guān)于從屬范數(shù)，有下述結(jié)論。

定理2.7矩陣范數(shù)‖A‖1，‖A‖∞，‖A‖2分別是向量范數(shù)‖x‖1，‖x‖∞，‖x‖2的從屬范數(shù)。

證明

(1)先證明是‖x‖∞的

從屬范數(shù)。

設(shè)x=(x1,x2,…，xn)T≠0，A≠0,令則于是對(duì)任意非零向量x∈Rn，有

下面說(shuō)明至少有一個(gè)x0∈Rn,x0≠0使設(shè)

取向量x0=(β1,β2,…，βn)T，

(j=1，2，

…，n)，由符號(hào)函數(shù)sign定義知‖x0‖∞=1，而

即

(2)再證明是‖x‖1的從屬范數(shù)。

設(shè)則有：

所以對(duì)任意非零向量x∈Rn，都有:設(shè)

取向量x0=(β1,β2,…，βn)T，其中

,

則顯然有‖x0‖1=1,而

所以

(3)最后證明是‖x‖2的從屬范數(shù)。

顯然對(duì)任意x∈Rn，有xTATAx≥0，從而ATA為對(duì)稱半正定矩陣。設(shè)ATA的特征值從大到小依次為λ1≥λ2≥…≥

λn≥0，特征值相應(yīng)的標(biāo)準(zhǔn)正交特征向量為u1,u2,…，un，

對(duì)任意非零向量x∈Rn，有:

所以另一方面，若取x=u1，則有:

故2.2高斯消去法

高斯順序消去法是一個(gè)古老的求解線性代數(shù)方程組的方法(早在公元前250年，我國(guó)就掌握了解線性代數(shù)方程組的消去法)，對(duì)這個(gè)方法進(jìn)行改進(jìn)，變形得到的主元消去法、三角分解法等仍是目前計(jì)算機(jī)上常用的方法。2.2.1高斯順序消去法

設(shè)有線性代數(shù)方程組

(2.1)或?qū)憺榫仃囆问?/p>

簡(jiǎn)記為Ax=b。首先舉一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明順序消去法的基本思想。

例2.2用順序消去法解線性代數(shù)方程組

解第一步，將此方程組第一個(gè)方程乘以－2，加到方程組的第三個(gè)方程上，消去第三個(gè)方程中的未知數(shù)x1，得到與原方程組等價(jià)的方程組第二步，將此方程組第二個(gè)方程加到方程組第三個(gè)方程上，消去第三個(gè)方程中的未知數(shù)x2，得到與原方程組等價(jià)的三角形方程組

對(duì)此方程組經(jīng)過(guò)回代，容易求得其解為x*=(1，2，3)T。上述過(guò)程用矩陣表述如下:由此看出，高斯順序消去法的基本思想是：對(duì)線性代數(shù)方程組(2.1)式所對(duì)應(yīng)的增廣矩陣(A

b)進(jìn)行一系列“把某一行的非零常數(shù)倍加到另一行上”的初等行變換，使得

(A

b)中A的對(duì)角線以下的元素全變?yōu)?，從而使(2.1)式等價(jià)地轉(zhuǎn)化為容易求解的上三角形線性代數(shù)方程組，再通過(guò)回代得到上三角形線性代數(shù)方程組的解，即得到線性代數(shù)方程組(2.1)式的解。為方便敘述，我們記

(2.2)

即

1.消去過(guò)程

第一步，設(shè)，令,把(2.2)式中第1行的li1倍依次加到(2.2)式中的第i行(i=2，3，…，n)，則(2.2)式中第i(i≥2)行第j列(2≤j≤n)位置處的元素為因此，(2.2)式化為

(2.3)第二步，設(shè)，令，把(2.3)式中第2行的li2倍依次加到(2.3)式中的第i行(i=3，4，…，n)，則(2.3)式中第i(i≥3)行第j列(3≤j≤n)位置處的元素為因此，(2.3)式化為

(2.4)依次做下去，一直做到第n－1步，即有

(2.5)

至此,A(1)x=b(1)轉(zhuǎn)化為A(n)x=b(n)。

2.回代過(guò)程

容易看出，線性代數(shù)方程組(2.1)式經(jīng)過(guò)上述n-1步消去過(guò)程以后變?yōu)?2.5)式所對(duì)應(yīng)的上三角形線性代數(shù)方程組。若

以及上述消去過(guò)程中假設(shè),

…,

，則可得xn,xn-1,…，x2，x1為

(k=n－1，n－2，…，2，1)

(2.6)

此即為(2.1)式的解。注意：在Ax=b中，由于A∈Rn×n，為非奇異矩陣，如果a11=0，則A的第一列一定有元素不等于0，比如ai1≠0，于是交換第一行和第i行，將ai1調(diào)到(1，1)的位置，然后進(jìn)行消元計(jì)算，這時(shí)A(2)右下角矩陣為n－1階非奇異矩陣。繼續(xù)此過(guò)程，高斯消去法照樣可繼續(xù)進(jìn)行?？偨Y(jié)上述討論即有定理2.8。

定理2.8設(shè)Ax=b，其中A∈Rn×n，

(1)如果(k=1,2,…，n)，則可通過(guò)高斯順

序消去法將Ax=b化為等價(jià)的上三角形線性代數(shù)方程組(2.5)式，且計(jì)算公式為

(a)消元計(jì)算(k=1，2，…，n－1)：

(b)回代計(jì)算：

(2)如果A為非奇異矩陣，則可通過(guò)高斯消去法(及交換兩行的初等變換)將方程組Ax=b約化為(2.5)式。

(3)如果A的各階順序主子式di≠0(i=1,2,…，n)，則可通過(guò)高斯順序消去法將方程組Ax=b約化為(2.5)式，即

(2.7)下面計(jì)算高斯順序消去法中乘除法運(yùn)算的工作量。

(1)消去過(guò)程中的計(jì)算量。在第k步的消去過(guò)程中，對(duì)矩陣A(k)的元素作n－k次除法運(yùn)算和(n－k)2次乘法運(yùn)算，對(duì)b(k)作n－k次乘法運(yùn)算，于是消去過(guò)程中總的乘除運(yùn)算量為

(2)回代過(guò)程中的計(jì)算量。計(jì)算xk需作(n－k)次乘法運(yùn)算和一次除法運(yùn)算，于是回代過(guò)程中的運(yùn)算量為

因此，用高斯順序消去法計(jì)算線性代數(shù)方程組(2.1)式解的乘除法運(yùn)算次數(shù)為在浮點(diǎn)機(jī)上完成一次乘除運(yùn)算比完成一次加減運(yùn)算所耗的時(shí)間要多得多，故當(dāng)一個(gè)算法中的加減運(yùn)算次數(shù)與乘除運(yùn)算次數(shù)相差不多時(shí)，僅考慮乘除運(yùn)算次數(shù)就可以體現(xiàn)該算法的計(jì)算量。

如果在消去的過(guò)程中考慮進(jìn)行行交換，那么求線性代數(shù)方程組(2.1)式的解所進(jìn)行的乘除法運(yùn)算量不超過(guò)對(duì)于一個(gè)含有20個(gè)未知量的線性代數(shù)方程組，用高斯消去法求解，總的乘除法運(yùn)算量不超過(guò)3440次，用每秒1億次運(yùn)算速度的計(jì)算機(jī)來(lái)完成則是一瞬間的事情，而如果采用線性代數(shù)課程中學(xué)過(guò)的克萊姆法則求解，則其乘除法的運(yùn)算量大約為9.7×1020，也就是說(shuō)，即使用每秒1億次運(yùn)算速度的計(jì)算機(jī)計(jì)算，也需要30多萬(wàn)年。因此，算法的好壞對(duì)計(jì)算能力的提高至關(guān)重要。

例2.3采用四位有效數(shù)字，求下列線性代數(shù)方程組的解：

解方法1采用不進(jìn)行行交換的高斯消去法求解。把的第一行乘以－1764加到第二行,有:

回代可得x2=1.001，x1=－10.00。

方法2采用進(jìn)行行交換的高斯消去法求解。

交換增廣矩陣第一、二行，有：把的第一行乘以－0.0005670加到第二行,有:

回代可得x2=1.000，x1=10.00。從原線性代數(shù)方程組可看出精確解為x1=10.00，x2=1.000，即為方法2所求的解。那么方法1得出的解為何會(huì)有如此大的誤差呢？這主要是因?yàn)樵谟?jì)算x2時(shí)，產(chǎn)生的小誤差0.001導(dǎo)致了在求解x1時(shí)產(chǎn)生了更大的誤差，即誤差擴(kuò)大了20000倍。

從以上例子可以看出，高斯順序消去法是有缺陷的。它并沒(méi)有考慮同列對(duì)角線以下元素絕對(duì)值的大小關(guān)系，有時(shí)會(huì)導(dǎo)致用絕對(duì)值較小的數(shù)字做分母而出現(xiàn)較大的數(shù)字與較小數(shù)字進(jìn)行相加減運(yùn)算而被“吞掉”的現(xiàn)象，以至于產(chǎn)生某一未知元較小的誤差卻引起其它元更大的誤差。為了改變這一缺陷，實(shí)際應(yīng)用時(shí)較多采用高斯主元消去法。2.2.2高斯主元消去法

根據(jù)主元選取范圍不同，主元消去法又分為列主元消去法和全主元消去法。

1.列主元消去法

設(shè)線性代數(shù)方程組(2.1)式的增廣矩陣為首先在的第一列中選取絕對(duì)值最大的元素

作為第一列的主元，即

然后交換中的第一行與第i行，經(jīng)一次消元計(jì)算得

此消去過(guò)程與高斯順序消去法完全相同。重復(fù)上述過(guò)程，設(shè)已完成第k－1步的選主元素，交換兩行及消元過(guò)程后(A

b)已約化為第k步選主元素，在右下角方陣的第一列內(nèi)選取絕對(duì)值最大的元素作為這一列的主元，即

然后交換的第i行與第k行，再進(jìn)行消元計(jì)算。如此重復(fù)上述過(guò)程，直到最后將原線性代數(shù)方程組約化為回代求解

從上面分析可以看出，列主元消去法除了每步需要按列選出主元，然后進(jìn)行對(duì)換外，其消去過(guò)程與高斯順序消去法是相同的。

2.全主元消去法

全主元消去法是對(duì)于一般的矩陣，每一步都在要處理的矩陣(或消元后的低階矩陣)中選取絕對(duì)值最大的元素作為主元，從而使高斯消去法具有更好的數(shù)值穩(wěn)定性的方法。雖然全主元消去法的求解結(jié)果更加可靠，但由于全選主元每步耗時(shí)更多，而且要進(jìn)行列交換，那么所求未知量x1,x2,…,xn的次序就會(huì)被打亂，因此，實(shí)際應(yīng)用中一般使用列主元消去法。

2.3矩陣的三角分解

由線性代數(shù)知道，對(duì)矩陣進(jìn)行一次初等變換，就相當(dāng)于用相應(yīng)的初等矩陣去左乘或右乘原來(lái)的矩陣。因此，我們把上述求解線性代數(shù)方程組的高斯消去法用矩陣乘法表示出來(lái)，即可得到求解線性代數(shù)方程組的另一種直接方法——矩陣的三角分解法。設(shè)(2.1)式的系數(shù)矩陣A∈Rn×n的各階順序主子式均不為0。由于對(duì)A施行初等行變換相當(dāng)于用相應(yīng)的初等矩陣左乘矩陣A，因此對(duì)(2.1)式施行第一次消元后，化為

，其中A(1)化為A(2)

，b(1)化為b(2)，即其中，一般第k步消元后，化為，其中A(k)化為A(k+1)，b(k)化為b(k+1)，相當(dāng)于

LkA(k)=A(k+1)，Lkb(k)=b(k+1)

其中，重復(fù)這個(gè)過(guò)程，最后得到

(2.8)

其中,將上三角形矩陣A(n)記為U，由(2.8)式得

其中,

為單位下三角矩陣。由以上討論可知，高斯順序消去法實(shí)質(zhì)上產(chǎn)生了一個(gè)將A分解為兩個(gè)三角形矩陣相乘的因式。為明確起見(jiàn)，對(duì)矩陣的三角分解有如下定義。

定義2.4設(shè)A為n(n≥2)階方陣，稱A=LU為矩陣A的三角分解，其中L是下三角矩陣，U是上三角矩陣。

定義2.5若L是單位下三角矩陣，U是上三角矩陣，則三角分解A=LU稱為杜利脫爾(Doolittle)分解；若L是下三角矩陣，U是單位上三角矩陣，則稱A=LU為克羅脫(Grout)分解。應(yīng)該注意的是，矩陣A=LU的三角分解是不唯一的，如

其中，L1=LD，U1=D－1U。對(duì)角矩陣D為可逆的非單位矩陣，顯然L1≠L，U1≠U。為了保證A的三角分解的唯一性，我們有如下定理。

定理2.9如果非奇異矩陣A滿足下列三個(gè)條件之一，

則矩陣A有唯一的杜利脫爾分解A=LU和唯一的克羅脫分解

。

(1)A的各階順序主子式det(Ak)>0(k=1,2,…，n)；

(2)

(3)A為對(duì)稱正定矩陣。

證明僅給出條件(1)下杜利脫爾分解唯一性的證明，其余情形讀者可練習(xí)證明。

根據(jù)以上高斯消去法的矩陣分析，當(dāng)det(Ak)>0(k=1,2,…,n)時(shí)，杜利脫爾分解過(guò)程可以進(jìn)行到底，即A=LU的存在性已證。以下證明分解的唯一性。

設(shè)A為非奇異矩陣，且

A=LU=L1U1

其中,L、L1

為單位下三角矩陣，U、U1為上三角矩陣。由于U１－1存在，因此

容易證明上(下)三角矩陣的逆矩陣仍然為上(下)三角矩陣，因而上式右邊為上三角矩陣，左邊為單位下三角矩陣，故上式要成立，兩邊都必須等于單位矩陣，從而U=U1，L=L1。證畢。2.3.1直接三角分解法

將高斯消去法改寫(xiě)為緊湊形式，可以直接從矩陣A的元素得到計(jì)算L、U元素的遞推公式，而不需要任何中間步驟，這就是所謂的直接三角分解法。一旦實(shí)現(xiàn)了矩陣A的LU分解，那么求解線性代數(shù)方程組Ax=b的問(wèn)題就等價(jià)于求解兩個(gè)三角方程組

Ly=b，求y

Ux=y，求x

的問(wèn)題，而這兩個(gè)線性代數(shù)方程組只要回代，就可以求出其解。

1.不選主元的三角分解法

設(shè)A為非奇異矩陣，且有分解式A=LU，其中L為單位下三角矩陣，U為上三角矩陣，即

(2.9)第一步，用L的第一行分別乘U的第j(j=1，2，…，n)列，比較兩邊可得

a1j=u1j

(j=1，2，…，n)

分別用L的第i(i=2，3，…，n)行乘U的第一列，比較兩邊可得

ai1=li1u11

(i=2，3，…，n)

即得

(i=2，3，…，n)

這樣就求出了L的第一列和U的第一行的所有元素。第二步，用L的第二行分別乘U的第j(j=2，3，…，n)列，比較兩邊可得

a2j=l21u1j+u2j

(j=2，3，…，n)

即得

u2j=a2j－l21u1j

(j=2，3，…，n)

分別用L的第i(i=3，4，…，n)行乘U的第二列，比較兩邊可得

ai2=li1u12+li2u22

即得

這樣就求出了L的第二列和U的第二行的所有元素。依次進(jìn)行下去，一直到第k－1步，即已求出L的前k－1列和U的前k－1行的所有元素。

第k步，用L的第k行分別乘U的第j(j=k，k+1，…，n)列，比較兩邊可得

akj=lk1u1j+…+lk，k－1uk－1，j+ukj

(j=k，k+1，…，n)

即得

ukj=akj－(lk1u1j+…+lk，k－1uk－1，j)

(j=k，k+1，…，n)分別用L的第i(i=k+1，…，n)行乘U的第k列，比較兩邊可得

aik=li1uik+…+li，k－1uk－1，k+likukk

(i=k+1，…，n)

即得總結(jié)上述討論，得到用直接三角分解法求解Ax=b(要求A的所有順序主子式都不為零)的計(jì)算公式：及求解Ly=b，Ux=y的計(jì)算公式：

例2.4用杜利脫爾分解法求線性代數(shù)方程組的解：

解設(shè)第一步有：

u11=1,

u12=2,

u13=3

l21=1,

l31=1

第二步有：

u22=1,

u23=2

l32=1

第三步有：

u33=1

l33=1于是有

由Ly=b得y=(2,1,1)T；由Ux=y得x=(1，－1，1)T。

直接三角分解法大約需要次乘除法運(yùn)算，與高斯順序消去法的計(jì)算量基本相同。

2.選主元的三角分解法

從直接三角分解公式可以看出，當(dāng)ukk=0時(shí)，或者當(dāng)ukk絕對(duì)值很小時(shí)，按分解公式計(jì)算可能會(huì)引起舍入誤差的積累，但如果A為非奇異矩陣，則可通過(guò)對(duì)A進(jìn)行行交換后再分解的方法實(shí)現(xiàn)LU分解。也就是說(shuō)，可采用與列主元消去法類似的方法，將直接三角分解法修改為(部分)選主元的三角分解法。

定理2.10對(duì)非奇異矩陣A，存在n階置換陣

(ik≥k)，使得PA有杜利脫爾分解，即PA=LU。

證明由于A為非奇異矩陣，因而有

Ln－1Pn－1…L2P2L1P1A=U

成立，此式等價(jià)于用帶行交換的高斯消元法將A化為上三角形矩陣。其中Lk為單位下三角矩陣；Pk為初等置換矩陣，表示進(jìn)行第k行與它下面的某行進(jìn)行交換，且PkPk=I；U

為上三角形矩陣。從而有其中，容易驗(yàn)證為單位下三角矩陣，因此

例2.5用帶行交換的杜利脫爾分解求線性代數(shù)方程組的解。

解

于是于是

即令P=P2，L－1=P2L1P2，則

這樣我們得到A的杜利脫爾分解為PA=LU。因此，由Ax=b有PAx=Pb，即LUx=Pb，故

回代計(jì)算可得y=(5，7，4)T，x=(2，3，4)T。2.3.2平方根法

許多問(wèn)題的求解所歸納出來(lái)的線性代數(shù)方程組Ax=b，其系數(shù)矩陣常常具有對(duì)稱正定性。由上節(jié)討論可知，這樣的系數(shù)矩陣A一定有唯一的杜利脫爾分解，因而完全可用前述方法分解并求解。然而利用矩陣A的對(duì)稱正定性，我們可以建立更好的三角分解法，這就是下面的平分根法。

定義2.6設(shè)A是n(n≥2)階實(shí)對(duì)稱正定矩陣，L是非奇異的下三角矩陣，則稱A=LLT為矩陣A的喬列斯基(Cholesky)分解。

喬列斯基分解法計(jì)算公式如下所述。設(shè)A為實(shí)對(duì)稱正定矩陣，令A(yù)=LLT，即第一步，分別用L的第i(i=1，2，…，n)行乘LT的第一列，比較兩邊元素可得

a11=l11l11，ai1=l11li1

(i=2，3，…，n)

即得

第二步，分別用L的第i(i=2，3，…，n)行乘以LT第二列，比較兩邊元素可得

即得依次進(jìn)行下去，直到第n－1步。

第n步，用L的第n行乘LT的第n列，比較兩邊元素可得

即得綜上所述，可以得到解對(duì)稱正定方程組Ax=b的平方根法計(jì)算公式，對(duì)于i=1，2，…，n，有：而求解線性代數(shù)方程組Ax=b相當(dāng)于求解兩個(gè)三角形方程組：

Ly=b

(求y)

LTx=y

(求x)

從而有：由計(jì)算公式①知：

所以這說(shuō)明在喬列斯基分解過(guò)程中，元素lis的平方不會(huì)超過(guò)A的最大對(duì)角元素，因而舍入誤差的放大受到了限制。因此，用平方根方法求解對(duì)稱正定矩陣所對(duì)應(yīng)的線性代數(shù)方程組時(shí)可以不考慮選主元問(wèn)題。平方根法約需次乘除法，大約為一般直接LU分解法計(jì)算量的一半。

在上述計(jì)算lis的公式中，由于每步都有開(kāi)方運(yùn)算，因此也稱喬列斯基分解法為平方根法。在用平方根法解對(duì)稱正定矩陣所對(duì)應(yīng)的線性代數(shù)方程組時(shí)，不可避免地要用到開(kāi)方運(yùn)

算，為了避免開(kāi)方運(yùn)算，我們可以對(duì)喬列斯基分解法作以改進(jìn)，從而得到以下定理。

定理2.11

n(n≥2)階對(duì)稱正定矩陣A必有如下分解：

A=LDLT

其中，L是單位下三角矩陣；D是對(duì)角元素全為正的對(duì)角矩陣，并且這種分解是唯一的。

證明因?yàn)锳為對(duì)稱正定矩陣，A的順序主子式全大于0，從而A有唯一的杜利脫爾分解，因?yàn)?/p>

所以故有將等式右端三個(gè)矩陣分別記為L(zhǎng)DR，因?yàn)锳T=A，所以有：

A=LDR=RTDLT=AT

或

A=L(DR)=RT(DLT)

由杜利脫爾分解的唯一性可知，L=RT，LT=R，從而

A=LDLT

即上式分解的唯一性成立。應(yīng)用定理2.11的分解式A=LDLT解線性代數(shù)方程組Ax=b，其分解計(jì)算量與LLT分解計(jì)算量差不多，但LDLT分解不需要開(kāi)方計(jì)算。

例2.6用改進(jìn)的平方根法解方程組：

解

設(shè)由矩陣乘法得即得于是有

從而由Ly=b得y=(2,3,1)T；由DLTx=y得x=(1,1,1)T。

關(guān)于喬列斯基分解的唯一性有如下定理。

定理2.12

n(n≥2)階對(duì)稱正定矩陣A一定有喬列斯基分解A=LLT，當(dāng)限定L對(duì)角線上元素全為正時(shí)，喬列斯基分解是唯一的。

證明由定理2.11可知，存在單位下三角矩陣L1，對(duì)角線元素全為正的對(duì)角矩陣D=diag(u11,u22，…，unn)，使得

記

則有

再令，顯然L是非奇異的下三角矩陣，故A有喬列斯基分解A=LLT，當(dāng)L的對(duì)角線元素全為正時(shí)，由杜利脫爾分解的唯一性可推知喬列斯基分解的唯一性。2.3.3解三對(duì)角方程組的追趕法

有些實(shí)際問(wèn)題，如二階常微分方程邊值問(wèn)題、熱傳導(dǎo)問(wèn)題等導(dǎo)出的線性代數(shù)方程組的系數(shù)矩陣是三對(duì)角矩陣，即Ax=d，其中，并且滿足條件

即三對(duì)角矩陣A是嚴(yán)格對(duì)角占優(yōu)矩陣，此時(shí)A的各階順序主子式不為零，因此A有唯一的杜利脫爾分解。但根據(jù)A是三對(duì)角矩陣的特點(diǎn)，易知三對(duì)角矩陣有如下更特殊的杜利脫爾三角分解式：

A=LU且由矩陣乘法運(yùn)算，比較上式兩邊對(duì)應(yīng)元素可得如下計(jì)算公式：從而將求解方程組Ax=d化為求解兩個(gè)二對(duì)角方程組Ly=d和Ux=y，計(jì)算公式如下：

如果把A進(jìn)行克羅脫分解，則有：

即有由矩陣乘法運(yùn)算，比較上式兩邊對(duì)應(yīng)元素可得如下計(jì)算公式：從而將求解方程組Ax=d化為求解兩個(gè)方程組和，計(jì)算公式為追趕法公式實(shí)際上就是把高斯消去法用到求解三對(duì)角線方程組上去的結(jié)果。這時(shí)由于A特別簡(jiǎn)單，因此使得求解的計(jì)算公式非常簡(jiǎn)單，而且計(jì)算量?jī)H為5n－4次乘法，而另外增加一個(gè)方程組僅增加3n－2次乘法運(yùn)算，可見(jiàn)追趕法的計(jì)算量是比較小的。

例2.7用追趕法求解三對(duì)角線性代數(shù)方程組：

解令A(yù)=LU，即利用矩陣乘法運(yùn)算，再比較兩邊對(duì)應(yīng)元素可得從而從而由Ly=d及Ux=y可算出

2.4矩陣的條件數(shù)與方程組的性態(tài)

考慮線性代數(shù)方程組Ax=b，其中A為非奇異矩陣，x為方程組的精確解。由于A(或b)元素是測(cè)量得到的，或者是計(jì)算的結(jié)果，在第一種情況下，A(或b)常帶有某種觀測(cè)誤差，而在后一種情況下A(或b)又包含有舍入誤差，因此參與線性代數(shù)方程組運(yùn)算的實(shí)際矩陣是A+δA(或b+δb)。本節(jié)討論線性代數(shù)方程組的解對(duì)系數(shù)矩陣A與常數(shù)項(xiàng)b的擾動(dòng)(誤差)的敏感性問(wèn)題。先來(lái)觀察兩個(gè)例子。

例2.8線性代數(shù)方程組：

的精確解為(1,1)T，若A及b作微小擾動(dòng)，擾動(dòng)后的線性代數(shù)方程組為則其精確解為(－2，7)T。由此可見(jiàn)，在本例中，A與b的微小變化引起了x的很大的變化，這表明x對(duì)A與b的擾動(dòng)是敏感的。此例中，detA=－10－4，方程組由兩條幾乎平行的直線組成，因而當(dāng)其中一條直線有很小的變化時(shí)，新交點(diǎn)與原交點(diǎn)相差較遠(yuǎn)。

例2.9線性代數(shù)方程組：的精確解為x=(9.2,－12.6,4.5,－1.1)T，如果對(duì)方程組的系數(shù)矩陣A作微小擾動(dòng)，則變?yōu)?/p>

從而其精確解為x=(－8.1,137,－34,22)T。同樣，解也有很大的誤差。下面來(lái)詳細(xì)分析線性代數(shù)方程組Ax=b中向量b和系數(shù)矩陣A的微小擾動(dòng)對(duì)解x的影響。首先來(lái)看一些相關(guān)基本概念。

如例2.8和例2.9所示，當(dāng)方程組的系數(shù)矩陣A或b有微小變化時(shí)，方程組的解可能會(huì)產(chǎn)生很大的變化，這樣的方程組稱為病態(tài)方程組。

定義2.7如果矩陣A或常數(shù)項(xiàng)b的微小變化，引起方程組Ax=b解的巨大變化，則稱此方程組為“病態(tài)方程組”，相對(duì)于方程組而言，矩陣A稱為“病態(tài)”矩陣，否則稱方程組

為“良態(tài)”方程組，A為“良態(tài)”矩陣。

應(yīng)該注意，矩陣的“病態(tài)”性質(zhì)是矩陣本身的特性，下面希望找出刻畫(huà)矩陣“病態(tài)”性質(zhì)的量。設(shè)有方程組：

Ax=b

(2.10)其中，A為非奇異矩陣，x為(2.10)式的精確解，以下我們來(lái)研究方程組的系數(shù)矩陣A(或b)的微小誤差(擾動(dòng))對(duì)解的影響問(wèn)題。

1.常數(shù)項(xiàng)b有擾動(dòng)

設(shè)A是精確的，b有誤差δb，解為x+δx，即

A(x+δx)=b+δb

則

δx=A－1δb

‖δx‖≤‖A－1‖‖δb‖

(2.11)

由(2.10)式得‖b‖≤‖A‖‖x‖，即

(2.12)

于是由(2.11)式及(2.12)式得定理2.13。

定理2.13設(shè)A是非奇異矩陣，Ax=b≠0,且A(x+δx)=b+δb,則

(2.13)

上式給出了解的相對(duì)誤差的上界，常數(shù)項(xiàng)b的相對(duì)誤差在解中可能放大‖A－1‖‖A‖倍。

2.系數(shù)矩陣A有擾動(dòng)

設(shè)(2.10)式中b是精確的，A有微小誤差(擾動(dòng))δA，解為x+δx，即

(A+δA)(x+δx)=b

則

(A+δA)δx=－(δA)x

而

A+δA=A(I+A－1δA)當(dāng)‖A－1δA‖<1時(shí)，(I+A－1δA)－1存在，則有

δx=－(I+A－1δA)－1A－1(δA)x

因此設(shè)

‖A－1‖‖δA‖<1

即得

(2.14)

3.系數(shù)矩陣A和常數(shù)項(xiàng)b都有擾動(dòng)

設(shè)(2.10)式中A和b都有小擾動(dòng)時(shí)，解為x+δx，即

(A+δA)(x+δx)=(b+δb)

則

(A+δA)δx=δb－δAx

得

δx+A－1δAδx=A－1δb－A－1δAx從而

‖δx‖－‖A－1‖‖δA‖‖δx‖≤‖A－1‖‖δb‖

+‖A－1‖‖δA‖‖x‖

兩邊同除‖x‖，并由(2.12)式得當(dāng)‖A－1‖‖δA‖<1時(shí)，可得

(2.15)

分析(2.13)~(2.15)式可知，無(wú)論方程組(2.10)式中右端常數(shù)項(xiàng)b有擾動(dòng)，還是系數(shù)矩陣A有擾動(dòng)，或者兩者都有擾動(dòng)，總之，量‖A－1‖‖A‖愈小，由A(或b)的相對(duì)誤差

引起的解的相對(duì)誤差就愈小，量‖A－1‖‖A‖愈大，解的相對(duì)誤差就愈大，所以量‖A－1‖‖A‖實(shí)際上刻畫(huà)了解對(duì)原始數(shù)據(jù)變化的靈敏程度，即刻畫(huà)了方程組的“病態(tài)”程度。

定義2.8設(shè)A為n階非奇異矩陣，稱數(shù)

Cond(A)v=‖A‖v‖A－1‖v

為矩陣A的條件數(shù)。其中，‖·‖v為Rn×n中的某種矩陣范數(shù)。

由此看出，矩陣的條件數(shù)與矩陣范數(shù)有關(guān)。矩陣的條件數(shù)是一個(gè)十分重要的概念，由上面討論知，當(dāng)A的條件數(shù)相對(duì)比較大，即Cond(A)>>1時(shí)，方程組Ax=b是“病態(tài)”的(即A為“病態(tài)”或者說(shuō)相對(duì)于解方程組來(lái)說(shuō)A是壞條件的)；當(dāng)A的條件數(shù)相對(duì)較小時(shí)，方程組Ax=b是“良態(tài)“的(或者說(shuō)A是好條件的)。注意，方程組病態(tài)性質(zhì)是方程組本身的特性，A的條件數(shù)愈大，方程組的病態(tài)程度愈嚴(yán)重，也就愈難用一般的計(jì)算方法求比較精確的解。常用的條件數(shù)有：條件數(shù)的性質(zhì)有：

(1)對(duì)任意非奇異矩陣A∈Rn×n，有Cond(A)≥1；

(2)對(duì)任意非奇異矩陣A∈Rn×n及c∈R，c≠0，有Cond(cA)=Cond(A)；

(3)對(duì)于任意正交矩陣A，有Cond(A)2=1;

(4)如果P為正交矩陣，A為非奇異矩陣，則有Cond(PA)2=Cond(AP)2=Cond(A)2。

例2.10已知希爾伯特(Hilbert)矩陣:

計(jì)算H3的條件數(shù)。

解

(1)計(jì)算H3的條件數(shù)Cond(H3)10：

同理可計(jì)算得Cond(H6)∞=2.9×107，Cond(H7)∞=

9.85×108?？梢?jiàn)，隨著n的增大，Cond(Hn)2急劇增加，因此，以Hn為系數(shù)矩陣的線性代數(shù)方程組Hnx=b是嚴(yán)重病態(tài)的。

(2) 考慮方程組

設(shè)H3及b有微小誤差(取3位有效數(shù)字)，有：

(2.16)簡(jiǎn)寫(xiě)為(H3+δH3)(x+δx)=b+δb，方程組H3x=b與(2.16)式的精確解分別為

x=(1，1，1)T

x+δx=(1.089512538,0.487967062,1.491002798)T于是δx=(0.089512538,－0.512032938,

0.491002798)T，可以算得：

這就是說(shuō),H3與b的相對(duì)誤差不超過(guò)0.2%，而引起的解的相對(duì)誤差則超過(guò)了50%。由上述例題可以看出，對(duì)于給定的線性代數(shù)方程組Ax=b，要判斷它是否病態(tài)并不容易，因?yàn)橛脳l件Cond(A)=‖A‖‖A－1‖判斷時(shí)要求出A－1，而計(jì)算A－1是比較費(fèi)勁的，那么在實(shí)際計(jì)算中如何發(fā)現(xiàn)病態(tài)情況呢？

(1)如果在系數(shù)矩陣A的三角分解時(shí)(尤其是用主元素消去法解(2.10)式)出現(xiàn)小主元，則對(duì)大多數(shù)矩陣來(lái)說(shuō)，A可能是病態(tài)的。

(2)系數(shù)矩陣A的行列式值相對(duì)很小，或系數(shù)矩陣某些行近似線性相關(guān)，則A可能是病態(tài)的。

(3)系數(shù)矩陣A的元素間數(shù)量級(jí)相差很大，并且無(wú)一定規(guī)則，則A可能是病態(tài)的。一般病態(tài)線性代數(shù)方程組的求解是比較困難的，線性代數(shù)方程組給定時(shí)，其系數(shù)矩陣的條件數(shù)也是隨之確定的，因而線性代數(shù)方程組的性態(tài)是方程組本身固有的性質(zhì)，與求解線性方程組的算法無(wú)關(guān)。

在計(jì)算機(jī)上求解線性方程組，都是所給方程組的擾動(dòng)方程組，這是因?yàn)閷⑾禂?shù)矩陣和常數(shù)項(xiàng)輸入計(jì)算機(jī)后，機(jī)器要對(duì)數(shù)作十進(jìn)制和二進(jìn)制轉(zhuǎn)化，由于字長(zhǎng)的限制總有誤差。對(duì)于良態(tài)方程組，只要求解方法穩(wěn)定，即可得到比較滿意的計(jì)算結(jié)果；但對(duì)于病態(tài)方程組，即使采用穩(wěn)定性好的算法也未必能得到理想解。對(duì)于病態(tài)方程組Ax=b，實(shí)際應(yīng)用中使用下述兩種方法進(jìn)行處理：

(1)采用高精度的算術(shù)運(yùn)算。如采用雙精度運(yùn)算，使由于舍入誤差的放大而損失若干有效數(shù)位后，還能保留一些有效數(shù)位，改善或減輕“病態(tài)”影響。

(2)對(duì)方程組進(jìn)行預(yù)處理。如用可逆對(duì)角矩陣對(duì)方程組進(jìn)行矩陣平衡，降低系數(shù)矩陣的條件數(shù)。具體作法是尋找可逆對(duì)角矩陣D，使方程組Ax=b轉(zhuǎn)化為等價(jià)方程組DAx=Db，并且使DAx=Db的條件數(shù)相對(duì)較小，如計(jì)算(i=1，2，…)，取D=diag(S－11，S－12，

…，S－1n)，那么Cond(DA)的值比Cond(A)要小得多。

例2.11對(duì)線性代數(shù)方程組：

(2.17)

計(jì)算條件數(shù)Cond(A)∞。

解

可見(jiàn)原方程組為病態(tài)方程組。現(xiàn)對(duì)方程組進(jìn)行預(yù)處理。

取，

得

設(shè)DA=A′，Db=b′,則有同解方程組:

A′x=b′

(2.18)而

于是當(dāng)用列主元消去法解(2.17)式時(shí)(計(jì)算到三位數(shù)字)：

得到很壞的結(jié)果：x2=1，x1=0。

現(xiàn)用列主元消去法解(2.18)式，得到

從而得到較好的解：x1=1，x2=1。2.5解線性代數(shù)方程組的迭代法

考慮線性代數(shù)方程組:

Ax=b

(2.19)其中,A為非奇異矩陣，當(dāng)A為低階稠密矩陣時(shí)，選主元消去法是解(2.19)式的有效方法，但是，對(duì)由工程技術(shù)中產(chǎn)生的大型稀疏矩陣方程組(A的階數(shù)n

很大，零元素很多，例如求某些偏微分方程數(shù)值解所產(chǎn)生的線性方程組，n≥104)，利用迭代法求解(2.19)式是合適的。在計(jì)算機(jī)的內(nèi)存和運(yùn)算方面，迭代法通常都可利用A中有大量零元素的特點(diǎn)。本節(jié)將介紹迭代法的一些基本理論及雅可比(Jacobi)迭代(簡(jiǎn)稱J－迭代)、高斯賽德?tīng)?Gauss-Seidel)迭代(簡(jiǎn)稱GS-迭代)、逐次超松弛(SuccesiveOver-Relaxation)迭代(簡(jiǎn)稱SOR-迭代)和對(duì)稱逐次超松弛(SymmetricSuccessiveOverRelaxation)迭代(簡(jiǎn)稱SSOR迭代)。其中，超松弛迭代法應(yīng)用很廣泛。

先看下面簡(jiǎn)例，以便了解迭代法的基本思想。

例2.12求解線性代數(shù)方程組：

(2.20)

解記為Ax=b，其中，線性代數(shù)方程組的精確解x*=(3，2，1)T。現(xiàn)將(2.20)式改寫(xiě)為

(2.21)

也可簡(jiǎn)寫(xiě)為

x=Bx+f其中，任取初始值，比如取x(0)=(0，0，0)T，代入(2.21)式右邊(若(2.21)式為等式即求得線性代數(shù)方程組的解，但一般不滿足)，得到新的值x(1)=(x(1)1，x(1)2，x(1)3)T=(2.5,3,3)T，再將x(1)代入(2.21)式右邊得到x(2)。反復(fù)利用這個(gè)計(jì)算程序，得到一個(gè)向量序列和一般的計(jì)算公式(迭代公式)：

(2.22)簡(jiǎn)寫(xiě)為

x(k+1)=Bx(k)+f

其中，k表示迭代次數(shù)(k=0，1，2，…)。

迭代到第10次時(shí)有：

x(10)=(3.000032,1.999838,0.9998813)T

‖ε(10)‖∞=0.000187

(ε(10)=x(10)－x*)

從此例看出，由迭代法產(chǎn)生的向量序列x(k)逐次逼近線性代數(shù)方程組的精確解x*。對(duì)于任何一個(gè)線性代數(shù)方程組x=Bx+f(由Ax=b變形得到的等價(jià)方程組)，由迭代法產(chǎn)生的向量序列x(k)是否一定逐步逼近線性代數(shù)方程組的解x*呢？回答是不一定。請(qǐng)讀者考慮用迭代法解下述方程組：對(duì)于給定方程組x=Bx+f，設(shè)有唯一解x*，則

x*=Bx*+f

(2.23)

又設(shè)x(0)為任取的初始向量，按下述公式構(gòu)造向量序列

x(k+1)=Bx(k)+f

(k=0，1，2，…)(2.24)其中，k表示迭代次數(shù)。

定義2.9

(1)對(duì)于給定的線性代數(shù)方程組x=Bx+f，用(2.24)式逐步代入求近似解的方法稱為迭代法(或稱為一階定常迭代法，這里B與k無(wú)關(guān))。

(2)如果存在(記為x*)，則稱此迭代法收斂，顯然，x*就是線性代數(shù)方程組的解，否則稱迭代法發(fā)散。由上述討論，需要研究{x(k)}的收斂性。引入誤差向量：

ε(k+1)=x(k+1)－x*

由(2.24)式減去(2.23)式得

ε(k+1)=Bε(k)

(k=0,1,2,…)

遞推得

ε(k)=Bε(k－1)=…=Bkε(0)

可見(jiàn)要考察{x(k)}的收斂性，就要研究B在什么條件下有

，即要研究B滿足什么條件時(shí)有。2.6基本迭代法

對(duì)線性代數(shù)方程組:

Ax=b(2.25)

其中，A=(aij)∈Rn×n為非奇異矩陣，下面研究如何建立解Ax=b的各種迭代方法。

將A分裂為

A=M－N

(2.26)其中，M為非奇異矩陣，且要求線性代數(shù)方程組Mx=d容易求解，一般選擇為A的某一部分元素構(gòu)成的矩陣，稱M為A的分裂矩陣。于是，求解Ax=b轉(zhuǎn)化為求解Mx=Nx+b，

即

由此可構(gòu)造一個(gè)迭代法

(2.27)

其中，B=M－1N=M－1(M－A)=I－M－1A，f=M－1b，稱

B=I－M－1A為迭代法的迭代矩陣。通過(guò)選取不同的M矩陣，就可得到解Ax=b的各種迭代方法。設(shè)aii≠0(i=1,2,…，n)，將A分為三部分：

(2.28)2.6.1雅克比迭代法(J-迭代法)

由aii≠0(i=1,2,…，n)，選取M為A的對(duì)角元素組成的矩陣，即選取M=D(對(duì)角陣)，因此A=D－N。由(2.27)式得到解Ax=b的雅克比迭代法：

(2.29)

其中，BJ=I－D－1A=D－1(L+U)，f=D－1b，稱BJ為求解Ax=b的雅克比迭代法的迭代矩陣。以下給出雅克比迭代的分量計(jì)算公式。令x(k)=(x(k)1，x(k)2，…，x(k)n)T，由雅克比迭代公式(2.29)有：

即有于是，解Ax=b的雅克比迭代法的計(jì)算公式為

(2.30)

由(2.30)式可知，雅克比迭代法的計(jì)算公式簡(jiǎn)單，每迭代一次只需計(jì)算矩陣和向量的乘法一次，且計(jì)算過(guò)程中原始矩陣A的元素始終不變。

例2.13用J迭代法計(jì)算線性代數(shù)方程組：

的近似解x(k+1)，要求‖x(k+1)－x(k)‖∞<10－5(精確解為x1=3,x2=4,x3=－5)。

解應(yīng)用J-迭代法，取x(0)=(1，1，1)T，得到迭代公式對(duì)k=0，1，…，計(jì)算得

x(1)=(5.250000,7.000000,-5.750000)T

x(2)=(0.750000,2.125000,-4.250000)T

x(58)=(2.999996,3.999996,-4.999999)T

且滿足‖x(58)－x(57)‖∞<10－5。2.6.2高斯-賽德?tīng)柕?GS-迭代法)

選取矩陣M為A的下三角部分，即M=D－L(下三角矩陣)，因此A=M－N，由(2.27)式得到解Ax=b的高斯賽德?tīng)柕ǎ?/p>

(2.31)

其中，BG=I－(D－L)－1A=(D－L)－1U，f=(D－L)－1b，

稱BG=(D－L)－1U為解Ax=b的高斯-賽德?tīng)柕ǖ牡?/p>

陣。以下給出高斯-賽德?tīng)柕ǖ姆至坑?jì)算公式。記x(k)=(x(k)1，x(k)2，…，x(k)n)T，由(2.31)式有：

(D－L)x(k+1)=Ux(k)+b

即

得于是，解Ax=b的高斯賽德?tīng)柕ǖ挠?jì)算公式為

(2.32)雅克比迭代法不使用變量的最新信息計(jì)算xi(k+1)，而由高斯-賽德?tīng)柕?2.32)可知，計(jì)算x(k+1)的第i個(gè)分量xi(k+1)時(shí),利用了已經(jīng)計(jì)算出的最新分量xj(k+1)(j=1，2，…，i－1),高斯-賽德?tīng)柕煽醋鍪茄趴吮鹊ǖ囊环N改進(jìn)。由(2.32)式可知，高斯-賽德?tīng)柕康淮沃恍栌?jì)算一次矩陣與向量的乘法。

例2.14用高斯-賽德?tīng)柕ń饩€性方程組(2.20)。

解應(yīng)用高斯-賽德?tīng)柕?，取x(0)=(0，0，0)T，得對(duì)k=0，1，…，計(jì)算

x(1)=(2.500000,2.090909,1.227273)T

x(7)=(3.000002,1.9999987,0.9999932)T

此時(shí)‖x*－x(7)‖∞<2.02×10－6。由此例可知，用高斯-賽德?tīng)柕ā⒀趴吮鹊ń馔痪€性代數(shù)方程組(2.20)(且取x(0)=(0,0,0)T)時(shí)均收斂，而高斯-賽德?tīng)柕ū妊趴吮鹊ㄊ諗靠欤?即取相同初始值x(0)，在同樣精度要求下，高斯-賽德?tīng)柕ㄋ璧螖?shù)較少)，