计算科学 - 冗余变量是否有利于寻根收敛 - 吾爱随笔录

假设我有 $n$ 一般非线性方程 $n$ 变量，例如 for $n=2$ 系统 $F(x,y)=0$

\begin{aligned} x^{2} + 2 y - 4 & = 0 \\ \sqrt{8} x + y^{2} - 5 & = 0 \end{aligned}

$\begin{aligned} x^2+2y-4&=0\\ \sqrt{8}x+y^2-5&=0 \end{aligned}$

通过为中间结果引入变量，我可以将其转换为（几乎，至少，直到一些额外的奇点，我不关心我的问题）具有更多变量的等效方程组，例如 4 4 个变量的方程 $G(x,y,z,w)=0$

\begin{aligned} x \cdot x - z & = 0 \\ y \cdot y - w & = 0 \\ z + 2 y - 4 & = 0 \\ \sqrt{8} x + w - 5 & = 0 \end{aligned}

$\begin{aligned} x\cdot x-z&=0\\ y\cdot y-w&=0\\ z+2y-4&=0\\ \sqrt{8}x+w-5&=0 \end{aligned}$

现在我想以数值方式求解这样的系统，例如，使用像KINSOL这样的牛顿求解器。

在使用该系统时是否有任何可预期甚至可证明的优势？ $G$ 带有冗余变量（ $z$ 和 $w$ ) 过度使用简化系统 $F$ ? 还是通常情况更糟？

如果这个问题完全可以回答，那么答案对选择不同的求解器是否敏感？

通过挥手的论点，我同样可以得出相反的猜测：

变量越多，算法在寻找根方面的自由度就越大，并且在困难区域（例如局部不良条件数或高曲率）中不会那么容易卡住
变量越多，搜索空间的维度就越高，因此算法越有可能误入歧途

我无法想象这个问题以前从未被处理过。但显然，我不知道正确的关键字。

附录（20180310）：这个问题背后的主要思想是，通过在一组复杂的方程组中为每个中间结果引入辅助变量，可以将上述原理推向极限。剩下的是每个二元运算符（引用三个变量）的一组“原子”方程， $b(x_i,x_j)-x_k=0$ ，或一元运算符/基本函数（引用两个变量）， $u(x_l)-x_m = 0$ , 而不是更复杂的复合方程 $f(x_1,...,x_n)=0$ 可以直接计算违反约束的情况（这很好），但是引用了许多变量（这很糟糕）。

因此，一个密集的非线性系统被简化为一个稀疏的非线性系统，同样在求解过程中，这会导致一个稀疏的线性系统。对于求根算法来说，“原子”方程可能（希望）更容易处理。

因此，问题可以重新表述为：求解具有较少变量的密集（或非常非局部耦合）系统是否更好（非线性收敛速度），或者求解等效稀疏（或仅局部耦合）系统更好许多变量（其中大部分仅代表函数计算的中间结果）。