Root Finding

Root

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

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

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

          _________
    -b ± V b2 - 4ac
x = ---------------
          2a

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

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

Root Finding: 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)異號的區間。如果左右兩個區間都確定有根,那麼就只檢查左邊區間。一旦找到根,就馬上結束遞迴。

至於f(a)和f(b)同號的區間、f(a)和f(b)為零的區間,就無法處理了。

這就是二分法。二分法其實也正是Binary Search。

找到所有根

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

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

精確度

分割區間越多次,答案就越精確。

float、double變數,能夠儲存的位數有限,不可能精確,有著一個極限。不斷分割區間,就能到達極限。一個float變數的範圍約為10^38到10^-38,分割區間log₂(10^76) ≒ 252次,定能得到float變數所能儲存的最精確的數值。

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

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

範例:求平方根

嚴格遞增函數

連續函數,嚴格遞增(減);若有根,保證只有一個根。

Root Finding: Secant Method

割線法

一張圖勝過千言萬語。

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

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

Root Finding: Newton's Method

牛頓法

割線法採用割線,牛頓法採用切線。牛頓法的收斂速度比較快,但是計算時間比較多。

如果給定的函數,其導數不需要dx,例如多項式函數,那麼我們可以預先用紙筆推導導數式子,讓計算結果更精準。

凸函數

連續函數,斜率嚴格遞增(減);若有根,牛頓法能找到根。

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

連續函數,斜率嚴格遞增(減),正是凸(凹)函數:函數圖形上面任意劃一道割線,總是凸出來的函數。

Fixed Point Finding

Fixed Point

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

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

求根、求不動點,本質上是同一件事情。求根變成求不動點:等號兩邊同時加上x。求不動點變成求根:等號兩邊同時減去x。

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

數學系課程才會介紹不動點,相信大家完全沒印象。然而在計算學當中,不動點擁有超高效率演算法,是一大利器。

Eigenpoint【尚無專有名詞】

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

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

求根、求特徵點,本質上是同一件事情。求根時,將函數乘上任意倍率,根依然相同──如此就變成了求特徵點。

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

Fixed Point Finding: 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 < |λ|               夾在±λ之間

Lipschitz Function

方才的函數條件,再添上等號,稱作Lipschitz Function。

Equation Solving

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 finding
f(x) + x = x          --->  g(x) = x      fixed point finding
λf(x) + λx = λx       --->  h(x) = λx     eigenpoint finding
λf(x) + λq(x) = q(x)  --->  p(x) = q(x)   equation solving

UVa 358 10341 10428 10566 10668 11277

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

Increasing Function:遞增函數。輸入變大,輸出也跟著變大的函數。適合Bisection Method。

Convex Function:凸函數。隨便劃一道割線,函數曲線總是凹下去的函數。凸函數的斜率是遞增函數。適合Newton 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

我沒有研究。