Fixed-Point Iteration 原理

前言：本文主要内容来自于对 Numerical Analysis, Richard L. Burden, J. Douglas Faires 一书 CHAPTER 2 Fixed-Point Iteration的归纳与思考

一、关于fixed-point

1. 什么是fixed point？

定义

The number p is a fixed-point for a given function g if g( p ) = p。

可以看到，fixed-point 是自变量与函数取值相同的点的横（纵）坐标，也可以看作是函数g( p ) 和函数y = f( x ) 的交点横（纵）坐标。

2. 推出该概念有什么用？

可以将求根问题转化为 fixed-point 求解问题，从而起到简化作用。两种问题在下面两种情况下可以相互转换。

(i) Given a root-finding problem f( p ) = 0, we can define functions g with a fixed point at p in a number of ways, e.g.
g( x ) = x - f( x ) , or as g( x ) = x +kf( x ), where k is a constant
(ii) If the function g has a fixed point at p, then the function defined by f( x ) = x - g( x ) has a zero at p.

3. 怎么判断函数是否存在fixed point？

下面给出fixed point 的存在性和唯一性定理，两者可以分别用中值定理和拉格朗日均值定理证明。需要注意的是，该定理为fixed point 存在的充分不必要条件。例如函数 f( x ) =$3^{-x}$3−x 在区间[0,1]上存在唯一不动点，但是却不满足唯一性条件（g’(0) = -1.0986）。
存在性

If g $\in$∈ C[a, b] and g( x ) $\in$∈ [a, b] for all x $\in$∈ [a, b], then g has at least one fixed point in [a, b].

唯一性

If, in addition, g’( x ) exists on (a, b) and a positive constant k < 1 exists with |g’( x )| $\leq$≤ k, for all x $\in$∈ (a, b), then there is exactly one fixed point in [a, b].

二、Fixed-Point Iteration

对于阶数较低的多项式函数，可以直接求解方程得到方程的根或者是fixed point，但是对于高阶多项式模型和指数函数等复杂函数，例如：p = g( p ) = $3^{-p}$3−p ，直接求解变得很困难，因此提出了迭代求近似解的思路。

迭代过程：
程序流程：

三、x = g(x) 函数形式如何选择？

接下来给一个定点迭代求方程根的问题实例。我们知道方程$x^3$x3+$4x^2$4x2-10 = 0，在区间[1，2]上有一个根。利用 fixed-point iteration 方法求解该根的逼近值时，需要根据方程构造形如 x = g(x) 的fixed-point form。通过对原方程进行变型，我们得到了以下5种不同的表达形式

令初始估计值 $p_0$p0​ = 1.5，得到以下迭代表

已知 actual root is 1.365230013。可以从表中看到

• g 取不同形式时，算法迭代次数差异较大；
• g 取不同形式时，根的估计值不同，甚至有些会出现错误（如a 发散，b 求解错误）；
• 似乎函数的复杂度与迭代次数和精度之间出现了矛盾。

如何构造 fixed-point form 使其准确而快速的收敛到根值问题的准确解呢？

首先，我们引入一个定理 Fixed-Point Theorem

上述定理是对 fixed point 存在性和唯一性定理的延伸，大概内容是讲如果一个函数在一个区间内满足了存在性和唯一性定理，那么可以通过逐次逼近的方式获得该 fixed point 的近似解。

近似解 $p_n$pn​ 和真实值 $p$p 逼近的误差有多大呢？

上述定理的推论告诉了我们该误差的大概范围

可以看到的是，两者的接近程度(收敛率)与因子 $k^n$kn 直接相关。意思就是，如果 $k$k 越小，那么逼近的精度越高，同时算法的收敛速度也会越快（因为较小的n值也能满足逼近精度要求）。
到这里我们即能回答上面的问题了，我们利用 Fixed-Point Iteration 求解根值问题的解时，构造的函数 g 需满足 Fixed-Point Theorem，且其导数 g’( x ) 在 fixed point 处尽可能的小。