上頁 12345678910 次頁

方程式求解問題 (第 8 頁)

康明昌

 

首頁 | 搜尋

.原載於數學傳播第八卷第四期、第九卷第一期
.作者當時任教於台大數學系

註釋
對外搜尋關鍵字
 
八、Sturm 法則

大學教程裡的「方程式論」是以 Galois 理論為主,高中數學的「方程式論」則是處理另外一些問題,如:

1. 代數基本定理:
任意的 n 次複數係數方程式恰有 n 個複數根。 (證明請參閱 L.V. Ahlfors,《Complex analysis》第二版, 122頁;或 P. Samuel《Algebraic theory of numbers》, 44頁。)

2. 根與係數的關係 14

3. 對稱式: x1, x2,…,xn 的任意對稱多項式都可以表示成基本對稱式 $\sigma_1,\sigma_2$,…,$\sigma_n$ 的多項式,其中

\begin{eqnarray*}
\sigma_1&=&x_1+\cdots+x_n,\\
\sigma_2&=&\sum_{1\leq j_1 < j_2...
..._{j_2}\cdots x_{j_i},\\
&&\cdots\\
\sigma_n&=&x_1x_2\cdots x_n
\end{eqnarray*}


4. Cardano 公式與 Ferrari 公式

5. Lagrange 內插公式: 若 a1,…,an 是相異 n 個數,b1,…,bn 是任意 n 個數,則存在唯一的 n-1 次多項式 f(x),滿足 f(ai)=bi, i=1,2,…,n。 事實上 15

\begin{displaymath}
f(x)=\sum_{i=1}^n b_i \cdot \prod_{j \neq i} \frac{x-a_i}{a_i-a_j}
\end{displaymath}

6. 行列式 (determinant) 與 結式 (resultant) 16

7. 實係數方程式根的上、下界。

8. 秦九韶-Horner 近似根求法,Newton 近似根求法。 (請參考,《數學分析導引》上冊,241-244頁與245-247頁,凡異出版社出版。)

9. Descartes符號法則、Fourier-Budan 法則、Sturm 法則。 以下我們僅就 Sturm 法則做詳細討論。

   
 
8.1 實係數方程式實數根的數目

問題:

(1) 方程式 x4+12x2+5x-9=0 有多少正實根?
(2) 更一般的,任給實係數方程式 $f(x)=x^n+a_1x^{n-1}+\cdots+a_{n-1}x+a_n=0$,任給 $a,b \in \mathbf{M}$。試問 f(x)=0[a,b] 有多少(實數)根?

在十七世紀,René Descrates(笛卡爾;1596∼1650)找到一個估計實數根數目的方法。J. Fourier(1768∼1830)早在1797年以前就找到一個更精確的估定方法,不過他只是把這個方法教給他的學生,並沒有把它寫成論文發表出來。1803年 Budan 獨立的發現同樣的方法 17 。 因此我們把這個方法叫做 Fourier-Budan 法則。

在介紹 Descrates 法則與 Fouier-Budan 法則之前,我們先定義變異數的概念。

有限數列 $\{1,-2,-\frac{1}{2},4\}$ 的符號依次是 + - - +。其中第一項與第二項的符號改變,第三項與第四項的符號也改變,我們就說的 $\{1,-2,-\frac{1}{2},4\}$ 變異數是 2。考慮另一個有限數列 {1,0,-2,-4,0,3},我們先把零去掉,再考慮其變異數,因此這個數列的變異數是 2。

以方程式 x5-2x3-4x2+3=0 為例,取出其係數 {1,0,-2,-4,0,3},其變異數是 2,因此其正根的數目(重根要計算其重數)是 2+2l,其中 l 是某個整數。同理,方程式 3x3-x-1=0,其係數的變異數是 1,所以正根的數目是 1+2l,其中 l 是某個整數。現在我們可以敘述 Descartes 符號法則如下:

Descartes 符號法則:
若實係數方程式 $a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0=0$ 的正根數目(重根要計算其重數)是 N,而 v$\{a_n,a_{n-1},\cdots,a_1,a_0\}$ 的變異數,則 $v\geq N$,且 v-N 是一個偶數。

Fourier-Budan 法則比 Descartes 符號更能準確的估計實數根的數目。 以方程式 f(x)=x3-7x-7=0 為例,我們要估計 f(x)=0(3,4) 之間根的數目(重根要計算其重數)。令 f(1)(x)f(x) 的一階導函數, f(2)(x)f(x) 的二階導函數,f(3)(x)f(x) 的三階導函數。 設 v3{ f(3),f(1)(3),f(2)(3),f(3)(3)} 的變異數, v4{ f(4),f(1)(4),f(2)(4),f(3)(4)} 的變異數, 故 v3=1v4=0。詳細計算如下,


\begin{displaymath}
\begin{tabular}{c\vert cccc\vert c}
$x$ & $f(x)$ & $f^{(1)}(...
...& 6 & 0\\
-2& -1 & 5 &-12&6&3\\
-1&-1&-4&-6&6&1
\end{tabular}\end{displaymath}

Fourier-Budan 法則說, 方程式 f(x)=0(3,4) 之間根的數目是 v3-v4-2l=1-2l, 其中 l 是零或某個正整數;方程式 f(x)=0(-2,-1) 之間有 v-2-v-1-2l=2-2l 個根,其中 l 是零或某個正整數; 方程式 f(x)=0(-1,3) 之間有 v-1-v3-2l=-2l 根, 其 l 是零或某個正整數。把這個法則完整的敘述如下

Fourier-Budan 法則:
考慮 n 次的實係數方程式 f(x)=0,且 $f(a),f(b)\neq 0(a<b)$。令 va$\{ f(a),f^{(1)}(a), f^{(2)}(a),\cdots,f^{(n)}(a)\}$ 的變異數, vb$\{ f(b),f^{(1)}(b), f^{(2)}(b), \cdots, f^{(n)}(b)\}$ 的變異數, Nf(x)=0(a,b) 之間根的數目(重根要計算其重數),則 $v_a \geq v_b,v_a-v_b \geq N$,且 va-vb 是一個偶數。

我們不準備證明 Descartes 符號法則與 Fourier-Rudan 法則。 這些證明並不困難,讀者可以自己做或參考,《數學分析導引》(上冊),250-251頁,凡異出版社出版。

   
 
8.2 Sturm 法則

Charles Sturm(1803∼1855)是一個瑞士人,不過他很早就到巴黎定居。Sturm 在數學史上以研究物理數學的偏微分方程聞名,這就是所謂 Sturm-Liouville 理論。 據 Sturm 說,他在研究偏微分方程時,有許多靈感是來自他過去研究實係數方程式根的分布所累積的經驗。事實上他在1929年就提出 Sturm 法則,完全解決實係數方程式根的分布問題。Galois 在數學圈認識的朋友本來不多,而 Sturm 就是這少數人中的一個。據說,Galois 在知道 Sturm 法則的內容之後,他在幾分鐘內就給出一個證明。

以方程式 f(x)=x5+2x4-5x3+8x2-7x-3 為例。

\begin{eqnarray*}
\mbox{{\fontfamily{cwM0}\fontseries{m}\selectfont \char 73}}f_...
...dots \\
f_3(x) &=& q_4(x)f_4(x)-f_5(x), \; \deg f_5 < \deg f_4,
\end{eqnarray*}


f2(x)=66x3-150x2+172x+61f3(x)=-464x2+1135x+723f4(x)=-32599457x-8486093,f5(x)=-1

我們想計算 f(x)=0(1,3) 之間根的數目。 因為 f5(x)=-1f0(x)=f(x)f1(x)=f'(x) 的最大公約式, 故 f(x)=0 沒有重根。注意, $f(1),f(3) \neq 0$

v1{ f0(1),f1(1),f2(1),f3(1),f4(1),f5(1) } 的變異數, v3{ f0(3),f1(3),f2(3), f3(3),f4(3),f5(3) } 的變異數。 則 v1=2v3=1。Sturm 法則說,f(x)=0(1,3) 之間根的數目恰好是 v1-v3=1。所謂 Sturm 法則可以敘述如下:

Sturm 法則(簡單形式):
f(x)=0 是沒有重根的 n 次實係數方程式, 且 $f(a),f(b)\neq 0(a<b)$。 我們要計算 f(x)=O(a,b) 之間根的個數。 定義

\begin{eqnarray*}
f_0(x) &=& f(x),f_1(x)=f'(x),\\
f_0(x)&=&q_1(x)f_1(x)-f_2(x),...
...(x)-f_s(x),\deg f_s < \deg f_{s-1},\\
f_{s-1}(x)&=&q_s(x)f_s(x)
\end{eqnarray*}


vavb 各為 $\{ f_0(a),f_1(a) ,\cdots, f_s(a) \}$$\{ f_0(b),f_1(b)\cdots,f_s(b) \}$ 的變異數。 則 $v_a \geq v_b$,且 f(x)=0(a,b) 之間根的數目恰好是 va-vb

Sturm 法則(一般形式):
f(x)=0 是任意 n 次實係數方程式,且 $f(a),f(b)\neq 0(a<b)$。 定義

\begin{eqnarray*}
f_0(x)&=&f(x),\\
f_1(x)&=&f'(x),\\
f_0(x)&=&q_1(x)f_1(x)-f_2...
...,\deg f_s < \deg f_{s-1},f_s \neq 0\\
f_{s-1}(x)&=&q_s(x)f_s(x)
\end{eqnarray*}


$g_0=\frac{f_0(x)}{f_s(x)},\frac{f_0(x)}{f_s(x)}$$g_s=\frac{f_0(x)}{f_s(x)}=1$, 且 vavb 各為 $\{ g_0(a),g_1(a),\cdots, g_s(a) \}${ g0(b),g1(b),…,gs(b)} 的變異數。 則 $v_a \geq v_b$,且 f(x)=0(a,b) 之間根的數目恰好是 va-vb(重根只計算一次)。

我們現在要證明簡單形式的 Sturm 法則。至於一般形式的 Sturm 法則的證明,讀者不妨自己做做看,或參考 N. Jacobson,《Basic Algebra I》, 295-299頁。先注意以下兩件事,

(1) 若 $a \leq \alpha \leq b$,則 α 不可能是 fi(x)=fi+1(x)=0 的公解,其中 i=0,1,…,s-1

因為,設 $f_i(\alpha)=f_{i+1}(\alpha)=0$,則 $f_{i-1}(\alpha) = q_i(\alpha)f_i(\alpha) - f_{i+1}(\alpha)=0$, 同理 $f_{i-2}(\alpha)=\cdots=f_1(\alpha)=f_0(\alpha)=0$。 故 α 是 f(x)=f'(x)=0 的公解,這與 f(x)=0 沒有重根的假設違反。

(2) 若 $f_i(\alpha)=0$,其中 $1 \leq i \leq s-1$, 則 $f_{i+1}(\alpha)= - f_{i+1}(\alpha)$

因為 $f_{i+1}(\alpha)=g_i(\alpha)f_i(\alpha)-f_{i+1}(\alpha)$ $=-f_{i+1}(\alpha)$

我們開始證明 Sturm 法則。

第一步驟:
xa 變化到 b,考慮 fi(x) 的符號變化的情形, $1 \leq i \leq s-1$。注意,fs(x)f(x)f'(x) 的公因式; 因 f(x)=0 沒有重根,故 fs(x) 恆為常數。

假設 fi(x)$x=\alpha$ 的左邊到右邊變了符號,則 $f_i(\alpha)=0$(勘根定理)。設 $\epsilon>0$ 是足夠小的正數,則 fi-1,fi,fi+1 的符號變化不出以下四種情形:


\begin{displaymath}
\begin{tabular}{\vert c\vert ccc\vert ccc\vert} \hline
& $\...
...$f_{i+1}$ & $-$ & $-$ & $-$ & + & + & + \\ \hline
\end{tabular}\end{displaymath}

說明:由於 fi(x)$x=\alpha$ 變號,故 $f_i(\alpha-\epsilon)$$f_i(\alpha)$$f_i(\alpha+\epsilon)$ 的符號是 $+ \bigcirc +$$- \bigcirc -$。因為 $f_i(\alpha)=0$,利用注意事項(1)與(2), 可知 $f_{i-1}(\alpha)$$f_{i+1}(\alpha)$ 的符號是 $+ \; -$$- \; +$。 因為 $\alpha-\epsilon$,與 $\alpha+\epsilon$。都足夠靠近 α, 故 $f_{i-1}(\alpha-\epsilon)$$f_{i-1}(\alpha+\epsilon)$ 的符號與 $\alpha_{i-1}(\alpha)$ 一致; 同理, $f_{i+1}(\alpha-\epsilon)$$f_{i+1}(\alpha+\epsilon)$ 的符號也和 $f_{i+1}(\alpha)$ 一致。

由上表可知, { fi-1(x),fi(x),fi+1(x)} 的變異數恆為 1, 不管 x$\alpha-\epsilon,\alpha$,或 $\alpha+\epsilon$

第二步驟:
xa 變化到 b,考慮 f0(x) 的符號變化的情形。

因為 f(x)=0 只有單根,如果 α 是 f(x)=0 的根,則 $f(x)=(x-\alpha) \cdot g(x)$, 其中 $g(0) \neq 0$。因此 g(x)$x=\alpha$ 附近不改變符號(勘根定理)。 所以 f(x)$x=\alpha$ 附近一定要改變符號。同時,因為,α 是單根, 故 $f'(\alpha) \neq 0$,可知 fi(x)=f'(x)$x=\alpha$ 附近不改變符號。 這些觀察結果可歸納如下:


\begin{displaymath}
\begin{tabular}{\vert c\vert ccc\vert ccc\vert ccc\vert ccc\...
...\\
$f_1$ & + & + & + & $-$ & $-$ & $-$ \\ \hline
\end{tabular}\end{displaymath}

但是第一(左上)與第四(右下)表是不可能發生:因為,在第一表中, f1(x) = f'(x) >0,故 f0(x)=f(x) 是增加函數,可知 $f(\alpha - \epsilon) >0 > f(\alpha + \epsilon)$ 是不可能的。

因此, { f0(x),f1(x) } 的變異數,在 $x=\alpha - \epsilon$ 時比 $x=\alpha +\epsilon$ 恰好多 1。也就是,每通過一個 f(x)=0 的根,變異數就少 1。

綜合第一與第二步驟,可知 $v_a \geq v_b$,且 va - vb 恰好是 f(x)=0(a,b) 之間根的個數。 18

   

上頁 12345678910 次頁

回頁首
 
(若有指正、疑問……,可以在此 留言寫信 給我們。)
EpisteMath

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有


編輯:朱安強 最後修改日期:4/26/2002