translate-template/node167.html at main · 0382/translate-template · GitHub

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
<!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/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;
    }
    .algorithm {
        font-family: inherit;
        font-size: inherit;
        white-space: pre-wrap;
        border: 1px solid #ddd;
    }
</style>
</head>

<body>
<!--Navigation Panel-->
<a name="tex2html3275" href="node168.html">
<button class="navigate">下一节</button></a>
<a name="tex2html3269" href="node165.html">
<button class="navigate">上一级</button></a>
<a name="tex2html3263" href="node166.html">
<button class="navigate">上一节</button></a>
<a name="tex2html3271" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html3273" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html3276" href="node168.html">Rayleigh商迭代</a>
<b>上一级：</b><a name="tex2html3270" href="node165.html">单向量和多向量迭代</a>
<b>上一节：</b><a name="tex2html3264" href="node166.html">幂法</a>
<br>
<br>
<!--End of Navigation Panel-->

<h4><a name="SECTION001440020000000000000">
逆迭代</a>
</h4>

<p>
如果我们能够对一个位移<span class="math-inline">\sigma</span>分解<span class="math-inline">A - \sigma \, B</span>，我们就可以将逆迭代推广到计算问题(<a href="node156.html#gsymeig">5.1</a>)在<span class="math-inline">\sigma</span>附近的特征值，如算法<a href="node167.html#invit_gsymeig">5.2</a>所示。<a name="17197"></a>

<pre class="algorithm" id="invit_gsymeig">
算法5.2：广义厄米特征值问题的逆迭代
(1) 开始于猜测向量 <span class="math-inline">y</span>
(2) for <span class="math-inline">k = 1,2,\dots</span>
(3)     计算 <span class="math-inline">w = By</span>
(4)     <span class="math-inline">\eta = (w^*y)^{1/2}, \; v = y/\eta, \; w = w / \eta</span>
(5)     计算 <span class="math-inline">y = (A-\sigma B)^{-1}w</span>
(6)     <span class="math-inline">\theta = w^*y</span>
(7)     如果 <span class="math-inline">\Vert (1/\theta)y - v\Vert_2 \le \epsilon_M</span>，停止
(8) end for
(9) 获得结果 <span class="math-inline">\lambda = \sigma + 1/\theta, \; x = y/\theta</span>
</pre>

<p>
以下是关于此算法的一些注释。在步骤(3)中我们乘以<span class="math-inline">B</span>，而在步骤(5)中我们解一个以位移矩阵<span class="math-inline">A-\sigma B</span>为系数的线性方程组。在实际应用中，我们会先进行一次稀疏高斯消元，并在后续操作中使用其<span class="math-inline">L</span>和<span class="math-inline">U</span>因子。步骤(4)确保向量<span class="math-inline">v</span>具有单位<span class="math-inline">B</span>范数。量<span class="math-inline">\theta</span>是一个瑞利商，

<div class="math-display" id="theta_rq">\theta=w^{\ast}y=w^{\ast}(A-\sigma B)^{-1}w=v^{\ast}B(A-\sigma B)^{-1}Bv. \tag{5.7}</div>

在步骤(7)中我们测试一个残差向量，

<div class="math-display">r=(1/\theta)y-v=(A-\sigma B)^{-1}(\tilde{\lambda}B-A)v,</div>

其中<span class="math-inline">\tilde{\lambda}=\sigma+1/\theta</span>是当前的近似特征值。逆迭代的收敛条件与标准厄米特征值问题类似。

<p>
<br><hr>
<!--Navigation Panel-->
<a name="tex2html3275" href="node168.html">
<button class="navigate">下一节</button></a>
<a name="tex2html3269" href="node165.html">
<button class="navigate">上一级</button></a>
<a name="tex2html3263" href="node166.html">
<button class="navigate">上一节</button></a>
<a name="tex2html3271" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html3273" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html3276" href="node168.html">Rayleigh商迭代</a>
<b>上一级：</b><a name="tex2html3270" href="node165.html">单向量和多向量迭代</a>
<b>上一节：</b><a name="tex2html3264" href="node166.html">幂法</a>
<!--End of Navigation Panel-->
<address>
Susan Blackford
2000-11-20
</address>
</body>
</html>