What Does a Fixer Fix? | 不动点迭代固定了什么?

📚 What Does a Fixer Fix? | 不动点迭代固定了什么?

When faced with a tricky equation f(x)=0, a mathematician might ask, “What if we could find a number that stays fixed under some cleverly chosen transformation?” That transformation, often called an iterator or a fixer, does not literally repair something broken; rather, it pins down a solution by repeatedly applying a function g until the values stop changing. In numerical analysis, this is known as fixed-point iteration, and the “fixer” is the function g whose fixed points coincide with the roots of the original equation. This article explores what a fixer fixes, how it works, and why it sometimes succeeds and sometimes fails, all within the context of the IB Mathematics curriculum.

面对一个棘手的方程 f(x)=0,数学家可能会问:“如果我们能找到一个在某种巧妙变换下保持固定的数呢?”这种变换通常称为迭代函数或“固定者”,它并不是修理什么破损的东西;相反,它通过反复应用函数 g 直到数值不再变化,从而锁定一个解。在数值分析中,这被称为不动点迭代,而那个“固定者”就是函数 g,它的不动点与原方程的根一致。本文将探讨一个固定者究竟固定了什么、它如何工作、为何有时成功有时失败,所有内容均基于 IB 数学课程。


1. What Is a Fixed Point? | 什么是不动点?

A fixed point of a function g is a number s such that g(s) = s. Graphically, it is the x-coordinate where the curve y = g(x) meets the line y = x. If we can rewrite the equation f(x)=0 into the form x = g(x), then any fixed point of g is automatically a root of f, because f(s)=0 implies s = g(s). For example, the equation x² − x − 1 = 0 can be rearranged as x = √(x+1) (for x > −1) or x = 1 + 1/x (for x ≠ 0). Both expressions define possible fixers that share the same fixed points — the golden ratio φ ≈ 1.618 and its conjugate.

函数 g 的不动点是指满足 g(s)=s 的数 s。从图形上看,它是曲线 y=g(x) 与直线 y=x 交点的横坐标。如果能把方程 f(x)=0 改写为 x=g(x) 的形式,那么 g 的任意不动点都会自动成为 f 的根,因为 f(s)=0 意味着 s=g(s)。例如,方程 x²−x−1=0 可改写为 x=√(x+1)(x>−1)或 x=1+1/x(x≠0)。这两个表达式都定义了可能的固定者,它们拥有相同的不动点——黄金比例 φ≈1.618 及其共轭。


2. Turning Equations into Fixed-Point Form | 将方程化为不动点形式

There is never a unique way to rewrite f(x)=0 as x = g(x); in fact, infinitely many choices exist. This flexibility is both a blessing and a curse: some choices lead to rapid convergence, others to divergence. Common strategies include isolating the variable algebraically, adding x to both sides, or using inverse functions. For instance, starting from f(x)=x²−x−1=0, we may set:

将 f(x)=0 改写为 x=g(x) 的形式绝不止一种;事实上,有无穷多种选择。这种灵活性既是好事也是麻烦:有些选择导致快速收敛,另一些则导致发散。常见的策略包括代数隔离变量、两边同时加 x 或使用反函数。例如,从 f(x)=x²−x−1=0 出发,我们可以设:

  • g₁(x) = √(x+1) (by taking the square root after adding 1 to both sides) —— 两边加 1 后开平方
  • g₂(x) = 1 + 1/x (by dividing the original equation by x) —— 原方程除以 x
  • g₃(x) = x² − 1 (by simply moving the linear term) —— 直接移项

Each g captures the same fixed point φ, but their behaviour under iteration can be dramatically different. Choosing a good fixer is a central skill in numerical problem-solving.

每一个 g 都包含相同的不动点 φ,但它们在迭代下的表现可能截然不同。选择好的固定者是数值求解的核心技巧。


3. The Iteration Algorithm | 迭代算法

Fixed-point iteration follows a simple recipe: start with an initial guess x₀, then repeatedly apply the chosen function g. The sequence is defined by xₙ₊₁ = g(xₙ) for n = 0, 1, 2, … If the sequence converges, its limit s satisfies s = g(s) and is therefore a root of the original equation. The algorithm stops when successive values are close enough, e.g., |xₙ₊₁ − xₙ| < tolerance. This method requires no derivative calculations, making it easy to program on a calculator or computer.

不动点迭代遵循简单的步骤:从一个初始猜测 x₀ 开始,然后反复应用选定的函数 g。序列定义为 xₙ₊₁ = g(xₙ),n = 0, 1, 2, … 如果序列收敛,其极限 s 满足 s=g(s),因而就是原方程的一个根。当连续值足够接近时算法停止,例如 |xₙ₊₁−xₙ| < 容许误差。这种方法不需要计算导数,因此很容易在计算器或计算机上编程实现。

xₙ₊₁ = g(xₙ) → limit s where g(s)=s


4. Cobweb Diagrams: Visualising Convergence | 蛛网图:收敛可视化

A cobweb diagram offers a powerful geometric insight into fixed-point iteration. On the same axes, plot the line y = x and the curve y = g(x). Starting from (x₀, 0) on the x-axis, draw a vertical line to the curve, reaching the point (x₀, g(x₀)). Then move horizontally to the line y = x, landing at (g(x₀), g(x₀)). Drop vertically again to the curve at (g(x₀), g(g(x₀))) and repeat. The path zigzags either towards the intersection (convergence) or away from it (divergence). A staircase pattern indicates monotonic convergence, while an inward spiral shows oscillatory convergence.

蛛网图为不动点迭代提供了强有力的几何洞察。在同一坐标系中画出直线 y=x 和曲线 y=g(x)。从 x 轴上的 (x₀,0) 开始,向上作垂直线至曲线,到达点 (x₀, g(x₀))。然后水平移动到直线 y=x,到达 (g(x₀), g(x₀))。再次向下作垂直线交曲线于 (g(x₀), g(g(x₀))),重复此过程。这条折线要么朝着交点(收敛)锯齿形前进,要么远离交点(发散)。阶梯状图案表示单调收敛,而向内螺旋表示振荡收敛。

For g₁(x)=√(x+1) near φ, the cobweb shows a staircase approaching the fixed point. For g₂(x)=1+1/x, the diagram produces a spiral that tightens around φ. In contrast, g₃(x)=x²−1 pulls the cobweb away from the intersection, illustrating divergence.

对于在 φ 附近的 g₁(x)=√(x+1),蛛网展示出走向不动点的阶梯。对于 g₂(x)=1+1/x,图线呈现围绕 φ 收紧的螺旋。相比之下,g₃(x)=x²−1 会将蛛网从交点拉开,表明发散。


5. The Key Convergence Condition | 关键收敛条件

Whether an iteration converges locally depends on the derivative of g at the fixed point. The fundamental condition is:

迭代是否局部收敛取决于 g 在不动点处的导数。基本条件是:

|g'(s)| < 1

If the absolute value of the slope of g at the fixed point is less than 1, then the fixed point is said to be attracting, and there exists a neighbourhood of s such that any starting value inside it will converge to s through iteration. If |g'(s)| > 1, the fixed point is repelling, and iteration pushes starting values away (except for the exact fixed point itself). The borderline case |g'(s)| = 1 requires higher-order analysis and may lead to very slow convergence or divergence depending on the specifics.

如果 g 在不动点处的斜率绝对值小于 1,则称该不动点为吸引的,并且存在 s 的一个邻域,使得其中任意初始值通过迭代都会收敛到 s。如果 |g'(s)|>1,不动点就是排斥的,迭代会将初始值推开(除非一开始就恰好选在不动点上)。边界情况 |g'(s)|=1 需要高阶分析,可能带来极慢的收敛或发散,视具体情况而定。

For our three fixers at φ≈1.618, we can compute approximate derivatives: g₁'(φ) = 1/(2√(φ+1)) ≈ 0.38 < 1 (convergent); g₂'(φ) = −1/φ² ≈ −0.38 (|g₂'|<1, convergent but oscillatory); g₃'(φ) = 2φ ≈ 3.236 > 1 (divergent). The absolute values fully align with the geometric observations from the cobweb diagrams.

对于我们三个固定者在 φ≈1.618 处,可计算近似导数:g₁'(φ)=1/(2√(φ+1))≈0.38<1(收敛);g₂'(φ)=−1/φ²≈−0.38(|g₂'|<1,收敛但振荡);g₃'(φ)=2φ≈3.236>1(发散)。绝对值与蛛网图的几何观察完全吻合。


6. Why the Condition Works | 条件为何有效

The convergence condition emerges naturally from the mean value theorem. Consider the error eₙ = xₙ − s. Using the iteration and the fixed-point property, eₙ₊₁ = xₙ₊₁ − s = g(xₙ) − g(s). By the mean value theorem, there exists some ξ between xₙ and s such that g(xₙ)−g(s) = g'(ξ)(xₙ−s). Thus |eₙ₊₁| = |g'(ξ)| |eₙ|. If |g’| is bounded by a constant L < 1 near s, the error shrinks by at least a factor L each step, guaranteeing geometric convergence. This also explains why a derivative larger than 1 in magnitude magnifies errors and causes divergence.

收敛条件自然地从中值定理推导出来。考虑误差 eₙ = xₙ−s。利用迭代和不动点性质,eₙ₊₁ = xₙ₊₁−s = g(xₙ)−g(s)。由中值定理,存在介于 xₙ 与 s 之间的某个 ξ 使得 g(xₙ)−g(s)=g'(ξ)(xₙ−s)。因此 |eₙ₊₁| = |g'(ξ)| |eₙ|。如果在 s 附近 |g’| 被某个小于 1 的常数 L 界住,误差每一步至少以因子 L 缩小,保证了几何级数式收敛。这也解释了为何导数绝对值大于 1 会放大误差、导致发散。


7. Choosing the Right Fixer | 选择合适的迭代函数

Because any f(x)=0 can be rewritten in countless ways, the art is to select a g such that |g'(s)| is as small as possible, ideally zero. A smaller derivative yields faster convergence. The table below compares three different fixers for the equation x²−x−1=0, evaluated at the positive root s=φ.

因为任何 f(x)=0 都可以用无数种方式改写,其艺术在于选择使 |g'(s)| 尽可能小的 g,理想情况是零。导数越小,收敛越快。下表比较了方程 x²−x−1=0 的三个不同固定者,在正根 s=φ 处求值。

g(x) |g'(φ)| Behaviour
√(x+1) ≈ 0.38 Monotonic convergence 单调收敛
1 + 1/x ≈ 0.38 Oscillatory convergence 振荡收敛
x² − 1 ≈ 3.24 Divergence 发散

Many textbook problems ask students to find a form that guarantees convergence. A safe strategy is to rearrange so that the varying part of the expression acts as a small perturbation around the fixed point, for instance by writing x = x − k·f(x) with a suitable constant k. This leads to the relaxation method and links directly to Newton’s method.

许多教科书问题要求学生找出能保证收敛的形式。一个稳妥的策略是改写使得表达式中变化的部分在不动点附近只充当一个小扰动,例如通过 x = x−k·f(x) 并选择合适的常数 k。这引出了松弛法,并直接联系到牛顿法。


8. Speed of Convergence | 收敛速度

When |g'(s)| is strictly between 0 and 1, the iteration converges linearly, meaning the number of correct decimal places increases roughly by a constant amount each step. The asymptotic error constant is |g'(s)|. If |g'(s)|=0, convergence becomes at least quadratic: the error in the next step is proportional to the square of the current error, leading to a doubling of correct digits per iteration. This supercharged behaviour is highly desirable and is exemplified by Newton’s method. The order of convergence can be analysed by Taylor expanding g(x) around s: if g'(s)=0 and g”(s)≠0, the method is quadratically convergent.

当 |g'(s)| 严格在 0 和 1 之间时,迭代为线性收敛,意味着每一步正确小数位数大致增加一个常数量。渐近误差常数就是 |g'(s)|。如果 |g'(s)|=0,收敛至少是二次的:下一步的误差与当前误差的平方成正比,导致每次迭代正确位数翻倍。这种超级加速的行为非常理想,牛顿法就是典型例子。收敛阶可以通过将 g(x) 在 s 附近泰勒展开来分析:若 g'(s)=0 且 g”(s)≠0,方法就是二次收敛的。


9. Newton’s Method as a Special Fixer | 牛顿法:特殊的固定者

Newton’s method for solving f(x)=0 is given by xₙ₊₁ = xₙ − f(xₙ)/f'(xₙ). This can be viewed as a fixed-point iteration with the special fixer g(x) = x − f(x)/f'(x). At a simple root s where f(s)=0 and f'(s)≠0, differentiating this g using the quotient rule gives g'(s) = 0. Hence Newton’s method is a fixer that makes |g'(s)| = 0 at the root, securing at least quadratic convergence. This is why Newton’s method typically homes in on a root extremely quickly once it’s close. However, the method requires the derivative f'(x) and may fail if the initial guess is far from a root or near a point where f'(x)=0.

求解 f(x)=0 的牛顿法由 xₙ₊₁ = xₙ − f(xₙ)/f'(xₙ) 给出。这可以看作不动点迭代,其特殊的固定者为 g(x)=x−f(x)/f'(x)。在单根 s 处(f(s)=0 且 f'(s)≠0),利用商法则对此 g 求导可得 g'(s)=0。因此牛顿法是一种使得在根处 |g'(s)|=0 的固定者,保证了至少二次收敛。这就是为什么牛顿法一旦接近根,通常能极快地逼近解。不过,该方法需要导数 f'(x),若初始猜测远离根或靠近 f'(x)=0 的点,则可能失败。


10. Worked Example and Common Pitfalls | 实例与常见陷阱

Let us solve x² − 2 = 0 (finding √2) using three fixers. Take x₀ = 1.5.

让我们用三个固定者求解 x²−2=0(求 √2)。取 x₀=1.5。

Comments

屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导,国外大学本科硕士研究生博士课程论文辅导

This site uses Akismet to reduce spam. Learn how your comment data is processed.

咨询微信:16621398022(同微信) · 联系我们