-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathnode128.html
166 lines (142 loc) · 11.4 KB
/
node128.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
<!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>Q^* T Q 的稳定性</title>
<meta charset="utf-8">
<meta name="description" content="Q^* T Q 的稳定性">
<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="tex2html2676" href="node129.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2670" href="node124.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2666" href="node127.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2672" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2674" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2677" href="node129.html">锁定和清洗的实现</a>
<b>上一级：</b><a name="tex2html2671" href="node124.html">正交收缩变换</a>
<b>上一节：</b><a name="tex2html2667" href="node127.html">清洗</a>
<br>
<br>
<!--End of Navigation Panel--><h4><a name="SECTION001357040000000000000">
<span class="math-inline">Q^* T Q</span>的稳定性</a>
</h4>
算法<a href="node124.html#alg-orthQ">4.9</a>所示的收缩正交变换构造显然是稳定的（即，它在各分量上相对精确地表示了在精确算术中得到的变换）。毫无疑问，相似变换<span class="math-inline">Q^* T Q</span>能够完全保留矩阵<span class="math-inline">T</span>的特征值的数值精度。然而，在锁定和/或清除过程中，三对角形式的保持程度存在一个严重的问题。为了确保如果<span class="math-inline">T y = y \theta</span>，则<span class="math-inline">T_+ \equiv Q^* T Q</span>是对称的且在数值上是三对角的（即，非三对角带外的所有元素相对于<span class="math-inline">\Vert T \Vert</span>都是微小的），需要对基本算法进行修改。
<p>
<span class="math-inline">T_+ = Q^* T Q</span>为三对角形式依赖于表达式中的项<span class="math-inline">g y^* T R</span>消失：
<div class="math-display">Q^* T Q = L^*TR + g y^*T R + \theta e_1 e_1^*.</div>
<p>
然而，进一步检查发现：
<div class="math-display">e_1^* Q = e_1^* L + (e_1^* y) g^* = \eta_1 g^*,</div>
其中<span class="math-inline">\eta_1</span>是<span class="math-inline">y</span>的第一个分量。因此，<span class="math-inline">\Vert g \Vert = \frac{1}{\vert \eta_1 \vert}</span>。当<span class="math-inline">y</span>的第一个分量很小时，可能会出现数值困难。具体来说，<span class="math-inline">y^* T = \theta y^*</span>，因此在精确算术中<span class="math-inline"> y^* T R = 0</span>。然而，在有限精度下，计算出的<span class="math-inline">\mathrm{fl}(y^* T) = \theta y^* + z^*</span>。误差<span class="math-inline">z</span>相对于<span class="math-inline">\Vert T \Vert</span>将在<span class="math-inline">\epsilon_M</span>的量级上，但：
<div class="math-display">\Vert g y^*T R \Vert = \Vert g\Vert \cdot \Vert z^* R \Vert =\frac{1}{\vert \eta_1 \vert} \Vert z^* R \Vert,</div>
因此，这一项可能相当大，如果<span class="math-inline">\eta_1 = O(\epsilon_M)</span>，它可能达到<span class="math-inline">O(1)</span>的量级。这是一个严重的问题，并且在实践中如果不进行我们提出的修改，这种情况就会发生。
<p>
解决办法是引入逐步可接受的扰动和对向量<span class="math-inline">y</span>的重缩放，以同时强制满足以下条件：
<div class="math-display">Q^* y = e_1 \ \ \mathrm{and}\ \ y^* T Q = \theta e_1^*</div>
</div>
在有限精度下具有足够的准确性。为了实现这一点，我们将设计一个方案，以实现：
<div class="math-display">y^* T q_j = 0 \ \ \mathrm{for} \ \ j > 1</div>
在数值上。如[<a href="node421.html#sore98">420</a>]所示，这一修改足以在数值上建立<span class="math-inline">q_i^* T q_j = 0</span>，相对于<span class="math-inline">\Vert T \Vert</span>，对于<span class="math-inline">i > j + 1</span>。
<p>
基本思想如下：如果在第<span class="math-inline">j</span>步，计算出的量<span class="math-inline">\mathrm{fl}(y^* T q_j)</span>不够小，则通过用一个数<span class="math-inline">\phi</span>缩放向量<span class="math-inline">y_j</span>和用一个数<span class="math-inline">\psi</span>缩放分量<span class="math-inline">\eta_{j+1}</span>来调整它，使其足够小。在进行<span class="math-inline">q_{j+1}</span>的计算之前，进行这种重缩放，我们有<span class="math-inline">y_j \leftarrow y_j \phi</span>和<span class="math-inline">\hat{y}_j \leftarrow \hat{y}_j \psi</span>，其中<span class="math-inline">y^* = [ y_j^* , \hat{y}_j^*]</span>。当然，<span class="math-inline">\Vert y \Vert</span>不应因这种缩放而改变，因此这是必需的。这给出了以下方程组来确定<span class="math-inline">\phi</span>和<span class="math-inline">\psi</span>：如果<span class="math-inline">\vert y_j^* T_j \hat{q}_j + \rho_j \beta_j \eta_{j+1} \vert > \epsilon_M \tau_{j+1}</span>，
<div class="math-display">
\begin{aligned}
(\tau_j \phi)^2 + (1 - \tau_j^2)\phi^2 &= 1, \\
y_j^* T_j \hat{q}_j\phi + \rho_j \beta_j \eta_{j+1}\psi &= \pm \epsilon_M \tau_{j+1}.
\end{aligned}
</div>
<p>
如果<span class="math-inline">\rho_j</span>在<span class="math-inline">\sqrt{\epsilon_M}</span>的量级上，这种缩放可以被吸收到<span class="math-inline">\rho_j</span>中，而不改变<span class="math-inline">y</span>，也不影响<span class="math-inline">Q</span>的数值正交性。当<span class="math-inline">y</span>被修改时，之前计算的<span class="math-inline">q_i, 2 \le i \lt j,</span>不需要改变。在第<span class="math-inline">j</span>步之后，向量<span class="math-inline">y_j</span>在后续步骤中仅被重新缩放，定义<span class="math-inline">q_i, 2 \le i \le j,</span>的公式对<span class="math-inline">y_j</span>的缩放是不变的。有关详细信息，请参阅[<a href="node421.html#sore98">420</a>]。
<p>
算法<a href="node128.html#alg-orthQ2">4.10</a>实现了这一方案来计算可接受的<span class="math-inline">Q</span> <sup><a href="#footnote-q">1</a></sup>。在实践中，这种变换可以在不存储<span class="math-inline">Q</span>的情况下就地计算和应用，以获得<span class="math-inline">T \leftarrow Q^* T Q</span>和<span class="math-inline">V \leftarrow VQ</span>。然而，这种实现相当微妙，构造<span class="math-inline">Q</span>的细节要求避免额外的存储。该代码与上述描述略有不同，因为向量<span class="math-inline">y</span>仅在所有列<span class="math-inline">2</span>到<span class="math-inline">m</span>确定后才被重新缩放到单位范数。
<div style="text-align: left;">
<img src="icon/alg4.10.png" id="alg-orthQ2" alt="Algorithm 4.10 Stable Orthogonal Deflating Transformation for IRLM"/>
</div>
<p>
有几个实现问题：
<dl>
<dt><strong>(3)</strong></dt>
<dd>这里显示的扰动<span class="math-inline">y(i)</span>避免了特征向量<span class="math-inline">y</span>中精确零初始项的问题。理论上，当<span class="math-inline">T</span>未简化时，这种情况不应该发生，但如果<span class="math-inline">\theta</span>在初始向量中弱表示，这种情况可能在数值上发生。有一种更简洁的实现方法，不修改零项。这是最简单（也是最粗糙）的修正。
<p>
</dd>
<dt><strong>(10)</strong></dt>
<dd>一旦<span class="math-inline">\tau_j = \Vert y_j\Vert</span>足够大，就不需要进一步的修正。删除这个if-clause将恢复到算法<a href="node124.html#alg-orthQ">4.9</a>所示的未修改的<span class="math-inline">Q</span>计算。
<p>
</dd>
<dt><strong>(16)</strong></dt>
<dd>这显示了几种可能的修改<span class="math-inline">y</span>的方法之一，以实现<span class="math-inline">Q^* T Q</span>的非三对角带外元素在数值上微小的目标。更复杂的策略会将尽可能多的缩放吸收到对角元素<span class="math-inline">Q(j,j) = \rho</span>中。这里，不缩放<span class="math-inline">\rho</span>而是缩放<span class="math-inline">y</span>的分支设计为使<span class="math-inline">{\rm fl}(1 + (\rho \psi)^2) = {\rm fl}(1 + \rho^2) = 1</span>。
</dd>
</dl>
<hr>
<ol>
<li id="footnote-q">目前，有一种更为优秀的算法用于构建和应用这些变换；参见 D. Sorensen, Deflation for Implicitly Restarted Arnoldi Methods, CAAM Technical Report, TR 98-12, Rice University, 1998 (revised August 2000).</li>
</ol>
<hr><!--Navigation Panel-->
<a name="tex2html2676" href="node129.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2670" href="node124.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2666" href="node127.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2672" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2674" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2677" href="node129.html">锁定和清洗的实现</a>
<b>上一级：</b><a name="tex2html2671" href="node124.html">正交收缩变换</a>
<b>上一节：</b><a name="tex2html2667" href="node127.html">清洗</a>
<!--End of Navigation Panel-->
<address>
Susan Blackford
2000-11-20
</address>
</body>
</html>