数值分析(numerical analysis),为
数学的一个
分支,是研究分析用计算机求解数学计算问题的数值计算方法及其理论的学科。它以
数字计算机求解数学问题的理论和方法为研究对象,为
计算数学的主体部分。
简介
数值分析的目的是设计及分析一些计算的方式,可针对一些问题得到近似但够精确的结果。以下是一些会用利用数值分析处理的问题:
直接法迭代法
直接法利用固定次数的步骤求出问题的解。这些方式包括求解
线性方程组的
高斯消去法及QR算法,求解
线性规划的单纯形法等。若利用无限精度算术的计算方式,有些问题可以得到其精确的解。不过有些问题不存在
解析解(如
五次方程),也就无法用直接法求解。在电脑中会使用
浮点数进行运算,在假设运算方式
稳定的前提下,所求得的结果可以视为是精确解的近似值。
迭代法是通过从一个初始估计出发寻找一系列
近似解来解决问题的数学过程。和直接法不同,用迭代法求解问题时,其步骤没有固定的次数,而且只能求得问题的近似解,所找到的一系列近似解会
收敛到问题的精确解。会利用审敛法来判别所得到的近似解是否会
收敛。一般而言,即使使用无限精度算术的计算方式,迭代法也无法在有限次数内得到问题的精确解。
在数值分析中用到迭代法的情形会比直接法要多。例如像
牛顿法、
二分法、雅可比法、广义最小残量方法(GMRES)及
共轭梯度法等等。在计算矩阵代数中,大型的问题一般会需要用迭代法来求解。
离散化
许多时候需要将连续模型的问题转换为一个离散形式的问题,而离散形式的解可以近似原来的连续模型的解,此转换过程称为
离散化。例如求一个函数的积分是一个连续模型的问题,也就是求一
曲线以下的面积若将其离散化变成
数值积分,就变成将上述面积用许多较简单的形状(如长方形、梯形)近似,因此只要求出这些形状的面积再相加即可。
例如在二小时的赛车比赛中,记录了三个不同时间点的赛车速度,如下表:
利用离散化的方式,可以假设赛车在0:00到0:40之间的速度、0:40到1:20之间的速度及1:20到2:00之间的速度分别为三个定值,因此前40分钟的总位移可近似为(2/3h×140km/h)=93.3公里。可依此方式近似二小时内的总位移为93.3公里 + 100公里 + 120公里 = 313.3公里。位移是速度的
积分,而上述的作法是用
黎曼和进行数值积分的一个例子。
误差
误差是数值分析的重要主题之一。误差的形成可分为几种不同的原因。
舍入误差
当进行数值分析的设备只能用有限位数来表示一个
实数时,就会出现
舍入误差(Round-off error),例如用可显示十位数字的
计算器计算1/3,所得到的结果0.333333333,和实际数值的误差就是舍入误差。即使进行数值分析的设备用浮点数来表示实数,仍无法完全避免舍入误差的问题。
离散化误差
若迭代法的数值分析算到某一程度就中止计算,或是使用一些近似的数学程序,程序所得结果和精准解不同,就会出现
截尾(Truncation)误差。将问题
离散化后,由于离散化问题的解不会和原问题的解完全一様,因此会出现离散化误差。例如用迭代法计算 3x3+4=28的解,在计算几次后我们认为其解为1.99,就会有0.01的截尾误差。
一旦有了误差,误差就会借着计算继续的扩散。例如一个计算机中的加法是不准的,则a+b+c+d+e的计算也一定不准。例如刚刚计算3x+4=28的解为1.99,若后续的运算需要用到3x+4=28的解,用1.99代入所得的结果也会不准。当用近似的方式处理数学式时就会出现截尾误差。
以积分为例,完全精准的积分需要求出曲线下方无限个梯形的面积和,但用在数值分析中会用有限个梯形的面积和来近似无限个梯形的面积和,此时就会出现截尾误差。若要对一个函数进行微分,其微分量需要趋近于0,但实务上只能选择很小的微分量。
领域研究
数值分析依其待求解的问题不同,分为不同的领域。
函数求值
数值分析中最简单的问题就是求出函数在某一特定数值下的值。最直觉的方法是将数值代入函数中计算,不过有时此方式的效率不佳。像针对
多项式函数的求值,较有效率的方式是
秦九韶算法,可以减少乘法及加法的次数。若是使用
浮点数,很重要的是是估计及控制舍入误差。
求解方程
另一种常见的问题是求特定方程式的解。首先会依方程式是否线性来区分,例如方程式 2x+5=3是线性方程式,而2x25=3是非线性方程式。此领域许多的研究都和求解
线性方程组有关。直接法是线性方程组的系数以矩阵来表示,再利用矩阵分解的方式求解,这些方法包括
高斯消去法、LU分解,对于对称矩阵(或埃尔米特矩阵)及正定矩阵可以用乔莱斯基分解,非方阵的矩阵则可以用QR分解。迭代法包括有雅可比法、高斯–塞德迭代法、逐次超松驰法(SOR)及
共轭梯度法,一般会用在大型的线性方程组中。
求根算法是要解一
非线性方程,其名称是因为函数的根就是使其值为零的点。若函数本身
可微且其导数是已知的,可以用
牛顿法求解,其他的方法包括
二分法、割线法等。线性化则是另一种求解非线性方程的方法。
求解特征值
许多重要的问题可以用
奇异值分解或
特征分解来表示。例如有些
图像压缩算法就是以奇异值分解为基础。统计学中对应的工具称为
主成分分析。
最优化
最优化问题的目的是要找到使特定目标函数有最大值(或最小值)的点,一般而言这个点需符合一些约束。
依目标函数及约束条件的不同,最佳化又可以再细分:例如
线性规划处理目标函数及约束条件均为线性的情形,常用
单纯形法来求解。若目标函数及约束条件其中有一项为非线性,就是
非线性规划的范围。
有约束条件的问题可以利用拉格朗日乘数转换为没有约束条件的问题。
积分计算
数值积分的目的是在求一
定积分的值。一般常用牛顿-寇次公式,包括辛普森积分法、高斯求积等。上述方式是利用分治法来处理积分问题,也就是将大范围的积分切割成许多小范围的积分,再进行计算。不过在高维度时,上述作法可能会因为要作许多的计算而变得不实用(也就是维数之咒所描述的情形),此时可以采用蒙地卡罗方法或半蒙地卡罗方法。(可参照蒙地卡罗积分,或是适用于高维度的稀疏网格法。)
微分方程
数值分析也会用近似的方式计算微分方程的解,包括
常微分方程及
偏微分方程。
常微分方程往往会使用迭代法,已知曲线的一点,设法算出其斜率,找到下一点,再推出下一点的资料。欧拉方法是其中最简单的方式,较常使用的是龙格-库塔法。
偏微分方程的数值分析解法一般都会先将问题离散化,转换成有限元素的次空间。可以透过
有限元素法、
有限差分法及
有限体积法,这些方法可将偏微分方程转换为代数方程,但其理论论证往往和泛函分析的定理有关。另一种偏微分方程的数值分析解法则是利用离散傅立叶变换或
快速傅立叶变换。