数值分析 笔记 2

非线性方程解法

非线性方程的含义很广泛，常见的特例为$n$次多项式方程，对于任一非线性方程，如果其某一实根$x^{*}$满足：

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

则称$x^{*}$为$m$重根

对于解方程这个问题，输入为函数值$y$，解为自变量$x$，因此其绝对条件数为：

$$\Big| \frac{\Delta x}{\Delta y} \Big| \approx \Big| \frac{1}{f'(x)} \Big|$$

因此对于多重根即$f'(x) = 0$，问题是很敏感的

二分法

二分法的成立基于以下充分条件：

二分法的算法很简单，不再赘述，注意其中$\varepsilon$代表区间长度阈值

如果使用计算机进行二分法求解，那其最小的有根区间长度为$2^{E + 1}\varepsilon_{\text{mach}}$，其中$E$为准确根$x^{*}$对应的浮点数指数，即$E = \lfloor \log_{2}|x^{*}| \rfloor$，因此其最大相对误差为$2\varepsilon_{\text{mach}}$

二分法总能收敛，但是收敛速度慢，且初始区间难以确定

不动点迭代法

首先将方程$f(x) = 0$变形为$x = g(x)$，从而将求$f(x)$零点问题转化为求$g(x)$不动点的问题，而不动点可以通过迭代来实现：

$$\begin{align*} x_{0} &= C \\ x_{k + 1} &= g(x_{k}) \end{align*}$$

如果最终序列$x_{k}$收敛到$x^{*}$，则$x^{*}$为原方程的根

关键问题是，对于同一个函数$f(x)$可能会有多种变形方式，在这种情况下，不同变形的收敛性可能并不相同，例如对于$x^{4} - x - 2 = 0$：

$$\begin{align} x &= x^{4} - 2 \\ x &= \sqrt[4]{x + 2} \end{align}$$

其中式$(1)$是发散的，但是式$(2)$是收敛的

全局收敛

针对不动点迭代法的收敛性，有如下定理：

局部收敛

上述全局收敛是求出了迭代式在一整个区间上的行为，而在不动点周围的邻域内，同样可以定义局部收敛：如果$g(x)$有不动点$x^{*}$，$\exist D = [x^{*} - \delta, x^{*} + \delta]$，使得$\forall x_{0} \in D$，迭代法都收敛到$x^{*}$，则称该方法局部收敛

证明略

稳定性与收敛阶

若非线性方程进行数值解时，得到的解序列$x_{n}$收敛，并且误差项$e(x_{k}) = x_{k} - x^{*} $满足：

$$\lim_{k\to \infty} \frac{|e(x_{k + 1})|}{|e(x_{k})|^{p}} = c \in (0, \infty)$$

则称其为$p$阶收敛，即收敛阶为$p$，对于一个收敛的方法，其收敛阶是唯一的，例如二分法的收敛阶大体上是1

收敛阶越高，迭代法收敛的越快

判断收敛阶的充要条件是：

其证明方法较简单，如下

• 充分性：由Lagrange余项Taylor展开可知：

  $$e(x_{k + 1}) = g(x_{k}) - g(x^{*}) = \frac{g^{(p)}(x_{k})}{p!}(x_{k} - x^{*})^{p} = \frac{g^{(p)}(x_{k})}{p!}e(x_{k})^{p}$$

  之后直接按照收敛阶的定义即可
• 必要性，假设其直到$q \neq p$阶导数不为0，之前所有阶均为0，同样由Taylor可以证明其$q$阶收敛，这与收敛阶的唯一性矛盾

牛顿法

原理很简单，利用切线近似曲线

在点$(x_{k}, f(x_{k}))$处，函数的切线方程为：

$$f(x_{k}) + f'(x_{k})(x - x_{k}) = 0$$

转化形式后可以得到迭代式：

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

保证$f'(x_{k}) \neq 0$，求导易知对于$f(x)$的单根 $x^{*}$ 有 $g'(x^{*}) = 0$，因此有：

例如计算机中使用的平方根的方式即为对$f(x) = x^{2} - c$利用牛顿法求根：

$$x_{k + 1} = \frac{1}{2}(x_{k} + \frac{c}{x_{k}})$$

可以证明这种方法是在$\mathbb{R}^{+}$上全局收敛的

判停准则

迭代法的停止条件通常有：

• $|f(x_{k})| \leq \varepsilon_{1}$：残差判据，但这可能说明我们找到了另一个根，而非期望收敛的值
• $|x_{k} - x_{k - 1}| \leq \varepsilon_{2}$，误差判据
• $|x_{k} - x_{k - 1}| \leq \varepsilon_{3}|x_{k}|$，相对误差判据

通常将从残差判据与下面两种或其中一种结合使用

问题

• 牛顿法是局部收敛的，依赖于初值的选取

• 牛顿法对连续性的要求较高，因为$g'(x)$中涉及到了$f''(x)$

  例如$f(x) = \text{sgn}(x - a)\sqrt{x - a}$则对任意初值都无法收敛，原因是$f'(x)$在$x = a$处并不连续

割线法与抛物线法

割线法是为了规避牛顿法中的求导问题，使用过$x_{k}, x_{k - 1}$的割线来代替切线，其迭代方程为：

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

这是一种广义的迭代法（同时由前两项进行迭代）其收敛阶满足：

如果我们能够从前三项推导，这样的方法称之为抛物线法，但是开口向上的抛物线不一定与x轴有交点，因此我们可以构建一个$x = P(y)$的抛物线，之后用$x_{k}, x_{k - 1}, x_{k - 2}$待定系数

这个方法同样称为逆二次插值法，局部收敛阶 $p\approx 1.839$

实用求根技术

牛顿下山法

防止牛顿法迭代过程发散的一种有效思路，定义一个比例因子序列$\lambda_{i}\in (0, 1]$，迭代方程为：

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

算法为：

牛顿下山法