2177數(shù)值分析課件

1、 第二章第二章 線性方程組的直接解法線性方程組的直接解法 2.1 2.1 引引 言言 在自然科學和工程技術中在自然科學和工程技術中, ,很多問題歸結(jié)為解線性方程很多問題歸結(jié)為解線性方程組組. .有的問題的數(shù)學模型中雖不直接表現(xiàn)為含線性方程組有的問題的數(shù)學模型中雖不直接表現(xiàn)為含線性方程組, ,但它的數(shù)值解法中將問題但它的數(shù)值解法中將問題“離散化離散化”或或“線性化線性化”為線性為線性方程組方程組. .因此線性方程組的求解是數(shù)值分析課程中最基本的因此線性方程組的求解是數(shù)值分析課程中最基本的內(nèi)容之一內(nèi)容之一. . 線性方程組線性方程組: :結(jié)束nnnnnnnnnnbxaxaxabxaxaxabxax

2、axa22112222212111212111常記為矩陣形式常記為矩陣形式 Ax=b (2.2) 1 此時此時A是一個是一個nn方陣方陣, ,x和和b是是n維列向量維列向量. . 根據(jù)線性代數(shù)知識若根據(jù)線性代數(shù)知識若 |A| 0,(2.2) 0,(2.2)的解存在且唯一的解存在且唯一. . 關于線性方程組的解法一般分為兩大類關于線性方程組的解法一般分為兩大類, ,一類是一類是直接法直接法, ,即經(jīng)過有限次的算術運算即經(jīng)過有限次的算術運算, ,可以求得可以求得(2.1)(2.1)的精確解的精確解( (假定計假定計算過程沒有舍入誤差算過程沒有舍入誤差).).如線性代數(shù)課程中提到的克萊姆算如線性代數(shù)

3、課程中提到的克萊姆算法就是一種直接法法就是一種直接法. .但該法對高階方程組計算量太大但該法對高階方程組計算量太大, ,不是不是一種實用的算法一種實用的算法. .實用的直接法中具有代表性的算法是實用的直接法中具有代表性的算法是高斯消元法高斯消元法, ,其它算法都是它的變形和應用其它算法都是它的變形和應用. . 另一類是另一類是迭代法迭代法, ,它將它將(2.1)(2.1)變形為某種迭代公式變形為某種迭代公式, ,給出初給出初始解始解x0 0, ,用迭代公式得到近似解的序列用迭代公式得到近似解的序列xk k, ,k=0,1,2, =0,1,2, , ,在一定的條件下在一定的條件下xk kx* *

4、( (精確解精確解).).迭代法顯然有一個收斂條迭代法顯然有一個收斂條件和收斂速度問題件和收斂速度問題. . 這兩種解法都有廣泛的應用這兩種解法都有廣泛的應用,我們將分別討論我們將分別討論,本章介紹直本章介紹直接法接法.結(jié)束結(jié)束 2 2.2 2.2 高斯高斯(Gauss)(Gauss)消元法消元法 高斯消元法是一種古老的方法高斯消元法是一種古老的方法. .我們在中學學過消元法我們在中學學過消元法, ,高斯消元法就是它的標準化的、適合在計算機上自動計算高斯消元法就是它的標準化的、適合在計算機上自動計算的一種方法的一種方法. .2.2.1 2.2.1 高斯消元法的基本思想高斯消元法的基本思想例例1

5、 1 解方程組解方程組 (2.3)(2.3) (2.4) (2.4) (2.5) (2.5)3946572132321321321xxxxxxxxx第一步第一步, ,將將(2.3)(2.3)乘乘-2-2加到加到(2.4)(2.4)；(2.3)(2.3)乘乘-1-1加到加到(2.5),(2.5), 得到得到 (2.3)(2.3) (2.6) (2.6) (2.7) (2.7)462431323232321xxxxxxx 3結(jié)束結(jié)束第二步第二步, ,將將(2.6)(2.6)乘乘-2/3-2/3加到加到(2.7),(2.7),得到得到 (2.3)(2.3) (2.6) (2.6) (2.8) (2.

6、8)32032043132332321xxxxxx回代回代: :解解(2.8)(2.8)得得x3 3, ,將將x3 3代入代入(2.6)(2.6)得得x2 2, ,將將x2 2, , x3 3代入代入(2.3)(2.3)得得x1 1, ,得到解得到解 x* *=(2,1,-1)=(2,1,-1)T T 容易看出第一步和第二步相當于增廣矩陣容易看出第一步和第二步相當于增廣矩陣:b在作在作行變換行變換, ,用用ri表示增廣陣表示增廣陣A:b的第的第i行行: :441620130321361941572321:3132122rrrrrrbA結(jié)束結(jié)束 4320413200013032132332rrr

7、 由此看出上述過程是逐次消去未知數(shù)的系數(shù)由此看出上述過程是逐次消去未知數(shù)的系數(shù), ,將將Ax=b化化為等價的三角形方程組為等價的三角形方程組, ,然后回代解之然后回代解之, ,這就是高斯消元法這就是高斯消元法. .2.2.2 2.2.2 高斯消元法公式高斯消元法公式 記記Ax=b為為A(1)x=b(1),A(1)和和b(1)的元素記為的元素記為 和和 ,i,j=1,2,n.第一次消元第一次消元,目的是消掉第二個方程到第目的是消掉第二個方程到第n個方程個方程中的中的x1項項,得到得到A(2)x=b(2),這個過程須假定這個過程須假定 0.) 1 (ija) 1 (ib) 1 (11a結(jié)束結(jié)束 5

8、)2()2()2()2(2)1(1)2()2(2)1(1)2(2)2(22)1(12)1(11),3,2()1()1(2)1(1)1()1(2)1(1)1(2)1(1)1(22)1(21)1(12)1(11)1()1(:00:11bAbbbaaaaaaabbbaaaaaaaaabAnnnnnnrrlrninnnnnnniii 在在A(1):b(1)中中, ,紅方框中的元素是要化為紅方框中的元素是要化為0 0的部分；的部分；A(2):b(2)中中, ,紅方框中的元素全部已發(fā)生變化紅方框中的元素全部已發(fā)生變化, ,故上標由故上標由(1)(1)改改(2),(2),計算公式為計算公式為: :結(jié)束結(jié)束

9、6)1(11)1()2()2(1)1(11)1()2()1(11)1(110blbbaalaaaaliiiijiijijii (i=2,3,n) (i,j=2,3,n) (i=2,3,n) (i=2,3,n)第第k次消元次消元(1(1kn-1)-1) 設第設第k-1次消元已完成次消元已完成,且且 0,此時增廣矩陣如下此時增廣矩陣如下:)(kkka)()()2(2)1(1)()()2(2)1(1)()()2(2)2(22)1(1)1(12)1(11)()(:knkkknnkknnnknkkkkkkkkbbbbaaaaaaaaaaabA結(jié)束結(jié)束 7 本次消元的目的是對框內(nèi)部分作類似第一次消元的處理

10、本次消元的目的是對框內(nèi)部分作類似第一次消元的處理,消掉第消掉第k+1個方程到第個方程到第n個方程中的個方程中的xk項項,即把即把 到到 化化為零為零.計算公式如下計算公式如下:)(, 1kkka)(knka)()()1()1()()()1()()(0kkikkikikikkkjikkijkijkkkkikikblbbaalaaaal (i=k+1,n) (i,j=k+1,n) (i=k+1,n) (i=k+1,n) 只要只要 0,(k=1,2,n-1)消元過程就可以進行下去消元過程就可以進行下去.當當k=n-1時時,消元過程完成消元過程完成,得得:)()2(2) 1 (1)()2(2) 1 (

11、1)2(22) 1 (12) 1 (11)()(:nnnnnnnnnbbbaaaaaabA)(kkka結(jié)束結(jié)束 8 它的方陣部分它的方陣部分A(n)是一個上三角形矩陣是一個上三角形矩陣,它對應的方程組是它對應的方程組是一個上三角形方程組一個上三角形方程組,只要只要 0,就可以回代求解就可以回代求解,公式為公式為)(nnna)(1)()()()(iiinijjiijiiinnnnnnaxabxabx (i=n-1,n-2,1)綜合以上討論綜合以上討論, ,高斯消元法解線性方程的公式為高斯消元法解線性方程的公式為: : 1 1消元消元 令令 ( (i,j=1,2,=1,2, ,n) )iiijij

12、bbaa) 1 () 1 (,結(jié)束結(jié)束 9)()()1()()()1()1()()(0kkikkikikkjikkijkijkikkkkkikikblbbalaaaaal( (i=k+1,k+2,n) ) ( (i,j=k+1,k+2,n) ) ( (i=k+1,k+2,n) (2.9) (2.9)2 2回代回代, ,若若 0 0)(nnna)(1)()()()(iiinijjiijiiinnnnnnaxabxabx (i=n-1,n-2,1) (2.10)(2.10)結(jié)束結(jié)束 對對k=1=1到到n-1,-1,若若 0 ,0 ,進行進行: : ( (i=k+1,k+2,n) )(kkka 10

13、2.2.3 高斯消元法的條件高斯消元法的條件 以上過程中以上過程中,消元過程要求消元過程要求 0 (i=1,2,n-1),回代過程則回代過程則進一步要求進一步要求 0,但就方程組但就方程組Ax=b講講, 是否等于是否等于0是無法是無法事先看出的事先看出的.)(nnna)(iiia)(iiia注意注意A的順序主子式的順序主子式Di (i=1,2,n)在消元過程中不變在消元過程中不變.這是因這是因為消元所作的變換是為消元所作的變換是“將某行的若干倍加到另一行將某行的若干倍加到另一行”上上,據(jù)線性代數(shù)知識據(jù)線性代數(shù)知識,此類變換不改變行列式的值此類變換不改變行列式的值.若高斯消元若高斯消元過程已進行

14、了過程已進行了k-1步步(此時當然應有此時當然應有 0,ik-1),這時計算這時計算A(k)的順序主子式的順序主子式:)(iiia(1 )11 1(1 )( 2 )21 12 2(1 )( 2 )(1 )11 12 21 ,1(1 )( 2 )()1 12 2kkkkkkk kDaDaaDaaaDaaa結(jié)束結(jié)束 11)(1) 1 (111iiiiiaDDaD 有遞推公式有遞推公式( (i=2,3,k) )顯然顯然, , 可知可知,消元過程能進行到底的充要條件消元過程能進行到底的充要條件是是Di0 ,(i=1,2,n-1),若要回代過程也能完成若要回代過程也能完成,還應加上還應加上Dn=A0,綜

15、合上述有綜合上述有:00)(iiiiaD定理定理2.1 高斯消元法消元過程能進行到底的充要條件是系數(shù)高斯消元法消元過程能進行到底的充要條件是系數(shù)陣陣A的的1到到n-1階順序主子式不為零；階順序主子式不為零；Ax=b能用高斯消元法解能用高斯消元法解的充要條件是的充要條件是A的各階順序主子式不為零的各階順序主子式不為零.2.2.4 高斯消元法的計算量估計高斯消元法的計算量估計 消元過程的工作量消元過程的工作量,參看公式參看公式(2.9),k是消元次數(shù)是消元次數(shù),k=1,2,n-1,第第k步消元時步消元時,計算計算lik(i=k+1,n)需要需要n-k次除法次除法；計算；計算 (i,j=k+1, ,

16、n)需要需要(n-k)2次乘法及次乘法及(n-k)2次加減法；計算次加減法；計算 需要需要n-k次乘法及次乘法及n-k次減法次減法,合計合計:) 1( kija) 1( kib結(jié)束結(jié)束 12 乘除法次數(shù)乘除法次數(shù) 加減法的次數(shù)加減法的次數(shù)111122) 1(6) 12)(1()()(nknknnnnnknkn111122) 1(6) 12)(1()()(nknknnnnnknkn 回代過程的工作量回代過程的工作量,參見公式參見公式(2.10),求求xk需需n-k次加減法次加減法, n-k次乘法和次乘法和1次除法次除法,合計為合計為 乘除法次數(shù)乘除法次數(shù)12) 1() 1(nknnkn 加減法次

17、數(shù)加減法次數(shù)12) 1()(nknnkn 總的運算次數(shù)為總的運算次數(shù)為 乘除法乘除法 (當當n較大時較大時)333323nnnn結(jié)束結(jié)束 13 加減法加減法 (當當n較大時較大時)36) 12)(1(3nnnn 一般講乘除法的運算比加減法占用機時多得多一般講乘除法的運算比加減法占用機時多得多, ,往往只往往只統(tǒng)計乘除法次數(shù)而稱高斯消元法的運算量為統(tǒng)計乘除法次數(shù)而稱高斯消元法的運算量為 次次. .33n 2.3 選主元的高斯消元法選主元的高斯消元法 在上節(jié)的算法中在上節(jié)的算法中,消元時可能出現(xiàn)消元時可能出現(xiàn) =0的情況的情況,高斯消元高斯消元法將無法繼續(xù)；即使法將無法繼續(xù)；即使 0,但但 0 (

18、i=1,2, ,n). 38)32.2(/112/1112kkjkjkikijijjkjkjjjjlllallalyxLbLyT結(jié)束 39結(jié)束 40).(,/,/3321121111nnilxlyxnilylbyiinikkkiiiiiikkikii結(jié)束 41 nnnnnnnnnffffxxxxbacbacbacbA12112111122211結(jié)束 42)35.2(, 3 ,2,/1, 3 ,2,/111111nicniabbbciiiiiii)36.2(, 3 ,2,/)(/1111niyafybfyiiiii).(,3721211nnixyxyxiiiinn結(jié)束 432.8 向量和矩陣的范

19、數(shù)向量和矩陣的范數(shù)在分析方程組的解的誤差及下章中迭代法的收斂時在分析方程組的解的誤差及下章中迭代法的收斂時,常產(chǎn)生一個問題常產(chǎn)生一個問題,即如何即如何判斷向量判斷向量x的的“大小大小”,對矩陣也有類似的問題對矩陣也有類似的問題.本節(jié)介紹本節(jié)介紹n維向量和維向量和nn矩陣矩陣的范數(shù)的范數(shù).結(jié)束結(jié)束|max|,|, |1211221ininiiniixxxxxx1 442.8.1 向量范數(shù)向量范數(shù)定義定義2.1 x和和y是是Rn中的任意向量中的任意向量,向量范數(shù)向量范數(shù)是定義在是定義在Rn上的實值函數(shù)上的實值函數(shù),它滿足它滿足:容易看出容易看出,實數(shù)的絕對值實數(shù)的絕對值,復數(shù)的模復數(shù)的模,三維向量

20、的模都滿足以上三條三維向量的模都滿足以上三條,n維向量的維向量的范數(shù)概念是它們的自然推廣范數(shù)概念是它們的自然推廣.常使用的向量范數(shù)有三種常使用的向量范數(shù)有三種,設設x=(x1,x2,xn)T (1) x 0,并且并且,當且僅當當且僅當x=0時時, x =0;(2) k x =|k| x ,k是一個實數(shù)是一個實數(shù);(3) x + y x + y 容易驗證容易驗證, ,它們都滿足三個條件它們都滿足三個條件. .例例6 6 x=(1,0.5,0,-0.3)=(1,0.5,0,-0.3)T, T, 求求解解: :結(jié)束結(jié)束115761305018130050122221x.x.x2.8.2 2.8.2

21、矩陣范數(shù)矩陣范數(shù)從向量范數(shù)出發(fā)從向量范數(shù)出發(fā), ,可以定義矩陣的范數(shù)可以定義矩陣的范數(shù). .定義定義2.22.2 設設A是是nn矩陣矩陣, ,定義定義|max|max|1|0AxxAxAnnRxxRxx為矩陣為矩陣A的范數(shù)的范數(shù). .這樣定義的范數(shù)有如下性質(zhì)這樣定義的范數(shù)有如下性質(zhì): :45xxx,21(1) (1) A0,0,并且并且, ,當且僅當當且僅當A A是零矩陣時是零矩陣時, , A = =0 0(2) (2) kA= |= |k| | A(3)(3)兩個同階方陣兩個同階方陣A,B, ,有有A+BA+B(4)(4)A是是nn矩陣矩陣, ,x是是n維向量維向量, ,有有AxAx(5)(

22、5)A,B都是都是nn矩陣矩陣, ,有有ABAB矩陣范數(shù)最常用的有以下三種矩陣范數(shù)最常用的有以下三種: :它們分別與向量的三種范數(shù)對應它們分別與向量的三種范數(shù)對應,即用一種向量范數(shù)可定義相應的矩陣范數(shù)即用一種向量范數(shù)可定義相應的矩陣范數(shù).定理定理2.5 Rn空間上的范數(shù)等價空間上的范數(shù)等價.即對任意給定的兩種范數(shù)即對任意給定的兩種范數(shù) 有下列關系有下列關系: m M 其中的其中的m,M是正的常數(shù)是正的常數(shù), 表示向量或矩陣的表示向量或矩陣的范數(shù)范數(shù).結(jié)束結(jié)束njijniniijnjaAAaA1112111|max|max|（1 1 是是ATA的最大特征值）的最大特征值）46從以上定理看出從以上

23、定理看出,當向量或矩陣的任一種范數(shù)趨于零時當向量或矩陣的任一種范數(shù)趨于零時,其它各種范數(shù)也趨于其它各種范數(shù)也趨于零零.因此討論向量和矩陣序列的收斂性時因此討論向量和矩陣序列的收斂性時,可不指明使用的何種范數(shù)；證明時可不指明使用的何種范數(shù)；證明時,也只要就某一種范數(shù)證明就行了也只要就某一種范數(shù)證明就行了.有了向量和矩陣范數(shù)的概念有了向量和矩陣范數(shù)的概念,就可以定義向量和矩陣序列的收斂就可以定義向量和矩陣序列的收斂.定義定義2.3 如果如果 稱向量序列稱向量序列x (k)收斂于向量收斂于向量x.。結(jié)束結(jié)束0|lim)(xxkk定義定義2.4 如果如果 稱方陣序列稱方陣序列A (k)收斂于方陣收斂于

24、方陣A.。0|lim)(AAkk定理定理2.6 向量序列向量序列x (k)收斂于向量收斂于向量x的充要條件是的充要條件是:njxxjkjk, 2 , 1,lim)(定理定理2.7 方陣序列方陣序列A (k)收斂于方陣收斂于方陣A的充要條件是的充要條件是:njiaaijkijk, 2 , 1,lim)(2.8.3 譜半徑譜半徑定義定義2.5 設設n階方陣階方陣A的特征值為的特征值為j (j=1,2,n),則稱為則稱為A的譜半徑的譜半徑.|max)(1jnjA|)(AA 47定理定理2.8 方陣譜半徑和方陣范數(shù)有如下關系方陣譜半徑和方陣范數(shù)有如下關系:證證: : 設設i是是A的任一特征值的任一特征

25、值, ,xi為對應的特征向量為對應的特征向量 Axi= ixi兩邊取范數(shù)兩邊取范數(shù), ,用矩陣性質(zhì)用矩陣性質(zhì)(4)(4)有有 | |i| |x iAx i 因為因為 x i 0,0,所以所以x i00所以所以 | |i | |A i=1,2,=1,2, ,n, , 所以所以 ( (A)=max|)=max|i | |A.定理定理2.9 設設A是是nn階矩陣階矩陣,A的各次冪組成的矩陣序列的各次冪組成的矩陣序列 I,A,A2, ,Ak, 收斂于零收斂于零,即即 的充要條件是的充要條件是(A)1.證明從略證明從略.結(jié)束結(jié)束例例7求求A1 1, , A2 2 , , A , , ( (A).0lim

26、kkA4142. 3246|246222A，所以之模最大顯然210121012A解解:顯然顯然A1 1 =4, =4,A=4=4 .2464,0)412)(4(541464145|,5414641453212，TT，AAIAA解之得48結(jié)束結(jié)束這里這里,我們指出我們指出,對于實對稱矩陣對于實對稱矩陣A,有有2.8.4 條件數(shù)及病態(tài)方程組條件數(shù)及病態(tài)方程組線性方程組線性方程組 Ax=b 的解是由系數(shù)陣的解是由系數(shù)陣A及右端向量及右端向量b決定的決定的.由實際問題中得到由實際問題中得到的方程組中的方程組中,A的元素和的元素和b的分量的分量,總不可避免地帶有誤差總不可避免地帶有誤差,因此也必然對解向

27、因此也必然對解向量量x產(chǎn)生影響產(chǎn)生影響.222, 0) 24)(2(210121012|3212，AI解之得4142. 322|)(2233A，所以之模最大顯然2|)(AA 1.設設Ax=b中僅中僅b向量有誤差向量有誤差b ,對應的解對應的解x發(fā)生誤差發(fā)生誤差x ,即即:bbxAAxbbxxA)(49這就提出一個問題這就提出一個問題:當當A有誤差有誤差A,b有誤差有誤差b時時,解向量解向量x有多大誤差有多大誤差?即當即當A和和b有微小變化時有微小變化時,x的變化有多大的變化有多大? 若若A和和b的微小變化的微小變化,也只導致也只導致x的微小變的微小變化化,則稱此問題是則稱此問題是“良態(tài)良態(tài)”的

28、；反之的；反之,若若A和和b的微小變化會導致的微小變化會導致x的很大變化的很大變化,則稱此問題為則稱此問題為“病態(tài)病態(tài)”問題問題.在以下的討論中在以下的討論中,設設A非奇異非奇異,b0,所以所以|x|0. 注意到注意到Ax=b, ,所以所以Ax=b, ,若若A非奇異非奇異, ,有有 x= =A-1-1b. .結(jié)束結(jié)束2.A有誤差有誤差A ,b無誤差無誤差,此時有類似的結(jié)論。此時有類似的結(jié)論。|1bbAAxx|Abx 定義定義2.6 若若nn方陣方陣A非奇異非奇異,則稱則稱AA-1-1為為A的條件數(shù)的條件數(shù),記為記為 Cond(A)=AA-1-1由于選用的范數(shù)不同由于選用的范數(shù)不同,條件數(shù)也不同

29、條件數(shù)也不同,在有必要時在有必要時,可記為可記為Condp(A)=ApA-1-1p (p=1,2, ).503.由以上分析不難看出由以上分析不難看出,當當b和和A一定時一定時,AA-1-1的大小的大小,決定了決定了x 的相對的相對誤差限誤差限. AA-1-1越大時越大時,x 可能產(chǎn)生的相對誤差越大可能產(chǎn)生的相對誤差越大,即問題的即問題的“病態(tài)病態(tài)”程程度越嚴重度越嚴重.同時同時,我們看出我們看出,Ax=b 的的“病態(tài)病態(tài)”程度程度,只與只與A的元素有關的元素有關,而與而與b的的分量是無關的分量是無關的.為此為此,我們有我們有:所以所以 xA-1-1 b . . 又因為又因為b=AxAx,所以所

30、以 兩式相除兩式相除, ,有有即即x的相對誤差小于等于的相對誤差小于等于b的相對誤差的的相對誤差的AA-1-1倍倍. . 由于由于1=I=AA-1AA-1=cond(A),可知可知cond(A)總是大于等于總是大于等于1的數(shù)的數(shù).條件條件數(shù)反映了方程組的數(shù)反映了方程組的“病態(tài)程度病態(tài)程度”.條件數(shù)越小條件數(shù)越小,方程組的狀態(tài)越好方程組的狀態(tài)越好,條件數(shù)很大條件數(shù)很大時時,稱方程組為病態(tài)方程組稱方程組為病態(tài)方程組.但多大的條件數(shù)才算病態(tài)則要視具體問題而定但多大的條件數(shù)才算病態(tài)則要視具體問題而定,病病態(tài)的說法只是相對而言態(tài)的說法只是相對而言. 結(jié)束結(jié)束51條件數(shù)的計算是困難的條件數(shù)的計算是困難的,這首先在于要算這首先在于要算A-1,而求而求A-1比解比解Ax=b的工作量還大的工作量還大,當當A確實病態(tài)時確實病態(tài)時,A-1也求不準確；其次要求范數(shù)也求不準確；其次要求范數(shù),特別是求特別是求A2, A-12又十分