数值分析与科学计算导引——误差与算法举例

第一章 数值分析与科学计算导引

1.1 数值分析的对象、作用与特点

数值分析是数学的一个分支，以下是关于其对象、作用与特点的具体介绍：

数值分析的对象

数值分析主要研究的是如何利用计算机等工具，对各种数学问题进行数值求解。具体来说，其对象包括以下几类：

• 方程求解：涵盖代数方程和微分方程等。例如，求解一元二次方程(ax^{2}+bx + c = 0)的根，或者求解描述物理过程的偏微分方程，如热传导方程、波动方程等。
• 数值逼近：对于一些复杂的函数，难以直接进行计算和处理，需要用简单的函数（如多项式函数、三角函数等）来逼近。比如在计算机图形学中，用多项式曲线来逼近复杂的图形轮廓。
• 数值积分与微分：计算定积分的值以及函数的导数的数值近似。在物理中计算物体的质心、转动惯量等问题时，常需要进行数值积分；在分析信号的变化率等问题时，需要数值微分。
• 线性代数问题：像求解线性方程组(Ax = b)，其中(A)是系数矩阵，(x)是未知数向量，(b)是常数向量；以及求矩阵的特征值和特征向量等问题。在结构力学、电路分析等领域有广泛应用。

数值分析的作用

• 科学研究：在物理学、化学、天文学等学科中，许多问题无法得到精确的解析解，数值分析提供了一种有效的求解途径。比如在计算天体力学中行星的轨道时，通过数值方法可以得到满足一定精度要求的轨道数据。
• 工程技术：在航空航天、机械制造、电子工程等领域，数值分析用于设计和优化。例如在飞机机翼的设计中，通过数值模拟计算气流在机翼表面的流动情况，以优化机翼的形状和结构。
• 经济金融：用于风险评估、投资组合优化、期权定价等。如利用数值方法求解布莱克-斯科尔斯期权定价模型，为金融市场的交易和风险管理提供重要依据。
• 数据分析与处理：在大数据时代，数值分析在数据拟合、数据插值、数据压缩等方面发挥着重要作用。例如在气象数据处理中，通过数值方法对离散的气象观测数据进行插值和拟合，得到连续的气象场分布。

数值分析的特点

• 近似性：由于计算机的字长有限等原因，数值分析得到的结果通常是近似解。例如对无理数(\pi)，在计算机中只能用有限位小数来表示，计算结果必然存在一定的误差。
• 递推性：很多数值算法都采用递推的方式进行计算，通过已知的结果逐步推出后续的结果。如在计算斐波那契数列时，利用(F(n)=F(n - 1)+F(n - 2))的递推关系，从初始值(F(0)=0)，(F(1)=1)开始逐步计算出后续的项。
• 稳定性：数值算法的稳定性至关重要，如果一个算法在计算过程中对初始数据的微小扰动非常敏感，导致结果出现很大偏差，那么这个算法就是不稳定的。例如在求解线性方程组时，有的算法可能因为系数矩阵的某些特性而出现数值不稳定的情况。
• 高效性：需要在有限的时间和计算资源下得到满足精度要求的结果。因此，设计高效的算法是数值分析的重要任务之一。比如在矩阵乘法中，Strassen算法通过分治思想，减少了乘法运算的次数，提高了计算效率。

1.2 数值计算的误差

误差分类

误差与有效数字

绝对误差：简称误差,设$x$为准确值，$x^{\ast }$为$x$的一个近似值,称$e^{\ast }=x^{\ast }-x$为绝对误差。
绝对误差限：$|e^{\ast }|=|x^{\ast }-x|⩽ϵ(x^{\ast })$,$ϵ(x^{\ast })$称绝对误差限。
相对误差：$e_r^{\ast }=\frac{x^{\ast }-x}{x^{\ast }}=\frac{e^{\ast }}{x^{\ast }}$
相对误差限：$|{ϵ}_r(x^{\ast })|=|\frac{ϵ(x^{\ast })}{x^{\ast }}$|
有效数字：若近似值$x^{\ast }$的误差限是一位的半个单位，该位到$x^{\ast }$的第一位非零数字共$n$位，就说$x^{\ast }$有$n$位有效数字。
相对误差比值：$|\frac{x{f}^{{}^{\prime }}}{f}|$

• 容易得到以下定理：

1. 四舍五入得到的数据，其有效位数的确定方法如下：从左边第一个非零数字起，到末位数字止，所有的数字，包括$0$，都是这个数的有效数字。
2. 设近似数$x^{\ast }$表示为：
   $$x^{\ast }=\pm 10^m(\sum _{i=1}^l{a}_i\times 10^{-l+1})$$
   且$x^{\ast }$具有$n$位有效数字，则其相对误差限满足以下关系：${ϵ}_r(x^{\ast })⩽\frac{1}{2a_1}\times 10^{-(n-1)}$。
3. ${ϵ}_r(x^{\ast })⩽\frac{1}{2(a_1+1)}\times 10^{-(n-1)}$,则$x^{\ast }$至少具有$n$位有效数字。

数值运算的误差估计

$$ϵ(\sum _{i=1}^n(\pm )x_i^{\ast })⩽\sum _{i=1}^nϵ(x_i^{\ast })$$
$$ϵ(\prod _{i=1}^n{x}_i^{\ast })⩽\sum _{j=1}^n(ϵ(x_j^{\ast })\prod _{i=1,i\ne j}^n|x_i^{\ast }|)$$
$${ϵ}_{(}f(x^{\ast }))=|\frac{df(x^{\ast })}{dx}|ϵ(x^{\ast })$$
$$ϵ(f(x^{\ast },y^{\ast }))\approx \sqrt{{\left(\frac{\partial f}{\partial x}\right)}^2{ϵ}^2(x^{\ast })+{\left(\frac{\partial f}{\partial y}\right)}^2{ϵ}^2(y^{\ast })}$$

1.3 算法举例

秦九韶算法求多项式值

开根号迭代算法

牛顿切线

加权平均的松弛技术