数值分析

数值分析（英语：numerical analysis），是指在数学分析（区别于离散数学）问题中，对使用数值近似（相对于一般化的符号运算）算法的研究。巴比伦泥板YBC 7289是关于数值分析的最早数学作品之一，它给出了 2 {displaystyle {sqrt {2}}} 在六十进制下的一个数值逼近， 2 {displaystyle {sqrt {2}}} 是一个边长为1的正方形的对角线，在公元前1800年巴比伦人也已在巴比伦泥板上计算勾股数 ( 3 , 4 , 5 ) {displaystyle (3,4,5)} ，即直角三角形的三边长比。数值分析延续了实务上数学计算的传统。巴比伦人利用巴比伦泥板计算 2 {displaystyle {sqrt {2}}} 的近似值，而不是精确值。在许多实务的问题中，精确值往往无法求得，或是无法用有理数表示（如 2 {displaystyle {sqrt {2}}} ）。数值分析的目的不在求出正确的答案，而是在其误差在一合理范围的条件下找到近似解。在所有工程及科学的领域中都会用到数值分析。像天体力学研究中会用到常微分方程，最优化会用在资产组合管理中，数值线性代数是资料分析中重要的一部分，而随机微分方程及马尔可夫链是在医药或生物学中生物细胞模拟的基础。在电脑发明之前，数值分析主要是依靠大型的函数表及人工的内插法，但在二十世纪中被电脑的计算所取代。不过电脑的内插算法仍然是数值分析软件中重要的一部分。数值分析的目的是设计及分析一些计算的方式，可针对一些问题得到近似但够精确的结果。以下是一些会用利用数值分析处理的问题：直接法和迭代法考虑以下问题要求解未知数x若是用迭代法，可用迭代法求解f(x) = 3x3 − 24=0，初值为a = 0, b = 3, f(a) = −24, f(b) = 57。计算到目前为止，问题的解是界于1.875及2.0625之间，若继续往下算，可以得到更精确的答案。直接法利用固定次数的步骤求出问题的解。这些方式包括求解线性方程组的高斯消元法及QR算法（英语：QR algorithm），求解线性规划的单纯形法等。若利用无限精度算术的计算方式，有些问题可以得到其精确的解。不过有些问题不存在解析解（如五次方程），也就无法用直接法求解。在电脑中会使用浮点数进行运算，在假设运算方式稳定的前提下，所求得的结果可以视为是精确解的近似值。迭代法是通过从一个初始估计出发寻找一系列近似解来解决问题的数学过程。和直接法不同，用迭代法求解问题时，其步骤没有固定的次数，而且只能求得问题的近似解，所找到的一系列近似解会收敛到问题的精确解。会利用审敛法来判别所得到的近似解是否会收敛。一般而言，即使使用无限精度算术的计算方式，迭代法也无法在有限次数内得到问题的精确解。在数值分析中用到迭代法的情形会比直接法要多。例如像牛顿法、二分法、雅可比法、广义最小残量方法（GMRES）及共轭梯度法等。在计算矩阵代数中，大型的问题一般会需要用迭代法来求解。许多时候需要将连续模型的问题转换为一个离散形式的问题，而离散形式的解可以近似原来的连续模型的解，此转换过程称为离散化。例如求一个函数的积分是一个连续模型的问题，也就是求一曲线以下的面积若将其离散化变成数值积分，就变成将上述面积用许多较简单的形状（如长方形、梯形）近似，因此只要求出这些形状的面积再相加即可。例如在二小时的赛车比赛中，记录了三个不同时间点的赛车速度，如下表利用离散化的方式，可以假设赛车在0:00到0:40之间的速度、0:40到1:20之间的速度及1:20到2:00之间的速度分别为三个定值，因此前40分钟的总位移可近似为(2/3h × 140 km/h) = 93.3 公里。可依此方式近似二小时内的总位移为93.3 公里 + 100 公里 + 120 公里 = 313.3 公里。位移是速度的积分，而上述的作法是用黎曼和进行数值积分的一个例子。误差是数值分析的重要主题之一。误差的形成可分为几种不同的原因。当进行数值分析的设备只能用有限位数来表示一个实数时，就会出现舍入误差（Round-off error），例如用可显示十位数字的计算器计算1/3，所得到的结果0.333333333，和实际数值的误差就是舍入误差。即使进行数值分析的设备用浮点数来表示实数，仍无法完全避免舍入误差的问题。若迭代法的数值分析算到某一程度就中止计算，或是使用一些近似的数学程序，程序所得结果和精准解不同，就会出现截尾（Truncation）误差。将问题离散化后，由于离散化问题的解不会和原问题的解完全一様，因此会出现离散化误差（英语：discretization error）。例如用迭代法计算 3 x 3 + 4 = 28 {displaystyle 3x^{3}+4=28} 的解，在计算几次后我们认为其解为1.99，就会有0.01的截尾误差。一旦有了误差，误差就会借着计算继续的扩散。例如一个计算机中的加法是不准的，则a+b+c+d+e的计算也一定不准。例如刚刚计算 3 x 3 + 4 = 28 {displaystyle 3x^{3}+4=28} 的解为1.99，若后续的运算需要用到 3 x 3 + 4 = 28 {displaystyle 3x^{3}+4=28} 的解，用1.99代入所得的结果也会不准。当用近似的方式处理数学式时就会出现截尾误差。以积分为例，完全精准的积分需要求出曲线下方无限个梯形的面积和，但用在数值分析中会用有限个梯形的面积和来近似无限个梯形的面积和，此时就会出现截尾误差。若要对一个函数进行微分，其微分量需要趋近于0，但实务上只能选择很小的微分量。非良置问题：考虑一函数f(x) = 1/(x − 1)，f(1.1) = 10，f(1.001) = 1000。当x只改变小于0.1的数值，f(x)的变化将近1000。因此在x = 1的附近计算f(x)是一个非良置的问题。良置问题：相反的，函数 f ( x ) = x {displaystyle f(x)={sqrt {x}}} 在x不接近0时，其值的计算就是一个良置的问题。数值稳定性是数值分析中一个重要的主题。若一算法中不论什么原因产生了误差，此误差不会在运算中明显增加，此算法为数值稳定的算法。若问题为良置（well-conditioned）的，就会符合上述的特性，也就是问题数据微小的变化只会造成其解的微小变化。相反的，若问题数据微小的变化会造成其解的巨大变化，会称问题为非良置或病态（ill-conditioned）。原始问题及求解问题算法都可以分为良置及非良置，任何的组合都是允许的。一个求解良置问题的算法可能是数值稳定的，也可能是数值不稳定的。数值分析的重点就是找到适定性问题的数值稳定算法。例如，计算2的平方根（大约是1.41421）本身是一个适定性问题。许多求解的算法都是从一个初始的近似值x1开始去求解，例如x1=1.4，再继续计算x2、x3等。巴比伦法就是一个具有此特性的算法。另一个方法，先称之为X方法，算法为xk + 1 = (xk2−2)2 + xk。以下分别用初始值 x1 = 1.4及x1 = 1.42，用二种方式进行几次迭代。可观察到不论初始值多少，巴比伦法都可以快速的收敛，但X方法在初始值为1.4时收敛的很慢，在初始值为1.42时X方法会发散。因此巴比伦法是数值稳定的方法，而X方法是数值不稳定的方法。数值分析依其待求解的问题不同，分为不同的领域。内插法：假设一点钟的气温为20度，三点钟时为14度，可以用线性内插法推测一点半及二点钟时的气温分别是18.5度及17度。外推法：假设某国家国内生产总值平均每年成长百分之五，去年国内生产总值为一百万元，可推测今年的国内生产总值为一百零五万元。回归分析：给定几个二维坐标上的点，回归分析就是设法找到一条最接近这些点的直线。最优化：有一个卖饮料的小贩，若每杯饮料100元，每天可以卖197杯饮料，若饮料单价增加1元，每天就会少卖1杯饮料。饮料定价为148.5元时，其每天的收入为最大值。不过由于饮料单价需为正整数，因此饮料定价可定为149元，对应每天的收入为22,052元。微分方程：假设在一房间中的不同位置放置一百个风扇，然后在房间中放置一根羽毛，羽毛会依房间中气流而移动，而房间中的气流可能相当复杂。不过每一秒量测一次羽毛附近空气的速度，假设羽毛下一秒是等速的直线运动，即可求得下一秒时羽毛的位置，再量测当时羽毛附近空气的速度，……。这种方法称为欧拉方法，常使用在常微分方程的数值分析。数值分析中最简单的问题就是求出函数在某一特定数值下的值。最直觉的方法是将数值代入函数中计算，不过有时此方式的效率不佳。像针对多项式函数的求值，较有效率的方式是秦九韶算法，可以减少乘法及加法的次数。若是使用浮点数，很重要的是是估计及控制舍入误差。内插法求解以下的问题：有一未知函数在一些特定位置下的值，求未知函数在已知数值的点之间某一点的值。外推法类似内插法，但需要知道数值的点是在其他已知数值点的范围以外。一般而言外推法的误差会大于内插法。曲线拟合是在已知一些数据的条件下，找到一条曲线完全符合现有的数据，数据可能是一些特定位置及其对应的值，也可能是其他资料，例如角度或曲率等。回归分析类似曲线拟合，也是根据一些特定位置及其对应的值，要找到对应曲线。但回归分析考虑到数据可能有误差，因此所得的的曲线不需要和数据完全符合。一般会使用最小方差法来进行回归分析。另一种常见的问题是求特定方程的解。首先会依方程是否线性来区分，例如方程 2 x + 5 = 3 {displaystyle 2x+5=3} 是线性方程，而 2 x 2 + 5 = 3 {displaystyle 2x^{2}+5=3} 是非线性方程。此领域许多的研究都和求解线性方程组有关。直接法是线性方程组的系数以矩阵来表示，再利用矩阵分解的方式求解，这些方法包括高斯消元法、LU分解，对于对称矩阵（或埃尔米特矩阵）及正定矩阵可以用乔莱斯基分解（英语：Cholesky decomposition），非方阵的矩阵则可以用QR分解。迭代法包括有雅可比法、高斯–塞德迭代法、逐次超松驰法（英语：successive over-relaxation）（SOR）及共轭梯度法，一般会用在大型的线性方程组中。求根算法是要解一非线性方程，其名称是因为函数的根就是使其值为零的点。若函数本身可微且其导数是已知的，可以用牛顿法求解，其他的方法包括二分法、割线法等。线性化（英语：Linearization）则是另一种求解非线性方程的方法。许多重要的问题可以用奇异值分解或特征分解来表示。例如有些图像压缩算法就是以奇异值分解为基础。统计学中对应的工具称为主成分分析。最优化问题的目的是要找到使特定目标函数有最大值（或最小值）的点，一般而言这个点需符合一些约束。依目标函数及约束条件的不同，最优化又可以再细分：例如线性规划处理目标函数及约束条件均为线性的情形，常用单纯形法来求解。若目标函数及约束条件其中有一项为非线性，就是非线性规划的范围。有约束条件的问题可以利用拉格朗日乘数转换为没有约束条件的问题。数值积分的目的是在求一定积分的值。一般常用牛顿－寇次公式，包括辛普森积分法、高斯求积等。上述方式是利用分治法来处理积分问题，也就是将大范围的积分切割成许多小范围的积分，再进行计算。不过在高维度时，上述作法可能会因为要作许多的计算而变得不实用（也就是维数之咒所描述的情形），此时可以采用蒙地卡罗方法或半蒙地卡罗方法。（可参照蒙地卡罗积分（英语：Monte Carlo integration），或是适用于高维度的稀疏网格（英语：sparse grid）法。）数值分析也会用近似的方式计算微分方程的解，包括常微分方程及偏微分方程。常微分方程往往会使用迭代法，已知曲线的一点，设法算出其斜率，找到下一点，再推出下一点的资料。欧拉方法是其中最简单的方式，较常使用的是龙格－库塔法。偏微分方程的数值分析解法一般都会先将问题离散化，转换成有限元素的次空间。可以透过有限元素法、有限差分法及有限域积法（英语：finite volume method），这些方法可将偏微分方程转换为代数方程，但其理论论证往往和泛函分析的定理有关。另一种偏微分方程的数值分析解法则是利用离散傅里叶变换或快速傅里叶变换。20世纪末，大部分数值分析的算法都已用许多不同的编程语言实现。Netlib（英语：Netlib）软件库包含了许多数值分析算法的程式，大部分是Fortran及C语言的程式。商业产品也实现了许多不同的数值分析算法，包括国际数学及统计程序库数字型档及英商纳格资讯（英语：Numerical Algorithms Group）软件库，GNU科学数值库则是自由软件的数值分析算法软件库。数值分析的商用应用程序包括MATLAB、S-PLUS（英语：S-PLUS）、LabVIEW及互动式数据语言（IDL）等，自由软件或开源软件的数值分析应用程序则包括FreeMat、Scilab、GNU Octave （类似Matlab）、IT++（C++函式库连 library）、R语言 （类似S-PLUS）及一些Python的衍生版本。各应用程序的性能有很大的差异：一般而言向量及矩阵的运算都很快，而各应用程序标量运算的速度差异则可能会超过10倍以上。许多计算机代数系统的软件（像Mathematica及Maple）由于使用无限精度算术的计算方式，可以得到比一般软件更准确的结果。电子试算表的软件也可以处理一些简单的数值分析问题。