用介值定理证明（非线性方程求解）

二分法

二分法的使用需要前提条件，即对形式为 f(x)=0 的非线性方程，有

f(x)∈C([a,b]),f(a)f(b)<0

这里区间 [a,b] 是方程的根的隔离区间，由微积分中的连续性定理、介值定理可以知道这个区间中必然存在零点。

二分法是方程求根问题的一种直接搜索方法，优点是算法简单直观，数值解的精度易于判别，局限性是只适用于标量方程，且需要事先确定一个方程的根的隔离区间，过大的隔离区间会导致过长的搜索时间。

弦截法

为获得比二分法更快的速度，在其基础上设计了弦截法

隔离区间中的精确解存在一个邻域，在邻域上连续二阶可微且隔离区间中的精确解存在一个邻域，f(x)在邻域上连续二阶可微且f′(x)≠0,Q=△max|f″|σmaxf′<1

之后不断地在区间中取两点并作弦线，寻找弦线与x轴的交点。

对于这个迭代逼近的过程，一般表达式为

xk+1=xk−xk−xk−1f(xk)−f(xk−1)f(xk),k=1,2,⋯

误差估计的公式太复杂。

有些教材的弦截法是放在牛顿迭代法的后面的，就算是个殊途同归吧。

Picard迭代法

在皮卡迭代法中，假设的非线性方程的形式为 x=ϕ(x) ，那么迭代的轨迹就是不断地在 y=ϕ(x) 和 y=x 之间折返。 其纵坐标就不过是交线，而横坐标由 x+k+1=ϕ(xk) 决定。

皮卡迭代法依赖初始点的选取，选取得不合适很可能造成迭代过程发散。皮卡迭代法的收敛性准则要求迭代函数 ϕ(x) 满足

存在有a<=ϕ(x)<=b存在q<1,有|ϕ′(x)|<=q<1

且误差估计为

|x∗−xk|<=q1−q|xk−xk−1|

Aitken迭代法

非线性方程在求解基本都是躲避不开迭代法（ xk 和 xk+1 的递进关系式）的，理论上 只要迭代的次数足够多，就可以得到任意精度的结果，但是收敛的过程往往缓慢，从而使得计算量巨大， 因此提出了很多加速迭代的方法。

对于精确解 x∗ 的某一个近似值 x0 ，使用迭代公式迭代一次后可以得到

x1=ϕ(x0)

那么由微分中值定理，此时这一步的误差为

x1−x∗=ϕ(x0)−ϕ(x∗)=ϕ′(ξ)(x0−x∗)

其中 ξ 为介于 x∗ 和 x0 的某一个值。

现在假设上式的的改变不大，近似地取近似值L，有

x1−x∗≈L(x0−x∗)

对校正值 x1=ϕ(x0) 再一次校正，向前走一步迭代有 x2=ϕ(x1) ，且

x2−x∗=L(x1−x∗)

联立上一个行间式，有

x1−x∗x2−x∗≈x0−x∗x1−x∗

进而经简化推知

x∗≈x0−(x1−x0)2x2−2x1+x0

这里综合了和，用以来表示方程的精确解，由此来看，这里是在用计算和。略作推广就可以得到递进的关系式

xk+1=xk−(xk+1−xk)2xk+2−2xk+1+xk=xk−(Δxk)2Δ2xk,(k=0,1,⋯)

这就是Aitken加速方法。

可以证明

limk→∞xk+1−x∗xk−x∗=0

也就是说明了这个算法的收敛速度比原本的迭代公式更快。

若原迭代公式为线性收敛，那么阿特金迭代法为平方收敛；若原迭代公式为p阶收敛，且为p阶连续 可导，那么阿特金法是2p-1阶收敛。

Steffensen迭代法

将阿特金迭代法和不定点迭代法结合在一起就可以得到一个新的迭代法

yk=ϕ(xk),zk=ϕ(yk)xk+1=xk−(yk−xk)2zk−2yk+xk,(k=0,1,⋯)

这个新的迭代方法被称为是史蒂芬孙迭代法。

这个方法相当于在原本的迭代序列基础上计算每一步的误差 并构成了新的序列，对误差列外推到0，即过点 (xk,ϵ(xk)) 和 (yk,ϵ(yk)) 作线性插值 函数，这个曲线与x轴的交点就是 xk+1 ，也就是方程

ϵ(xk)+ϵ(yk)−ϵ(xk)yk−xk(x−xk)=0

的解 x=xk−(yk−xk)2zk−2yk+xk=xk+1 。

史蒂芬孙迭代是2阶收敛的。

牛顿迭代法

牛顿迭代法的思想非常精彩（而且我自己也成功地独立设计出来了这个算法），它是对一个连续函数曲线作线性化的处理，再不断地迭代修正。 对于非线性方程 f(x)=0 ，取一点 xk 作为精确解 x∗ 的近似值，在这一点上进行泰勒展开有

f(x)≈f(xk)+f′(xk)(x−xk)

按理说 f′(xk) 一般不为零，于是就可以用切线不断地逼近方程的解，这样就可以得到牛顿迭代法的迭代公式

xk+1=xk−f(xk)f′(xk),(k=0,1,⋯)

分析牛顿迭代法的收敛性，当方程只有单根时，其在邻近区间是平方收敛的。

简化牛顿法和牛顿下山法

牛顿迭代法的缺点在于计算量大，且不一定很容易就能计算出一阶导数，此外其收敛性也很 依赖选取的初始点，所以给出了基于牛顿法的扩展方法。

简化牛顿法也称为平行弦法，迭代公式为 xk+1=xk−Cf(xk),C≠0

迭代函数为 ϕ(x)=x−Cf(x) 。

平行弦法的意义在于计算量省，但是只能线性收敛。

牛顿下山法的意义在于避免因初始值选取不当造成的结果发散

为了避免这类情况的发生从而 对迭代过程加上一个要求

|f(xk+1)|<|f(xk)|

也就是一个单调性的要求。只要满足了这个要求，就称算法为下山法。

在实际计算时，将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用 牛顿法加快收敛速度. 。为此，将牛顿法的结果与前一项的近似值进行适当地加权平均作为新的改进值

xk+1=λxk+10+(1−λ)xk

其中称 λ 为下山因子，即有

xk+1=xk−λf(xk)f′(xk),(k=0,1,⋯)

就是牛顿下山法。

在选择下山因子时，从1开始，逐次减半进行试算，直到使得单调下降条件成立。

抛物线法

抛物线法和之前迭代法的思想是一样的，都是用某种曲线（或者直线）去拟合，并寻找交点作为近似解。在这里使用的拟合得到的结果就是一个抛物线。

抛物线法首先需要非线性方程的三个近似根，以此构造二次插值多项式。

抛物线法是超线性收敛。