数据词典：数值计算（Numerical Computation）

赵老师

数值计算(numerical computation) 是指有效使用数字计算机求数学问题近似解的方法与过程，或这些方法与过程连同有关理论所构成的学科。数值计算是一门实用性很强的学科， 近年来随着计算机的发展和广泛应用，许多计算领域的问题，如计算力学、计算物理、计算化学、计算经济学等新分支都可归结为数值计算问题。

早在公元前14 世纪的商代就基本形成十进制的记数法，春秋战国时代筹算已得到普遍应用，并形成和发展了算筹作为通用有效的计算工具,以后改进演化为算盘，相应发展了珠算方法。

数值计算在古代已取得了重要成果。早在公元1 世纪，汉代的“九章算术”记载了开平方、开立方、解一元二次方程和三元一次方程的方法。公元5 世纪南北朝时期，著名数学家祖冲之算得圆周率π为3. 14 159 265，精确到小数点后7位，这项纪录保持了近千年。南宋数学家秦九韶于1247 年写成“数书九章”，提出的联立一次同余式和高次方程数值解的秦九韶法，比西方Euler和Horner于1819年提出的算法早五百多年。

    随着近代数学的形成和发展，数值计算也取得了相应的进步。20 世纪40 年代中后期, 电子计算机的出现与迅速发展，有力推动了数值计算的研究与发展，解决了许多难度与规模都很大的计算问题，提出了许多新的数值方法，数值计算在整个科学技术和经济生活中的重要性得到前所未有的体现，并获得极大的发展，形成了一门新的学科分支。

数值计算与计算机的发展相辅相成，相互促进。大量数值计算的需要，促使计算机体系结构及性能不断更新，而计算机的发展又推动着数值计算方法的发展，每当计算机发生一次变革，数值计算也产生一次飞跃。为适应现代计算机的飞速发展，对数值计算提出了新的要求，对原有计算方法提出了重新评价、筛选、改造和创新。与此同时，也涌现了许多新概念、新方法，从而构成了现代数值计算的新涵义，如计算机系统界面的多媒体化，给计算过程可视化提供了软件环境。

数值计算研究有效使用计算机数值求解各种数学问题，包括离散型方程的数值求解和连续系统离散化的数值求解，在数值求解数学问题时，需要考虑误差、收敛性和稳定性等问题。所谓关于给定计算问题的一个近似算法是收敛的，是指由该算法能产生近似解的一个无穷集合，这个集合按某种选定的距离能逼近精确解到任意程度。即对任给的ε> 0，都能从该集合中找到与精确解的距离小于ε的近似解。误差是指连续系统离散化产生的方法误差( 截断误差) 和数值计算过程中产生的误差(舍入误差) 。稳定性是指在执行数值算法的过程中，舍入误差的积累不影响产生可靠结果。此外，还要研究算法的计算复杂性(计算量大小为时间复杂性，存储量大小为空间复杂性) 以及在使用计算机时，算法的自适应性。因此，误差、收敛性、稳定性、计算复杂性和自适应性是数值计算的基本问题，刻画了数值计算方法的可靠性、准确性、效率以及使用方便性，是数值计算必须研究的基本理论。

数值计算的研究内容随着计算机发展和应用范围的扩大而不断扩大，从数学类型看，它包括数值逼近、数值微分与数值积分、数值代数、最优化方法、常微分方程数值解法、积分方程数值解法、偏微分方程数值解法、计算几何、计算概率统计等。

数值逼近是研究函数的离散逼近，用适合于计算机上计算的简单函数(如多项式，连分式等) 逼近复杂函数。主要包括插值法、最佳一致逼近、最佳平方逼近与最小二乘逼近。各种代数插值是连续系统离散化的基础，理论与实践表明，分段低次插值比高次插值具有更好的稳定性。由于样条函数具有良好的特性，已成为函数逼近的重要工具而被广泛应用，样条逼近是函数逼近的一个重要研究方向。数值逼近也是生成初等函数子程序的重要方法。

数值微分与数值积分是在数值逼近基础上发展起来的计算微分与积分的数值方法。数值微分由于稳定性问题计算效果不理想，特别是对高阶导数和多元函数偏导数的计算效果更差。80 年代提出的新方法是用公式的数值求导或用符号运算的解析求导。数值积分常用的方法是数值稳定的，各种方法的差异在于计算量大小和自适应性，反常积分与高振荡积分要采用特殊的数值积分法。

快速傅里叶变换( FF T) 是用三角函数逼近周期函数的递推方法，它把N 个点变换的计算量从O( N2 ) 下降为O( N log2 N) ，当N 很大，效果尤为明显。FFT 算法为调和分析方法在谱分析、信号处理和图象处理等领域应用计算机开辟了道路，也开创了各种快速算法的先河。

数值代数是对有限维离散型方程的数值求解，内容包括线性代数方程组数值解法、矩阵特征值问题数值解法、一元方程求根、非线性代数方程组数值解法等。各种连续系统的离散化，最终归结为有限维离散型方程的数值求解。这类方程的数值解法分为两类，一类是迭代法，主要是构造收敛快、计算复杂性好的算法。对线性方程，人们针对不同类型方程特点，构造了行之有效的各种迭代法。对非线性方程，以牛顿法为代表的各种牛顿型迭代法已得到广泛应用，但由于这类方法只具有局部收敛性，因此，近20 年来，具有大范围收敛的同伦连续法、单纯同伦算法、区间迭代法和单调迭代法等成为该领域的重要研究课题。另一类是直接法，它只对线性方程和极特殊的非线性方程有效，直接法由于舍入误差影响, 方法的稳定性和方程是否病态等问题受到极大关注。当前病态方程组及大型稀疏方程组数值解法仍然是重要的研究方向。特征值计算包括标准特征值、广义特征值和反特征值问题的计算，反特征值问题由于条件的不同，提法各异，目前发展迅速并有广泛应用。

最优化方法是数值计算的一个迅速发展的领域，它研究在结构比较复杂的集合上泛函的极值问题。首先是规划问题，包括线性规划、非线性规划和动态规划等问题，经济学中许多问题可归结为这类问题。线性规划是理论成熟、应用最广泛的部分，基本解法是单纯形法。1984年，N.Karmarker提出了一种多项式时间的新方法，引起广泛注意。此外，运筹学和对策论中提出的极小极大问题及相应的计算方法也是最优化计算的研究内容。在经济和工程中求解大型最优化问题，目前已有可供使用的通用和专用的计算软件。

常微分方程数值解法包括初值问题与边值问题两类，初值问题的基本算法是龙格库塔法和阿当姆斯法。近20 年来，刚性问题的数值解法及其稳定性理论的研究有很大进展。边值问题的数值解法主要有两种，一种是转化为初值问题的打靶法；另一种是直接离散化的差分方法和变分方法。积分方程数值方法是直接将数值积分公式转化为离散化方程求解。

偏微分方程数值解法主要研究方程的离散化和对离散方程的求解，以及有关适定性、收敛性、稳定性、误差和自适应性等理论问题，使用计算机进行科学与工程计算往往涉及到偏微分方程的数值解法,诸如天气预报、反应堆设计的核扩散研究、液体流动、超音速流及弹性力学、地球物理、地震勘探等。

偏微分方程数值解法有正演问题和反演问题两类。正演问题是给定方程和定解条件求偏微分方程的解，它主要是二维和三维的定常问题和非定常问题。微分方程的离散化主要有差分法和有限元法两大类。差分法以差商逼近导数, 将微分方程离散为差分方程，这种方法简单，适用于任何类型的方程，同时便于机器实现。有限元方法基于等价的变分原理的形式，采取任意格网分片逼近的手段，把传统对立的差分方法与里茨伽辽金变分方法有机地结合起来，发展成为解定常问题的主导方法，并推广到非定常问题。有限元法具有几何上灵活适应的突出优点, 特别适合于解决复杂性大的问题。目前已有比较成熟的通用和专用有限元法计算软件，这些软件在众多科技领域和工程设计中已得到普遍应用。反演问题是在给定方程的模式下，已知其解或解的某一部分，要反推求该方程的系数和边界的形式等，起着导果求因的作用。这类问题在医疗卫生、无损探测、遥感遥测、地震勘探、地球物理等领域大量存在，它们通常是不适定的、病态的, 有其特殊的难点。反演问题数值解法是一个正在开拓的新领域。

计算几何是数值计算的新分支，它研究静态或动态的几何形体和视象的离散化，以及逼近与生成的计算方法，是计算机辅助几何设计(CAGD) 这门技术的数学基础。计算几何在计算机制图、计算机辅助设计、计算机辅助制造、计算机动画、计算机视象、机器人技术等众多领域有重要的应用。

计算概率统计主要研究随机数据的统计分析计算和概率系统模型的随机模拟计算。前者包含多元统计分析计算、时间序列分析计算、马尔可夫链计算和数值滤波等。后者最常用的是蒙特卡罗法。这方面的计算是根据实际问题的概率统计模型, 对试验观测数据或随机模拟数据进行统计分析处理，给出实际问题性质的统计描述、统计控制或统计预测的数值结果。目前已研制出了众多的计算概率统计软件供用户使用。

数值计算软件是数值计算研究的另一个重要方面，每个数值软件实现一个特定的计算方法的标准程序模块，由一个或几个标准子程序组成。由于数值计算软件经常为用户使用，因此，它的研制除了要吸取一般软件理论和技术外，还有它自身的特点。首先要对计算方法进行认真选择，考虑方法的适用性、准确性、稳定性、计算量和存储量等因素。其次每个数值计算软件必须经过全面严格测试，以确保其正确性和可靠性。第三，每个数值计算软件需有详尽的说明书，对软件的使用、适用范围及正确性给予确切说明。目前, 已问世的数值计算软件涉及到数值计算各领域。随着数值计算方法的进一步发展和计算机的更广泛应用，数值软件包含的内容也将越来越广泛。

并行算法是数值计算的一个特别活跃的新领域, 它随着并行计算机的发展而迅速发展。并行计算机包括单指令流多数据流计算机(SIMD) 和多指令流多数据流计算机(MIMD) 两类，与其相应的算法分为同步并行算法和异步并行算法两类。20 世纪60 年代末到70 年代初，由于解偏微分方程及大型线性方程组等科学计算的需要，人们开始设计阵列式与向量式的新型结构计算机，开始研究同步并行算法。

1972 年，阵列式计算机ILIACN IV 在美国宇航局投入运行，TI ASC 在欧洲运转，此后向量计算机CDCSTAR 100 和CRAY 1 等相继于1974 年和1976 年在美国投入运转。从1972 年到1981 年这一时期，并行算法进入实践的阶段与具体并行机的相关性增强，并行算法复杂性分析与评估有了新的内容，并行数值计算软件开始研制，但集中在串行程序的向量化研究上。

1982年—1991年是并行算法研究的兴盛期，在这一阶段，MIMD 超级计算机系统CRAY X MP、HEP 与CRAY 2 等相继投入运行，各类MIMD 计算机系统如雨后春笋，特别是大规模并行SIMD 计算机CM 2 及MIMD 计算机CM 5 相继于1987年和1991 年问世，一些大型科学与工程问题，如来自航天、化学、天体物理、材料科学、数据检索、石油勘探、天气预报等广泛领域中的问题，都能应用这种大规模并行计算机来求解。这时期并行计算的特点是:同步并行算法日益成熟并逐步完善；SIMD 计算机语言开始形成以For t ran 90 为基础的标准框架；异步并行计算成了热门研究课题。

1992 年以后，并行计算开始转入标准化时期，这时期出现了规模更大速度更快的并行机，1994 年思维公司推出了它的第五代并行处理系统CM5E，它的峰值运算速度达到每秒830亿次浮点运算，CRAY 研究公司也于1994 年宣布了世界上最先进的并行处理机CRAY T3D 系统，该系统由2 048个处理机组成，其峰值运算速度达每秒3 072 亿浮点运算，这些对并行算法引起了深刻的变革，出现了一些新的研究方向，如格子气方法、基于神经网络的并行算法以及演化算法等。而并行计算语言的标准化和并行虚拟机的研究为并行算法的研究开辟了道路。

【出处】张效祥. 计算机科学技术百科全书,清华大学出版社,2018年5月第3版.