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

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

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

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

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

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

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

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

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

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

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

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

1）消元過(guò)程

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

(3―11)2）回代過(guò)程

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

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

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

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

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

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

(n-1)(n-2)次乘法運(yùn)算。消元次數(shù)k=1時(shí)，需n-1次除法運(yùn)算,需n(n-1)次乘法運(yùn)算消元次數(shù)k=2時(shí)，需n-2次除法運(yùn)算,需(n-1)(n-2)次乘法運(yùn)算…消元次數(shù)k=n-1時(shí)，需n-k=1次除法運(yùn)算,需(n-(k-1))(n-k)=2*1次乘法運(yùn)算除法運(yùn)算總次數(shù)(n-1)+…+1=n(n-1)/2乘法運(yùn)算總次數(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回代過(guò)程的計(jì)算除法運(yùn)算次數(shù)為n次.乘法運(yù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消去法的運(yùn)算次數(shù)與n3同階，記為O(n3)克萊姆法則需運(yùn)算次數(shù)為(n2-1)*n!+n二、主元素消去法用高斯消去法求解下列方程組(用四位有效數(shù)字計(jì)算):①②②-①×1/10-5,得

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

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

化簡(jiǎn)得

x2=0.6000

回代求得

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

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

解：第一列消元時(shí)，②中-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列主元素消去法的計(jì)算過(guò)程:

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

aij-aik·akj/akk?aij

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

2.全主元素消去法

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

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

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

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

x1=1.000,x2=3.000,x3=2.000

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

x1=1.000,x2=2.000,x3=3.000全主元素消去法的計(jì)算過(guò)程:

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

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

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

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

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

其中｜a1｜＞｜c(diǎn)1｜＞0

｜ak｜≥｜bk｜+｜c(diǎn)k｜,bkck≠0,k=2,3,…,n-1

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

令

其中

當(dāng)k=n時(shí),因?yàn)?/p>

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矩陣的三角分解

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

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

LUx=b

令Ux=y

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

4.2矩陣三角分解的唯一性設(shè)非奇異矩陣A存在一種三角分解LU,一般這種分解未必唯一,這是因?yàn)槿我庖粋€(gè)同階的非奇異對(duì)角矩陣D總有

(LD)(D-1U)=L1U1

它也是矩陣A的一種