node134.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>算法</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;
    }
</style>
</head>

<body>
<!--Navigation Panel-->
<a name="tex2html2762" href="node135.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2756" href="node131.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2750" href="node133.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2758" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2760" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2763" href="node135.html">变体</a>
<b>上一级：</b><a name="tex2html2757" href="node131.html">带状Lanczos方法</a>
<b>上一节：</b><a name="tex2html2751" href="node133.html">基本性质</a>
<br>
<br>
<!--End of Navigation Panel--><h2><a name="SECTION001363000000000000000"></a> <a name="rwf:bandsym_alg"></a>
算法
</h2>

<p>
厄米矩阵 <span class="math-inline">A</span> 的带状 Lanczos 算法的完整陈述如下。

<div style="text-align: left;" id="rwf:alg1">
<img src="icon/alg4.12.png" alt="Band Lanczos Method for HEP"/>
</div>

<p>
接下来，我们将更详细地讨论算法<a href="node134.html#rwf:alg1">4.12</a>的一些步骤。
<dl>
<dt><strong>(4)</strong></dt>
<dd>通常，是否需要对 <span class="math-inline">\hat{v}_j</span> 进行收缩的决策应基于检查是否

<div class="math-display" name="#rwf:AGA">\Vert\hat{v}_j\Vert_2 \leq {\tt dtol}, \tag{4.42}</div>

其中 <span class="math-inline">{\tt dtol}</span> 是一个适当选择的收缩容差。如果满足(<a href="node134.html#rwf:AGA">4.42</a>)，则对向量 <span class="math-inline">\hat{v}_j</span> 进行收缩。在这种情况下，如果 <span class="math-inline">j-p_c</span> 为正，则将其添加到包含 <span class="math-inline">T_j^{\rm {(d)}}</span> 中非零行索引的集合 <span class="math-inline">{\mathcal I}</span> 中，并将当前块大小更新为 <span class="math-inline">p_c=p_c-1</span>。如果 <span class="math-inline">p_c=0</span>，则块 Krylov 序列(<a href="node131.html#rwf:ABA">4.27</a>)耗尽，算法自然终止。如果 <span class="math-inline">p_c>0</span>，则删除向量 <span class="math-inline">\hat{v_j}</span>，将其余候选向量 <span class="math-inline">\hat{v}_{k+1}</span> 的索引 <span class="math-inline">k+1</span> 重置为 <span class="math-inline">k</span>，最后，算法返回到步骤(3)。如果不满足(<a href="node134.html#rwf:AGA">4.42</a>)，则不需要收缩，算法继续进行步骤(5)。

<p>
通常，在(<a href="node134.html#rwf:AGA">4.42</a>)中，会选择一个小的容差 <span class="math-inline">{\tt dtol}</span>，例如机器精度的平方根。然而，<span class="math-inline">{\tt dtol}</span> 不一定很小；算法<a href="node134.html#rwf:alg1">4.12</a>及其性质对于任何 <span class="math-inline">{\tt dtol}</span> 的选择仍然正确。请注意，如果在(<a href="node134.html#rwf:AGA">4.42</a>)中设置 <span class="math-inline">{\tt dtol}=0</span>，则算法仅进行精确收缩。

<p>
</dd>
<dt><strong>(5)</strong></dt>
<dd>向量 <span class="math-inline">\hat{v}_j</span> 已通过收缩检查，现在被归一化为下一个 Lanczos 向量 <span class="math-inline">v_j</span>。归一化使得

<div class="math-display">\left\Vert v_j \right\Vert _2 = 1\quad \text{for all}\quad j.</div>

<p>
</dd>
<dt><strong>(6)</strong></dt>
<dd>其余的候选向量，

<span class="math-inline">\hat{v}_{j+1},\hat{v}_{j+2},\ldots,\hat{v}_{j+p_c-1}</span>，与最新的 Lanczos 向量 <span class="math-inline">v_j</span> 进行显式正交化。请注意，在前 <span class="math-inline">p</span> 步中，某些 <span class="math-inline">t_{j,k-p_c}</span> 将具有非正列索引。它们用于使起始基正交，但不需要存储在 <span class="math-inline">T_j</span> 矩阵中。

<p>
</dd>
<dt><strong>(7)</strong></dt>
<dd>通过计算一个新的候选向量 <span class="math-inline">\hat{v}_{j+p_c}</span>，作为最新 Lanczos 向量 <span class="math-inline">v_j</span> 的 <span class="math-inline">A</span> 倍数，推进块 Krylov 序列。

<p>
</dd>
<dt><strong>(8)</strong></dt>
<dd>向量 <span class="math-inline">\hat{v}_{j+p_c}</span> 与先前的 Lanczos 向量 <span class="math-inline">v_{k_0}</span>, <span class="math-inline">v_{k_0+1}</span>, <span class="math-inline">\ldots</span>, <span class="math-inline">v_{j-1}</span> 进行正交化，其中 <span class="math-inline">k_0=\max\{1,j-p_c\}</span>。这里，我们利用了矩阵 <span class="math-inline">T_j^{(\rm pr)}</span> 是厄米的特性，因此我们不显式计算 <span class="math-inline">t_{kj}</span>，而是设置 <span class="math-inline">t_{kj} = \overline{t_{jk}}</span>。请注意，<span class="math-inline">t_{jk}</span> 在步骤(6)中已显式计算。

<p>
</dd>
<dt><strong>(9)</strong></dt>
<dd>向量 <span class="math-inline">\hat{v}_{j+p_c}</span> 与 Lanczos 向量 <span class="math-inline">v_k</span>，<span class="math-inline">k\in {\mathcal I}</span>，以及 <span class="math-inline">v_j</span> 进行显式正交化。请注意，使用改进的 Gram-Schmidt 方法进行此正交化。

<p>
</dd>
<dt><strong>(11)</strong></dt>
<dd>现在已计算出第 <span class="math-inline">j</span> 行和第 <span class="math-inline">j</span> 列中的所有非零元素，并将它们添加到前一次迭代 <span class="math-inline">j-1</span> 的矩阵 <span class="math-inline">T_{j-1}^{(\rm pr)}</span> 中，以产生当前矩阵 <span class="math-inline">T_{j}^{(\rm pr)}</span>。这里，我们约定在算法<a href="node134.html#rwf:alg1">4.12</a>中未显式定义的条目 <span class="math-inline">t_{ik}</span> 和 <span class="math-inline">s_{ik}</span> 设置为零。

<p>
</dd>
<dt><strong>(12)</strong></dt>
<dd>为了测试收敛性，计算厄米矩阵 <span class="math-inline">T_j^{\rm {(pr)}}</span> 的特征值 <span class="math-inline">\theta_i^{(j)}</span>，<span class="math-inline">i=1,2,\ldots,j</span>，如果某些 <span class="math-inline">\theta_i^{(j)}</span> 是 <span class="math-inline">A</span> 的期望特征值的良好近似，则停止算法。
</dd>
</dl>

<p>
<hr><!--Navigation Panel-->
<a name="tex2html2762" href="node135.html">
<button class="navigate">下一节</button></a>
<a name="tex2html2756" href="node131.html">
<button class="navigate">上一级</button></a>
<a name="tex2html2750" href="node133.html">
<button class="navigate">上一节</button></a>
<a name="tex2html2758" href="node5.html">
<button class="navigate">目录</button></a>
<a name="tex2html2760" href="node422.html">
<button class="navigate">索引</button></a>
<br>
<b>下一节：</b><a name="tex2html2763" href="node135.html">变体</a>
<b>上一级：</b><a name="tex2html2757" href="node131.html">带状Lanczos方法</a>
<b>上一节：</b><a name="tex2html2751" href="node133.html">基本性质</a>
<!--End of Navigation Panel-->
<address>
Susan Blackford
2000-11-20
</address>
</body>
</html>