跳转至

严格压缩怎样保证迭代找到唯一根？

先备知识

本单元只在实闭区间内从已学的 Cauchy 准则直接证明。若 \(0\le q<1\)，几何尾和可精确控制无限步误差。

学习目标

  1. 完证实闭区间上的压缩映射定理；2. 核对几何增量的指标；3. 推导先验与后验误差界；4. 区分固定点存在、唯一与迭代收敛。

牵引问题

怎样从一次误差缩小的不等式推出：迭代永不跑出区间、必有极限、极限是不动点且唯一，并能在不知道极限值时停止？

探索与猜想

若 \(x_{n+1}=g(x_n)\) 且 \(g\) 将区间映回自身，则所有迭代都合法。压缩式使相邻增量逐次乘 \(q\)；任意远的两项之差是这些增量的有限和。

概念与理论

实闭区间压缩映射定理

设 \(g:[a,b]\to[a,b]\)，且存在 \(0\le q<1\) 使

\[ |g(x)-g(y)|\le q|x-y|\qquad(x,y\in[a,b]). \]

则 \(g\) 在 \([a,b]\) 中有唯一不动点 \(p\)；任取 \(x_0\in[a,b]\)，由 \(x_{n+1}=g(x_n)\) 定义的数列都趋于 \(p\)。

证明。 首先用归纳法证明 \(x_n\in[a,b]\)：初值成立；若 \(x_n\in[a,b]\)，由自映射条件 \(x_{n+1}=g(x_n)\in[a,b]\)。

记

\[ d_j=|x_{j+1}-x_j|\qquad(j\ge0). \]

当 \(j=0\) 时，\(d_0=q^0d_0\) 就是等式，不涉及负下标。当 \(j\ge1\) 时，压缩式给出

\[ d_j=|g(x_j)-g(x_{j-1})|\le qd_{j-1}; \]

递推应用 \(j\) 次得到

\[ d_j\le q^j d_0=q^j|x_1-x_0|\qquad(j\ge0). \]

对 \(m>n\)，三角不等式与有限几何和给出

\[ \begin{aligned} |x_m-x_n| &\le\sum_{j=n}^{m-1}|x_{j+1}-x_j|\\ &\le |x_1-x_0|\sum_{j=n}^{m-1}q^j\\ &\le\frac{q^n}{1-q}|x_1-x_0|. \end{aligned} \]

右端随 \(n\to\infty\) 趋零，所以 \((x_n)\) 是 Cauchy 数列，因而趋于某个实数 \(p\)。又所有 \(x_n\in[a,b]\)；若 \(p>b\)，充分后 \(x_n>b\)，矛盾，\(p<a\) 同理，故 \(p\in[a,b]\)。

不用连续性定理，只以压缩式直接验证：

\[ |g(p)-p|\le |g(p)-g(x_n)|+|x_{n+1}-p| \le q|p-x_n|+|x_{n+1}-p|\to0. \]

故 \(g(p)=p\)。若 \(r\) 也是不动点，则 \(|p-r|\le q|p-r|\)；因 \(1-q>0\)，得 \(p=r\)。\(\square\)

两条误差界

令上面 \(m\to\infty\)，得到先验界

\[ |x_n-p|\le\frac{q^n}{1-q}|x_1-x_0|. \]

若从当前增量向后求和，注意 \(|x_{n+r+1}-x_{n+r}|\le q^{r+1}|x_n-x_{n-1}|\)，故得到后验界

\[ |x_n-p|\le\frac{q}{1-q}|x_n-x_{n-1}|\qquad(n\ge1). \]

\(q\) 因子不能漏掉；若用新增量 \(|x_{n+1}-x_n|\) 证书，则相应为 \(|x_n-p|\le |x_{n+1}-x_n|/(1-q)\)。

例题与迁移

例题 1：主压缩

对 \(g(x)=1/(2+x)\) 与 \([0,1]\)，有 \(1/3\le g(x)\le1/2\)，故 \(g([0,1])\subseteq[0,1]\)；且

\[ |g(x)-g(y)|=\frac{|x-y|}{(2+x)(2+y)}\le\frac14|x-y|. \]

所以 \(q=1/4\) 合法，唯一不动点由 \(p^2+2p-1=0\) 及 \(p\in[0,1]\) 得 \(p=\sqrt2-1\)。

例题 2：唯一固定点仍可能振荡

\(x_{n+1}=1-x_n\) 在 \([0,1]\) 上有唯一不动点 \(1/2\)，但 \(|g(x)-g(y)|=|x-y|\)，只能取 \(q=1\)。若 \(x_0\ne1/2\)，则 \(x_{n+2}=x_n\)，不收敛。另一个对照 \(x_{n+1}=\frac{x_n}{1+x_n}\)（\(x_0>0\)）满足 \(x_n=x_0/(1+nx_0)\to0\)，却是 \(1/n\) 级慢变，不能由有限样本冒充统一几何压缩。

即时检验与回望

  1. 自映射条件在证明中做了什么？
答案

它归纳保证每个 \(x_n\) 都留在压缩不等式适用的闭区间内，并在极限阶段配合闭性保证 \(p\in[a,b]\)。

  1. 后验界为什么有 \(q/(1-q)\)？
答案

从 \(x_n\) 到极限的第一个未来增量 \(|x_{n+1}-x_n|\) 已至多是 \(q|x_n-x_{n-1}|\)，后续形成 \(q+q^2+\cdots=q/(1-q)\)。

习题与答案

习题 1：不变迭代

写出证明 \(x_n\in[a,b]\) 的归纳步骤。

答案

\(x_0\in[a,b]\)。若 \(x_n\in[a,b]\)，则 \(x_{n+1}=g(x_n)\in g([a,b])\subseteq[a,b]\)，归纳完成。

习题 2：几何增量

证明 \(|x_{j+1}-x_j|\le q^j|x_1-x_0|\)。

答案

\(j=0\) 时两端相等。\(j\ge1\) 时先由压缩式得到 \(d_j\le qd_{j-1}\)，再反复应用 \(j\) 次，得到 \(d_j\le q^jd_0=q^j|x_1-x_0|\)；全过程不出现 \(x_{-1}\)。

习题 3：唯一性

完整证明两个不动点必相等。

答案

若 \(g(p)=p,g(r)=r\)，则 \((1-q)|p-r|\le0\)。但两因子都非负且 \(1-q>0\)，所以 \(|p-r|=0\)，即 \(p=r\)。

习题 4：后验停止阈值

要保证 \(|x_n-p|\le\tau\)，旧增量应满足什么条件？

答案

由后验界，充分条件是 \(|x_n-x_{n-1}|\le(1-q)\tau/q\)（\(q>0\)）。若 \(q=0\)，一次迭代后函数在区间上为常数，已到不动点。

习题 5：闭区间作用

解释为何只证明迭代都在开区间 \((a,b)\) 还不够。

答案

Cauchy 极限可能落在端点而不属于开区间；此时 \(g\) 未必在极限处有定义，固定点步骤失效。闭区间包含所有数列极限候选端点。

常见误区与后续

  • 固定点方程的解不自动保证迭代收敛。
  • 几何求和要核对起始指标；后验常数中的 \(q\) 不能漏。
  • 本定理只在实闭区间上证明；下一证书单元将把每个假设与停止条件拆开审计。