第3章 線性代數(shù)方程組的解法

第三章線性代數(shù)方程組的解法引言高斯消去法高斯列主元消去法矩陣分解法向量和矩陣范數(shù)解線性代數(shù)方程組的迭代法第一節(jié)引言

快速、高效地求解線性方程組是數(shù)值線性代數(shù)研究中的核心問(wèn)題，也是目前科學(xué)計(jì)算中的重大研究課題之一。各種各樣的科學(xué)和工程問(wèn)題，往往最終都要?dú)w結(jié)為求解一個(gè)線性方程組。線性方程組的數(shù)值解法有：直接法和迭代法。直接法：在假定沒(méi)有舍入誤差的情況下，經(jīng)過(guò)有限次運(yùn)算可以求得方程組的精確解；(快速有效)迭代法：從一個(gè)初始向量出發(fā)，按照一定的迭代格式，構(gòu)造出一個(gè)趨向于真解的無(wú)窮序列(節(jié)省內(nèi)存)。高斯消去法是解線性方程組最常用的方法之一，它的基本思想是通過(guò)逐步消元，把方程組化為系數(shù)矩陣為三角形矩陣的同解方程組，然后用回代法解此三角形方程組可得方程組的解。第二節(jié)高斯消去法我們知道，下面有3種方程的解我們可以直接求出：①②上三角③下三角消元法就是對(duì)方程組做些等價(jià)的變換，變?yōu)槲覀円阎?種類型之一，而后求根。對(duì)方程組，作如下的變換，解不變①交換兩個(gè)方程的次序②一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0的數(shù)③一個(gè)方程的兩邊同時(shí)乘以一個(gè)非0數(shù)，加到另一個(gè)方程因此，對(duì)應(yīng)的對(duì)增廣矩陣(A,b)，作如下的變換，解不變。①交換矩陣的兩行②某一行乘以一個(gè)非0的數(shù)③某一行乘以一個(gè)非0數(shù)，加到另一行舉例（一）解：例：直接法解線性方程組高斯消去法的主要思路：將系數(shù)矩陣A經(jīng)過(guò)消元過(guò)程化為上三角矩陣，然后回代求解?？紤]一般n階線性方程組：矩陣形式=

即:相當(dāng)于第i個(gè)方程-第一個(gè)方程×數(shù)→新的第i方程同解！第一方程不動(dòng)！

一、Gauss消去法計(jì)算過(guò)程第一步消元：消元：上述消元過(guò)程除第一個(gè)方程不變以外,第2—第n個(gè)方程全消去了變量1，而系數(shù)和常數(shù)項(xiàng)全得到新值：每步消元，先計(jì)算系數(shù)，然后計(jì)算矩陣新元素及右端項(xiàng)系數(shù)矩陣與常數(shù)項(xiàng)：討論第K次消元，得到消元公式第K次消元目的：aik(k)=0(i=k+1….n),設(shè)akk(k)≠0,為使aik(k)=0(i=k+1….n）選取適當(dāng)因子M使aik(k)-Makk(k)=0可求出

M=aik(k)/akk(k)第i個(gè)方程其他系數(shù)的變化為（Ri-M.Rk)aij(k+1)=aij(k)–M.akj(k)(i=k+1….n,j=k+1…..n+1)所以，第K次消元時(shí)（后）（K=1….n-1)消元因子：

M=aik(k)/akk(k)(i=k+1,n）系數(shù)變化：

①aij(k+1)=aij(k)

（i≤k)

②aij(k+1)=aij(k)-M.akj(k)(i>k,j=k+1…n+1)最后得到：[A(n)|b(n)](n-1次消元后）其增廣矩陣為：回代：

Xn=ann+1(n)/ann(n)

編程時(shí)，為節(jié)省內(nèi)存將Xn放在ann+1(n)

同理Xi放在

ain+1(i)

第i次回代公式（i=n-1…..1)Xi(即ain+1(i))=(ain+1(i)-）/aii(i)二、算法描述1、消元對(duì)k=1…..n-1

消元因子：

C=aik(k)/akk(k)

(i=k+1….n）系數(shù)變化：

①aij(k+1)=aij(k)

（i≤k)②aij(k+1)=aij(k)-C.akj(k)

(i>k,j=k+1,…,n+1)2、回代第i次回代公式（

i=n,n-1….1)Xi(即ain+1(i))=(ain+1(i)-）/aii(i)

三、特點(diǎn)1、優(yōu)點(diǎn)：公式簡(jiǎn)明，容易程序化2、缺點(diǎn)：第k次消元時(shí)，必須

akk

≠0,且當(dāng)

akk

0時(shí)，誤差很大，數(shù)值不穩(wěn)定(p35N-S圖）第三節(jié)GAUSS列主元消去法一、高斯消去法的缺點(diǎn)在簡(jiǎn)單的高斯消去法中，如果遇到

a（k）kk=0,則消去過(guò)程就會(huì)中斷，如果a（k）kk≠0，但其絕對(duì)值很小時(shí)，在高斯消去法中，因?yàn)镸=aik(k)/akk(k)

，所以不是因?yàn)镸數(shù)值過(guò)大，就是舍入誤差過(guò)大，與實(shí)際的解相差很遠(yuǎn)。

零主元或小主元問(wèn)題例如：求解下列方程組此方程組的準(zhǔn)確解為：x1=10.00；x2=1.00下面采用高斯消去法解方程組（取四位有效數(shù)字），消元后得-1043x2=-1044，則x2=1.001.

將x2代入第一個(gè)方程中，得x1=-9.713顯而易見(jiàn)，利用高斯消去法得到的結(jié)果與精確解相差太懸殊了從求解過(guò)程可以看出，在第一種解法中，乘以的系數(shù)為m=5.291/0.0030如果將兩個(gè)方程互換，再采用高斯消去法解方程組消元后得59.14x2=59.14，則x2=1.000

將x2代入第一個(gè)方程中，得x1=10.000此時(shí)，利用高斯消去法得到的結(jié)果與精確解一致。從求解過(guò)程可以看出，在第一種解法中，乘以的系數(shù)為m=5.291/0.0030，第二種解法中，乘以的系數(shù)為m=0.0030/5.291。我們希望m盡量小，希望主元盡可能大，就有了列主元消去法（按列）。二、列主元消去法

1、選主元再消元在每一步消元之前，即第k次消元時(shí)，在第k列上選取絕對(duì)值最大的元素為主元素

ai0k(最大值在i0行上）

若|ai0k|<εp中斷否則若i0≠k

將i0和k行互換

再按高斯消去法消元

2、回代不改變方程組的解，同時(shí)又有效地克服了Gauss消元的缺陷

三、算法描述1、選主元（對(duì)

k=1…..n-1)(1)p(主元素）0(2)對(duì)

i=k……n做若|aik|>p則p|aik|i0i2、換行

a

kj<-->ai0j(j=k……n)3、消元：同Gausss4、回代:同Gausss

（p175)

取四位有效數(shù)字計(jì)算。解②中-18為主元,交換②和①得

①②③①②③例1用列主元素消去法解方程組

②+①×12/18,③+①×1/18得

①②③第二列消元時(shí),主元為1.167,交換方程②和③得①②③③+②×1/1.167得①②③回代求得

x1=1.000,x2=2.000,x3=3.001方程組的實(shí)際解

x1=1,x2=2,x3=3四、高斯―約當(dāng)消去法

前面所述的消去法均要進(jìn)行兩個(gè)過(guò)程,即消元過(guò)程和回代過(guò)程。但對(duì)消元過(guò)程稍加改變可以把方程組化為對(duì)角形

此時(shí)求解就不要回代了。這種無(wú)回代過(guò)程的主元素消去法稱為高斯―約當(dāng)(Jordan)消去法。特別是方程組還可化為

顯然等號(hào)右端即為方程組的解。對(duì)于n階線性方程組,其增廣矩陣為首先把主元素(按列選主元或全選主元)調(diào)換到主對(duì)角線上,并化為1,再將主元素所在列的其它元素消為0練習(xí)：1、用GAUSS消去法解方程組

2x1+x2+x3=4x1+3x2+2x3=6x1+2x2+2x3=52、用GAUSS列主元消去法解方程組

2x1+x2+2x3=55x1-x2+x3=8x1-3x2-4x3=-43、用GAUSS列主元消去法解方程組

-3x1+2x2+6x3=410x1-7x2=75x1-x2+5x3=6第四節(jié)矩陣分解法（直接法）復(fù)習(xí)、基本概念1、順序主子式（P40定義1）

n*n階矩陣A的左上角P*P階子矩陣的行列式

P=稱為A的P階順序主子式2、正定矩陣特征值都大于0(或各階順序主子式都大于0)的實(shí)矩陣(如何求特征值？）

解特征多項(xiàng)式|λE-A|=03.矩陣相乘公式Cm×n=Am×kB

k×nA的第i行

(ai1ai2….aik)B的第j列（b1jb2j……bkj)cij=(ai1b1j+ai2b2j+….aikbkj)=

思考:下面矩陣左乘的結(jié)果?設(shè)li1=ai1(1)/a11(1)==結(jié)果為:M=------為第2次消元后的結(jié)果?2第四節(jié)矩陣分解法（直接法）一、三角分解法從矩陣的初等變換來(lái)看,前面講的高斯消去法和列主元消去法來(lái)解方程，實(shí)際是通過(guò)一系列的初等變換將方程組的系數(shù)矩陣A化為三角矩陣，其每一步的消元過(guò)程相當(dāng)于對(duì)增廣矩陣(A,b)作一次初等變換。下面將上述這種方程組的消去過(guò)程通過(guò)矩陣分解來(lái)實(shí)現(xiàn)。在消去第一列中的ai1(i=2,3,…,n)時(shí),左乘的矩陣為令：在消去第一列中的ai1(i=2,3,…,n)時(shí),左乘的矩陣為2在消去第二列中的ai2(i=2,3,…,n)時(shí),左乘的矩陣為這樣就把A化為一個(gè)上三角矩陣U，即根據(jù)得A=LU稱為矩陣A的LU分解或三角分解。把A分解為一個(gè)單位下三角陣L和一個(gè)上三角陣的乘積，稱為A的LU分解，也叫Doolittle（杜利特爾）分解。一般的，如果能把系數(shù)矩陣分解為A=LU，其中L為單位下三角陣，U為非奇異上三角陣，那么方程Ax=b可化為

LUx=b

令Ux=y，則有Ly=b，這樣原方程組轉(zhuǎn)化為先解下三角方程組Ly=b，求出y，再解上三角方程組Ux=y求出x。即:a11a12….a1n1

u11u12..u1i…u1na21a22……a2nl211

u22

.u2i…u2n……………ar1ar2……a

rn

lr1lr2……1(lrr)uii..uin…………..…………..…an1an2…annln1ln2……...1

unn

=

正如高斯消去法中的消元過(guò)程不一定能進(jìn)行到底那樣，一個(gè)矩陣也不一定能進(jìn)行LU分解。由下面討論能進(jìn)行LU分解的條件。定理1：(p40)nxn階矩陣有唯一LU分解的充分必要條件是矩陣A的各階順序主子式都不等于0。證明略。我們關(guān)心的是如何進(jìn)行LU分解，即如何把LU求出來(lái)。設(shè)A的各階順序主子式都不等于0，并設(shè)L=(lij),U=(uij)。由A=LU知：a11a12…a1na21a22…a2n……ar1ar2…arn……an1an2…annlr1

lr2

lr3U=先計(jì)算U的第一行，L的第一列元素，有矩陣乘法知

a1j=u1j(j=1,2,…,n)

ai1=li1u11(i=2,3,…n)得到

u1j=a1j(j=1,2,…,n)

li1=ai1/u11(i=2,3,…,n)類似的由A的第二（r）行元素，計(jì)算U的第二（r）行，由A的第二（r）列元素計(jì)算L的第二（r）列元素。一般的計(jì)算U的第r行，L的第r列元素的方法設(shè)計(jì)考慮A的第r行，第r列元素，由矩陣乘法知：由得到由得到按公式將A進(jìn)行LU分解后，此時(shí)AX=b

LUx=b令Ux=y，則Ly=b，方程組Ax=b化為下列兩個(gè)等價(jià)的方程組

Ly=b

Ux=y

y1b1y2=b2…...

yn

bn

y1=b1l21y1+y2=b2

li1y1+li2y2+….Lii-1yi-1+yi=bi……….ln1y1+ln2y2+………+yn=bn可以計(jì)算yi(下三角方程組)再帶入U(xiǎn)X=Y………x1y1x2=y2…………xn

yn同理，可求：xn=yn/unn=a11=u11a12=u12

u11=a11u12=a12a21=l21u11a22=l21u12+u22

l21=a21/u11u22=a22-l21u12

注意計(jì)算順序u11u12u13……….u1nl21l31….ln1第一步計(jì)算u22u23………u2nl32….ln2第二步計(jì)算….

unn第n步計(jì)算LU計(jì)算的緊湊格式例3用杜利特爾分解方法求解下列方程組的解：2-11-3647/3-8解：利用上面3-19計(jì)算公式

可求得

再由Ly=b求出y后根據(jù)Ux=y最后求得原方程組的解為從上面的討論我們可以看到,用LU分解方法解線性方程組,就是將其化為依次求解下面兩個(gè)三角形方程組:Ly=b

Ux=y顯然求解Ly=b的過(guò)程即為消元過(guò)程,它只不過(guò)是對(duì)

LUx=b

兩端左乘L-1而得,即

Ux=L-1b=y

而求解Ux=y的過(guò)程即為回代過(guò)程。因此三角分解方法實(shí)質(zhì)上還是高斯消去法。二、解對(duì)稱正定的平方根法在工程計(jì)算中，常遇到方程組的系數(shù)矩陣是對(duì)稱正定矩陣，由于對(duì)稱正定的性質(zhì)，它的三角分解的形式有著特殊性，因此，其計(jì)算量以及在計(jì)算機(jī)中的存儲(chǔ)量可大大減少。二、解對(duì)稱正定的平方根法定理2：若n階方陣A對(duì)稱正定，則存在唯一的對(duì)角元素為正的下三角陣L，使A=LLT(Cholesky分解）證明略a11a12…a1na21a22…a2n……ar1ar2…arn……an1an2…ann由a11=l211，得l11=考慮第一行元素，a1j=l11lj1,j=2,3,…n，得lj1=a1j/l11這樣就計(jì)算出L的第一列，LT的第一行考慮第二列的下三角元素，由a22=l221+l222，得到由ai2=li1l21+li2l22,得到li2=（ai2-li1l21）/l22,i=3,…,n這樣就計(jì)算出L的第二列，LT的第二行一般的由上面的推導(dǎo)可求出按行計(jì)算公式:對(duì)i=1,2,…n將A分解后，即A=LLT，代入Ax=b，得

LLTx=b將其化為下列與原方程組等價(jià)的兩個(gè)方程組

Ly=bLTx=y然后回代，求出y與x。此時(shí)AX=bLLTX=b令LTX=Y

則AX=b等價(jià)于LY=b

LTX=Y=由

LY=b得l11y1=b1l21y1+l22y2=b2………………..li1y1+li2y2+…liiyi=bi…………………ln1y1+li2y2+…lnnyn

=bn解之得:yi=(bi-)/lii(i=1,...n)

l11x1+l21x2+….ln1xn=y1l22x2+….ln2xn=y2………………..

liixi+…lnixn=yi…………………lnnxn

=yn解之得：xi=(yi-)/lii(i=n,....,1)

再代入LTX=Y

例1：用平方根法求

4x1+2x2+4x3=42x1+10x2+5x3=114x1+5x2+21x3=-9

例1：用平方根法求

4x1+2x2+4x3=42x1+10x2+5x3=114x1+5x2+21x3=-9解:系數(shù)矩陣:424l11

l

11

l21

l312105=l21

l22

l

22

l324521l31

l32

l33

l

33

例2用LLT分解方法解線性方程組

取四位小數(shù)計(jì)算。解用公式(3―26)依次計(jì)算由式(3―27)求得

y1≈1.3416,y2≈-0.4474,y3≈1.7320再由式(3―27)求得原方程組的解為

x1≈0.9993,x2≈0.9989,x3≈0.9999實(shí)際上,原方程組的準(zhǔn)確解為

x1=1,x2=1,x3=1例3：已知方程組Ax=f,其中

2-1b0A=-12af=1b-120試問(wèn)參數(shù)a和b滿足什么條件時(shí)，可選用平方根法求解該方程組。三、解三對(duì)角陣的追趕法解三對(duì)角方程組的追趕法（Thomas算法）基本思想：

AX=F=若A為對(duì)角占優(yōu)即

|b1|>|c1||bi|≥|ai|+|ci|i=2,,..n-1ai.ci≠0|bn|>|an|則A可以寫(xiě)成：A=LU即

對(duì)比法求得pi與qi的遞推公式：p1=a1

a1=p1*1q1=c1/p1c1=p1*q1對(duì)于i=2,3,…n行計(jì)算pi=ai-bi*qi-1

ai=bi*qi-1+piqi=ci/piAX=F即LUX=F可寫(xiě)成由

LY=F知

=由矩陣乘法可求將（3.29)代入可得

i=2,...n求出yi后再由

UX=Y即

=

同樣根據(jù)矩陣乘法求

(3.32)i=n-1,..1

例（大綱

p13)取b=0,a=-1,用追趕法解方程組A=LUAX=fLUX=fLY=fUX=Y=第五節(jié)向量和矩陣的范數(shù)在數(shù)值分析中，經(jīng)常要分析解向量的誤差，比較誤差向量的“大小”，那么怎么定義向量的大小，并進(jìn)行比較呢？這可以對(duì)向量按一定的法則取一個(gè)非負(fù)實(shí)數(shù)，作為它的“長(zhǎng)度”，然后以其長(zhǎng)度為標(biāo)準(zhǔn)進(jìn)行比較，這就是數(shù)值方法中廣泛應(yīng)用的范數(shù)的概念。第五節(jié)向量和矩陣的范數(shù)一、向量的范數(shù)定義1:若向量x∈Rn

即x=(x1,x2.....xn)T,定義某個(gè)實(shí)數(shù)值函數(shù)N(X)=||X||，若滿足以下三個(gè)條件：

(1)||X||≥0當(dāng)且僅當(dāng)X=0時(shí)，||X||=0正定性

(2)||C.X||=|C|.||X||C為任意常數(shù)齊次性

(3)||X+Y||≤||X||+||Y||三角不等式則稱N(X)是R上的一個(gè)向量范數(shù)或模。例1:向量空間

x=(x1,x2,x3)T,

（1）|x1|+|2x2|+|x3|是不是一種向量范數(shù)？（2）|x1+3x2|+|x3|是不是一種向量范數(shù)？

2、常用的向量范數(shù)1-范數(shù)||X||1=2-范數(shù)||X||2=()1/2∞-范數(shù)||X||∞=max|xi|

1<=i<=np-范數(shù)||X||p=()1/p例2

已知向量

X=（1,-2,3)T求||X||1

，||X||2

，||X||∞要求:會(huì)計(jì)算向量的范數(shù)3、向量范數(shù)的性質(zhì)設(shè)x,y∈Rn則

|||x||-||y|||<=||x-y||

證：||x||=||(x-y)+y||<=||x-y||+||y||所以

||x||-||y||<=||x-y||同理||y||-||x||<=||y-x||=||x-y||也即：||x||-||y||>=-||x-y||所以：|||x||-||y|||<=||x-y||（2）設(shè)||x||α與||x||β是Rn上任意兩種向量范數(shù)，則存在正常數(shù)m和M使一切

x∈Rn

有m||x||β<=||x||α<=M||x||β如：||X||∞<=||X||1<=n||X||∞

說(shuō)明：向量范數(shù)的等價(jià)性，說(shuō)明x的一切范數(shù)都是等價(jià)的。一種范數(shù)對(duì)應(yīng)一種長(zhǎng)度，一種長(zhǎng)度對(duì)應(yīng)一種收斂性，等價(jià)性表明，當(dāng)||x||α趨于0時(shí)，||x||β也趨于0，只不過(guò)趨于0的速度不一樣，即收斂的速度不一樣。但收斂性是一樣的。定義3:設(shè)向量序列X(K)=(x1(K),x2(K).....xn

(K))T

和向量X*=(x1*,x2*...xn*)T

對(duì)任意i(i=1,2...n)有則稱向量序列{X(K)}收斂于X*

記做說(shuō)明：如果向量的每一個(gè)分量都收斂，則向量收斂于X*。定理3：對(duì)Rn上的任一種向量范數(shù)||.||，向量序列{x(k)}收斂于向量x*的充要條件是：||x(k)–x*||0（當(dāng)k->∞時(shí))x(k)–x*=（x1(k)-x1*,x2(k)-x2*,xn(k)-xn*）T

xi(k)->xi*xi(k)-xi*->0||x(k)–x*||∞

0由范數(shù)的等價(jià)性知，存在M，m>0使得m||x(k)–x*||∞

≤||x(k)–x*||≤M||x(k)–x*||∞說(shuō)明：看向量x(k)

是否收斂于向量x*，就要看||x(k)–x*||是否收斂于0。二、矩陣的范數(shù)1、定義4若矩陣A∈Rn×n

的某個(gè)非負(fù)實(shí)值函數(shù)N(A)=||A||滿足

(1)||A||≥0當(dāng)且僅當(dāng)A=0時(shí)，||A||=0正定性

(2)||C.A||=|C|.||A||C為任意常數(shù)齊次性

(3)||A+B||≤||A||+||B||三角不等式

(4)||AB||≤||A||||B||相容性則稱N(A)是Rn×n

上的一個(gè)矩陣范數(shù)或模。

在數(shù)值計(jì)算中,為了進(jìn)行某種估計(jì),常常要比較不同向量的范數(shù),向量有時(shí)以Ax的形式出現(xiàn),其中A為n×n階矩陣

A=(aij)n×n

這就需要尋求‖x‖和‖Ax‖之間的某種關(guān)系定義5設(shè)X∈Rn

，A∈Rn×n，且給出一種向量范數(shù)||X||，則稱為矩陣A的算子范數(shù)。說(shuō)明:||AX||γ≤||A||γ.||X||γ常用公式由向量范數(shù)誘導(dǎo)出的矩陣范數(shù)，即矩陣范數(shù)和向量范數(shù)的關(guān)系。A的行范數(shù)||A||∞=max1<=i<=n2、常用的矩陣范數(shù)A的列范數(shù)||A||1=max1<=j<=nA的2范數(shù)||A||2=

A的p范數(shù)||A||p=()1/2例3已知

A=-1302計(jì)算A的1，2，∞范數(shù)要求:會(huì)計(jì)算矩陣的范數(shù)定義6譜半徑設(shè)A∈Rn×n

的特征值為λi(i=1,2...n)稱ρ(A)=max|λi|為A的譜半徑

1≤i≤n

那么,譜半徑和范數(shù)之間是什么關(guān)系呢?定理4：特征值上界定理設(shè)

A∈Rn×n,則ρ(A)≤||A||，即A的譜半徑不超過(guò)A的任何一種范數(shù)。證明：設(shè)λ是A的任一特征值，x為相應(yīng)的特征向量，則

AX=λx|λ|||x||=||λx||=||AX||<=||A||||X||所以|λ|〈=||A||也即ρ(A)〈=||A||結(jié)論：任何一種特征值都小于范數(shù)，最大的特征值是譜半徑。

三、方程組的性態(tài)和條件數(shù)方程組的系數(shù)和右端項(xiàng)都或多或少的帶有誤差，這種誤差有時(shí)會(huì)使方程組的解面目全非，有時(shí)卻影響不大。這涉及到方程組解的敏感程度。首先來(lái)考察一個(gè)例子：(p49例11)Ax=b12x17精確解為12-1x2=-1312x17A(x+δx)=b+δb2-1.0009x2=-1.003此時(shí)方程組的解為：y10.99988

y2=3.00006

p49(例10)

2x1+6x2=82x1+6.00001x2=8.00001其解為：x1=1x2=12x1+6x2=82x1+5.9999x2=8.00002其解為：x1=10x2=-2說(shuō)明：有的方程對(duì)擾動(dòng)敏感，有的不敏感。定義6若矩陣A或常數(shù)項(xiàng)的微小變化，引起方程組AX=b解的巨大變化，則稱此方程組為“病態(tài)”方程組，矩陣A稱為“病態(tài)”矩陣，否則，稱此方程組為“良態(tài)”方程組，矩陣A稱為“良態(tài)”矩陣注意：矩陣“病態(tài)”的性質(zhì)是矩陣本身的特性，我們希望找出刻畫(huà)矩陣病態(tài)本身的量。討論

A,b有擾動(dòng)時(shí)（δA，δb),對(duì)解的相對(duì)誤差的影響，分三種情況討論：（1）b有擾動(dòng)δb時(shí)的情況（b->b+δb

）此時(shí)，解為

X+δX,則有A(X+δX)=b+δb

據(jù)AX=b得AδX=δbδX=A-1δb||δX||<=||A-1||||δb||①

由b=AX知||b||<=||A||||X||

則②

由①，②可得2）設(shè)b精確，A有擾動(dòng)

δA（A->A+δA

）

此時(shí)(A+δA)(X+δX)=b

由AX=b知

(A+δA)δX=-δAX

即

AδX=-δA(X+δX)||δX||=||A-1δA(X+δX)||<=||A-1||||δA||(||X||+||δX||)整理得(1-||A-1||||δA||)||δX||<=||A-1||||δA||||X||當(dāng)||A-1||||δA||<1時(shí)有：變形為：3)A,b都有擾動(dòng)

δA，δb,解為X+δX

由此我們可知：A或b有擾動(dòng)時(shí),解的相對(duì)誤差的上界隨||A-1||||A||的增大而增大，也即||A-1||||A||標(biāo)志著方程組解的敏感程度。并且完全是由系數(shù)矩陣A的特性所決定的。定義7設(shè)A為非奇異陣，稱Cond(A)=||A-1||||A||為矩陣A的條件數(shù)由此可知，方程組AX=b的病態(tài)程度可由系數(shù)矩陣A的條件數(shù)Cond(A)來(lái)刻畫(huà)，其值越大，方程組的病態(tài)就越嚴(yán)重。常用的條件數(shù)有：

(1)Cond(A)∞=||A-1||∞||A||∞(2)Cond(A)2=||A-1||2||A||2=當(dāng)A為對(duì)稱正定時(shí)Cond(A)2=|λ1|/|λn|,其中

λ1，λn為矩陣A的最大和最小特征值例:求矩陣A的條件數(shù)逆陣的求法A-1=A*/|A|A*為A的伴隨矩陣判斷以為系數(shù)矩陣的方程組是病態(tài)還是良態(tài)。1、常用的向量范數(shù)1-范數(shù)||X||1=2-范數(shù)||X||2=()1/2∞-范數(shù)||X||∞=max|xi|

1<=i<=n復(fù)習(xí)A的行范數(shù)||A||∞=max

1<=i<=n2、常用的矩陣范數(shù):A的列范數(shù)||A||1=max

1<=j<=n

A的2范數(shù)||A||2=

A的F范數(shù)||A||F=()1/23、譜半徑

設(shè)

A∈Rn×n

的特征值為λi(i=1,2...n)稱ρ(A)=max|λi|為A的譜半徑

1≤i≤n4、特征值上界定理設(shè)A∈Rn×n,則ρ(A)≤||A||

，即A的譜半徑不超過(guò)A的任何一種范數(shù)5、條件數(shù)設(shè)

A為非奇異陣，稱Cond(A)=||A-1||||A||為矩陣A的條件數(shù)---------方程組AX=b的病態(tài)程度可由系數(shù)矩陣A的條件數(shù)Cond(A)來(lái)刻畫(huà)，其值越大，方程組的病態(tài)就越嚴(yán)重常用的條件數(shù)有：

(1)Cond(A)∞=||A-1||∞||A||∞(2)Cond(A)2=||A-1||2||A||2

第六節(jié)解線性方程組的迭代法解：從三個(gè)方程中分別分離出x1,x2,x3,即：一、雅可比(Jacobi)迭代(簡(jiǎn)單迭代)法及其收斂條件回憶非線性方程求根的迭代法？下面用一個(gè)具體的例子說(shuō)明雅可比迭代的基本思想。例：用簡(jiǎn)單迭代法解方程組：這樣就構(gòu)成了

X=CX+d

的形式用任意一組近似值（x1(k),x2(k),x3(k)）代入上式右端，可得到一組新的近似值（迭代格式）：取初始值X(0)=（0，0，0）T可得：方程的精確解為：x1=1.1x2=1.2x3=1.3可見(jiàn)，當(dāng)?shù)螖?shù)增加時(shí)，迭代結(jié)果越來(lái)越逼近其精確解，這時(shí)我們認(rèn)為迭代格式是收斂的。x1

(k+1)=-x2(k)+5x3(k)-4.2x2

(k+1)=10x2

(k)-2x3

(k)-7.2x3(k+1)=0.5x1(k)+5x2(k)-8.3例如：方程組依次從第三、第一及第二個(gè)方程分離出x1,x2,x3？但是對(duì)于任意線性方程組，按各種方式建立的簡(jiǎn)單迭代格式是否一定收斂？回答是否定的。迭代格式必須滿足一定條件才能收斂！開(kāi)始迭代…….顯然不收斂!可見(jiàn)，對(duì)同一方程組，同樣的初始值，由于變量分離的方式不同，其結(jié)果也不同，一個(gè)收斂，一個(gè)發(fā)散。1、迭代公式

方程組AX=b即:a11x1

+a12x2+……..a1nxn=b1a21x1+a22x2+……..a2nxn=b2……………….

ai1x1+ai2x2+…aiixi

...ainxn

=bi……………….an1x1+an2x2+………annxn

=bn若aii≠0，則可從第i個(gè)方程分離出xi(i=1,2….n)若aii≠0，則從第i個(gè)方程分離出:其中cij=-aij/aii,di=bi/aii

(i=1,...,n,j=1,....,n,j≠i)

cii

=0

xi=(bi-)/aii=+di(i=1,...,n)

即:x1=c11x1

+c12x2+……..c1nxn+d1x2=c21x1+a22x2+……..c2nxn+d2……………….xi=

ci1x1+ci2x2+…ciixi

...cinxn

+di……………….xn

=cn1x1+cn2x2+………annxn

+dnxi(k+1)=+di(i=1,...,nk=0,1,2...)(3.40)-------Jacobi迭代公式(分量形式)也可寫(xiě)成X(K+1)=CX(K)+d-------Jacobi迭代公式(矩陣形式)

其中cij=-aij/aii

j≠i

cii=0選一初始近似值x(0)=(x1(0),x2(0),…,xn(0))T，用上式進(jìn)行迭代計(jì)算，可得到一個(gè)近似解序列

x1(k),x2(k),…,xn(k)(k=0,1,2,…)如果極限存在，則稱迭代格式收斂，其極限值(x1,x2,…,xn)T就是原方程組的解。按照上述格式進(jìn)行迭代求方程組的解的方法稱為簡(jiǎn)單迭代法，又稱為雅可比迭代法。2、迭代格式的收斂條件充分條件1在迭代格式中，若則雅可比迭代格式對(duì)任意初始值x(0)和d都是收斂的。證明：回憶定義3:設(shè)精確解為X*=(x1*,x2*...xn*)T

對(duì)任意i(i=1,2...n)有則稱向量序列{X(K)}收斂于X*，記作

根據(jù)定理4，要證明當(dāng)k->∞時(shí)，

由于x*滿足方程X*=CX*+dxi

*=ci1x1*

+ci2x2*

+…ciixi*...cinxn*+dixi

(k)=ci1x1(k-1)

+ci2x2(k-1)

+…ciixi

(k-1)...cinxn

(k-1)+dixi

(k)-xi

*=ci1(x1(k-1)-x1*)

+ci2(x2(k-1)

-x2)+...+cin(xn

(k-1)-xn*)

|xi

(k)-xi

*|<=|ci1||x1(k-1)-x1*|

+|ci2||x2(k-1)

-x2*|+...+|cin||xn

(k-1)-xn*|<=(|ci1|+|ci2|+…+|cin|).所以

因?yàn)?<μ<1,δ0為一常數(shù),當(dāng)k->∞時(shí)，證得δk->0。μΔk-1充分條件2在迭代格式中，若則雅可比迭代格式收斂。充分條件3在迭代格式中，若則雅可比迭代格式收斂。匯總充分條件1，2，3，只要迭代矩陣至少有一種范數(shù)<1，則雅可比迭代格式收斂。迭代收斂格式，什么時(shí)候終止？每次迭代后判斷|xi(k+1)-xik|=|Δxi(k)|<ε是否成立，如果成立，可停止迭代。由Jacobi迭代公式

xi(k+1)=+di(i=1,...,nk=0,1,2...)，在迭代的每一步計(jì)算過(guò)程中，是用x（k)的全部分量來(lái)求x(k+1)

的所有分量，

顯然，在計(jì)算第i個(gè)分量xi(k+1)時(shí)，已經(jīng)計(jì)算出的最新分量

x1(k+1),…..xi-1(k+1)沒(méi)有被利用，對(duì)這些最新計(jì)算出的分量加以利用，也即在Jacobi迭代中用:x1(k+1),…..xi-1(k+1）來(lái)代替x1(k),…..xi-1(k）所得公式即為Gauss-seidel迭代。二、Gauss-Seidel迭代法及其收斂條件1、迭代公式

Xi(k+1)=++di

(i=1,2....,n)(3-41)

其中

cij=-aij/aii(i=1,...,n,j=1,....,n,j≠i)

cii=0di=bi/aii

2、迭代格式的收斂條件充分條件1在迭代格式中，若則高斯-賽德?tīng)柕袷綄?duì)任意初始值x(0)和d都是收斂的。

充分條件2在迭代格式中，若則高斯-賽德?tīng)柕袷绞諗俊R總充分條件1，2，只要迭代矩陣至少有一種范數(shù)<1，則高斯-賽德?tīng)柕袷绞諗?。迭代收斂格式，什么時(shí)候終止？每次迭代后判斷|xi(k+1)-xik|=|Δxi(k)|<ε是否成立，如果成立，可停止迭代。三、嚴(yán)格對(duì)角占優(yōu)矩陣的雅可比和高斯-賽德?tīng)柕袷蕉x8

設(shè)A=(aij)是一個(gè)

nxn矩陣，若

|aii|>(i=1,2....,n)

則稱A為嚴(yán)格對(duì)角占優(yōu)矩陣。定理4:方程組Ax=b，其中A為n階嚴(yán)格對(duì)角占優(yōu)矩陣時(shí)，一定存在收斂的雅可比迭代和高斯-賽德?tīng)柕袷?。證明。

總結(jié)：

Jacobi迭代收斂條件充分條件(1):方程組AX=b的系數(shù)矩陣A為

嚴(yán)格對(duì)角占優(yōu)陣充分條件(2):迭代矩陣至少存在一種矩陣范數(shù)||.||,

使

||C||<1充要條件(3)：迭代矩陣的譜半徑ρ(C)<1總結(jié)：

高斯-賽德?tīng)柕諗織l件充分條件1:方程組

AX=b的系數(shù)矩陣A對(duì)稱正定充分條件2:方程組

AX=b的系數(shù)矩陣A嚴(yán)格對(duì)角占優(yōu)充分條件3：迭代矩陣C的范數(shù)||C||<1充要條件4：迭代矩陣C的譜半徑

ρ(C)<1例1:已知：

8x1-3x2+2x3=204x1+11x2-x3=336x1+3x2+12x3=36寫(xiě)出

jacobi迭代格式，判斷其收斂性解:由原方程可得jacobi迭代公式x1(k+1)=3/8x2(k)-2/8x3(k)+20/8x2

(k+1)=-4/11x1(k)+1/11x3

(k+33/11x3

(k+1)=-6/12x1(k)–3/12x2(k)+36/12因?yàn)橄禂?shù)矩陣對(duì)角占優(yōu),所以,該迭代公式收斂例2：設(shè)有方程組

X=CX+d,考察用迭代法

X(k+1)=CX(k)+d求解方程的收斂性其中

C=0.90d=10.30.82例3：將例1改寫(xiě)成Gauss-seidel迭代

x1(k+1)=3/8x2(k)-2/8x3(k)+20/8x2

(k+1)=-4/11x1(k+1)+1/11x3

(k)+