非線性方程式的解

我們先看一個簡單的範例,若\(f(x)=e^x-2x-1\),要解\(f(x)=0\) 我們可以寫成 \(e^x=2x+1\),然後左右兩端取 \(log\) 得到 \(x=log(2x+1)\), 亦即 \(g_1(x) = log(2x+1)\)。或是我們保留 \(x\) 的一次項,其餘的部分搬到另外一邊得到 \(x = \frac{e^x-1}{2}\),這時 \(g_2(x)= \frac{e^x-1}{2}\) 。解固定點的方法最直覺的方式是簡單遞迴。簡單遞迴的形式如下

\(x_{n+1} = g(x_n)\)

當我們有一個猜測的起始解 \( x_0\),透過這一個簡單遞迴的公式就可以得到數列 \(\{x_n\}\),若 \( x_n \to \xi\) 我們有 \(\xi = g(\xi)\),亦即 \(\xi\) 為 \( f(x) = 0\) 的解。 使用簡單遞迴的方式來解固定點問題,很自然地我們會問兩個問題,第一是起始點是否會影響解的結果?第二是在什麼條件下,簡單遞迴的遞迴式會收斂。

假設 \(g(x)= sin(x)\),起始點 \(x_0=0.8\),使用簡單遞迴計算127981次的結果可以得到固定點的逼近解為 0.004662660628882 ,這時逼近解與上一步逼近解的誤差為 \(10^{-8}\)。下圖為第10000步到第127981 步 \(\|x_{i+1}-x_i\|\) 的結果。我們可以看到收斂的速度會越來越緩慢,所耗費的時間也非常冗長。

sin fix pt

對應的Python 程式如下:

  1. MaxItr = 10000
  2. i = 0
  3. whileabs(x-x1)> tol & i< MaxItr:
  4. i+=1
  5. x = x1
  6. x1 = gx(x)
  7. print x