清华大学高等数值分析(李津)所有作业答案合集.docx

1、“高等数值分析”第一次书面作业20130917题目求证：在矩阵的LU分解中， 证明：在高斯消去过程中，假设 ，若a=0，可以通过列变换使得前面的条件成立，这里不考虑这种情况。对矩阵A进行LU分解， ，其中 ，、为n维线性空间的自然基。是通过对单位阵进行初等变换得到，通过逆向的变换则可以得到单位阵，由此很容易得到的逆矩阵为。故 上式中的每一项均是初等变换，从右向左乘，则每乘一次相当于对右边的矩阵进行一次向下乘法叠加的初等变换。由于最初的矩阵为单位阵，变换从右向左展开，因而每一次变换不改变已经更新的数据，既该变换是从右向左一列一列更新数据，故。数学证明：具有 和 的形式，且有而具有的形式，因此：#

2、“高等数值分析”第二次书面作业20130924题目一问：能否用逐次householder相似变换变实矩阵A为上三角矩阵，为什么？解：不能用逐次householder相似变换变A为上三角矩阵，原因如下：A记作： ，存在householder阵 s.t. ，则 第一列的元素不能保证为的倍数，故无法通过householder变换实现上三角化。20130924题目二问：能否用逐次householder相似变换变实矩阵A为上Hessenberg矩阵，怎么做？解：可以用逐次householder相似变换变A为上Hessenberg矩阵，方式如下：记 ，其中为n-1维向量。 设 ，其中 ，则其中为n-22阶

3、阵，除最右一列以外都为0。若 中，为(n-k-1)(k+1)矩阵，且除最右一列外都为0，设 是对做householder变换对应的householder阵，则如此，An-2就是上Hessenberg矩阵，即 ，整个过程是通过householder变换得来，Q是householder阵的乘积，故是单位正交矩阵。#“高等数值分析”第三次书面作业20130926题目问：若对算子范数 ， ，s.t. ，证明： 可逆； 证明： 对于方程 ，移项得 ，两边取范数得而 ，故，而，所以，等号成立当且仅当 ，即，这就说明方程只有0解，故 可逆； #事实上，更一般的结论是可逆，且“高等数值分析”第四次书面作业20

4、131010题目问：设 ，证明： ， ；。证明： 设 （N0），（范数的连续性），因此， ，由范数的连续性可得，。若不成立，则 ，令 的第j项为1，其余项皆为0，则第i个元素为，且不趋于0，故不趋于0。综上， （是M的上确界），由于，由夹挤定理，由范数的连续性可知，。由特征值定义， 易证，所以，而非零，所以，所以。综上，#“高等数值分析”第五次书面作业20131012题目1问：设 ，而且非奇异，求解 等价于极小化，试推导极小化这个泛函的最速下降法。解：设 ，取 ，求出，s.t.取得最小值， 极小化的最速下降法：Step1给定 ，计算 ；Step2对于若，则停止；其中 为一事先给定的停机常数；否

5、则 Step3转到Step220131012题目2问：A为一对称正定矩阵，证明 是一种向量范数，且有 ，其中，分别为A的最大、最小特征值。证明：首先证明是一种向量范数：正定性由对称正定矩阵的等价性质可知，当且仅当时等号成立，因而，当且仅当时等号成立，正定性成立；齐次性，其中 ，齐次性成立；三角不等式由A的对称正定性质，存在可逆矩阵Q，s.t. ，因而，当且仅当共线等式成立。由上述两式可得，当且仅当共线等式成立，三角不等式成立。由于A是对称正定矩阵，所以A的所有特征向量构成n维空间的一组正交基，设为 ，用这组正交基表示为由正交性质可推出由于对称正定矩阵的所有特征值都大于0，所以其中，分别为A的最

6、大、最小特征值。#“高等数值分析”第六次书面作业20131015题目1问： 设A为一 对称正定矩阵，如在求解 的最速下降法中取 为一固定常数。试分析其收敛性。解： 由教材引理2.1.1，取 ，得 对于正定矩阵A，若 ，则，当时，算法不收敛。若 ，则，算法不收敛。因此，当 时，算法收敛，否则不能断定算法收敛。20131015题目2问： ， ，取 。用最速下降法求出 ，并计算出 与（2.1.10）比较。解：Step1给定 ，计算 ；Step2 容易得到 ，所以 由矩阵A的特征系数 ，得由于，所以，满足不等式（2.1.10），但由于，所以，两边差别不大，即收敛速度较慢。“高等数值分析”第七次书面作业

7、20131017题目1问： 推导在CG法中，可写成 ，。解： 将 带入上式得又，所以由定理2.2.1，及公式和， 推导完毕。20131017题目2问： 证明在CG法中，至多n步即可得到方程 的精确解，即 一定是方程的精确解。证明：是经过n步极小化得到的，且，是n维线性空间的一组基，因此是方程的精确解（由A对称正定，方程一定有精确解），否则若存在 是方程的精确解，且，这就违背了极小化的含义，因此一定是方程的精确解。#“高等数值分析”第八次书面作业20131022题目问： 利用性质“当 时，”直接由算法公式证明：对 且无中断时，有 ，并解释良性中断。证明：Arnoldi算法：Step1 Step2

8、 ， ， Step3，若，则；否则良性中断。从算法中可以看出，显然。假设（）， 显然；由性质“当 时，”可知，所以，继而，这就得到。综上，对于 且无中断时，有。当出现良性中断时，此时，即不再与线性无关，即此步前得到的线性空间对A不变，此时方程的解 ，由定理3.2.2知，此时得到的为方程的精确解。“高等数值分析”第九次书面作业20131024题目1问：在Lanczos过程中，若不考虑舍入误差，证明 与正交。证明：在Lanczos算法中，且每个都是单位向量。当j=1， ，即 与正交。假设 与两两正交，那么显然对所有的kj-1成立。 即 与正交。由数学归纳法原理知，在不计舍入误差条件下， 与正交。2

9、0131024题目2问：A为对称矩阵，证明若A有重特征值Lanczos过程必然会中断，反之成立否？证明：假设Lanczos过程不中断，那么将进行到最后一步，得到 ，由定理2.5.2，的特征值必然彼此不同，即没有重特征值，进而A没有重特征值。由反证法原理得，若A有重特征值Lanczos过程必然会中断。反之，若Lanczos过程中断，A不一定有重特征值，例如 ，取，则 ， ，过程中断，但A特征值为1、2、3，无重特征值，因而原结论反过来不成立。“高等数值分析”第十次书面作业20131029题目1问：当A可逆，证明：当时（k步良性中断），必有可逆。证明：在arnoldi算法中， ，设的一个特征值 的

10、特征向量是 ，则有，即也是A的特征值，对应特征向量为，进一步可以证明的所有特征值均为A的特征值。由于A可逆，故A无0特征值，所以无0特征值，进而得出可逆。在上述证明中，矩阵无0特征值与矩阵的行列式值不为0是等价的，这由特征值的定义式就可以证明，是显然的。20131029题目2问：考虑线性方程组 ，其中A是对称正定矩阵，用Galerkin原理求解方程， ，这里是一个固定的向量。 ，证明：其中，应该取哪个向量在某种意义上是最佳的？证明：利用A的对称正定性，等式得证。考虑取一定的使得最小， 取与共线时最佳，此时最小。但包含精确解，这是在不可能得到的（否则就不需要解方程了）。在第二章讲到的最速下降法中

11、，取的是，这是可行的。“高等数值分析”第十一次书面作业20131031题目1问：方程组 中系数矩阵是对称正定的，取。用Galerkin原理求解，其中是上一步的残余向量。a) 用和满足 的向量构成K中的一组基，给出计算的公式。b) 写出从到的计算公式。c) 该算法收敛吗？解：a) 设，则，所以b) ，非奇异。 c) 可以计算得到，即该算法收敛。其中 ，是方程精确解。20131031题目2问：矩阵以及 ，m=2，完成求解的Arnoldi和GMRES算法，得出 和。解：Arnoldi算法：Step1 Step2 ， Step3， Step4Step5所以 ，下面是利用matlab实现arnoldi算

12、法的一个程序和实验结果：clear all;clc;A=1 0 0 0;1 1 0 0;1 1 1 0;1 1 1 1;b=1 1 1 1;x0=0 0 0 0;f0=b-A*x0;H=zeros(size(A,1)+1,size(A,2);q1=f0./sqrt(f0*f0);m=2;for j=1:m for i=1:j H(i,j)=(A*qj)*qi; f1=A*qj; for t=2:j+1 ft=ft-1-H(t-1,j).*qt-1; end; fj=fj+1; end; H(j+1,j)=sqrt(fj*fj); if H(j+1,j)=0 qj+1=fj./H(j+1,j);

13、 end;end;HQ=zeros(size(A,1),size(A,2);for i=1:m Q(:,i)=qi;end;Qe1=zeros(m,1);e1(1)=1;x=x0+Q(:,1:m)*inv(H(1:m,1:m)*(sqrt(f0*f0).*e1)arnoldi算法：m=2的实验结果：H = 2.5000 -1.1180 0 0 1.1180 0.5000 0 0 0 0.4472 0 0 0 0 0 0 0 0 0 0Q = 0.5000 -0.6708 0 0 0.5000 -0.2236 0 0 0.5000 0.2236 0 0 0.5000 0.6708 0 0x =

14、0.8000 0.4000 -0.0000 -0.4000在舍入误差范围内与之前人工计算的结果一致（从第三个元素为-0.0000而不是0.0000可以看出计算是有舍入误差的）。当m=n=4时，结果如下：H = 2.5000 -1.1180 0.0000 -0.0000 1.1180 0.5000 -0.4472 -0.0000 0 0.4472 0.5000 -0.2236 0 0 0.2236 0.5000 0 0 0 0.0000Q = 0.5000 -0.6708 0.5000 -0.2236 0.5000 -0.2236 -0.5000 0.6708 0.5000 0.2236 -0.

15、5000 -0.6708 0.5000 0.6708 0.5000 0.2236x = 1.0000 0.0000 -0.0000 -0.0000 ，且得到的结果为精确解。GMRES算法：Step1由上面的Arnoldi算法可以得到，Step2 对根号内函数求偏导取值为0可得， ，由函数的凸性可知取上述值时函数取极小值，同时也是最小值。所以“高等数值分析”第十二次书面作业20131112题目1问：证明若H为有0特征值的上Hess阵则一步QR迭代即可算得H的0特征值并可收缩（降阶）。证明：H为上Hess阵，进行一次QR迭代有 ，为正交阵，是上三角矩阵且对角元中0元均在下方（可以通过givens变

16、换实现）。由于H有0特征值，故对角元中至少有一个0元（由矩阵行列式为0即可说明），因而可以通过一步QR迭代找到H的0特征值。设，有如下形式： ，也是一个上Hess矩阵，且有如下的形式：因此可以收缩降阶，且不需额外操作。 “高等数值分析”第十三次书面作业20131114题目1求：对 ，取 为位移，完成一步隐式位移QR迭代。解：S1：位移 S2：利用givens 变换作QR分解 S3： 20131114题目2证明：设A对称， 使 ，则 ，这里是Rayleigh商。证明：相当于对进行了一个方向和大小的改变，由向量加减运算的三角形关系可知，当与垂直时，最小，而事实上，即时，与垂直，此时有。严格证明如下

17、：设 ， ，则，求导得当时，取最小值，即取最小值，得证。“高等数值分析”第十四次书面作业20131121题目1问：给出用逐次Householder构造正交Q，W，使得 的算法，其中B为双对角阵。解：利用householder变换逐步将矩阵A的左下角变为0，并行地将次右上角变为0，具体操作如下：S1： ，即实现了第一行和第一列的变换，具体的householder阵可以通过反射定理求出，这里不具体给出。S2：进行到k步时，其中为kk的双对角矩阵，B为除了最后一行第一个元素外均为0。构造矩阵和，使得，那么S3:重复S2，直到完全二对角化。20131121题目2问：用Strum法，判断有几个正特征值。

18、解：在strum法中， 。在此题中， ， ，所以，由此可以得到如下结果：由定理，可得A矩阵严格大于0的特征值有 “高等数值分析”第十五次书面作业20131126题目问：验证隐式QR算法中的GR的第一列和显示QR算法中的Q的第一列相同。证明： 为双对角矩阵，通过追赶法不断通过Givens变换得到的矩阵也是双对角矩阵。其中对B的前两列作用，将变为0，且逐次givens变换得到的的第一列和的第一列相同，因为后面的变换矩阵对第一列没有影响。通过逐次givens变换做QR分解得为下三角矩阵，对前两列作用，且把变为0。由于和方向相同，和都是把前面对应的第二个非零元素变为0，因而。由前面的讨论，的第一列与的

19、第一列相同，同样的，的第一列与的第一列相同，因此与的第一列相同，证毕。“高等数值分析”第十六次书面作业20131128题目问：证明牛顿法中的 就是差商法中的p阶DD 。证明：在牛顿法中， 容易验证，p=0时，p=1时，假设p=k时，那么p=k+1时，即。由数学归纳法原理可知，牛顿法中的 就是差商法中的p阶DD。“高等数值分析”第十七次书面作业20131203题目证明：若且为在上分片1次插值，则有 。证明：， ， 所以， 而，因此又，对于1次插值， ，因此要证不等式成立。“高等数值分析”第十八次书面作业20131205题目1求证：若积分公式 至少有n次代数精度，则必有 ，这里 。证明：若积分公式

20、 至少有n次代数精度，则 ，有，其中表示所有n次多项式构成的集合。可表示为带入积分等式得，等式左边积分和求和可交换，故，又因为是任意的n次多项式，因而必有。#20131205题目2求：已知 ，有 ，先查出的值（n=3,6,12），再用外推近似计算。解：查询数学手册（或用计算器计算）得： 经过两次外推经过一次外推得到的结果是 可见，两次外推得到的结果要比一次外推的结果更精确。“高等数值分析”第十九次书面作业20131210题目问：下列映射 哪些在D上是压缩映射。i. ii.iii.解：对于一元函数，向量范数取绝对值，因此由压缩映像的定义可以得到“ ，都有，则称f为D上的一个压缩映射 ”。i. ，

21、所以当 时，因而 ，是D上的压缩映射。ii. ，由导数连续性可知，在D开区间内存在x使得该导数绝对值大于1，因而不是D上的压缩映射。iii. 是常函数，因而使D上的压缩映射。“高等数值分析”第二十次书面作业20131212题目问： ， 。在最坏可能的初值条件下，要 需要多少次迭代，其中迭代法为 。解：对于任意的 ，有 所以， 容易验证，该迭代的不动点为 ，所以 。在最坏的情况下，需要 次迭代才能满足。表示取整函数。实际上，初值很难取得这么差，迭代次数也会小得多。“高等数值分析”第二十一次书面作业20131219题目问： ，存在且可逆，记 。证明：存在 ，使得 。证明： 其中另可得， 或 ，取正值，所以存在使得成立。