非线性方程组的数值解

type

status

date

slug

summary

二分查找法

对于方程，其奇数重根有如下的性质：存在的某个邻域，使得邻域内分别在零点左和右的两点有，所以只需保证，每次将或替换为，直到误差达到要求即可。

二分查找法一定收敛，但收敛速度较慢。但二分查找法较为依赖初始值的选取，且无法处理偶数重根。

迭代法

不动点迭代

如果一函数满足在处，那么就可以尝试使用迭代格式

来找到这个。但这个迭代格式在某区间上不一定能够收敛，于是寻找使它收敛的条件：

首先，在这个区间内方程应有根，即满足：

据此可得出两种互斥情况：

其次，无论，这一迭代法每迭代一次所产生的误差应小于上一次产生的误差，即：

或称：

重写为：

据此可得出，与上述情况2矛盾.

因此可以得到数值分析版本的压缩映像原理(在泛函分析中这一原理有更准确和泛化的定义)：

若在区间上满足条件：

则初值在上的迭代格式收敛于

在实际中很少对于区间内每两点都找到一个来验证上述第2条条件，故压缩映像原理有另一种提法，即对于第2条条件，令，则：

若在区间上满足条件：

则初值在上的迭代格式收敛于

然而我们还是觉得麻烦，验证在区间上处处导数小于1还算是麻烦，故我们又对它换了一种提法：

若在的某一邻域内连续可导(注意：连续可导指的是"连续地可导"，指导函数连续，而不是"函数连续且函数可导")，而，若，则一定存在某个的邻域，使得收敛于.

迭代的收敛速度

假使一迭代序列收敛于，且有如下关系：

则称迭代序列 是 阶收敛的。这一阶数刻画了在附近估计误差缩小的速度，故可以刻画序列收敛于的速度.但形式看上去就不方便使用，实际工程中更是难以凭借它来估算收敛速度，而这个次方给我们一种提示：是否可以使用级数展开方法，使得这个与导数联系起来？

我们对满足的在处执行Taylor展开并代入：

即：

而基线性无关，因此可以得出：

因此可以使用上式来计算收敛阶数：第一个在解处非零的导数是几阶，收敛阶数就是几阶.

函数值迭代

简单迭代法

故基于压缩映像原理之扩展，我们可以将方程经过同解转化，化为能够收敛的的形式来迭代求解. 这种转化不仅仅是两边同时加一个，可能还需要基于其导函数对其调整，使其根周围的导数小于1，故在此之前，可以先使用二分查找法缩小根的范围.

简单迭代法收敛较慢，且大部分情况下是一阶收敛(线性收敛)，不能满意.

Steffensen加速

在充分大时，有关系：

解出

令，即

即得Steffensen加速法原理. 它至少是2阶收敛的.

在Steffensen加速的运算过程中，我们首先使用一般迭代法求出，后直接持续使用式子直到进入误差允许范围.

插值迭代

插值迭代的主要思想是用线性方程或简单的多项式方程近似非线性方程，逐步逼近其解.

Newton迭代法

Newton迭代法使用在处的切线与轴的交点作 . 即：

Newton法同样满足

收敛速度：易求得，故Newton法至少2阶收敛.

但Newton法对重根是线性收敛的，因此有如下改进手段：

，为根的重数

使用同解方程的根代替的根

弦截法

弦截法基于Newton法，使用差商来代替导数：

它需要两个初值，一般取确定有解区间的两端点

muller法(抛物线法)

抛物线法是三点的弦截法. 使用过三点的抛物线的，在方向上的零点作

对于非线性方程组：

有两种解法：其一是将其在某一点线性展开为超平面，以这个切平面来近似这个方程；其二是将其转化为同解的、具有最小值0的非线性函数，再通过梯度下降求出其最值.

Newton-Raphson法，线性化求解

不难得出，对于，以其在点处的切平面代替之可有：

为了方便求解，将所有的方程都在同一点处展开，故可以使用方程组：

来代替上述的方程组，用矩阵的形式表示则为：

第一项偏导数矩阵为Jacobi矩阵

将上述式子变形：

简记为，则可以直接构建迭代格式

梯度下降法求解

易知，上述的非线性方程组与方程：同解(平方和为零当且仅当各项均为零)

可以设置损失函数，对其执行梯度下降算法求出解.