数值分析典型例题与习题最新版本

三、四章内容提要典型例题分析,数值分析典型例题II,化难为易,化繁为简,化繁为简,初等行变换不改变方程组的解,1.交换矩阵的第i行与第j行的位置,2.以非零数k乘以矩阵的第i行的每个元素,3.把矩阵的第i行的每个元素的k倍加到第j行的对应元素上去,A(n1)=Fn-1Fn-2F1A,其中Fk为Frobenius矩阵。,A=F1-1F2-1Fn-1-1A(n1),直接方法:高斯消元法,LU,高斯消元法本质是矩阵的分解。,矩阵分解(Top10Algorithms),(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)非负矩阵分解LearningthePartsofObjectsbyNon-negativeMatrixFactorization,Nature,1999,Demo1,I=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,),迭代法思想:,Iterate:Tosayordoagainoragainandagain,迭代背后的思想是一种与传统思维模式截然不同的方式,传统思维方式往往希望一遍做好,一次成功;但是迭代开发意味着反复地做,不断地根据反馈进行调整。,迭代格式构造,收敛条件(局部vs全局),中止准则,加速(松弛思想),Aitken加速方法超松弛加速方法,共轭梯度法的关键是构造一组两两共轭的方向(第k步迭代生成共轭方向张成k维子空间)。巧妙的是共轭方向可以由上次搜索方向和当前的梯度方向组合产生。,现代迭代方法(Top10Algorithms),最速下降法思想简单,但收敛速度慢。本质上因为负梯度方向函数下降快是局部性质。,复杂性:,高斯消元法共用乘法和除法次数为n3/3+n2-n/3,常用记号O表示是多少阶的,则O(n3/3)。,注释2:复杂性对估计求解大型方程组所需的时间有用。例如在一台特定的计算机上求解n=500个方程的方程组所需的时间我们可以通过求解一个n=50个方程的方程组得到一个很好的猜测,即对用掉的时间按比例放大1000倍。,注释1:按O的记法,把n的不同次幂相加的结果仅保留了最高次幂,因为最高次幂决定了当n趋近无穷时的极限形态。换而言之,对于大的n,低阶项对算法的执行时间的估计没有太大影响,仅需要近似估计执行时间时可以忽略不计。,常用的范数:,Hilbert矩阵条件数:fori=1:10c(i)=cond(hilb(i),2);%vander(1:i)end,plot(1:10,c),范数(全局),问题的好与坏,算法的快与慢,|X(k+1)X*|B|X(k)X*|,范数的威力和魅力:,ekT=00100,=ImkekT,Fk1=I+mkekT,(k=1,2,n1),F1-1F2-1Fn-1-1=,Fk1Fj1=I+mkekT+mjejTkj,F1-1F2-1Fn-1-1=I+m1e1T+mn-1en-1T,例1.,ekTmj=0,kj,例2.设A为对称矩阵。高斯消元法一步后,A约化为,证明B也是对称矩阵。,约化主元不为零的判断,定理3.1约化主元的充分必要条件是矩阵A各阶顺序主子式不等于零。即,例4.严格对角占优矩阵的约化主元ak,k(k-1)0(k=1,n)。,例3.严格主对角占优矩阵一定是非奇异的。,严格对角占优矩阵:高斯消元法中约化主元不等于零,Jacobi方法,GS方法和SOR方法收敛。,思考:若A是严格对角占优矩阵,当0w=1时,SOR方法收敛。,例5.Ax=b,其中A对称正定,问解此方程的Jacobi迭代法是否一定收敛？,对称正定矩阵:直接法高斯消元法中约化主元大于零,迭代法GS方法,SOR方法,最速下降方法和共轭梯度法收敛。,例6.,例7.,例8.,病因是条件数大,病症是什么呢?,例9.矩阵的Doolittle分解,A=LU,L为单位下三角矩阵,U为上三角矩阵。,a11=u11,a1n=u1n,a21=m21u11,an1=mn1u11,对A的元素aij,当jk和ik+1时,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)/u22,矩阵L和矩阵U的元素计算公式,计算次序,更新顺序:先行后列列除行不除旧元素减去所在行和列前k-1分量点乘的加和,Doolittle分解：,更新顺序:先列后行行除列不除旧元素减去所在行和列前k-1分量点乘的加和,Crout分解：,求矩阵的Doolittle分解,三对角矩阵分解,步骤I:,三对角矩阵分解A=LU,(k=2,3,n),下三角方程组LY=f,步骤II:,上三角方程组UX=Y,步骤III:,求解三对角方程组的追赶法,对称正定矩阵的Cholesky分解,(1)对于非零向量,xTAx总是正的;(2)A的顺序主子式全大于零;(3)A的特征值全为正实数。helpchol,对称正定矩阵:,1)序列收敛2)迭代矩阵谱半径小于13)迭代矩阵特征值全小于14)迭代矩阵范数小于15)反证法,迭代法收敛证明思路:,例10.设A是一个可逆矩阵,矩阵序列满足Xk+1=Xk(2IAXk)，（k=0,1,2,）则当时,证明：由Xk+1=Xk(2IAXk)，得IAXk+1=IAXk(2IAXk)=(IAXk)2于是IAXk=(IAXk-1)2=(IAXk-2)22=,例11.,思路:,(1)A1=B(I+R+R2+)；(2)任意给定n阶矩阵X0,由迭代格式Xk+1=XkR+B(k=0,1,2,)产生的矩阵序列Xk收敛到矩阵A-1；(3)对矩阵序列Xk,有误差估计式,例12.设A是n阶可逆矩阵,有A的一个近似逆B,令R=IAB。如果|R|q1,试证明,收敛的w取值范围。,例13.方程组Ax=b,其中A是对称正定阵,讨论迭代格式,思路:,例14.,思路:,续例14.,思路:,例15.,思路:,定理4.1对任意的f和任意的初始向量X(0)迭代法X(k+1)=BX(k)+f收敛的充分必要条件是,例16.,思路:,例17.,思路:-1/2a1/2收敛,-1/2a1时系数矩阵正定。,例18.,例18.,例18.,参考:WrittingFastMatlabCodes,1.中小规模线性方程组x=Ab;%SolvesA*x=b,2.(超)大规模线性方程组(Preconditionedcg),作业,题目1:从理论角度(复杂度和收敛性)比较各种方法的优劣。,题目2:从数值角度比较各种方法的性能(公平),题目3:科研或生活中遇到的线性方程组？,提示:,参考代码:Matlab代码IterativeSolver,1.如何生成方程组A=gallery(poisson,n);b=ones(size(A,1),1);x0=zeros(size(A,1),1);,2.如何生成方程组矩阵市场:/MatrixMarket/UFSparseMatrixCollection:/research/sparse/matrices/,提示:,3.更具挑战和趣味的例子图像编辑参考:Matlab代码Possion图像复原参考:DeblurringImages:Matrices,Spectra,andFilteringGooglePageRank参考:NumericalComputingwithMATLAB数据挖掘和模式识别参考:MatrixMethodsinDataMiningandPatternRecognition高光谱图像解混参考:SparseUnmixingofHyperspec