首先给出一个基础的数学定理

设 $f$ 在闭区间 $[a,b]$ 上连续，且$\begin{array}{rcl} f(a)\,f(b) &<& 0 \end{array}$

则 $f$ 在 $a$ 与 $b$ 之间至少有一个根满足$f(r) = 0$

基于以上原理，我们就能提出第一种近似求根办法：二分法

二分法 The Bisection Method

首先确定范围$[a,b]$满足$\begin{array}{rcl} f(a)\,f(b) &<& 0 \end{array}$，取$\begin{array}{rcl} c &=& \dfrac{a+b}{2} \end{array}$，看 $\begin{array}{rcl} f(a)\,f(c) \end{array}$

• 如果$\begin{array}{rcl} f(a)\,f(c) &<& 0 \end{array}$，说明根在$[a,c]$，令$b=c$；
• 如果$\begin{array}{rcl} f(a)\,f(c) &\ge& 0 \end{array}$，说明根在$[c,b]$，令$a=c$；

重复以上步骤，直到区间已经够短$\begin{array}{rcl} |a-b| &<& \mathrm{tol} \end{array}$，则输出$\begin{array}{rcl} \dfrac{a+b}{2} \end{array}$

误差分析 Error Analysis

通过二分法，我们得到一系列区间 $[a_n,b_n]$ ，$\{a_n\}$递增有上界，$\{b_n\}$递减有下界

因此极限存在且相等，也就是 $f$ 的一个根。

而二分法每次区间长度减半，则

那么对于n步后，误差界即为

若误差小于半个单位（第 $p$ 位小数），就称解 精确到 $p$ 位小数：

代入上式，我们就可以得到

这也就是我们根据区间和精确位数来确定二分法步数n的办法

---

不动点迭代 Fixed-Point Iteration(FPI)

定义

若 $F(x^{*}) = x^{*}$ ，则称实数x 是函数 F 的不动点。

迭代中的收敛

全局收敛定理

考虑 $x=F(x)$，F 是定义在闭区间 $[a,b]$ 上的连续函数，若

•  $x\in[a,b]\Rightarrow F(x)\in[a,b]$（也就是F把区间映进自己）
• 存在 $0\le L<1$，使得对所有 $x\in[a,b]$，$\begin{array}{rcl} |F'(x)| &\le& L < 1 \end{array}$（也就是导数全部小于 1）

则对 任意 初值 $x_0\in[a,b]$，迭代$\begin{array}{rcl} x_k = F(x_{k-1}), \end{array}$都收敛到 $F$ 在 $[a,b]$上的 唯一 不动点 $x^{*}$。

局部收敛定理

若F连续可微，$F(x^{*})=x^{*}$，且$\begin{array}{rcl} S = |F'(x^{*})| < 1 \end{array}$

则只要初值足够靠近 $x^{*}$，不动点迭代就会局部收敛。$S$ 常称为渐近收敛因子 Asymptotic convergence factor。

判断下面的迭代格式能不能用来求近似解。若不能，改成能收敛的形式。
$\begin{array}{rcl} (1)\quad x &=& 4-2^{x} \\ (2)\quad x &=& \sqrt[3]{1+x^{2}} \end{array}$

答案：

给出一个不动点迭代格式，用来求方程$\begin{array}{rcl} x^{3}-x^{2}-0.8 = 0 \end{array}$在 $x_0=1.5$ 附近的近似解。

答案：

---

收敛率 Convergence Rate

PPT上列出了这几种收敛率

• …（比线性慢）
• 线性收敛 Linear Convergence
• 二次收敛 Quadratic Convergence（比线性收敛更快）
• …（快于二次）

线性收敛

设 $e_n$​ 是第 $n$ 步的误差（通常 $e_n=x_n-x^{*}$）。若存在收敛率 $S\neq 0$，使得

则称该方法 线性收敛，收敛率为 $S$.

• $|S|$ 越小，线性收敛越快；
• $S>0$：误差同号，从一侧靠近；
• $S<0$：误差正负交替（振荡靠近）；
• $S=0$不算线性，属于更快的超线性（例如等下要讲的Newton）

二次收敛

若 $\begin{array}{rcl} \lim_{n\to\infty}\dfrac{e_{n+1}}{e_n^{2}} &=& M < \infty \end{array}$

则称该迭代二次收敛

一般收敛率 rate of convergence

$x^*$ 是 $x=F(x)$，误差 $e_k=x_k-x^{*}$。若存在 $p$ 和 $c\neq 0$，使得

则称迭代 $x_{k+1}=F(x_k)$的 收敛率为 $p$。

由之前定义我们可知，

• 当$p=1, c<1$时，线性收敛
• 当$p=2$时，二次收敛

我们还可以通过连续对F进行求导来判断它是什么收敛：

设 $x^{*}$是不动点，在邻域 $U(x^{*})$内 $F$ 有直到 $p$阶的连续导数，并且

则该迭代局部 $p$ 阶收敛，收敛率为 $p$。

FPI 的线性收敛

设 $F$ 连续可微，$F(x^{*})=x^{*}$，且 $\begin{array}{rcl} S = F'(x^{*}) 当-1 < S < 1 且S\neq 0 \end{array}$

则当初值足够靠近 $x^{*}$ 时，不动点迭代线性收敛到该不动点，收敛率就是 $S=F'(x^{*})$

牛顿法 Newton’s Method

首先给出公式

当$f ′ (x_n )=0$ 时公式不可用。

设 $f(x^{*})=0$，$f$二阶连续可微。若$\begin{array}{rcl} f'(x^{*}) &\neq& 0 \end{array}$，则牛顿法局部二次收敛到 $x^{*}$。渐近常数为

即

若 $f'(x^{*})=0$，一般会退回线性收敛。

要理解这个，我们先来看重根

重根 multiplicty root

$x^*$ 是 $f$ 的 $m$ 重根 当且仅当 前 $m-1$阶导数在该点都为 0，第 $m$ 阶不为 0：

• m=1时，单根，$f(x^{*})=0$但 $f'(x^{*})\neq 0$（即牛顿二次收敛的条件）
• m≥2时，重根，曲线在根处与 $x$ 轴相切（甚至更平）。

若 $f$是 $m+1$次连续可微，且 $x^{*}$ 是 $m$重根，则牛顿局部线性收敛，且收敛率$S$满足

我们可以得到

修正牛顿法 Modified Newton’s Method

为了解决重根只会线性收敛的问题，我们提出修正办法：步长乘上重数 $m$

若 $f$ 在含根区间 $[a,b]$ 上 $m+1$次连续可微，$x^{*}$ 是 $m$ 重根（$m>1$），则

局部二次收敛到 $x^{*}$

对比：

作业

给出计算 $1/\sqrt{a}$的 Newton 迭代，且公式里 不要出现开方和除法。

答案：

设计 不用除法 的算法计算 $1/c$（$c>1$），再用它算 $1/1.2345$。

答案：

割线法 Secant Method

割线法和牛顿法很相似，它使用最近两点的差商代替导数，因此需要两个初值 $x_0,x_1$

对单根来说，割线法是超线性（superlinear）——比线性快、比二次慢。常见的收敛率是黄金比

---

敏感问题（感觉不太重要？）

若输入（方程）只改一点点，输出（根）却动很大，就称问题敏感（sensitive）。用 误差放大因子 和 条件数 来定量。

假设

• 原方程 $f(x)=0$，真根为 $r$；
• 输入加上小扰动 $\epsilon g(x)$（$\epsilon$ 很小）；
• 根变成 $r+\Delta r$，满足$\begin{array}{rcl} f(r+\Delta r)+\epsilon g(r+\Delta r) &=& 0 \end{array}$

在 $x=r$ 处把 $f,g$ 使用泰勒展开到一阶：

丢掉 $O((\Delta r)^{2})$，并用 $f(r)=0$：

若 $\epsilon$ 很小且 $f'(r)\neq 0$，分母里的 $\epsilon g'(r)$可略，得到框中的主公式：

根的扰动与 $\epsilon$ 成正比，放大倍数大约是 $|\dfrac{g(r)}{f'(r)}|$。$f'(r)$越接近 0，问题越敏感。

等价地

这其实来自 $f(r+\Delta r)\approx f'(r)\Delta r$，是线性近似的另一写法

敏感性主要还是看上面的 $\Delta r\approx -\epsilon g(r)/f'(r)$