6.3 Faddeev-Leverrier算法求特征多项式

算法

  index.php/tags-41973.html" >���迹求特征多项式的特点是计算量特别大，性能不高，为此Faddeev和Laverrier两人研究出了更好的求特征多项式的算法。这种算法是一种迭代法，通过创建一个矩阵系列 B k B_k Bk​来实现。初始定义 B 1 = A B_1=A B1​=A，然后按以下公式递推：

B k = A ( B k − 1 − c k − 1 E ) c k = 1 k t r ( B k ) B_k=A(B_{k-1}-c_{k-1}E)\\ c_k=\frac1k tr(B_k) Bk​=A(Bk−1​−ck−1​E)ck​=k1​tr(Bk​)

  最终得到的特征多项式为：

Δ A ( λ ) = λ n − c 1 λ n − 1 − ⋯ − c k λ n − k − ⋯ − c n \Delta_A(\lambda)=\lambda^n-c_1\lambda^{n-1}-\cdots-c_k\lambda^{n-k}-\cdots-c_n ΔA​(λ)=λn−c1​λn−1−⋯−ck​λn−k−⋯−cn​

  举个例子，以下矩阵：

A = ( 2 − 4 1 2 3 − 2 1 5 5 ) B 1 = ( 2 − 4 1 2 3 − 2 1 5 5 ) c 1 = 10 B 2 = ( − 23 25 5 − 12 − 39 6 7 − 14 − 34 ) c 2 = − 48 B 3 = ( 105 0 0 0 105 0 0 0 105 ) c 3 = 105 ∣ λ E − A ∣ = λ 3 − 10 λ 2 + 48 λ − 105 A=\begin{pmatrix}2 & -4 & 1\\ 2 & 3 & -2\\ 1 & 5 & 5\\ \end{pmatrix}\\ B_1=\begin{pmatrix}2 & -4 & 1\\ 2 & 3 & -2\\ 1 & 5 & 5\\ \end{pmatrix}\\ c_1=10\\ B_2 = \begin{pmatrix}-23 & 25 & 5\\ -12 & -39 & 6\\ 7 & -14 & -34\\ \end{pmatrix}\\ c_2=-48\\ B_3=\begin{pmatrix}105 & 0 & 0\\ 0 & 105 & 0\\ 0 & 0 & 105\\ \end{pmatrix}\\ c_3=105\\ |\lambda E-A|=\lambda^3 -10\lambda^2+48\lambda-105 A= ​221​−435​1−25​ ​B1​= ​221​−435​1−25​ ​c1​=10B2​= ​−23−127​25−39−14​56−34​ ​c2​=−48B3​= ​10500​01050​00105​ ​c3​=105∣λE−A∣=λ3−10λ2+48λ−105

Python实现

  算法比较简单，所以代码也相对较短。

    def faddeev_laverrier(self):        n = len(self.__vectors)        b = []        c = []        b.append(self)        c.append(self.trace(1))        e = Matrix(Matrix.unit_matrix(n))        for i in range(1, n):            b_k = self * (b[i - 1] - e * c[i - 1])            print('b',i,'=', b_k.to_latex())            b.append(b_k)            c.append(1 / (i + 1) * b_k.trace(1))        return [1] + [-e for e in c]