CS205A Lecture 9 Nonlinear equations and convergence analysis

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第九讲，这一讲开始介绍非线性系统，首先介绍了单变量函数求根的问题。

Chapter 7 非线性系统

这一部分主要介绍求根的问题，即

$$\begin{aligned} 给定：&f:\mathbb R^n \to \mathbb R^m\\ 找到：&\vec x' 使得f(\vec x' )=\vec 0 \end{aligned}$$

这一部分首先介绍定义域和值域都是一维的情形，即$n=m=1$。

单变量问题

在讨论之前，考虑以下两个例子：

$$f(x)=\begin{cases} -1 & x\le 0\\ 0 & x >0 \end{cases}\\ f(x)=\begin{cases} -1 & x\in \mathbb Q\\ 0 & 其他 \end{cases}$$

上述函数的求根问题不好处理，这说明在求解问题之前，我们需要对函数$f​$做一些假设，下面给出一些假设，按照假设强弱的顺序排列：

• 连续性：当$x\to y$时，$f(x)\to f(y)$。
• Lipschitz：$\Arrowvert f(x)-f(y) \Arrowvert \le C\Arrowvert x-y \Arrowvert ​$
• 可微性：对所有的$x$，$f’(x)$存在。
• $C^k$：如果一个函数$k$阶可微，并且这$k$个导数都连续，那么称该函数是$C^k$；$C^{\infty}$说明$f$的任意阶导数存在且连续。

一个显然的事实是，随着假设增强，我们可以设计处更高效的算法来求解

$$f(x')=0$$

下面将介绍几种方法。

二分法

假设我们只知道$f$连续，那么我们可以利用如下定理设计一个求根算法：

定理7.1 (中值定理)

$$假设f:[a,b]\to \mathbb R连续, 如果f(x)<u<f(y)，\\ 那么存在介于x,y之间的z，使得f(z)=u$$

如果我们知到两个值$\ell, r$，满足$f(\ell).f(r)<0$，那么由中值定理可知$\ell, r$之间存在零点，这就给出找到零点$x’$的二分法：

1. 计算$c=\frac {\ell +r}2$
2. 如果$f(c)=0$，返回$x’=c​$
3. 如果$f(\ell).f(c)<0$，令$r=c$；否则令$\ell =c$
4. 如果$|r-\ell|<\epsilon $，返回$x’\approx c$
5. 返回步骤1

该算法每次将区间$[\ell, r]$的长度减少一半，并且保证零点在该区间内，因此该算法一定会找到零点，所以收敛性得到保证。接着研究收敛的效率，一般的，我们假设$E_k$为第$k$次迭代结果$x_k$和$x’$的误差上界，即

$$|x_k -x'| <E_k$$

在二分法中，我们有

$$E_k = |r_k -\ell_k|$$

并且由算法，不难得到

$$E_{k+1}=\frac 12 E_k$$

因为$E_{k+1}​$关于$E_k​$是线性的，所以我们称二分法是线性收敛。

不动点法

这里我们假设存在$C<1​$，使得

$$| g(x)-g(y) | \le C| x-y |$$

即满足Lipschitz条件。考虑如下问题，

$$g(x')=x'$$

满足上述条件的$x’$称为$g(x)$的不动点，特别的，求根问题等价于求解如下方程的不动点：

$$f(x)+x=x$$

在之前的假设下，我们有如下算法：

1. 初始化$x_0$
2. 令$x_k =g(x_{k-1})​$

下面证明算法的收敛性，考虑$E_k$：

$$\begin{aligned} E_k &= |x_k -x'|\\ &=|g(x_{k-1}) -g(x')|\\ &\le C|x_{k-1}- x'| & \text{Lipschitz条件}\\ &=CE_{k-1} \end{aligned}$$

因为$C<1$，所以我们有

$$E_k \le C^k |E_0|\overset {k\to \infty}\to 0$$

所以不动点法保证收敛，并且是线性收敛。

那么函数$g$合适满足上述Lipschitz条件呢？一个重要的情形是$g$为$C^1$并且$|g’(x’)|<1$。由$g’$的连续性，存在区间$N=[x’-\delta, x+\delta’]$，使得存在$\epsilon> 0$，对任意$x\in N$，我们都有

$$|g'(x)|<1-\epsilon$$

那么利用拉格朗日中值定理，我们有

$$\begin{aligned} |g(x)-g(y)| &=|g'(\theta)|.|x-y|\\ &< (1-\epsilon)|x-y| \end{aligned}$$

到目前为止，尽管不动点法保证收敛，但是由于收敛依然是线性的，所以和二分法对比似乎没有优势，但是，考虑一个特殊情形：

$$g'(x')=0$$

那么

$$g(x_k)=g(x')+\frac 12 g''(x')(x_k-x')^2+O((x_k-x')^3)$$

因此

$$\begin{aligned} E_k &= |x_k -x'|\\ &=|g(x_{k-1}) -g(x')|\\ &\le \frac 12 |g''(x')|.|(x_k-x')^2+O((x_k-x')^3)| \\ &\le \frac 12 (|g''(x')|+\epsilon).(x_k-x')^2 & 当x_{k-1}\to x'时存在上述\epsilon \\ &=\frac 12 (|g''(x')|+\epsilon)E_{k-1}^2 \end{aligned}$$

所以$E_k$关于$E_{k-1}$是二次的，因此收敛是二次收敛，二次收敛远比线性收敛快得多。

牛顿法

这里我们假设$f$是$C^1$，对于$x_k \in \mathbb R$，因为$f$可微，所以可以在$x_k$附近由直线代替：

$$f(x)\approx f(x_k)+f'(x_k)(x-x_k)$$

求解$f(x)\approx 0$可得

$$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$$

迭代上述公式的方法被称为牛顿法，下面将证明其收敛性，令

$$g(x)=x-\frac{f(x)}{f'(x)}$$

求导可得

$$\begin{aligned} g'(x)&=1-\frac{f'(x)^2-f(x)f''(x)}{f'(x)^2}\\ &=\frac{f(x)f''(x)}{f'(x)^2} \end{aligned}$$

假设$x’$是$f$的一重根，那么

$$f(x')=0,f'(x')\neq 0$$

所以

$$g'(x')=0$$

由不动点法的推导可知，上述收敛是二次的，这体现了牛顿法的优势。

割线法

在牛顿法中，我们需要求导数$f’$，如果$f$是一个非常复杂的函数，那么这将非常困难，但是由导数的定义，我们可以进行如下近似：

$$f'(x_k)\approx \frac{f(x_k) -f(x_{k-1})}{x_k -x_{k-1}}$$

将上式带入牛顿法中，得到如下迭代式

$$x_{k+1}=x_k -\frac{f(x_k)(x_k -x_{k-1})}{f(x_k) -f(x_{k-1})}$$

那么上述算法的效率如何呢？可以证明，上述收敛速率为

$$\frac {1+\sqrt 5}2$$

因此该算法的效率介于线性和$2$次之间，由于该算法不需要求解$f’$，所以是一个非常好的替代选择。

单变量情形总结

• 单变量的情形我们一般无法直接求解，但是可以用迭代法求解。
• 我们需要判断算法是否收敛，如果$E_k$是误差上界，那么我们必须要有$E_k\overset{k\to 0}\to 0$。关于收敛速度，基本情形如下：
  • 线性收敛：对某个$C<1,E_{k+1}<CE_k$
  • 超线性收敛：对某个$r>1,E_{k+1}\le CE_k^r$
  • 二次收敛：$E_{k+1}\le CE_k^2​$
  • 三次收敛：$E_{k+1}\le CE_k^3$
• 一个方法可能收敛很快，但是每次迭代可能需要更多计算量（牛顿法），所以我们更倾向于对简单算法做更多次的迭代。