Numerical Methods Using MATLAB(4版)-02-Nonlinear Equations

引自Numerical Methods Using MATLAB(4版)书籍，如有侵权请联系删除

前言

这一章节主要讲述求 $f(x)=0$ 这一方程根的不同方法。

学习总结

不动点迭代

我们假设按照 $g(x)$ 这一函数迭代，初始值为 $p_0$ ，那么我们接下来会得到序列 $\{p_k\}$ 。如果这个序列是收敛的，那么能得到一个不动点 $P$ 使得 $P=g(P)$ 。
当 $g∈C[a,b]$ 时，有以下几条定理：
1、如果 $y=g(x)$ 满足 $y∈[a,b]$ ， $x∈[a,b]$ ，那么 $g$ 在 $[a,b]$ 中有不动点 $P$ 。
2、如果 $g'(x)$ 在 $(a,b)$ 中有定义且对任意 $x∈(a,b)$ 存在 $|g'(x)| \leq K < 1$ ，那么 $g$ 在 $[a,b]$ 上有唯一不动点 $P$ 。
当 $g,g'∈C[a,b];p_0∈(a,b);$ 对所有 $x∈[a,b],g(x)∈[a,b]$ 时，有以下几条定理：
1、如果对任意 $x∈(a,b)$ 存在 $|g'(x)| \leq K < 1$ ，那么迭代收敛到唯一不动点，称为吸引不动点。
2、如果对任意 $x∈(a,b)$ 存在 $|g'(x)| > 1$ ，那么迭代无法收敛到不动点，称为反叛不动点。
P46的公式14是如何得到的？
|a-b|<=|a-c|+|c-b|

证明过程

方法一二分法

二分法的过程很简单在此不过多赘述。

二分法的定理：
假设 $f∈C[a,b]$ ，并且存在 $r∈[a,b]$ 使得 $f(r)=0$ 。如果 $f(a)$ 和 $f(b)$ 符号相反，且 $\{c_n\}_{n=0}^{\infty}$ 代表二分过程中中间点序列，那么有
$|r-c_n| \leq \frac{b-a}{2^{n+1}},n=0,1,...$
且有
$\lim_{n\rightarrow\infty}c_n=r.$

二分法的优点：
可以提前预估解的精确度。假设重复 $N$ 次二分，那么我们通过以下能够保证 $c_N$ 近似于解，且误差少于 $\delta$ ：
$N=int(\frac{ln(b-a)-ln(\delta)}{ln(2)})$
proof.
$(1)Nln2=ln(b-a)-ln(\delta)$
$(2)ln2^N=ln(b-a)-ln(\delta)$
$(3)2^N=\frac{(b-a)}{\delta}$
$(4){\delta}=\frac{(b-a)}{2^N}$

方法二错位法

因为二分法收敛得比较慢，所以我们发明了错位法。

错位法的原理：
该方法连接 $(a,f(a))$ 和 $(b,f(b))$ 两点，其连线在 $x$ 轴的交点取为 $(c,0)$ ，然后和二分法一样， $f(c)$ 与哪个端点互为相反数，则更新区间。
其中求 $c$ 的公式如下：
$c=b-\frac{f(b)(b-a)}{f(b)-f(a)}$

其中，二分法的误差err=abs(b-a)，错位法的误差err=abs(b-a)/2
但是错位法的误差为什么是这样的呢？证明？

逼近区域的初始化和收敛标准

上述方法都是全局收敛的，但如果在区间内有多个解，那么我们就需要更小的区间分别来寻找这些解。接下来会描述Newton-Raphson和割线法来求解，这两种方法都是求局部收敛的。这种局部收敛会收敛得更快。有部分算法会结合这两种类型的算法，在开始使用全局收敛，当接近根的时候再使用局部收敛。
作图是一种方法。但是计算机有时候也会遇到精确度不够的特殊情况，我们需要考虑到。与此同时，由于计算机精度有限，我们可能会遇到 $f(x_k) \approx 0$ 的情况，这时候我们需要判断附近 $x_{k-1}$ 和 $x_{k+1}$ 两点斜率是否相反，相反才行。
即，判断根，一个是两边 $f(x)$ 符合相反，一个是两边斜率相反且 $f(x_k) \approx 0$ 。
$(i)(y_{k-1})(y_k)<0,or$
$(ii)|y_k|<\epsilon \ and \ (y_k-y_{k-1})(y_{k+1}-y_k)<0.$
对于计算机求根，我们需要一个算法来判断什么时候循环终止，因此我们需要制定数值，防止死循环，同时也要保持一定精度。我们可以有以下两种评判标准：
$|p_n-p_{n-1}| < \delta,(the \ \ absolute \ \ error)$
$\frac{2|p_n-p_{n-1}|}{|p_n|+|p_{n-1}|} < \delta,(the \ \ relative \ \ error)$
（其中，第二种标准为什么不是直接除 $|p_n|$ ，是为了防止除0现象。）

解误差与残差的区别

残差

解误差

如图，解误差是 $y$ 的误差，残差是 $x$ 的误差。一般情况下我们很难得到 $P$ ，所以解误差少用。

方法三 Newton-Raphson法

如果f(x)，f'(x)，f''(x)在根p附近连续，那么我们可以使用更快的算法来收敛，其中Newton-Raphson法就是其中最有用和最出名的算法之一。牛顿法并不能保证找到根，也会出现循环或发散的情况。

Newton-Raphson法的原理
假设 $f∈C^2[a,b]$ ，且 $p∈[a,b]$ ， $f(p)=0$ 。如果 $f'(p) \neq 0$ ，则存在 $\delta > 0$ 使得序列 $\{p_k\}_{k=0}^{\infty}$ 满足以下公式：
$p_k=g(p_{k-1})=p_{k-1}-\frac{f(p_{k-1})}{f'(p_{k-1})},k=1,2,...$
其中序列最终收敛到 $p$ ，且 $p_0∈[p-\delta,p+\delta]$ 。
且根据不动点迭代的原理，需满足
$g'(x)=\frac{f(x)f'''(x)}{(f'(x))^2}<1,for \ \ all \ \ x∈(p-\delta,p+\delta).$

proof.
$p_0$ 非常逼近 $p$
$(1)f(x)=f(p_0)+f'(p_0)(x-p_0)+\frac{f''(c)(x-p_0)^2}{2!},$

$(2)0=f(p_0)+f'(p_0)(x-p_0)+\frac{f''(c)(x-p_0)^2}{2!},$

$(3)0 \approx f(p_0)+f'(p_0)(x-p_0),$

$(4)p_1 = p_0-\frac{f(p_0)}{f'(p_0)}.$

Newton-Raphson法的推论
可以用来找平方根，这个推论的重点在于函数g(x)只能有简单的加减乘除运算，如果有根号运算，可能会陷入循环，因此我们采用这种推论求根号。
假设 $A>0$ 且 $p_0>0,p_0 \approx \sqrt{A}$ ，有
$p_k=\frac{p_{k-1}+\frac{A}{p_{k-1}}}{2},k=1,2,...$
使得 $\lim_{n\rightarrow\infty}p_k=\sqrt{A}$ 。

proof.
设 $f(x)=x^2-A$ ，再用牛顿法求根迭代。

根的定义
假设 $f(x)$ 及其 $M$ 阶导数 $f^{(M)}(x)$ 在 $x=p$ 上有定义且连续，并当且仅当
$f(p)=0,f'(p)=0,...,f^{(M-1)}(p)=0,f^{(M)}(p) \neq 0$

则我们称 $f(x)=0$ 在 $x=p$ 上有 $M$ 个根。
且存在一个连续函数 $h(x)$ 可以表达为 $f(x)=(x-p)^Mh(x),h(p) \neq 0.$

收敛速度
如果p是单根，那么牛顿法可以快速收敛，每次迭代精确的小数位数都可以翻倍。如果p是多根，每次后继误差都是前面误差的一部分。这里是为什么？
假设 $\{p_n\}_{n=0}^{\infty}$ 收敛到 $p$ ，且有 $E_n=p-p_n(n \geq 0)$ （解误差，可以用残差代替）。如果正常量 $A \neq 0$ ， $R >0$ 存在，则
$\lim_{n \rightarrow \infty}\frac{|p-p_{n+1}|}{|p-p_n|^R}=\lim_{n \rightarrow \infty}\frac{|E_{n+1}|}{|E_n|^R}=A.$
其中 $R$ 为序列收敛到 $p$ 的阶数， $A$ 为渐进误差常量。
当 $R=1$ 时，一般有 $A<1$ ，称为线性收敛。
当 $R=2$ 时，一般有 $A$ 为常量即可，称为平方收敛。
$R$ 越大，收敛得越快。

牛顿法收敛速度的定理
如果 $p$ 是单根，收敛速度是平方的， $|E_{n+1}| \approx \frac{|f''(p)|}{2|f'(p)|}|E_n|^2$ 。
如果 $p$ 是 $M$ 根，收敛速度是线性的， $|E_{n+1}| \approx \frac{M-1}{M}|E_n|$ 。

加速牛顿法的收敛速度
牛顿法是线性收敛到根的，为了加速，我们可以使用以下公式产生序列平方收敛到根：
$p_k=p_{k-1}-\frac{Mf(p_{k-1})}{f'(p_{k-1})}.$

方法四割线法

割线法与错位法几乎是一样的，但是错位法是在缩小区间，割线法是在快速找点。其单根收敛阶数为 R ≈ 1.618033989。
$p_{k+1}=g(p_k,p_{k+1})=p_k-\frac{f(p_k)(p_k-p_{k-1})}{f(p_k)-f(p_{k-1})}.$

收敛速度的比较

方法五 Aitken's Process

牛顿法中对于多根收敛速度是线性的，而使用加速牛顿法，得提前知道根的个数。因此我们提出一些其他方法来加速。
定义
对于收敛数列 $\{p_n\}_{n=0}^{\infty}$ ，定义 $\Delta p_n=p_{n+1}-p_n,n \geq 0$ 。而 $\Delta^kp_n=\Delta^{k-1}(\Delta p_n),k \geq 2$ 。
举例： $\Delta^2p_n=\Delta(\Delta p_n)=\Delta(p_{n+1})-\Delta(p_n)=p_{n+2}-2p_{n+1}+p_n$ 。
定理
假设数列 $\{p_n\}_{n=0}^{\infty}$ 线性收敛到 $p$ ，且对所有 $n \geq 0$ 有 $p-p_n \neq 0$ 。如果这里存在一个实数 $A$ ，有 $|A|<1$ 使得
$\lim_{n \rightarrow \infty}\frac{p-p_{n+1}}{p-p_n}=A,$
则我们可以定义数列 $\{q_n\}_{n=0}^{\infty}$ 有
$q_n=p_n-\frac{(\Delta p_n)^2}{\Delta^2p_n}=p_n-\frac{(p_{n+1}-p_n)^2}{p_{n+2}-2p_{n+1}+p_n}$
通过 $\lim_{n \rightarrow \infty}|\frac{p-q_n}{p-p_n}|=0$ 我们可以知道 $q_n$ 收敛要快于 $p_n$ 。

方法六 Muller's Method

该方法是割线法的另一种演绎，只是减去了导数的计算，但需要三个点。该方法比割线法快甚至几乎和牛顿法一样快，但会涉及复杂一点的运算。
假设 $p_2$ 是最近似 $p$ 的点，定义变量 $t=x-p_2$ ， $h_0=p_0-p_2$ ， $h_1=p_1-p_2$ 。
定义二元方程 $y=at^2+bt+c$ 。
代入，我们可以分别得到以下式子：
$t=h_0:ah_0^2+bh_0+c=f_0,$

$t=h_1:ah_1^2+bh_1+c=f_1,$

$t=0:a0^2+b0+c=f_2,$

通过以上式子我们求得 $a,b,c$ 。然后求根 $z=\frac{-2c}{b\pm \sqrt{b^2-4ac}}$ 。最后可得 $p_3=p_2+|z|$ 。在之后的迭代中，我们舍去 $\{p_0,p_1,p_3\}$ 中离 $p$ 最远的点，并将 $p_2=p_3$ 。

词汇学习

spherical 球形
corollary 必然的
oscillate 摆动
interval 间隔的
consecutive 连续的
leisure 休闲
concavity 凹
slope 坡
quotient 商
secant 割线
projectile 弹丸
elapse 过去
fitfall 健身
lemma 引理
asymptotic 渐进的
parabola 抛物线
auxiliary 辅助的