数值分析讲义（五）：非线性方程组
建议先阅读 数值分析讲义（四）：线性方程组/矩阵运算数值求解 Part II。本篇整理非线性方程组的基本问题、Newton 方法的局部收敛性及其全局化策略。
5.1 引言
本章讨论求解非线性方程组的方法。
非线性方程组
要求解 $x\in D$，使
成立，其中给定一个映射
\[F= \begin{pmatrix} F_1\\ \vdots\\ F_n \end{pmatrix} :D\to\mathbb{R}^n, \qquad D\subseteq\mathbb{R}^n\]$D$ 是非空闭集。
许多具有实际意义的问题，尤其是在技术领域，都具有非线性特征，需要求解非线性方程组。例如，电路仿真以及非线性偏微分方程的离散化，会在天气和气候模型、结构力学计算、生产技术中的成形过程等问题中产生大型非线性方程组。
线性方程组的解集只可能是唯一解、无解，或者整个仿射子空间。与此不同，非线性方程也可能有多个孤立解，甚至有无穷多个孤立解。
例 5.1.1
- $n=1$，$D=\mathbb{R}$，$F(x)=x^2-a$，$a>0$。
存在两个实数解
-
$n=1$，$D=\mathbb{R}$，$F(x)=x^2+a$，$a>0$。
不存在实数解。 -
$n=1$，$D=\mathbb{R}$，$F(x)=x\sin(x)$。
存在无穷多个解
- 单位圆与直线 $G:x_2=ax_1+b$ 的交点，其中 $a,b\in\mathbb{R}$：
$n=2$，$D=\mathbb{R}^2$，
解的个数由 $a,b$ 的取值决定，可能有两个、一个或没有实数解。
在许多应用中，函数 $F$ 是连续可微的，即其偏导数
\[\frac{\partial F_i}{\partial x_j}, \qquad 1\le i,j\le n\]存在且连续。在这种情况下，一阶泰勒展开给出
\[F(x+s)=F(x)+F'(x)s+R(x;s),\]其中雅可比矩阵为
\[F'(x)= \begin{pmatrix} \frac{\partial F_1}{\partial x_1}(x)&\cdots&\frac{\partial F_1}{\partial x_n}(x)\\ \vdots&\ddots&\vdots\\ \frac{\partial F_n}{\partial x_1}(x)&\cdots&\frac{\partial F_n}{\partial x_n}(x) \end{pmatrix},\]余项为 $R(x;s)$，并且
\[\lim_{s\to 0}\frac{\|R(x;s)\|}{\|s\|}=0, \qquad \text{简写为 } R(x;s)=o(\|s\|).\]这为构造快速求解方法提供了基础。
5.2 Newton 方法
Newton 方法是求解非线性方程组的重要方法之一，因为它在解附近通常收敛很快。为便于说明，下面假设 $D=\mathbb{R}^n$。
考虑用 Newton 方法求解方程组
\[F(x)=0 \tag{5.1}\]其中 $F:\mathbb{R}^n\to\mathbb{R}^n$ 连续可微。
5.2.1 方法推导
一维情形下的直观推导
先设 $n=1$。此时 $F(x):\mathbb{R}\to\mathbb{R}$ 是实函数。设 $x^{(k)}$ 是方程 (5.1) 的某个解 $\overline x$ 的近似值。Newton 方法的思想是：在 $x^{(k)}$ 处用函数图像 $(x,F(x))$ 的切线近似 $F$，并将切线与 $x$ 轴的交点作为下一次迭代点 $x^{(k+1)}$。
切线方程为
\[y=F(x^{(k)})+F'(x^{(k)})(x-x^{(k)}),\]$x^{(k+1)}$ 是下式
\[F(x^{(k)})+F'(x^{(k)})(x-x^{(k)})=0\]的解。若 $F’(x^{(k)})\ne 0$，则
\[x^{(k+1)} =x^{(k)}-F'(x^{(k)})^{-1}F(x^{(k)}).\]因此
\[x^{(k+1)}=x^{(k)}+s^{(k)},\]其中 $s^{(k)}$ 通过求解下列方程得到：
\[F'(x^{(k)})s^{(k)}=-F(x^{(k)}).\]例 5.2.1
对于 $F(x)=x^2-a$，$a>0$，有
一般情形
在一般情形下，设 $x^{(k)}\in\mathbb{R}^n$ 为当前迭代点。则 $\overline x$ 是方程 (5.1) 的解，当且仅当 $\overline x=x^{(k)}+s$，其中 $s$ 满足方程
\[F(x^{(k)}+s)=0. \tag{5.2}\]Newton 方法用一阶泰勒展开近似 $F(x^{(k)}+s)$，即
\[F(x^{(k)}+s) =F(x^{(k)})+F'(x^{(k)})s+o(\|s\|),\]其中 $F’(x^{(k)})$ 是 $F$ 在 $x^{(k)}$ 处的雅可比矩阵；当 $s$ 较小时，余项也较小。
因此，在第 $k$ 次 Newton 迭代中，用下面的线性化方程代替 (5.2)：
\[F(x^{(k)})+F'(x^{(k)})s=0.\]由此得到如下算法。
算法 5.2.2：方程组的局部 Newton 方法
选择初始点 $x^{(0)}\in\mathbb{R}^n$。
对 $k=0,1,\ldots$：
- 若 $F(x^{(k)})=0$：停止，结果为 $x^{(k)}$。
- 求解 Newton 方程，得到 Newton 步 $s^{(k)}\in\mathbb{R}^n$：
- 令
示意取 $F(x)=x^2-2$。每次在当前迭代点作切线，并把切线与 $x$ 轴的交点作为下一次迭代；初始点足够接近根时，迭代点会很快靠近 $\overline x=\sqrt{2}$。
5.2.2 Newton 方法的超线性和二次局部收敛
在适当条件下，可以证明 Newton 方法具有很快的局部收敛速度。
为简化记号，下面始终使用欧几里得范数 $|\cdot|_2$ 及其诱导的矩阵范数；当然，也可以使用其他范数。
下面的定理给出 Newton 方法的超线性和二次局部收敛性。
定理 5.2.3（Newton 方法的快速局部收敛）
设 $F:\mathbb{R}^n\to\mathbb{R}^n$ 连续可微，$\overline x\in\mathbb{R}^n$ 满足
且 $F’(\overline x)$ 非奇异。则存在 $\delta>0$，使得：
i) 在半径为 $\delta$ 的球
\[B_\delta(\overline x) := \{x\in\mathbb{R}^n:\|x-\overline x\|_2<\delta\}\]中，$\overline x$ 是 $F$ 的唯一零点。
ii) 对所有 $x^{(0)}\in B_\delta(\overline x)$，算法 5.2.2 要么在某一步达到 $x^{(k)}=\overline x$ 并终止，要么生成一个序列，满足
\[(x^{(k)})\subset B_\delta(\overline x),\]该序列超线性收敛到 $\overline x$，即
\[\lim_{k\to\infty}x^{(k)}=\overline x,\]并且
\[\|x^{(k+1)}-\overline x\|_2 \le \nu_k\|x^{(k)}-\overline x\|_2\]其中 $\nu_k\downarrow 0$，即该收敛因子趋于零。
iii) 若 $F’$ 在 $B_\delta(\overline x)$ 上满足 Lipschitz 条件，且 $L$ 为 Lipschitz 常数，即
\[\|F'(x)-F'(y)\|_2 \le L\|x-y\|_2 \qquad \forall x,y\in B_\delta(\overline x),\]则 $(x^{(k)})$ 甚至以二次速度收敛到 $\overline x$，即
\[\lim_{k\to\infty}x^{(k)}=\overline x,\]并且
\[\|x^{(k+1)}-\overline x\|_2 \le C\|x^{(k)}-\overline x\|_2^2,\]其中，当 $\delta>0$ 足够小时，可以选取
\[C=L\cdot\|F'(\overline x)^{-1}\|_2.\]提示：若 $F$ 在闭球 $B_\delta(\overline x)$ 上具有连续的二阶导数，则 $F’$ 自动满足 Lipschitz 条件。
不过，算法 5.2.2 中的 Newton 方法通常只从足够接近某个解 $\overline x$ 的初始点出发时才会收敛。
例 5.2.4
考虑
函数 $F$ 只有一个零点 $\overline x=0$，且连续可微，并满足 $F’(x)>0$。尽管如此，当 $\lvert x^{(0)}\rvert>1$ 时，从任意这样的初始点出发，Newton 方法都不会收敛（见习题）。
为了使 Newton 方法从任意初始点出发都能收敛，需要对它进行适当的全局化处理。
5.2.3 Newton 方法的全局化
本节介绍 Newton 方法的一种改进。对于一大类函数 $F$，这种改进能够保证从任意初始点出发的全局收敛。
这一方法基于如下观察：方程 (5.1) 的每个解 $\overline x$ 都是最小化问题
\[\min_{x\in\mathbb{R}^n}\|F(x)\|_2^2\]的全局极小点。
具体采用如下策略：
- 使用 Newton 步 $s^{(k)}$，但配合步长 $\sigma_k\in(0,1]$，将新迭代点取为
- 选择步长 $\sigma_k$，使
成立，而且下降幅度足够大。
对函数
\[\phi(\sigma) := \|F(x^{(k)}+\sigma s^{(k)})\|_2^2\]全局化策略沿离散候选步长 $1,1/2,1/4,\ldots$ 回溯，选取满足 Armijo 条件的最大步长。图中完整步长 $\sigma=1$ 使残差平方增大，因此改用 $\sigma=1/2$。
在 $\sigma=0$ 处作泰勒展开，得到
\[\phi(\sigma) =\phi(0)+\phi'(0)\sigma+o(\sigma) = \|F(x^{(k)})\|_2^2 +2\sigma F(x^{(k)})^T F'(x^{(k)})s^{(k)} +o(\sigma).\]代入 Newton 方程
\[F'(x^{(k)})s^{(k)}=-F(x^{(k)})\]代入上式可得
\[\|F(x^{(k)}+\sigma s^{(k)})\|_2^2 = \|F(x^{(k)})\|_2^2 -2\sigma\|F(x^{(k)})\|_2^2 +o(\sigma).\]固定 $\delta\in(0,1)$。当 $F(x^{(k)})\ne 0$ 且 $\sigma$ 足够小时，有
\[\|F(x^{(k)}+\sigma s^{(k)})\|_2^2 \le \|F(x^{(k)})\|_2^2 -2\delta\sigma\|F(x^{(k)})\|_2^2.\]这说明可以采用下面的 Armijo 步长规则。
Armijo 步长选择
取定
（例如取 $\delta=10^{-3}$ 通常效果较好）。从下列集合中选取满足条件的最大步长
\[\sigma_k\in\left\{1,\frac12,\frac14,\ldots\right\}\]使
\[\|F(x^{(k)}+\sigma_k s^{(k)})\|_2^2 \le \|F(x^{(k)})\|_2^2 -2\delta\sigma_k\|F(x^{(k)})\|_2^2. \tag{5.4}\]由此得到如下算法。
算法 5.2.5：方程组的全局化 Newton 方法
选择初始点 $x^{(0)}\in\mathbb{R}^n$。
对 $k=0,1,\ldots$：
- 若 $F(x^{(k)})=0$：停止，结果为 $x^{(k)}$。
- 求解 Newton 方程，得到 Newton 步 $s^{(k)}\in\mathbb{R}^n$：
- 按 Armijo 规则 (5.4) 确定 $\sigma_k$。
- 令
相应的收敛性由下面的定理保证。
定理 5.2.6
设 $F:\mathbb{R}^n\to\mathbb{R}^n$ 连续可微，并取任意初始点 $x^{(0)}\in\mathbb{R}^n$。记
并定义水平集
\[N_f(x^{(0)}) := \{\,y:f(y)\le f(x^{(0)})\,\},\]若对该水平集中的每个点 $x$，雅可比矩阵 $F’(x)$ 都可逆，且 $N_f(x^{(0)})$ 是紧集（在 $\mathbb{R}^n$ 中等价于有界且闭），则从 $x^{(0)}$ 出发运行算法 5.2.5 时，要么在有限步内终止，要么生成序列
\[(x^{(k)})\subset N_f(x^{(0)}),\]并满足：
i) $(x^{(k)})$ 收敛到方程 (5.1) 的某个解 $\overline x$。
ii) 存在 $l\ge 0$，使得当 $k\ge l$ 时都有 $\sigma_k=1$。因此，算法最终会恢复为每一步都取完整 Newton 步的局部方法，并以超线性或二次速度收敛到 $\overline x$。
返回阅读 数值分析讲义（四）：线性方程组/矩阵运算数值求解 Part II。
来源、版权与使用说明
本文整理自本地保存的 TU Darmstadt 2016 年 Mathematik 4 ET/3Inf 讲义文件 Skript-Mathe4ET-3Inf-2016-Kap4-5.pdf 中的第 4 章，并参考同目录下的中文翻译草稿 Skript-Mathe4ET-3Inf-2016-Kap4.zh.md。正文为个人学习、翻译与知识整理用途发布，文中的中文表述、补充说明和重新制作的图表不代表原作者或官方立场。
本文中的个人整理、中文表述、补充解释以及我重新制作的图表，可在注明作者与原始材料来源的前提下，用于非商业学习、交流和引用。由于本文部分内容基于课程讲义的翻译与整理，原始讲义及其中可能包含的材料仍应以其原作者、课程页面及相关授权说明为准。若需进行商业使用、系统转载、出版，或大规模改编，建议先确认原始材料的授权状态。
如文中存在翻译、公式、术语或理解上的疏漏，或相关权利方认为内容使用不当，欢迎联系指出，我会及时处理或删除。
AI feedback
AnonymousLoading AI feedback…