清华大学贾仲孝老师 高等数值分析 复习资料 2013.1.7 v1.0

1/14清华大学贾仲孝老师高等数值分析复习资料2013.1.7v1.0【仅供参考】精仪系曹哲制作备注：1.本资料为2008-2012五年题目与答案，与2013的题目。前者根据十个类型划分。2.波浪线为没有答案。一般没有答案的是因为已经列举与答案高度相似的例子。删除线为2013年不考。3.部分答案使用与题目类似的例题进行解答。黑底色部分为从某幻灯片截取，并不代表是重点。4.本答案仅供参考，不保证完全正确。如有瑕疵，那是必须滴。1.(2012.1)Housholder和Givens变换对一个3*3的矩阵做QR分解，按步骤做。A对称。(2009.3)A为三阶对称矩阵(1)用Givens正交相似变换，变为对称三角矩阵。(2)用Householder正交化方法进行QR分解。(2008.3)令A=(034300401)分别用Givens变换和Householder变换计算A的QR分解。(2011.1)用Givens变换QR分解一个3*2矩阵，并求解最小二乘。A=111102B=112(2010.4)采用Givens算法对A进行QR分解，并利用得到的分解，进行最小二乘运算min||Ax-b||A=1101122B=111(2006)用Givens变换QR分解一个3*2矩阵，并求解最小二乘。A=111102B=111Householder,112240130A2/14(2006)1)21aaA1121a111111CSSCG211C211S00220221111aGaGAG022)1(1a122222CSSCG222C222S00101212AGG001012)(112GGA∵G2、G1是正交矩阵2121212121210212112121212121212121121TTGGQA=QR3/1421212121212102121Q001012R可以验证QQT=I，且R是上三角阵∴QR分解完成1)用HouseHolder求解的另解A=[a1a2]1121a0021x222)1,1,22(11111Tyaya42242221422422212121222111TIH210210121AH2121)2(2a012x22)22,222(2)2(22)2(21Tyaya2212222222222'2TIH221222222211'22HH4/1400101212AHH2121212121210212121HHQ001012R2.(2012.2)(1).证Rayleigh商收敛于主特征值，参考讲义。(2).幂法算主特征值对应的主特征向量，按步骤做，一般的初值都是一步收敛。(2011.5)A=uv’，u、v均为向量，A的秩为1.(1)证明u’v为A的特征值(2)A还有哪些其他的特征值。答案：0(3)用幂法求A的主特征值，几步可以收敛？为什么？答案：1步(2013.3)(2009.5)(1)叙述求特征值的幂法。证明：当特征值向量方向的误差sin(准确特征向量和近似特征向量)=ek的时候，相应特征值的误差为0(ek2)(2)用幂法求矩阵[111111111]的主特征值和主特征向量。这道题是05年秩为1的问题的变形，其秩也为1，看出他只有0和u’v=3两个特征值。3是主特征值，对应的特征向量是1√3*[111]。所以可以一开始就把其初始向量选为和[111]相同方向的向量，一步就发现收敛。(2008.6)令A=(−3103−2301−3)取初始向量𝑣0=1√3(1,1,1)𝑇，用幂法准确计算A的主特征值λ和主特征向量。(2012.2)(1))()(121kkV)()(121kkV)(1210kkxaVVVAVVxRHH)()]([)]([12101210kHkHxaAxaAVV110xaAV120110101101210)()]([axaxaxaxaAVVHHkH5/141)(VVAVVxRHH(2011.5)(1)λ=v’u(2)λ1=v’uλ2=λn=0(3)一步收敛1)证明：Au=uv’u=u(v’u)=(v’u)u(即)(uvuuuvAuuvATTT)故(v’u,u)为特征对2)解：因为A的秩为1，所以λ=v′u和n-1个03)解：因为幂法收敛速度𝜆2𝜆1=0𝑣𝑢=0所以一步收敛(2009.5)(1)(2008.6)210021012A例：用幂法求矩阵的按模最大的特征值和相应的特征向量。(0)3(0,0,1),10.Tv取(0)(0)(0,0,1),Tuv解：(1)(0)(0,1,2),2,TvAu6/14(2008.6)𝑣0=1√3(1,1,1)𝑇，P0=v0HAv0|Av0-p0v0|较大v1=Av0=1√3(−2,4,−2)𝑇𝑣1=𝑣1‖𝑣1‖=1√6(−12−1)𝑇𝜌1=𝑣1𝐻𝐴𝑣1=−5|𝐴𝑣1−𝜌1𝑣1|=|[5−105]1√6−1√6[5−1051]|=0收敛完全一回事儿的另一种写法：32343200AVu616261111uuv5111AvvT0111vAv收敛(1)(1)(0,0.5,1),Tvu(2)(1)(0.5,2,2.5),2.5,TvAu(8)(7)(2.7650948,2.9981848,2.9990924)vAu2.9990924(8)(9)(8)(0.9219772,0.9996973,1)(2.8436517,2.9993946,2.9996973)uvAu32.99969732.99909240.000604910由12.9996973.故相应特征向量为(2.8436517,2.9993946,2.9996973)x。1233,2,1A事实上，的特征值，11-1,1T与对应的特征向量为（，）。212.3此例中比值为7/143.(2012.3)8/144.(2012.5)(2010.6)(1)叙述经典/精化的Rayleigh-Ritz的主要收敛结论(2)描述经典/精化的Arnoldi方法过程(2008.4)描述计算计算部分特征值和特征向量的Arnoldi方法和精化Arnoldi方法。9/14讲义P93955.(2012.6)(2008.1)(1)使用插值点x0=2，x1=2.5，x2=4，求f(x)=1/x的二次Lagrange插值多项式。f(3)近似值是多少？实际误差是多少？Ans:1/60(2013.6)(1)设f(x)=√1+𝑥，令x0=0，x1=0.6，x2=0.9，写出二项差值多项式，计算f(0.44)的近似值，并计算其与准确值的误差.(2009.1)(1)f(x)=√𝑥,x0=0,x1=0.6,x2=0.9，写出二项差值多项式，计算f(0.44)的近似值，并计算其与准确值的误差。(2010.3)(1)f(x0)=a,f(x1)=b,f(xc)=c,x=(1-k)/h,k-1,2,3;采用拉格朗日插值法，得到二次插值函数。(2012.6)(2008.1)(1)另解：Δ=|𝐿3(𝑥)−𝑓(3)|=11206.(2011.2)(2010.2,2009.2)证明：对于Minres和Gmres(1)A有k个特征值时，至多k步收敛(2)A有n个不同的特征值，r0由k个属于不同特征值的特征向量构成时，k步收敛(1)当A有K个不同的特征值1XXAkiiiniiiydxcr110iiiyAyji10/140id，K中断0id，收敛小于等于K-1(2)ro可表示为kiiixcr10，0ic第m步，mmr},...,{11211kkioxxspanxxArmkmxxspankmxxspanmkkkmdim,},...,{,},...,{11kmmkmkkkkkmmkmcccccccccxxrAArr112222211111110100],...[],...,,[kmmKmkm,dim,kkkyAVrr00,kkkrAr若此题问CG、Lanczos、Arnoldi，则最后一步改为0,kkkrr7.(2011.3)A为m*n矩阵，mn(1)用完全QR分解，不完全QR分解以及SVD表示A+(2)用完全QR分解以及SVD得到min||Ax-b||问题的xls和hrs，并证明8.(2011.4,2010.1)(2008.2)对于线性方程组Ax=b，给定初值x0，r0=b-Ax0，取v1=r0/||r0||。在准确运算下，证明：(1)如果从v1开始的Arnoldi过程在第m步中断，则Arnoldi方法计算出的近似解xm为准确解。(2)如果Arnoldi方法中断，则Arnoldi过程必然不会中断。(3)如果A=AT对称正定，则Lanczos方法不中断。即W’AV非奇异。(讲义有)(2011.4,2010.1)(2008.2)1)kTkkkTkkkkkkkkkkkyeyeqTerQyAQAxbyQxAbAxbr11000)()(方法中断，0k2)假设过程中断，0kkkkTQAQ∴Tk特征值全是A的，11/14∴Tk非奇异，)()(mHA与方法中断，Hm奇异不符∴得证。3)n步，)()(ATnTk、Tk+1的特征值时交错的假设Tm奇异，0)(mmT0)()(11mmmmTT0)(nnT0)(An，与A正定矛盾，得证。9.(2013.2)(2011.6)(2010.5)(2008.5)(1)令ϕ(x)=12𝑥𝑇𝐴𝑥−𝑥𝑇𝑏，其中，A对称正定，考虑φ(α)=ϕ(𝑥𝑘+𝛼𝑝𝑘)，其中pk是搜索方向，xk是x=A-1b的当前近似值。φ(α)对什么值α=α𝑘达到最小？证明当𝑥𝑘+1=𝑥𝑘+𝛼𝑘𝑝𝑘时，𝑏−𝐴𝑥𝑘−1⊥𝑝𝑘。(2)在准确运算下，证明求解n阶非奇异线性方程组的CG、Lanczos、MINERS、Arnoldi，CMres方法至多n步一定找到精确解。(2011.6)(2)当A=I-BB’时，其中B的秩为p，用CG求解Ax=b的问题，最多几步可以收敛，为什么？(2009.4)迭代格式xk+1=xk+alpha*dk,其中dk为搜索方向。（1）求步长alpha，使得||x*-xk+1||极小（2）给出另一个种迭代格式，分析收敛性(讲义P18下方~P19上方)(2013.2)(2013.6)(2011.6)(2010.5)(20