-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathnode124.html
169 lines (152 loc) · 7.94 KB
/
node124.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
<!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="tex2html2618" href="node125.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2612" href="node117.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2606" href="node123.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2614" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2616" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2619" href="node125.html">锁定或清洗</a>
<b>上一级：</b><a name="tex2html2613" href="node117.html">隐式重启Lanczos</a>
<b>上一节：</b><a name="tex2html2607" href="node123.html">收缩与停止规则</a>
<br>
<br>
<!--End of Navigation Panel-->
<h2><a name="SECTION001357000000000000000"></a> <a name="orth_sec"></a>
正交收缩变换
</h2>
我们将利用一种特殊的正交变换来实现上述的收缩方案。这些收缩方案与一个与需要收缩（锁定或清洗）的Ritz值相关联的特征向量有关。给定一个单位长度的向量<span class="math-inline">y</span>，如算法<a href="node124.html#alg-orthQ">4.9</a>所示，计算出一个正交矩阵<span class="math-inline">Q</span>，使得<span class="math-inline">Q e_1 = y</span>（因此<span class="math-inline">e_1 = Q^* y</span>）。这个正交矩阵具有非常特殊的形式，可以写成
<div class="math-display" id="upform">
Q = R + y e_1^*, \quad \text{其中} \quad R e_1 = 0, R^* y = 0
</div>
其中<span class="math-inline">R</span>是上三角矩阵。它也可以写成
<div class="math-display" id="loform">
Q = L + y g^*, \quad \text{其中} \quad L e_1 = 0, L^* y = e_1 - g
</div>
其中<span class="math-inline">L</span>是下三角矩阵，
<span class="math-inline">g^* \equiv e_1^* + \frac{1}{\eta_1} e_1^* R</span>。
这里我们假设
<span class="math-inline">y^T=(\eta_1,\dots,\eta_n)</span>。
<p>
现在，考虑矩阵<span class="math-inline">Q^* T Q</span>。代入
<span class="math-inline">Q^* = (L + y g^* )^*</span>，
<span class="math-inline">Q = (R + y fe_1^* )</span> 来自<a href="node124.html#loform">4.24</a>和<a href="node124.html#upform">4.23</a>
以及事实
<span class="math-inline">Q^* T y = \theta e_1</span> 和 <span class="math-inline">1 = y^*y</span>，将得到
<div class="math-display">
\begin{aligned}
Q^* T Q &= Q^* T ( R + y e_1^*) \\
&= (L^* + g y^*) TR + \theta e_1 e_1^* \\
&= L^*TR + g y^*T R + \theta e_1 e_1^*.
\end{aligned}
</div>
由于<span class="math-inline">L^*</span>和<span class="math-inline">R</span>都是上三角矩阵，因此<span class="math-inline">L^*TR</span>是上Hessenberg矩阵，其第一行和第一列均为零，因为<span class="math-inline">Le_1 = Re_1 = 0</span>。同时，<span class="math-inline">g y^*T R = g \theta y^*R = 0</span>。由此我们得出<span class="math-inline">L^*TR</span>也必须是对称的，因此是三对角的。因此，我们看到
<span class="math-inline">T_+ \equiv Q^* T Q</span> 具有以下形式
<div class="math-display">T_+ = \begin{bmatrix} \theta & 0 \\0 & \widehat{T} \end{bmatrix},</div>
其中<span class="math-inline">\widehat{T}</span>是对称且三对角的。
<p>
需要注意的是，如算法<a href="node124.html#alg-orthQ">4.9</a>计算的那样，<span class="math-inline">Q</span>将在元素相对误差上达到机器精度<span class="math-inline">\epsilon_M</span>，且没有元素增长。
<pre style="text-align: left;" id="alg-orthQ">
算法 4.9 IRLM的正交收缩变换
(1) 以 <span class="math-inline">k</span> 维的向量 <span class="math-inline">y</span> 开始，其中 <span class="math-inline">\Vert y \Vert = 1</span>
(2) <span class="math-inline">Q = 0, \; Q(:,1) = y</span>
(3) <span class="math-inline">\sigma=y(1)^2, \tau_0 = \vert y(1)\vert</span>
(4) for j = 2,...,k
(5) <span class="math-inline">\sigma=\sigma+y(j)^2, \; \tau = \sqrt\sigma</span>
(6) if <span class="math-inline">\tau_0 \ne 0</span>
(7) <span class="math-inline">\gamma = (y(j)/\tau)/\tau_0</span>
(8) <span class="math-inline">Q(1:j-1,j)=-y(1:j-1)\gamma</span>
(9) <span class="math-inline">Q(j,j)=\tau_0/\tau</span>
(10) else
(11) <span class="math-inline">Q(j-1,j) = 1</span>
(12) end if
(13) <span class="math-inline">\tau_0 = \tau</span>
(14) end for
</pre>
<p>
<br><hr>
<!--Table of Child-Links-->
<a name="CHILD_LINKS"><strong>子章节</strong></a>
<ul>
<li><a name="tex2html2620" href="node125.html">锁定或清洗单个特征值</a>
<li><a name="tex2html2621" href="node126.html">锁定<span class="math-inline">\theta</span></a>
<li><a name="tex2html2622" href="node127.html">清洗<span class="math-inline">\theta</span></a>
<li><a name="tex2html2623" href="node128.html"><span class="math-inline">Q^* T Q</span>的稳定性</a>
</ul>
<!--End of Table of Child-Links-->
<hr>
<!--Navigation Panel-->
<a name="tex2html2618" href="node125.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2612" href="node117.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2606" href="node123.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2614" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2616" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2619" href="node125.html">锁定或清洗</a>
<b>上一级：</b><a name="tex2html2613" href="node117.html">隐式重启Lanczos</a>
<b>上一节：</b><a name="tex2html2607" href="node123.html">收缩与停止规则</a>
<!--End of Navigation Panel-->
<address>
Susan Blackford
2000-11-20
</address>
</body>
</html>