非线性方程及其迭代解法

数值分析

『数值分析』4. 非线性方程与迭代解法

马上考试了，简单复习一下几种常见的非线性方程的数值迭代解法

主要包含

• 对分法
• 简单迭代法
• Steffensen 加速收敛法
• Newton迭代法

对于每种方法基本以四个角度站考

前言

求解线性方程的根可以直接求解，对于线性方程组可以用上一章学到的方法对增广炬阵求得数值解，然而对于非线性方程，甚至大多数情况都没有精确解，只能通过数值计算方法求解。因此对一些基础方法的原理，使用条件，具体评估的部分便比较重要。

几点基本符号：p收敛阶数，实际的“精确解”

二分法

• 原理

  闭区间上连续函数的零点定理

• 条件

  只能求解单根或奇数重根

• 评估

  收敛条件太慢

简单迭代法

对于$f(x)=0\Leftrightarrow x=\phi(x)$

原理

不动点定理: $x^* =\phi(x^*)$

• 关键
  • 不动点的存在性： 定理 4.1
  • 迭代法是否收敛：定理4.1 ，定理 4.2

收敛公式

$x=\phi(x)$

评估

等价的迭代公式多样，需尽可能找到其中收敛的公式并收敛速度较快的

• 定理4.4 迭代法的收敛速度依赖于迭代函数的选取

关键定理：

• 定理4.1

  $\phi(x) \in C[a,b]在(a,b)$内可导，且满足如下条件：

  • $x\in [a,b] 时,\phi(x)\in[a,b]$ ：迭代序列不超界
  • $x\in [a,b] 时,|\phi^\prime(x)\le L<1|$,其中$L$为常数

  则有：

  • 方程在区间内时有唯一跟
  • 简单迭代法序列收敛
  • 有误差估计$|s-x_k\le \frac{L^k}{1-L}|x_1-x_0||,|s-x_k\le \frac{L}{1-L}|x_k-x_{k-1}||$
  • TODO: 证明概述

• 定理4.2

  $s=\phi(s),\phi^\prime(x)$在包含$s$的开区间连续，若$|\phi^\prime(s)|<1$，迭代法局部收敛

Steffensen 加速收敛法

原理

微分中值定理，两步迭代）通过,$\phi^\prime(\xi_k) = \phi^\prime(\xi_{k+1})$

条件

$|\phi^\prime(x)| \le L <1$

迭代公式

$s\approx x_k -\frac{(x_{k+1}-x_k)^2}{x_{k+2}-2x_{k+1}+x_k}$

评估

至少是二阶收敛的，但是若简单迭代法已经有$p(p\ge2)$阶收敛速度，使用此迭代法提高收敛速度作用不大

• 定理4.5 此方法至少是二阶收敛

  有点麻烦，这个证不动。。

4.1.5 Newton 迭代法

基本思想

牛顿下山法，若基本牛顿法迭代后的点不能使得|f|更小，在二者之间找到更好的点

原理

Taylor公式，非线性方程线性化

条件

1. 初等牛顿法：

   1. 二阶导数连续，一阶导数不为零，在区间内局部收敛，则收敛于s,(p=2)

      • 定理4.6， 满足定理4.2
      • 一阶导数小于一，0的邻域
      • 证明：
        • Taylor公式，二阶导数，代入即证平方收敛

   2. 区间[a, b]存在二阶导数连续，则产生的序列单调收敛于唯一 的根，且平方收敛

      • 定理4.7

        $当x\in[a,b]时，f^\prime(x)\not=0  \qquad x_0 \in [a,b],f(x_0)f^{\prime\prime}(x_0)>0$

2. 牛顿下山法

   相比于牛顿法增加迭代过程具有单调性$|f(x_{k+1})|<|f(x_k)|$

   有下山因子：$0<\epsilon_\lambda\le\lambda\le1$

   • 从$\lambda=1逐渐减半，直至满足单调性$
   • 作为前奏选取牛顿法的初始值

迭代公式

初等牛顿法：$x_{k+1}=x_k-\frac{f(x_k)}{f^\prime(x_k)}$

简化牛顿法：$x_{k+1}=x_k-\frac{f(x_k)}{f^\prime(x_0)}$

牛顿下山法：$x_{k+1}=x_k-\lambda \frac{f(x_k)}{f^\prime(x_0)}$

割线法：$x_{k+1}=x_k -\frac{f(x_k)(x_k-x_{k-1})}{f(x_k)-f(x_{k-1)}}$

评估

初等牛顿法：收敛快，稳定性好，精度高，

但是计算量大，初始值选取要求高

简化牛顿法：计算量小，只有线性收敛，$p=1$

牛顿下山法：当$\lambda \not=1$时只有线性收敛，但对初值的选取较宽，作为前奏使用

割线法：简化计算量,收敛速度，：$p=1.618$

4.1.5.2 求解方程m重根的Newton迭代法

基本思想

改进2：$f(x) = (x-x^*)^mg(x)$,使用特殊函数转化为单根

条件

多重根, $m\ge2$

迭代公式

改进1：$x_{k+1}=x_k-\frac{mf(x_k)}{f^\prime(x_k)}$

改进2：$x_{k+1}=x_k-\frac{f(x_k)f^\prime(x_k)}{f^\prime(x_k)^2-f(x_k)f^{\prime\prime}(x_k) }$

评估

改进一：m的位置，求重数：$m = \frac 1{1-\lambda_k}$

(不证明)

改进

改进一：

二阶收敛

改进二：

有函数$u(x) =\frac{f(x)}{f^\prime(x)}$,去掉重根，经过代换m重根变为单根

4.1.5.3 割线法

基本思想

条件

• 收敛速度证明：TODO
• 单点割线法：
  • $f(a)f(b)<0, \qquad f^{\prime\prime}(x)在区间[a,b]上不变号$
  • $当x\in[a,b]时，f^\prime(x)\not=0  \qquad x_0 ,x_1\in [a,b],f(x_0)f^{\prime\prime}(x_0)>0,f(x_0)f(x_1)<0$

迭代公式

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

改进

单点割线法：简化计算，速度进一步减慢

非线性方程组的迭代解法

• 相对着重于定理的迁移，大致如下
  • 向量序列收敛的定义：范数收敛
  • 全微分所得Jacobi矩阵

其余除了离散$newton$迭代法基本类似，不过条件从1维拓展到了多维，而离散牛顿迭代主要在插值中讨论

需要着重强调的是，对于非线性方程组$x=G(x)$的迭代法的收敛性：

其谱半径$\rho(G^\prime(x^*))<1$仅仅是迭代法收敛的充分条件

书籍参考自数值分析 颜庆津