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

第二题。对于 1 中的矩阵，将特征值进行平移，使得实部有正有负，和 1 的结果进行比较，方法的收敛速度会如 何？基本的 Arnoldi 算法有无峰点？若有，基本的 GMRES 算法相应地会怎样？ 答：
1. 使用如下方法对第一题中的 A 矩阵进行平移
A' AI
则得到的矩阵的特征值为 i' i 。
10-1
10-1
10-2
10-2
||rk||/||b||
||rk||/||b||
10-3
10-3
10-4
10-4
10-5
10-5
10-6
10-6
10-7 0
20
40
60
80
100 120 140 160 180
与与与与
10-7 0
20
40
60
80
100 120 140 160 180
与与与与
当负特征值个数逐渐增多时，迭代次数与负特征值个数 m 的关系曲线如下图
100
与 与 与 GMRES与 与
10-1
10-1
10-2
10-2
||rk||/||b||
||rk||/||b||
10-3
10-3
10-4
10-4
10-5
10-5
10-6
10-6
10-7 0
101 100
20 40 60 80 100 120 140 160 180 200 与与与与
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 950与 )
10-1
与 与 Aronldi
与 与 与 与 与 与 与 ||rk||与 与 与 与 (m=40)
与 与 GMRES 与 与 Aronldi
10-2
10-3
10-4
10-5 10-6
10-2
10-7 0
200
400
600
800
1000
1200
1400
与与与与与
160 180 200 220 240 260 280 300 320 340 与与与与与
与 与 GMRES 与 与 Aronldi
200
150
与与与与
100
50
0
0
50
3. 计算时间与 m 之间的关系
与 与 与 Arnoldi与 与 与 与 与 与 与 与 与 m与 与 与 与 与 5.5
100
150
m
与 与 与 GMRES与 与 与 与 与 与 与 与 与 m与 与 与 与 与 10
与与与与
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 600与 ) 101
与 与 与 Arnoldi与 与
100
Biblioteka Baidu
与 与 与 GMRES与 与
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 900与 ) 101
与 与 与 Arnoldi与 与
对第一题的 A，分别取、、、、、、、、、、，得到 的负特征值分别为、、、、、、、、、、个。分别求解上述矩阵，得到的结 果如下
||rk||/||b||
2、基本的 Arnoldi 和 GMRES 方法 代入前面提到的初始值 A、b、x0，得到的收敛结果如下
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 n=1000) 100
与 与 与 Arnoldi与 与
10-1
与 与 与 GMRES与 与
10-2
10-3
||rk||/||b||
||rk||/||b||
||rk||/||b||
||rk||/||b||
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 1与 ) 102
与 与 与 Arnoldi与 与 与 与 与 GMRES与 与
100
10-2
10-4
10-6
10-8 0
104 102
100
200
4. 结论 从上述结果中分析可得如下结论： 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方法 的相对残差要小。
300
400
500
600
700
与与与与
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 5与 )
与 与 与 Arnoldi与 与 与 与 与 GMRES与 与
100
10-2
10-4
10-6 0
102 100
100
200
300
400
500
600
700
与与与与
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 50与 )
9 5
8
4.5 7
与 与 与 与 与 与 (s) 与 与 与 与 与 与 (s)
4
6
5
3.5 4
3
3
0
50
100
150
0
50
100
150
m
m
从上述结果中看到在 m=40 左右时，同时有求解时间和迭代总步长最小的结果。当 m=40 时，得到的收敛曲线 结果如下图所示：
与 与 与 与 与 与 与 ||rk||与 与 与 与 (m=40) 100
与 与 GMRES
10-1
与 与 Aronldi
10-2
10-3
||rk||/||b||
10-4
10-5
10-6
10-7 0
5
10
15
20
25
30
35
与与与与
||rk||/||b|| ||rk||/||b||
与 与 与 与 与 与 与 ||rk||与 与 与 与 (m=40) 100
与 与 GMRES
与 与 与 Arnoldi与 与 与 与 与 GMRES与 与
10-2
10-4
10-6
10-8 0
104 102
100 200 300 400 500 600 700 800 900 与与与与
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 200与 )
与 与 与 Arnoldi与 与 与 与 与 GMRES与 与
与 与 与 Arnoldi与 与 与 与 与 与 与 与 m与 与 与 与 与 900
与 与 与 Arnoldi与 与
800
与 与 与 GMRES与 与
700
600
与与与与与
500
400
300
200
100 0
100 200 300 400 500 600 700 800 900 1000 m
注：上图标题有误，应为两种基本算法迭代步长与负特征值个数 m 的关系曲线
与 与 与 与 与 与 与 与 与 与 与 与 m与 与 与 与 与 与 与
与 与 GMRES 与 与 Aronldi
1600
1500
与与与与与
1400
1300
1200
1100
1000
900 0
50
100
150
m
从表中数据可以看出，结果相差并不大 2. 重启次数与 m 之间的关系
与 与 与 与 与 与 与 与 与 与 与 m与 与 与 与 与 与 与 250
与 与 Re(x)
500 400 300 200 100
0 -100 -200 -300 -400 -500
0
与 与 与 与 A与 与 与 与 与 与 与 与
与与与
50 100 150 200 250 300 350 400 450 500 与 与 Im(x)
2) b 的初值为 b=(1,1,1,1..1)T 3) 迭代初值为 x0=0 4) 停机准则为
此外，从收敛曲线上看，由于特征值均处在右半平面，收敛曲线平滑，收敛速度（收敛因子）比较均匀。
3、重启动的 GMRES 和 Arnoldi 算法 对上述 A、b、x0 使用重启动的 Arnoldi 和 GMRES 算法。变化 m 经过多次实验，得到如下结果： 1. 总迭代步长与 m 之间的关系
1900 1800 1700
结果讨论 1) 现象：随着负特征值的增多，Arnoldi 过程跳动越严重，但是整体是收敛的！这是由于负特征值的存 在，使得海森贝格矩阵 H 发生近似奇异而发生近似中断而引起的。然而，GMRES 的残差始终单调 不减，当 Aronldi 出现尖峰时，GMRES 的残差不变。 2) 当负半平面特征值个数比较少时，迭代次数明显变多，并在负半平面特征值个数为 200 左右时，迭 代次数最多，耗时最长，收敛速度最慢； 3) 当负半平面特征值个数变得比较多时，迭代次数减少，并且将比第一题的收敛速度更快得多，只需 200 多步迭代即可收敛。 4) 针对选取 A 的特殊性，
第二次实验作业 清华大学 高等数值分析 贾仲孝老师作业 第一题：构造例子特征值全部在右半平面时，观察基本的 Arnoldi 方法和 GMRES 方法的数值性态，和相应重新 启动算法的收敛性。 答： 1、计算初始条件 1) 矩阵 A 的生成 根据实 Schur 分解，构造矩阵如下形式
1 1
1 1
与 与 与 Arnoldi与 与 与 与 与 GMRES与 与
10-7 0
101 100
20
40
60
80
100 120 140 160 180
与与与与
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 1000与 )
与 与 与 Arnoldi与 与 与 与 与 GMRES与 与

2 2
A


2 2O

OO



n / 2 n / 2 n / 2 n / 2 nn
其中，A 由 n/2 个块形成，每个对角块具有如下形式，对应一对特征向量i ii
A


i i
i i

、
这里，取 n=1000，得到矩阵 A。经过验证，A 的特征值分布均在右半平面，如下图所示
100
10-2
10-4
10-6
10-8 0
100 200 300 400 500 600 700 800 900 与与与与
||rk||/||b||
||rk||/||b||
||rk||/||b||
||rk||/||b||
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 2与 ) 102
10-2
10-4
10-6
10-8 0
104 102
100
200
300
400
500
600
700
与与与与
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 100与 )
与 与 与 Arnoldi与 与 与 与 与 GMRES与 与
100
10-2
10-4
10-6
10-8 0
104 102
100
200
300
400
500
600
700
800
与与与与
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 400与 )
与 与 与 Arnoldi与 与 与 与 与 GMRES与 与
100
10-2
10-4
10-6
10-8 0
50
100
150
200
250
10-4
10-5
10-6
10-7 0
100
200
300
400
500
600
与与与与
结果讨论：从图中可以看出，基本的 Arnoldi 方法经过 554 步收敛，基本的 GMRES 方法经过 535 步收敛。这 是由于 GMRES 具有残差最优性，会略快于 Arnoldi 方法，但是，由于两种方法的基本原理近似，GMRES 方法不 会实质性的提速。
与 与 与 Arnoldi与 与 与 与 与 GMRES与 与
100
10-2
10-4
10-6
10-8 0
102 100
100
200
300
400
500
600
700
与与与与
与 与 与 与 与 与 与 ||rk||与 与 与 与 (与 与 与 与 与 与 与 20与 )
与 与 与 Arnoldi与 与 与 与 与 GMRES与 与