第3章 線形方程組直接求根法

第三章解線性方程組的直接法§1消元法1.1消元法的描述1.2高斯消元法1.3克勞特消元法1.4平方根法1.5追趕法1.6消元法的應用條件§2選主元的高斯消元法2.1列主元素法2.2全主元素法§1.1消元法的描述矩陣形式：線性方程組解唯一的條件：其解為：其中，Ai為方程組右端向量B代替A中第i列向量所得的矩陣?？巳R姆(Cramer)法則§1.1消元法的描述直接法：假設計算過程中不產生舍入誤差，經過有限次運算可求得方程組的精確解法。思路：將線性方程組變形成等價的三角方程組。例：先消去方程組中后兩個方程中的變量x1，得同解方程組：§1.1消元法的描述再消去上方程組第三個方程中的變量x2，得同解方程組：上三角方程組§1.1消元法的描述1.1

方法描述思路:先逐次消去變量，將方程組化解成同解的上三角方程組，此過程稱為消元過程；然后按方程相反順序求解上三角方程組，得到原方程的解，此過程稱為回代過程。設有線方程組:（1）§1.1消元法的描述(1)為消元方便，經常用l11除(3.1)1：其中:(3.2)(2)為把(3.1)2,(3.1)3中的x1項消去，引入如下參數(shù):§1.1消元法的描述(3)按以下方式消去式(3.1)2,(3.1)3中的x1項：0+(a22-l21u12)x2+(a23-l21u13)x3=b2-l21z1(3.1)2-l21×(3.2)

:(3.1)3-l31×

(3.2)0+(a32-l31u12)x2+(a33-l31u13)x3=b3-l31z1a32(1)x2+a33(1)x3=b3(1)

(3.4)簡記為a22(1)x2+a23(1)x3=b2(1)

(3.3)§1.1消元法的描述(4)用l22除(3.3)式得：aij(1)=aij(0)-li1u1j

,bi(1)=bi(0)-li1z1aij(0)=aij,bi(0)=bi其中其中(3.5)§1.1消元法的描述(5)為將(3.4)中的x2項消去，引入乘數(shù)a33(2)=a33(1)–l32u23=a33–l31u13–l32u23,

b3(2)=b3(1)-l32z2=b3–l31z1-l32z2(6)消去(3.4)式中的x2項：(3.4)-l32(3.5):0+(a33(1)–l32u23)x3=b3(1)

-l32z2簡記為:

a33(2)x3=b3(2)

(3.6)其中§1.1消元法的描述同樣對(3.6)式遍除l33得

u33x3=z3(3.7)

以上的計算過程稱為消元過程。其中§1.1消元法的描述消元過程結束就可得到下列線組：u11x1+u12x2+u13x3=z1

u22x2+u23x3=z2(3.8)

u33x3=z3簡記為UX=Z，其中§1.1消元法的描述其中(3.8)式右端的z由下列公式確定：簡記為LZ=B，其中§1.1消元法的描述按照線組(3.8)可以逐次求出x1、x2、x3，稱為回代過程。由UX=Z,LZ=B得LUX=B，與AX=B比較知:

A=LU(3.9)消元過程實質上就是將原線組AX=B分解為兩個三角形線組LZ=B和UX=Z的計算過程.§1.1消元法的描述系數(shù)lij、uij的計算公式:（擇定）

（擇定）

（擇定）§1.1消元法的描述系數(shù)lij、uij的計算公式規(guī)律:系數(shù)由上三角、下三角和z向量組成，上三角為u系數(shù)矩陣，下三角為l系數(shù)矩陣。u,z系數(shù)矩陣元素的分母為所在行對應的l對角線元素；l系數(shù)矩陣的分母為所在列對應的u對象線元素；uij,zi,lij系數(shù)矩陣的分子為原方程對應的系數(shù)aij與LU矩陣中i行j列的對應元素乘積之和的差；§1.1消元法的描述系數(shù)lij、uij的計算順序:u11u12u13z1li1l21u22u23z2l22l31l32u33z3l33123456§1.1消元法的描述這種計算規(guī)律可用一般公式表示為§1.1消元法的描述回代過程:在已知lij的基礎上,建立求解x1,x2,…,xn的三角形線組，按由上而下的方程次序解出x1,x2,…,xn?！?.1消元法的描述§1.1消元法的描述思路：取lii=1(i=1,2,…,n)相應的計算公式為：§1.2高斯(Gauss)消元法§1.2高斯消元法用高斯消元法解下列線性方程組例3.1：解:u系數(shù)的第一列值為原方程第一列的系數(shù)緊湊格式進一步求得:z1=0,z2=3

,z3=1.01921-23x1+11x2+x3=0

2.26086x2+1.52174x3=31.01924x3=1.01921x1=0.99999x2=1.99999x3=0.99997§1.2高斯消元法思路：取l11=a11(0)=a11,

l22=a22(1),l33=a33(2),…,lnn=ann(n-1)，即uii=1§1.3克勞特(Crout)消元法相應的計算公式為：用克勞特消元法解下列線性方程組例3.2：解:按克勞特消元法的計算公式,計算結果如下:§1.3克勞特消元法§1.3克勞特消元法l系數(shù)的第一列值為原方程第一列的系數(shù)；u系數(shù)對角線上的值為1x1+1.5x2+2x3=3x2-8x3=-8x3=2x1=3-1.5*8-2*2=13x2=-8+8*2=8x3=2§1.3克勞斯特消元法取lii=uii(i=1,2,…,n)

,則：§1.4平方根法(Cholesky)系數(shù)矩陣必須為對稱矩陣才可用此法線性方程組具有對稱性，即aij=aji

，則有§1.4平方根法由此推得uij=lji，即lij與uij相對于對角線是對稱分布的。這樣得到消元的計算公式為：§1.4平方根法P76頁公式改正?！?.4平方根法§1.4平方根法用平方根法解下列線性方程組例3.2：解:按平方根法的計算公式,計算結果如下:系數(shù)矩陣為對稱矩陣§1.4平方根法對角線上的l,u系數(shù)值為消元法對角線上分子的值開平方x1+0.42x2+0.54x3=0.30.90752x2–0.10270x3=0.412110.83537x3=0.59336x1=-0.24052x2=0.37372x3=0.71030§1.4平方根法追趕法就是應用克勞特消元法求解三對角線形的線性方程組的解§1.5追趕法b1x1+c1x2 =d1a2x1+b2x2+c2x3 =d2a3x2+b3x3+c3x4 =d3

an-1xn-2+bn-1xn-1+cn-1xn=dn-1anxn-1+bnxn=dn（1）lij,uij(克勞特消元法的公式)l11=b1

u12=c1/l1100……….0l21=a2l22=b2-a2u12u23=c2/l2200

l32=a3l33=b3-a3u23

u34=c3/l330

ln-1n-2=an-1

ln-1n-1=bn-1-an-1un-2n-1

un-1n=cn-1/ln-1n-10………0

lnn-1=anlnn=bn-anun-1n0§1.5追趕法（2）zi(i=1,2,…,n)§1.5追趕法或（3）xi(i=n,n-1,…,2,1)§1.5追趕法或§1.5追趕法用追趕法解下列線性方程組例3.2：解:按追趕法的計算公式,計算結果如下:§1.5追趕法x1-0.5x2=1x2-0.66667x3=0x3=3.00001x1=2.00001x2=2.00002x3=3.00001§1.5追趕法定理1:若A的各階主子式均不為0,即§1.6消元法的應用條件則lii0,uii0，消元法可用。因A=LU

0A1=|a11|=L1U1=|l11||u11|=|l11u11|

,所以,l110,

u110§1.6消元法的應用條件證明：§1.6消元法的應用條件命題得證

證明：因實對稱矩陣為正定的必要且充分條件是其所有的主子式都大于零，即|A1|>0,|A2|>0,…,|An|>0

顯然滿足定理1中|Ai|0的條件,因此定理2得證。§1.6消元法的應用條件定理2

若A為實對稱正定矩陣,則lii0,uii0(i=1,2,…,n)消元法可用。如果系數(shù)矩陣對稱正定且采用平方根法進行求解，則必有l(wèi)ii2>0(i=1,2,…,n)，這是因為

不必進行復數(shù)運算§1.6消元法的應用條件定理3

若A為強對角線優(yōu)勢矩陣，則 lii0,uii0(i=1,2,…,n)

在這種情況下，A的各階主子矩陣A1,A2…An均是強對角線優(yōu)勢矩陣.根據阿達馬定理知,|Ai|0,按定理1知lii0,uii0(i=1,2,…,n)，證畢?！?.6消元法的應用條件證明：所謂強對角線優(yōu)勢矩陣是指其對角線上元素的絕對值大于同行上其余元素絕對值之和的矩陣，用公式表示為:阿達馬定理

r階線組|Ar|0的一個充分條件為下述強對角線條件

假設|Ar|=0,則線組ArX=0有非零解1,2,…,設k=max(1,2,…,r)，代入第k個方程，有如下等式與等式成立:§1.6消元法的應用條件證明：反證法（假設結論不成立）成立

此結論與條件矛盾，故假設|Ar|=0不對，定理得證?！?.6消元法的應用條件§2主元素法1.消元法有缺點對于幾個公式lij=分子/ujj,uij=分子/lii,zi=分子/lii,xi=分子/uii,如果分母小會把分子的誤差放大公式likukj，這些累計量在運算量大時累積的誤差也會很大。分母為零的時候無法計算提出主元素法是為控制舍入誤差§2.1列主元素法列主元素法就是在待消元方程的所在列中選取主元素,經方程的行交換,置主元素于對角線位置后進行消元的方法.思路:主元素:絕對值最大的元素。列主元素法交換原則：在第k列中將主元素所在的方程與第k個方程進行交換，使主元素位于第k個對角線元素位置上。

10x1-19x2-2x3=3(1)-20x1+40x2+x3=4(2)x1+4x2+5x3=5(3)第一列選擇-20作為該列的主元素§2.1列主元素法用列主元素法解下列線性方程組例3.2：解:1§2.1列主元素法-20x1+40x2+x3=3(4)

10x1-19x2-2x3=4(5)x1+4x2+5x3=5(6)計算l21,l31(消去(5)(6)中的x1)經過方程的行交換,將-20置于a11的位置l21=-10/20=-0.5，l31=-1/20=-0.05(5)-l21×(4),(6)-l31×(4)后得:1x2–1.5x3=5(7)6x2+5.05x3=5.2(8)選6為主元素,同上方程換行,消去x26x2+5.05x3=5.2(9)x2–1.5x3=5(10)§2.1列主元素法x1被消去了-2.34168x3=4.13332(11)(換行)(消去x2)保留有主元素的方程:-2.34168x3=4.13332(11)-20x1+40x2+x3=4(4)6x2+5.05x3=5.2(9)回代x3=-1.76511x2=2.35230x1=4.41634§2.1列主元素法如果不是按列選主元素，而是在全體待選系數(shù)中選取，則得全主元素法。

10x1-19x2-2x3=3(1)-20x1+40x2+x3=4(2)x1+4x2+5x3=5(3)

選擇所有系數(shù)中絕對值最大的40作為主元素，交換第一、二行和交換第一、二列使該主元素位于對角線的第一個位置上，得§2.2全主元素法用全主元素法解下列線性方程組例3.3：解:計算l21=-19/40=0.475，l31=4/40=0.1(5)-l21(4),(6)-l31(4)得0.5x1–1.525x3=4.9(7)3x1+4.9x3=4.6(8)選4.9為主元素,重復前面兩個步驟§2.2全主元素法40x2-20x1+

x3=4(4)-19x2+10x1-2x3=3(5)

4x2+x1+5x3=5(6)§2.2全主元素法

4.9x3+3x1=4.6

(9)1.525x3+0.5x1=4.9(10)1.43366x1=6.33161