Ridders' method的推導過程?

Ridder's method 並沒有要求 g(x)=f(x)e^((x-x1)Q) 必須變成

直線函數, 只是要求 g(x_3) 與 g(x_1), g(x_2) 共線, 其中 x_3

是 x_1 與 x_2 的中點.

Ridder's method 先將 f(x) 轉換成 g(x), 藉由

    f(x) = 0 if and only if g(x) = 0

將解方程式 f(x) = 0 的問題變成解 g(x) = 0.

與 Ridder's method 相關的有二分法與割線法. 二分法先取二點 

x_1, x_2 使 f(x_1)f(x_2) < 0, 然後取中點 x_3= (x_1+x_2)/2 

來縮小根所在範圍. 割線法則是在 x_1 與 x_2 之間用一直線近似 

f(x). 設

    y_1= f(x_1), y_2= f(x_2), 

則 f(x)=0 之直線近似解 x_4, 依直線插補原理:

     (0 - y_1)/(x_4 - x_1) = (y_2 - y_1)/(x_2 - x_1)

得

    x_4 = x_1 - (x_2-x_1)y_1/(y_2-y_1)

           = (x_1 y_2 - x_2 y_1)/(y_2 - y_1)

           = x_2 - (x_2-x_1)y_2/(y_2-y_1)

令 g_1 = g(x_1), g_3 = g(x_3). 將上述割線法之 x_4 算法代

入, 得

    x_4 = x_3 - g_3(x_3-x_1)/(g_3-g_1)

但記得 g_3 要滿足 g_3 = (g_1+g_2)/2, 也就是

    y_3 e^[Q(x_2-x_1)/2] = {y_1 + y_2 e^[Q(x_2-x_1)]}/2

令 t = e^[Q(x_2-x_1)/2], 則 e^[Q(x_2-x_1)] = t^2, 上列條

件即

    y_1 - 2y_3 t + y_2 t^2 = 0

解 t 得

    t = {2y_3 ±√[(2y_3)^2 - 4y_1 y_2]}/(2 y_2)

      = {y_3 ±√[(y_3)^2-y_1 y_2]}/y_2

注意 t > 0, 因此上式雖有 "±" 二解, 實際上 t 可能無(實)解, 

二 解, 或恰一 (正) 解. 

將上列 t 之解代入 x_4 公式:

    x_4 = x_3 - y_3 t (x_3-x_1)/(y_3 t - y_1)

注意

   y_3 t/(y_3 t - y_1) 

    = (y_3 t y_2)/(y_3 t y_2 - y_1 y_2)

              y_3{y_3±√[(y_3)^2-y_1y_2]}

    = ---------------------------------------------------------   

        {(y_3)^2±y_3√[(y_3)^2-y_1y_2] - y_1y_2}

    = y_3/{±√[(y_3)^2-y_1y_2]}

最後一式可由前一式的 "±" 分別代入 "+" 與 "-" 得知.

所以,

    x_4 = x_3 - y_3(x_3-x_1)/{±√[(y_3)^2-y_1y_2]}

        = x_3 ± y_3(x_3-x_1)/√[(y_3)^2-y_1y_2]

其中 "±" 視前面 t 之解應代入 "+" 或 "-" 決定. 用原問之

符號, 即是

    x4 = x3 ± (x3-x1)f3/√(f3^2-f1 f2])