北航数值分析计算实习二.pdf

《北航数值分析计算实习二.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数值分析计算实习（二）姓名：张时毓学号：SY1403531一、方案设计1.用带双步位移的QR分解法求A的全体特征根先对A进行拟上三角化，得到??(??−1)，然后对??(??−1)用带双步位移的QR分解法进行QR分解，逐步得到A的全部特征根。算法流程图如图1所示。2.求实特征根对应的特征向量设拟上三角化过程为??(??−1)=??′−1????′其中??′为正交阵。QR分解迭代过程为??=??(??−1)1??=??−1????=??−1…??−1??−1??????…??=(????…??)−1??(??−

2、1)(????…??)??+1????????21112??12??12??记??′′=????…??，则有12????=??′′−1??(??−1)??′′=??′′−1??′−1????′??′′=(??′??′′)−1??(??′??′′)??+1其中??′′为正交阵。记Q=??′??′′，则有??=??−1??????+1其中Q为正交阵。因此??与A相似，设A和??的特征值分别为λ，λ…λ和λ′，λ′…λ′，对应的特??+1??+112??12??征值分别为x，x…x和x′，x′…x′，则有12??1

3、2??λ=λ′(??=1，2…??)????x=Qx′(??=1，2…??)????实特征根对应的特征向量即为Q中对应的列向量。3.QR分解从r=1开始，记??(1)=??，构造相似变换矩阵Hr，使??(??+1)=????(??)??r=n-1时，有??(??)=????(??−1)??−1其中R=??(??)Q=??1??2…????−1A=QR开始对A进行拟上三角化得到A(n-1)初始化给定精度er0，最大迭代次数Lk=1m=nA1=A(n-1)Y

4、am,m-1(k)

5、

6、am-1,m-2(

7、k)

8、0(??)(??)????

9、??=????−????????=(0…0,??????−????…??????)2??????????????−10????=??−2=�0??�‖????‖2??−1若每步计算先算H(??+1)(??)(??+1)r，再由??=??????计算??，则需做一次矩阵减法、一次向量乘法和一次矩阵乘法，即n2次减法和n2+n3次乘法，计算量大，因此，令1ℎ=‖??‖2????2????????=ℎ????=??(??)????????=??(??)????????则有??(??+1)=??(??)−??????

10、??????(??+1)=??(??)−??????????此时，计算??(??+1)只需作n2次减法和n+n2次乘法，计算量大大降低。4.拟上三角化用QR方法求特征值时，直接对A进行分解迭代次数太多，因此先对A进行拟上三角化，再对得到的拟上三角阵进行QR分解，从而减少迭代次数。(1)=??，构造相似变换矩阵H拟上三角化过程与QR分解类似，从r=1开始，记??r，使??(??+1)=????(??)??????r=n-2时，有??(??−1)=????(??−2)????−2??−2得到的??(??−1)即为

11、拟上三角阵。Hr的构造方法如下：若??????=0，(??≥??+1)，则取????=??；否则，取(??)(??)??????=(0…0,????+1,??…??????)e=????+1(??)+‖????‖????+1,??≤0????=�(??)+‖????‖????+1,??>0(??)(??)??????=????−????????+1=(0…0,??????−????…??????)2??????????????0????=??−2=�0??�‖????‖2??为减小计算量，令1ℎ=‖??‖2?

12、???2????????=ℎ????=??(??)????????=??(??)??????????=????????????????=????−????????则有??(??+1)=??(??)−??????−??????????????5.基本QR方法令??=??∈????×??，对A作QR分解1????=??????????=????=??−1??????+1??????????????+1相