这里可以使用幂法吗?

计算科学 线性代数 优化 线性求解器 计算几何 本征系统
2021-12-20 23:29:40

给定一组执行三角剖分的个点,可以构造系数使得每个点是与其相连的点的凸组合。假设相邻的一组点然后,对于每个nλij>0xiN(i)xixi

jN(i)λijxj=xi

jN(i)λj=1.

以矩阵形式,

Λx=x

其中是一个正方形,,行随机矩阵(非负条目,无自环)。Λn×n

现在假设给定矩阵我的问题是:Λ

  1. 是否可以通过幂法(即通过重复将乘以向量“主导”特征向量是,因此必须将其正交化为“第二主导”。我问是因为上面的矩阵形式让我想起了特征值/特征向量的定义。xΛ1n

  2. 如果不是,那么计算这种配置的好方法是什么?解决方案是否独特?

我认为配置是找到最小值问题的解决方案x

(i,j)E(xixj)2,

其中是三角剖分的边的集合。然而,这里应该计算与最小特征值相关的特征向量。为了建立这种关系,我使用了拉普拉斯算子和邻接矩阵之间的关系,如下文所述。E

还有一个有趣的问题:

  1. 系数可以构造成,这意味着矩阵是对称的吗?这种构造系数的方式意味着幂方法应该收敛到λijλij=λjiΛx
1个回答

你的直觉是对的,求解给定类似于特征值问题,除了你已经知道特征值及其对应的特征向量您还知道其余特征值的模数小于 1,因为是左随机矩阵,因此如果您对查找其余特征值/特征向量感兴趣,幂法似乎会起作用。您建议“去除”最大特征值以使幂方法收敛到第二主要特征向量的想法称为通货紧缩Λx=xxΛλ1=1x1=1nΛλ1=1x2,如果您想使用幂方法找到其余的特征向量,这将是必要的。有一些很简单的方法可以加速幂法,你应该搜索上移逆迭代,以及它的改进瑞利商迭代

具有相同的模数),则幂(移位逆,瑞利商)方法可能不起作用。为了克服这个问题,您可以使用subspace iteration,这基本上是幂方法,除了您将随机初始向量替换为矩阵(其列是线性独立的),以便您一次收敛到多个特征向量。最流行的子空间迭代版本利用 QR 分解进行归一化,通常称为QR 算法QR 算法的优点是可以设置得到λ2λ3xΛ. 幂法中的许多想法(例如,使用移位、使用通缩)可以扩展到 QR 算法以加速收敛。您还可以做其他事情来使 QR 算法更快(例如,使用 Householder 变换将矩阵减少为上 Hessenberg 矩阵,或者如果您的矩阵稀疏或您对并行性感兴趣,则使用 Given 的旋转)。Λ

TLDR;如果你想要所有的特征值,你可能应该使用 QR 算法。如果您只想要几个最大(或最小或中间)的特征值,您可以使用瑞利商迭代 + 通缩。如果您的矩阵庞大且稀疏,这可能是有利的,在这种情况下,您不需要计算昂贵的 QR 分解。

请注意,所有这些方法都属于“子空间迭代”的范畴(它们的收敛证明与幂方法基本相同)。您可以方便地查找我在这里提到的大部分内容。此外,这些方法非常易于理解和实施,这就是我推荐这些方法的原因。现在普遍使用更复杂的特征值算法,但它们中的许多都依赖于相同的原理。