数值分析——近似当中的精确
小编说：
谢谢大家对我们的关注，我们是由一大群来自各个领域的小伙伴轮流写文章来分享自己对不同领域的理解，和一些心得，希望能够为大家科普一些有趣的东西，也方便不同领域的童鞋的互相的了解与合作，因为一个领域发展的很完善的东西说不定就解决了另外一个领域的悬而未决的问题。
这篇文章介绍的是数学当中的一个偏应用领域的分支——数值分析——的基本思想和方法。数学是门有千年以上历史的学科，它的发展特点之一是对自身概念体系的严格化。譬如微积分的概念在最初发展时，并没有非常严格的基础。在17世纪牛顿、莱布尼茨开创微积分理论的时候，诸如“无穷小”这样的概念被频繁使用，但却并没有被很好地定义，以致于在很长一段时间内微积分学说都因为不够严谨而备受质疑。为微积分做严格化的努力持续了很长时间，直到150年后的19世纪，它的基础才被柯西和魏尔斯特拉斯等人严格建立起来：通过epsilon - delta语言定义了极限，然后基于极限再定义了导数，以至于发展出后面的一系列理论。这样微积分理论才无可辩驳地被数学家广为接受。
现代数学发展到上世纪，细化出了众多的分支。在数学的标准之下，这些分支无一例外，都是非常“严格”的。然而在这其中，却出现了一门”不那么严格”的学科——数值分析，或者狭义上所说的应用数学。
数值分析的发展伴随着计算机技术的广泛使用。这里我们需要举一个例子来说明它的必要性。假设我们现在要做科学计算，而算式当中用到了根号，譬如“根号10”。这个时候我们就需要知道精确到多少位是什么样子的。在数学的其他分支中，我们很少需要了解一个无理数的小数点后若干位是长什么样子的，但是在科学计算中我们就非常有必要知道。那么问题来了，我们如何计算呢？或者一般地说，对任意一个数x，我们该如何计算它的根号呢？我们日常使用的计算器都会实现开根号的算法。一个非常著名的方法是牛顿迭代法：首先随便找一个数r，然后依次计算
那么不难说明，这样产生的数列 r_n 会逐渐逼近根号x。这个算式当中的每一个运算（加法，乘法，除法）都是可以被计算机执行的，因此我们可以把它写成程序，放入计算机中，用来进行开根运算。然而数值分析的工作不止于此。在完成了“近似”的任务以后，还有必要进行定量分析。对应于上面这个例子就是：算法给出的r_n，到底在什么样的精度上逼近"根号x"了呢？如果不回答这个问题，那么我们对于这个计算仍然是缺少信心的，因为我们不知道这个近似解到底有多大的误差，以及是不是符合精度上的要求。
用牛顿迭代法求二次函数的根（来源：维基百科）
数值分析中的关于收敛速度的理论证明了，上面的牛顿法是“平方收敛”的。也就是说，每进行一次迭代，r_ 与真实值的误差大致上跟前一个 r_n 的误差的平方在一个量级。这意味着每进行一次迭代，r_n 中正确的小数位数大致上会加倍。有了这样的理论保证，我们就不难推算出算法会在大约多少步以后达到预期的精度了。
（注：实际中计算器使用的开根算法和上述可能并非完全一致，而一般是改进过的或者其他效率高的算法。）
数值分析的发展一直遵循了上面的路径：构造某种数学工具来计算一个东西的数值解（近似解），然后运用数学理论来分析这个数值解离真实解到底差多远，或者说，解的误差有多大。一个好的算法，应该可以利用相对少的计算资源，来达到期望的误差。
数值分析经过多年的发展，特别是依赖于计算机技术的普及进步，在很多领域得到了应用。文章的剩下部分就选几个相对热门的方向尝试作一些介绍。
微分方程数值解
微分方程常常来源于物理和工程学。在航天领域中，飞行器的轨迹可以由常微分方程近似。温度在介质中的传导由经典的热方程描述，物质的波动可以通过波方程研究，还有著名的流体力学方程可以描述流体（气体或液体）随时间的状态改变。以上这三种方程都是偏微分方程。
非常可惜的是，对于大多数微分方程，我们都无法用显式表达出它们的解。特别是加上一些复杂的初始和边界条件以后，显式求解就显得更加不可能了。这时数学家们能做的往往只能是保证方程的解是存在的和唯一的。更有甚者，例如大名鼎鼎的Navier–Stokes方程，也就是上面提到的流体力学方程，我们对于它的解到底存不存在都搞不清楚。美国克雷数学研究所在2000年挑选出了千禧年的七大数学难题，设置每道题100万美元的奖金，奖励给成功给出解答的人，其中一个问题就是Navier–Stokes方程。顺便值得一提的是，这七个问题中至今为止只有一个被成功解决（庞加莱猜想被证明为真），但神秘的获奖者俄罗斯人佩雷尔曼却拒绝了领奖以及百万奖金。
对于微分方程，由于显式求解不是一个选项，数值求解就变得尤为重要。在这方面非常多的算法被发展出来，例如最为简单的有限差分方法，还有极其成功的有限元法以及有限体积法。它们的思想都是把连续的函数用一些离散的点表示，进而把连续的微分方程转化为离散的代数方程，使得问题可以被求解。
微分方程的一个应用实例是天气预报。可能很多人并不了解，现代的天气预报已经主要凭借数值方法来生成了。大气是流体，所以它的状态变化可以借助流体动力方程描述。如果把用各种方法收集到的气象信息作为初始条件输入到这些大气动力模型当中，并且由计算机求解，就可以预测未来一段时间内的天气情况。最早的数值天气预报模型非常糟糕，“就算预测第二天的天气跟前一天一模一样，准确率也比数学模型要来得高”，我的数值代数老师在课上这样讲。但是由于模型的改进和计算机性能的大幅提升，现今数值预测方法已经成为主流，并且越来越少地需要人工干预了。今天世界上的很多计算能力最强的超算（超级计算机）都被用来进行天气预报的计算。
最优化问题
最优化问题寻求某个问题的最优解，一般情况下我们希望最小化（或者最大化）一个函数。一类传统的方法是迭代法。迭代法从一个初始点开始，不断寻找新的点，使得函数在新点上取值更小，如此循环下去，以期望找到函数的极小点。寻找新点的方法很多，例如可以求得函数在当前位置沿各个方向的偏导数，然后沿着斜率最大的方向下降，这个方法就叫做梯度下降法。在处理二次函数的优化问题时，有特别的共轭梯度法，它相比梯度下降法收敛速度快了很多。
梯度下降法的示意图（来源：维基百科）
由于深度学习的兴起，梯度下降法在统计学习中受到了前所未有的重视。被称为“随机梯度下降”的算法在每次迭代时只选择一个或者若干个样本进行优化，从而避免了为整个样本集的计算梯度的巨大运算量，大大降低了运算复杂度。这使得大数据集上的机器学习成为可能。同时神经网络由于其惊人的优秀表现，成为当下很多人工智能领域的首选工具。除了神经网络，梯度下降算法也被应用到逻辑回归（logistic regression）、支持向量机（SVM）等机器学习的计算当中。
矩阵的特征空间
矩阵的特征值和特征向量问题是数学里的经典内容。在理论层面，关于矩阵的特征值和特征向量有着非常丰富完备的结论；但在数值上对它们求解则往往是一个相当棘手的问题。在实际应用当中，对于“对称矩阵”的特征空间求解在统计中的主成分分析（PCA）和图论中的谱方法（spectral graph theory）都有重要的应用。求解这样的问题，在传统上有QR算法，而在最近divide-and-conquer算法因为其效率和稳定性而受到了重视。
在本文的最后写一点个人的想法，作为结束。数值分析在某种意义上起源于人类的好奇心，因为我们想知道诸如“根号10”、π、e 这样的数到底等于多少。到了后来我们慢慢发现，计算这些数值的重要性，已经远远超过了满足我们好奇心的程度。如果去仔细研究对这些数的一些近似方法，你会发现它们跟纯理论的关系实际上是非常紧密的。所以今天我们在一些数值方法上遇到了瓶颈，例如对于流体的湍流效应不能很精确地求解，那在Navier–Stokes方程理论上的突破也许是解决问题的一条路径。
在另一方面，我们对于未来的预测永远都是有精度上的限制的，这是因为计算机的性能不可能无限强大，而我们对初始条件也不可能做到无限细分。这在某种程度上可能还原了数值分析的原本意义——我们可以无限地逼近真实的解，但可能永远都无法达到那个真实的解。
作者介绍：
本文作者许文放，现就读于宾州州立大学数学系，研究方向是偏微分方程数值解和图论。
版权声明：
本文采用若干网络图片，版权归原作者所有。本文版权归作者许文放（以下简称“作者”）所有，未经作者授权不得转载、摘编或利用其它方式使用本文内容。已获得作者本人授权使用作品的，应在授权范围内使用，并注明“来源：微信公众号 跨行业俱乐部”。违反上述声明者，作者将追究其相关法律责任。
- 发表于:
- 原文链接：http://kuaibao.qq.com/s/20180302G0NHFE00?refer=cp_1026
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
