[C語言數值分析] 非線性方程式求解 - 勘根定理－Edison.X. Blog

[回目錄]

非線性方程式與線性方程式

實數係函數種類，不是很正式的分法，區分下面幾種

(1) 常數函數 (constant function)： f(x) = C

(2) 多項式函數 (polynomial function)： f(x) = a0 + a1x^1 + a2x^2+...+anx^n

(3) 線性函數 (linear function)：f(x) = a0 + a1x，也可表示為 y = ax + b，只要不屬於此型態表示法者均為非線性函數。故多項式函數屬非線性函數。

而上可知，多項式函數屬於非線性函數之一種。

而非線性函數，也不只多項式函數一種，大致以下粗分

(1) 多項式函數(polynomial function)： y = f(x) = a0 + a1x^1 + a2x^2+...+anx^n ，上面提過了。

(2) 有理函數 (rational function)：y=f(x) / g(x)，同為多項式函數相除結果。

(3) 超越函數(trancedental function)：其他有看到三角函數、對數、指數等所組成，就叫超越函數。

該如何直接求得非線性方程式之解

單以 y = x^2 + 2x -3 這類型多項式函數而言，要求得其根並不難，只要進行因式分解即可。

甚至在高次之多項式函數時，一次因式判別定理也有機會得到一組有理根，

但因式判別定理判別的是有理根，不是實根，所以根號 2 這些無理數試不出來，

甚至複雜一點的超越函數：f(x) = y = x * sin(2x) - 3*x^2*cos( sin(2x) ) 之類的函式，

這用筆算幾乎是求不出根，大多情況下，直接使用一些近似法方式去取得根。

故針對問題：「如何直接求得非線性方程式之解」，目前沒這方法。

在面對複雜之超越函數或高次多項式函數時，大多都是先進行初步分析，

先將解之可能範圍縮小，再對此範圍進行求解。

至於要如何從 [-∞，∞」將範圍縮小到 [a, b] ，這是接下來要討論的問題。

勘根定理

在給定 f(x) 函數如上圖之情況下，該如何判別 [a,b] 間有沒有根的存在？

先以簡單的單調函數為例，看以下的函數圖形

若 f(x) 為單調函數時，當 f(a) * f(b) < 0 的時候，便可知在 [a, b] 間有一組解，

其情況包含了以下圖型之兩種。

注意到，事實上應該是 f(a) * f(b) <= 0 才對，當 0 發生時，代表 a 或 b 其中一點為一組解。

而當 f(a) * f(b) > 0 時，對單調函數而言，該區間沒有解，可能圖形如下。

剛剛所強調的是「單調函數」，但若非單調函數的話，上述情況必須做一點修改。

若 f(a) * f(b) <= 0 ，則 [a, b] 必包含 "單數個實根"

可能圖形如下所示

上圖之 f(a) * f(b) < 0，但實際上卻有 3 個實根，

然而使得 f(a) * f(b) < 0 之情況，只要在 [a,b] 區間有，

有單數個實根即可，故此判別法並不能完全保證 [a,b] 之間只有唯一解，

但若 [a,b] 本身距離短時，幾乎不會有這種情形發生。

那為何不會有 2 個、4個實根之情況？看圖便知

上圖裡， f(x) 在 [a,b] 區間中有二個實根，不論圖形是上凹或下凹，

f(a) , f(b) 正負號必相同，故使得 f(a) * f(b) >0 必成立。

整理一下勘根定理講了什麼

(1) 若 f(a) * f(b) <=0 ，則代表 f(x) 函數在 [a,b] 區間中，至少有一實數根 (有可能更多)

(2) 若 f(a) * f(b) > 0，則代表 f(x) 函數在 [a, b] 區間中，有可能有實根，也有可能沒實根。

上面第二句聽起來很像廢話，但主要是在敘述，即使用勘根定理，也可能會有「漏根」的情況發生。

一般分析法則

一般在分析時，常先找一區域，判斷該區域是否有可能有解，再進行細部搜尋；

假設 f(2) * f(10) < 0 ，便代表了 f(x) 於 [2, 10] 裡至少包含了一根；

然而若 f(2) * f(10) > 0 ，可能表代了 f(x) 於 [2,10] 裡沒根，也可能是偶數個根，

故區間若切太大，容易造成「缺根」之情形；

但若在沒事前分析情況下，區間切太小，卻又在「判斷有沒有根」這件事上花費時間，

故強調，在進行非線性方程式求解前，應先分析該問題，以先縮小根可能存在範圍為佳。

C 程言程式碼

/*******************************************************************/
/*                                                                 */
/*     filename : HasRoot.c                                        */
/*     author   : edison.shih/edisonx                              */
/*     compiler : Visual C++ 2008                                  */
/*     date     : 2011.03.07                                       */
/*                                                                 */
/*         A.L.L.      R.I.G.H.T.S.     R.E.S.E.R.V.E.             */
/*                                                                 */
/*******************************************************************/

#include <stdio.h>
double func(double x)
{
     double x2=x*x, x3=x2*x;
     return (x3 - 5.48*x2 - 1.4883*x + 20.394828);
}

int HasRoot(double low, double up, double (*fx)(double))
{
     return fx(low) * fx(up) <= 0.0;
}

int main()
{
     const double low = -10.0;
     const double up = +10.0;
     double x;
     for(x=low; x<=up; x+=1.0)
           if(HasRoot(x, x+1.0, func))
                printf("\n> There is one least root at [ %+5.2lf , %+5.2lf ] ", x, x+1.0);
     return 0;
}