-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathnode132.html
111 lines (102 loc) · 7.29 KB
/
node132.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
<!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="tex2html2734" href="node133.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2728" href="node131.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2722" href="node131.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2730" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2732" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2735" href="node133.html">基本性质</a>
<b>上一级：</b><a name="tex2html2729" href="node131.html">带状Lanczos方法</a>
<b>上一节：</b><a name="tex2html2723" href="node131.html">带状Lanczos方法</a>
<br>
<br>
<!--End of Navigation Panel--><h2><a name="SECTION001361000000000000000"></a> <a name="rwf:bandsym_defl"></a><a name="8317"></a>
收缩的必要性
</h2>
<p>
使用 <span class="math-inline">p \gt 1</span> 个初始向量会带来一个额外的难题，这是在单个向量 <span class="math-inline">p=1</span> 情况下不会出现的。对于单个初始向量 <span class="math-inline">b</span>，标准Lanczos算法在经过 <span class="math-inline">j</span> 次迭代后终止，如果下一个Krylov向量 <span class="math-inline">A^j b</span> 与之前的Krylov向量线性相关，即
<span class="math-inline">A^j b \in {\mathcal K}^j(A,b)</span>.
在这种情况下，Lanczos向量构成了 <span class="math-inline">A</span> 不变子空间 <span class="math-inline">{\mathcal K}^j(A,b)</span> 的一组基，并且Lanczos三对角矩阵的所有特征值也是 <span class="math-inline">A</span> 的特征值。子空间 <span class="math-inline">{\mathcal K}^j(A,b)</span> 是 <span class="math-inline">A</span> 不变的，意味着Krylov序列已被完全耗尽，因此再增加更多的Krylov向量也不会扩展Krylov子空间。这种在 <span class="math-inline">j</span> 次迭代后的终止是自然而然的。
<p>
然而，在 <span class="math-inline">p>1</span> 的情况下，首次出现的线性相关向量在(<a href="node131.html#rwf:ABA">4.27</a>)中并不意味着块Krylov序列已被耗尽。它仅仅意味着该线性相关向量及其后续的 <span class="math-inline">A</span> 倍数不包含任何新信息，因此，这些向量应从(<a href="node131.html#rwf:ABA">4.27</a>)中移除。这种检测并删除线性相关向量的过程称为<i>精确收缩</i>。例如，假设初始向量(<a href="node131.html#rwf:AAB">4.26</a>)使得向量 <span class="math-inline">A b_1</span> 是 <span class="math-inline">b_1, b_2, \ldots, b_p</span> 的线性组合。那么 <span class="math-inline">A b_1</span> 肯定与(<a href="node131.html#rwf:ABA">4.27</a>)中 <span class="math-inline">A b_1</span> 左侧的Krylov向量线性相关；实际上，每个向量 <span class="math-inline">A^i b_1</span> 且 <span class="math-inline">i \geq 1</span> 都与(<a href="node131.html#rwf:ABA">4.27</a>)中 <span class="math-inline">A^i b_1</span> 左侧的向量线性相关。在这种情况下，所有向量 <span class="math-inline">A^i b_1</span>，<span class="math-inline">i \geq 1</span>，都需要从(<a href="node131.html#rwf:ABA">4.27</a>)中删除，从而得到收缩后的块Krylov序列
<div class="math-display">b_1, b_2, \ldots, b_p, A b_2, A b_3, \ldots, A b_{p}, \ldots, A^{k-1} b_2, A^{k-1} b_3, \ldots, A^{k-1} b_{p}, \ldots.</div>
对于 <span class="math-inline">p>1</span>，与 <span class="math-inline">p=1</span> 的情况相反，首次出现精确收缩并不意味着由带状Lanczos方法生成的Lanczos矩阵的任何特征值也是 <span class="math-inline">A</span> 的特征值。然而，在发生了 <span class="math-inline">p</span> 次精确收缩之后，就像 <span class="math-inline">p=1</span> 的情况一样，Lanczos向量跨越了一个 <span class="math-inline">A</span> 不变子空间，并且Lanczos矩阵的所有特征值也是 <span class="math-inline">A</span> 的特征值。
<p>
当然，在有限精度算术中，无法区分完全线性相关和几乎线性相关的向量。因此，在实践中，几乎线性相关的向量也需要被检测和删除。在下文中，我们将检测和删除线性相关及几乎线性相关向量的过程称为<i>收缩</i>。
<p>
<hr><!--Navigation Panel-->
<a name="tex2html2734" href="node133.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2728" href="node131.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2722" href="node131.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2730" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2732" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2735" href="node133.html">基本性质</a>
<b>上一级：</b><a name="tex2html2729" href="node131.html">带状Lanczos方法</a>
<b>上一节：</b><a name="tex2html2723" href="node131.html">带状Lanczos方法</a>
<!--End of Navigation Panel-->
<address>
Susan Blackford
2000-11-20
</address>
</body>
</html>