Root

Root

找到確切的輸入數值,讓輸出數值是零,稱作「求根」。這樣的輸入,稱作「根」,可能有許多個、也可能不存在。

以函數圖形表達函數的根:當輸入變數只有一個,是函數曲線與X軸的相交之處。當輸入變數只有兩個,是函數曲面與XY平面的相交之處。當輸入變數有許多個,請讀者自行推廣。

中學數學談過多項式函數的求根,相信大家印象深刻。比如一元二次多項式函數的求根(解一元二次多項式方程式),有個號稱數學界最難背的公式:二a分之負b正負根號b平方減四ac。

          _________
    -b ± V b² - 4ac
x = ———————————————
          2a

以下則是談一般的函數的求根。多項式函數,性質優美,擁有特定公式;一般的函數,雜亂無章,沒有固定公式,只好利用電腦了。最簡單的求根演算法,就是窮舉法:窮舉各種輸入,看看輸出是不是零。

窮舉法非常慢。接下來介紹更快的方法。

Root: Bisection Method

用途

用來找到連續函數的根。bi-這個字首是「雙」的意思,而section是「分段」的意思。中文譯作「二分法」。

勘根定理

解釋演算法之前,得先複習一下高中數學的「勘根定理」。

連續函數的圖形當中,當起點與終點分別在X軸的兩側,那麼一定在某處穿過X軸。換句話說,在某處有根。換句話說,至少有一個根。

以數學符號說明勘根定理

連續函數f(x),任意區間[a,b]。a和b分別代入f(x),得到f(a)和f(b)。

如果f(a)和f(b)是一正一負、是異號,即f(a) f(b) < 0,就表示座標(a, f(a))和座標(b, f(b))這兩點位於X軸的兩側。因為f是連續函數,所以座標(a, f(a))到座標(b, f(b))的路線,一定碰到X軸至少一次──區間[a,b]裡面至少有一個根。

如果f(a)和f(b)是同號,即f(a) f(b) > 0,就表示座標(a, f(a))和座標(b, f(b))這兩點位於X軸的同側──區間[a,b]裡面可能有根,也可能無根。

如果f(a)和f(b)有零,即f(a) f(b) = 0,此時a和b就是根──區間[a,b]裡面可能還有其他根,也可能無根。

另外,當[a,b]的端點恰好沒有定義在f(x)當中,則無法計算出f(a)和f(b)的值。要解決這個問題,可以將區間略微縮小一些,像是[a + 0.001, b - 0.001],即可避免端點沒有定義的情況。

二分法

區間切兩半,縮小區間,夾擠根,逼近根。

遞迴下去,直到區間足夠微小。

找到一個根

左右兩個區間都處理,結果跟窮舉法沒兩樣。

不如只處理其中一個區間吧!只處理確定有根的區間,即f(a)和f(b)異號的區間。如果左右兩個區間都確定有根,那麼就只處理左邊區間。這正是Binary Search。

f(a)和f(b)同號的區間,放棄處理,不確定是否有根。f(a)和f(b)為零的區間,中止處理,顯然已經找到一個根。f(a)和f(b)異號的區間,繼續處理,二分尋找根。

最小精確度

二分越多次,答案越精確。

float變數、double變數,能夠儲存的位數有限,不可能精確,有著一個極限。不斷分割區間,就能到達極限。一個float變數的範圍約為10³⁸到10⁻³⁸,分割區間log₂10⁷⁶ ≈ 252次,定能得到float變數所能儲存的最精確的數值。

據我測試,不管迴圈計算多少遍,a b的大小關係永遠不變,而c永遠會在[a,b]當中,不會超出範圍。

迴圈不斷計算之後,有些函數造成a b最終相等,也有些函數造成a b永遠不相等,永遠相差一個最小精確度的值。要解決不相等的問題,只需判斷c是a或是b即可。

自訂精確度

[a,b]寬度大於自訂精確度,就繼續分割區間。[a,b]寬度小於等於自訂精確度,就立即停止迴圈。因為c永遠在[a,b]當中,所以c的誤差不超過自訂精確度。

如此一來,得以減少迴圈次數,不必做到252次。

找到所有根

整條數線細分成許多微小區間。f(a)和f(b)同號的區間,視作沒有根;f(a)和f(b)為零的區間,視作只有端點有根;f(a)和f(b)異號的區間,視作剛好有一個根,實施二分法找到根。

只要細分的足夠細膩,理論上可以找到所有根,除了一種例外:根恰好是局部極值。此時必須配合其他的求根方法,才能處理這個例外。

範例:求平方根

遞增函數

連續遞增(減)函數,若有根,保證能找到根。

二分法不斷地縮小根的範圍。

Root: Newton's Method

牛頓法

一張圖勝過千言萬語。

範例:求平方根

x = sqrt(n)
x² = n
x² - n = 0
f(x) = x² - n
f′(x) = 2x

凸函數

斜率是連續遞增(減)函數,若有根,保證能找到根。

以斜率的觀點來看,牛頓法不斷地縮小斜率範圍。

Root: Secant Method

割線法

牛頓法採用切線,割線法採用割線。

缺點:遞推次數更多、計算步驟更多。優點:不用微分。

一開始選定的兩點,如果不夠靠近根,割線可能會亂跑。

運氣不好時,割線呈水平線,割線法會故障;割線趨近水平線,下一點會溢位。

Fixed Point

Fixed Point(Fixpoint)

找到確切的輸入數值,讓輸出和輸入完全一樣。這樣的輸入稱作「不動點」。可能有許多個,也可能不存在。

以函數圖形表達函數的不動點:當輸入變數只有一個,是函數曲線與直線y = x的相交之處。當輸入變數超過一個,此處不討論。

Eigenpoint【尚無正式名稱】

找到確切的輸入數值,讓輸出是輸入的倍數,倍數是某個定值。這樣的輸入稱作「特徵點」。可能有許多個,也可能不存在。

以函數圖形表達函數的特徵點:當輸入變數只有一個,是函數曲線與直線y = λx的相交之處。當輸入變數超過一個,此處不討論。

求根、求不動點、求特徵點,本質上是同一件事情。

求根變成求不動點:等號兩邊同時加上x。求不動點變成求根:等號兩邊同時減去x。

f(x) = 0   <--->   f(x) + x = x   <--->   g(x) = x

求根變成求特徵點:再乘上任意倍率。求特徵點變成求根:反向操作。

f(x) = 0   <--->   λ (f(x) + x) = λx   <--->   h(x) = λx

只要知道怎麼求不動點、特徵點,就能求根。碰巧的是,不動點擁有高速演算法!

Fixed Point: Fixed Point Iteration

不動點遞推法

不斷代入上次求得的數值。就這麼簡單。

即是在函數圖形與45°斜線之間往返。越走越小圈、越走越近。

運氣不好時,無法得到不動點。

越走越大圈、越走越遠。

程式碼很短,只有一個迴圈。

平緩函數:斜率絕對值小於1的連續函數

遭遇不動點,其中一種情況,就是步伐越來越短。測量X軸方向的步伐大小,即是x₀ x₁ x₂……之間的間距。當間距越來越小,最後xₜ = xₜ₊₁ = f(xₜ)趨近相等,遭遇不動點xₜ。

此處只討論這種情況。

|x₁ - x₀| > |x₂ - x₁| > |x₃ - x₂| > ......

|x₁ - x₀| > |x₂ - x₁|   此處以開頭兩項為例。事實上任意相鄰兩項都成立。

|x₁ - x₀| > |f(x₁) - f(x₀)|

    |f(x₁) - f(x₀)|   
1 > ——————————————— = |slope|
       |x₁ - x₀|      

|slope| < 1

-1 < slope < 1

先後間距變小,移項之後,割線斜率介於±1。

也就是說,一個連續函數,任意兩點的割線的斜率的絕對值都小於1,保證有不動點。無論起點在哪裡,都能找到不動點。

換句話說,切線的斜率的絕對值都小於1。不太斜的連續函數。

特徵點遞推法

在函數圖形與斜率λ的直線之間往返。上次求得的數值,除以λ之後才代入。

平緩函數:斜率絕對值小於|λ|的連續函數

遭遇特徵點,其中一種情況,就是步伐越來越短。中略。割線的斜率介於±λ。

|x₁ - x₀| > |x₂ - x₁| > |x₃ - x₂| > ......

|x₁ - x₀| > |x₂ - x₁|   此處以開頭兩項為例。事實上任意相鄰兩項都成立。

|x₁ - x₀| > |f(x₁/λ) - f(x₀/λ)|   上次求得的數值,除以λ之後才代入。

|λχ₁ - λχ₀| > |f(χ₁) - f(χ₀)|     變數代換

|λ| |χ₁ - χ₀| > |f(χ₁) - f(χ₀)|

      |f(χ₁) - f(χ₀)|   
|λ| > ——————————————— = |slope|
         |χ₁ - χ₀|      

|slope| < |λ|

-|λ| < slope < |λ|               介於±λ

Equation

Equation

由未知數(變數)、已知數(常數)的各種運算來構成式子。兩個相等的式子,就叫作「方程式」。

2x + 1 = (4x² + 3) / (x - 1)

方程二字借自中國古代數學書籍,意義相去甚遠,是個不精準的翻譯。按照英文字面意義來翻譯,應該稱作「等式」才對。

中學數學教了很多方程式的計算,例如解一元二次方程式、解聯立方程式,並且搭配幾何學一起講解。大學指考前,算了千百次,應當難不倒各位。

方程式有什麼用途呢?其實就是設x、解x。這兩件事情很難用中文講個明白,不過只要經歷許多數學題目之後,自然而然就能體會到設x、解x的精神所在。

求根、求不動點、求特徵點、求解,本質上是同一件事情。

方程式重新整理成函數的模樣,就能求解。

2x + 1 = (4x² + 3) / (x - 1)

等量減法公理,兩邊同減一樣多的東西。(移項)
2x + 1 - (4x² + 3) / (x - 1) = 0

整理成函數的模樣,然後求根即可!
f(x) = 2x + 1 - (4x² + 3) / (x - 1)

方程式重新整理成函數的模樣,就能以各種姿勢求解。

f(x) = 0                                  root
f(x) + x = x          --->  g(x) = x      fixed point
λf(x) + λx = λx       --->  h(x) = λx     eigenpoint
λf(x) + λq(x) = q(x)  --->  p(x) = q(x)   solution

UVa 358 10341 10428 10566 10668 11277

容易求根、求不動點、求特徵點、求解的函數類型

Increasing Function:遞增函數。輸入變大,輸出跟著變大(或不變)。斜率是正數(或零)。適合Bisection Method。

Convex Function:凸函數。隨便劃一道割線,函數曲線總是凹下去(或平貼)。斜率是遞增函數。適合Newton's Method。

Lipschitz Function:平緩函數。隨便劃一道割線,斜率的絕對值小於(或等於)一個定值。適合Fixed Point Iteration。

Polynomial Function:多項式函數。可以手工推導公式解,也可以使用上述演算法求解。

大家習慣改成嚴格版本、去掉等號,讓函數曲線不會平貼座標軸、不會產生無限多根。

System of Equations(Simultaneous Equations)

許多道方程式同時成立,整體稱作「方程組」或者「聯立方程式」。

⎧ 1 x + 2 y - 4 sin(z) = 1
⎨ 2 x - 4 y + 2 cos(z) = 2
⎩ 3 x + 1 y + 1 exp(z) = 3

Inequality

Inequality(Inequation)

「不等式」。等號=改成了小於<、大於>、小於等於≤、大於等於≥、不等於≠。

2x + 1 < (4x² + 3) / (x - 1)

System of Inequalities

「不等式組」、「聯立不等式」。許多道不等式同時成立。

⎧ 1 x + 2 y - 4 sin(z) < 1
⎨ 2 x - 4 y + 2 cos(z) ≤ 2
⎩ 3 x + 1 y + 1 exp(z) > 3

不等式可以重新整理成函數的模樣。

大於可以重新整理成小於。

⎧  1 x + 2 y - 4 sin(z) - 1 < 0          ⎧ f(x,y,z) < 0
⎨  2 x - 4 y + 2 cos(z) - 2 ≤ 0   --->   ⎨ g(x,y,z) ≤ 0
⎩ -3 x - 1 y - 1 exp(z) + 3 < 0          ⎩ h(x,y,z) < 0

Constraint Satisfaction

「約束滿足」。許多道等式與不等式同時成立。