node120.html

<!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>GEMV形式的Lanczos方法</title>
<meta charset="utf-8">
<meta name="description" content="GEMV形式的Lanczos方法">
<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="tex2html2562" href="node121.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2556" href="node117.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2550" href="node119.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2558" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2560" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2563" href="node121.html">收敛性质</a>
<b>上一级：</b><a name="tex2html2557" href="node117.html">隐式重启Lanczos</a>
<b>上一节：</b><a name="tex2html2551" href="node119.html">位移的选择</a>
<br>
<br>
<!--End of Navigation Panel--><h2><a name="SECTION001353000000000000000"></a>
<a name="8054"></a>
GEMV形式的Lanczos方法
</h2>

在算法<a href="node118.html#alg-irlm">4.7</a>每次重启时，我们拥有一个 <span class="math-inline">k</span>步的Lanczos分解

<div class="math-display">AV_k = V_k T_k + r_k e_k^{\ast}</div>

或者，对于<span class="math-inline">k=0</span>，有一个初始向量<span class="math-inline">r_0</span>。
算法<a href="node120.html#alg-ksteplan">4.8</a>提供了一个模板，用于应用<span class="math-inline">p</span>个额外的
Lanczos步骤将其扩展为一个<span class="math-inline">m</span>步的Lanczos分解

<div class="math-display">AV_m = V_m T_m + r_m e_m^{\ast}.</div>

<p>

<pre style="text-align: left;" id="alg-ksteplan">
算法 4.8：<small>m</small> 步Lanczos分解
(1)  开始于 <span class="math-inline">r = r_k</span> （之前的剩余向量或初始向量），令 <span class="math-inline">\beta_k = \Vert r_k \Vert</span>
(2)  for j = k+1,...,m
(3)      <span class="math-inline">v_j = r/\beta_{j-1}</span>
(4)      <span class="math-inline">r = Av_j - v_{j-1}\beta_{j-1}</span>
(5)      <span class="math-inline">\alpha_j = v^\ast_j r</span>
(6)      <span class="math-inline">r = r - v_j\alpha_j</span>
(7)      if <span class="math-inline">\Vert r \Vert_2 \lt \rho \sqrt{\alpha_j^2 + \beta^2_{j-1}}</span>
(8)          <span class="math-inline">s = V_j^\ast r</span>
(9)          <span class="math-inline">r = r - V_j s</span>
(10)         <span class="math-inline">\alpha_j = \alpha_j + s_j, \; \beta_j = \beta_j + s_{j-1}</span>
(11)     end if
(12) end for
</pre>

<p>
我们现在将描述一些实现细节，参考算法<a href="node120.html#alg-ksteplan">4.8</a>中的相应阶段。
<dl>
<dt><strong>(2)</strong></dt>
<dd>如果从头开始(<span class="math-inline">k=0</span>)，取<span class="math-inline">r_0=v</span>作为初始向量。
理想情况下，为了计算特征值，应尝试构建一个在感兴趣的特征向量方向上占优势的<span class="math-inline">v</span>。
在没有其他考虑的情况下，随机向量是一个合理的选择。

<p>
</dd>
<dt><strong>(3)</strong></dt>
<dd>将<span class="math-inline">r</span>归一化以获得新的基向量<span class="math-inline">v_{j}</span>。
范数
<span class="math-inline">\beta_{j-1} = \Vert r \Vert</span>
已经在步骤(7)中为前一个<span class="math-inline">j</span>计算过了。

<p>
</dd>
<dt><strong>(5)</strong></dt>
<dd>这是Lanczos三项递归步骤，用于使<span class="math-inline">r</span>相对于<span class="math-inline">V_j</span>的两个最新列正交化。
它以改进的格拉姆-施密特形式组织。

<p>
</dd>
<dt><strong>(7)</strong></dt>
<dd>此<em>if</em>子句中的语句序列确保新的残差方向<span class="math-inline">r</span>在数值上与先前计算的方向正交，即与<span class="math-inline">V_{j}</span>的所有列正交。
参数<span class="math-inline">\rho</span>必须指定（
<span class="math-inline">0 \le \rho &lt; \infty</span>）。
此测试询问的问题是：“<span class="math-inline">r = Av_{j}</span>是否接近已经构建的空间？”
比率

<span class="math-inline"> \Vert r\Vert/ \sqrt{ \alpha_{j}^2 + \beta_{j-1}^2 } = \tan \theta</span>，
其中<span class="math-inline">\theta</span>是向量<span class="math-inline">r</span>与<span class="math-inline">V_{j}</span>的值域空间之间的夹角。
<span class="math-inline">\rho</span>的值越大，正交性要求越严格。
当<span class="math-inline">\rho = 0</span>时，算法恢复为没有再正交化的标准Lanczos过程。
这种修正的一个步骤可能不够，应该作为一个迭代实现，后续修正的测试为
<span class="math-inline">\Vert r\Vert &lt; \rho \Vert s \Vert</span>；
参见[<a href="node421.html#dgks76">96</a>]中的讨论。
如果在固定次数的尝试后（例如五次）没有生成合适的<span class="math-inline">r</span>，则应将<span class="math-inline">\beta_{j}</span>设为零，并随机生成一个向量，该向量与基<span class="math-inline">V_j</span>正交，并替换<span class="math-inline">r</span>以继续分解。
我们建议设置<span class="math-inline">\rho = 1</span>。
</dd>
</dl>

<p>
众所周知，经典的Lanczos三项方案在 Ritz 值（近似特征值）收敛到 <span class="math-inline">A</span> 的特征值时，将无法精确生成正交向量。
为了解决这个问题，我们引入了一种迭代细化技术，该技术以非常合理的成本保持正交性至完全工作精度。
隐式重启的特殊情况使得这种修改对于获得准确的特征值和数值上正交的特征向量至关重要。
如果数值正交性没有保持，隐式重启机制的效果将降低，甚至可能失败。

<p>
<hr>

<!--Navigation Panel-->
<a name="tex2html2562" href="node121.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2556" href="node117.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2550" href="node119.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2558" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2560" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2563" href="node121.html">收敛性质</a>
<b>上一级：</b><a name="tex2html2557" href="node117.html">隐式重启Lanczos</a>
<b>上一节：</b><a name="tex2html2551" href="node119.html">位移的选择</a>


<!--End of Navigation Panel-->
<address>
Susan Blackford
2000-11-20
</address>
</body>
</html>