1.1 迭代與迴圈#

概念說明#

迭代是一種數學與演算法層次的概念：給定初始狀態 \(x_0\) ，反覆套用某個轉換規則 \(x_{k+1} = f(x_k)\) ，產生一連串逼近解的序列。迴圈則是程式語言中實現迭代的語法構造（for、while）。兩者是「理念」與「載體」的關係——同一個迭代過程，可以用 while 迴圈、遞迴、生成器，甚至硬體電路來實現。

迭代過程的三個基本要素：

初始值：迭代從哪裡出發（ \(x_0\) ）。
更新規則：每一步如何由舊狀態算出新狀態（ \(f\) ）。
停止條件：何時認為已經「足夠好」而停止。

停止條件通常有三類：達到固定次數、誤差小於容許值（|x_{k+1} - x_k| < ε）、或狀態不再改變（收斂或不動點）。數值迭代多採用誤差容忍度，離散迭代則常用固定上限。

一個關鍵認知是：迭代序列未必收斂。 \(x_{k+1} = 2x_k\) 從 \(x_0=1\) 出發會發散； \(x_{k+1} = -x_k\) 會在兩點間震盪。因此設計迭代法時，必須同時回答「會不會收斂」與「收斂得多快」兩個問題，這正是第 2、3 章的主題。

生活類比#

把湯調味：嚐一口（評估誤差）、加一撮鹽（更新狀態）、再嚐一口，直到鹹淡合宜（停止條件）。你不需要一次算出「該加幾克鹽」的解析解，而是透過小步逼近——這正是迭代法的精髓。

演算法步驟#

以「用迭代逼近 \(\sqrt{2}\) 」為例（巴比倫法，第 2 章將證明其正確性）：

設定初始猜測 \(x_0 = 1\) ，容許誤差 eps = 1e-12。
重複： \(x_{k+1} = \dfrac{1}{2}\left(x_k + \dfrac{2}{x_k}\right)\) 。
當 \(|x_{k+1} - x_k| < \text{eps}\) 時停止。
輸出 \(x_{k+1}\) 。

Python 範例#

def sqrt2(eps=1e-12, max_iter=100):
    x = 1.0                     # 初始值
    for k in range(max_iter):
        x_new = 0.5 * (x + 2/x) # 更新規則
        if abs(x_new - x) < eps:  # 停止條件
            return x_new, k + 1
        x = x_new
    return x, max_iter

val, steps = sqrt2()
print(f"sqrt(2) ≈ {val!r}，迭代 {steps} 次")

執行後會發現：僅約 5 次迭代，就達到雙精度浮點數的極限。這種「平方收斂」的威力，將貫穿全書。

複雜度與收斂性分析#

迭代的「成本」不是單步指令數，而是 迭代次數 × 每次迭代的成本。巴比倫法每步除一次，收斂階為 2（誤差近似平方縮小），故達到 \(p\) 位精度約需 \(O(\log p)\) 次迭代。對比逐位試探法需 \(O(p)\) 次，差距是數量級的。分析迭代法時的三個標準問題：序列是否收斂？收斂到正確答案嗎？需要多少步？

練習#

修改 sqrt2 求 \(\sqrt{10}\) ，並用 math.sqrt(10) 驗證。
寫出迭代 \(x_{k+1} = x_k/2 + 1\) 的前五項，觀察它趨近哪個數？用代數解出「若收斂則 \(x = x/2 + 1\) 」驗證你的觀察。
設計一個迭代：從 100 開始，奇數則 \(3n+1\) 、偶數則 \(n/2\) （考拉茲猜想）。列印序列直到 1，並統計步數。