使用逆功率迭代实现 Jenkins Traub 算法-解网

问：

来自 Jenkins-Traub 迭代的维基百科文章建议，这些步骤也可以通过三种不同形式的逆向量迭代来实现。它建议一个矩阵来执行此迭代。我的问题是，当根源未知时，如何创建这个矩阵。因此，难道不应该不可能创建多项式P_1吗？此外，它说的是系数矩阵，但 Ps 是多项式？我想s_lambda，也不清楚要使用哪些起始向量和班次。此外，Jenkins 和 Traub 的原始论文中有一个解释，它假设多项式的系数矩阵是逆迭代的。我尝试实施他们的方法，但到目前为止，结果与原始算法的结果相加。实现即这里。

到目前为止，我只有以下三个阶段的代码（不包括规范化）：

def stage_1(A,h_lambda,max_iteration):
    h_bar_lambda = h_lambda / h_lambda[0]
    for _ in range(max_iteration):
      h_bar_lambda = A @ h_bar_lambda
    h_lambda = h_bar_lambda
    return h_lambda    

def stage_2(A,s_lambda,h_bar_lambda,dim,max_iteration):
  for _ in range(max_iteration):
    h_bar_lambda = np.linalg.inv(A-s_lambda[i]*np.eye(dim)) @ h_bar_lambda
  h_lambda = h_bar_lambda
  return h_lambda

def stage_3(A,s_lambda,h_bar_lambda,dim,max_iteration):
  for _ in range(max_iteration):
    h_bar_lambda = np.linalg.inv(A-s_lambda[i]*np.eye(dim)) @ h_bar_lambda
    s_lambda = np.array([rayleigh_s_lambda(A,h_bar_lambda,s_lambda),0,0,0,0])
  h_lambda = h_bar_lambda
  return h_lambda,s_lambda 

def rayleigh_s_lambda(A,v,s_lambda):
   return s_lambda.T @ (A @v) / (s_lambda.T @ v)

第 3 阶段主要以 Jenkins 和 Traub 的原始论文为导向。

python 数学矩阵数值方法特征值

使用原始矩阵的频谱位移可以加速逆幂迭代的收敛，从而使感兴趣的特征值接近零。这种偏移是通过减去单位矩阵的倍数来实现的。因此，将特征值的当前最佳猜测用作移位值是有意义的（如在第 3 阶段）。由于矩阵分解的成本，在中等步骤数内保持位移值恒定也是一个有效的决定（如第 2 阶段）。

Jenkins 和 Traub 的主要见解是，无需任何矩阵运算即可在伴随矩阵上实现移位逆幂迭代。回到多项式=有限序列，使用线性因子（又名）进行一次或两次长除法可以获得相同的结果。霍纳计划（不是霍纳、鲁菲尼或霍尔德雷德（？）发明的，而是更古老的民间传说）。

所以详细

当根未知时，如何创建这个矩阵。

矩阵只是所写的伴随矩阵。任何包含根的方程都会在计算结束时解决（假设的）状态，例如说如果是根，则可以拆分线性因子。Horner-Ruffini-Lagrange-Newton 方案或长除法（带余数）允许计算这样的因式分解。如果不直接在根上完成，它还会计算残差，即多项式值。rP(r)=0P(x)=(x-r)*P_1(x)P(x)=(x-a)*Q(x,a)+P(a)

如果你想直接使用矩阵，霍纳的思考是无关紧要的。

因此，难道不应该不可能创建多项式P_1

是的，是的。知道和知道根是一样的，根是目的，而不是方法的初始状态。Jenkins-Traub 中迭代的思想是，知道的近似值同样等同于知道一个根的近似值。Newton、Halley、Durand-Kerner等都是基于线性因子的改进，即直接的根。Jenkins-Traub 基于对其他多项式因数的改进，发现它提高了可靠性。P_1P_1

牛顿	哈蕾	Jenkins-Traub 第 3 阶段
$Newton fractal$	$Halley fractal$	$Jenkins fractal$

Fatou/Julia 使用 Newton、Halley 和 Jenkins-Traub 阶段 3 迭代设置第一个根的收敛。颜色亮度步长对应于到达根周围的白色区域的迭代次数。请注意，一个牛顿步长对应于两个多项式计算，而另一个步长每步有 3 个计算。

此外，它说的是系数矩阵，但 Ps 是多项式？

正如评论中所指出的，这是维基百科文章中的一个错误，其中P_k被用作线性因子的协因子，同时用作原始多项式的系数。

(旧答案）如果你知道一个更好的名字，...它是在基中表示线性算子的矩阵，因此条目是系数、坐标......？它基于的系数。P

我想s_lambda，也不清楚要使用哪些起始向量和班次。

这就是第一阶段和第二阶段的目的。阶段 1 计算以开头的初始多项式因子。通过不移位的反幂迭代，它缓慢地收敛到最小根的因式分解中的多项式因子。这不是很可靠，因为可能有多个类似小量级的根。阶段 2 的小随机偏移与其说是根近似，不如说是打破了阶段 1 结束时可能存在的对称性。趋势是选择并强调最接近移位值的小根。但这样的根源可能在有意义的意义上并不存在。H=P'

无论如何，在第 2 阶段结束时，期望多项式表示良好的因式分解，即（近似）互补线性因子包含可用于完全移位的第 3 阶段的良好根近似。H

数学可以很简洁，特别是当几个符号代表大量数据或一些复杂的算法时。我重写了这篇 WP 文章，目的是包含至少一个完整的算法（CPOLY 相当简单，RPOLY 有更多神秘的细节）以及所有相关的公式和想法。将其扩展到教学标准将给出比原始文本更长的文本，这与 WP 是百科全书相矛盾。我对不会过度增加文章篇幅的改进持开放态度。但这应该在WP文章的讨论页上讨论。

P_0,...,P_（n-1）是多项式的系数 P（X） = X^n + P_（n-1）X^（n-1）+...+P_1X+P_0。它们要么作为全局输入给出，要么作为最后一个根的线性因子的辅助因子。它来自原始论文，但也许没有那么幸运地将 lambda 用于整数迭代计数器。这封信没有更深层次的含义，人们同样可以把 k 作为计数器。

1赞 Lutz Lehmann 8/11/2023

对象 H 在（逆）幂迭代中起迭代向量的作用，对象H_bar是归一化向量。这里的归一化是将最高度系数设置为 1。因此，从 H_bar[k] 计算 H[k+1]，并将其归一化为 H_bar[k+1] 给出了当前根估计/近似值的偏移量作为因子。

1赞 Lutz Lehmann 8/11/2023

我看不出你从哪里得到这个想法。伴随矩阵是复数的（稀疏）矩阵。如果对它进行逆幂迭代，则不涉及进一步的多项式。剩下的联系是向量和 H 多项式都是固定长度的复数的有限序列。作为这样的序列，算法的两种解释应该给出相同的结果。

1赞 Lutz Lehmann 8/11/2023

是的，这很糟糕，使用相同的符号在同一个地方表达两个不同的想法。我将把系数更改为 a_k，因为它们是在顶部声明的。

上一个：在 Julia 中，有没有任何方法可以加速“点积”和“hcat”操作？

下一个：我不明白 Machine Epsilon 是什么意思

使用逆功率迭代实现 Jenkins Traub 算法

Implementing Jenkins Traub algorithm with inverse Power Iteration

评论

评论