06.1-不動點迭代法

不動點迭代法（Fixed Point Iteration）#

不動點迭代法是一種數值方法，用於求解方程 \(f(x) = 0\) 或等價的形式 \(x = g(x)\) 的根，這其中 \(g(x)\) 是由原始方程轉換得到的函數。此方法是迭代法的一種，通過從一個初始猜測值開始，不斷進行迭代，並根據不動點的特性逐漸逼近方程的解。

1. 不動點的概念#

不動點是指對於一個函數 \(g(x)\) ，若存在某個值 \(x^*\) ，使得： [ g(x^) = x^ ] 那麼這個 \(x^*\) 就是函數 \(g(x)\) 的不動點。換句話說，將 \(x^*\) 代入函數 \(g(x)\) ，得到的結果仍然是 \(x^*\) 。

2. 不動點迭代法的基本思想#

不動點迭代法的核心是從一個初始猜測值 \(x_0\) 開始，反覆使用迭代公式： [ x_{n+1} = g(x_n) ] 直到迭代結果 \(x_n\) 收斂到某一個值 \(x^*\) ，這個 \(x^*\) 就是方程的解，即 \(g(x^*) = x^*\) 。

3. 不動點迭代法的步驟#

**選擇初始猜測值 \(x_0\) **：根據問題選擇一個合理的初始值 \(x_0\) 。
**定義迭代函數 \(g(x)\) **：將原方程轉換為不動點方程形式，即將方程 \(f(x) = 0\) 轉化為 \(x = g(x)\) 的形式。
進行迭代：使用迭代公式 \(x_{n+1} = g(x_n)\) 進行計算，逐步逼近解。
判斷收斂性：在每次迭代後，檢查 \(|x_{n+1} - x_n|\) 是否足夠小，若小於預設的誤差範圍，則認為已經收斂，停止迭代。

4. 不動點迭代法的收斂性#

不動點迭代法的收斂性取決於迭代函數 \(g(x)\) 的特性，具體來說： - 如果 \(|g'(x)| \leq k < 1\) 在不動點附近成立，則不動點迭代法收斂，並且收斂速度較快。 - 如果 \(|g'(x)| > 1\) ，則迭代過程會發散，無法收斂。

為了保證收斂，通常需要選擇合適的 \(g(x)\) ，使得在目標根附近， \(|g'(x)|\) 小於 1。

5. 例子#

假設我們要解方程 \(x^2 - 2 = 0\) ，即求 \(\sqrt{2}\) ，我們可以將方程轉換為不動點形式： [ x = \frac{1}{2}(x + \frac{2}{x}) ] 這樣，我們就可以用不動點迭代法來進行求解： 1. 設定初始猜測值 \(x_0 = 1\) 。 2. 使用迭代公式 \(x_{n+1} = \frac{1}{2}(x_n + \frac{2}{x_n})\) 進行迭代，直到解收斂。

6. 優缺點#

優點：#

簡單易用：不動點迭代法的實現相對簡單，通常只需要簡單的迭代公式即可。
計算效率高：在某些情況下，不動點迭代法收斂速度快，並且計算開銷小。

缺點：#

依賴於初始猜測：不動點迭代法的收斂性高度依賴於初始猜測，若選擇不當，可能會導致發散或收斂到錯誤的解。
收斂條件嚴格：要求 \(|g'(x)|\) 小於 1，並且需要選擇適當的轉換函數來保證收斂。

7. 不動點迭代法的總結#

不動點迭代法是一種簡單的數值方法，適用於求解某些方程的解，特別是當方程可以轉換為不動點形式時。儘管它有時收斂性較慢且依賴於初始猜測，但在許多情況下，尤其是解的範圍已知且轉換函數設計得當時，不動點迭代法仍然是一個非常有效的解法。