CS205A Lecture 1 Introduction; numerics; error analysis

之前一直想学数值分析,网上查阅了下,发现一个斯坦福的公开课还不错,讲义,作业,视频都有,所以决定10周时间学完,后续会做一些笔记。

课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第一讲,这一讲主要介绍数值分析的基本概念。

Chapter 1 数值与误差分析

存储带小数的数字

计算机中的数字都是以二进制形式存储,例如$463$可以表示为:

表格的形式如下:

$1$ $1$ $1$ $0$ $0$ $1$ $1$ $1$ $1$
$2^8$ $2^7$ $2^6$ $2^5$ $2^4$ $2^3$ $2^2$ $2^1$ $2^0$

小数也同理,只要加上$2^{-n}$次方即可,例如$463.25$:

$1$ $1$ $1$ $0$ $0$ $1$ $1$ $1$ $1.$ $0$ $1$
$2^8$ $2^7$ $2^6$ $2^5$ $2^4$ $2^3$ $2^2$ $2^1$ $2^0$ $2^{-1}$ $2^{-2}$

但是很多小数会表示为循环小数,例如:

这种形式的小数无法用有限二进制字符串表示,所以在计算机中的计算就会有近似的问题,考虑如下代码:

1
2
3
4
double x = 1.0;
double y = x / 3.0;
if (x == y *3.0) cout << " They are equal !";
else cout << " They are NOT equal .";

从数学上来说,上述结果应该输出” They are equal !”,但实际上会输出” They are NOT equal .”,原因是我们刚刚提到的问题。为了避免上述问题,我们应该使用如下代码:

1
2
3
4
double x = 1.0;
double y = x / 3.0;
if ( fabs (x-y *3.0) < numeric_limits < double >:: epsilon ) cout << " They are equal !";
else cout << " They are NOT equal .";

接下来讨论几种表示数的方式。

定点数表示

定点数的存储方式很简单,我们存储从$2^{-k}$到$2^l$之间的$2$的幂对应的$0/1$系数,其中$k,l \in \mathbb N$。对$127.75$来说,$k=2, l=7​$。定点数存储的优势在于可以使用整数的加减法对其运算,例如

但是定点数的精度是一个很大的问题,如果我们只有一个小数点的精度($k=1$),那么对于

我们会将其近似为

这就会产生很大的误差。

浮点数表示

浮点数表示的想法源于科学计数法,我们定义如下参数:

  • 基数$\beta \in \mathbb N$,对于常见的科学计数法,$\beta =10$。
  • 精度$p \in \mathbb N​$表示十进制中的小数点的位数。
  • 指数范围$[L,U]$代表$b​$的可能值。

那么浮点数表示如下:

其中$d_{k}\in [0,\beta-1], b\in [L,U]$。注意浮点数的间隔是不均匀的,这是因为通常我们有

我们还定义机器精度为最小的$\epsilon_m >0$,使得$1+\epsilon_m$可以表示。

其他

其他表示方式使用的较少,这里稍作介绍,例如用整数对$(a,b)​$表示有理数,定义加法和加法和除法:

还有一种比较有用的表示方式为$(a,\epsilon ),a,\epsilon \in \mathbb R$,其中$a$表示真值,$\epsilon $表示误差。可以理解为$(a,\epsilon )$表示范围$(a-\epsilon ,a+\epsilon)$,注意此时加减法时要同时更新误差:

理解误差

计算过程中有很多误差,常见的误差形式如下:

  • 截断误差
  • 离散化误差
  • 建模误差
  • 经验常数
  • 用户输入

更具体的介绍可以参考讲义。

误差分类

考虑如下例子:

虽然都是$0.01$的误差,但是显然后者的影响更小,这就引入了绝对误差和相对误差的概念:

  • 绝对误差:测量的绝对误差是近似值与其真值之间的差值。
  • 相对误差:测量的相对误差是绝对误差除以真值。

不过在绝大多数情况下,真值都不知道(否则无需测量),解决方式是进行估计。

为了介绍后面的内容,考虑求根问题:

在实际处理中,假设我们找到$x$,因为我们不知道根,所以我们只能根据$|f(x)|$有多小来判断$x$是否接近根,这就引入了后向误差的概念:

  • 向后误差:Backward error is given by the amount a problem statement would have to change to realize a given approximation of its solution.

这段话比较难翻译,大意就是可以通过一个间接问题来估计原来的误差,例如之前的例子,我们很难估计$|x’-x|​$,但是$|f(x)|​$就很好计算。再来看一个例子,考虑$\sqrt x​$的计算,我们要判断$1.4​$是否接近$\sqrt 2​$,此处向后误差为:

与之相对应的,直接计算$|x- x’|$被称为向前误差

敏感性

因为有时候很小的向后误差并不能保证很小的向前误差,这就引出了条件数的概念:

  • 条件数:微小扰动下向前误差的改变量和向后误差的改变量的比值。

来看一个例子,考虑一元函数$f(x)=0$的求根问题:

实际问题

实际中经常会碰到数值溢出的问题,例如下面计算向量范数的问题:

1
2
3
4
double normSquared = 0;
for (int i = 0; i < n; i++)
normSquared += x[i]*x[i];
return sqrt ( normSquared );

如果$n$很大,那么求平方和时就会溢出,一个改进方法是使用如下事实:

因为$|\frac{x_i} M| \le 1$,所以就可以避免溢出的问题,代码如下:

1
2
3
4
5
6
7
8
double maxElement = epsilon ; // don 't want to divide by zero !
for (int i = 0; i < n; i++)
maxElement = max( maxElement , fabs (x[i ]));
for (int i = 0; i < n; i++) {
double scaled = x[i] / maxElement ;
normSquared += scaled * scaled ;
}
return sqrt ( normSquared ) * maxElement ;

实际中还有一个比较重要的算法为Kahan summation,考虑累加法:

1
2
3
double sum = 0;
for (int i = 0; i < n; i++)
sum += x[i];

当$n$很大时,sum会变得非常大,以至于加上x[i]不变(因为精度为题),从而会产生较大的误差,Kahan summation的思路是考虑累加时产生的误差:

对应的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double sum = 0;
double compensation = 0; // an approximation of the error

for (int i = 0; i < n; i++) {
// try to add back to both x[i] and the missing part
double nextTerm = x[i] + compensation ;

// compute the summation result of this iteration
double nextSum = sum + nextTerm ;

// compute the compensation as the difference between the term you wished
// to add and the actual result
compensation = nextTerm - ( nextSum - sum );

sum = nextSum ;
}

本文标题:CS205A Lecture 1 Introduction; numerics; error analysis

文章作者:Doraemonzzz

发布时间:2019年03月16日 - 21:19:00

最后更新:2019年03月19日 - 01:06:57

原始链接:http://doraemonzzz.com/2019/03/16/CS205A Lecture 1 Introduction; numerics; error analysis/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。