跳转至

代數基本定理

定義

任何復係數一元 \(n\) 次多項式（\(n\) 至少為 \(1\)）方程在複數域上至少有一根。

由此推出，\(n\) 次復係數多項式方程在複數域內有且只有 \(n\) 個根，重根按重數計算。

有時這個定理也表述為：

任何一個非零的一元 \(n\) 次復係數多項式，都正好有 \(n\) 個複數根。

代數基本定理的證明，一般會用到複變函數或者近世代數，因此往往作為一個熟知結論直接應用。

根據代數基本定理，一個復係數多項式 \(f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0\) 一定可以唯一地分解為：

\[ f(x)=a_n{(x-x_1)}^{k_1}{(x-x_2)}^{k_2}\ldots{(x-x_t)}^{k_t} \]

其中各個根均為複數，\(k_1+k_2+\ldots+k_t=n\)。

虛根成對定理

代數基本定理的研究對象是復係數多項式。當對實係數多項式進行研究時，雖然也能分解出複數根，卻需要將研究範圍擴大，不太方便。

虛根：非實數根。

定理：實係數多項式的根的共軛複數也是該多項式的根。

證明：直接在代數基本定理的等式兩端取共軛即證畢。

如果根本身是實數，則取共軛仍為它本身，不受影響。

如果根是虛根，則虛根的共軛複數也是原多項式的根。那麼，兩個虛根就可以配對。

定理：實數係數方程的共軛虛根一定成對出現，並且共軛虛根的重數相等。

證明：假設一個根為 \(a+b\mathrm{i}\)，則另一個根為 \(a-b\mathrm{i}\)。這意味着在分解式中存在兩項：

\[ (x-a-b\mathrm{i})(x-a+b\mathrm{i})=x^2-2ax+a^2+b^2 \]

可以看到兩項乘在一起，各項係數會全部變為實數。這個等式右端的二次實係數多項式整除原始的多項式。

於是，在代數基本定理的等式中，兩遍同時除以這個二次三項式，得到的仍舊是實係數多項式的等式。對新等式重複操作，隨着次數的下降，若干次後即不存在虛根。

因此，每對共軛虛根的重數相等。證畢。

以下是虛根成對定理的推論：

  • 實係數奇次多項式至少有一個實根，並且總共有奇數個實根。
  • 實係數偶次多項式可能沒有實根，總共有偶數個實根。

稱上述二次三項式 \(x^2-2ax+a^2+b^2=x^2+px+q\) 為二次實係數不可約因式。不可約是指它在實數範圍內不可約。

定理：實係數多項式一定是一次或者二次實係數不可約因式的積。

證明：

只要實係數多項式有一個實根 \(c\)，就有一個實係數因式 \(x-c\) 和它對應；有一對虛根 \(a\pm b\mathrm{i}\)，就有一個實係數因式 \(x^2-2ax+a^2+b^2\) 和它對應。

因此，只要在原始的代數基本定理分解式中，利用虛根成對定理進行配對，即證畢。

根據虛根成對定理，一個實係數多項式 \(f(x)=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_0\) 一定可以唯一地分解為：

\[ f(x)=a_n{(x-x_1)}^{k_1}{(x-x_2)}^{k_2}\ldots{(x-x_t)}^{k_t}{(x^2+p_1x+q_1)}^{l_1}{(x^2+p_2x+q_2)}^{l_2}\ldots{(x^2+p_sx+q_s)}^{l_s} \]

其中各項係數均為實數，\(k_1+k_2+\ldots+k_t+2(l_1+l_2+\ldots+l_s)=n\)。

林士諤算法

簡介

怎樣對實係數多項式進行代數基本定理的分解？如果將數域擴充至複數會很複雜。

如果只在實數範圍內進行分解，只能保證，當次數大於 \(2\) 的時候，一定存在實係數二次三項式因式。

這是因為，如果該多項式有虛根，直接湊出一對共軛虛根即可。如果該多項式只有實根，任取兩個實根對應的一次因式乘在一起，也能得到實係數二次三項式因式。

找到二次三項式因式之後，再從二次式中解實根或復根就極為容易。於是便有逐次 找出一個二次因子 來求得方程的復根的計算方法，這種方法避免了複數運算。

在 1940 年 8 月、1943 年 8 月和 1947 年 7 月，林士諤先後在 MIT 出版的《數學物理》雜誌上接連正式發表了 3 篇關於解算高階方程式復根方法的論文1，每次均有改進。

這個方法今天還在現代計算機中進行快速運算，計算機程序包（如 MATLAB）中的多項式求根程序依據的原理也是這個算法。

過程

要想找到一個二次三項式因子，就要將多項式分解為：

\[ f(x)=(x^2+p_1x+q_1)g(x) \]

由於無法一下子找到二次三項式因子，按照迭代求解的思路，對於初始值有：

\[ f(x)=(x^2+px+q)g(x)+rx+s \]

會產生一個一次式作為餘項。只要餘項足夠小，即可近似地找到待求因子。

我們希望最終解是初始值加一個偏移修正：

\[ p_1=p+dp \]
\[ q_1=q+dq \]

餘式中的兩個數 \((r, s)\) 由除式的給定係數 \((p, q)\) 決定。有偏導數關係：

\[ dr=\frac{\partial r}{\partial p}dp+\frac{\partial r}{\partial q}dq \]
\[ ds=\frac{\partial s}{\partial p}dp+\frac{\partial s}{\partial q}dq \]

在初始的等式中，被除式 \(f(x)\) 是給定的，商式 \(g(x)\) 和餘式 \(rx+s\) 隨着除式 \(x^2+px+q\) 的變化而變化。因此有偏導數關係

\[ 0=xg(x)+\frac{\partial g(x)}{\partial p}(x^2+px+q)+\frac{\partial r}{\partial p}x+\frac{\partial s}{\partial p} \]
\[ 0=g(x)+\frac{\partial g(x)}{\partial q}(x^2+px+q)+\frac{\partial r}{\partial q}x+\frac{\partial s}{\partial q} \]

注意到，偏導數只是一個數值，與變元 \(x\) 無關。因此有整除關係

\[ xg(x)=-\frac{\partial g(x)}{\partial p}(x^2+px+q)-\frac{\partial r}{\partial p}x-\frac{\partial s}{\partial p} \]
\[ g(x)=-\frac{\partial g(x)}{\partial q}(x^2+px+q)-\frac{\partial r}{\partial q}x-\frac{\partial s}{\partial q} \]

這裏的結論是，待求的偏導數，恰好是對商式繼續做除法的餘式。多項式對給定二次三項式的除法，直接計算即可。這裏就求得了四個偏導數。

我們希望 \(s\) 和 \(r\) 加上偏移 \(ds\) 與 \(dr\) 得到 \(0\)，即 \(ds\) 與 \(dr\) 是 \(s\) 和 \(r\) 的相反數。因此要解方程：

\[ -\frac{\partial r}{\partial p}dp-\frac{\partial r}{\partial q}dq=r \]
\[ -\frac{\partial s}{\partial p}dp-\frac{\partial s}{\partial q}dq=s \]

從上述方程組中解得 \(p\) 和 \(q\) 相應的偏移 \(dp\) 和 \(dq\)，直接用二階行列式求解即可。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// a 是原始的多項式，n 是多項式次數，p 是待求的一次項，q 是待求的常數項
void Shie(double a[], int n, double *p, double *q) {
  // 數組 b 是多項式 a 除以當前迭代二次三項式的商
  memset(b, 0, sizeof(b));
  // 數組 c 是多項式 b 乘以 x 平方再除以當前迭代二次三項式的商
  memset(c, 0, sizeof(c));
  *p = 0;
  *q = 0;
  double dp = 1;
  double dq = 1;
  while (dp > eps || dp < -eps || dq > eps || dq < -eps)  // eps 自行設定
  {
    double p0 = p;
    double q0 = q;
    b[n - 2] = a[n];
    c[n - 2] = b[n - 2];
    b[n - 3] = a[n - 1] - p0 * b[n - 2];
    c[n - 3] = b[n - 3] - p0 * b[n - 2];
    int j;
    for (j = n - 4; j >= 0; j--) {
      b[j] = a[j + 2] - p0 * b[j + 1] - q0 * b[j + 2];
      c[j] = b[j] - p0 * c[j + 1] - q0 * c[j + 2];
    }
    double r = a[1] - p0 * b[0] - q0 * b[1];
    double s = a[0] - q0 * b[0];
    double rp = c[1];
    double sp = b[0] - q0 * c[2];
    double rq = c[0];
    double sq = -q0 * c[1];
    dp = (rp * s - r * sp) / (rp * sq - rq * sp);
    dq = (r * sq - rq * s) / (rp * sq - rq * sp);
    *p += dp;
    *q += dq;
  }
}

參考資料與註釋

  1. 林士諤。論劈因法解高階特徵方程根值的應用問題。數學進展，1963(03):207-217. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用