19.2.2 非线性方程组

若含有 $n$ 个未知量 $x_1,x_2,\cdots ,x_n$ 的 $n$ 个方程的非线性方程组

$$\begin{array}{}\text{(19.55)}& F_i\left(x_1,x_2,\cdots ,x_n\right)=0\left(i=1,2,\cdots ,n\right)\end{array}$$

有解, 通常数值解仅可由迭代法得到.

19.2.2.1 一般迭代法

若方程 (19.55) 可以转化为不动点形式

$$\begin{array}{}\text{(19.56)}& x_i=f_i\left(x_1,x_2,\cdots ,x_n\right)\left(i=1,2,\cdots ,n\right),\end{array}$$

则可用一般迭代法. 从估计的近似值 $x_1^{\left(0\right)},x_2^{\left(0\right)},\cdots ,x_n^{\left(0\right)}$ 出发,通过下面的方法得到改进值.

1. 同步迭代

$$\begin{array}{}\text{(19.57)}& x_i^{(\mu +1)}=f_i\left(x_1^{\left(\mu \right)},x_2^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)\left(i=1,2,\cdots ,n;\mu =0,1,2,\cdots \right).\end{array}$$

2. 顺序迭代

$$x_i^{(\mu +1)}=f_i\left(x_1^{(\mu +1)},\cdots ,x_{i-1}^{(\mu +1)},x_i^{\left(\mu \right)},x_{i+1}^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)$$$$\begin{array}{}\text{(19.58)}& \left(i=1,2,\cdots ,n;\mu =0,1,2,\cdots \right).\end{array}$$

对该方法收敛性特别重要的是,在解的邻域函数 $f_i$ 应该较弱地依赖于未知量, 即如果函数 $f_i$ 可微,其偏导数的绝对值必须相当小. 我们得到收敛性条件

$$K<1$$

其中

$$\begin{array}{}\text{(19.59)}& K=\underset{i}{max}\left(\sum _{k=1}^{n}max\left|\frac{\partial f_i}{\partial x_k}\right|\right).\end{array}$$

带有量 $K$ 的误差估计如下:

$$\begin{array}{}\text{(19.60)}& \underset{i}{max}\left|x_i^{(\mu +1)}-x_i\right|\le \frac{K}{1-K}\underset{i}{max}\left|x_i^{(\mu +1)}-x_i^{\left(\mu \right)}\right|,\end{array}$$

这里 $x_i$ 为要求的解的分量, $x_i^{\left(\mu \right)}$ 与 $x_i^{(\mu +1)}$ 为相应的第 $\mu$ 次和第 $\mu +1$ 次近似值.

19.2.2.2 牛顿法

牛顿法可以用来求解形如 (19.55) 的问题. 在得到初始近似值 $x_1^{\left(0\right)},x_2^{\left(0\right)},\cdots ,x_n^{\left(0\right)}$ 后, $F_i$ 作为 $n$ 个独立变量 $x_1,x_2,\cdots ,x_n$ 的函数按泰勒公式展开 (参见第 630 页 7.3.3.3,1.). 在线性项后终止展开, 由 (19.55) 可得线性方程组, 其迭代改进则通过如下公式得到

$$F_i\left(x_1^{\left(\mu \right)},x_2^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)+\sum _{k=1}^n\frac{\partial F_i}{\partial x_k}\left(x_1^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)\left(x_k^{(\mu +1)}-x_k^{\left(\mu \right)}\right)=0$$$$\begin{array}{}\text{(19.61)}& \left(i=1,2,\cdots ,n;\mu =0,1,2,\cdots \right).\end{array}$$

要在每一步迭代中求解的线性方程组 (19.61) 的系数矩阵为

$$\begin{array}{}\text{(19.62)}& {\mathbf{F}}^{\prime }\left({\mathbf{x}}^{\left(\mu \right)}\right)=\left(\frac{\partial F_i}{\partial x_k}\left(x_1^{\left(\mu \right)},x_2^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)\right)\left(i,k=1,2,\cdots ,n\right),\end{array}$$

称之为雅可比矩阵. 若雅可比矩阵在解的邻域内是可逆的, 牛顿法是局部平方收敛的,即收敛基本上依赖于是否适当选取了初始近似值. 若在 (19.61) 中代入 $x_k^{(\mu +1)}-$ $x_k^{\left(\mu \right)}=d_k^{\left(\mu \right)}$ ,则牛顿法可写成校正形式

$$\begin{array}{}\text{(19.63)}& x_k^{(\mu +1)}=x_k^{\left(\mu \right)}+d_k^{\left(\mu \right)}\left(i=1,2,\cdots ,n;\mu =0,1,2,\cdots \right).\end{array}$$

为降低对初值的依赖性,与松弛法类似,引入所谓阻尼或步长参数 $\gamma$ (阻尼法):

$$\begin{array}{}\text{(19.64)}& x_k^{(\mu +1)}=x_k^{\left(\mu \right)}+\gamma d_k^{\left(\mu \right)}\left(i=1,2,\cdots ,n;\mu =0,1,2,\cdots ;\gamma >0\right).\end{array}$$

确定参数 $\gamma$ 的方法见 [19.31].

19.2.2.3 无导数高斯-牛顿法

为求解最小二乘问题 (19.24), 对非线性问题可以进行如下迭代:

(1) 从适当的初值 $x_1^{\left(0\right)},x_2^{\left(0\right)},\cdots ,x_n^{\left(0\right)}$ 出发,对于非线性函数 $F_i\left(x_1,x_2,\cdots ,x_n\right)$ $\left(i=1,2,\cdots ,m;m>n\right)$ 由牛顿法 (19.61) 的线性函数 ${\tilde{F}}_i\left(x_1,x_2,\cdots ,x_n\right)$ 近似,得到迭代步骤如下:

$${\tilde{F}}_i\left(x_1,\cdots ,x_n\right)=F_i\left(x_1^{\left(\mu \right)},x_2^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)+\sum _{k=1}^n\frac{\partial F_i}{\partial x_k}\left(x_1^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)\left(x_k-x_k^{\left(\mu \right)}\right)$$$$\left(i=1,2,\cdots ,m;\mu =0,1,2,\cdots \right)\text{.}$$

(19.65)

(2) 在 (19.65) 中代入 $d_k^{\left(\mu \right)}=x_k-x_k^{\left(\mu \right)}$ ,校正项 $d_k^{\left(\mu \right)}$ 由高斯最小二乘法,即求解线性最小二乘问题确定

$$\begin{array}{}\text{(19.66)}& \sum _{i=1}^m{\tilde{F}}_i^2\left(x_1,\cdots ,x_n\right)=min,\end{array}$$

例如借助正则方程 (见 (19.42)), 或豪斯霍尔德方法 (参见第 1280 页 19.6.2.2).

(3)所求解的近似值由以下公式给出:

$$\begin{array}{}\text{(19.67a)}& x_k^{(\mu +1)}=x_k^{\left(\mu \right)}+d_k^{\left(\mu \right)}\end{array}$$

或

$$\begin{array}{}\text{(19.67b)}& x_k^{(\mu +1)}=x_k^{\left(\mu \right)}+\gamma d_k^{\left(\mu \right)}\left(k=1,2,\cdots ,n\right),\end{array}$$

其中 $\gamma \left(\gamma >0\right)$ 类似于牛顿法为步长参数.

重复步骤 (2) 与步骤 (3),用 $x_k^{(\mu +1)}$ 代替 $x_k^{\left(\mu \right)}$ 得到高斯-牛顿法. 于是得到近似值序列,其收敛性依赖于初值的准确性. 误差的平方和可以通过引入参数 $\gamma$ 而降低.

如果偏导数 $\frac{\partial F_i}{\partial x_k}\left(x_1^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)\left(i=1,2,\cdots ,m;k=1,2,\cdots ,n\right)$ 的计算量过大, 偏导数可由以下差分近似得到

$$\frac{\partial F_i}{\partial x_k}\left(x_1^{\left(\mu \right)},\cdots ,x_k^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)$$$$\approx \frac{1}{h_k^{\left(\mu \right)}}[F_i\left(x_1^{\left(\mu \right)},\cdots ,x_{k-1}^{\left(\mu \right)},x_k^{\left(\mu \right)}+h_k^{\left(\mu \right)},x_{k+1}^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)$$$$-F_i\left(x_1^{\left(\mu \right)},\cdots ,x_k^{\left(\mu \right)},\cdots ,x_n^{\left(\mu \right)}\right)]$$$$\begin{array}{}\text{(19.68)}& \left(i=1,2,\cdots ,m;k=1,2,\cdots ,n;\mu =0,1,2,\cdots \right).\end{array}$$

所谓离散步长 $h_k^{\left(\mu \right)}$ 可能依赖于迭代步数和变量值.

若用 (19.68) 近似,则高斯-牛顿法仅需计算函数值 $F_i$ ,即该方法是与导数无关的.