1 牛顿迭代法

牛顿迭代法实质上是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方程来求解。

1.1 牛顿法

牛顿迭代法又称切线法，是一种有特色的求根方法。用牛顿迭代法求的单根的主要步骤：

（1）Newton法的迭代公式

（2）以附近的某一个值为迭代初值，代入迭代公式，反复迭代，得到序列

（3）若序列收敛，则必收敛于精确根，即。

牛顿法有显然的几何意义，方程的根可解释为曲线与轴交点的横坐标。设是根的某个近似值，过曲线上横坐标为的点引切线，并将该切线与轴交点的横坐标作为的新的近似值。

牛顿法初值的选择：若在上连续，存在2阶导数，且满足下列条件：

（1）；

（2）在内不变号，且；

（3）在内不变号，且；

（4），且 ；

则对任意的初值，牛顿迭代序列收敛于在内的唯一根。

牛顿的优缺点：牛顿法是目前求解非线性方程（组）的主要方法，至少二阶局部收敛，收敛速度较快，特别是当迭代初值充分靠近精确解时。对重根收敛速度较慢（线性收敛），对初值的选取很敏感，要求初值相当接近真解，需要求导数。

1.2 哈利牛顿法

哈利法（Halley）可用于加速牛顿法收敛，哈利迭代公式：

哈利法在单根情况下可达到三阶收敛。

1.3 简化牛顿法

将牛顿法的迭代公式改为

为保证收敛，系数只需满足即可。如果取常数，则称为简化牛顿法，也称平行弦法。

简化牛顿法线性收敛。

1.4 牛顿下山法

牛顿法的收敛性依赖初值的选取，如果偏离所求根较远，则牛顿法可能发散。牛顿下山法，引入下山因子，保证函数值稳定下降的同时，加速收敛速度。

牛顿下山法公式：

下山因子的取法：从开始，逐次减半，即，直到满足下降条件。

1.5 重根情形

当为的重根时，则可表为，其中，此时用牛顿迭代法求仍然收敛，只是收敛速度将大大减慢，牛顿法求方程的重根时仅为线性收敛。

将求重根问题化为求单根问题进行牛顿法求解。对，令函数

则化为求的单根的问题，对它用牛顿法是二阶收敛的。其迭代函数为

从而构造出迭代方法

2 牛顿迭代法MATLAB算法实现

算法说明：

（1）输入参数的判定和必要的处理，包括可变参数的处理，若某个可变参数不输入，则采用默认值。

（2）由于牛顿法需要计算方程的一阶导数和二阶导数（重根情形），故方程的定义采用符号定义（避免手工计算方程的导数所带来的计算量），在算法solve_diff_fun(equ)中实现符号函数的一阶导数和二阶导数的计算，并转换为匿名函数进行数值运算。

（3）根据参数method选择执行不同的牛顿迭代方法，具体：

    1）“newton”为牛顿法newton()；

    2）“simplify”为简化的牛顿法simplify_newton()；

    3）“halley”为哈利法（牛顿加速法）newton_halley()；

    4）“downhill”为牛顿下山法newton_downhill()，下山法包括了下山因子的存储；

    5）“multi”为重根情形newton_multi_root()。

（4）根据参数display选择是否显示迭代过程信息或仅显示结果信息。

（5）可变输出参数的判定和必要处理。

思考：MATLAB中没有类似于Python的list结构，如何在未知迭代次数的情况下，预分配内存，存储迭代过程变量信息？

3 牛顿迭代法案例测试

例1：求非线性方程在区间的近似根

可视化函数图像：

从图中可以看出，在区间内存在四个根，此处仅求在附近的根，其他根求解自行设计。

验证输入参数：

验证输出参数，仅有一个输出参数，则为结构体，且输出迭代过程：

验证输出参数，有三个输出参数，分别为近似解、方程在近似解处的误差精度和退出标记，1表示收敛到满足精度要求的近似解，且输出最终迭代结果：

例2：求带有重根的非线性方程在附近的近似解

由于简化的牛顿法收敛速度较慢，此处不再可视化简化的牛顿法。

可视化各牛顿法的误差精度下降曲线如图3，可见在存在重根情形下，采用牛顿重根公式，收敛速度极快，其次为牛顿哈利法。由于此处未用到下山因子，故牛顿法和牛顿下山法求解过程一致。

各方法迭代过程

例3：求非线性方程在附近的近似解：

其中下山法由于在第二次迭代时引入了下山因子0.25，故其下降曲线相对于牛顿法而言，保持了下降收敛的性质。