数值分析典型例题与习题2ppt课件

1、1/51三、四章内容提要三、四章内容提要典型例题分析典型例题分析数值分析典型例题典型例题 II2/51Axb 化难为易化难为易化繁为简化繁为简化繁为简化繁为简3/51初等行变换不改变方程组的解初等行变换不改变方程组的解1.交换矩阵的第交换矩阵的第i行与第行与第j行的位置行的位置2.以非零数以非零数k乘以矩阵的第乘以矩阵的第i行的行的每个元素每个元素3.把矩阵的第把矩阵的第i行的每个元素的行的每个元素的k倍倍加到第加到第j行的对应元素上去行的对应元素上去4/51A(n 1) = Fn-1Fn-2F1 A其中其中Fk 为为 Frobenius矩阵。矩阵。A=F1-1F2-1 Fn-1-1 A(n

2、1)直接方法直接方法: 高斯消元法高斯消元法 L U高斯消元法本质是矩阵的分解。 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) 非负矩阵分解非负矩阵分解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 迭代背后的思想是一种与传统思维模式截然不同的方式迭代背后的思想是一种与传统思维模式截然不同的方式,传统思维方式往往希望一遍做好传统思维方式往往希望一遍做好,一次成功一次成功;但是迭代开发意但是迭代开发意味着反复地做味着反复地做,不断地根据反馈进行调整。不断地根据反馈进行调整。8/5111( )( )()|*|kkkXXXXBB 11( )*( )()|kkkLLxxxx ( )xx 迭代格式构造迭代格式构造收敛条件收敛条件(局部局部vs全局全局)中止准则中止准则*(0)*()( )|()| 1,(, ()N xxxN xxx

5、xx 为为的的不不动动点点在在 的的连连续续且且则则迭迭代代法法对对任任意意某某邻邻域域收收敛敛(0)X( )1| | |1fBB 对对任任意意的的 和和迭迭代代法法收收敛敛的的充充分分必必要要条条件件是是和和充充分分条条件件是是任任意意的的初初始始向向量量加速加速(松弛思想松弛思想)Aitken加速方法加速方法 超松弛加速方法超松弛加速方法9/51 共轭梯度法共轭梯度法的关键是构造一组两两共轭的关键是构造一组两两共轭的方向的方向( (第第k步迭代生成共轭方向张成步迭代生成共轭方向张成k维子维子空间空间) )。巧妙的是。巧妙的是共轭方向可以由上次搜索共轭方向可以由上次搜索方向和当前的梯度方向组

6、合产生。方向和当前的梯度方向组合产生。现代迭代方法现代迭代方法 ( (Top 10 Algorithms) ) 最速下降法最速下降法思想简单思想简单,但收敛速度慢。本质但收敛速度慢。本质上因为负梯度方向函数下降快是局部性质。上因为负梯度方向函数下降快是局部性质。10/51复杂性复杂性: :高斯消元法共用乘法和除法次数为高斯消元法共用乘法和除法次数为n3/3+ n2-n/3,常用记号常用记号O表示是多少阶的表示是多少阶的,则则O (n3/3)。注释注释2: : 复杂性对估计求解大型方程组所需的时间有用。复杂性对估计求解大型方程组所需的时间有用。例如在一台特定的计算机上求解例如在一台特定的计算机上

7、求解n= =500个方程的方程组所个方程的方程组所需的时间我们可以通过求解一个需的时间我们可以通过求解一个n= =50个方程的方程组得到个方程的方程组得到一个很好的猜测一个很好的猜测,即对用掉的时间按比例放大即对用掉的时间按比例放大1000倍。倍。注释注释1: :按按O的记法的记法,把把n的不同次幂相加的结果仅保留了最的不同次幂相加的结果仅保留了最高次幂高次幂,因为最高次幂决定了当因为最高次幂决定了当n趋近无穷时的极限形态。趋近无穷时的极限形态。换而言之换而言之,对于大的对于大的n ,低阶项对算法的执行时间的估计没有低阶项对算法的执行时间的估计没有太大影响太大影响, 仅需要近似估计执行时间时可

8、以忽略不计。仅需要近似估计执行时间时可以忽略不计。11/511211ninixxxxx 121maxmax,ininxxxxx 常用的范数常用的范数:22222121|ninixxxxx 111maxnijj niAa 2(),( )max|( )|TiiAA ABB其其中中11maxniji njAa 2,1:2,2ni jFi jAa 注注释释不不是是向向量量 范范数数诱诱导导的的算算子子范范数数是是与与向向量量 范范数数相相容容矩矩阵阵范范数数。 12/5112(),04(), 2(),AF 计计 算算及及 其其 逆逆 矩矩 阵阵 的的 1 1范范 数数 列列 和和 范范 数数范范 数数

9、 行行 和和 范范 数数范范 数数 谱谱 范范 数数范范 数数 及及 各各范范 数数 意意 义义 下下 的的 条条 件件 数数 。12=6,=4,= 4.4954,= 4.5826FAAAA 1211410A 11113212=1,=,= 1.1238,= 1.1456FAAAA 13/511条条 件件 数数 为为 的的 矩矩 阵阵 ？1222cond| |()()1TTTAAIAAAAAAA 正正 交交 矩矩 阵阵 ( () ) = = = = cond|1III 算算 子子 范范 数数( ( ) )= =Hilbert矩阵条件数矩阵条件数:for i=1:10c(i)=cond(hilb(

10、i),2);%vander(1:i)end,plot(1:10,c)14/51范数范数(全局全局)问题的好与坏问题的好与坏 算法的快与慢算法的快与慢| X(k+1) X* | |B| | X(k) X* | 1| |()|AAxbxb 范数的威力和魅力范数的威力和魅力: :*| |0 |maxaaaaBxBxmaxxxaaBB 向向量量范范数数 诱诱导导的的算算子子范范数数是是所所有有与与即即最最坏坏结结果果里里面面最最好好的的向向量量范范数数 相相容容矩矩阵阵范范数数的的下下界界( () )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.设设A为对称矩阵。为对称矩阵。高斯消元法一步后高斯消元法一步后,A约化为约化为 1110TaB 证明证明 B 也是对称矩阵也是对称矩阵。 1111111111111111111,0TTaTnaaF AmmIAAm 1

12、11111TaBA 18/51约化主元不为零的判断约化主元不为零的判断定理定理3.1 约化主元约化主元 的充分必要条件是矩阵的充分必要条件是矩阵A各阶顺序主子式各阶顺序主子式不等于零。即不等于零。即(1),0 ( =1,2, )kk kakn 11110 ( =1, )kkkkkaaDknaa 19/51例例4 4. .严格对角占优矩阵的严格对角占优矩阵的约化主元约化主元ak,k(k-1) 0 (k=1,n) 。例例3 3. .严格主对角占优矩阵一定是非奇异的。严格主对角占优矩阵一定是非奇异的。 严格对角占优矩阵严格对角占优矩阵: :高斯消元法中约化主元高斯消元法中约化主元不等于零不等于零,J

13、acobi方法方法, GS方法和方法和SOR方法收敛。方法收敛。思考思考: 若若A是严格对角占优矩阵是严格对角占优矩阵, 当当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 设设 对对称称正正定定矩矩阵阵 证证明明是是向向量量范范数数。22222:=+()TTTTTATTTAAACholeskyALLxx Ax x LL xL xx yLxyL xL yxy 思思路路 对对称称正正定定矩矩阵阵的的分分解解。112c,=+ababxxaaxaxax2 2和和是是两两个个向向量量范范数数和和是是两两个个正正实实数数

15、证证明明是是向向量量范范数数。22/51例例7 7. .max1222min()cond( )| |()TTA AAAAA A 2max|()TAA A 1,TTA AA A AA 和和特特征征值值互互为为倒倒数数和和特特征征值值相相同同。1-1-12maxmaxmin|()()=1/()TTTAA AA AA A 23/51例例8 8. .2,( )AAA 如如果果矩矩阵阵 对对称称 则则2max2max2minmin,()( )() |( )| ,cond( )( )()TTTTTTTiiTAACDCA AACDC CDCCDDCA AAA AAAAA A 对对称称 则则病因病因是条件数大

16、是条件数大, ,病症病症是什么呢是什么呢? ?,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 ,当当 jk 和和 ik+1时时 1

17、1kkjkrrjrkjuam 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 nnnnnnnummuumuuuA

18、1,1222211121127/51更新顺序更新顺序: 先先行行后后列列列列除除行行不除不除旧元素减去旧元素减去所在所在行行和和列列前前k-1分量点乘的加和分量点乘的加和Doolittle分解：分解：更新顺序更新顺序: 先先列列后后行行行行除除列列不除不除旧元素减去旧元素减去所在所在行行和和列列前前k-1分量点乘的加和分量点乘的加和Crout分解：分解：28/51 求矩阵的求矩阵的Doolittle分解分解1212253222351323A 1212253222351323 1212211222351123 1212211222331103 29/51三对角矩阵分解三对角矩阵分解 532422

19、3112 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的特征值全为正实数的特征值全为正实数。help chol对称正定矩阵对称正定矩阵: :34/511) 序列收敛序列收敛2) 迭代矩阵谱半径小于迭代矩阵谱半径小于13)

21、 迭代矩阵特征值全小于迭代矩阵特征值全小于1 4) 迭代矩阵范数小于迭代矩阵范数小于15) 反证法反证法迭代法收敛证明思路迭代法收敛证明思路:| 0BxxIB = =或或35/51例例1010. .设设A是一个可逆矩阵是一个可逆矩阵, 矩阵序列满足矩阵序列满足 Xk+1=Xk(2I A Xk )，（，（k =0, ,1, ,2, ,） 则当则当 时时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)

22、22 = 20()kIAX20lim()0kkIAX 1limkkXA 36/51例例1111. .1122()20,JacobiGSijAaa aAx b 设设是是 阶阶矩矩阵阵且且试试证证明明求求解解方方程程组组= = 的的方方法法和和方方法法同同时时收收敛敛或或发发散散。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, )产生的矩阵序列产生的矩阵序列 Xk 收敛到矩阵收敛到矩阵A-1；(3)对矩阵序列对矩阵序列 Xk , 有误差估计式有误差估计式|11|11kkkXXqAX 例例1212. .设设A是是n阶可逆矩阵阶可逆矩阵,有有A的一个近似逆的一个近似逆B,令令 R=I AB。如果如果 | R | q 1,| |1,kkkxBxfxBBxxBxfxx 设设有有唯唯一一解解若若矩矩阵阵的的谱谱半半径径（ ) )但但有有一一个个特特征征值值求求证证存存在在初初始始向向量量使使得得迭迭代代格格式式产产生生的的序序列列收收敛敛于于 。例

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 设设 为为对对称称正正定定矩矩阵阵 证证明明迭迭代代格格式式其其中中则则对对于于任任意意初初始始向向量量收收敛敛到到= = 的的解解。例例16

25、.16.思路思路: 43/51112233,1 11Jacobiaaaxbaaxbaaxb 研研究究 满满足足什什么么条条件件时时 求求解解线线性性方方程程组组的的迭迭代代方方法法收收敛敛。例例17.17.思路思路: -1/2a1/2收敛收敛, -1/2a1时系数矩阵正定。时系数矩阵正定。 44/51例例18.18.11=C,nB CDD 对对称称矩矩阵阵11=C,kkkkknBCDD 对对称称矩矩阵阵 | |1| |,B 收收敛敛于于零零的的充充分分必必要要条条件件是是。进进一一步步地地如如果果越越小小 则则收收敛敛速速度度越越快快。45/51例例18.18.231111,1 ,1mm mJ

26、JJ 3112211112112211112211, mkkkkkkkkkkkkkkkkkkmk mkkkkkmk mkkkkkkkm mCCCJJCCCCCCJC 进进一一步步有有 23,| |1kkkmJJJ 收收敛敛于于零零的的充充分分必必要要条条件件是是。| |1B 收收敛敛于于零零矩矩阵阵的的充充分分必必要要条条件件是是。46/51例例18.18.121121,1 ,iiiiriirnnkkkkkkrJJJJnnJJJBP J P JJ 其其中中1=,JordanB P JP JB 对对于于一一般般矩矩阵阵是是 的的标标准准形形。lim=0lim=0lim=0kkkikkkBJJ故故47/51参考参考: :Writting Fast Matlab Codes1. .中小规模线性方程组中小规模线性方程组x = Ab; % Solves A*x = b2.(.(超超) )大规模线性方程组大规模线性方程组(Preconditioned cg)48/51作业作业题目题目1: 从理论角度从理论角度(复杂度和收敛性复杂度和收敛性)比较各比较各 种方法