高级数值分析 第 6 章 非线性方程组迭代法

本文由手写笔记《高级数值分析》扫描件的 LaTeX 转录稿改写而来，忠实保留原稿的文字与公式。 定理与定义的编号是本站为方便指代所加，原稿只有名称、没有编号。

6.1 引言

设要求解非线性方程组

$$F(x)=0,\qquad F:\mathbb R^n\to\mathbb R^n.$$

非线性迭代法通常构造成不动点格式

$$x^{(k+1)}=\varphi\bigl(x^{(k)}\bigr),$$

其中解 $x^*$ 满足 $x^*=\varphi(x^*)$。更一般地，$p$ 步迭代可写为

$$x^{(k)}=\varphi_k\bigl(x^{(k-p)},x^{(k-p+1)},\ldots,x^{(k-1)}\bigr), \qquad k\ge p.$$

将其化为一阶迭代时，令

$$y^{(k)}= \begin{bmatrix} x^{(k)}\\x^{(k+1)}\\\vdots\\x^{(k+p-1)} \end{bmatrix},$$

即可把 $p$ 步格式视作扩展空间中的不动点迭代。

定义 6.1（收敛与收敛阶）

若 $x^{(k)}\to x^*$，则称迭代序列收敛到 $x^*$。若存在常数 $C>0$、整数 $k_0$ 及 $p\ge1$，使得对一切 $k\ge k_0$ 有

$$\left\lVert x^{(k+1)}-x^*\right\rVert\le C\left\lVert x^{(k)}-x^*\right\rVert^{p},$$

则称该迭代为 $Q$-阶至少为 $p$ 的收敛。当 $p=1$ 且可取 $0<C<1$ 时，称为 $Q$-线性收敛；当 $p>1$ 时，称为超线性收敛。

定义 6.2（$R$-线性收敛）

若存在 $C>0$、$0<q<1$ 及 $k_0$，使得

$$\left\lVert x^{(k)}-x^*\right\rVert\le Cq^k,\qquad k\ge k_0,$$

则称 $x^{(k)}$ $R$-线性收敛到 $x^*$。$Q$-线性收敛必蕴含 $R$-线性收敛。

6.2 一元非线性方程

考虑方程

$$f(x)=0.$$

6.2.1 二分法

设 $f\in C[a_0,b_0]$，并且

$$f(a_0)f(b_0)<0.$$

由介值定理，区间 $(a_0,b_0)$ 内至少存在一个零点 $x^*$。取中点

$$x_k=\frac{a_k+b_k}{2}.$$

若 $f(a_k)f(x_k)<0$，令 $a_{k+1}=a_k$、$b_{k+1}=x_k$；否则令 $a_{k+1}=x_k$、$b_{k+1}=b_k$。由此得到嵌套区间

$$[a_0,b_0]\supset[a_1,b_1]\supset\cdots, \qquad b_k-a_k=2^{-k}(b_0-a_0).$$

当 $b_k-a_k<\varepsilon$ 时停止。若零点唯一，则 $x_k\to x^*$，并且

$$|x_k-x^*|\le\frac{b_k-a_k}{2} =\frac{b_0-a_0}{2^{k+1}}.$$

二分法收敛可靠且不需要导数信息，但收敛速度较慢。

6.2.2 不动点迭代

将 $f(x)=0$ 等价地改写为

$$x=\varphi(x),$$

并取迭代

$$x_{k+1}=\varphi(x_k).$$

定理 6.1（压缩映射原理）

设 $\varphi\in C[a,b]$，$\varphi([a,b])\subseteq[a,b]$，且存在 $0\le L<1$，使得

$$|\varphi'(x)|\le L,\qquad x\in[a,b].$$

则方程 $x=\varphi(x)$ 在 $[a,b]$ 内有唯一解 $x^*$。任取 $x_0\in[a,b]$，迭代 $x_{k+1}=\varphi(x_k)$ 均收敛到 $x^*$，且

$$|x_k-x^*|\le\frac{L^k}{1-L}|x_1-x_0|.$$

定理 6.2（局部收敛判别）

设 $\varphi\in C^1$，且 $x^*=\varphi(x^*)$。

1. 若 $|\varphi'(x^*)|<1$，则存在 $x^*$ 的一个邻域，使其中任意初值产生的迭代均收敛到 $x^*$；
2. 若 $|\varphi'(x^*)|>1$，则 $x^*$ 为不稳定不动点：充分接近但不等于 $x^*$ 的初值一般不会收敛到 $x^*$。

并且在 $x_k\to x^*$、$x_k\ne x^*$ 时，

$$\lim_{k\to\infty}\frac{x_{k+1}-x^*}{x_k-x^*}=\varphi'(x^*).$$

定理 6.3（不动点迭代的高阶收敛）

设 $\varphi\in C^p$，$x^*=\varphi(x^*)$，并且

$$\varphi'(x^*)=\cdots=\varphi^{(p-1)}(x^*)=0, \qquad \varphi^{(p)}(x^*)\ne0.$$

则当初值充分接近 $x^*$ 时，迭代至少 $Q$-阶 $p$ 收敛，且

$$\lim_{k\to\infty} \frac{x_{k+1}-x^*}{(x_k-x^*)^p} =\frac{\varphi^{(p)}(x^*)}{p!}.$$

6.2.3 Newton 法

在 $x_k$ 处以 $f$ 的切线近似 $f$：

$$L_k(x)=f(x_k)+f'(x_k)(x-x_k).$$

令 $L_k(x_{k+1})=0$，得到 Newton 迭代

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

定理 6.4（Newton 法的局部收敛性）

设 $f\in C^2$，$f(x^*)=0$ 且 $f'(x^*)\ne0$。当 $x_0$ 充分接近 $x^*$ 时，Newton 迭代收敛到 $x^*$，且为二阶收敛：

$$\lim_{k\to\infty} \frac{x_{k+1}-x^*}{(x_k-x^*)^2} =\frac{f''(x^*)}{2f'(x^*)}.$$

若 $x^*$ 是 $f$ 的 $m$ 重根，即

$$f(x^*)=f'(x^*)=\cdots=f^{(m-1)}(x^*)=0, \qquad f^{(m)}(x^*)\ne0,$$

则通常 Newton 法仅线性收敛，并有

$$\lim_{k\to\infty}\frac{x_{k+1}-x^*}{x_k-x^*}=\frac{m-1}{m}.$$

为避免每步求导，可用相邻两点的差商替代导数，得到割线法：

$$x_{k+1}=x_k- \left[\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}\right]^{-1}f(x_k).$$

割线法的收敛阶为

$$p=\frac{1+\sqrt5}{2}.$$

若以每步所需函数计算次数衡量效率，则割线法的效率指标

$$E_S=\ln\frac{1+\sqrt5}{2}$$

高于 Newton 法的指标 $E_N=\ln\sqrt2$。

6.3 非线性方程组

现讨论非线性方程组

$$F(x)=0,\qquad F=(f_1,\ldots,f_n)^T:\mathbb R^n\to\mathbb R^n.$$

以下设 $D\subset\mathbb R^n$ 为定义域，$x^*\in D$ 是方程组的解。

6.3.1 局部收敛性

若迭代写为

$$x^{(k+1)}=\varphi\bigl(x^{(k)}\bigr),$$

则 $x^*$ 是不动点，即 $\varphi(x^*)=x^*$。

定理 6.5（方程组不动点迭代的局部收敛性）

设 $\varphi$ 在 $x^*$ 的某邻域内连续可微，且

$$\varphi(x^*)=x^*,\qquad \rho\bigl(\varphi'(x^*)\bigr)<1,$$

其中 $\rho(\cdot)$ 表示谱半径。则存在 $x^*$ 的一个邻域 $B(x^*,\delta)\subset D$，使得任取 $x^{(0)}\in B(x^*,\delta)$，迭代序列均收敛到 $x^*$。

6.3.2 Newton 法

在 $x^{(k)}$ 处对 $F$ 作一阶线性化。记 $J_F(x)=F'(x)$ 为 Jacobi 矩阵，则 Newton 步为

$$x^{(k+1)}=x^{(k)}-\bigl[F'(x^{(k)})\bigr]^{-1}F(x^{(k)}).$$

实际计算时通常不显式求逆，而是先解线性方程组

$$F'(x^{(k)})s^{(k)}=-F(x^{(k)}),$$

再令

$$x^{(k+1)}=x^{(k)}+s^{(k)}.$$

定理 6.6（Newton 法的局部收敛性）

设 $F$ 在 $x^*$ 的某邻域内连续可微，$F(x^*)=0$ 且 $F'(x^*)$ 非奇异。则当初值 $x^{(0)}$ 充分接近 $x^*$ 时，Newton 迭代收敛到 $x^*$。若 $F'$ 在该邻域内 Lipschitz 连续，即存在常数 $L>0$ 使

$$\left\lVert F'(x)-F'(y)\right\rVert\le L\left\lVert x-y\right\rVert,$$

则 Newton 法二次收敛。

6.3.3 割线法

为避免在每一步重新计算 Jacobi 矩阵，可用线性函数

$$L(x)=Ax+b$$

插值 $F$。若给定 $n+1$ 个点 $x^{(0)},\ldots,x^{(n)}$，并满足

$$L\bigl(x^{(i)}\bigr)=F\bigl(x^{(i)}\bigr),\qquad i=0,\ldots,n,$$

且这些点仿射无关，则 $A,b$ 唯一确定。令

$$H_{k,n}= \bigl[x^{(k+1)}-x^{(k)},\ldots,x^{(k+n)}-x^{(k+n-1)}\bigr],$$ $$T_{k,n}= \bigl[F(x^{(k+1)})-F(x^{(k)}),\ldots, F(x^{(k+n)})-F(x^{(k+n-1)})\bigr].$$

当 $H_{k,n}$ 非奇异时，线性模型的系数为

$$A_{k,n}=T_{k,n}H_{k,n}^{-1}.$$

于是割线迭代可以写成

$$x^{(k+1)}=x^{(k)}-A_{k,n}^{-1}F\bigl(x^{(k)}\bigr).$$

该方法每步利用前面若干点的函数值差分近似导数信息。

6.3.4 拟 Newton 法

拟 Newton 法以矩阵 $B_k$ 近似 $F'(x^{(k)})$，取

$$x^{(k+1)}=x^{(k)}-B_k^{-1}F\bigl(x^{(k)}\bigr).$$

令

$$s_k=x^{(k+1)}-x^{(k)},\qquad y_k=F(x^{(k+1)})-F(x^{(k)}),$$

则更新矩阵应满足割线条件

$$B_{k+1}s_k=y_k.$$

Broyden 秩一更新在保持 $B_{k+1}s_k=y_k$ 的同时，使对 $B_k$ 的改动尽量小：

$$B_{k+1}=B_k+ \frac{(y_k-B_ks_k)s_k^T}{s_k^Ts_k}.$$

由更新式立刻可验证 $B_{k+1}s_k=y_k$。在实际应用中还可采用 BFGS、PSB、DFP 等更新公式；它们与割线法、Newton 法一样，均以近似 Jacobi 矩阵为核心。

6.3.5 最小二乘法

当方程组无精确解或希望以残量衡量近似程度时，可转而求解非线性最小二乘问题

$$\min_{x\in\mathbb R^n}\Phi(x), \qquad \Phi(x)=\frac12\left\lVert F(x)\right\rVert_2^2 =\frac12\sum_{i=1}^n f_i(x)^2.$$

其梯度为

$$\nabla\Phi(x)=\sum_{i=1}^n f_i(x)\nabla f_i(x) =F'(x)^TF(x).$$

因此任何满足 $F(x)=0$ 的点都是 $\Phi$ 的全局极小点，并且为驻点；反之，$\nabla\Phi(x)=0$ 是最小二乘问题的一阶必要条件。Gauss–Newton 法正是以该目标函数为基础构造的迭代方法。