《Numerical Recipes》是一本讲数值算法的书。这本书的第二版,作者根据不同的编程语言,提供了这本书的好几个版本,如《Numerical Recipes in C++》,《Numerical Recipes in Matlab》,《Numerical Recipes in Fortran》等。中文《C++数值算法》是这本书C++版本的翻译版。本书的第三版似乎只提供了C++版本。
这本书的内容包括:
- 线性代数方程组求解
- 内插法和外推法
- 函数积分
- 函数求值
- 特殊函数
- 随机数
- 排序
- 求根和非线性方程组
- 函数的极值
- 特征系统
- 快速傅里叶变换
- 傅里叶和谱应用
- 数据的统计描述
- 数据建模
- 分类和推断(不知道翻译的对不对,看到再改)
- 常微分方程组的积分
- 两点边值问题
- 积分方程和反演理论
- 偏微分方程
- 计算几何
- 非典型的数值算法
本人打算系统的把这本书学一遍,相应的知识逐渐记录到这个博客里。
下面说明一下本书的基本约定和其他一些琐碎的东西。
本书制定了一些基础的数据类,如矩阵类,向量类等,这些类都是以模板的形式提供的。同时本书定义了一些基础的数据类型,包括指定类型的矩阵类,向量类等。根据不同的使用目的,重命名成不同的名字,如VecInt_I,VecInt,VecInt_O,VecInt_IO分别表示常数型整形向量,整形向量,在函数参数中用来保存输出结果的整形向量,用来给函数传递数据并保存输出结果的整形向量。其中后三种背后实际上是同一种类型,使用不同的名字只是为了方便阅读代码时的理解。C++的基础数据类型也都被重新命名,如int
型被重命名乘Int
,double
->Doub
。在些代码时尽量不要使用编程语言的内置数据类型,这样在需要修改数据类型时,只需要修改头文件就行。
本书中返回矩阵的函数几乎都是写成void的形式,真正的返回值放在函数的参数项上,引用形式。作者说这主要是为了防止额外的复制。因为有些编译器在把函数返回的临时变量赋值给相应的左值变量时,会发生额外的复制。白白浪费效率。这一点不知道现在是否还存在。我特意写过简单的类,用来检测是否会发生额外复制的情况。g++编译的结果是,这种情况没有发生。尤其现在C++11强调避免不必要的额外复制,特别定义了右值引用,转移的相关语法,按说这种情况不会发生。如果确实担心额外的复制浪费资源的话,底层的数据存储实际上可以用TNT来做,TNT的array实际上存储的只是一个智能指针,即使发生额外复制的话,也只是多复制了一次指针,对性能应该不会产生太大影响。当然作者这么写,我们就这么看吧。
关于浮点型的计算机内部实现:
在浮点表示中,一个数由一个符号位s,一个整指数E和一个正的整尾数M组成:
$$S\times M\times b^{E-e}$$其中b一般是2,e是指数的偏移量,在特定的机器上是一个常数。现代计算机一般遵守IEEE标准,对这些细节都有规定。浮点型的存储格式如下表:
S | E | F | Value | |
float | any | 1-254 | any | $${\left(-1\right)}^S\times 2^{E-127}\times 1.F$$ |
any | 0 | nonzero | $${\left(-1\right)}^S\times 2^{E-127}\times 0.F\ast$$ | |
0 | 0 | 0 | +0.0 | |
1 | 0 | 0 | -0.0 | |
0 | 255 | 0 | +∞ | |
1 | 255 | 0 | -∞ | |
any | 255 | nonzero | NaN | |
double | any | 1-2046 | any | $${\left(-1\right)}^S\times 2^{E-1023}\times 1.F$$ |
any | 0 | nonzero | $${\left(-1\right)}^S\times 2^{E-1022}\times 0.F\ast$$ | |
0 | 0 | 0 | +0.0 | |
1 | 0 | 0 | -0.0 | |
0 | 2047 | 0 | +∞ | |
1 | 2047 | 0 | -∞ | |
any | 2047 | nonzero | NaN | |
*unnormalized values |
下面是一个浮点数的例子:
$$0\ 01111111111\ 1000 (+ 48 more\ zeros) = +1 \times 2^{1023-1023} \times 1.1_2 = 1.5$$
舍入误差和截断误差
舍入误差是针对浮点型来讲的。整形如果不溢出的话,都是精确运算。按照本书所讲,浮点型在进行加减运算的时候,要先对较小数的尾数进行移位,以使指数位部分相同,然后对尾数部分进行加减运算。如果进行运算的两个数差别太大的话,尾数部分就需要移动很多位,一部分甚至全部的有效尾数数据会因为移出存储空间而被舍去。因此而造成的运算误差被称为舍入误差(不知道乘除运算是怎样进行的。)一般认为舍入误差是随机的,但实际上在一些情况下会偏向一个方向,甚至有一些算法在极端情况下会严重放大舍入误差。
截断误差是指由于计算机运算的不连续性导致的误差,是由算法产生的误差。比如在用数值方法显式求解微分方程时,我们总要选取一定步长,导数变化的一阶小量会被舍去,由此造成的误差称为截断误差。即使计算机运算的精度是无限高,截断误差依然存在,这是由算法造成的。
一般认为舍入误差和截断误差是相互独立的。
其他
C++自带的vector,取值函数有at()和重载的[]运算符。其中at进行边界检查,[]不进行边界检查。
Visits: 1148