窮人的多項式求根法

本文的閱讀等級:初級

給定三次多項式

\displaystyle  p(x)=x^3-6x^2-72x-27

如何求得 p(x) 的三個根?你可以購買一套商用數學軟體或使用校園授權軟體 (費用已經隱藏在繳交的學費中)。例如,MATLAB,輸入兩個指令:

    p = [1 -6 -72 -27];
    r = roots(p)

馬上就得到答案:

    r =
          12.1229
          -5.7345
          -0.3884

如果你近來阮囊羞澀或無法取得校園授權軟體,是否還有其他不用花錢的便捷方法?易經曰:「窮則變,變則通,通則久。」下面我介紹一個窮人的多項式求根法。首先我們要備妥一個免費的矩陣特徵值計算程式,譬如,具有多種功能的線上矩陣計算器 Online Matrix Calculator。在主畫面視窗鍵入三次多項式 p(x)3\times 3 階相伴 (companion) 矩陣

\displaystyle  \left[\!\!\begin{array}{rrc}  0&1&0\\  0&0&1\\  27&72&6  \end{array}\!\!\right]

勾選 Eigenvalues/eigenvectors,按下 Calculate,可得三個特徵值,此即為三次多項式 p(x) 的根。事實上,MATLAB 採用完全相同的多項式求根算法[1]。有錢或沒錢的差別待遇往往僅在於外表包裝不同而已。

 
考慮 n 次多項式

\displaystyle  f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0,~~a_n\neq 0

上式通除非零常數 a_n 不會改變多項式的根,故可設首一 (領先係數為 1) 多項式

\displaystyle  p(x)=x^n+c_{n-1}x^{n-1}+\cdots+c_1x+c_0

其中 c_i=a_i/a_ni=0,1,\ldots,n-1。對於 n 次首一多項式 p(x),我們定義 n\times n 階相伴矩陣

\displaystyle  C=\begin{bmatrix}  0&1&0&\cdots&0\\  0&0&1&\cdots&0\\  \vdots&\vdots&\ddots&\ddots&\vdots\\  0&0&0&\cdots&1\\  -c_0&-c_1&-c_2&\cdots&-c_{n-1}  \end{bmatrix}

相伴矩陣 C 的特徵多項式 \det(xI-C) 即為 p(x) (見“每週問題 January 18, 2010”),因此 C 的特徵值就是 p(x) 的根。下面提供一個簡易的證法。設 \lambdap(x) 的一根,故 p(\lambda)=\lambda^n+\sum_{i=0}^{n-1}c_i\lambda^i=0。令 \mathbf{x}=(1,\lambda,\lambda^2,\ldots,\lambda^{n-1})^T。計算

\displaystyle\begin{aligned}  C\mathbf{x}&=\begin{bmatrix}  0&1&0&\cdots&0\\  0&0&1&\cdots&0\\  \vdots&\vdots&\ddots&\ddots&\vdots\\  0&0&0&\cdots&1\\  -c_0&-c_1&-c_2&\cdots&-c_{n-1}  \end{bmatrix}\begin{bmatrix}  1\\  \lambda\\  \vdots\\  \lambda^{n-2}\\  \lambda^{n-1}  \end{bmatrix}\\  &=\begin{bmatrix}  \lambda\\  \lambda^2\\  \vdots\\  \lambda^{n-1}\\  -\sum_{i=0}^{n-1}c_i\lambda^i  \end{bmatrix}=\begin{bmatrix}  \lambda\\  \lambda^2\\  \vdots\\  \lambda^{n-1}\\  \lambda^n  \end{bmatrix}=\lambda\begin{bmatrix}  1\\  \lambda\\  \vdots\\  \lambda^{n-2}\\  \lambda^{n-1}  \end{bmatrix}=\lambda\mathbf{x},\end{aligned}

得知 \lambdaC 的特徵值,\mathbf{x} 是對應的特徵向量。令 C\mathbf{x}_i=\lambda_i\mathbf{x}_i1\le i\le n,其中 \mathbf{x}_i=(1,\lambda_i,\lambda_i^2,\ldots,\lambda_i^{n-1})^T 為對應特徵值 \lambda_i 的特徵向量。合併 n 個特徵向量,可得下列 Vandermonde 矩陣

\displaystyle  V=\begin{bmatrix}  \mathbf{x}_1&\mathbf{x}_2&\cdots&\mathbf{x}_n  \end{bmatrix}=\begin{bmatrix}  1&1&\cdots&1\\  \lambda_1&\lambda_2&\cdots&\lambda_n\\  \lambda_1^2&\lambda_2^2&\cdots&\lambda_n^2\\  \vdots&\vdots&\ddots&\vdots\\  \lambda_1^{n-1}&\lambda_2^{n-1}&\cdots&\lambda_n^{n-1}  \end{bmatrix}

即有 CV=V\hbox{diag}(\lambda_1,\ldots,\lambda_n)。若 C 有相異的特徵值,則 V 是可逆的 (見“特殊矩陣 (8):Vandermonde 矩陣”),這時 C 可對角化為 V^{-1}CV=\hbox{diag}(\lambda_1,\ldots,\lambda_n)。如果 C 有相重的特徵值,則 V 是不可逆的,且 C 不可對角化 (證明涉及最小多項式,詳見“多項式的相伴矩陣”)。

 
註解
[1] MATLAB: Polynomial roots 下面是 roots 所對應的指令:
      A = diag(ones(n-1,1),-1);
      A(1,:) = -p(2:n+1)./p(1);
      eig(A)

Advertisements
本篇發表於 線性代數專欄, 應用之道 並標籤為 , , , 。將永久鏈結加入書籤。

6 則回應給 窮人的多項式求根法

    • ccjou 說道:

      Wolfram 當然合用,可這樣就沒有相伴矩陣的故事好寫了。好比電影法則,如果警察太早出場(或不夠笨),主角便沒機會獨自一人奮力殺光所有的壞蛋。

  1. kafuka 說道:

    有两个非常小的typo,矩阵 C 第三行的第三个省略号因为 \vdots

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s