最优化基础：非线性方程求根

对分法

假设 $f$ 在有限区间 $[a,b]$ 上连续，且 $f(a)f(b)<0$ ，那么 $f$ 在 $(a,b)$ 至少有一个零点。给定位置容差 $\varepsilon>0$ ，对分法的算法流程如下：

起始的计算区间 $[x_l,x_r]=[a,b]$ ，此时满足两端异号 $f(x_l)f(x_r)<0$ 。
选取中点 $x_m = \frac12(x_l+x_r)$ ，计算 $f(x_m)$ 。
如果 $f(x_m)=0$ ，则找到零点，求解完成；否则，若区间长度 $x_r-x_l\le\varepsilon$ ，则输出中点，此时它与区间内某个零点的距离不超过 $\varepsilon/2$ 。
否则左右两个区间 $[x_l,x_m]$ ， $[x_m,x_r]$ 恰有一个满足两端异号，选取它作为新的计算区间 $[x_l',x_r']$ ，回到第二步。

收敛性分析：进行 $k$ 次对分之后，计算区间长度为 $2^{-k}(b-a)$ ，因此至多进行 $N$ 次对分。

Copy LaTeX

误差分析：记 $x^*$ 为嵌套区间保留的零点（无限对分时为区间的公共极限点），第 $k$ 次对分之后中点 $x_m^{(k)}$ 满足

Copy LaTeX

Remark

算法的前提条件保证了至少有一个零点，但如果在区间中有多个零点，则可能收敛到其中任一零点。

也可以另外设置残差容差 $\varepsilon_f$ ，在 $|f(x_m)|\le\varepsilon_f$ 时停止，但这只能直接保证残差小。若还知道区间内 $f$ 可微且 $|f'(x)|\ge\mu>0$ ，才能由中值定理得到位置误差估计 $|x_m-x^*|\le |f(x_m)|/\mu$ 。

牛顿法

假设 $f(x)$ 在 $x$ 附近有一个零点 $x^*$ ，牛顿法的流程是：从 $x^{(0)}=x$ 出发，构造迭代点列 $\{x^{(k)}\}$ ，希望极限趋于零点

Copy LaTeX

具体的构造方法为：在 $(x^{(k)},f(x^{(k)}))$ 处作 $f$ 的切线，切线与 x轴交点记作 $x^{(k+1)}$ 。

Copy LaTeX

迭代的终止条件有两个：

Copy LaTeX

Remark

牛顿法对迭代的初值很敏感，要求初值与真正的零点足够靠近（靠近程度也与 $f$ 自身性质有关）；否则可能跳转并收敛到另外的零点，或者直接不收敛。
在初值合适选取时，并且 $f \in C^2$ 在 $x^*$ 有单根时，收敛速度可以达到二阶。（如果在 $x^*$ 是重根，可能需要对格式进行修改）
$Copy LaTeX$
仅有凸性并不足以保证牛顿法从任意初值收敛，还需要控制初值、导数和迭代所在的区间。例如对 $f(x)=x^2-R$ （ $R>0$ ），任取正初值可得到收敛到 $\sqrt R$ 的经典平方根迭代。

对于二阶收敛速度的证明：假设零点非重根，记 $e^{(k)} = x^{(k)} - x^*$ ，则有

Copy LaTeX

对 $f(x^{*}) = f(x^{(k)}-e^{(k)})$ 在 $x^{(k)}$ 处进行泰勒展开

Copy LaTeX

因此有

Copy LaTeX

经典的平方根算法就是牛顿法的具体应用：计算 $f(x)=x^2-R$ 的零点

Copy LaTeX

关于非线性方程求根的牛顿法可以直接推广到非线性方程组上：求 $X\in R^n$ ，满足 $F(X) = 0 \in R^n$ 。这里为了简化问题，取约束个数和自变量维数相同，并且假设问题的解存在。最简单是线性情形 $F(X)=AX$ ， $A \in R^{n\times n}$ 是常系数方阵。迭代公式为

Copy LaTeX

其中 $J(X)$ 为 Jacobi 矩阵。

Copy LaTeX

这里要求 $F(X)$ 足够光滑，并且假设 Jacobi 矩阵始终可逆。

割线法

牛顿法需要使用导函数信息，有时对于非线性函数 $f(x)$ 直接求导很困难，可以使用最近两个点的割线斜率进行近似。

Copy LaTeX

为了启动格式，需要提供两个不同的初始值 $x_0,x_1$ ，并在各步保证分母非零（若已找到根则停止）。当 $f\in C^2$ 、 $x^*$ 为单根且初值足够接近时，割线法局部收敛；在 $f''(x^*)\neq0$ 的非退化情形下，其收敛阶为 $\frac{1+\sqrt{5}}2\approx1.62$ 。重根或不合适的初值不具有这一保证。

不动点法

对于方程 $f(x)=0$ ，总是可以转化为如下形式

Copy LaTeX

即 $f$ 的零点 $x$ 是 $F$ 的不动点，然后可以据此设计迭代格式

Copy LaTeX

基于压缩映射原理，我们希望在区间 $[a,b]$ 上的 $F$ 是压缩映射，要求 $F:[a,b]\to [a,b]$ ，并且存在 $0<L<1$ 使得

Copy LaTeX

此时才可以保证不动点迭代收敛。

不动点法提供了非常自由的构造方式：针对具体问题，设计不同的 $F$ 并检验压缩映射条件，就可以给出很多不动点迭代格式。牛顿法实质是一种不动点法：

Copy LaTeX

用 $f(x+f(x))-f(x)$ 近似 $f'(x)f(x)$ ，还可得到 Steffensen 迭代。它每一步只依赖当前点，与前面使用最近两个迭代点的割线法不同：

Copy LaTeX