清华大学高等数值分析-第三次作业第八题复习过程

数值分析第三版习题答案
《数值分析第三版习题答案》
数值分析是一门研究利用数学方法和计算机技术解决实际问题的学科。

《数值分析第三版习题答案》是一本重要的教材，它包含了大量的习题和答案，帮助学
生更好地理解和掌握数值分析的知识。

在这本教材中，学生将会学习到一些重要的数值分析方法，比如插值法、数值
积分、常微分方程数值解法等。

这些方法在工程、物理、经济等领域都有着广
泛的应用，因此掌握这些方法对于学生来说非常重要。

《数值分析第三版习题答案》不仅提供了习题的答案，还对每个答案进行了详
细的解释，帮助学生更好地理解每个问题的解决方法。

通过练习这些习题，学
生可以提高他们的数值分析能力，为将来的工作和研究打下坚实的基础。

除了学生，这本教材也对教师和研究人员有着重要的意义。

教师可以通过这本
教材中的习题和答案来设计课程和考试，帮助学生更好地掌握数值分析的知识。

研究人员则可以通过这本教材中的方法和技巧来解决实际问题，推动学科的发展。

总之，《数值分析第三版习题答案》是一本非常重要的教材，它对于学生、教师和研究人员都有着重要的意义。

希望更多的人能够通过这本教材来学习和掌握
数值分析的知识，为推动科学技术的发展做出更大的贡献。

第三次作业第八题取b=(1,1,1,...1)T ,x0=0，停机准则为10-6。

1）当取A 1=(a ij )=1/(i+j-1)时，取阶数n=50，m=20时，得到收敛曲线如下0246810121416182010-1010-810-610-410-210GMRES 算法的||r k ||收敛曲线（所有步数） (A=A 1 阶数n=50, m=20)迭代次数||r k ||/||b ||结果表明，重启的GMRES 算法没有重启就得到了非常精确的结果。

这是由于该矩阵在n 较小时的数值正定特性有关。

取n=500 m=20计算结果如下，该图为重启次数与残差之间的关系曲线010203040506070809010010-610-510-4GMRES 算法的||r k ||收敛曲线 (A=A 1 阶数n=500, m=20)重启次数||r k ||/||b ||可以看出，该方法重启100步都无法收敛到10-6。

提高m 的值为m=100，计算如下010203040506070809010010-1010-810-610-410-210迭代次数||r k ||/||b ||从结果中可以看出，第一次计算（未重启）就得到了精确的结果。

该方法是数值qi 下面将阶数增为1000，m=20计算如下010203040506070809010010-710-610-510-410-3GMRES 算法的||r k ||收敛曲线 (A=A 1 阶数n=1000, m=20)重启次数||r k ||/||b ||图中可以看出，重启的GMRES 已经无法收敛，并且残差下降非常慢，没有再进行计算的必要。

将m 增为100，结果依然如前面，在一次重启就解出了结果。

010203040506070809010010-1010-810-610-410-210迭代次数||r k ||/||b ||2）当取A=A 2◆ 当n=100时，对该矩阵使用GMRES 方法，迭代20步即得到结果。

北京航空航天大学2020届研究生《数值分析》实验作业第九题院系：xx学院学号：姓名：2020年11月Q9:方程组A.4一、 算法设计方案（一）总体思路1.题目要求∑∑===k i kj s r rsy x cy x p 00),(对f(x, y) 进行拟合，可选用乘积型最小二乘拟合。

),(i i y x 与),(i i y x f 的数表由方程组与表A-1得到。

2.),(**j i y x f 与1使用相同方法求得，),(**j i y x p 由计算得出的p(x,y)直接带入),(**j i y x 求得。

1. ),(i i y x 与),(i i y x f 的数表的获得对区域D ={ （x,y)|1≤x ≤1.24,1.0≤y ≤1.16}上的f (x , y )值可通过xi=1+0.008i ，yj=1+0.008j ，得到),(i i y x 共31×21组。

将每组带入A4方程组，即可获得五个二元函数组，通过简单牛顿迭代法求解这五个二元数组可获得z1~z5有关x,y 的表达式。

再将),(i i y x 分别带入z1~z5表达式即可获得f(x,y)值。

2.乘积型最小二乘曲面拟合2.1使用乘积型最小二乘拟合，根据k 值不用，有基函数矩阵如下：⎪⎪⎪⎭⎫ ⎝⎛=k i i k x x x x B 0000 ， ⎪⎪⎪⎭⎫ ⎝⎛=k j jk y y y y G 0000数表矩阵如下：⎪⎪⎪⎭⎫⎝⎛=),(),(),(),(0000j i i j y x f y x f y x f y x f U记C=[rs c ]，则系数rs c 的表达式矩阵为：11-)(-=G G UG B B B C T TT ）（通过求解如下线性方程，即可得到系数矩阵C 。

UG B G G C B B T T T =)()(2.2计算),(),,(****j i j i y x p y x f (i =1,2,…,31 ; j =1,2,…,21) 的值),(**j i y x f 的计算与),(j i y x f 相同。

5 道大题，若干小题，卷面成绩满分70
1.(1)求f(x)=sqrt(1-x A2)在span{1,x,xA2}上，权函数为rou=1/sqrt(1-x A2)的最佳平方逼近多项式
⑵求证高斯型求积公式中的A(k)满足A(k)= / p(x)l(x)dx= / p(x)lA其(X)dXk)为Lagrange多项
式
2.(1)Ax=b中A非奇异，则用J法、GS法、SOR法、SSOR法求解等价方程ATAx=ATb各种方法的收敛性怎样？(其中0<w<2)
(2)A严格对角占优，求证其有唯一的LU分解，对称矩阵[3 1 0;1 3 1;0 1 3]求其cholysky分解
3.(1)写出用Lanczos方法计算某矩阵第一列的a和B
⑵已知矩阵[3 0 0;0 3 2;0 2 3]，求其QR分解，计算一步H'=RQ
4(1)f(x)=[x2A2-x1A2-x1 其精确解为x*=[0 0 0],写出牛顿法的计算公式sin(x1A2)-x2];
(2)已知G(x)=[x2A2-x1A2 sin(x1A2)];
给出区域D 使得在此区域内的初始值可以收敛到精确解，并说明原因
5.(1)线性2 步法-0.5y(n)-0.5y(n+1)+y(n+2)=h/2*(f(n)+f(n+1)+f(n+2))，计算其局部阶段误差的阶数若h=0.1,判断其稳定性
⑵已知R(z)的稳定函数是exp(z)的pade(1,2)逼近多项式，计算其稳定域，是否是A-稳定？(pade 逼近的计算公式卷子上给了)。

数值分析第三次作业解答思考题：1：（a ）对给定的连续函数，构造等距节点上的Lagrange 插值多项式，节点数目越多，得到的插值多项式越接近被逼近的函数。

×;(b) 对给定的连续函数，构造其三次样条函数插值，则节点数目越多，得到的样条函数越接近被逼近的函数。

√(c) 高次的Lagrange 插值多项式很常用。

×(d) 样条函数插值具有比较好的数值稳定性。

√3． 以0.1,0.15,0.2为插值节点，计算()f x = Lagrange 插值多项式 2()P x ， 比较2(0)P 和(0)f ，问定理4.1的结果是否适用本问题？ 解： 构造插值多项式：0122022(0.15)(0.2)()0.050.1(0.1)(0.2)()0.050.05(0.1)(0.15)()0.10.05()()()()(0)0;(0)0.1403x x l x x x l x x x l x P x x x x f P --=⨯--=⨯--=⨯=++==在（0，2）区间，5''''''23()(0.2)118.585458f x x f -=≤=从而，对任意的 '''3()(0,0.2),(0)0.05933!f ξξω∈≤ 不存在'''32()(0,0.2),(0)(0)(0)0.14033!f f P ξξω∈=-=。

演示程序：x=0:0.01:0.2; y=x.^(1/2);plot(x,y,'r')pause,hold onx0=[0.1,0.15 ,0.2]; y0=x0.^(1/2); x=0:0.01:0.2; y1=lagrangen(x0,y0,x); plot(x,y1,'b')5：（a ）求()f x x =在节点123452,0.5,0, 1.5,2x x x x x =-=-=== 的三次样条插值（150M M ==）。

高等数值分析实验一工物研13 成彬彬2004310559一．用CG，Lanczos和MINRES方法求解大型稀疏对称正定矩阵Ax=b作实验中，A是利用A= sprandsym(S,[],rc,3)随机生成的一个对称正定阵，S是1043阶的一个稀疏阵A= sprandsym(S,[],0.01,3);检验所生成的矩阵A的特征如下：rank(A-A')=0 %即A=A’，A是对称的；rank(A)=1043 %A满秩cond(A)= 28.5908 %A是一个“好”阵1．CG方法利用CG方法解上面的线性方程组[x,flag,relres,iter,resvec] = pcg(A,b,1e-6,1043);结果如下：Iter=35，表示在35步时已经收敛到接近真实xrelres= norm(b-A*x)/norm(b)= 5.8907e-007为最终相对残差绘出A的特征值分布图和收敛曲线：S=svd(A); %绘制特征值分布subplot(211)plot(S);title('Distribution of A''s singular values');;xlabel('n')ylabel('singular values')subplot(212); %绘制收敛曲线semilogy(0:iter,resvec/norm(b),'-o');title('Convergence curve');xlabel('iteration number');ylabel('relative residual');得到如下图象：为了观察CG方法的收敛速度和A的特征值分布的关系，需要改变A的特征值：(1).研究A的最大最小特征值的变化对收敛速度的影响在A的构造过程中，通过改变A= sprandsym(S,[],rc,3)中的参数rc(1/rc为A的条件数)，可以达到改变A的特征值分布的目的：通过改变rc=0.1，0.0001得到如下两幅图以上三种情况下，由收敛定理2.2.2计算得到的至多叠代次数分别为：48，14和486，由于上实验结果可以看出实际叠代次数都比上限值要小较多。

数值分析第三次作业及答案1． （P201(4)）用梯形方法解初值问题 '0;(0)1,y y y ⎧+=⎨=⎩ 证明其近似解为2,2nn h y h -⎛⎫= ⎪+⎝⎭并证明当0h →时，它收敛于原初值问题的准确解.xy e -=111112111000 [(,)(,)]2(,)()22222222 1,.2,.lim l n n n n n n n n n n n n n n nn n n h hy y f x y f x y hf x y y y y y y h h h y y y y h h h h y y h h n y nh x y +++++++-→=++=-⇒=+-----⎛⎫⎛⎫⎛⎫⇒==== ⎪ ⎪ ⎪+++⎝⎭⎝⎭⎝⎭-⎛⎫=⇒= ⎪+⎝⎭=⇒=证：梯形公式为由因用上述梯形公式以步长经步计算到故有0022im lim 22x nhx h h h h e h h -→→--⎛⎫⎛⎫== ⎪ ⎪++⎝⎭⎝⎭2． (P202(6)) 写出用四阶经典的龙格—库塔方法求解下列初值问题的计算公式：''3,01;,01;(1)1)2)(0)1;(0) 1.y y x y x y x x y y ⎧=<<⎧=+<<⎪+⎨⎨=⎩⎪=⎩ 12113224330.2(,)(,) 1.1()0.1 22221)(,) 1.11()0.112222(,) 1.n n n n n n n n n n n n n n n nn n n n h k f x y x y h h h h k f x y k x y k x y h h h h k f x y k x y k x y k f x h y hk x h y hk ===+=++=+++=++=++=+++=++=++=+++=解：令1123412132431222()0.222(22)0.2214 1.22140.021463/(1)3(0.1)/(10.1)2)3(0.1)/(10.1)3(0.2)/(10.2)0.2(6n n n n n n n n n nn n n n n n x y hy y k k k k x y k y x k y k x k y k x k y k x y y k ++⎧⎪⎪⎪⎨⎪⎪⎪++⎩=++++=++=+⎧⎪=+++⎪⎨=+++⎪⎪=+++⎩=+123422).k k k +++3． (P202(7)) 证明对任意参数t ，下列龙格库塔－公式是二阶的：12312131();2(,);(,);((1),(1)).n n n nn n n n h y y K K K f x y K f x th y thK K f x t h y t hK +⎧=++⎪⎪⎪=⎨⎪=++⎪=+-+-⎪⎩'''2'''31'123'2'()()()()[(,())(,())(,())]23!()[((,)(,)22(,)(,)())((,)(,n n n n x n n y n n n n n n n n n x n n y n n n n n n x n n y h y x y x hy x f x y x f x y x f x y x hh hy y K K y f x y f x y th f x y thf x y O h f x y f x y ζ++=++++=++=++++++证：由一元函数的泰勒展开有又由二元函数的泰勒展开有'22''32''311)(1)(,)(1)(,)())](,)[(,)(,)(,)]()2(),(,())[(,())(,())(,())]()2()y n n n n n n n x n n y n n n n n n n n n n x n n y n n n n n n t h f x y t hf x y O h h y hf x y f x y f x y f x y O h y y x h y y hf x y x f x y x f x y x f x y x O h y x y +++-+-+=++++==++++为考虑局部截断误差，设上式有比较与31111 ()()n n n R y x y O h t +++=-=两式，知其局部误差为故对任意参数，公式是二阶的。

《数值分析》复习要求
1. 数值方法引论
有效数字，数值方法稳定性
2. 线性方程组的直接解法
Gauss 消去法，以及相联系的A=LU ； 列主元Gauss 消去法；
直接分解求解方法：LU 分解，追赶法， Cholesky 方法；
矩阵范数，条件数，
误差分析，b →b+δb 情况
3. 线性方程组的迭代解法
()()1k k x Bx f +=+
收敛充要条件，收敛速度；
求解Ax=b 的Jacobi 迭代，G-S 迭代， 分量形式，迭代矩阵，收敛的充要条件， 充分条件；
SOR 迭代，方法及收敛性，最佳松弛因子
4. 非线性方程的数值解法
不动点迭代
()1k k x x ϕ+=
局部收敛性，收敛阶；
Newton 迭代，收敛性；单根，重根收敛阶
5. 插值法
Lagrange, Newton, Hermite 插值方法，余项；
均差，重节点均差；
分段低次插值以及三次样条插值函数概念；
6. 函数逼近
正交多项式，最小二乘法，
线性以及特殊非线性化成线性问题
7. 数值积分
代数精度，梯形公式，Simpson 公式以及 相应的复合求积公式、方法和余项；
Gauss求积公式，构造方法，
Gauss─Legendre求积,[ -1,1]，[a,b]
8.常微分方程初值问题的数值解法
单步法：Euler，隐式Euler，梯形方法，改进Euler，中点公式，四阶经典R-K方法；
局部截断误差，主项，方法阶，相容性，
收敛性和绝对稳定性。

线性多步法，方法的局部截断误差，
主项以及方法阶。

高等数值分析第三章作业参考答案1.考虑线性方程组Ax=b,其中A是对称正定矩阵.用Galerkin原理求解方程K=L=Span(v),这里v是一个固定的向量.e0=x∗−x0,e1=x∗−x1证明(e1,Ae1)=(e0,Ae0)−(r,v)2/(Av,v),(∗)其中r=b−Ax0.v应当取哪个向量在某种意义上是最佳的?证明.令x1=x0+αv,那么r1=r−αAv,e1=e0−αv.由Galerkin原理,有(r1,v)=0,因此α=(r,v)/(Av,v).注意到r1=Ae1,r=Ae,有(Ae1,v)=0.于是(e1,Ae1)=(e0−αv,Ae1)=(e0,Ae1)=(e0,Ae0)−α(e0,Av)=(e0,Ae0)−α(r,v)即(∗)式成立.由(∗)式知当v=e0时, e1 A=0最小,即近似解与精确解的误差在A范数意义下最小,算法一步收敛(但是实际中这个v不能精确找到);在最速下降意义下v=r时最佳.2.求证：考虑线性方程组Ax=b,其中A是对称正定矩阵.取K=L=Span(r,Ar).用Galerkin方法求解,其中r是上一步的残余向量.(a)用r和满足(r,Ap)=0的p向量构成K中的一组基.给出计算p的公式.解.设p=r+αAr,(r,Ap)=0等价于(Ar,p)=0.解得α=−(Ar,r)/(Ar,Ar).(b)写出从x0到x1的计算公式.解.设x1=x0+β1r+β2p,那么r1=r−β1Ar−β2Ap,再由Galerkin原理,有(r1,r)=(r1,p)=0,解得β1=(r,r)/(Ar,r),β2=(r,p)/(Ap,p).(c)该算法收敛吗?解.该算法可描述为：(1)选初始x0∈R n,计算初始残差r0=b−Ax0,ε>0为停机准则；(2)对k=0,1,2,...直到 r k <εαk=−(r k,Ar k) (Ar k,Ar k);p k=r k+αAr k;βk=(r k,r k) (Ar k,r k);γk=(r k,p k) (Ap k,p k);r k+1=r k−βk Ar k−γk Ap k;x k+1=x k+βk r k+γk p k.此算法本质上是由CG迭代一步就重启得到的,所以是收敛的,下面给出证法.设用此算法得到的x k+1=x k+¯p1(A)r k,那么e k+1 A=minp1∈P1e k+p1(A)r k A≤ e k+¯p1(A)r k A= e k−¯p1(A)Ae k A≤max1≤i≤n|˜p(λi)| e k A其中0<λ1≤...≤λn为A的特征值,˜p(t)=1−t¯p1(t)是过(0,1)点的二次多项式.当˜p满足˜p(λ1)=˜p(λn)=−˜p(λ1+λn2)时可使max1≤i≤n|˜p(λi)|达到最小.经计算可得min ˜p max1≤i≤n|˜p(λi)|≤(λ1−λn)2(λ1−λn)2+8λ1λn<1故若令κ=λ1/λn,则e k+1 A≤(κ−1)2κ2+6κ+1e k A,方法收敛.3.考虑方程组D1−F−E−D2x1x2=b1b2,其中D1,D2是m×m的非奇异矩阵.取L1=K1=Span{e1,e2,···,e m},L2= K2=Span{e m+1,e m+2,···,e n}.依次用(L1,K1),(L2,K2)按讲义46和47页公式Az∗=r0r0−Az m⊥LW T AV y m=W T r0x m=x0+V(W T AV)−1W T r0各进行一步计算.写出一个程序不断按这个方法计算下去,并验证算法收敛性.用L i=AK i重复上述各步骤.解.对任意给定x0=x(0)1x(0)2,令r=b−Ax0,V1=[e1,e2,...,e m],V2=[e m,e m+1,...,e n].对L i=K i情形,依次用(L1,K1),(L2,K2)各进行一步计算：(L1,K1)(L2,K2)z(1) 1=V1y1z(2)1=V2y2r0−Az(1)1⊥L1r0−Az(2)1⊥L2(V T1AV1)y1=V T1r0,D1y1=V T1r0(V T2AV2)y2=V T2r0,−D2y2=V T2r0x(1)1=x(1)+V1D−11V T1r0x(2)1=x(2)−V2D−12V T2r0得如下算法：(1)选初始x0∈R n,计算初始残差r0=b−Ax0,ε>0为停机准则；(2)对k=1,2,...直到 r k <ε求解D1y1=r k−1(1:m);求解−D2y2=r k−1(m+1:n);x k=x k−1+V1y1+V2y2;r k=r k−1−AV1y1−AV2y2.收敛性:r k=r k−1−AD−11−D−12rk−1=0−F D−12ED−11rk−1Br k−1算法收敛⇔ρ(B)<1⇔ρ(ED−11F D−12)<1.对L i=AK i情形,依次用(L1,K1),(L2,K2)各进行一步计算:(L1,K1)(L2,K2)z(1) 1=V1y1∈K1z(2)1=V2y2∈K2r0−Az(1)1⊥L1=AK1r0−Az(2)1⊥L2=AK2(V T1A T AV1)y1=V T1A T r0(V T2A T AV2)y2=V T2A T r0(D T1D1+E T E)y1=V T1A T r0(D T2D2+F T F)y2=V T2A T r0x(1) 1=x(1)+(D T1D1+E T E)−1V T1A T r0x(2)1=x(2)+(D T2D2+F T F)−1V T2A T r0得如下算法：(1)选初始x0∈R n,计算初始残差r0=b−Ax0,ε>0为停机准则；(2)对k=1,2,...直到 r k <ε求解(D T1D1+E T E)y1=(A T r k−1)(1:m);求解(D T2D2+F T F)y2=(A T r k−1)(m+1:n);x k=x k−1+V1y1+V2y2;r k=r k−1−AV1y1−AV2y2.收敛性:r k=r k−1−A(D T1D1+E T E)−1(D T2D2+F T F)−1A T rk−1(I−B)r k−1算法收敛⇔ρ(I−B)<1⇔0<λ(B)<2.4.令A=3−2−13−2...............−2−13,b=1...2用Galerkin原理求解Ax=b.取x0=0,V m=W m=(e1,e2,···,e m).对不同的m,观察 b−Ax m 和 x m−x∗ 的变化,其中x∗为方程的精确解.解.对于 b−Ax m 和 x m−x∗ ,都是前n−1步下降趋势微乎其微,到第n步突然收敛。