1.6 问题的性态与条件数在线视频

今天我们介绍第六节

问题的性态与算法的数值稳定性

应用计算机解决实际问题

计算结果的精度与所解问题的性态

与算法的数值稳定性有密切关系

问题性态是数学本身的

固有属性与算法无关

算法的数值稳定性是指

算法控制误差的能力

本节就讨论这两个问题

首先我们来讨论问题的性态

一个数学问题可以分为良态与病态

若初始数据的微小变化

只引起计算结果的微小变化

这样的数学问题我们称之为良态

反之

若初始数据的微小变化

就引起计算结果的较大变化

则称问题是病态的

早在1963年气象学家洛伦兹

就提出了蝴蝶效应的概念

我们来看这幅图

所谓蝴蝶效应是指

南美洲亚马孙河流域的一只蝴蝶

扇动了几下翅膀就可能引起两周后

美国得克萨斯州的一场龙卷风

蝴蝶扇动翅膀意味着

初始条件产生了微小的变化

几周之后

在遥远的地方会引起一场龙卷风

也就是说

初始数据的微小变化

会引起结果的极大差异

蝴蝶效应就是病态问题的一种体现

我们再看几个例子

首先我们来看一个函数求值问题

P(x)=x2+x-1150

求P(x)在x=100/3.

与x=33处的函数值

我们带值计算分别求出

P（x)在x=100/3处的值

等于-50/9

约等于-5.6

而在33点的值等于-28

我们将100/3减33

发现两者之差小于0.34

而它们的计算结果负的5.6

减负的28所等于22.4

计算结果发生了较大变化

因此我们说

P(x)在100/33

这一点处的求值问题是病态的

我们对于同样的函数

换两个点来求值

考察P(x)在x=1

以及x=1.1处的函数值

那么通过计算分别求出

P(1)=-1148

P(1.1)=-1147.7

很显然

初始数据的微小变化

1-1.1=0.1

初始数据的变化很小

计算结果的变化也很小

P(1.1)-P(1)

它们的差也很小

这意味着

P(x)在x=1点的求值问题

是良态的

这个例子说明函数求值问题的性态

不仅与函数本身有关

还和点的位置有关

我们再从几何上

观察一下良态问题

与病态问题的特点

图中所给曲线

是P(x)等于x2+x-1150的图形

由图可见

在x=1附近图形比较平缓

而在X=33附近

图形较陡

因此良态求值问题

对应较平滑的函数图形

而病态求值问题

对应较陡的函数图形

我们看下面的例子

求解线性方程组

这是一个三元线性方程组

我们先把它的系数矩阵

用两位有效数字来表示

右端项也用两位有效数字来表示

那么我们的线性方程组就表示为

右侧的这样的一个

具有两位有效数字的线性方程组

求解右侧的线性方程组

我们得到了它的解

x1 x2 x3 的值

那么左侧这个线性方程组的

精确解是什么呢

我们看到它的精确解

是x1=x2=x3=1

很显然

两边的方程组的解相差甚远

这也表示

这个线性方程组的求解问题

是一个病态问题

那么如何量化问题的性态

我们下面给出这样的一段定义

设R为计算结果的相对误差

e为初始数据的相对误差

如果能找到一个正数m

使得R的绝对值

小于等于m乘以e的绝对值

或者R的绝对值

近似等于m乘以e的绝对值

那么这个数m

就是计算结果的相对误差

对初始数据的相对误差的

一个放大倍数

我们将数m

称为问题的条件数

记为cond.很显然

若问题是病态的

则条件数m就大

若问题是良态的

则条件数就小

不同的数学问题

条件数的表达式

也有所不同

下面我们就来考察一个

函数求值问题的条件数

设f(x）在[a b]上

有连续导数

计算f(x)在

p点的函数值

这里p属于[a b]

我们来推导一下

函数求值问题的条件数

那么这里初始数据就是p

计算结果是f(p)

我们用e来表示

初始数据的相对误差

等于dx比p

计算结果的相对误差R等于

f(p+dx)-f(p)

比上f(p)

下面我们来寻求R与e之间的关系

根据微分中值定理

f(p+dx)-f(p)

等于f'(P)乘以dx

这里ξ位于p与p+dx之间

根据已知条件

f'(x)是连续的

因此当dx很小时

我们可以假设f'(ξ)

近似的等于f'(p)

从而f(p+dx)减去

f(p)就约等于

f'(p)乘以dx

将这个式子带入

上面的R的表达式

我们就得到了R约等于

f'(p)乘以dx比上f(p)

那么为了让

初始数据的相对误差出现,我们分母

添一个p

同时分子

也增加一个p

两边取绝对值就得到下式

e的绝对值的系数

就是函数求值问题的条件数

我们将它记作cond(f)

cond(f)等于

p乘以f'(p)比上f(p)的绝对值

这样我们就建立了R

与初始数据相对误差e之间的一种关系式

那么近似号右侧的第一项

p乘以f'(p)

除以f(p)的绝对值

就是我们要寻求的

m, 也就是函数求值问题的条件数

下面我们再回到

例一例二两个问题中

分别算一下刚才两个问题的条件数

那么我们得到例一中的

条件数是406 比较大

例二中的条件数

等于2.6乘10的负3次方比较小

所以问题1是病态的

问题二是良态的

病态问题的求解

是一个很复杂的问题

本课程基本不做涉及