-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathnode163.html
160 lines (132 loc) · 7.98 KB
/
node163.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
<!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="tex2html3216" href="node164.html">
<button class="navigate">下一节</button></a>
<a name="tex2html3210" href="node155.html">
<button class="navigate">上一级</button></a>
<a name="tex2html3204" href="node162.html">
<button class="navigate">上一节</button></a>
<a name="tex2html3212" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html3214" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html3217" href="node164.html">直接方法</a>
<b>上一级：</b><a name="tex2html3211" href="node155.html">广义厄米特征值问题</a>
<b>上一节：</b><a name="tex2html3205" href="node162.html">存储和工作量</a>
<br>
<br>
<!--End of Navigation Panel--><h1><a name="SECTION001420000000000000000"></a><a name="sec:dense_gsym"></a><a name="17092"></a>
转换为标准问题
</h1>
<p>
我们可以将GHEP（<a href="node156.html#gsymeig">5.1</a>）重新表述为一个标准特征值问题，如果我们能对矩阵<span class="math-inline">B</span>或<span class="math-inline">A</span>或它们的线性组合进行因式分解。关于矩阵分解的简要概述，请参见§<a href="node385.html#sec:directsolvers">10.3</a>。
<p>
在前一种情况下，我们进行分解
<div class="math-display" id="B_chol">B=LL^{\ast}, \tag{5.4}</div>
例如，使用Cholesky分解，并对
<div class="math-display" id="C_eigenvalues">Cy=\lambda y, \tag{5.5}</div>
应用标准的厄米算法，其中<span class="math-inline">C=L^{-1}AL^{-\ast}</span>。原矩阵束（<a href="node156.html#gsymeig">5.1</a>）的特征向量<span class="math-inline">x</span>可以通过回代恢复，
<div class="math-display">x=L^{-\ast}y\,.</div>
这种策略在矩阵<span class="math-inline">B</span>相对于求逆是良态的，或者其结构比<span class="math-inline">A</span>更简单时是可取的，例如当<span class="math-inline">B</span>是对角矩阵时。<sup><a href="node163.html#footnote-b-ill">1</a></sup>
<p>
矩阵<span class="math-inline">C</span>是厄米的，我们可以应用第四章<a href="node85.html#chap:heig">4</a>中描述的任何迭代算法。每次矩阵<span class="math-inline">C</span>应用于一个向量时，计算按照表达式中的括号顺序进行，
<div class="math-display">y=Cx=L^{-1}(A(L^{-\ast}x)),</div>
即先回代，然后矩阵向量乘法，再前向代入。
<p>
我们也可以应用第四章<a href="node85.html#chap:heig">4</a>中的移位-反演谱变换（SI），注意到
<br><p></p>
<div class="math-display">(C-\sigma I)^{-1}= (L^{-1}AL^{-\ast}-\sigma I)^{-1}= L^{\ast}(A-\sigma B)^{-1}L,</div>
并使用对称不定分解，通常，<a name="AshBfact"></a>A-B=R^DR
其中<span class="math-inline">D</span>是块对角矩阵，以计算
<div class="math-display">y=(C-\sigma I)^{-1}x=L^{\ast}(R^{-1}(D^{-1}(R^{-\ast}(Lx))))</div>
按照括号中的顺序。
<p>
与标准情况一样，这种移位-反演变体通常收敛步数更少，弥补了对移位矩阵<span class="math-inline">A-\sigma B</span>进行因式分解和在三角矩阵上应用额外操作的成本。
<p>
看起来移位-反演算法需要两次矩阵分解，一次是<span class="math-inline">B</span>（<a href="node163.html#B_chol">5.4</a>），一次是<span class="math-inline">A-\sigma B</span>（<a href="node163.html#AshBfact">5.6</a>），但如果我们使用专门为广义特征问题开发的算法（<a href="node156.html#gsymeig">5.1</a>），则可以避免对<span class="math-inline">B</span>进行分解，这些算法将在本章后面描述。
<p>
另一种避免分解<span class="math-inline">B</span>的方法是应用第七章<a href="node203.html#chap:nep">7</a>中描述的非厄米矩阵算法，对非厄米矩阵
<div class="math-display">C=(A-\sigma B)^{-1}B\,.</div>
原矩阵束（<a href="node156.html#gsymeig">5.1</a>）的特征值<span class="math-inline">\lambda</span>可以计算为
<div class="math-display">\lambda=\sigma+\frac{1}{\theta},</div>
其中<span class="math-inline">\theta</span>是<span class="math-inline">C</span>的特征值。它与原矩阵束（<a href="node156.html#gsymeig">5.1</a>）具有相同的特征向量。
<p>
第二种方法的主要优点是我们可以使用标准的非厄米代码，例如隐式重启Arnoldi方法（参见§<a href="node220.html#sec:nsymiram">7.6</a>），易于获得。只要<span class="math-inline">B</span>相对于求逆是良态的，非对称矩阵<span class="math-inline">C</span>的特征问题就是良态的，但仍有可能得到违反GHEP某些性质的解，例如，可能会得到具有微小但非零虚部的特征值。
<p>
<hr>
<ol>
<li id="footnote-b-ill">
当矩阵 <span class="math-inline">B</span> 处于病态时，将选主元技术融入Cholesky分解中可以增强该过程的数值稳定性[<a href="node421.html#dht00">472</a>]。
</li>
</ol>
<hr><!--Navigation Panel-->
<a name="tex2html3216" href="node164.html">
<button class="navigate">下一节</button></a>
<a name="tex2html3210" href="node155.html">
<button class="navigate">上一级</button></a>
<a name="tex2html3204" href="node162.html">
<button class="navigate">上一节</button></a>
<a name="tex2html3212" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html3214" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html3217" href="node164.html">直接方法</a>
<b>上一级：</b><a name="tex2html3211" href="node155.html">广义厄米特征值问题</a>
<b>上一节：</b><a name="tex2html3205" href="node162.html">存储和工作量</a>
<!--End of Navigation Panel-->
<address>
Susan Blackford
2000-11-20
</address>
</body>
</html>