計算方法 線性方程組的數(shù)值解法

第3章線性代數(shù)計算方法§1高斯消去法§2高斯―約當(dāng)消去法§3解實三對角線性方程組的追趕法§4矩陣的三角分解§5行列式和逆矩陣的計算§6迭代法

§7迭代法的收斂性AX=b若A非奇異，即|A|≠0，則X=A-1b克萊姆法則：則Xi=Ai/|A|計算量：一個n階行列式，需要(n-1)*n!次乘法要計算n+1個n階行列式，需(n+1)(n-1)*n!X含有n個分量，要做n次除法，共需運算次數(shù)(n+1)(n-1)*n!+n=(n2-1)*n!+n每項共n個因子共包含n！項解線性方程組的兩類方法:直接法:

經(jīng)過有限次運算后可求得方程組精確解的方法(不計舍入誤差!)迭代法：從解的某個近似值出發(fā)，通過構(gòu)造一個無窮序列去逼近精確解的方法(一般有限步內(nèi)得不到精確解)§1高斯消去法高斯消去法是一個古老的直接法，由它改進的方法是目前計算機上常用的求低階稠密矩陣方程組的有效方法。思路首先將方程組Ax=b

化為上三角方程組，此過程稱為消去過程，再求解上三角方程組，此過程稱為回代過程.§1高斯消去法一、順序消去法1、三角形方程組的解法

且aii≠0,i=1,2,…,n(3―4)由方程組(3―4)的最后一個方程直接可得將其代入倒數(shù)第二個方程可求得如此再解出xn-2,…,x2,x1，一般有(3―5)2、一般線性方程組的解法現(xiàn)舉例如下:解方程組①②③(3―6)

作②-①消去②中的x1,作③-①×4消去③中的x1,則方程組(3―6)化為①②③(3―6′)對方程組(3―6′)作③-②×,得到三角形方程組①②③(3―6")從方程組(3―6“)的方程③解出x3,將所得的結(jié)果代入方程②求出x2,再把x3、x2同時代入方程①解出x1。這樣可求出方程組的解為

上述求解方程組的方法就是高斯(Gauss)消去法。從式(3―6)到(3―6“)的過程稱為消元過程而由(3―6”)求出x3、x2、x1的過程稱為回代過程。

因此用高斯消去法求解線性方程組要經(jīng)過消元和回代兩個過程。2、一般的線性方程組將增廣矩陣的第i行+li1

第1行，得到：消去過程：第一步：設(shè)，計算因子其中第k步：設(shè)，計算因子且計算共進行n

1步，得到定理：若A的所有順序主子式均不為0，則高斯消去法能順序進行消元，得到唯一解?；卮^程：

3、順序高斯消去法的計算步驟：在計算機上實現(xiàn)時,我們常把方程組右端的常數(shù)項排于系數(shù)矩陣的第n+1列，

1）消元過程

對于k=1,2,…,n-1列,若按順序有某一ark≠0,r≥k,則交換k與r行,然后計算

(3―11)2）回代過程

對于k=n,n-1,…,2,1,計算(3―12)4、計算量：消元次數(shù)k=1時，計算li1(i=2,3，…，n)需n-1次除法運算.

使aij(1)變?yōu)閍ij(2)

以及使bi(1)變?yōu)閎i(2)需要

n(n-1)次乘法運算和n(n-1)次加(減)法運算.消元次數(shù)k=2時，計算li2(i=3，…，n)需n-2次除法運算.

使aij(2)變?yōu)閍ij(3)

以及使bi(2)變?yōu)閎i(3)需要

(n-1)(n-2)次乘法運算。消元次數(shù)k=1時，需n-1次除法運算,需n(n-1)次乘法運算消元次數(shù)k=2時，需n-2次除法運算,需(n-1)(n-2)次乘法運算…消元次數(shù)k=n-1時，需n-k=1次除法運算,需(n-(k-1))(n-k)=2*1次乘法運算除法運算總次數(shù)(n-1)+…+1=n(n-1)/2乘法運算總次數(shù)n(n-1)+(n-1)(n-2)+…+3.2+2.1=n(n-1)(n+1)/3總次數(shù)N1=n(n-1)/2+n(n-1)(n+1)/3回代過程的計算除法運算次數(shù)為n次.乘法運算總次數(shù)為1+…+(n-1)=n(n-1)/2回代總次數(shù)N2=n+n(n-1)/2=n(n+1)/2

N=N1+N2=n(n-1)/2+n(n-1)(n+1)/3=n3/3+n2-n/3Gauss消去法的運算次數(shù)與n3同階，記為O(n3)克萊姆法則需運算次數(shù)為(n2-1)*n!+n二、主元素消去法用高斯消去法求解下列方程組(用四位有效數(shù)字計算):①②②-①×1/10-5,得

(1.000-1.000×1/10-5)x2=1.000-0.6000×1/10-5化簡可得

x2=0.6000回代求得

x1=105(0.6-0.6000)=0而方程組的解應(yīng)為

x1=0.4000x2=0.6000

10-5做除數(shù)的原因①②

x1+x2=1①10-5x1+x2=0.6

②②-①×10-5/1，得

(1000-1000×10-5)x2=0.6-1.000×10-5

化簡得

x2=0.6000

回代求得

x1=(1-0.6000)=0.40001.列主元素消去法所謂列主元素消去法就是在每一步消元過程中取系數(shù)子矩陣的第一列元素中絕對值最大者作主元。對線性方程組(3―1)進行n-1次消元后,可得到上三角形方程組必須指出的是方程組(3―13)中的系數(shù)aij(i≤j)和右端的bi已經(jīng)改變了,并非與原來相同。這樣就可對方程組(3―13)回代求解。

(3―13)取四位有效數(shù)字計算。

解：第一列消元時，②中-18為主元,交換②和①得

①②③①②③例1用列主元素消去法解方程組②+①×12/18,③+①×1/18得

①②③第二列消元時,主元為1.167,交換方程②和③得

①②③③+②×1/1.167得①②③回代求得

x1=1.000,x2=2.000,x3=3.001方程組的實際解

x1=1,x2=2,x3=3列主元素消去法的計算過程:

(1)消元過程。對于k=1,2,…,n-1進行下述運算:①選主元,確定r,使得若ark=0,說明系數(shù)矩陣為奇異,則停止計算；否則進行下一步。②交換A的r、k兩行③對i=k+1,k+2,…,n,j=k+1,k+2,…,n+1計算(3―14)

aij-aik·akj/akk?aij

(2)回代過程。對于k=n,n-1,…,1計算(3―16)圖3.1圖3.1

2.全主元素消去法

所謂全主元素消去法,就是每步消元時選取系數(shù)子矩陣中絕對值最大的元素作主元。經(jīng)過n-1次消元后,方程組(3―1)可化為上三角形方程組(3―17)注意：這里方程組(3―17)中的系數(shù)aij(i≤j)及bi一般改變了。特別是未知數(shù)的排列順序,由于全主元素的消元過程中,其系數(shù)矩陣可能進行了列對調(diào),那么未知數(shù)也相應(yīng)地作了對調(diào)。例如,若矩陣第i列與第j列對調(diào),則未知數(shù)xi與xj也相應(yīng)地對調(diào)了,xi的結(jié)果實質(zhì)上為xj的結(jié)果。

例2用全主元素消去法求解方程組

①②③解：這里主元為-18,交換方程①與方程②得①②③再全選主元,主元為2.333,交換x2和x3所在的兩列,同時改變兩未知數(shù)的排列號得

①②③③-②×0.944/2.333得①②③已經(jīng)化為三角方程組,回代求解

x1=1.000,x2=3.000,x3=2.000

這里未知數(shù)x2與x3已對調(diào),所以應(yīng)恢復(fù)解的順序,方程組的實際精確解為

x1=1.000,x2=2.000,x3=3.000全主元素消去法的計算過程:

(1)消元過程。對k=1,2,…,n-1進行下列運算:①選主元,確定r,t使得若art=0,則系數(shù)矩陣為奇異的,停止計算否則進行下一步。②交換A中的r、t兩行及t、k兩列,并記下交換的足碼t、k。③對i=k+1,k+2,…,n,j=k+1,k+2,…,n+1計算

(2)回代過程。對k=n,n-1,…,1，計算(3―18)

(3―19)(3―20)圖3.2

圖3.2§2高斯―約當(dāng)消去法前面所述的消去法均要進行兩個過程,即消元過程和回代過程。但對消元過程稍加改變可以把方程組(3―1)化為對角形

(3―21)此時求解就不要回代了。這種無回代過程的主元素消去法稱為高斯―約當(dāng)(Jordan)消去法。特別是方程組(3―21)還可化為(3―22)§3解實三對角線性方程組的追趕法

其中｜a1｜＞｜c1｜＞0

｜ak｜≥｜bk｜+｜ck｜,bkck≠0,k=2,3,…,n-1

｜an｜＞｜bn｜＞0我們將利用所謂“追趕法”解決令

令

其中

當(dāng)k=n時,因為

bnx

n-1+anxn=rn又

xn-1=un-1-vn-1

xn于是追趕追趕例3解線性方程組解依公式(3―27)、(3―31)求得v3=0(一般v3不必算)再由式(3―32)、(3―30)求得方程組的解圖3.3圖3.3

§4矩陣的三角分解

對于線性方程組，若其系數(shù)矩陣A能夠分解成兩個三角形矩陣相乘,譬如,A=LU

L為下三角矩陣,U為上三角矩陣,則求解方程組(3―1)就化為求解

LUx=b

令Ux=y

則Ly=b計算F1A？計算F2(F1A)？福羅貝留斯矩陣這樣就把A化為一個上三角矩陣U，即在需要進行行交換時，還得左乘某些排列矩陣Pij則A=LU矩陣A的LU分解或三角分解。

4.2矩陣三角分解的唯一性設(shè)非奇異矩陣A存在一種三角分解LU,一般這種分解未必唯一,這是因為任意一個同階的非奇異對角矩陣D總有

(LD)(D-1U)=L1U1

它也是矩陣A的一種