四川大學(xué)數(shù)值分析期末總復(fù)習(xí)

1、四川大學(xué)水利水電學(xué)院數(shù)值分析程復(fù)習(xí)課四川大學(xué)水利水電學(xué)院Gauss消元法解線性代數(shù)方程組的直接法列主元素消去法全主元素消去法矩陣三角分解法范數(shù)、條件數(shù)平方根法LU分解法追趕法列主元素三角分解法四川大學(xué)水利水電學(xué)院第四章 解線性代數(shù)方程組的直接法（適用于中等規(guī)模的n階線性方程組）范數(shù)、條件數(shù)Gauss消去法LU分解法平方根法四川大學(xué)水利水電學(xué)院了解幾個：順序主子式Di：方陣前i行、前i列元素矩陣的行列式；非奇異矩陣：對方陣A而言， 即可證明A非奇異，涉及特征值時，全部 特征值均不等于0可證明A非奇異.對稱正定矩陣：A的全部特征值大于0；順序主子式全大于0； 行列式為正；嚴(yán)格對角占優(yōu)矩陣：詳見書P

2、173.0A TAA四川大學(xué)水利水電學(xué)院Gauss消去法11 11221121 1222221 122nnnnnnnnnna xa xa xba xa xa xba xa xa xb線性代數(shù)方程組：用矩陣及向量形式表示：AX = b（PS:A為非奇異矩陣，即 ）1112111212222212nnnnnnnnaaaxbaaaxbAXbxbaaa0A 四川大學(xué)水利水電學(xué)院消元過程：消元過程：實質(zhì)上是用)1(11)1(21/aa去乘以第一個方程，得到一個新的方程，然后用第二個方程減去這個新的方程，使其第一項為0，最終變成：)2(2)2(23)1(232)2(22bxaxaxann同樣取)1(11)

3、1(31aa乘以第一個方程，得到一個新的方程，然后用第三個方程減去這個新的方程，使其第一項為0，最終變成： 上標(biāo)(2)實際上表示經(jīng)過消去法一步，以此類推(3)表示經(jīng)過消去法兩步。)2(3)2(33)1(332)2(32bxaxaxann四川大學(xué)水利水電學(xué)院(1)(1)(1)(1)11112211(2)(2)(2)22222(2)(2)(2)32233(2)(2)(2)22nnnnnnnnnnnaxaxaxbaxaxbaxaxbaxaxb重復(fù)此步驟n-1次最終得到等價方程組：經(jīng)過消元法n-1步后，可以得到一個等價的上三角形方程組：（PS：經(jīng)過初等變換得到的矩陣與原矩陣等價）(1)(1)(1)(1

4、)(1)11112213311(2)(2)(2)(2)22223322(3)(3)(3)33333 nnnnnna xa xa xa xba xa xa xba xa xb( )( ) nnnnnna xb( )( )nnAxb即：已為00四川大學(xué)水利水電學(xué)院經(jīng)過回代可得到方程組的解：1( )( ).nnnnnnxbxa此時必須滿足條件：( )0nnnan階線性方程組消元過程所需要的總運算量為：nnn313123消元乘法運算量：消元除法運算量：221()(1)3nknkkn11(1)2nknkn回代乘除法運算量：) 1(2nn四川大學(xué)水利水電學(xué)院( )( )(1)( )( )(1)( )( )

5、1,1,1,kikikkkkkkkijijikkjkkkiiikkaliknaaalai jknbblbikn（4.1.1）( )( )( )( )( )11,1nnnnnnnkkkkkkjjkkj kxbaxbaxakn （4.1.2）四川大學(xué)水利水電學(xué)院消元法能夠運用的為：( )01,2,.,iiiaik：( )01,2,.,iiiaik矩陣A的順序主子式01,2,., ;.iDik kn推論：若矩陣A的順序主子式 則有： 01,2,., ;.iDik kn(1)( )1111,2,3,.,.kkkkkDaD aknD四川大學(xué)水利水電學(xué)院若某個主元 很小，會引起很大的誤差。 ()kkka因

6、此可以采用或。 實質(zhì)上是在消元法進行了k（k=0,1,2,.,n-1）步之后，選取系數(shù)矩陣A第k+1行到第n行中絕對值最大的元作為主元，并利用初等行變換和列變換交換其位置，使其置于對角線上，成為對角元，以減小誤差。 實質(zhì)上是在消元法進行了k（k=0,1,2,.,n-1）步之后，選取系數(shù)矩陣A第k+1列中絕對值最大的元作為主元，并利用初等行變換使主元其置于對角線上，成為對角元，以減小誤差。四川大學(xué)水利水電學(xué)院典型題目1、概念題、消元及回代公式； 2、用全主元素消去法或列主元素消去法解方程組； 3、相關(guān)定理、定義或變形證明題(詳見書本證明過程).：分別用全主元素消去法和列主元素消去法解方程組，并由

7、此計算系數(shù)行列式的值.第一步：消元法進行了0步后，選出前三行的主元素4，經(jīng)交換得：23123123 3 +4=1 - +2223.xxxxxxxx ，：323213214x +3x =1 - + 2223xxxxxx 3221214x+ 3x =177 + 4415 -222xxxx 經(jīng)Gauss消元得四川大學(xué)水利水電學(xué)院2131=-37612xxx 第二步：消元法進行了1步后，選出前兩行的主元素2，經(jīng)交換得：3212124+ 3 =115 2 - 2277 -44xxxxxx 經(jīng)Gauss消元得321224+ 3 = 115 2 - 2231 -22xxxxx 回代求解得：四川大學(xué)水利水電學(xué)

8、院第一步：選出第一列的主元素2，經(jīng)交換得：23123123 3 +4=1 - +2223.xxxxxxxx ，12312323223 - +2 3 +4=1.xxxxxxxx ，經(jīng)Gauss消元得12322322331 - 22 3 +4=1xxxxxx 四川大學(xué)水利水電學(xué)院第二步：選出第二列的主元素3，經(jīng)交換得：123232223 3 +4=131 - 22xxxxxx 經(jīng)Gauss消元得123233223 3 +4=1 21xxxxxx 321121=-376xxx 回代求解得：結(jié)果相同！結(jié)果相同！四川大學(xué)水利水電學(xué)院：矩陣A的元素 ，經(jīng)過Gauss消去法1步后，A變?yōu)?10a 11120

9、TarA證明若A 對稱，A2也對稱.證明：11121211.nijnnnaaaaAaaaGuass消元法第一步11121.0.0.nijnnaaaaa(2,)i jn四川大學(xué)水利水電學(xué)院1111;ijijijaaaaa1111.jijijiaaaaa即 故A2也是對稱矩陣.已知A為對稱矩陣, 故 1111=,=,=.ijjiiijjaaaaaa1111ijjiijijaaaaaa因此：211.ijnnAa 其中：221111.TijjinnnnAaaA 得證.四川大學(xué)水利水電學(xué)院矩陣三角分解法：對對矩陣進行一次初等變換，相當(dāng)于用相應(yīng)的初等矩陣去左矩陣進行一次初等變換，相當(dāng)于用相應(yīng)的初等矩陣去左

10、乘原來的矩陣。從這個觀點來考察乘原來的矩陣。從這個觀點來考察Gauss消去法，用矩陣乘法表消去法，用矩陣乘法表示，即可得到求解線性方程組的另一種直接法：矩陣的三角分解。示，即可得到求解線性方程組的另一種直接法：矩陣的三角分解。矩陣分解：矩陣分解：ALU四川大學(xué)水利水電學(xué)院1112111121212222212(1)(1)(1)(1)(1)(1)(1)(1)(1)(22131(1)(1)(1)1.1.101.00.1.nnnnnnnnaaaaaaaaaalllaaa2)(2)(2)(2)2.nnnnaaa1L(1)A(2)A(1)11(1)11,2,3, ,iialina第一步為：第一步為：LU

11、分解法四川大學(xué)水利水電學(xué)院第第k步為：步為：相當(dāng)于左乘矩陣相當(dāng)于左乘矩陣Lk( )( )( )( )1( )11,1, .11kkikkikkkkkkkknkaLliknlal( )( )kikkkkaa1, ,ikn 第第k行行第第i i行，行，四川大學(xué)水利水電學(xué)院(1)(1)(1)(1)1112131(2)(2)(2)22232(3)(3)1221333( ).0.00.000.nnnnnnnnaaaaaaaLLL L AUaaa總體有：總體有：21211111110010010100101nnllLLll易證：易證：四川大學(xué)水利水電學(xué)院1111112211221(.).nnnnALLL

12、LUL LLLU其中其中L為單位下三角陣，為單位下三角陣，U為上三角陣。為上三角陣。所以有：所以有：21313212,1111,.1nnn nlllULUlll四川大學(xué)水利水電學(xué)院().LybL UxbUxy注：分解理論由注：分解理論由Gauss消去法得出，因此能夠進行分解的條件與消去法得出，因此能夠進行分解的條件與Gauss消去法結(jié)果一樣。消去法結(jié)果一樣。* *（實際使用時也需要選主元，即列主元素三角分解法）（實際使用時也需要選主元，即列主元素三角分解法）由此，解線性方程組由此，解線性方程組Ax=b等價于解兩個三角形方程組：等價于解兩個三角形方程組：關(guān)鍵在于關(guān)鍵在于四川大學(xué)水利水電學(xué)院： A

13、的所有順序主子式均不為零，則的所有順序主子式均不為零，則A存在唯一的分解式存在唯一的分解式A=LU.(),ijnnAa11(1,2,., )kikirrkrikkkal ulikknu11(,1,., )kkjkjkrrjrual ujk kn：對非奇異矩陣：對非奇異矩陣A，存在排列陣，存在排列陣P，以及元素值全不，以及元素值全不大于大于1的單位下三角陣的單位下三角陣L和上三角陣和上三角陣U，使，使.PALU四川大學(xué)水利水電學(xué)院平方根法：設(shè)：設(shè)A為對稱正定矩陣，則存在唯一分解為對稱正定矩陣，則存在唯一分解 其中其中L為為 單位下三角陣，單位下三角陣，D D為對角陣且對角元全大于為對角陣且對角元

14、全大于0.0.,TALDL1/21/21/21/2()()TTTALDLLDDLLDLD：n n階矩陣階矩陣A A對稱正定時，則有如下分解：對稱正定時，則有如下分解： 則則A存在唯一分解存在唯一分解( (即平方根分解即平方根分解) )：其中其中G為下三角陣，規(guī)定為下三角陣，規(guī)定G的對角元的對角元全為正時，分解式是唯一的全為正時，分解式是唯一的. .TAGG四川大學(xué)水利水電學(xué)院12111,1(),(1, ).kkkkkkjjjkjkjkijiikkgaggag gkjng ：若線性代數(shù)方程組：若線性代數(shù)方程組 的系數(shù)矩陣的系數(shù)矩陣A A對稱正定，則用平方對稱正定，則用平方根法進行求解是穩(wěn)定的根法

15、進行求解是穩(wěn)定的. .（證明過程詳見（證明過程詳見P172P172）Axb：平方根法約需：平方根法約需 次乘法，大約為直接次乘法，大約為直接LU分解計算量的一半分解計算量的一半. .6/3n四川大學(xué)水利水電學(xué)院111)0(1,2,. )2) | |, (2,3,.,1),3) | |, | |,iiiinncinbacinbcba，定理：定理：A為三對角矩陣，且滿足為三對角矩陣，且滿足 則則A非奇異，且追趕法可實現(xiàn)。非奇異，且追趕法可實現(xiàn)。三對角方程組的三對角方程組的四川大學(xué)水利水電學(xué)院1111,(2,3,., ).,iiiiiiiqbapinqqbpc如果如果A存在存在LU分解，則有：分解，

16、則有：1111222222311111111,1nnnnnnnnnbcqcabcpqcpabcqcabpq其中其中四川大學(xué)水利水電學(xué)院111,(2,.,).,iiiiyfinyfp y.LUyfxy則：求解則：求解Ax=f11222333111,1nnnyfpyfpyfpyf 四川大學(xué)水利水電學(xué)院1,.,(1,.,1).nnniiiiiyxqyc xxinq111122221111,nnnnnnnqcxyqcxyqcxyqxy 再由再由解得解得以上稱為解三對角方程組的追趕法。以上稱為解三對角方程組的追趕法。四川大學(xué)水利水電學(xué)院典型題目1、利用LU方法、平方根法或追趕法對矩陣進行求解； 2、判斷

17、LU分解是否存在且唯一.：判斷下述矩陣的LU分解是否存在？若存在，是否唯一？1123241467A2111222331A3126251561546A( )0iiia已知(1,2,3.1)in0iD A有唯一的LU分解（LU存在且唯一）可從這兩方面對問題進行考慮四川大學(xué)水利水電學(xué)院？1123241467A2111222331A3126251561546A以從判斷矩陣的順序主子式為例0iD 對于A1 212024D 所以不存在LU分解對于A2 211022D 所以不存在LU分解對于A2 212125D 31262515161546D 所以存在唯一的LU分解四川大學(xué)水利水電學(xué)院范數(shù)、條件數(shù) 為了研究

18、線性方程組近似解的誤差估計和迭代法的收斂性，我們需要對 (n維向量空間)中的向量或 中矩陣的“大小”引入一種度量向量和矩陣的范數(shù)。n nRnR向量范數(shù)向量范數(shù) ：如果向量 的某個滿足條件：nxR( )N xx0,x 1）正定性： 當(dāng)且僅當(dāng)x=0時0;x ,;xxR2）齊次性：.xyxy3）三角不等式：nR則稱N(x)是 上的一個向量范數(shù).四川大學(xué)水利水電學(xué)院1maxiinxx 常用的幾種范數(shù)：向量的2-范數(shù)：12221()niixx11niixx向量的1-范數(shù)：向量的 -范數(shù)：絕對值之和模最大值四川大學(xué)水利水電學(xué)院| | | | | ,.nstsm xxM xxR ：對 上定義的任意兩種范數(shù)

19、必存在兩正常數(shù)m，M，使得：nR| | ,| | ,st( )*limkkxx：設(shè) 中一向量序列( )(1,2,.),kxk nR其中( )( )( )( )12,., .kkkkTnxxxx若滿足*12(,.,)TnnxxxxR*lim,(1,2,., )kjjkxxjn則稱向量序列 (依分量)收斂到 ，記作：( )kx*x( )*lim | 0.kkxx( )limkkxx：（PS： 必須為向量任一范數(shù).）| | 四川大學(xué)水利水電學(xué)院矩陣范數(shù)矩陣范數(shù) ：如果矩陣 的某個滿足條件：n nAR( )N AA0,A 1）正定性： 當(dāng)且僅當(dāng)x=0時0A ,;xxR2）齊次性：ABAB3）三角不等式

20、：nR則稱N(A)是 上的一個矩陣范數(shù).4）相容性：A BAB,;n nA BR,.n nA BR,;n nAR四川大學(xué)水利水電學(xué)院： 算子范數(shù)：0max,1sssxsAxAIx且常見的矩陣范數(shù)：max2(),TAA A譜范數(shù)111maxnijj niAa 列范數(shù)11maxniji njAa 行范數(shù)12211() .nnijFijAaF-范數(shù)算子范數(shù)四川大學(xué)水利水電學(xué)院( )limkkAA：設(shè) 中一矩陣序列 ( )(1,2,.),kAk n nR其中( )( )( )( )12,.,.kkkknAAAA若( )lim,( ,1,2,., ),kijijkaai jn則稱矩陣序列 收斂到矩陣 ，

21、記作：( )kAA( )lim | 0.kkAA：( )limkkAAPS：必須為任一種矩陣范數(shù).：設(shè) 為矩陣A的特征值，稱 為矩陣A的。(1 2, )i i, ,n1( )max|ii nS A 譜半徑和范數(shù)的關(guān)系：( ).S AA四川大學(xué)水利水電學(xué)院：設(shè)任意n階矩陣F滿足 ，則 非奇異，且：1F IF11.1IFF： lim01.kkAS A1( ).cond AAA（ 非奇異 ）：n nAR矩陣條件數(shù)的：1) cond( )1;A 2)cond()cond( );AA為任意非0常數(shù)。13)=1,cond( );AAA若 則4）若A是正交矩陣，則A的譜條件數(shù)等于1（相應(yīng)的譜范數(shù)也為1），為最小值.四川大學(xué)水利水電學(xué)院典型題目1、范數(shù)的證明與判斷(較難)，求常見范數(shù)(易)； 2、