之前一直想学数值分析，网上查阅了下，发现一个斯坦福的公开课还不错，讲义，作业，视频都有，所以决定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}$

但是很多小数会表示为循环小数，例如：

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

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 .”，原因是我们刚刚提到的问题。为了避免上述问题，我们应该使用如下代码：

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$的求根问题：

实际问题

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

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$，所以就可以避免溢出的问题，代码如下：

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，考虑累加法：

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

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

对应的代码如下：

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 ;
}