非线性方程基本理论

形如 $f(x)=0$
有没有根、有多少个根很难确定
一般求 $[a,b]$ 上的根

定义 $m$ 重根：若在 $x^*$ 点满足

f(x^*)=f'(x^*)=f''(x^*)=\cdots=f^{(m-1)}(x^*)=0

则称 $x^*$ 是 $f(x)$ 的 $m$ 重根

问题敏感性分析

可以把求解问题看成是 $f(x)=y$ ，求解 $y=0$ 时的 $x$ ，即 $y$ 是输入， $x$ 是输出

于是问题的绝对条件数为

\left|\frac{\Delta x}{\Delta y}\right|\approx\left|\frac1{f'(x^*)}\right|

于是， $f'(x^*)$ 越小，问题越敏感，重根的情形相当敏感

迭代法求解非线性方程

二分法

略去方法本身，以下是二分法的一些特性：

可靠方法，即总是可以收敛（经过有限次迭代后，区间长度会小于浮点数计算的精度）
缺点：收敛较慢；不容易确定初始有根区间
可以与其他方法结合使用

不动点迭代法

将 $f(x)=0$ 变形为 $g(x)=x$ ，选取初始值 $x_0$ ，进行如下迭代：

x_{n+1}=g(x_n)

若数列收敛到 $x^*$ ，则 $x^*$ 是 $g(x)$ 的不动点，即

g(x^*)=x^*

于是 $x^*$ 是 $f(x)=0$ 的解

注 $g(x)$ 不一定是 $f(x)+x$ ，可以采取其他形式的变形，这取决于 $f(x)$ 的具体形式

例在 $x_0=1.5$ 附近求 $x^4-x-2=0$ 的解

法一：令 $g(x)=\sqrt[4]{x+2}$ ，可以收敛到解

法二：令 $g(x)=x^4-2$ ，看上去计算量较小，但数列发散

不动点迭代法的收敛条件

定理设 $g(x)\in C[a,b]$ ，若

(1) $\forall x\in[a,b],\ a\leq g(x)\leq b$

(2) $\exists L\in(0,1),\ \forall x_1,x_2\in[a,b]$ ， $|g(x_1)-g(x_2)|\leq L|x_1-x_2|$

则 $g(x)$ 在 $[a,b]$ 上存在唯一不动点

证明

由(1)知

g(a)-a\geq 0 \geq g(b)-b

于是不动点存在；

假设不动点不唯一，即存在不动点 $x_1,x_2$ ，则

\frac{|g(x_1)-g(x_2)|}{|x_1-x_2|}=1

与(2)矛盾。

定理（全局收敛的充分条件） 若 $g(x)$ 满足上述两条件，则对任意初值 $x_0\in[a,b]$ ，不动点迭代 $x_{k+1}=g(x_k)$ 都收敛

证明

由题意，存在满足条件(2)的 $L\in(0,1)$

于是

|g(x_{k+1})-g(x_k)|\leq L|x_{k+1}-x_{k}|=L|g(x_{k})-g(x_{k-1})|

又

|g(x_1)-g(x_0)|\leq |a-b|

于是

|g(x_{k+1})-g(x_k)|\leq L^k|a-b|

于是数列 $g(x_k)$ 收敛

注上述定理中所谓的全局收敛即相对区间 $[a,b]$ 而言

注上述定理的条件(2)常常替换为更强但更易使用的形式： $g(x)\in C^1[a,b]$ 且
$\forall x\in[a,b],\ |g'(x)|<1$

定义（局部收敛） 若 $g(x)$ 有不动点 $x^*$ ， $\exists\ x^*$ 的邻域 $D:\ [x^*-\delta,x^*+\delta]$ ，使 $\forall x_0\in D$ ， $x_{k+1}=g(x_k)$ 都收敛到 $x^*$ ，则称该方法局部收敛

定理（局部收敛的充分条件） 设 $x^*$ 是 $g(x)$ 的不动点，若 $|g'(x^*)|<1$ ，且 $g'(x)$ 在 $x^*$ 的某邻域上连续，则迭代法局部收敛

证明略。可以利用全局收敛证明

稳定性与收敛阶

定义（收敛阶） 设迭代解序列 $\{x_0,x_1,\cdots,x_k,\cdots\}$ 收敛，若误差 $e(x_k)=x_k-x^*$ 满足：

\lim\limits_{k\to+\infty}\frac{|e(x_{k+1})|}{|e(x_k)|^p}=c\neq 0

则称该迭代法 $p$ 阶收敛

注对一个收敛的迭代法，收敛阶唯一、

注事实上，收敛阶不止对不动点迭代法有效。例如二分法可以认为近似是1阶收敛， $c=0.5$

定理（不动点迭代的收敛阶） 对迭代法 $x_{k+1}=g(x_k)$ ，若 $g^{(p)}(x)$ 在不动点 $x^*$ 附近连续，且整数 $p\geq 2$ ，则该方法在 $x^*$ 的邻域上 $p$ 阶收敛等价于：

g'(x^*)=g''(x^*)=\cdots=g^{(p-1)}(x^*)=0\neq g^{(p)}(x^*)

注定理证明可以考虑Taylor公式

牛顿法

牛顿法的优点：

减少不动点迭代法的构造盲目性
具有较好的收敛性

牛顿法原理

曲线在一点 $x_k$ 的切线方程为

P(x)=f(x_k)+(x-x_k)f'(x_k)

用此切线近似曲线在该点的局部，则可以用此切线的零点估计曲线的零点，即：

x_{k+1}=x\bigg|_{P(x)=0}=x_k-\frac{f(x_k)}{f'(x_k)}

这构造出了一种迭代法

牛顿法可以看成是一种具有特殊的 $g(x)$ 形式的不动点迭代：

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

注意到 $f(x)$ 的零点一定是 $g(x)$ 的不动点，因此可以利用不动点迭代法的收敛阶判断定理来分析

由于

g'(x)=1-\frac{[f'(x)]^2-f(x)f''(x)}{[f'(x)]^2}=\frac{f(x)f''(x)}{[f'(x)^2]}

因此， $f(x)$ 的零点也是 $g'(x)$ 的零点（这要求对应的零点是单根，否则上述等式分母为 $0$ ），于是牛顿法对单根至少2阶收敛

定理（牛顿法的收敛性） 若牛顿法在 $f(x)$ 的某个单根处的3阶导数连续，则牛顿法在此单根处至少局部2阶收敛

注对重根的情况，牛顿法只有一阶收敛性，并不比二分法更快

注尽管牛顿法的收敛性好，但它对函数的光滑性和初值选取有更高的要求

迭代法的判停准则

三种判停准则：

残差判据： $|f(x_k)|\leq \epsilon_1$
误差判据： $|x_k-x_{k-1}|\leq\epsilon_1$
相对误差判据： $|x_k-x_{k-1}|\leq \epsilon_3|x_k|$

三种判据有时需要组合使用

割线法与抛物线法

割线法是对牛顿法即“切线法”的进一步近似，使用割线近似切线来避免导数计算，使用的割线如下：

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

于是，迭代规则为

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

这是一种广义的不动点迭代法（不动点迭代法不应涉及 $x_{k-1}$ ）

定理（割线法的收敛阶） 若 $f(x)$ 在根 $x^*$ 的某邻域内二阶连续可微且 $f'(x)\neq 0$ ，当 $x_0,x_1$ 充分接近 $x^*$ 时（局部性），割线法按 $\phi^{-1}=\frac{\sqrt{5}+1}{2}\approx 1.618$ 阶收敛

割线法的另一种解释为：根据 $x_{k},x_{k-1}$ 线性插值得到的割线来求零点

因此，如果我们引入 $x_{k-2}$ ，则可以进行二次插值，得到一条对称轴平行于 $x$ 轴的抛物线，以此抛物线求零点的迭代法称为抛物线法

抛物线法的局部收敛阶为 $p\approx 1.839$

数值计算上的其他求根技术

牛顿下山法

为了防止牛顿法发散，选取一系列从1开始递减的比例因子 $\lambda_1\in(0,1]$ ，迭代方法改为如下：

x_{k+1}=x_k-\lambda_if(x_k)/f'(x_k)

判停准则为

|f(x_{k+1})|<|f(x_k)|

Zeroin通用求根算法

在有根区间内依次执行逆二次插值法、割线法、二分法

无需计算导数，且收敛效果较好