清华大学高等数值分析-第二次实验作业

第二次实验作业清华大学高等数值分析贾仲孝老师作业第一题：构造例子特征值全部在右半平面时，观察基本的Arnoldi方法和GMRES方法的数值性态，和相应重新启动算法的收敛性。答：1、计算初始条件1)矩阵A的生成根据实Schur分解，构造矩阵如下形式11112222/2/2/2/2nnAnnnn其中，A由n/2个块形成，每个对角块具有如下形式，对应一对特征向量iiiiiiiA、这里，取n=1000，得到矩阵A。经过验证，A的特征值分布均在右半平面，如下图所示050100150200250300350400450500-500-400-300-200-1000100200300400500复平面中A的特征值分布情况实部Im(x)虚部Re(x)特征值2)b的初值为b=(1,1,1,1..1)T3)迭代初值为x0=04)停机准则为2、基本的Arnoldi和GMRES方法代入前面提到的初始值A、b、x0，得到的收敛结果如下010020030040050060010-710-610-510-410-310-210-1100两种基本算法的||rk||收敛曲线(阶数n=1000)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法结果讨论：从图中可以看出，基本的Arnoldi方法经过554步收敛，基本的GMRES方法经过535步收敛。这是由于GMRES具有残差最优性，会略快于Arnoldi方法，但是，由于两种方法的基本原理近似，GMRES方法不会实质性的提速。此外，从收敛曲线上看，由于特征值均处在右半平面，收敛曲线平滑，收敛速度（收敛因子）比较均匀。3、重启动的GMRES和Arnoldi算法对上述A、b、x0使用重启动的Arnoldi和GMRES算法。变化m经过多次实验，得到如下结果：1.总迭代步长与m之间的关系0501001509001000110012001300140015001600170018001900两种重启算法总迭代步长与m的关系曲线比较总迭代次数m重启GMRES重启Aronldi从表中数据可以看出，结果相差并不大2.重启次数与m之间的关系050100150050100150200250两种重启算法重启次数与m的关系曲线比较重启次数m重启GMRES重启Aronldi3.计算时间与m之间的关系05010015033.544.555.5重启的Arnoldi算法求解运行时间与m的关系曲线求解运行时间(s)m050100150345678910重启的GMRES算法求解运行时间与m的关系曲线求解运行时间(s)m从上述结果中看到在m=40左右时，同时有求解时间和迭代总步长最小的结果。当m=40时，得到的收敛曲线结果如下图所示：0510152025303510-710-610-510-410-310-210-1100两种重启算法的||rk||收敛曲线(m=40)重启次数||rk||/||b||重启GMRES重启Aronldi020040060080010001200140010-710-610-510-410-310-210-1100两种重启算法的||rk||收敛曲线(m=40)总迭代次数||rk||/||b||重启GMRES重启Aronldi16018020022024026028030032034010-2两种重启算法的||rk||收敛曲线(m=40)总迭代次数||rk||/||b||重启GMRES重启Aronldi4.结论从上述结果中分析可得如下结论：1)对于这两种算法来说，重启动算法的总迭代步长要大于基本的算法，这个很容易理解，这是由于在重启动时，会丢掉一些之前算过的信息，从另一个点我们认为更好（其实不一定好）的初值x0重新开始计算。2)这两种重启动算法，在两次重启动的交接点处都会产生不连续。GMRES在两次重启动之间不满足残差单调不增，然而在单次重启的内部计算过程中，则满足单调不增的原则。Arnodli过程由于不具有残差二范数最小的性质，所以在以上两个位置处都可能会发生跳动。3)一般来说，重启次数随着m的增大不断减小，当m非常大的时候，就过度到了基本的不启动算法。4)随着m的增大，迭代总次数并不是单调下降的。重新启动的Arnoldi方法在m=40时迭代次数最少，重新启动的GMRES方法m=30或40时迭代次数最少。5)计算代价（用运算时间估算）与m不成线性关系，存在一个最优值，当m大到一定程度，虽然重启次数很小，但是每步代价很大，随着m的进一步增加，代价逐渐增大。6)重启的算法如果收敛的话，代价可能会远远小于不重启的算法。但是最合适的m的选取因问题不同而不同，不好把握。7)对于同样的矩阵A，GMRES方法的收敛速度一般比相应的Arnoldi方法快。这是由于其残差具有最优性，而且在迭代步数相同的情况下，GMRES方法的相对残差比相应的Arnoldi方法的相对残差要小。第二题。对于1中的矩阵，将特征值进行平移，使得实部有正有负，和1的结果进行比较，方法的收敛速度会如何？基本的Arnoldi算法有无峰点？若有，基本的GMRES算法相应地会怎样？答：1.使用如下方法对第一题中的A矩阵进行平移'AAI则得到的矩阵的特征值为'ii。对第一题的A，分别取、、、、、、、、、、，得到的负特征值分别为、、、、、、、、、、个。分别求解上述矩阵，得到的结果如下010020030040050060070010-810-610-410-2100102两种基本算法的||rk||收敛曲线(负特征值个数为1个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法010020030040050060070010-810-610-410-2100102两种基本算法的||rk||收敛曲线(负特征值个数为2个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法010020030040050060070010-610-410-2100102104两种基本算法的||rk||收敛曲线(负特征值个数为5个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法010020030040050060070010-810-610-410-2100102两种基本算法的||rk||收敛曲线(负特征值个数为20个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法010020030040050060070080090010-810-610-410-2100102两种基本算法的||rk||收敛曲线(负特征值个数为50个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法010020030040050060070080010-810-610-410-2100102104两种基本算法的||rk||收敛曲线(负特征值个数为100个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法010020030040050060070080090010-810-610-410-2100102104两种基本算法的||rk||收敛曲线(负特征值个数为200个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法05010015020025010-810-610-410-2100102104两种基本算法的||rk||收敛曲线(负特征值个数为400个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法02040608010012014016018020010-710-610-510-410-310-210-1100101两种基本算法的||rk||收敛曲线(负特征值个数为600个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法02040608010012014016018010-710-610-510-410-310-210-1100101两种基本算法的||rk||收敛曲线(负特征值个数为900个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法02040608010012014016018010-710-610-510-410-310-210-1100101两种基本算法的||rk||收敛曲线(负特征值个数为950个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法02040608010012014016018010-710-610-510-410-310-210-1100101两种基本算法的||rk||收敛曲线(负特征值个数为1000个)迭代次数||rk||/||b||基本的Arnoldi算法基本的GMRES算法当负特征值个数逐渐增多时，迭代次数与负特征值个数m的关系曲线如下图01002003004005006007008009001000100200300400500600700800900重启的Arnoldi算法总迭代步长与m的关系曲线总迭代次数m基本的Arnoldi算法基本的GMRES算法注：上图标题有误，应为两种基本算法迭代步长与负特征值个数m的关系曲线结果讨论1)现象：随着负特征值的增多，Arnoldi过程跳动越严重，但是整体是收敛的！这是由于负特征值的存在，使得海森贝格矩阵H发生近似奇异而发生近似中断而引起的。然而，GMRES的残差始终单调不减，当Aronldi出现尖峰时，GMRES的残差不变。2)当负半平面特征值个数比较少时，迭代次数明显变多，并在负半平面特征值个数为200左右时，迭代次数最多，耗时最长，收敛速度最慢；3)当负半平面特征值个数变得比较多时，迭代次数减少，并且将比第一题的收敛速度更快得多，只需200多步迭代即可收敛。4)针对选取A的特殊性，第三题、对1中的例子固定特征值的实部，变化虚部，比较收敛性。答：1)首先，固定A的特征值的实部，变化虚部。由前面可知，A的表达式为11112222/2/2/2/2nnAnnnn其中，A由n/2个块形成，每个对角块具有如下形式，对应一对特征向量iiiiiiiA将上式中的'iik改变k的大小，可以增加虚部的大小。本次实验，取k分别为0.5、1、1.5、2.5、4、5，分别得到的收敛曲线如下由前面可知，A的表达式为使用如下方法则可以在A的基础上固定A的实特征值，而增加Matlab程序基本的Arnoldi过程%ArnoldMethod%Byxxxxxxxxxxxx@2011-12-2%Email:[e-mail][x,Errs,flag]=Arnoldllb(A,b,x0,tol,mtime,cl)flag=0;H=[];Errs=[];r0=b-A*x0;nr0=norm(r0,2);V=r0/nr0;[nnn,n]=size(A);forj=1:mtime%disp(['k=',num2str(j)])%clc%disp([num2str(100*j/mtime),'%'])w=A*V(:,j);fori=1:jH(i,j)=V(:,i)'*w;w=w-H(i,j)*V(:,i);endH(j+1,j)=norm(w,2);ifH(j+1,j)1e-13disp('³öÏÖÖжÏ')endV=[V,w/H(j+1,j)];ifj=2%**********devideH=QRbyGivensMethod%{gm=nr0*[1;zeros(j-1,1)];Rm=H(1:j,1:j);Qm=eye(j,