非线性方程的延拓法
概述
- 前置概念：同伦
- 作用对象：非线性方程组
- 目的：扩大非线性方程组的收敛域
延拓法的基本思想
- 已知一个待求解的非线性方程组 \(F(x)=0\)
- 在方程组中引入一个参数 \(\lambda\)，构造 \(F(x)\) 的同伦映射 \(H(x,\lambda), \lambda \in [0,1]\), 使得
\(H(x,0)=0, H(x,1)=F(x)\)
- 已知 \(H(x,0)=0\) 的解是 \(x=x_0\) (可以是零向量 \(\bar{0}\) )
- 数值迭代，求解满足 \(H(x,1)=0\)
的解 \(x^*\)
- 构造序列 \(\\{ \lambda_i \\} = \\{0,...,\lambda_i,...1\\}, i = 0,1,2,...,N\)
- 以 \(x_0\) 为初值，求解 \(H(x,\lambda_1)=0\) （例如，Netwon迭代），解为 \(x_1\)
- 以 \(x_1\) 为初值，求解 \(H(x,\lambda_2)=0\)，解为 \(x_2\)
- 以 \(x_i\) 为初值，求解 \(H(x,\lambda_{i+1})=0\)，解为 \(x_{i+1}\)
- 最终求得 \(H(x,1)=0\) 的解 \(x_N\), 即 \(F(x)=0\)的解 \(x^*\)
- 该方法的结果相当于扩大了传统非线性方程组迭代求解方法的收敛域
Mark 1： Newton迭代时，可只迭代一步，因为最终目标是求 \(\boldsymbol{x}^*\) Mark 2：\(N\) 足够大
延拓法的数学表述
传统的求解非线性方程组求解方法是局部收敛的，只有初值 \(x_0\) 足够接近真值，迭代方法收敛。然而，延拓法作为可以扩大收敛域的有效方法，可以从任意的 \(x_0\) 出发，通过延拓求解得到方程的解 \(x^*\)。
引入参数 \(\lambda\)，构造一簇同伦映射 \(\boldsymbol{H}:D\times[0,1] \subset \mathbf{R}^{n+1}\rightarrow \mathbf{R}^n\) 代替单映射 \(\boldsymbol{F}(\boldsymbol{x})\)，令 \(\boldsymbol{H}\) 满足条件：
\[ \boldsymbol{H}(\boldsymbol{x}_0,0)=\boldsymbol{0} \]
\[ \boldsymbol{H}(\boldsymbol{x},1)=\boldsymbol{F}(\boldsymbol{x}) \]
它表明当 \(\lambda=0\) 时，\(\boldsymbol{H}(\boldsymbol{x},0)=\boldsymbol{0}\) 的解 \(\boldsymbol{x}_0\) 已知；当 \(\lambda=1\) 时，\(\boldsymbol{H}(\boldsymbol{x},1)=\boldsymbol{F}(\boldsymbol{x})=0\) 的解 \(\boldsymbol{x}^*\) 为非线性方程组的解。
现考虑同伦方程：
\[ \boldsymbol{H}(\boldsymbol{x},\lambda)=\boldsymbol{0} \\quad \lambda \in [0,1],\boldsymbol{x}\in D \subset\mathbf{R}^n \]
如果对每个 \(\lambda \in[0,1]\)，上述方程有解 \(\boldsymbol{x}=\boldsymbol{x}(\lambda), \boldsymbol{x}:[0,1]\rightarrow D\) 且连续，则 \(\boldsymbol{x}=\boldsymbol{x}(\lambda)\) 是关于参数 \(\lambda\in[0,1]\) 在 \(\mathbf{R}^{n+1}\) 中的一条曲线。该曲线的一端为已知点 \((\boldsymbol{x}_0,0)\)，另一端是点 \((\boldsymbol{x}^*,1)\)，\(\boldsymbol{x}^*\) 即为非线性方程组的解，这就是延拓法，也被称作同伦法。
满足条件的同伦可以有各种不同的取法，常用的有两种。
牛顿同伦： \[ \boldsymbol{H}(\boldsymbol{x},\lambda) =\boldsymbol{F}(\boldsymbol{x}) +(\lambda-1)\boldsymbol{F}(\boldsymbol{x}_0) \]
凸同伦： \[ \boldsymbol{H}(\boldsymbol{x},\lambda) = t \boldsymbol{F}(\boldsymbol{x}) +(1-\lambda)\boldsymbol{A}(\boldsymbol{x} - \boldsymbol{x}_0) \]
其中 \(\boldsymbol{A}\in\mathbf{R}^{n\times n}\) 是非奇的