-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathnode133.html
266 lines (221 loc) · 15.8 KB
/
node133.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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
<!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/katex@0.16.11/dist/katex.min.css" integrity="sha384-nB0miv6/jRmo5UMMR1wu3Gz6NLsoTkbqJghGIsx//Rlm+ZU03BU6SQNC66uf4l5+" crossorigin="anonymous">
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.11/dist/katex.min.js" integrity="sha384-7zkQWkzuo3B5mTepMUcHkMB5jZaolc2xDwL6VFqjFALcbeS9Ggm/Yr2r3Dy4lfFg" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/katex@0.16.11/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="tex2html2748" href="node134.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2742" href="node131.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2736" href="node132.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2744" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2746" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2749" href="node134.html">算法</a>
<b>上一级：</b><a name="tex2html2743" href="node131.html">带状Lanczos方法</a>
<b>上一节：</b><a name="tex2html2737" href="node132.html">收缩的必要性</a>
<br>
<br>
<!--End of Navigation Panel--><h2><a name="SECTION001362000000000000000"></a> <a name="rwf:bandsym_prop"></a>
基本性质
</h2>
<p>
经过前<span class="math-inline">j</span>次迭代后，带状Lanczos算法已经生成了前<span class="math-inline">j</span>个Lanczos向量(<a href="node131.html#rwf:ABB">4.28</a>)。这些向量被构造为正交归一的：
<div class="math-display" name="#rwf:ABC">V_j^{\ast} V_j = I_j,\quad \mathrm{其中}\quad V_j = \left[ \begin{array}{cccc}v_1 & v_2 & \cdots & v_j\end{array} \right]. \tag{4.29}</div>
这里，<span class="math-inline">I_j</span>表示<span class="math-inline">j\times j</span>的单位矩阵。
除了(<a href="node131.html#rwf:ABB">4.28</a>)，算法还构造了向量
<div class="math-display" name="#rwf:ABY">\hat{v}_{j+1},\hat{v}_{j+2},\ldots,\hat{v}_{j+p_c}, \tag{4.30}</div>
这些向量是接下来<span class="math-inline">p_c</span>个Lanczos向量的候选，
<span class="math-inline">v_{j+1},v_{j+2},\ldots,v_{j+p_c}</span>。
这里，<span class="math-inline">p_c</span>是起始向量数<span class="math-inline">p</span>减去在前<span class="math-inline">j</span>次迭代中发生的缩减次数。
向量(<a href="node133.html#rwf:ABY">4.30</a>)被构造为满足正交关系
<div class="math-display" name="#rwf:ABE">V_j^{\ast} \hat{v}_{k} = 0 \quad \mathrm{对于所有}\quad k=j+1,j+2,\ldots,j+p_c. \tag{4.31}</div>
带状Lanczos算法内置了一个基于向量(<a href="node133.html#rwf:ABY">4.30</a>)的简单缩减过程。
实际上，在第<span class="math-inline">j+1</span>次迭代时的精确缩减等价于
<span class="math-inline">\hat{v}_{j+1}=0</span>。
因此，在算法中，检查 <span class="math-inline">\left\Vert\hat{v}_{j+1}\right\Vert _2</span>
是否小于某个合适的缩减容差。
如果是，向量<span class="math-inline">\hat{v}_{j+1}</span>被缩减，<span class="math-inline">p_c</span>减1。
否则，<span class="math-inline">\hat{v}_{j+1}</span>被归一化为下一个Lanczos向量<span class="math-inline">v_{j+1}</span>。
<p>
算法中用于生成向量(<a href="node131.html#rwf:ABB">4.28</a>)和(<a href="node133.html#rwf:ABY">4.30</a>)的递推关系可以紧凑地总结如下：
<div class="math-display" name="#rwf:ABD">A V_j = V_j T_j + \begin{bmatrix} 0 & \cdots & 0 & \hat{v}_{j+1} & \hat{v}_{j+2} & \cdots & \hat{v}_{j+p_c}\end{bmatrix} + \hat{V}_j^{\rm {(dl)}}. \tag{4.32}</div>
这里，<span class="math-inline">T_j</span>是一个<span class="math-inline">j\times j</span>矩阵，其元素被选择以满足正交条件(<a href="node133.html#rwf:ABC">4.29</a>)和(<a href="node133.html#rwf:ABE">4.31</a>)。
矩阵
<span class="math-inline">\hat{V}_j^{\rm {(dl)}}</span>在(<a href="node133.html#rwf:ABD">4.32</a>)中包含大多数零列，以及在前<span class="math-inline">j</span>次迭代中被缩减的未归一化向量。
回想一下，<span class="math-inline">p-p_c</span>是被缩减向量的数量。
<p>
事实证明，只需在<span class="math-inline">2p_c+1</span>个连续的Lanczos向量之间显式强制正交性，一旦发生缩减，还需对<span class="math-inline">p-p_c</span>个固定早期向量进行正交。
因此，矩阵<span class="math-inline">T_j</span>“基本上”是带状的，带宽为<span class="math-inline">2p_c+1</span>，每次缩减时带宽减少2。
此外，每次不精确缩减都会导致<span class="math-inline">T_j</span>在带状部分之外和右侧的固定行中具有非零元素。
更准确地说，由缩减引起的每个这样的行的行索引由<span class="math-inline">k - p_c(k)</span>给出，其中<span class="math-inline">k</span>是发生缩减的迭代次数，<span class="math-inline">p_c(k)</span>是该迭代时的相应<span class="math-inline">p_c</span>值。
因此，矩阵<span class="math-inline">T_j</span>可以写成
<div class="math-display" name="#rwf:ABW">T_j = T_j^{\rm {(b)}} + T_j^{\rm {(d)}}, \tag{4.3}</div>
其中
<span class="math-inline">T_j^{\rm {(b)}}</span>是一个带状矩阵，
<span class="math-inline">T_j^{\rm {(d)}}</span>
包含由于缩减而在<span class="math-inline">T_j</span>带状部分之外的水平“尖峰”。
特别是，如果没有发生不精确缩减，那么
<span class="math-inline">T_j^{\rm {(d)}}</span>
是零矩阵。
最后，我们注意到<span class="math-inline">T_j</span>的带状部分
<span class="math-inline">T_j^{\rm {(b)}}</span>是
一个厄米矩阵。
<p>
例如，考虑<span class="math-inline">p=5</span>个起始向量的情况，并假设在前<span class="math-inline">j=15</span>次迭代中，在步骤<span class="math-inline">k=8</span>、<span class="math-inline">k=11</span>和<span class="math-inline">k=13</span>处发生了缩减。
这三个缩减对应于从块Krylov序列(<a href="node131.html#rwf:ABA">4.27</a>)中删除向量<span class="math-inline">A b_3</span>、<span class="math-inline">A^2 b_2</span>和<span class="math-inline">A^3 b_1</span>，以及这些向量的后续<span class="math-inline">A</span>倍数。
在这种情况下，矩阵
<span class="math-inline">T_{15}=T_{15}^{\rm {(b)}} + T_{15}^{\rm {(d)}}</span>
具有以下稀疏结构：
<div style="text-align: center;" id="rwf:ACA">
<img src="icon/t15.png" alt="T_{15}的带状结构"/>
</div>
这里，<span class="math-inline">{*}</span>表示带状部分
<span class="math-inline">T_{15}^{\rm {(b)}}</span>内可能非零的条目，
<span class="math-inline">{\tt d}</span>表示由于在迭代<span class="math-inline">k=8</span>、<span class="math-inline">k=11</span>和<span class="math-inline">k=13</span>处缩减而导致的
<span class="math-inline">T_{15}^{\rm {(d)}}</span>内可能非零的条目。
注意，这三个缩减已将初始带宽<span class="math-inline">2p+1=11</span>减少到迭代<span class="math-inline">j=15</span>时的<span class="math-inline">2p_c+1=5</span>。
<p>
经过<span class="math-inline">j</span>次带状Lanczos算法迭代后，通过计算
<span class="math-inline">T_j^{\rm {(pr)}}</span>的特征解，可以得到厄米特征值问题(<a href="node131.html#rwf:AAA">4.25</a>)的近似特征解，
<div class="math-display">T_j^{\rm {(pr)}} z_i^{(j)} = \theta_i^{(j)} z_i^{(j)},\quad i=1,2,\ldots,j.</div>
这里，
<span class="math-inline">T_j^{\rm {(pr)}}</span>是<span class="math-inline">A</span>在Lanczos基矩阵<span class="math-inline">V_j</span>所张成的空间上的投影，即
<div class="math-display" name="#rwf:ABG">T_j^{\rm {(pr)}} = V_j^{\ast} A V_j. \tag{4.35}</div>
每个值
<span class="math-inline">\theta_i^{(j)}</span>及其Ritz向量，
<span class="math-inline">x_i^{(j)} = V_j z_i^{(j)}</span>，产生<span class="math-inline">A</span>的一个近似特征对。
当然，矩阵
<span class="math-inline">T_j^{\rm {(pr)}}</span>不是通过其定义(<a href="node133.html#rwf:ABG">4.35</a>)计算的。
相反，我们使用公式
<div class="math-display" name="#rwf:ABP">T_j^{\rm {(pr)}} = T_j + \left(T_j^{\rm {(d)}}\right)^{\ast}. \tag{4.36}</div>
通过(<a href="node133.html#rwf:ABP">4.36</a>)，我们只需共轭并转置<span class="math-inline">T_j</span>带状部分之外的部分，并将其添加到<span class="math-inline">T_j</span>中以获得
<span class="math-inline">T_j^{\rm {(pr)}}</span>。
为了证明(<a href="node133.html#rwf:ABP">4.36</a>)确实成立，注意通过从左侧乘以<span class="math-inline">V_j^{\ast}</span>并使用正交关系(<a href="node133.html#rwf:ABC">4.29</a>)和(<a href="node133.html#rwf:ABE">4.31</a>)，我们得到
<div class="math-display" name="#rwf:ABF">T_j^{\rm {(pr)}} = V_j^{\ast} A V_j = T_j + S_j, \quad \mathrm{其中}\quad S_j = V_j^{\ast} \hat{V}_j^{\rm {(dl)}}. \tag{4.37}</div>
由于矩阵
<span class="math-inline">T_j^{\rm {(pr)}}</span>和
<span class="math-inline">T_j^{\rm {(b)}}</span>都是
厄米的，因此从(<a href="node133.html#rwf:ABW">4.33</a>)可以得出
<span class="math-inline">S_j = (T_j^{\rm {(d)}})^{\ast}</span>在(<a href="node133.html#rwf:ABF">4.37</a>)中。
因此(<a href="node133.html#rwf:ABF">4.37</a>)简化为(<a href="node133.html#rwf:ABP">4.36</a>)。
<p>
例如，对于(<a href="node133.html#rwf:ACA">4.34</a>)中的<span class="math-inline">T_{15}</span>，相关的矩阵
<span class="math-inline">T_{15}^{(\rm pr)} = T_{15} + (T_{15}^{\rm {(d)}})^{\ast}</span>
具有以下形式
<div style="text-align: center;" id="rwf:ACB">
<img src="icon/t15pr.png" alt="T_{15}^{(\rm pr)}的带状结构"/>
</div>
这里，<span class="math-inline">\overline{{\tt d}}</span>在带状部分下方是通过共轭并转置(<a href="node133.html#rwf:ACA">4.34</a>)中带状部分上方的相应条目获得的。
我们注意到，在(<a href="node133.html#rwf:ACB">4.38</a>)中，带状部分之外的条目<span class="math-inline">{\tt d}</span>和
<span class="math-inline">\overline{{\tt d}}</span>通常很小。
更准确地说，如果使用下面的缩减准则(<a href="node134.html#rwf:AGA">4.42</a>)，那么所有<span class="math-inline">{\tt d}</span>和
<span class="math-inline">\overline{{\tt d}}</span>的绝对值都被缩减容差<span class="math-inline">{\tt dtol}</span>所限制。
尽管这些条目很小，但将它们设置为零会引入不必要的误差。
实际上，投影性质(<a href="node133.html#rwf:ABG">4.35</a>)对于
<span class="math-inline">T_{j}^{\rm {(pr)}}</span>
仅在带状部分之外的所有条目<span class="math-inline">{\tt d}</span>和
<span class="math-inline">\overline{{\tt d}}</span>都包含在
<span class="math-inline">T_{j}^{\rm {(pr)}}</span>中时成立。
<p>
最后，我们注意到带状Lanczos算法在达到<span class="math-inline">p_c=0</span>时终止。
这意味着已经发生了<span class="math-inline">p</span>次缩减，因此块Krylov序列被耗尽。
由于<span class="math-inline">p_c=0</span>导致的终止，Lanczos向量的关系(<a href="node133.html#rwf:ABD">4.32</a>)简化为
<div class="math-display" name="#rwf:RED">A V_j = V_j T_j + \hat{V}_j^{\rm {(dl)}}. \tag{4.39}</div>
使用(<a href="node133.html#rwf:ABF">4.37</a>)，我们可以将(<a href="node133.html#rwf:RED">4.39</a>)重写为
<div class="math-display" name="#rwf:REE">A V_j - V_j T_j^{\rm {(pr)}} =\left(I - V_j V_j^{\ast} \right) \hat{V}_j^{\rm {(dl)}}. \tag{4.40}</div>
现在让
<span class="math-inline">\theta_i^{(j)}</span>和<span class="math-inline">z_i^{(j)}</span>是
<span class="math-inline">T_j^{\rm {(pr)}}</span>的任意特征对，并假设<span class="math-inline">z_i^{(j)}</span>被归一化
使得
<span class="math-inline">\Vert z_i^{(j)}\Vert _2 = 1</span>。
回想一下，对
<span class="math-inline">\theta_i^{(j)}</span>和
<span class="math-inline">x_i^{(j)} = V_j z_i^{(j)}</span>
被用作<span class="math-inline">A</span>的近似特征解。
通过从右侧乘以<span class="math-inline">z_i^{(j)}</span>并取范数，可以得出近似特征解
<span class="math-inline">\theta_i^{(j)}</span>和<span class="math-inline">x_i^{(j)}</span>的残差可以被限制为
<div class="math-display" name="#rwf:REF">\left\Vert A x_i^{(j)} - \theta_i^{(j)} x_i^{(j)} \right\Vert_2 = \left\Vert(I-V_jV^*_j)\hat{V}_j^\text{(dl)} z_i^{(j)}\right\Vert_2\leq \left\Vert \hat{V}_j^{\rm {(dl)}} \right\Vert_2. \tag{4.41}</div>
特别是，如果仅执行精确缩减，那么
<span class="math-inline">\hat{V}_j^{\rm {(dl)}} = 0</span>，并且(<a href="node133.html#rwf:REF">4.41</a>)表明
<span class="math-inline">T_j^{\rm {(pr)}}</span>的每个特征值
<span class="math-inline">\theta_i^{(j)}</span>确实是<span class="math-inline">A</span>的特征值。
对于一般缩减，
<span class="math-inline">\hat{V}_j^{\rm {(dl)}}\not=0</span>，然而，
<span class="math-inline">\Vert \hat{V}_j^{\rm {(dl)}} \Vert _2</span>的量级
是缩减容差。
更准确地说，如果使用下面的缩减检查(<a href="node134.html#rwf:AGA">4.42</a>)，那么
<div class="math-display">\left\Vert \hat{V}_j^{\rm {(dl)}} \right\Vert _2 \leq\sqrt{p} \; {\tt dtol},</div>
其中<span class="math-inline">{\tt dtol}</span>表示缩减容差。
<p>
<hr>
</p><!--Navigation Panel-->
<a name="tex2html2748" href="node134.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2742" href="node131.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2736" href="node132.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2744" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2746" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2749" href="node134.html">算法</a>
<b>上一级：</b><a name="tex2html2743" href="node131.html">带状Lanczos方法</a>
<b>上一节：</b><a name="tex2html2737" href="node132.html">收缩的必要性</a>
<!--End of Navigation Panel-->
<address>
Susan Blackford
2000-11-20
</address>
</body>
</html>