不动点迭代及其收敛性

什么是不动点迭代法

函数$f$的不动点是一个值$x$使得$f(x) = x$。例如，0和1是函数$f(x) = x^2$的不动点，因为$0^2 = 0$而$1^2 = 1$，即曲线$y = f(x)$与直线$y = x$存在交点$P(x^{\ast}, x^{\ast})$。

对于某些函数，通过某些初始猜测出发，反复地应用$f$，

直到值的变化不大时，就可以找到它的一个不动点。

算法描述如下：

def solve(f, guess, epsilon):
    i = 0
    while abs(guess - f(guess)) > epsilon:
        guess = f(guess)
        print '[ Epoch {0} ] guess = {1}'.format(i, guess)
        i += 1
    return guess

下面示例演示了

1. 求解$f(x) = \frac{x + \frac{5}{x}}{2} = x$也即求解$x^2=5$。
2. 求解$f(x) = \frac{x + \frac{8}{x^2}}{2} = x$也即求解$x^3=8$。

print solve(lambda x: (x + 5 / x) / 2.0, 10.0, 1e-8)
# [ Epoch 5 ] guess = 2.2360679775
print solve(lambda x: (x + 8 / (x ** 2)) / 2.0, 10.0, 1e-8)
# [ Epoch 27 ] guess = 2.00000000337

不动点迭代法的收敛性

一般地，将非线性方程$f(x) = 0$化为一个同解方程

并且假设$\varphi(x)$是一个连续函数，选定一个点$x_0$，计算

②式为求解非线性方程①的迭代公式，$\varphi(x)$为迭代函数，$x_k$为第$k$步的迭代值。 如果存在一点$x^*$，使得序列${x_k}$满足，

称②式收敛，否则为发散。

上例中，我们求解了方程$f(x) = x^2 - 5 = 0$，给出的同解方程是$\varphi(x) = \frac{x + \frac{5}{x}}{2} = x$和。

为什么我们不使用更简单的$\varphi(x) = \frac{5}{x} = x$？答案是，因为它不收敛，它关于直线$y = x$对称，易得$x_1 = \varphi(x_0)$及$x_2 = \varphi(x_1) = x_0$，$x$值总在$x_0$和$\varphi(x_0)$之间摆动。

一般地，我们有两种类型的收敛迭代。

对应有两种类型的发散

通过观察我们发现，在曲线$y = \varphi(x)$与直线$y = x$交点$P(x^{\ast}, x^{\ast})$处，$x^{\ast}$对应的曲线切线斜率的绝对值小于1（y=x的斜率）时，迭代收敛。一旦交点对应的曲线切线的斜率大于1，迭代就会无法收敛。

$\varphi(x)$要收敛，必须满足如下不动点定理。

设迭代函数$\varphi(x)$在区间$[a, b]$上连续，且满足

(1). 当$x \in [a, b]$时，$a \leq \varphi(x) \leq b$；

(2). 存在一正数$L$，满足$0 < L < 1$，且$\forall x \in [a, b]$，有

则：

a). 方程$\varphi(x) = x$在$[a, b]$内有唯一解$x^*$

b). 对于任意初值$x_0 \in [a, b]$，迭代法$x_{k+1} = \varphi(x_k)$均收敛于$x^{\ast}$

c). $\left| x_k - x^* \right| \leq \frac{L}{1 - L}\left| x_k - x_{k - 1} \right|$

d). $\left| x_k - x^* \right| \leq \frac{L^k}{1 - L}\left| x_1 - x_0 \right|$

证明过程如下：

设 $f(x) = x - \varphi(x)$，则$f(x)$在[a, b]上连续可导，根据条件(1)，

由根的存在定理，方程$f(x) = 0$在$[a, b]$上至少存在一个根(存在性)。

根据条件(2)，

则函数$f(x)$在$[a, b]$上单调递增，a).方程$f(x) = 0$在$[a, b]$内有唯一解$x^{\ast}$(唯一性)

由微分中值定理

即

因为$L < 1$, 因此对于任意初值$x_0$，迭代法$x_{k+1} = \varphi(k)$均收敛于$x^{\ast}$。