數(shù)值分析典型例題與習(xí)題2PPT課件

1、1/51三、四章內(nèi)容提要三、四章內(nèi)容提要典型例題分析典型例題分析數(shù)值分析典型例題典型例題 II2/51Axb 化難為易化難為易化繁為簡化繁為簡化繁為簡化繁為簡3/51初等行變換不改變方程組的解初等行變換不改變方程組的解1.交換矩陣的第交換矩陣的第i行與第行與第j行的位置行的位置2.以非零數(shù)以非零數(shù)k乘以矩陣的第乘以矩陣的第i行的行的每個元素每個元素3.把矩陣的第把矩陣的第i行的每個元素的行的每個元素的k倍倍加到第加到第j行的對應(yīng)元素上去行的對應(yīng)元素上去4/51A(n 1) = Fn-1Fn-2F1 A其中其中Fk 為為 Frobenius矩陣。矩陣。A=F1-1F2-1 Fn-1-1 A(n

2、1)直接方法直接方法: 高斯消元法高斯消元法 L U高斯消元法本質(zhì)是矩陣的分解。 1111,121nnnmmmL )1()1(2)1(2211211nnnnnaaaaaaU5/51矩陣分解矩陣分解( (Top 10 Algorithms) )(1)特征值分解特征值分解: A=CDC, C,D=eig(A)(3) LU分解分解: PA=LU, L,U,P=lu(A)(4)Cholesky分解分解: A=LLT, R=chol(A)(2)奇異值分解奇異值分解: A=USV , U,S,V = svd(A) (5) 非負(fù)矩陣分解非負(fù)矩陣分解Learning the Parts of Objects

3、by Non-negative Matrix Factorization, , 19996/51Demo1I=imread(monalisa.pgm);U,S,V=svd(double(I);s=diag(S);n1=5;Snew=diag(s(1:n1);zeros(size(s,1)-n1,1);figure,imshow(U*Snew*V,)n2=20;Snew=diag(s(1:n2);zeros(size(s,1)-n2,1);figure, imshow(U*Snew*V,)7/51*lim()nnxx 0101()()nnxxxxx 迭代法思想迭代法思想:Iterate: To

4、say or do again or again and again 迭代背后的思想是一種與傳統(tǒng)思維模式截然不同的方式迭代背后的思想是一種與傳統(tǒng)思維模式截然不同的方式,傳統(tǒng)思維方式往往希望一遍做好傳統(tǒng)思維方式往往希望一遍做好,一次成功一次成功;但是迭代開發(fā)意但是迭代開發(fā)意味著反復(fù)地做味著反復(fù)地做,不斷地根據(jù)反饋進(jìn)行調(diào)整。不斷地根據(jù)反饋進(jìn)行調(diào)整。8/5111( )( )()|*|kkkXXXXBB 11( )*( )()|kkkLLxxxx ( )xx 迭代格式構(gòu)造迭代格式構(gòu)造收斂條件收斂條件(局部局部vs全局全局)中止準(zhǔn)則中止準(zhǔn)則*(0)*()( )|()| 1,(, ()N xxxN xxx

5、xx 為為的的不不動動點點在在 的的連連續(xù)續(xù)且且則則迭迭代代法法對對任任意意某某鄰鄰域域收收斂斂(0)X( )1| | |1fBB 對對任任意意的的 和和迭迭代代法法收收斂斂的的充充分分必必要要條條件件是是和和充充分分條條件件是是任任意意的的初初始始向向量量加速加速(松弛思想松弛思想)Aitken加速方法加速方法 超松弛加速方法超松弛加速方法9/51 共軛梯度法共軛梯度法的關(guān)鍵是構(gòu)造一組兩兩共軛的關(guān)鍵是構(gòu)造一組兩兩共軛的方向的方向( (第第k步迭代生成共軛方向張成步迭代生成共軛方向張成k維子維子空間空間) )。巧妙的是。巧妙的是共軛方向可以由上次搜索共軛方向可以由上次搜索方向和當(dāng)前的梯度方向組

6、合產(chǎn)生。方向和當(dāng)前的梯度方向組合產(chǎn)生?，F(xiàn)代迭代方法現(xiàn)代迭代方法 ( (Top 10 Algorithms) ) 最速下降法最速下降法思想簡單思想簡單,但收斂速度慢。本但收斂速度慢。本質(zhì)上因為負(fù)梯度方向函數(shù)下降快是局部性質(zhì)。質(zhì)上因為負(fù)梯度方向函數(shù)下降快是局部性質(zhì)。10/51復(fù)雜性復(fù)雜性: :高斯消元法共用乘法和除法次數(shù)為高斯消元法共用乘法和除法次數(shù)為n3/3+ n2-n/3,常用記號常用記號O表示是多少階的表示是多少階的,則則O (n3/3)。注釋注釋2: : 復(fù)雜性對估計求解大型方程組所需的時間有用。復(fù)雜性對估計求解大型方程組所需的時間有用。例如在一臺特定的計算機(jī)上求解例如在一臺特定的計算機(jī)上

7、求解n= =500個方程的方程組所個方程的方程組所需的時間我們可以通過求解一個需的時間我們可以通過求解一個n= =50個方程的方程組得到個方程的方程組得到一個很好的猜測一個很好的猜測,即對用掉的時間按比例放大即對用掉的時間按比例放大1000倍。倍。注釋注釋1: :按按O的記法的記法,把把n的不同次冪相加的結(jié)果僅保留了最的不同次冪相加的結(jié)果僅保留了最高次冪高次冪,因為最高次冪決定了當(dāng)因為最高次冪決定了當(dāng)n趨近無窮時的極限形態(tài)。趨近無窮時的極限形態(tài)。換而言之換而言之,對于大的對于大的n ,低階項對算法的執(zhí)行時間的估計沒有低階項對算法的執(zhí)行時間的估計沒有太大影響太大影響, 僅需要近似估計執(zhí)行時間時可

8、以忽略不計。僅需要近似估計執(zhí)行時間時可以忽略不計。11/511211ninixxxxx 121maxmax,ininxxxxx 常用的范數(shù)常用的范數(shù):22222121|ninixxxxx 111maxnijj niAa 2(),( )max|( )|TiiAA ABB其其中中11maxniji njAa 2,1:2,2ni jFi jAa 注注釋釋不不是是向向量量 范范數(shù)數(shù)誘誘導(dǎo)導(dǎo)的的算算子子范范數(shù)數(shù)是是與與向向量量 范范數(shù)數(shù)相相容容矩矩陣陣范范數(shù)數(shù)。 12/5112(),04(), 2(),AF 計計 算算及及 其其 逆逆 矩矩 陣陣 的的 1 1范范 數(shù)數(shù) 列列 和和 范范 數(shù)數(shù)范范 數(shù)數(shù)

9、 行行 和和 范范 數(shù)數(shù)范范 數(shù)數(shù) 譜譜 范范 數(shù)數(shù)范范 數(shù)數(shù) 及及 各各范范 數(shù)數(shù) 意意 義義 下下 的的 條條 件件 數(shù)數(shù) 。12=6,=4,= 4.4954,= 4.5826FAAAA 1211410A 11113212=1,=,= 1.1238,= 1.1456FAAAA 13/511條條 件件 數(shù)數(shù) 為為 的的 矩矩 陣陣 ？1222cond| |()()1TTTAAIAAAAAAA 正正 交交 矩矩 陣陣 ( () ) = = = = cond|1III 算算 子子 范范 數(shù)數(shù)( ( ) )= =Hilbert矩陣條件數(shù)矩陣條件數(shù):for i=1:10c(i)=cond(hilb(

10、i),2);%vander(1:i)end,plot(1:10,c)14/51范數(shù)范數(shù)(全局全局)問題的好與壞問題的好與壞 算法的快與慢算法的快與慢| X(k+1) X* | |B| | X(k) X* | 1| |()|AAxbxb 范數(shù)的威力和魅力范數(shù)的威力和魅力: :*| |0 |maxaaaaBxBxmaxxxaaBB 向向量量范范數(shù)數(shù) 誘誘導(dǎo)導(dǎo)的的算算子子范范數(shù)數(shù)是是所所有有與與即即最最壞壞結(jié)結(jié)果果里里面面最最好好的的向向量量范范數(shù)數(shù) 相相容容矩矩陣陣范范數(shù)數(shù)的的下下界界( () )15/51 1111, 1nkkkkmmF nkkkkmmm, 100ekT= 0 0 1 0 0 =

11、 I mkekTFk1 = I + mk ekT( k = 1, 2, , n 1)16/51F1-1F2-1 Fn-1-1 = 111 1111,nnm 1111,121nnnmmmFk1 Fj1 = I + mk ekT+mj ejT kjF1-1F2-1 Fn-1-1 = I + m1 e1T+mn-1 en-1T 例例1.1. ekTmj =0, kj17/51例例2.2.設(shè)設(shè)A為對稱矩陣。為對稱矩陣。高斯消元法一步后高斯消元法一步后,A約化為約化為 1110TaB 證明證明 B 也是對稱矩陣也是對稱矩陣。 1111111111111111111,0TTaTnaaF AmmIAAm 1

12、11111TaBA 18/51約化主元不為零的判斷約化主元不為零的判斷定理定理3.1 約化主元約化主元 的充分必要條件是矩陣的充分必要條件是矩陣A各階順序主子式各階順序主子式不等于零。即不等于零。即(1),0 ( =1,2, )kk kakn 11110 ( =1, )kkkkkaaDknaa19/51例例4 4. .嚴(yán)格對角占優(yōu)矩陣的嚴(yán)格對角占優(yōu)矩陣的約化主元約化主元ak,k(k-1) 0 (k=1,n) 。例例3 3. .嚴(yán)格主對角占優(yōu)矩陣一定是非奇異的。嚴(yán)格主對角占優(yōu)矩陣一定是非奇異的。 嚴(yán)格對角占優(yōu)矩陣嚴(yán)格對角占優(yōu)矩陣: :高斯消元法中約化主元高斯消元法中約化主元不等于零不等于零,Ja

13、cobi方法方法, GS方法和方法和SOR方法收斂。方法收斂。思考思考: 若若A是嚴(yán)格對角占優(yōu)矩陣是嚴(yán)格對角占優(yōu)矩陣, 當(dāng)當(dāng)0 w =1時時, SOR方法收斂。方法收斂。 11detdetI BDLDLDU （- - ）= =( ( ( - -) ) ( ( ( - -) )- - ( ( (1 1- - ) ) + +) ) ) )= =0 020/51例例5 5. .Ax= =b b, ,其中其中A對稱正定對稱正定, ,問解此方程的問解此方程的Jacobi迭代法是否一定收斂？迭代法是否一定收斂？12310 40 410 410 820 40 813.xxx 1 09282031( ).B

14、對稱正定矩陣對稱正定矩陣: :直接法高斯消元法中約化直接法高斯消元法中約化主元大于零主元大于零, ,迭代法迭代法GS方法方法, ,SOR方法方法, ,最速下最速下降方法和共軛梯度法收斂。降方法和共軛梯度法收斂。21/51例例6 6. .,TAAxx Ax 設(shè)設(shè) 對對稱稱正正定定矩矩陣陣 證證明明是是向向量量范范數(shù)數(shù)。22222:=+()TTTTTATTTAAACholeskyALLxx Ax x LL xL xx yLxyL xL yxy 思思路路 對對稱稱正正定定矩矩陣陣的的分分解解。112c,=+ababxxaaxaxax2 2和和是是兩兩個個向向量量范范數(shù)數(shù)和和是是兩兩個個正正實實數(shù)數(shù)證

15、證明明是是向向量量范范數(shù)數(shù)。22/51例例7 7. .max1222min()cond( )| |()TTA AAAAA A 2max|()TAA A 1,TTA AA A AA 和和特特征征值值互互為為倒倒數(shù)數(shù)和和特特征征值值相相同同。1-1-12maxmaxmin|()()=1/()TTTAA AA AA A 23/51例例8 8. .2,( )AAA 如如果果矩矩陣陣 對對稱稱 則則2max2max2minmin,()( )() |( )| ,cond( )( )()TTTTTTTiiTAACDCA AACDC CDCCDDCA AAA AAAAA A 對對稱稱 則則病因病因是條件數(shù)大是

16、條件數(shù)大, ,病癥病癥是什么呢是什么呢? ?,maxmin*()()*0cond( )cond( )co1|2| ,+1nd( )AAkkAAxxAxAAx 24/51例例9 9. .矩陣的矩陣的Doolittle分解分解 A = LU, L為單位下三角矩陣為單位下三角矩陣,U為上三角矩陣。為上三角矩陣。 nnnnnnnuuuuuummm222112111,121111 nnnnnnaaaaaaaaaA212222111211a11= u11, , a1n= u1na21 = m21u11, , an1 = mn1u1125/51對對A的元素的元素aij ,當(dāng)當(dāng) jk 和和 ik+1時時 11

17、kkjkrrjrkjuam u 11kikirrkkrkikamuum m21u12+ u22=a22, , m21u1n+ u2n=a2n u22=a22 - m21u12, , u2n=a2n- m21u1n m31u12+ m32u22=a32, , mn1u12+ mn2u22=an2 m32=(a32- m31u12)/u22, , mn2=(an2- mn1u12)/u2226/5111kkjkrrjrkjam uu 11()/kikirrkkikrkam uum 矩陣矩陣L和矩陣和矩陣U的元素計算公式的元素計算公式計算次序計算次序123456 nnnnnnnummuumuuuA1

18、,1222211121127/51更新順序更新順序: 先先行行后后列列列列除除行行不除不除舊元素減去舊元素減去所在所在行行和和列列前前k-1分量點乘的加和分量點乘的加和Doolittle分解：分解：更新順序更新順序: 先先列列后后行行行行除除列列不除不除舊元素減去舊元素減去所在所在行行和和列列前前k-1分量點乘的加和分量點乘的加和Crout分解：分解：28/51 求矩陣的求矩陣的Doolittle分解分解1212253222351323A 1212253222351323 1212211222351123 1212211222331103 29/51三對角矩陣分解三對角矩陣分解 5324223

19、112 5324222/52/112 2/54/525/125/422/52/112 5325/125/422/52/112 14/515/412/11L 2/525/1222/512U30/51 nnbabacbA2211 1111,/kkkkkkkcbab 步驟步驟I:三對角矩陣分解三對角矩陣分解 A = L U nncc 22211( k = 2, 3, , n )31/51下三角方程組下三角方程組 LY = f 步驟步驟II: ), 2(),(111nkyfyfykkkk nnnfffyyy21212111 nnnnyyyxxxcc21211211 上三角方程組上三角方程組 UX =

20、Y )1 , 1(,/ )(/1nkxcyxyxkkkkknnn 步驟步驟III:求解三對角方程組的追趕法求解三對角方程組的追趕法32/5111diag(,)nnWuu 1,TALULWWULLWLL 其其中中為為下下三三角角矩矩陣陣。對稱正定矩陣的對稱正定矩陣的 Cholesky分解分解ALU 33/51(1) 對于非零向量對于非零向量, xTAx總是正的總是正的;(2) A的順序主子式全大于零的順序主子式全大于零;(3) A的特征值全為正實數(shù)的特征值全為正實數(shù)。help chol對稱正定矩陣對稱正定矩陣: :34/511) 序列收斂序列收斂2) 迭代矩陣譜半徑小于迭代矩陣譜半徑小于13)

21、迭代矩陣特征值全小于迭代矩陣特征值全小于1 4) 迭代矩陣范數(shù)小于迭代矩陣范數(shù)小于15) 反證法反證法迭代法收斂證明思路迭代法收斂證明思路:| 0BxxIB = =或或35/51例例1010. .設(shè)設(shè)A是一個可逆矩陣是一個可逆矩陣, 矩陣序列滿足矩陣序列滿足 Xk+1=Xk(2I A Xk )，（，（k =0, ,1, ,2, ,） 則當(dāng)則當(dāng) 時時1)(0 AXI 1lim AXkk證明：由證明：由Xk+1=Xk(2I A Xk )，得，得 I AXk+1 = I A Xk(2I A Xk )= (I A Xk )2 于是于是 I AXk =(I A Xk -1)2 =(I A Xk -2)2

22、2 = 20()kIAX20lim()0kkIAX 1limkkXA 36/51例例1111. .1122()20,JacobiGSijAaa aAx b 設(shè)設(shè)是是 階階矩矩陣陣且且試試證證明明求求解解方方程程組組= = 的的方方法法和和方方法法同同時時收收斂斂或或發(fā)發(fā)散散。121112 2111 2221220,|0aaa aJa aaaB 其其譜譜半半徑徑為為121112 2111 2212 2111 220,|0aaa aGSa aa aa aB 其其譜譜半半徑徑為為思路思路: 37/51(1) A1 = B ( I + R + R2 + )；(2)任意給定任意給定n階矩陣階矩陣X0,由

23、迭代格式由迭代格式 Xk+1 = Xk R + B ( k = 0,1,2, )產(chǎn)生的矩陣序列產(chǎn)生的矩陣序列 Xk 收斂到矩陣收斂到矩陣A-1；(3)對矩陣序列對矩陣序列 Xk , 有誤差估計式有誤差估計式|11|11kkkXXqAX 例例1212. .設(shè)設(shè)A是是n階可逆矩陣階可逆矩陣,有有A的一個近似逆的一個近似逆B,令令 R=I AB。如果如果 | R | q 1,| |1,kkkxBxfxBBxxBxfxx 設(shè)設(shè)有有唯唯一一解解若若矩矩陣陣的的譜譜半半徑徑（ ) )但但有有一一個個特特征征值值求求證證存存在在初初始始向向量量使使得得迭迭代代格格式式產(chǎn)產(chǎn)生生的的序序列列收收斂斂于于 。例例

24、15.15.11+*10*0*0*+*11,= ()=(),= +,=kkkkkkkkByy ByyxxB xxBxxyxxxy xxxByy （1 1）（ ）（1 1）則則取取初初始始向向量量思路思路: 定理定理4.1 對對任意的任意的f和和任意的初始向量任意的初始向量X(0)迭代法迭代法 X(k+1) =B X(k) +f 收斂的收斂的充分必要充分必要條件是條件是( )1B 42/51(1)( )(1)( ),0,2kkkkAxxxxAbAx b 設(shè)設(shè) 為為對對稱稱正正定定矩矩陣陣 證證明明迭迭代代格格式式其其中中則則對對于于任任意意初初始始向向量量收收斂斂到到= = 的的解解。例例16.

25、16.思路思路: 43/51112233,1 11Jacobiaaaxbaaxbaaxb 研研究究 滿滿足足什什么么條條件件時時 求求解解線線性性方方程程組組的的迭迭代代方方法法收收斂斂。例例17.17.思路思路: -1/2a1/2收斂收斂, -1/2a1時系數(shù)矩陣正定。時系數(shù)矩陣正定。 44/51例例18.18.11=C,nB CDD 對對稱稱矩矩陣陣11=C,kkkkknBCDD 對對稱稱矩矩陣陣 | |1| |,B 收收斂斂于于零零的的充充分分必必要要條條件件是是。進(jìn)進(jìn)一一步步地地如如果果越越小小 則則收收斂斂速速度度越越快快。45/51例例18.18.231111,1 ,1mm mJJ

26、J 3112211112112211112211, mkkkkkkkkkkkkkkkkkkmk mkkkkkmk mkkkkkkkm mCCCJJCCCCCCJC 進(jìn)進(jìn)一一步步有有 23,| |1kkkmJJJ 收收斂斂于于零零的的充充分分必必要要條條件件是是。| |1B 收收斂斂于于零零矩矩陣陣的的充充分分必必要要條條件件是是。46/51例例18.18.121121,1 ,iiiiriirnnkkkkkkrJJJJnnJJJBP J P JJ 其其中中1=,JordanB P JP JB 對對于于一一般般矩矩陣陣是是 的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)形形。lim=0lim=0lim=0kkkikkkBJJ故故47/51參考參考: :Writting Fast Matlab Codes1. .中小規(guī)模線性方程組中小規(guī)模線性方程組x = Ab; % Solves A*x = b2.(.(超超) )大規(guī)模線性方程組大規(guī)模線性方程組(Preconditioned cg)48/51作業(yè)作業(yè)題目題目1: 從理論角度從理論角度(復(fù)雜度和收斂性復(fù)雜度和收斂性)比較各比較各 種方法的優(yōu)劣。種方法的優(yōu)劣。題目題目2: 從數(shù)值角度比較各種方法的性能從數(shù)值角度比較各種方法的性能( (公平公平) )題目題目3: 科研或生活中遇到的線性方程組？科研或生活中