清华高等数值分析往年考题包含2011年2012年考题照片

1、高等数值分析历年考题高值试题（李津老师）一，填空题 （4*7）1. 求矩阵的二范数，条件数。矩阵A=0,2;3,02. 把一个矩阵SVD,然后求个广义逆算个结果3. CG法，求余量的方向二、简答1. 三类矩阵哪些能被 Householder 变换变换出来2. GMRES的性质，每次余量是否变小3. 本质上是证明牛顿迭代的超线性收敛三、计算1. strum 算法的使用，比书上习题还简单2. Arnoldi 过程中断时的若干性质证明3. 第八章 Galerkin 方法的求解，边值条件改成一阶导数。定理 8.4.3 的变形。答疑的时候一定要去听听， 李老师在讲牛顿迭代的超线性收敛和 Galerkin

2、 方法时眉飞色舞， 果断 就考了。2012 高等数值分析 （贾仲孝老师）首先庆贺自己研究生的第一门也是最后一门考试顺利结束，哦也，再也没有考试啦！贾哥延续了考题沿用往年题的优良传统，详情见拍照，全部是历年考题，基本上是按着去年 考题来的，只有一道题第二个小问号改了一下而已。1. 用 householder 和 givens 变换做 QR 分解，由于矩阵特殊，非常简单。如果拿不准，不妨用GS方法做一遍验证一下，因为不同的QR分解只是符号有差异而已，GS还是比householder简单很多的。2.1证明rayleigh商最大值等于 A的最大特征值，将 x拆成各个特征向量之和就容易证。2.2 幂法求

3、一个特征值，一步收敛3. 第三次作业第三题，也是去年的原题，基本上都不用想，直接默写就行了4.1去年考题。注意到 Ak*R（ k-1）=R（ k-1） *A（ k-1）,那么就类似冒泡算法把Ak移到最右边变成一个 A4.2有点小恶心，去年这个问号问的是Qk第一列是特征向量 x1,只需要两边同乘以e1即可，但今年问的是最后一行是特征向量xn，顿时就不会证了，当时打眼一看觉得貌似A也不能说明是可逆的，就没往反幂法这个方向去，但是后来想想其实最多也就是lamdaN=0 ，其他不为0，也许可以分情况讨论下？后来有同学说假设可逆用了反幂法也没得到什么结论.不知道.还好就是 5 分，丢了就丢了吧5 考过多

4、年的经典背诵题，默写 rayleigh ritz 方法和贾哥定理，以及 Arnolid 和精化 Arnolid 算法6.1 lagrange 差值，三个点而已6.2 最佳平方逼近，解一个 2*2 的法方程组就完事2003高等数值分析 (贾仲孝 )1 证明不动点定理(存在唯一性)2 第三章习题 83 共扼剃度法 ak 的选取，以及正交的证明4 梯形法(迭代，相容，稳定区间)具体为 dy/dt + y=0 y(0)=1?5 求正交阵使 H* ( 2/3 1/3 2/3 )=e1 求 I 2ww ( w 的二范数为 1 )的特征值已知H，问计算Ha的运算量6 摄动原理 误差分析7 拉各朗日插值(这里

5、实际考的是代数基本定理的应用)8 忘了2005 高等数值考题(贾哥版)下面是 B 卷内容，总共六道题1. 用Give ns变换QR分解一个3*2的矩阵，并求解一个最小二乘2. 证明：对于 Minres 和 Gmres(1) A 有 k 个特征值时，至多 k 步收敛(2) A有n个不同的特征值，r0由k个属于不同特征值的特征向量构成时，k步收敛(这里没有多”)3. A 为 m*n 矩阵， mn(1) 用完全QR分解，不完全 QR分解以及SVD表示A+用完全QR分解以及SVD得到min|Ax -b|问题的xls和rls，并加以证明4.(1) 证明 Arnoldi 过程中断时找到准确解(2) 证明

6、Arnoldi 过程中断时不会发生方法中断当A为正定对称阵时，证明Lanczos方法不会发生方法中断(即WAV非奇异，讲义上有的)4. A=uv。u,v均为向量， A的秩为1(1) 证明 uv 为 A 的特征值(2) A 还有哪些其他的特征值？(答案：0)(3) 用幂法求 A 的主特征值，几步可收敛？为什么？(答案： 1 步)5. 关于CG的问题(1)类似于推导alpha(k)，直接用书本上的方法就可以了当A=I-BB时，其中B的秩为p,用CG求解Ax=b问题，最多几步可收敛？为什么？(答案： min(p+1,n) )感觉把讲义上的东东都看懂了就没问题了，贾哥还是很好的人哪A_Ad2005 高

7、等数值分析试题(陆金甫老师)1. A=1,3;1,3;1,1;1,1 , b=记不清楚了，欢迎补充，反正4X啲:)1 )用 householder 变换完成 QR 分解2) 用 QR 分解的结果，求 |b -Ax| 的最小二乘解2. A=6,3;3,2 b=0; -11) 用CG法解这个方程2) 说了一堆CG里面关于A共轭的东西之后，让你证名CG法理论上至多需要 n步就可以得到精确解(有提示，先证明 r(k) 正交)3. A=1 0 0 01 1 0 00 1 1 00 0 1 1,v1=1,0,0,0, 完成 Arnoldi 过程4. F(x )记不清了，不过可以从 G(x )推岀来。G(x

8、)= 0.25(x2-0.1 X eAx1+1)0.25(x1 -0.125 X x1A2)D=x1,x2|0=x1,x2u2 问两点的稳定情况。6) 对称正定阵的问题可以一般化讨论 3 对角即可。判断7) 特征值问题条件数和解方程条件数是一回事。(就是去年那个题目 )判断8) 多重网格xxx。粗网络平滑高频，细网络平滑低频。判断9) 线性规划内点问题是多项式问题。任何线性规划问题都能数值求解。判断1 0)去年那个正则点题目计算题 1 0(建议现在大脑里装个 matlab)某该死的矩阵 lanczos3q0=(1 2 2)A=4 1 11 3 11 1 2计算题 15奇异值分解 求广义逆秩A=

9、4 1 ;1 1;1 2计算题 15 去年那个迭代题目，验证 11 是解，求牛顿迭代式以及 x1 x0=0.5 0.5 另外给了一个迭代式，同样初值求 x1证明题 10(u,v)=(v,f) 以及一堆 0 的边界条件u=f以及一堆 0 的边界条件证明上述两个问题等价证明题 10引理 3.3.22006 高等数值分析(白峰杉)填空4 X 101. A=(1,0.5;0.5,1), 求 2 范数和条件数。2. 还是这个A,求QR分解。38.判断对错，涉及到GUASS消去，线性规划，多重网格，求特征值时的条件数cond(A),赋范空间,还有一个忘了。 。9. du/dt=(u -(u+)(u-(u-

10、)，则(u+)是 (稳定/不稳定)的稳态解，(u-)是 (稳定/不稳定)的稳态解。10. f(x)=f(x1,x2,x3)=. (忘了)，求临界点、临界值、正则点、正则值。计算证明 15 X2 10 X31. 对称阵 A=(4,1,1;1,3,1;1,1,2) ，取 3q1=(1,2,2) ，用 Lanczos 过程将其三对角化。2. f(x)=(f1(x),f2(x)=0 。(1 )验证 x*=(1,1) 是方程的解。(2)写出 Newton 法迭代式， x0=(0.5,0.5) ，求 x1。( 3)给了一个迭代式fai(x)=. ，证明它在 x* 有局部收敛性，并做一步迭代，计算 x1 。

11、3. A=(4,1;1,1;1,2) ，求 SVD， A 的广义逆和 A 的秩。4. zm是Krylov子空间Km的向量，Lm=AKm。证明：(rO-Azm,v)，任取 v 属于 Lm等价于 |r0 -Azm|=|r0-Az| ，z 属于 Km。5. 证明：求解方程： d4u/dx4=f ， u(0)=u(1)=u(0)=u(1)=0等价于在空间L中找到这样的u满足：(u,v)=(f,v)，任取v属于L。L 主要的性质就是 v(0)=v(1)=v(0)=v(1)=0 。)2007高等数值分析 (贾仲孝)1.(1) f ( x_0 ) = a， f ( x_1 ) = b， f ( x_2 )

12、= c， x_k = ( k - 1 )/h, k = 0,1,2, 求 f ( x ) 的拉格朗日差值多 项式。 求f(x) = |x|在-1 , 1上的最小平方逼近，基函数取1, xA22.(1)若A可对角化，则当 A仅有k个不同特征值时，证明对于A x = b MINRES方法与GMRES方法至多 k 步找到精确解。若A的特征值各不相同，对A x = b而言，取x_0 = 0，b可以表示成由 k个特征向量，证明MINRES方法与 GMRES方法k步找到准确解。3.A = | 0 3 4 | 3 0 0 | 4 0 1 |(1) 用 Givens 变换实现 A 的相思变换使得 A 化成对称

13、三对角矩阵T ;(2) 用 Householder 变换实现 A 的 QR 分解。4.取G = -1 1 , x = g(x) = (xA2 - 1)/3 ,求证上述变换在 G内有唯一不动点。5.取x_k+1 = x_k + a_k d_k，其中 d_k为迭代方向(1) 若选取 a_k 使得 | r_k+1 | = min | b - A x_k |，给岀 a_k 的算式；(2) 求证 r_k+1 与 A d_k 垂直；若取d_k = r_k，证明对于任意的 x_0，则上述方法均收敛。6.取A = u v，其中 u与v不正交。(1) 证明 v u 为 A 特征值；(2) 证明 A 的其余特征值

14、均为 0；(3) 若对上述 A 使用幂法，则迭代几步之后收敛，收敛向量是什么？2007高等数值分析 (白峰杉)一、填空 13题每题 6分， 46题每题 3分1、A=1 1/4求| A求解Ax= b问题中的条件数 cond2 (A)1/4 1;2、求A的奇异值分解3、求解特征值问题 Ax=入X可题中的条件数4 求 A 的广义逆 A5 用 A 进行 jabobi 松弛迭代 迭代矩阵为6如果求方程xn+a1xAn-1+ an=O的根等价于求一个矩阵的特征值，这个矩阵是？二、判断对错 并说明理由 每题 3 分1、2、 列主元高斯消去法与LU 方法是等价的，求解大型稀疏矩阵的列主元消去法，由于不必每次都

15、选取最大的主元，因此与LU 方法不等价3、guass 消去解方程时，如果增长因子很大，结果一定不可靠4、任何实矩阵的问题，不失一般性，都可以只研究上三角矩阵5、多元代数方程组的解由方程组唯一确定，而且复杂度是多项式的，易于求解6、粗网格解决的是高频分量，细网格是低频7、任意空间，如果可以定义内积，就一定是赋范空间三、A = 4 2 1 3*q1=1 求前两个ritz值2 3 1 21 1 2; 2四、方程 8x1-x1A2+x2-8=08x2-x2A2+x1 -8=0I 、证明( 1 ， 1)是方程的解2、 x0=( 0， 0),newton 迭代，求 x13，对于函数 x11/8*x1A2+

16、1/8*x2 -1x2- 1/8*x2A2+1/8*x1 -1(1) 证明函数在x*处局部收敛(2) 如果 0x1,x2lamda_2=.=lamda_n 陈述幂法，并证明 sin(v1,x1)=O(dieta),p为第k步幕法得到的特征值，证明|p -lamda|=O(dietaAk),就是说精度是 dieta的k次方量级。2. ) 利用幂法求下列矩阵的主特征值和特征向量A= 1 1 1; 1 1 1; 1 1 1一步收敛，特征值是 3，特征向量是 1/sqrt(3)* 1 1 12009高等数值分析 (白峰杉老师 )总体来说，今年的题目不难，很多难的都没考。 但是白老师今年出来 3 道多选

17、题。同时很多东西光靠课件和教材是找不到，听课 很重要一、填空( 3*6=18 )A=2,1;1,2;(1)求|A|1 ;求多项式方程组Ax=b的Cond1(A);已知 QR 分解中的 Q=-0.8944 -0.4472;-0.4472 0.8944， 求 R=?若记A(0)=A，用QR迭代求特征值，问 A(1)=?(3) 求 A 的特征值问题条件数(4) 广义逆矩阵 A+=?二、判断题(请说明理由，或者改正)(3*4=12)1 、 Newton 法丢非线性方程组，只要初值充分接近解，那么一定收敛；2、如果一个多项式的条件数很大，那么这个问题有可能很不好求解；3、任意线性椭圆微分方程都可以4、

18、由于有限维空间的范数相互等价，所以min|Ax -b|v 都相同。三、多选题( 3*10=30 )1 、多项式 Pn(x)=xAn+a1xA(n -1)+ +a，0 以下说法正确的是：A、多项式的实值根的个数(算重根)由方程的次数和系数决定；B、用Newt on法求多项式的解一定收敛；C、D、E、多元多项式的根只有方程的阶数决定。2、假设有 n 的观察变量，总共有 m 个采样值。形成矩阵 A( m*n )。以下说法正确的是：A、如果矩阵的奇异值维 r,其秩为r；B、变量的协方差矩阵为 m阶；C、主成分分析的中心化指的是求每一行的平均值并减去该值；D、使用PCA实际上使用线性方法对数据进行降维和

19、去噪；E、当矩阵很大的时候，使用奇异值分解算法稳定；3、线性规划问题。以下说法正确的是：A、单纯性问题如果有最优解，一定在顶点处求到；B、单纯性算法可以有效求解大部分问题；C、单纯性经典意义上的复杂度是指数的；D、内点法的复杂度指示多项式的；E、？ 三、计算题1、Househoulder 变化(对教材的做法有一点改动)H2 2 1 0=(I -2vv/vv)2 2 1 0=a,0,0,0;(1)a=？ v=？(2)证明 Householder 矩阵对称、正交；2、 考虑一维 poison过程-(正三角)u=f。f=6x。区间在0,1； u(0)=0;u(1)=1;采用中心差分迭代格式，步长h=

20、0.25，离散化方程；(2)考虑线性方程组 Ax=b， A 对称正定。说明并证明极小化原理；3、非线性方程组 F(x)=0;(1) 用 Newton 法求解，写出 G(x)；(2) 当 F(x)=Ax-b 时，求出 G(x);(3) 写出 G(x*) 的谱半径，从而证明收敛。2010 高等数值分析 (贾哥)今年贾哥很厚道啊，几乎拿得是 06 年的卷子。 。我就不抄写了，和以前的题是一样的 按着 pretest 上的年号 -题号看就可以了。06-306-206-4 06-507-106-62010高等数值分析 （白峰杉 ）一、填空 （18 ，每空 3 分）：1. A4,3;3,4 求二范数，和二

21、范数的特征值的条件数2. 将 A 进行 QR 分解，求 household 变换矩阵 H= ；R=3. 求A的奇异值分解的三个矩阵U= ;S= ;V=.二、判断并写理由 /更正 （12,每题 3 分）：1. 解非线性方程的牛顿法是迭代法但不是不动点迭代2. 多重网格的粗网格是对高频分量的改善，。3. QR 分解求特征值，迭代得到的矩阵都是上hessenberg 矩阵4. 线性规划问题的优化。 。，平均意义下的计算复杂度是指数型的三、多项选择题 （30,每题 10把,你认为错误的写上理由）1. 多元多项式方程组P（X）=（p1（x）,p2（x）,.,pm（x）=0 , pk（x）的多项式次数为

22、dk,k=1,2,.,mA. 方程组解的个数上界满足d1+d2+.+d3B. m=1 时结论 A 符合代数基本定理,当然满足C.C. m=1 时,不论扰动加在何项,解的个数都能由代数基本定理确定。E理论上同伦算法可以得到多元方程组的全部解。但在实际上通常不可行，是因为计算每一条同 伦曲线的解都是很复杂。2.SVD分解和NMF分解A. SVD和NMF都是降维逼近的有效方法B. NMF 分解结果是由两个非负矩阵相乘C. SVD和 NMF都能降低维度和消解噪声。D. 个N维空间的一组正交基，不可能都是非负的。E.3. 关于积和式计算复杂度（顺序可能不对）A 积和式的计算有多项式型的计算复杂度的解法，

23、只是还没有找到B基于laplace展开的，积和式和行列式计算复杂度都是指数的C3-regular 矩阵指的是，矩阵的每一行元素的和与每一列元素的和都是3D 双元素的 Laplace 展开，是针对特殊形式的稀疏矩阵的E基于B,说明计算积和式和行列式的计算具有相同的计算复杂度。四、解答题（ 40）1.（ 12）非线性特征值问题，设u=（x,y）,则2x+y+ 入F（x,y,入）=F（u,入）=y+3 入x写岀Fu(u, 以及 F入(u,并写岀(x,y,入)=(0,时时的值(2) 写出临界点集合，临界值集合，正则点集合，正则值集合(3) 此方程组的解是否有分岔点？若有，可能在那些地方？2. (16)

24、微分方程的边界问题，-汕=1 x 0,1,u(0)=u(1)=0，证明它等价于寻找 u W，使得(u,v)=(f,v) 其中 W = v|v C(0,1), v分片连续，v(0) = v=0。3. (12)特征值分离证明，若对称实矩阵A的特征值 入1W入2 .矩年A巾勺主子矩阵的特征值卩1 卩2W .-1，证明！入1 卩1 w入2卩-1步卩-1 Hn n2011 高等数值分析(贾仲孝)刚考完回来。发一下，攒人品。 今年贾哥没有往年厚道，只有贾氏定理完全是原题。第一题在原来的 MINRES和GMRES基础上，增加了 Lanczos和Arnodi，不会证 第二题，矩阵是新的，考查 Gram-Schmidt 和 Householder 实现 QR 分解。第三题是作业题，可是多数同学都没复习到(往年不考作业，今年变了风格)第四题，好像是考查 QR 求解特征值的题目，时间不够，根本没细读题目。靠，这种科目岀没见 过的证明题，没法做。第五题，贾氏定理第六题， lagrange 差值的证明和最佳平方逼近求解。 具体题目吧，见附件的照片(手机像素不够，不太清晰，不过放大后仔细看效果还凑合吧)。以后考试，交卷之前最好都拍下来，方便学弟