数值分析与科学计算导引——误差与算法举例
文章目录
- 第一章 数值分析与科学计算导引
- 1.1 数值分析的对象、作用与特点
- 数值分析的对象
- 数值分析的作用
- 数值分析的特点
- 1.2 数值计算的误差
- 误差分类
- 误差与有效数字
- 数值运算的误差估计
- 1.3 算法举例
- 秦九韶算法求多项式值
- 开根号迭代算法
- 牛顿切线
- 加权平均的松弛技术
第一章 数值分析与科学计算导引
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
x为准确值，
x
∗
x^*
x∗为
x
x
x的一个近似值,称
e
∗
=
x
∗
−
x
e^*=x^*-x
e∗=x∗−x为绝对误差。
绝对误差限：
∣
e
∗
∣
=
∣
x
∗
−
x
∣
⩽
ϵ
(
x
∗
)
|e^*|=|x^*-x|\leqslant\epsilon(x^*)
∣e∗∣=∣x∗−x∣⩽ϵ(x∗),
ϵ
(
x
∗
)
\epsilon(x^*)
ϵ(x∗)称绝对误差限。
相对误差：
e
r
∗
=
x
∗
−
x
x
∗
=
e
∗
x
∗
e_{r}^{*}=\frac{x^*-x}{x^*}=\frac{e^*}{x^*}
er∗=x∗x∗−x=x∗e∗
相对误差限：
∣
ϵ
r
(
x
∗
)
∣
=
∣
ϵ
(
x
∗
)
x
∗
|\epsilon_r(x^*)|=|\frac{\epsilon(x^*)}{x^*}
∣ϵr(x∗)∣=∣x∗ϵ(x∗)|
有效数字：若近似值
x
∗
x^*
x∗的误差限是一位的半个单位，该位到
x
∗
x^*
x∗的第一位非零数字共
n
n
n位，就说
x
∗
x^*
x∗有
n
n
n位有效数字。
相对误差比值：
∣
x
f
′
f
∣
|\frac{xf^{'}}{f}|
∣fxf′∣
- 容易得到以下定理：
- 四舍五入得到的数据，其有效位数的确定方法如下：从左边第一个非零数字起，到末位数字止，所有的数字，包括 0 0 0，都是这个数的有效数字。
- 设近似数
x
∗
x^*
x∗表示为：
x ∗ = ± 1 0 m ( ∑ i = 1 l a i × 1 0 − l + 1 ) x^*=\pm10^m(\sum_{i=1}^{l}a_i\times10^{-l+1}) x∗=±10m(i=1∑lai×10−l+1)
且 x ∗ x^* x∗具有 n n n位有效数字，则其相对误差限满足以下关系： ϵ r ( x ∗ ) ⩽ 1 2 a 1 × 1 0 − ( n − 1 ) \epsilon_r(x^*)\leqslant\frac{1}{2a_1}\times10^{-(n - 1)} ϵr(x∗)⩽2a11×10−(n−1)。 - ϵ r ( x ∗ ) ⩽ 1 2 ( a 1 + 1 ) × 1 0 − ( n − 1 ) \epsilon_r(x^*)\leqslant\frac{1}{2(a_1+1)}\times10^{-(n - 1)} ϵr(x∗)⩽2(a1+1)1×10−(n−1),则 x ∗ x^* x∗至少具有 n n n位有效数字。
数值运算的误差估计
ϵ ( ∑ i = 1 n ( ± ) x i ∗ ) ⩽ ∑ i = 1 n ϵ ( x i ∗ ) \epsilon(\sum_{i=1}^{n}(\pm)x_{i}^{*})\leqslant\sum_{i=1}^{n}\epsilon(x_{i}^{*}) ϵ(i=1∑n(±)xi∗)⩽i=1∑nϵ(xi∗)
ϵ ( ∏ i = 1 n x i ∗ ) ⩽ ∑ j = 1 n ( ϵ ( x j ∗ ) ∏ i = 1 , i ≠ j n ∣ x i ∗ ∣ ) \epsilon(\prod_{i=1}^{n}x_{i}^{*})\leqslant\sum_{j=1}^{n}(\epsilon(x_{j}^{*})\prod_{i=1,i\neq j}^{n}|x_{i}^{*}|) ϵ(i=1∏nxi∗)⩽j=1∑n(ϵ(xj∗)i=1,i=j∏n∣xi∗∣)
ϵ ( f ( x ∗ ) ) = ∣ d f ( x ∗ ) d x ∣ ϵ ( x ∗ ) \epsilon_(f(x^*))=|\frac{df(x^*)}{dx}|\epsilon(x^{*}) ϵ(f(x∗))=∣dxdf(x∗)∣ϵ(x∗)
ϵ ( f ( x ∗ , y ∗ ) ) ≈ ( ∂ f ∂ x ) 2 ϵ 2 ( x ∗ ) + ( ∂ f ∂ y ) 2 ϵ 2 ( y ∗ ) \epsilon(f(x^*, y^*))\approx\sqrt{\left(\frac{\partial f}{\partial x}\right)^2\epsilon^2(x^*)+\left(\frac{\partial f}{\partial y}\right)^2\epsilon^2(y^*)} ϵ(f(x∗,y∗))≈(∂x∂f)2ϵ2(x∗)+(∂y∂f)2ϵ2(y∗)