没有合适的资源?快使用搜索试试~ 我知道了~
第5讲krylov 子空间算法.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 2 下载量 66 浏览量
2022-07-09
20:08:19
上传
评论 1
收藏 600KB PDF 举报
温馨提示
试读
75页
第5讲krylov 子空间算法.pdf
资源推荐
资源详情
资源评论
第 5 讲 Krylov 子空间算法
本章考虑下面的线性方程组
Ax = b, A ∈ R
n×n
, b ∈ R
n
, (5.1)
其中
x
∈
R
n
是我们所要求的解
.
目前求解大规模稀疏线性方程组
(5.1)
的首选方法是
子空间迭代法,
也
即是 Krylov 子空间算法. 其基本思想是在一个具有更小维数的子空间 K ⊂ R
n
中寻找满足精度要求的
近似解. 因此, 这类算法也可以看作是投影算法.
如果没有特别注明, 本章内容都是在实数域中讨论.
5.1 投影与投影算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
5.1.1 投影算子及其性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
5.1.2 投影算法一般形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5.2 Krylov 子空间与 Arnoldi 过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.2.1 Krylov 子空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.2.2 Arnoldi 过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.3 一般线性方程组的 Krylov 子空间算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.3.1 完全正交算法 (FOM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.3.2 广义极小残量法 (GMRES) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.3.3 GMRES 算法的实施细节 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.4 对称线性方程的 Krylov 子空间算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.4.1 Lanczos 过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.4.2 共轭梯度法 (CG) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.4.3 极小残量法 (MINRES) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.4.4 SYMMLQ 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5.5 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.5.1 Chebyshev 多项式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.5.2 CG 算法的收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.5.3 GMRES 算法的收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.6 基于双正交化过程的迭代算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.6.1 双正交化过程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.6.2 BiCG 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.6.3 QMR 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.7 无转置迭代算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.7.1 CGS 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.7.2 BiCGSTAB 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.8 正规方程的迭代算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.8.1 CGLS 算法和 Craig 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.8.2 LSQR 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
1
5.1 投影与投影算法 · 2 ·
5.1 投影与投影算法
5.1.1 投影算子及其性质
设 P : R
n
→ R
n
是一个线性映射. 如果
P
2
= P,
则我们称 P 是投影变换或投影算子 (projection operator), 有时简称投影 (projector).
本节中统一将投影变换简称为投影.
投影变换其实就是一个幂等矩阵.
下面是投影的几个基本性质:
性质 5.1 设 P : R
n
→ R
n
是一个投影, 则
(1) I −P 也是一个投影, 且 Ker(P) = Ran(I −P).
(2) P
T
也是一个投影.
性质 5.2 设 P : R
n
→ R
n
是一个投影, 则
R
n
= Ran(P) ⊕Ker(P).
反之, 若 V 和 L 是 R
n
的两个子空间, 且满足 R
n
= V ⊕L, 则存在唯一的投影 P 使得
Ran(P) = V 且 Ker(P) = L,
即对任意向量 x ∈ R
n
, 有
Px ∈ V 且 x −Px ∈L.
此时, 我们称 P 是沿 L 到 V 上的投影.
这里 Px 称为 x 在 V 中的投影 (沿 L).
由性质 5.2 可知, 投影算子由其像空间和零空间唯一确定.
设 A ∈ R
n×n
, 则 Ker(A) = Ran(A
T
)
⊥
, Ran(A) = Ker(A
T
)
⊥
.
设 W 是 L 的正交补, 即 W = L
⊥
, 则 W 的维数与 V 相同且 x −Px ∈ L 等价于
x −Px ⊥ W.
因此, 我们称 P 是 V 上与 W 正交的投影.
性质 5.3 设 V 和 W 是 R
n
中的两个子空间, 且维数相同. 如果 V ∩W
⊥
= {0} (或 R
n
= V ⊕W
⊥
), 则存
在唯一的投影 P 使得
Ran(P) = V 且 Ker(P) = W
⊥
,
5.1 投影与投影算法 · 3 ·
即 P 是 V 上与 W 正交的投影. 另外,
Px = 0 当且仅当 x ⊥ W.
设 V 和 W 的维数都是 m 且 R
n
= V ⊕W
⊥
. 令 {v
1
,v
2
,... ,v
m
} 和 {w
1
,w
2
,. .. ,w
m
} 分别是 V 和 W 的
一组基.
性质 5.4 设 P 是 V 上与 W 正交的投影, 则 P 可表示为
P = V (W
T
V )
−1
W
T
, (5.2)
其中 V = [v
1
,v
2
,. .. ,v
m
], W = [w
1
,w
2
,. .. ,w
m
].
证明. We first prove that W
T
V ∈ R
m×m
is nonsingular. Let
˜
W ∈ R
n×(n−m)
be a matrix whose columns form a
basis of W
⊥
. As R
n
= V ⊕W
⊥
, it follows that the columns of [V,
˜
W ] ∈R
n×n
form a basis of R
n
. erefore [V,
˜
W ]
is nonsingular and
rank(W
T
) = rank(W
T
[V,
˜
W ]) = rank([W
T
V,0]) = rank(W
T
V ).
Since rank(W
T
) = m, we have rank(W
T
V ) = m, which shows that W
T
V is nonsingular.
If P is the projector onto V and orthogonal to W, then we have Px ∈V and x −Px ⊥ W. Hence, there exists
a vector y ∈ R
m
such that
Px = V y and W
T
(x −V y) = 0.
It follows that y = (W
T
V )
−1
W
T
x. erefore,
Px = V y = V(W
T
V )
−1
W
T
x
holds for all x ∈ R
n
, which implies that P = V(W
T
V )
−1
W
T
.
虽然 P 是唯一的, 但其矩阵表示形式 (5.2) 并不唯一.
设 P 是一个投影, 如果
Ker(P) = Ran(P)
⊥
,
则称 P 是 Ran(P) 上的正交投影 (orthogonal projector), 否则称为斜投影 (oblique projector).
性质 5.5 投影 P 是正交投影的充要条件是 P
T
= P.
证明. If P
T
= P, then
Ker(P) = Ran(P
T
)
⊥
= Ran(P)
⊥
,
which implies that P is orthogonal.
Conversely, if P is orthogonal, then Ker(P) = Ran(P)
⊥
. Hence
Ran(P
T
) = Ker(P)
⊥
= Ran(P), Ker(P
T
) = Ran(P)
⊥
= Ker(P),
which indicates that P
T
and P have the same range and kernel. It follows from Proposition 5.2 that a projector
is uniquely determined by its range and kernel, so we have P
T
= P.
Let V = Ran(P). If P is an orthogonal projector, then for any vector x ∈ R
n
we have
Px ∈ V and x −Px ∈ V
⊥
. (5.3)
5.1 投影与投影算法 · 4 ·
性质 5.6 设 P : R
n
→ R
n
是 V 上的正交投影, 则 I −P 是 V
⊥
上的正交投影.
设 V 是由 V 中的一组标准正交基构成的矩阵, 则由性质 5.5 可知
P = VV
T
.
性质 5.7 设 P 是正交投影, 则
(1) ∥x∥
2
2
= ∥Px∥
2
2
+ ∥(I −P)x∥
2
2
, ∀x ∈ R
n
;
(2) ∥P∥
2
= 1.
证明. Let V = Ran(P). As P is orthogonal, it follows from (5.3) that Px ⊥ (I −P)x. erefore
∥x∥
2
2
= ∥Px ∥
2
2
+ ∥(I −P)x∥
2
2
.
is identity immediately gives ∥Px∥
2
≤∥x∥
2
and ∥P∥
2
≤1. Let y ∈ V be a nonzero vector. en Py = y, which
indicates that
∥P∥
2
= max
x=0
∥Px∥
2
∥x∥
2
≥
∥Py∥
2
∥y∥
2
= 1.
下面给出正交投影的一个重要应用.
考虑最佳逼近问题
min
x∈V
∥z −x ∥
2
(5.4)
其中 z 和 V 分别是给定的向量和子空间. 即在 2-范数意义下, 寻找 z 在 V 中最佳逼近. 这个问题的解就
可以通过正交投影来表示.
性质 5.8 设 P 是 V 上的正交投影, 则问题 (5.4) 的解为
x
∗
= Pz.
又 P 是由 V 唯一确定, 因此该问题的解也是唯一的.
证明. Since P is an orthogonal projector onto V, it holds that Pz ∈ V and (I −P)z ∈ V
⊥
. For any vector x ∈ V,
we have (I −P)z ⊥ (Pz −x) and
∥z −x ∥
2
2
= ∥(I −P)z + Pz −x∥
2
2
= ∥(I −P)z∥
2
2
+ ∥Pz −x∥
2
2
≥ ∥(I −P)z∥
2
2
,
where the equality holds if and only if x = Pz.
推论 5.1 x
∗
∈ V 是问题 (5.4) 的解的充要条件是
z −x
∗
⊥ V.
5.1 投影与投影算法 · 5 ·
推论 5.2 设 A ∈ R
n×n
对称正定, 则 x
∗
∈ V 是问题
min
x∈V
∥z −x∥
A
的解的充要条件是
A(z −x
∗
) ⊥ V,
其中 ∥z −x∥
A
, ∥A
1
2
(z −x)∥
2
.
证明. e proof is le as an exercise.
5.1.2 投影算法一般形式
设 K 是 R
n
的一个子空间, 维数为 dim(K) = m ≪ n. 我们需要在 K 中寻找精确解的一个 “最佳” 近
似. 由于 K 的维数是 m, 为了能够唯一确定这个近似解, 我们需要设置 m 个约束. 在通常情况下, 我们要
求残量满足 m 个正交性条件:
r = b −A ˜x ⊥ L, (5.5)
其中 ˜x 是我们所要寻找的近似解, L 是另一个 m 维子空间. 这就是数值计算中常用的 Petrov-Galerkin 条
件. 如果 L = K, 则称为 Galerkin 条件. 子空间 L 也称为 约束子空间 (constraint subspace).
显然, L 的不同取法会导致不同的投影算法. 当 L = K 时, 我们称为 正交投影法 (orthogonal
projection), 否则称为 斜投影法 (oblique projection).
因此, 一个投影算法可以描述为
find ˜x ∈ K such that b −A ˜x ⊥ L. (5.6)
如果给定一个初始近似值 x
(0)
∈ R
n
, 为了能够充分利用这个初值的相关信息, 我们改为在仿射空间
x
(0)
+ K 中寻找精确解的最佳近似. 此时算法可描述为
find ˜x ∈ x
(0)
+ K such that b −A ˜x ⊥ L. (5.7)
事实上, 如果我们将 ˜x 写成以下形式: ˜x = x
(0)
+ ˆx, 其中 ˆx ∈ K, 则 (5.85) 就是
find ˆx ∈ K such that r
0
−A ˆx ⊥ L , (5.8)
其中 r
0
= b −Ax
(0)
是初始残量. 这与 (5.6) 的形式是一样的.
下面我们考虑问题 (5.85) 或 (5.8) 的求解. 设 {v
1
,v
2
,. .. ,v
m
} 和 {w
1
,w
2
,. .. ,w
m
} 分别是 K 和 L 一组
基. 令 V = [v
1
,v
2
,. .. ,v
m
], W = [w
1
,w
2
,. .. ,w
m
]. 由于 ˜x ∈ x
(0)
+ K, 因此存在向量 y ∈ R
m
使得
˜x = x
(0)
+V y.
由正交性条件 (5.8) 可知
r
0
−AV y ⊥ w
i
, i = 1, 2,. .. ,m ,
即
W
T
AV y = W
T
r
0
.
如果 W
T
AV 是非奇异的, 则可解得 y = (W
T
AV )
−1
W
T
r
0
. 因此, 最佳近似解可表示为
˜x = x
(0)
+V (W
T
AV )
−1
W
T
r
0
.
剩余74页未读,继续阅读
资源评论
- yang_18882024-04-13资源质量不错,和资源描述一致,内容详细,对我很有用。
- eat_meat12023-10-17感谢资源主分享的资源解决了我当下的问题,非常有用的资源。
老帽爬新坡
- 粉丝: 83
- 资源: 2万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功