解線性方程組的直接法

主講教師：高小輝E-mail:fzlcstar@126.com第四章線性方程組AX=B的數(shù)值解法(TheSolutionofLinearSystemsAX=B)1求解4.1引言許多實(shí)際問(wèn)題可歸結(jié)為線性（代數(shù)）方程組機(jī)械設(shè)備、土建結(jié)構(gòu)的受力分析；經(jīng)濟(jì)計(jì)劃輸電網(wǎng)絡(luò)、管道系統(tǒng)的參數(shù)計(jì)算；企業(yè)管理大型的方程組需要有效的數(shù)值解法。數(shù)值解法的穩(wěn)定性和收斂性問(wèn)題需要注意。2小行星軌道計(jì)算問(wèn)題3天文學(xué)家要確定一小行星的軌道,在軌道平面建立以太陽(yáng)為原點(diǎn)的直角坐標(biāo)系.在坐標(biāo)軸上取天文單位(地球到太陽(yáng)的平均距離),對(duì)小行星作5次觀察,測(cè)得坐標(biāo)數(shù)據(jù)

(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5)將數(shù)據(jù)代入橢圓的一般方程:a1x2+a2xy+a3y2+a4x+a5y+1=0得a1xk2+a2xkyk+a3yk2+a4xk+a5yk+1=0(k=1,2,3,4,5)4即求解方程組可確定橢圓方程(小行星軌道方程)5對(duì)一般線性方程組:AX=b,其中當(dāng)系數(shù)矩陣A的行列式|A|≠0時(shí),則方程組有唯一解.6求解線性方程組:AX=b的一般過(guò)程:輸入：A，b解方程組算法輸出：

X直接法：經(jīng)過(guò)有限步算術(shù)運(yùn)算求得精確解迭代法：從初始解出發(fā)，逐步求出近似解來(lái)逼近在求解小型(未知數(shù)較少)方程組時(shí),直接法很有效.在求解大型方程組時(shí),迭代法是最有效的方法.74.2高斯消去法(GaussianElimination

)1.上三角線性方程組(Upper-triangularLinearSystem)

定義4.1NN矩陣A=[aij]中的元素滿足對(duì)所有i>j,有aij=0,則稱NN矩陣A=[aij]為上三角矩陣。如果A中的元素滿足對(duì)所有i<j,有aij=0,則稱NN矩陣A=[aij]為下三角矩陣。4.2.1順序高斯消去法89AX=B上三角線性方程組表示為：a11x1+a12x2+a13x3+…+a1n-1xn-1+a1nxn=b1a22x2+a23x3+…+a2n-1xn-1+a2nxn=b2a33x3+…+a3n-1xn-1+a3nxn=b3………….an-1n-1xn-1+an-1nxn=bn-1

annxn

=bn2.回代(BackSubstitution)設(shè)AX=B是上三角線性方程組，如果：akk0,k=1,2..n,則方程組存在唯一解。10證明：a11x1+a12x2+a13x3+…+a1n-1xn-1+a1nxn=b1a22x2+a23x3+…+a2n-1xn-1+a2nxn=b2a33x3+…+a3n-1xn-1+a3nxn=b3………….an-1n-1xn-1+an-1nxn=bn-1

annxn

=bn唯一用歸納法可證明xn-1,xn-2….x1是唯一的11例4.2：證明下列線性方程組無(wú)解

4x1–x2+2x3+3x4=207x3-4x4=-76x3+5x4=43x4=6例4.1：利用回代法求解線性方程組

4x1–x2+2x3+3x4=20–2x2+7x3-4x4=-76x3+5x4=43x4=6

x4=6/3=2x3=(4-5x4)/6=-1x2=(-7-7x3+4x4)/-2=-4x1=(20+x2-2x3-3x4)/4=3x4=2x3=-1x3=1/7a22=00x2

+12例4.3：證明下列線性方程組有無(wú)窮解

4x1–x2+2x3+3x4=20

0x2+7x3-0x4

=-76x3+5x4=43x4=6x4=2x3=-1x3=-1x2=4x1-16無(wú)窮解a22=013復(fù)習(xí)如A是NN矩陣a11a12a13…a1na21a22a23…a2n

……an1an2an3…annA=則A的行列式為：劃掉A的第i行和第j列后的行列式第i行展開(kāi)第j列展開(kāi)1438-45-17-69A=j=2,det(A)=-3+5+6=77-4-179287928-4-1i=1,det(A)=2-3+8

=2(45-6)-3(-36+7)+8(24-35)=775-1-69-4-179-457-6153.

如果NN矩陣A=[aij]是上三角矩陣或下三角矩陣，則：

定理：A是NN方陣，線性方程組AX=B有唯一解當(dāng)且僅當(dāng)det(A)016高斯消元法：思路首先將A化為上三角陣，再回代求解。=174初等變換(ElementaryTransformation)下列三種變換可使一個(gè)線性方程組變換成另一個(gè)等價(jià)的線性方程組交換變換：對(duì)調(diào)方程組的兩行比例變換：用非零常數(shù)乘方程組的某一行替換變換：將方程組的某一行乘一個(gè)常數(shù)再加到另一行

18例4.4：求拋物線y=A+Bx+Cx2,它經(jīng)過(guò)三點(diǎn)(1,1),(2,-1),(3,1)。

(2)-(1)A+B+C=1(1)B+3C=-2(2)2B+8C=0(3)(3)-2(2)A+B+C=1(1)B+3C=-2(2)2C=4(3)C=2,B=-8,A=7拋物線方程y=7-8x+2x2A+B+C=1(1)A+2B+4C=-1(2)A+3B+9C=1(3)(3)-(1)(3-1)(3-2)19上述求解方程組的方法就是高斯(Gauss)消元法。從式(4-1)到(4-2)的過(guò)程稱為消元過(guò)程而由(4-2)求出C、B、A的過(guò)程稱為回代過(guò)程。因此用高斯消去法求解性方程組要經(jīng)過(guò)消元和回代兩個(gè)過(guò)程。20可將線性方程組AX=B的系數(shù)存在N(N+1)增廣矩陣中a11a12a13…a1nb0a21a22a23…a2nb1

……an1an2an3…ann

bn[A|B]=215初等行變換(ElementaryRowOperation)對(duì)增廣矩陣進(jìn)行如下變換可得到一個(gè)等價(jià)的線性方程組交換行變換：對(duì)調(diào)矩陣兩行比例行變換：用非零常數(shù)乘矩陣某一行所有的元素替換行變換：將矩陣的某一行的所有元素乘一個(gè)常數(shù)再加到另一行對(duì)應(yīng)的元素上去。

224.2.2主元素（Pivot）高斯消去法

系數(shù)矩陣A中的元素arr用來(lái)消去akr(k=r+1,r+2,…,N),arr為第r個(gè)主元，第r行為主元行。例4.6

用增廣矩陣表示下列線性方程組，并求等價(jià)上三角線性方程組和方程組的解。x1+2x2+x3+4x4=132x1+0x2+4x3+3x4=284x1+2x2+2x3+x4=20-3x1+x2+3x3+2x4=6

23x1+2x2+x3+4x4=132x1+0x2+4x3+3x4=284x1+2x2+2x3+x4=20-3x1+x2+3x3+2x4=6

1214

132043

28

422120-3132

60761445-主元行＊2-主元行＊4-主元行＊-31214

130–42-5

2

0–6–2–15-3224-主元行＊-1.75-主元行＊1.507614451214

130–42-5

2

0–6–2–15-32009.55.2548.51214

130–42-5

2

00–5–7.5-350000–9-181214

130–42-5

2

00–5–7.5-35-主元行＊1.9回代：x4=2,x3=4,x2=-1,x1=3消元過(guò)程25有回代的高斯消去法(GaussianEliminationwithBackSubstitution)如果A是NN非奇異矩陣（存在A-1），則存在線性方程組UX=Y與線性方程組AX=B等價(jià)，這里U是上三角矩陣，并且akk0。當(dāng)構(gòu)造出U和Y后，可用回代法求解UX=Y，并得到方程組的解X。26消元記27Step1：設(shè)，計(jì)算因子將增廣矩陣第i行mi1

第1行，得到其中28一般地，假定已完成了(k-1)步消元，即已將[A(1)|B(1)]轉(zhuǎn)化為以下形式：29Stepk：設(shè)，計(jì)算因子共進(jìn)行？步n

1且計(jì)算30回代31消元法步驟(以4階為例)：增廣矩陣

32計(jì)算3個(gè)消元因子(乘子向量)(1)設(shè)a11≠0,[m21

m31

m41]T=[a21

a31

a41]T/a11

用-m21乘矩陣第一行后加到矩陣第二行;用-m31乘矩陣第一行后加到矩陣第三行;用-m41乘矩陣第一行后加到矩陣第四行;消元33用-m31乘矩陣第一行后加到矩陣第三行;消元34用-m41乘矩陣第一行后加到矩陣第四行;消元35第二輪消元后(2)設(shè)a22(1)≠0,計(jì)算第二個(gè)消元因子[m32

m42]T=[a32(1)

a42(1)]T

/a22(1)

用-m32乘矩陣第二行后加到矩陣第三行;用-m42乘矩陣第二行后加到矩陣第四行;36第三輪消元后用-m43乘矩陣第三行后加到矩陣第四行;(3)設(shè)a33(2)≠0,計(jì)算第三個(gè)消元因子:m43=a43(2)/a33(2)對(duì)應(yīng)三角形方程組37消元過(guò)程中,消元因子可排列為一矩陣用回代算法即可得出方程組的解.38由初等變換的知識(shí)可得.L×U=A在消元過(guò)程中,我們得到兩個(gè)矩陣此即為矩陣A的LU分解.39高斯消元法的主要缺陷1.計(jì)算消元因子mik=aik/akk當(dāng)分母akk為零時(shí),計(jì)算無(wú)法進(jìn)行;2.分母akk的絕對(duì)值非常小時(shí),也將會(huì)對(duì)計(jì)算結(jié)果誤差產(chǎn)生很大影響解決辦法40選主元以避免app(p)=0

如果app(p)=0,尋找第p行下滿足akp(p)

0的第一行，設(shè)為第k行，然后交換行k和行p，使新app(p)

0。如果app(p)≠0則不交換。此方法稱為平凡選主元方法。41將列主元所在行與第k行交換后,再按上面的高斯消元法進(jìn)行下去,此法即稱為列主元消元法。選|aik(k)|(i=k,…,n)最大的一個(gè)(列主元)選主元以減少誤差在每一步消元過(guò)程中取系數(shù)子矩陣的第一列元素中絕對(duì)值最大者作主元。42例4.7:

值x1=x2=1.000是如下方程組的解：

1.133x1+5.281x2=6.41424.14x1-1.210x2=22.93

用4位有效數(shù)字及選主元的高斯法求方程的解。行2-行1＊24.14/1.133:1.133x1+5.281x2=6.414-113.7x2=-113.8

x2=1.001,x1=0.995643例4.8：24.14x1-1.210x2=22.931.133x1+5.281x2=6.414

行2-行1＊1.133/24.14:24.14x1-1.210x2=22.935.338x2=5.338x2=1.000,x1=1.00044例用列主元法解第一列中絕對(duì)值最大是10，取10為主元45第二列的后兩個(gè)數(shù)中選出主元2.546X3=6.2/6.2=1X2=(2.5-5X3)/2.5=-1X1=(7+7x2-0x3)/10=0X1=0X2=-1X3=1N階方程組第k輪消元時(shí)，選第k列的后(n-k+1)個(gè)元素中絕對(duì)值最大者作主元。474.3矩陣三角分解法（TrianguarFactorization）定義

如果非奇異矩陣A可表示為下三角矩陣L和上三角矩陣U的乘積A=LU，則A存在一個(gè)三角分解。4.3.1高斯消去法和矩陣三角分解法a11x1+a12x2+a13x3+…+a1n-1xn-1+a1nxn=b1a21x1+a22x2+a23x3+…+a2n-1xn-1+a2nxn=b2a31x1+a32x2+a33x3+…+a3n-1xn-1+a3nxn=b3……an1x1+an2x2+an3x3+…+ann-1xn-1+annxn

=bn48a11a12a13…a1na21a22a23…a2na31a32a33…a3n……an1an2an3…ann=100…0

m2110…0

m31m321…0

……mn1mn2mn3…1u11u12u13…u1n0u22u23…u2n00

u33…u3n……00

0

…unn49a11a12a13…a1na21a22a23…a2na31a32a33…a3n……an1an2an3…annx1x2x3xn=b1b2b3bn100…0

m2110…0

m31m321…0

……mn1mn2mn3…1u11u12u13…u1n0u22u23…u2n00

u33…u3n……00

0

…unnx1x2x3xn=b1b2b3bny1y2y3yn50100…0

m2110…0

m31m321…0

……mn1mn2mn3…1y1y2y3yn=b1b2b3bnu11u12u13…u1n0u22u23…u2n00

u33…u3n……00

0

…unnx1x2x3xn=y1y2y3yn

UX=YLY=bYX51由初等變換的知識(shí)可得.L×U=A在高斯消元過(guò)程中,我們得到兩個(gè)矩陣此即為矩陣A的LU分解.52例4.3.2

求解：x1+2x2+4x3+x4=212x1+8x2+6x3+4x4=523x1+10x2+8x3+8x4=794x1+12x2+10x3+6x4=821241

2864

310884121061000

2100

311041211241

04-22

00-23000-6A===LU531000

2100

311041211241

04-22

00-23000-6x1x2x3x4=215279821000

2100

31104121y1y2y3y4=21527982y1=21y2=10y3=6y4=-2454x4=4x3=3x2=2x1=11241

04-22

00-23000-6x1x2x3x4=21106-24554.3.2直接三角分解法例4..3.1使用高斯消去構(gòu)造下列矩陣的三角分解：43-1

-2-45126A=

00-0.5100.250143-1

0-2.54.501.256.2500010001=43-1

-2-45126行2-行1*(-2/4)行3-行1*(1/4)

00-0.5100.25–0.5143-1

0-2.54.5008.5行3-行2*(1.25/-2.5)43-1-0.5-5–0.58.556定理設(shè)無(wú)行交換變換的高斯消去法可求解一般線性方程組AX=B，則矩陣A可分解為一個(gè)下三角矩陣L和一個(gè)上三角矩陣U的乘積：A=LU，而且L對(duì)角線元素為1，U的對(duì)角線元素非零。得到L和U后，可通過(guò)如下步驟得到X：

1、利用前向替換法對(duì)方程組LY=B求解Y2、利用回代法對(duì)方程組UX=Y求解X574.4置換矩陣

可能一個(gè)非奇異矩陣不能直接分解為A=LU例4.4.1證明下列矩陣不能直接分解為A=LU：126

48-1-235A=

58126

48-1-235A=

=100

m2110m31m321u11

u12

u13

0u22

u2300u33

1=u114=m21u11=m21-2=m31u11=m31

2=u128=m21u12+u22=4*2+03=m31u12+

m32u22

=(-2)*2+m32*0

=-459定義一個(gè)NN置換矩陣P是一個(gè)在每一行和每一列只有一個(gè)元素為1，而其它元素為0的矩陣。P的列是單位矩陣行的置換，可表示為：P=[E’k1E’k2……

E’kn

]’Pij=j=ki0其它情況如：0100

100000010010

P==[E’2E’1E’4

E’3]’60定理設(shè)P=[E’k1E’k2……

E’kn

]’是一個(gè)置換矩陣。PA是一個(gè)新的矩陣，它的行是將A中的行按行k1A,行k2A，…行knA調(diào)整順序后形成的。例4.4.2設(shè)A為44矩陣，P為上式中的置換矩陣，則PA矩陣中的行是將A中的行調(diào)整順序后形成的，順序?yàn)榈?，2，3，4行對(duì)應(yīng)于A中的第2，1，4，3行。

610100

100000010010

a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a44=a21a22a23a24a11a12a13a14a41a42a43a44a31a32a33a3462定理如果A是非奇異矩陣，則存在一個(gè)置換矩陣P，使得PA存在三角分解：PA=LU例4.4.3設(shè)A為非奇異矩陣126

48-1-235A=126

48-1-235PA=100

001010=126

-23548-1126

071700-25可分解U634.5擴(kuò)展高斯消去過(guò)程定理（非直接分解：PA=LU）設(shè)A是一NN矩陣。假設(shè)高斯消去法可求解經(jīng)過(guò)行變換的一般線性方程組AX=B。則存在一個(gè)置換矩陣P，使得PA可分解為一個(gè)下三角矩陣L和一個(gè)上三角矩陣U：PA=LU。而且L的主對(duì)角線元素為1，U的主對(duì)角線元素非零?？捎萌缦?步求出X：1、構(gòu)造矩陣L，U，P2、計(jì)算列向量PB3、用前向替換法對(duì)方程組LY=PB求解Y4、用回代法對(duì)方程組UX=Y求解X如何求P64a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a440010

010010000001P=a31a32a33a34a21a22a23a24a11a12a13a14a41a42a43a44通過(guò)選列主元0010

000110000100P=PAX=PBAX=B65x1+2x2+4x3+x4=212x1+8x2+6x3+4x4=523x1+10x2+8x3+8x4

=794x1+12x2+10x3+6x4=821241

2864

31088412106A=1、構(gòu)造矩陣L，U，P4121062864

3108812410001

010000101000P=4121061/2211

3/410.53.51/4–11.5–0.5664121061/2211

3/410.