CS205A Lecture 9 Nonlinear equations and convergence analysis

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

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

Chapter 7 非线性系统

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

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

单变量问题

在讨论之前,考虑以下两个例子:

上述函数的求根问题不好处理,这说明在求解问题之前,我们需要对函数$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$连续,那么我们可以利用如下定理设计一个求根算法:

定理7.1 (中值定理)

如果我们知到两个值$\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’$的误差上界,即

在二分法中,我们有

并且由算法,不难得到

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

不动点法

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

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

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

在之前的假设下,我们有如下算法:

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

下面证明算法的收敛性,考虑$E_k$:

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

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

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

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

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

那么

因此

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

牛顿法

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

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

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

求导可得

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

所以

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

割线法

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

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

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

因此该算法的效率介于线性和$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$
  • 一个方法可能收敛很快,但是每次迭代可能需要更多计算量(牛顿法),所以我们更倾向于对简单算法做更多次的迭代。

本文标题:CS205A Lecture 9 Nonlinear equations and convergence analysis

文章作者:Doraemonzzz

发布时间:2019年04月06日 - 15:02:00

最后更新:2019年04月06日 - 16:00:49

原始链接:http://doraemonzzz.com/2019/04/06/CS205A Lecture 9 Nonlinear equations and convergence analysis/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。