-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathnode166.html
130 lines (120 loc) · 5.73 KB
/
node166.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
<!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;
}
.algorithm {
font-family: inherit;
font-size: inherit;
white-space: pre-wrap;
border: 1px solid #ddd;
}
</style>
</head>
<body>
<!--Navigation Panel-->
<a name="tex2html3261" href="node167.html">
<button class="navigate">下一节</button></a>
<a name="tex2html3255" href="node165.html">
<button class="navigate">上一级</button></a>
<a name="tex2html3249" href="node165.html">
<button class="navigate">上一节</button></a>
<a name="tex2html3257" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html3259" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html3262" href="node167.html">逆迭代</a>
<b>上一级：</b><a name="tex2html3256" href="node165.html">单向量和多向量迭代</a>
<b>上一节：</b><a name="tex2html3250" href="node165.html">单向量和多向量迭代</a>
<br>
<br>
<!--End of Navigation Panel-->
<h4><a name="SECTION001440010000000000000">
幂法</a>
</h4>
直接迭代法在HPE问题中的应用可以推广至GHEP问题（<a href="node156.html#gsymeig">5.1</a>）。
<p>
首先我们假设矩阵B的Cholesky分解<span class="math-inline">B = L \, L^{\ast}</span>容易获得。然后我们将（<a href="node156.html#gsymeig">5.1</a>）重新表述为一个标准厄米特征值问题，涉及矩阵<span class="math-inline">C</span>，如前一小节（<a href="node163.html#C_eigenvalues">5.5</a>）所述，可能需要先使矩阵<span class="math-inline">B</span>正定，如引言部分（<a href="node156.html#make_B_pd">5.2</a>）所述。第§<a href="node94.html#sec_power_sym">4.3</a>节中的幂法现在采取以下形式。
<a name="17168"></a>
<pre class="algorithm">
算法 5.1：GHEP问题的幂法
(1) 取初始向量 <span class="math-inline">v</span>，计算 <span class="math-inline">y := Lv, \; z:= y / \Vert y \Vert_2</span>
(2) for <span class="math-inline">k = 2,3,\dots</span>
(3) 计算 <span class="math-inline">y := C z, \; \theta := z^T y</span>
(4) if <span class="math-inline">\Vert y - \theta z \Vert_2 \leq \epsilon_M</span> then
(5) 计算 <span class="math-inline">y := L^{-\ast} z, \; z := y / \Vert y \Vert_2</span> 并停止
(6) else
(7) <span class="math-inline">z := y / \Vert y \Vert_2</span>
(8) end if
(9) end for
</pre>
<p>
在步骤（3）中，计算<span class="math-inline"> y := C \, z</span>可以分解为三个步骤：
<div class="math-display">y_1 = L^{-\ast}\, z, \quad y_2 = A \, y_1, \quad\mathrm{and}\quad y = L^{-1} \, y_2. </div>
因此，幂法执行过程中无需显式了解矩阵<span class="math-inline">C</span>。幂法的收敛条件与标准HEP问题类似。
<p>
<br><hr>
<!--Navigation Panel-->
<a name="tex2html3261" href="node167.html">
<button class="navigate">下一节</button></a>
<a name="tex2html3255" href="node165.html">
<button class="navigate">上一级</button></a>
<a name="tex2html3249" href="node165.html">
<button class="navigate">上一节</button></a>
<a name="tex2html3257" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html3259" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html3262" href="node167.html">逆迭代</a>
<b>上一级：</b><a name="tex2html3256" href="node165.html">单向量和多向量迭代</a>
<b>上一节：</b><a name="tex2html3250" href="node165.html">单向量和多向量迭代</a>
<!--End of Navigation Panel-->
<address>
Susan Blackford
2000-11-20
</address>
</body>
</html>