研学小记：

     局部化分析的应用和限制

     Applications and Restrictions of Localization Analysis

                                                                                                                                                      邹谋炎

    Gauss-Seidel迭代是解大型代数方程组的常用算法，这个算法能够从物理上进行解读吗？

    回忆一下Gauss-Seidel迭代算法，描述如下。给每个未知量一个起始猜测，然后逐个地解代数方程组的每个方程，解每个方程时依次地只保留一个未知量，而把其余未知量代之以起始猜测值或经过计算更新后的值。这样，每次解一个一变量方程，实现变量更新。依次逐个地解每个方程，实现每个变量更新。重复许多遍，直到收敛。

    “解每个方程时依次地只保留一个未知量”是算法的要点。它的物理含义是清晰的。把每个未知量看成状态变量。含一个未知量的方程是以该未知量为中心、其余未知量为边界条件的关联关系。这种解方程的方法就是一种“局部化分析”。与此对照，对线性代数方程求解，以Gauss消去法为基础的各种算法（如LU分解）是非局部算法或整体算法或全局算法。

    了解电路的读者知道，按“回路电流法”或“节点电压法”列出的每个方程就是一组相互关联的回路或节点上状态的“局部化”描述。

    其实，“局部化分析”是一种很常见的分析计算方法，例如偏微分方程离散化求解；基于Markov随机场的图像分析、综合和反降晰；模拟退火和各种演化规划算法；神经网络学习算法；自组织神经网络算法；自适应信号处理算法；盲目信号分离和辨识等等。

    局部化分析的必要性常常是基于以下原因：难以实施整体描述和分析。困难可能来自（1）过程的无穷边界；（2）问题尺度太大，超出可得到的计算资源能力；（3）全局描述的复杂性太高。

    一个基本问题是：局部化分析是不是能够导致一个正确的解？有以下结果。

    (1) 由于非奇异线性代数方程的算子是一个压缩映象算子，对线性代数方程而言，如果局部化算法收敛，必定收敛到与任何整体算法相同的解。

   （2）即使对于非奇异线性代数方程，局部化算法不能保证在所有情况下都收敛。

   （3）Gauss-Seidel 迭代能够保证对一大类线性代数方程是收敛的（充分条件）：矩阵是对称正定的，或矩阵是“主对角占优”（Diagonally Dominant）。

    幸运的是，大量的数学物理问题，如力学、热传导、电磁场等问题的数值分析计算中，已经发现最终的代数方程常常不仅是正定（或可以转化成正定的），而且是主对角占优的。因此，Gauss-Seidel 迭代在应用上很成功。需要指出一个物理事实，正定而且主对角占优的矩阵，对应一个无源电阻网络的实现。可以认为，这些问题内涵着一个共性，称为“无源性”。这个概念不仅仅对电子信息领域有意义，也是更广泛物理领域中值得研究的概念。一个需要提到的事实是，使用电阻网络仿真来实现偏微分方程的求解是一个“古典方法”。虽然被人们淡忘了，笔者认为，它有可能成为下一代人工神经网络研究和仿真实现的一个新起点。

    以上所说局部化分析的第二条限制最值得重视。局部化分析原则上可以试用于非线性方程组的求解，但不保证收敛。当转化为最小化一个价格函数的优化问题时，如果算法收敛，一般只收敛到一个局部最小化点。在神经网络的研究中，有两个致命的问题：（1）局部化分析方法的滥用不能保证学习或训练方法结果的收敛性和正确性（仅在很受限制的条件下可以证明收敛性）；（2）更要命的是，局部化分析内在地是一种“串行”算法，与神经网络希望的“大量并行”处理有本质上的隔阂。可以想象，曾经风行的神经网络研究如果没有在“大量并行”处理的研究和实现上取得进步，我们就必须从源头上思考问题的症结和出路。

（注记：本文包含着若干原创性思想，利用这些思想者，需注明出处。）