迭代函数系统

迭代函数系统（iterated function system，简称 IFS）是一族反复作用于点或集合的映射。对完备度量空间中的有限个严格压缩映射，把一个非空紧集的所有像合并，再重复这一操作，会收敛到唯一的非空紧吸引子。这个结论不要求不同像互不相交，也不要求映射保持相似形状。

一个可手算的例子是实数轴上的 $S_{1} (x) = x / 2$ 与 $S_{2} (x) = x / 2 + 1 / 2$ 。从单点集 $P_{0} = {0}$ 出发，第一步得到 ${0, 1 / 2}$ ，第二步得到 ${0, 1 / 4, 1 / 2, 3 / 4}$ 。这些有限集合逐渐填密区间，但任意有限一步仍缺少区间中的绝大多数点。要准确说明“接近整个区间”，需要度量集合之间的误差。

非空紧集与 Hausdorff 距离

设 $(X, d)$ 是非空完备度量空间， $𝒦 (X)$ 表示它的所有非空紧子集。对点 $x$ 和非空集合 $B$ ，记 $d (x, B) = inf_{b \in B} d (x, b)$ 。两个非空紧集的 Hausdorff 距离定义为 $d_{H} (A, B) = max {sup_{a \in A} d (a, B), sup_{b \in B} d (b, A)} .$ 第一项要求 $A$ 的每一点都靠近 $B$ ；第二项反过来要求 $B$ 的每一点都靠近 $A$ 。紧性保证这些量有限。两项都为零时，由紧集的闭性可知两集合相等。对第三个非空紧集 $C$ ，选择 $B$ 中离 $x$ 最近的点，先得到 $d (x, C) \leq d (x, B) + d_{H} (B, C)$ ；对 $x \in A$ 取上确界，再交换 $A, C$ 重复一次，便得到三角不等式 $d_{H} (A, C) \leq d_{H} (A, B) + d_{H} (B, C)$ 。连同对称性与非负性，这证明它确实是 $𝒦 (X)$ 上的度量。

例如 $A = {0, 1}$ 、 $B = {0, 1 / 2, 1}$ 。因为 $A \subset B$ ，第一项为零；第二项在中点 $1 / 2$ 达到 $1 / 2$ ，所以 $d_{H} (A, B) = 1 / 2$ 。只检查第一项会把这个不同的集合误当作误差为零。

数轴上A含零和一，B还含二分之一；新增中点离A的最近距离为二分之一 — 方形标记表示A，圆形标记表示B；两端点属于两者。中点到A的距离决定了两集合的Hausdorff距离。

下面使用一个度量空间事实：当 $X$ 完备时， $(𝒦 (X), d_{H})$ 也完备。其作用是保证集合的 Cauchy 序列仍有非空紧极限。可以从紧性判别看出这一点：若 $A_{n}$ 为 Hausdorff–Cauchy 序列，对任意 $ε > 0$ ，足够靠后的集合都在某个紧集 $A_{N}$ 的 $ε / 3$ 邻域内。用 $A_{N}$ 的有限个半径 $ε / 3$ 的球，再加上有限个前项的有限覆盖，就得到 $⋃_{n} A_{n}$ 的有限个半径 $ε$ 的球覆盖。于是该并集全有界，其闭包 $C$ 在完备空间中紧。

在 $C$ 中取 $K = ⋂_{N \geq 1} \overline{⋃_{n \geq N} A_{n}} .$ 这是嵌套非空紧集的交，因而非空紧；它恰由序列 $x_{j} \in A_{n_{j}}$ 、 $n_{j} \to \infty$ 的极限点组成。若 $n, m \geq N$ 时 $d_{H} (A_{n}, A_{m}) < ε / 2$ ，固定 $x \in A_{n}$ ，从后续每个 $A_{m}$ 选离 $x$ 不超过 $ε / 2$ 的点，再在紧集 $C$ 中取收敛子列，便得到 $d (x, K) \leq ε / 2$ 。反向对 $y \in K$ 的极限表示取界，得到 $d (y, A_{n}) \leq ε / 2$ 。因此 $d_{H} (A_{n}, K) \to 0$ ，完备性成立。^[1]

Hutchinson 算子的收缩性

给定有限个映射 $S_{1}, \dots, S_{m} : X \to X$ ，其中 $m \geq 1$ 。假定每个映射满足统一的距离估计 $d (S_{i} (x), S_{i} (y)) \leq r_{i} d (x, y), 0 \leq r_{i} < 1,$ 并令 $q = max_{i} r_{i} < 1$ 。这里的“严格压缩”指存在这样的全局常数；仅有每一对不同点的距离都严格减小，不足以给出本节使用的统一 $q$ 。

定义 Hutchinson 算子 $F (A) = ⋃_{i = 1}^{m} S_{i} (A) .$ 压缩映射连续，紧集的连续像仍紧，有限个非空紧集的并仍是非空紧集，所以 $F : 𝒦 (X) \to 𝒦 (X)$ 。选择紧集作为论域也避免了把一般闭集的连续像误当成闭集。

要证明这个算子收缩，取任意 $z \in F (A)$ ，写成 $z = S_{i} (a)$ ，其中 $a \in A$ 。从 $B$ 选离 $a$ 最近的点 $b$ ；紧性保证最近点存在。由于 $S_{i} (b) \in F (B)$ ， $d (z, F (B)) \leq d (S_{i} (a), S_{i} (b)) \leq r_{i} d (a, B) \leq q d_{H} (A, B) .$ 对所有 $z$ 取上确界，再交换 $A, B$ 重复论证，就得到 $d_{H} (F (A), F (B)) \leq q d_{H} (A, B) .$ 关键是给两集合中的点使用同一个分支 $S_{i}$ 作比较；无需假设分支的像相互分离。^[2]

唯一吸引子及确定性误差界

从任意 $A_{0} \in 𝒦 (X)$ 出发，令 $A_{n + 1} = F (A_{n})$ ，并记 $Δ_{0} = d_{H} (A_{1}, A_{0})$ 。反复应用收缩性， $d_{H} (A_{n + 1}, A_{n}) \leq q^{n} Δ_{0} .$ 对 $m > n$ ，沿相邻项使用三角不等式，把误差相加： $d_{H} (A_{m}, A_{n}) \leq \sum_{j = n}^{m - 1} q^{j} Δ_{0} \leq \frac{q^{n}}{1 - q} Δ_{0} .$ 因为 $q < 1$ ，这是 Cauchy 序列。由前述完备性，存在 $K \in 𝒦 (X)$ 使 $A_{n} \to K$ 。收缩性还给出 $d_{H} (F (K), K) \leq q d_{H} (K, A_{n}) + d_{H} (A_{n + 1}, K) ⟶ 0,$ 故 $F (K) = K$ 。若另有非空紧集 $L = F (L)$ ，则 $d_{H} (K, L) \leq q d_{H} (K, L)$ ，由 $q < 1$ 强迫距离为零，得到 $K = L$ 。这完整证明了非空紧吸引子的存在性和唯一性。

令上面求和式中的 $m \to \infty$ ，便得到可以停止计算的界 $d_{H} (A_{n}, K) \leq E_{n} := \frac{q^{n} Δ_{0}}{1 - q} .$ 如果已知初始误差，还可用 $d_{H} (A_{n}, K) \leq q^{n} d_{H} (A_{0}, K)$ ；但计算时通常不知道 $K$ ，所以由第一步距离得到的 $E_{n}$ 更实用。给定 $ε > 0$ ，只需找到 $E_{n} \leq ε$ 的 $n$ 。当 $q = 0$ 时，各映射都是常值映射，一步就达到吸引子；当 $Δ_{0} = 0$ 时，初始集合已经是不动集。

区间吸引子的可复算例子

回到 $S_{1} (x) = x / 2$ 、 $S_{2} (x) = x / 2 + 1 / 2$ 。它们把 $[0, 1]$ 分别送到 $[0, 1 / 2]$ 、 $[1 / 2, 1]$ ，所以 $F ([0, 1]) = [0, 1]$ ；由唯一性，吸引子就是 $K = [0, 1]$ 。

从 $P_{0} = {0}$ 出发，归纳得到 $P_{n} = {\frac{k}{2^{n}} : k = 0, 1, \dots, 2^{n} - 1} .$ 归纳步骤中，第一支把分子送到 $0, \dots, 2^{n} - 1$ ，第二支把分子送到 $2^{n}, \dots, 2^{n + 1} - 1$ ，分母都变为 $2^{n + 1}$ 。所有分支的并因此恰好给出下一层。

集合 $P_{n}$ 位于 $K$ 内，相邻点间距为 $2^{- n}$ ，最后一点是 $1 - 2^{- n}$ 。区间内部的相邻点之间，最远点到 $P_{n}$ 的距离至多是间距的一半；右端点 $1$ 到它的距离却为整个间距。因此 $d_{H} (P_{n}, [0, 1]) = 2^{- n} .$ 本例中 $q = 1 / 2$ 、 $Δ_{0} = 1 / 2$ ，一般误差界恰好给出同一个数。若目标误差为 $1 / 32$ ，取 $n = 5$ 即可：得到32个点，最后一点为 $31 / 32$ 。

从单点零开始的前四层二进制点集，每层点数加倍，最右点与端点一之间的缺口依次为一、二分之一、四分之一和八分之一 — 实心点是有限迭代结果，右端空心圈标出尚未包含的端点1。金色尾段给出本例真正达到的最大误差。

一个变式是把初始集合改为 $Q_{0} = {0, 1}$ 。此时 $Q_{n} = {k / 2^{n} : 0 \leq k \leq 2^{n}}$ 包含两个端点，最大误差出现在相邻点的中点，故 $d_{H} (Q_{n}, K) = 2^{- n - 1}$ 。第一步距离仍为 $1 / 2$ ，通用界仍是 $2^{- n}$ ，因而这次上界并不紧。误差界可以保证精度，却不必等于实际误差。

有理仿射系统的精确实现

下面实现实数轴上的有限仿射系统 $S_{i} (x) = a_{i} x + b_{i}$ ，要求 $a_{i}, b_{i}$ 、初始点和正容差均为有理数，且 $| a_{i} | < 1$ 。函数返回排序后的有限点集、误差上界 $E_{n}$ 和迭代层数，不修改输入。它完整应用所有分支，采用 Fraction 精确算术；拒绝浮点输入，以免把近似的小数误作已经验证的误差证书。

Python 3

from fractions import Fraction


def rational(value):
    if isinstance(value, bool) or not isinstance(value, (int, Fraction)):
        raise TypeError("use int or Fraction, not floating-point input")
    return Fraction(value)


def deterministic_ifs(maps, seed, eps, *, max_candidates=100000,
                      max_iter=100):
    for value, lower in ((max_candidates, 1), (max_iter, 0)):
        if isinstance(value, bool) or not isinstance(value, int) or value < lower:
            raise ValueError("invalid resource limit")
    maps = tuple((rational(a), rational(b)) for a, b in maps)
    if not maps:
        raise ValueError("at least one map is required")
    q = max(abs(a) for a, b in maps)
    if q >= 1:
        raise ValueError("every map must be a strict contraction")
    points = tuple(sorted({rational(x) for x in seed}))
    if not points:
        raise ValueError("seed must be nonempty")
    eps = rational(eps)
    if eps <= 0:
        raise ValueError("eps must be positive")

    def image(values):
        if len(maps) * len(values) > max_candidates:
            raise MemoryError("candidate budget exceeded before expansion")
        return tuple(sorted({a * x + b for a, b in maps for x in values}))

    def hausdorff(left, right):
        return max(max(min(abs(x - y) for y in right) for x in left),
                   max(min(abs(y - x) for x in left) for y in right))

    first = image(points)
    bound = hausdorff(points, first) / (1 - q)
    n = 0
    while bound > eps:
        if n >= max_iter:
            raise RuntimeError("iteration budget exhausted before tolerance")
        points = first if n == 0 else image(points)
        n += 1
        bound *= q
    return points, bound, n


maps = [(Fraction(1, 2), 0), (Fraction(1, 2), Fraction(1, 2))]
points, bound, n = deterministic_ifs(maps, [0], Fraction(1, 32))
print(n, len(points), points[0], points[-1], bound)
# 5 32 0 31/32 1/32

正确性由两个不变量连接到前面的证明：每次更新后的 points 精确等于 $F^{n} (P_{0})$ ；bound 精确等于 $q^{n} Δ_{0} / (1 - q)$ 。去掉重复点只改变集合的表示，不改变集合。循环只在此界不超过容差时返回；若资源不足则明确报错，不把未达精度的点集作为成功结果。

设第 $n$ 层去重后有 $p_{n}$ 个点。一次展开生成 $m p_{n}$ 个候选，去重后有 $p_{n + 1} \leq m p_{n}$ 个点；在把有理数运算和散列看作单位操作的模型中，集合生成预期需要 $O (m p_{n})$ 次操作，排序需要 $O (p_{n + 1} \log p_{n + 1})$ 次比较。代码首次朴素计算 Hausdorff 距离还需 $O (p_{0} p_{1})$ 次距离比较。两层集合和临时候选集合的存储为 $O (p_{n} + p_{n + 1} + m)$ 个有理数。位复杂度还取决于分子、分母的长度，不能把任意大整数运算视为固定成本。

最坏情况下点数按 $m^{n} p_{0}$ 增长；较小误差不意味着计算便宜。max_candidates 在生成前按 $m p_{n}$ 保守检查，可能拒绝实际重复点很多的展开；max_iter 则限制迭代层数。两项限制均属于实现的资源预算，而非吸引子存在性的条件。

条件失效与数值边界

完备性确实用于保留极限。若 $X = (0, 1)$ 、 $S (x) = x / 2$ ，映射仍把 $X$ 送入自身且压缩比为 $1 / 2$ ，但零不属于 $X$ 。若存在非空紧不变集 $K \subset X$ ，它的最小值 $a > 0$ 应满足 $a = a / 2$ ，矛盾。

压缩常数严格小于一也不能删去。在 $ℝ$ 上，恒等映射使每个非空紧集都不变，唯一性失效；平移 $S (x) = x + 1$ 则没有非空紧不变集。有限性保证有限并仍紧；例如无限多个常值映射 $S_{j} (x) = 1 / j$ 虽然各自的压缩常数都是零，但其像的并为 ${1, 1 / 2, 1 / 3, \dots}$ ，不是闭集，算子已不能按上述定义把紧集送入紧集。无限系统需另加条件。唯一性也限于非空紧集：单映射 $S (x) = x / 2$ 在 $ℝ$ 上的紧吸引子是 ${0}$ ，而非紧集 $ℝ$ 同样满足集合不变式。

若改用浮点数，每一步存储集合 ${\tilde{A}}_{n + 1}$ 与精确映射结果 $F ({\tilde{A}}_{n})$ 之间会有额外误差。假定已经独立保证这项 Hausdorff 误差不超过 $η$ ，则 $e_{n + 1} \leq q e_{n} + η, e_{n} := d_{H} ({\tilde{A}}_{n}, K),$ 递推给出 $e_{n} \leq q^{n} e_{0} + η \frac{1 - q^{n}}{1 - q} .$ 因此反复迭代不会消除持续产生的舍入误差；当 $q$ 接近一时，误差累积尤其明显。实际程序还可能发生溢出、产生 NaN，或将过近的点舍入为同一点。没有经过验证的 $η$ 时，直接套用精确公式不能得到严格浮点误差证书。上面的实现通过精确有理数避免这一问题，包括拒绝 NaN、无穷和普通浮点参数；若要处理非有理映射，可改用有验证界的区间算法。

绘制随机迭代点时，每轮通常只选择一个分支，这与这里保留所有分支的集合迭代不同。一张有限随机点云即使外观接近吸引子，也没有自动给出“吸引子的每一点都靠近已绘点”的反向 Hausdorff 界。随机方法的概率性结论需要另设选枝机制并单独证明，不能用有限图像替代本篇的确定性覆盖估计。

参考资料

↑ John E. Hutchinson. Fractals and Self Similarity, Indiana University Mathematics Journal 30 (1981), 713–747。链接为作者重排版；§2.4，第6页讨论 Hausdorff 距离及完备性。
↑ Hutchinson，同上，作者重排版§3.1，第10—12页；§3.2，第12页的收缩定理。第13页的补注说明：若改在一般非空闭有界集上操作，需要对像取闭包；在本篇使用的非空紧集空间上无需该修正。

[hutchinson-metric-1] John E. Hutchinson. Fractals and Self Similarity, Indiana University Mathematics Journal 30 (1981), 713–747。链接为作者重排版；§2.4，第6页讨论 Hausdorff 距离及完备性。

[hutchinson-contraction-2] Hutchinson，同上，作者重排版§3.1，第10—12页；§3.2，第12页的收缩定理。第13页的补注说明：若改在一般非空闭有界集上操作，需要对像取闭包；在本篇使用的非空紧集空间上无需该修正。

[1]

[2]