数值分析 笔记 2

非线性方程解法

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

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

则称x∗x^{*}为mm重根

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

∣ΔxΔy∣≈∣1f′(x)∣\Big| \frac{\Delta x}{\Delta y} \Big| \approx \Big| \frac{1}{f'(x)} \Big|

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

二分法

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

若f(x)∈C[a,b]f(x) \in C[a, b]，且f(a)f(b) < 0，则f(x)f(x)在(a,b)(a, b)内至少有一个实根

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

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

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

不动点迭代法

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

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

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

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

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

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

全局收敛

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

对于g(x)∈C[a,b]g(x) \in C[a, b]，若有：

∀x∈[a,b],a≤g(x)≤b∃L∈(0,1),∀x1,x2∈[a,b],∣g(x1)−g(x2)∣≤L∣x1−x2∣\begin{align} &\forall x\in [a, b],\quad a\leq g(x) \leq b \\ &\exist L\in (0, 1), \forall x_{1}, x_{2} \in [a, b],\quad |g(x_{1}) - g(x_{2})| \leq L|x_{1} - x_{2}|\end{align}

则g(x)g(x)在[a,b][a, b]内有唯一不动点，并且∀x0∈[a,b]\forall x_{0} \in [a, b]，不动点迭代法都收敛到这个唯一的不动点x∗x^{*}，误差满足：

∣xk−x∗∣≤Lk1−L∣x1−x0∣|x_{k} - x^{*}| \leq \frac{L^{k}}{1 - L} |x_{1} - x_{0}|

如果仅需要判断收敛性，而不需要知道绝对误差的范围，则条件(4)(4)可以简化为：

∀x∈[a,b],∣g′(x)∣<1\begin{align} \forall x \in [a, b], \quad |g'(x)| < 1\end{align}

这可以由Lagrange中值定理推出

局部收敛

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

设x∗x^{*}是g(x)g(x)的不动点，若∣g′(x∗)∣<1|g'(x^{*})| < 1，且g′(x)g'(x)在x∗x^{*}某个邻域，则迭代法局部收敛

证明略

稳定性与收敛阶

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

lim⁡k→∞∣e(xk+1)∣∣e(xk)∣p=c∈(0,∞)\lim_{k\to \infty} \frac{|e(x_{k + 1})|}{|e(x_{k})|^{p}} = c \in (0, \infty)

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

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

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

若g(x)g(x)在x∗x^{*}附近 p≥2p\geq 2 阶连续可导，则收敛阶为 pp 的充要条件是：

g′(x∗)=g′′(x∗)=⋯=g(p−1)(x∗)=0g(p)(x∗)≠0\begin{align*} g'(x^{*}) = g''(x^{*}) &= \cdots = g^{(p - 1)}(x^{*}) = 0 \\ g^{(p)}(x^{*}) &\neq 0\end{align*}

其证明方法较简单，如下

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

    e(xk+1)=g(xk)−g(x∗)=g(p)(xk)p!(xk−x∗)p=g(p)(xk)p!e(xk)pe(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≠pq \neq p阶导数不为0，之前所有阶均为0，同样由Taylor可以证明其qq阶收敛，这与收敛阶的唯一性矛盾

牛顿法

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

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

f(xk)+f′(xk)(x−xk)=0f(x_{k}) + f'(x_{k})(x - x_{k}) = 0

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

xk+1=g(xk)=xk−f(xk)f′(xk)x_{k + 1} = g(x_{k}) = x_{k} - \frac{f(x_{k})}{f'(x_{k})}

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

对于f(x)=0f(x) = 0的单根x∗x^{*}，若f(x)f(x)在x∗x^{*}附近有连续二阶导数，则牛顿法至少局部二阶收敛

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

xk+1=12(xk+cxk)x_{k + 1} = \frac{1}{2}(x_{k} + \frac{c}{x_{k}})

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

判停准则

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

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

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

问题

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

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

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

割线法与抛物线法

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

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

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

若f(x)f(x)在根x∗x^{*}某邻域内二阶连续可导且一阶导不为0，当 x0,x1x_{0}, x_{1} 充分接近 x∗x^{*} 时，割线法按 p≈1.618p \approx 1.618 阶收敛

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

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

实用求根技术

牛顿下山法

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

xk+1=xk−λif(xk)f′(xk)x_{k + 1} = x_{k} - \lambda_{i}\frac{f(x_{k})}{f'(x_{k})}

算法为：

牛顿下山法
牛顿下山法
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。