第二章 數(shù)值代數(shù)

1、2.1 Gauss消去法消去法2.2 直接三角分解法直接三角分解法 2.3 范數(shù)和誤差分析范數(shù)和誤差分析 Cramer法則法則n20時(shí)，時(shí)， 計(jì)算量太大，現(xiàn)實(shí)上不可行計(jì)算量太大，現(xiàn)實(shí)上不可行 Cramer法則數(shù)學(xué)上很重要，計(jì)算上無(wú)價(jià)值法則數(shù)學(xué)上很重要，計(jì)算上無(wú)價(jià)值11 1111 1nnnnnnna xa xba xa xb,1,jjDxjnD1 理論基礎(chǔ)理論基礎(chǔ) 2 順序順序Gauss消去法消去法 3 選主元技術(shù)選主元技術(shù) 4 追趕法追趕法 引理引理2.1 證明證明(P14)11 1111 1nnmmnnma xa xba xaxb( , )( , )A bA b 行初等變換mnmnmnnbx

2、axabxaxa1111111同解例例2.1 消元過(guò)程消元過(guò)程 回代過(guò)程回代過(guò)程123123123634265xxxxxxxxx(1)(1)(1)11111,1(1)(1)(1)11,1nnnnnnnn na xa xaa xa xabAx用矩陣初等行變換化系數(shù)矩陣為三角形用矩陣初等行變換化系數(shù)矩陣為三角形(1)(1)(1)(1)1,112131(1)(1)(1)(1)(1)2,12122232(1)(1)(1)(1)(1)3,13132333(1)(1)(1)(1)(1),1123(1)11nnnnnnn nnnnnnaaaaaaaaaaaaaaaaaaaa(1)(2)(1)(1)11 11

3、(1)11,iijijijiaaal ala2, ;2,1injn(1)(1)(1)(1)1,112131(2)(2)(2)2,1232(2)(2)(2)(2)3,132333(2)(2)(2)(2),123(1)11(2)22000nnnnnnn nnnnnaaaaaaaaaaaaaaaaa(2)(3)(2)(2)2222(2)22,iijijijiaaal ala3, ;3,1injn)()() 1(kkjikkijkijalaa)()(kkkkikikaal1, 1; 1, 1;, 1nknkjnki1111()(1)()nknknk nknk乘法次數(shù)除法次數(shù)(1)11(2)22(3(1

4、)(1)(1)(1)1,112131(2)(2)(2)2,1232(3)()33)3,13( ),)13(000000nnnnnnnnnnnnaaaaaaaaaaaaaa( )01,2,kkkakn，主元素上三角矩陣(1)11(1)(1)(1)112211,12)(2)(2)222,1( ),122( )nnnnnnnnnnnnnxa xa xaxaaaxaxaa回代回代) 1 , 1()()(1)()(1,)()(1,nkaxaaxaaxkkknkjjkkjknkknnnnnnn1111()1nknknk乘法次數(shù)除法次數(shù)消元消元 回代回代 總和總和11(1)(25)()(2)6nkn nnn

5、k nk2) 1() 1(11nniknnink332333nnnn計(jì)算量主要在消元比較Cramer法則Gauss 法快很多如果如果A=(aij)n n的順序主子式的順序主子式均不為零，順序均不為零，順序Gauss消去法求解可行。消去法求解可行。 為什么要選主元素？為什么要選主元素？主元素主元素=0，計(jì)算就不能進(jìn)行。，計(jì)算就不能進(jìn)行。主元素主元素 0, 計(jì)算過(guò)程數(shù)值不穩(wěn)定。計(jì)算過(guò)程數(shù)值不穩(wěn)定。怎樣選主元素？怎樣選主元素？ 把絕對(duì)值大的數(shù)調(diào)到對(duì)角線(xiàn)上把絕對(duì)值大的數(shù)調(diào)到對(duì)角線(xiàn)上例例 2.2 3位有效數(shù)字位有效數(shù)字 21001. 02121xxxx5461621311111361 5131 4()2

6、111 6rr 選主元21310.50.5615001.5 1.50420.5 8.5rrrr 2361500.5 8.5001.5 1.524rr 如果如果A=(aij)n n的的行列式行列式不為零不為零，選列主元素，選列主元素Gauss消去法求解可行。消去法求解可行。 比較：比較：如果如果A A=(=(a aijij) )n n n n的的順序主子式均不為零順序主子式均不為零，順序順序GaussGauss消去法求解可行。消去法求解可行。三對(duì)角方程組三對(duì)角方程組 順序順序Gauss消去法應(yīng)用于三對(duì)角線(xiàn)性方程組消去法應(yīng)用于三對(duì)角線(xiàn)性方程組得到所謂得到所謂追趕法追趕法，其中消元過(guò)程為，其中消元過(guò)

7、程為“追追”，回代過(guò)程為回代過(guò)程為“趕趕”。1 112121222321211111nnnnnnnnnnnnb xc xda xb xc xdaxbxcxda xb xd追追 k=2, , n 趕趕 k= n-1, , 1 追趕法不對(duì)零元素計(jì)算，只有追趕法不對(duì)零元素計(jì)算，只有2(n-1)+(n-1)+n+(n-1) =5n-4次乘除法計(jì)算量次乘除法計(jì)算量注意注意: :追趕法假定主元不為追趕法假定主元不為0, 0, 計(jì)算中不選主元計(jì)算中不選主元. .,11bb 11dd,11kkkkkkkclbbbal1kkkkdlddnnnbdxkkkkkbxcdx1高斯消去法的矩陣表示高斯消去法的矩陣表示L

8、U分解法分解法平方根法平方根法改進(jìn)的平方根法改進(jìn)的平方根法對(duì)一個(gè)矩陣施行一次行變換，相當(dāng)于左乘一個(gè)相對(duì)一個(gè)矩陣施行一次行變換，相當(dāng)于左乘一個(gè)相應(yīng)的初等矩陣。應(yīng)的初等矩陣。順序高斯消去法相當(dāng)于矩陣三角分解順序高斯消去法相當(dāng)于矩陣三角分解A=LUP21 例題例題 P3P2P1A=U選列主元高斯消去法相當(dāng)于三角分解選列主元高斯消去法相當(dāng)于三角分解PA=LU, 其其中中P為行置換矩陣為行置換矩陣(詳見(jiàn)課本詳見(jiàn)課本38頁(yè)頁(yè))A=LU (Doolittle分解分解)解方程組解方程組P22 例例2.5待定系數(shù)法待定系數(shù)法1112121nnlllL11121222nnnnuuuuuUuLybAxbLUxbUx

9、y待定系數(shù)法待定系數(shù)法(依次顯式計(jì)算，無(wú)須解方程組依次顯式計(jì)算，無(wú)須解方程組)111211112112221212221212111nnnnnnnnnnnnaaauuuaaaluuaaalluLU分解法和分解法和Gauss消去法具有相同的可行性條消去法具有相同的可行性條件件, 基本相同的計(jì)算量和計(jì)算精度?；鞠嗤挠?jì)算量和計(jì)算精度。LU分解法具有比分解法具有比Gauss消去法更好的設(shè)計(jì)靈活消去法更好的設(shè)計(jì)靈活性。性。 當(dāng)多次求解具有相同系數(shù)矩陣和不同右段向量的當(dāng)多次求解具有相同系數(shù)矩陣和不同右段向量的線(xiàn)性方程組線(xiàn)性方程組 ；防止防止“大數(shù)吃小數(shù)大數(shù)吃小數(shù)” ； LU分解存儲(chǔ)可使用緊湊格式分解存

10、儲(chǔ)可使用緊湊格式 。三角分解的其他形式三角分解的其他形式: Crout分解等分解等.A=LLT(Cholesky分解分解)基本方法基本方法: 待定系數(shù)法待定系數(shù)法手算：由順序主子式先求對(duì)角線(xiàn)手算：由順序主子式先求對(duì)角線(xiàn)編程編程: 使用公式使用公式 i=k+1, n, k=1,n乘除法次數(shù)乘除法次數(shù)n(n+4)(n-1)/6, 開(kāi)方開(kāi)方n次次P24 例例2.6 112kjkjkkkklal11212212nnnnlllLlll1,1,kkkkDlknD )(111kjkjijikkkikllall可行性條件可行性條件: 對(duì)稱(chēng)正定對(duì)稱(chēng)正定.直接驗(yàn)證知：在平方根法中，直接驗(yàn)證知：在平方根法中， ，k

11、=1, ,n, j=1, , k中間量中間量lkj不會(huì)出現(xiàn)放大不會(huì)出現(xiàn)放大, 從而平方根法是數(shù)值從而平方根法是數(shù)值穩(wěn)定的。不必選主元穩(wěn)定的。不必選主元. . kkkjkjkjkkalla12|A=LDLT, 待定系數(shù)法待定系數(shù)法利用順序主子式先求對(duì)角線(xiàn)利用順序主子式先求對(duì)角線(xiàn)111,2,kkkDdD dknD1211211,1nnndlLDdll改進(jìn)在哪里？改進(jìn)在哪里？(1)(1)避免了開(kāi)方運(yùn)算避免了開(kāi)方運(yùn)算; ; (2)(2)計(jì)算的可行性條件減弱為計(jì)算的可行性條件減弱為A A對(duì)稱(chēng)非奇異。對(duì)稱(chēng)非奇異。 P26 例例2. 71 范數(shù)和條件數(shù)范數(shù)和條件數(shù)2 數(shù)據(jù)擾動(dòng)分析數(shù)據(jù)擾動(dòng)分析引例引例 121

12、221.00021.0001xxxx121221.00012xxxx1121xx1220 xx病態(tài)方程組：數(shù)據(jù)小擾動(dòng)解大誤差。注意：兩組解都是相應(yīng)方程組的精確解， 沒(méi)有計(jì)算誤差什么原因?qū)е路匠探M病態(tài)？什么原因?qū)е路匠探M病態(tài)？怎樣識(shí)別病態(tài)方程組？怎樣識(shí)別病態(tài)方程組？病態(tài)方程組怎樣求解？病態(tài)方程組怎樣求解？ Rn上實(shí)值函數(shù)上實(shí)值函數(shù)|.|, 滿(mǎn)足滿(mǎn)足正定性正定性 |x| 0, 且且|x|=0 x=0齊次性齊次性 | x|= | |x|三角不等式三角不等式 |x+y| |x| + |y|常用向量范數(shù)常用向量范數(shù)1maxii nxx 11niixx12221niixxRnn上實(shí)值函數(shù)上實(shí)值函數(shù)|.|,

13、 滿(mǎn)足滿(mǎn)足正定性正定性 |A| 0, 且且|A|=0A=0齊次性齊次性 | A|= | |A|三角不等式三角不等式 |A+B| |A| + |B|相容性相容性 |AB| |A| |B|與向量范數(shù)相容與向量范數(shù)相容 |Ax| |A| |x|1111121211maxmaxmax()trace()niji njnijj niTii nnnTijFijAaAaAA AAaA A 行范數(shù)列范數(shù)譜范數(shù)F范數(shù)(跡范數(shù))相容性： |Ax|v |A| v |x| v, v=1,2, |Ax|2 |A| F |x| 2|x|p0 |x|q0pqpxcxxc2112pqpcAAcA病態(tài)方程組：系數(shù)矩陣條件數(shù)很大病態(tài)方程組：系數(shù)矩陣條件數(shù)很大P32例例2.10(2)(P16例例2.2)1 ( )cond AA A條件數(shù)111001. 0A100001001. 0A1011A病態(tài)順序Gauss選主元不病態(tài)不病態(tài)右端數(shù)據(jù)擾動(dòng)右端數(shù)據(jù)擾動(dòng)Ax*=b , A(x*+ x)=b+ b證明證明 | x| |A-1