-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathnode143.html
121 lines (106 loc) · 7.69 KB
/
node143.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
<!DOCTYPE html>
<!--Converted with LaTeX2HTML 99.2beta6 (1.42)
original version by: Nikos Drakos, CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<html>
<head>
<title>预处理</title>
<meta charset="utf-8">
<meta name="description" content="预处理">
<meta name="keywords" content="book, math, eigenvalue, eigenvector, linear algebra, sparse matrix">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-nB0miv6/jRmo5UMMR1wu3Gz6NLsoTkbqJghGIsx//Rlm+ZU03BU6SQNC66uf4l5+" crossorigin="anonymous">
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.js" integrity="sha384-7zkQWkzuo3B5mTepMUcHkMB5jZaolc2xDwL6VFqjFALcbeS9Ggm/Yr2r3Dy4lfFg" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/contrib/auto-render.min.js" integrity="sha384-43gviWU0YVjaDtb/GhzOouOXtZMP/7XUzwPTstBeZFe/+rCMvRwr4yROQP43s0Xk" crossorigin="anonymous"></script>
<script>
document.addEventListener("DOMContentLoaded", function() {
var math_displays = document.getElementsByClassName("math-display");
for (var i = 0; i < math_displays.length; i++) {
katex.render(math_displays[i].textContent, math_displays[i], { displayMode: true, throwOnError: false });
}
var math_inlines = document.getElementsByClassName("math-inline");
for (var i = 0; i < math_inlines.length; i++) {
katex.render(math_inlines[i].textContent, math_inlines[i], { displayMode: false, throwOnError: false });
}
});
</script>
<style>
.navigate {
background-color: #ffffff;
border: 1px solid black;
color: black;
text-align: center;
text-decoration: none;
display: inline-block;
font-size: 18px;
margin: 4px 2px;
cursor: pointer;
border-radius: 4px;
}
.crossref {
width: 10pt;
height: 10pt;
border: 1px solid black;
padding: 0;
}
</style>
</head>
<body>
<!--Navigation Panel-->
<a name="tex2html2900" href="node144.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2894" href="node140.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2888" href="node142.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2896" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2898" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2901" href="node144.html">算法模板</a>
<b>上一级：</b><a name="tex2html2895" href="node140.html">重启与收缩</a>
<b>上一节：</b><a name="tex2html2889" href="node142.html">收缩</a>
<br>
<br>
<!--End of Navigation Panel--><h4><a name="SECTION001373030000000000000">
预处理</a>
</h4>
对于像GMRES或CGS这样的迭代求解器，结合方程（<a href="node142.html#eq:jddefl">4.50</a>）进行预处理，其复杂度仅比单向量情况（参见第<a href="node137.html#sec:jdsym">4.7.1</a>节）稍高。假设我们有一个可用的左预处理器<span class="math-inline">{K}</span>，用于操作符<span class="math-inline">A-\theta_j^{(m)}I</span>。令<span class="math-inline">\widetilde{Q}</span>表示矩阵<span class="math-inline">\widetilde{X}_{k-1}</span>扩展后，将<span class="math-inline">{u}_j^{(m)}</span>作为其第<span class="math-inline">k</span>列。在这种情况下，预处理器<span class="math-inline">{K}</span>必须限制在与<span class="math-inline">\widetilde{Q}</span>正交的子空间内，这意味着我们需要在这个子空间内有效工作，即
<div class="math-display">\widetilde{K} \equiv (I-\widetilde{Q}\widetilde{Q}^\ast){K}(I-\widetilde{Q}\widetilde{Q}^\ast) .</div>
类似于单向量情况，这一过程可以出乎意料地高效实现。
<p>
假设我们使用一个初始猜测<span class="math-inline">{t}_0=0</span>的Krylov求解器，并通过左预处理来近似求解修正方程（<a href="node142.html#eq:jddefl">4.50</a>）。由于起始向量位于与<span class="math-inline">\widetilde{Q}</span>正交的子空间内，Krylov求解器的所有迭代向量都将处于该空间内。在这个子空间内，我们需要计算向量<span class="math-inline">{z} \equiv\widetilde{K}^{-1}\widetilde{A}{v}</span>，其中向量<span class="math-inline">{v}</span>由Krylov求解器提供，并且
<div class="math-display">\widetilde{A}\equiv(I-\widetilde{Q}\widetilde{Q}^\ast)(A-\theta_j^{(m)} I)(I-\widetilde{Q}\widetilde{Q}^\ast).</div>
这一计算分两步进行。首先我们计算
<div class="math-display">\widetilde{A}{v} =(I-\widetilde{Q}\widetilde{Q}^\ast) (A-\theta^{(m)}_j I)(I-\widetilde{Q}\widetilde{Q}^\ast){v} =(I-\widetilde{Q}\widetilde{Q}^\ast){y}</div>
其中<span class="math-inline">y \equiv (A-\theta_j^{(m)} I){v}</span>，因为<span class="math-inline">\widetilde{Q}^\ast {v}=0</span>。然后，通过左预处理，我们解出<span class="math-inline">{z}\perp \widetilde{Q}</span>，即
<div class="math-display">\widetilde{K} {z}=(I-\widetilde{Q}\widetilde{Q}^\ast){y} .</div>
<p>
由于<span class="math-inline">\widetilde{Q}^\ast {z}=0</span>，因此<span class="math-inline">{z}</span>满足<span class="math-inline">{K}{z}={y}-\widetilde{Q}\vec{\alpha}</span>或<span class="math-inline">{z}={K}^{-1}{y} - {K}^{-1}\widetilde{Q}\vec{\alpha}</span>。条件<span class="math-inline">\widetilde{Q}^\ast {z}=0</span>导致
<div class="math-display">\vec{\alpha}=(\widetilde{Q}^\ast {K}^{-1}\widetilde{Q})^{-1}\widetilde{Q}^\ast {K}^{-1}{y} .</div>
向量<span class="math-inline">\widehat{y}\equiv {K}^{-1}{y}</span>从<span class="math-inline">{K}\widehat{y}={y}</span>中解出，同样地，<span class="math-inline">{\widehat{Q}}\equiv{K}^{-1}\widetilde{Q}</span>从<span class="math-inline">{K}{\widehat{Q}}=\widetilde{Q}</span>中解出。注意，最后一组方程在迭代过程中只需解一次，因此对于<span class="math-inline">{i}_S</span>次线性求解器迭代，实际上需要<span class="math-inline">{i}_S+{k}</span>次预处理器操作。同时注意，在Krylov求解器的迭代中，左预处理操作符的矩阵向量乘法仅需一次<span class="math-inline">\widetilde{Q}^\ast</span>和<span class="math-inline">{K}^{-1}\widetilde{Q}</span>操作，而非四次投影操作符<span class="math-inline">(I-\widetilde{Q}\widetilde{Q}^\ast)</span>的操作。这在算法<a href="node144.html#alg:corrit2">4.18</a>给出的解决方案模板中有详细阐述。如果操作符<span class="math-inline">{K}</span>在多次连续特征值计算中保持不变，可以实现明显的节省（详细信息参见[<a href="node421.html#slvm98">412</a>]）。
<p>
<hr><!--Navigation Panel-->
<a name="tex2html2900" href="node144.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2894" href="node140.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2888" href="node142.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2896" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2898" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2901" href="node144.html">算法模板</a>
<b>上一级：</b><a name="tex2html2895" href="node140.html">重启与收缩</a>
<b>上一节：</b><a name="tex2html2889" href="node142.html">收缩</a>
<!--End of Navigation Panel-->
<address>
Susan Blackford
2000-11-20
</address>
</body>
</html>