那些年,数值计算教会我的道理

本文是受 这条推文 启发所写的。我不是一个数学系学生,领悟不了高深数学定理中的哲理,只能从日常打交道的数值计算方法中写点鸡汤,与诸君共享。

为什么我们需要数值解?因为现实太复杂,完美的解析解对绝大部分问题来说是不存在的,只有那些简单的问题才有解析解。采用数值解的话,我们可以根据问题的规模和我们的计算能力来决定我们希望获得多高精度的解。太高精度的解对我们来说并没有意义,够用就好。

很多数值解法都有一个共同的思想,即找到一组正交基,在其张成的空间里求原问题的最优解(往往是解方程组)。这样求得的解当然不是原问题的最优解,因为原问题往往是定义在无穷维的空间上的,而求解的空间是有限的。我们没有办法尽善尽美在无限维空间中求解,但是我们可以选出我们最关心的维度,这样构造解的时候只需遵循有限的限制。为什么要正交基?不正交的基有时候也不是不可以,但是处理起来会很麻烦。比起相互制掣的要求,互相独立的要求肯定更容易考虑。把各个成分之间互相影响的因素降到最低,更有利于我们设计、控制和调整问题的解。

为什么要用迭代法?因为我们有太多的问题(变量和方程),消元法这种逐个逐个解决的耗时太大,完全不切实际。迭代法让我们每次都能获得一个更好一点的情况,直到收敛到某个满足要求的范围内,而这往往比精确解决所有问题要快得多了。

经典的迭代解法,如雅可比(Jacobi),高斯-赛德尔(Gauss-Seidel)以及超松弛(SOR)法,都是定常迭代法,每次更新的模式都是一样的,由迭代矩阵唯一确定了。这就像选定了一个方法,一条道走到黑,不是不能得到解,但是对迭代矩阵的性质有要求,很多时候并不能收敛。

梯度下降法(Steepest Descend)每一步沿着梯度下降最快的方向走,然而收敛到解的速度相当慢。沿着阻力最小、最容易前进的方向移动自然是最简单的,但并不是通往目的地最快的道路。

广义最小残量方法(GMRES)记得之前每一步的残差,并从它们张成的空间里求出下一次更新的方向。然而每次求更新方向的运算量与保存的此前的步数 k 的平方成正比,越到后面,每一次求解更新方向所需的计算量就更大,而且 Krylov 子空间更接近线性相关。记得过去的教训能为以后的方向提供参考,但是历史积累越多,负担也越重,而且会变成『日光之下无新事』(线性相关)。因此,GMRES 往往在若干步迭代以后就以当前的解作为初始解,不再考虑之前保存的残差信息,重新开始迭代。令人惊讶的是,这种方法往往收敛性也很好。

共轭梯度法(Conjugate Gradient)每一次的更新方向都与前面的方向共轭,理论上最多不超过 N 次就能收敛到精确解。它每次更新的方向都是当前的梯度方向与上一次更新方向的组合,因此之前每一次的更新方向信息都得以保留。如果说 GMRES 是记得过去的错误,那么 CG 则是记得过去的方向,并且每次都在没有尝试过的方向上进行尝试。然而,浮点数的精度是有限的,很多步的迭代以后,共轭性会开始丧失,就像人的记忆不可能完整无误一样,因此实际上不是经常可以在 N 步以内收敛到精确解附近。

预条件子(Preconditioner)是用来改变原有问题的操作,它将待求解的问题从 Ax=b 变成了 MAx = Mb。预条件子可以是一个矩阵,或者某个对应于一个固定矩阵的操作,并且应该是易于求逆的。一般而言,预条件子 M 的逆应该接近 A 的逆。每次迭代的时候,都是先求解关于 M 的系统,再用得到的结果求解关于 A 的系统。M^-1 接近 A^-1 就像找到了一个类似于现有系统(A)的系统(M),但是是更容易解决的(M 易于求逆),这样我们解决现有系统 A 的时候,可以参考对 M 的求解结果,使得我们更快求解出现有的系统。

多重网格法(Multigrid)通过对方程组残差在细网格与粗网格之间的投影和求解,能交替快速消除误差的高频和低频分量,提高收敛速度。这就像是看问题不能总是盯着局部看(细网格),也不能只看大方向(粗网格)不考虑细节。交替考虑全局方向和局部细节能让问题更快得到解决。

区域分解法(Domain Decomposition)将求解的几何区域进行了划分,交由不同处理单元同时处理,每次更新时每个处理单元都要从相邻处理单元中获取更新了的信息。对于大型问题,DD 是必要的,否则无法利用大量的处理单元。但是,DD 的收敛速度比每个处理单元所采用的求解方法的收敛速度要慢,因为每个处理单元拿到的信息都是不完整的,就像一个团队中没有谁能处理所有信息和问题。如果各个子区域的重叠比例越大,它们得到的信息就更准确,收敛步数就越少,然而求解的速度也会变慢。这就像团队成员之间互相重叠的知识越多,他们越能准确理解别人的工作,以及别人的工作结果对自己工作的影响,也就不需要那么多的调整和磨合,但是需要更多的时间和精力去处理别人的工作结果。

对于迭代法而言,初解选得如何,并不影响收敛性。选得好,可能只是少迭代几步。但只要方法是对的,方向是对的,不论你从哪里起步,最后都能到达终点。

发表评论

电子邮件地址不会被公开。 必填项已用*标注