8.2 分形與迭代函數系統#

概念說明#

迭代函數系統（Iterated Function System, IFS）是「用迭代畫出無限細節」的方法。給定一組壓縮仿射變換 \(\{w_1, \dots, w_N\}\) （每個都是縮小＋旋轉＋平移，且壓縮率 \(< 1\) ），定義 \(W(S) = w_1(S) \cup \cdots \cup w_N(S)\) 。巴拿赫不動點定理（2.2 節，在集合的完備空間上套用 Hausdorff 距離）保證： \(W\) 有唯一不動點集合 \(A = W(A)\) ——吸引子，它就是分形。 fern 蕨葉、Sierpiński 三角、Koch 曲線都是這種「多個壓縮映像的共同不動點」。

實作吸引子的標準方法是 Chaos Game（隨機迭代法）：任取起點，每步隨機挑一個變換 \(w_i\) 作用，畫出落點。數萬步後，軌跡「撒」出的點雲恰好密布整個吸引子。原理：壓縮性使軌道被吸向 \(A\) ，隨機挑選使它遍歷 \(A\) 的各部分（遍歷性）。

IFS 的兩個深刻面向：

自我相似：吸引子由自己的縮小版拼成（ \(A = \cup w_i(A)\) ），放大任何部分都能看到整體的縮影——分形維數介於整數之間（Sierpiński 三角 \(\log 3/\log 2 \approx 1.585\) ）。
壓縮編碼：整棵蕨葉由 4 組係數（每組 6 個數字）完全描述——極簡規則生成極複雜形體。這啟發了分形影像壓縮（找影像自身的仿射自相似來編碼）與自然物建模（植物、地形、雲）。

與 8.1 的對照極具啟發：邏輯斯蒂映射示範迭代如何失去可預測性（混沌），IFS 示範迭代如何獲得確定結構（吸引子）。兩者的共同根柢都是不動點理論——前者在混沌區沒有穩定不動點，後者全靠壓縮性保證唯一不動點。

生活類比#

兩面鏡子相對，內含一個物件：影像中套影像、無窮自我相似——這就是縮小變換的不動點。食譜「先照規則縮小三份、各自加上變化、再重複」的摺紙雪花，最後的形狀也是一組規則的不動點。

演算法步驟#

Chaos Game 繪製流程：

定義 \(N\) 個壓縮仿射變換 \(w_i(x) = A_i x + b_i\) 及選取機率 \(p_i\) （常與面積成比例）。
隨機起點 \(x_0\) 。
迭代 \(M\) 次（前 10~20 步為暫態，不畫）：隨機依 \(p_i\) 選 \(w_i\) ， \(x \leftarrow w_i(x)\) ，記錄 \(x\) 。
將所有落點渲染成圖（累積到 2D 直方圖/點陣）。

變換設計（以 Sierpiński 三角為例）：三個頂點 \(v_1, v_2, v_3\) ， \(w_i(x) = \frac{1}{2}(x + v_i)\) ，機率各 1/3。

Python 範例#

import numpy as np

def ifs(transforms, probs, n=100000, burn=20, seed=0):
    rng = np.random.default_rng(seed)
    x = rng.random(2)
    pts = np.empty((n, 2))
    for i in range(burn + n):
        w = transforms[rng.choice(len(transforms), p=probs)]
        x = w[:4].reshape(2, 2) @ x + w[4:]
        if i >= burn:
            pts[i - burn] = x
    return pts

# Sierpiński 三角
V = np.array([[0, 0], [1, 0], [0.5, np.sqrt(3)/2]])
sierp = [np.r_[0.5*np.eye(2), 0.5*v] for v in V]
pts = ifs(sierp, [1/3]*3)
print("Sierpiński 點數:", len(pts), "範圍:",
      pts.min(0).round(2), pts.max(0).round(2))

# Barnsley 蕨葉（經典四變換）
fern = [
    np.array([0.00, 0.00, 0.00, 0.16, 0.0, 0.0]),          # 莖
    np.array([0.85, 0.04, -0.04, 0.85, 0.0, 1.6]),         # 主葉
    np.array([0.20, -0.26, 0.23, 0.22, 0.0, 1.6]),         # 左枝
    np.array([-0.15, 0.28, 0.26, 0.24, 0.0, 0.44]),        # 右枝
]
fp = [0.01, 0.85, 0.07, 0.07]
fern_pts = ifs(fern, fp, n=150000)
print("蕨葉點數:", len(fern_pts),
      "x 範圍:", fern_pts[:,0].min().round(2), fern_pts[:,0].max().round(2))

# 繪圖（需 matplotlib）：
# import matplotlib.pyplot as plt
# plt.scatter(pts[:,0], pts[:,1], s=0.1); plt.axis("equal"); plt.show()

複雜度與收斂性分析#

生成 \(M\) 點成本 \(O(M)\) 、記憶體 \(O(M)\) （或直接渲染 \(O(1)\) ）。理論收斂：Hausdorff 距離下 \(d(W^k(S_0), A) \le L^k d(S_0, A)\) ，壓縮率 \(L = \max_i \text{lip}(w_i)\) ；蕨葉最大壓縮率約 0.87，暫態數十步即可。Chaos Game 的統計性質由遍歷定理保證：點的分布收斂到吸引子上的不變測度。分形維數可由盒計數法實測： \(\dim = \lim \frac{\ln N(\varepsilon)}{\ln(1/\varepsilon)}\) ，對 Sierpiński 應得 1.585。設計要訣：機率 \(p_i\) 影響點密度不影響形狀；壓縮率接近 1 時暫態變長、細節浮現慢。

練習#

修改 Sierpiński 的壓縮率從 0.5 改為 0.6，觀察吸引子如何改變（提示：變換不再互不相交）。
用盒計數法實測蕨葉的分形維數（對不同 \(\varepsilon\) 數非空格數，做線性回歸）。
實作 Koch 曲線的 L 系統（字串改寫）版本，與 IFS 版本比較，思考「符號迭代」與「幾何迭代」的等價性。