当前课程知识点：计算方法 > 第1章 计算方法概论 > 1.7 算法数值稳定性 > 1.7 算法数值稳定性
下面我们讨论算法的数值稳定性
什么是算法的数值稳定性呢
一个数值算法
若输入数据的误差
在计算过程中不增长
并对最终的结果影响不大
我们就称该算法是数值稳定的算法
否则称其为不稳定算法
如果一个算法
对某些数据是稳定的
那么我们称这个算法是
条件稳定算法
如果一个算法对任何数据
均是稳定的
我们称这个算法
是无条件稳定的算法
下面举个例子
在如上四位字长十进制的
计算机数系中求解二次方程
x2-320x+16=0
对一个二次方程
ax2+bx+c=0
我们给出下面两个求解公式
第一个公式就是我们
熟悉的二次方程求根公式
第二公式就是依据韦达定理
给出的求根公式
我们分别用这两个求根公式来求解
x2-320x+16=0
这个二次方程
采用公式1求解
我们得到了两个解
x1=0.3199
乘以10的3次方
x2等于0.1乘10
采用公式二求解
我们得到了x1
等于0.3199乘10的3次方
x2=0.5002
乘以10的负1次方
两个公式求出的解
的第一个变量x1是相同的
第二个变量是不同的
我们再来看精确解
精确解x1=319. 950
x2=0.0500078
相对比
我们发现公式2的解的精度更高
那么为什么公式1会产生误差
原因就在于在公式1中
b方远远的大于4ac
我们这里b是-320
b方远远的大于4ac
这个
4倍的ac相乘 等于64
所以导致相近数相减产生误差
一般的,求解二次方程
ax2+bx+c=0
我们说我们熟悉的求根公式
它是一个条件稳定的公式
它对于b2
远远地大于4ac的这样的一些数据
它是不稳定的
不满足这个不等式
它就是稳定的
所以是条件稳定
而公式2
对于所有的数据都是稳定的
所以公示2是无条件稳定的算法
如何量化算法的数值稳定性
我们给出下述定义
设E0是初始误差
En是算法n步之后的误差
若En近似等于
C倍的n乘以E0
C是常数
我们就称误差的增长是线性的
若En近似的等于
C的n次方乘以E0
C的n次方乘以E0
这里C的绝对值大于1
我们就称误差的增长是指数级的
当算法的误差增长是指数级的时候
它一定是不稳定的
下面我们考察一个例子
计算 如上定积分
被积函数是x的n次方比上x加5
积分区间是0到1
我们要依次计算
n取0, 1到23时
积分In的值
当n等于零的时候
我们可以直接计算
等于In6-In5
它是一个无穷多位的数
我们可以依次取n为1,2
一直算下去
随着n的增大
In的计算程度
也就越来越复杂
因此我们希望
推导一个递推公式来计算
我们将被积函数的分子
加上五倍的Xn-1
再减去五倍的Xn-1
将前两项合并提出Xn-1
那么 和分母就消掉了
这样我们就把
原积分
转化为n分之一
减去五倍的In-1
我们得到了这样的一个递推公式
从而构造了算法A
已知I0 求In
按照上面的递推公式
我们可以依次的算出I1
通过I1等于负的
五倍的I0加1来求出I1
然后再利用I2等于负的五倍的I1
加二分之一来求出I2. 以此类推
按照这个递推公式
我们得到了下面的计算结果
前两行是n取0到11的计算结果
后面两行
是n取12到23的计算结果
那么上述结果是否正确呢
我们再来看一下In的定义
由In的定义
我们发现
In应该是非负的
但是我们发现最后一行
已经出现了正负相间的情况
有正有负
因此这个结果一定是错误的
那么问题出现在哪呢
下面我们做一下误差分析
I0刚才我们直接计算
得出了它的精确值
0.182321556
省略后面
I0 (bar)是I0的近似值
等于0.18232
I 0与I0 (bar)的误差
我们记为E0, I0 (bar)是有限位
I0是无穷位
它们之间有误差 我们记为E0
类似的
用I0 (bar)
由递推式是我们算出了I1 (bar)
它和精确的I1
又产生了误差
我们记为e1
e1等于I1减去I1 (bar)
等于负的五倍的e0
一般的
我们In (bar)是In的近似
并设en等于
In减去In (bar)
那我们也导出了一个en的公式
en等于负的五倍的en减1
en等于负的五倍的en-1
等于负5的n次方乘以e0
大家看到,这个
公式告诉我们
误差的增长是指数级的
从而呢
算法A是不稳定的
因此计算结果是错误的
下面我们换一种算法
由算法A我们推出下面的算法B
注意一下算法B与算法A的区别
我们将In-1放在等号的左侧
将In放在等号的右侧
我们将n从大到小进行计算
首先给出I25一个估值
0.0071
然后我们采用这个递推公式
算出下面的计算结果
由n等于25开始算起
I25开始算起
算I24一直算到I0
我们发现最后I0的结果
0.1823 具有4位有效数字
那说明
这个算法B是数值稳定的
因为它的误差是指数衰减的
逐渐缩小
那么I25是怎么得到这个估值呢
我们由In的定义知道
知道这个In它是一个递减的数列
那我们可以导出
In-1大于等于6n分之1
小于等于5n分之1
这样我们就可以得到I25
大于等于6乘26分之1
小于等于5乘26分之1
将I25取左右两个数的算术平均值
我们就得到了I25的一个估值
从而就构造了算法B
从而就构造了算法B
这个例子告诉我们
尽管理论上很完美
如果在计算过程中
不能很好的控制误差
那么也会导致计算结果的失真
本节我们介绍了
问题的性态与算法的数值稳定性
用计算机解决实际问题
我们说计算结果
它的精度与问题的性态
与算法的数值稳定性有着密切的关系
-1.1 引言
--1.1 引言
-1.2 算法与效率
-1.3 计算机数系与浮点运算
-1.4 误差与有效数字
-1.5 四则运算与函数求值的误差
-1.6 问题的性态与条件数
-1.7 算法数值稳定性
-第1章 作业
--第一章 作业
-2.1 引言 2.2 线性空间
-2.3 内积空间与元素的夹角
-2.4 赋范线性空间
-2.5 向量范数与向量序列极限
-2.6 矩阵范数
--2.6 矩阵范数
-第二章 作业
--第二章 作业
-3.1 引言
--3.1 引言
-3.3 不动点迭代法
--3.2 二分法
-3.4 不动点迭代法的收敛条件
-3.5 牛顿迭代法及其变形
-3.6 迭代法收敛阶
-3.7 重根的计算与加速收敛
-3.8 数值实验
--3.8 数值实验
-第3章 作业
--第3章 作业
-4.1 引言
--4.1 引言
-4.2 Lagrange插值
-4.3 Lagrange插值余项
-4.4 Newton差商插值
-4.5 Hermite插值
-4.6 分段多项式插值
-4.7 三次样条插值
-4.8 数值实验
--4.8 数值实验
-第4章 作业
--第4章 作业
-5.1 函数逼近与曲线拟合基本概念
-5.2 连续函数的最佳平方逼近
-5.3 曲线拟合的最小二乘法
-第5章 作业
--第5章 作业
-6.1 引言 6.2 高斯消元法
-6.3 矩阵分解与应用
-6.4 误差分析 6.5 数值实验
-第6章 作业
--第6章 作业
-7.1 引言 7.2 线性方程组的迭代法（上）
-7.2 线性方程组的迭代法
-7.3 非线性方程组的迭代法
-7.4 数值实验
--7.4 数值实验
-第7章 作业
--第7章 作业
-8.1 引言
--8.1 引言
-8.2 幂法与反幂法
-8.3 矩阵的正交分解
-8.4 QR方法
--8.4 QR方法
-8.5 Jacobi方法
-第8章 作业
--第8章 作业
-9.1 引言
-9.2 牛顿-柯特斯公式
-9.3 复合牛顿-柯特斯公式
-9.4 龙贝格算法
-9.5 高斯型求积公式
-9.6 数值微分
--9.6 数值微分
-10.1 引言
--10.1 引言
-10.2 梯形公式和改进的欧拉方法
-10.3 单步法的误差与稳定性收敛性
-10.4 高阶单步方法
-10.5 线性多步法
-10.6 多步法的误差与稳定性
-10.7 一阶微分方程组与高阶微分方程
-第10章 作业
--第10章 作业
