绪论

数值分析Numerical Analysis研究数值求解各类数学问题的方法和相应的数学理论，研究的对象是数学问题，所用的方法是数学方法，因此也称为数值数学（Numerical Mathematics）

数值分析研究的内容可以划分为以下几个主要方面：

• 数值代数： 主要包括线性代数方程组和非线性方程与方程组的数值解法，特征值与特征向量的数值计算等内容
• 数值逼近： 主要包括函数逼近、数值微分和数值积分等内容
• 常微分方程与动力系统的数值解法
• 偏微分方程的数值解法
• 最优化理论和方法，主要研究在一定的约束条件下如何选取某些因素的值，使某项或者某几个指标达到最优
• 误差理论： 主要研究近似方法的误差（即数值结果与原问题精确解之间的误差）以及影响误差的主要因素，因为每一中数值方法严格说来都是近似方法，这是数值分析中非常重要的一个问题。

数值方法的特点

求解一个数学问题的数值方法就是要给出该问题的一个近似的数值结果，因此，首先数值结果就要能算的出来，其次结果应有一定额精度，满足实际问题的要求，一般要求误差满足制定的值$\epsilon$,最后，计算时间应该尽可能的少

求解一个数学问题一般会有多种数值方法，在保证所需精度的条件下，计算时间越少的数值方法越好，对串行机而言，这相当于计算量越少越好。

例1-1 考虑求解线性代数方程组$Ax = b$,其中系数矩阵A是$n \times n$的方阵个，其行列式D$\equiv \detA \neq 0$
按照克拉默（Cramer）法则，则解为$x_i = D_i / D$
每个行列式按照Laplace展开计算，这就给给出额一个求解例1-1的数值方法，下面分析该算法的计算量，$x_i = D_i / D$共需计算$n + 1$个行列式，用laplace展开计算n阶行列式，约需要$n!$次乘法，这样，不计加法，该算法共需要$n + 1n! = n+1!$以上的乘法，对于一个20阶的方程组，就需要$20! \approx 5.11 * 10^{19}$次以上的乘法，设用每秒可做亿次乘法的计算机，一年可以做$365 \times 24 \times 3600 \times 10^8 \approx 3.15 \times 10^{15}$次乘法，所以用此计算机上用克拉默法则求解20阶的线性方程组，需要的时间在$5.11 \times 10^{19} \div 3.15 \times 10^{15} \approx 1.62 \times 10^4 = 1.62$万年以上
而使用高斯（Gauss）消元法求解，乘除的运算次数不超过3074次，与克拉默法则比较运算量有天壤之别，方程组的阶数增大，运算量的差别还会更大。

一个数值方法一般包括若干计算公式，递推化是许多计算公式采取的形式，其基本思想是将一个相对复杂的计算你过程归结为简单过程的多次重复，而这次计算机上是可以通过循环来实现

例1-2 考虑对于给定的$x$计算多项式$Px = a_0x^n + a_1x^{n-1} + \cdots + a_{n-1}x + a_n$的值

可以将它改写成等价形式
$$Px = a_0x^{n-1} + a_1x^{n-2} + \cdots a_{n-2}x + a_{n-1}x + a_n \\\qquad \qquad \qquad \quad = a_0x^{n-2} + a_1x^{n-3} + \cdots a_{n-3}x + a_{n-2}x + a_{n-1}x + a_n \\\qquad \quad = \cdotsa_0x + a_1x + a_2x + \cdots + a_{n-1}x + a_n$$
就可以得到递推公式
$v_0 = a_0$
$v_k = xv_{k-1} + a_k$
$vn = P_nx$
这一算法被称为霍纳（Horner）算法,我们也称为秦九韶算法。

例1-3 计算积分$\int_0^1x^ne^{x-1}dx$

解 利用分部积分公式，可以得到递推关系$I_n = 1 - nI_{n-1}$

数制

一个数通常写成$A = d_nd_{n-1}d_{n-2}\cdots d_1d_0.d_{-1}d_{-2}\cdots d_{-m},$ 此时$0 \leq d_j \leq 9$且$d_j$为整数$A = \sum_{-m}^n d_j 10^{j-1}$这是十进制数的表达，
计算机内部采用的进制不是十进制而是二进制、八进制等。$$A = \sum_{-m}^n d_j k^{j-1}, k=\set{2,8, \cdots}$$

浮点数

任意一个实数$x$,可以用整数部分加小数部分来表示，也可以表示为$x=s \times 10^k$

误差

数值计算式近似求解数学模型，误差是不可避免的，数学模型是由自然现象或社会现象归结出的，但与实际的自然现象或社会现象又有差别，这种差别称为模型误差，进行数值计算自然要考虑这一误差，要求数值计算的精度高于模型误差是没有意义的。

绝对误差、相对误差

设$x$是数$\dot{x}$的近似值，误差$x - \dot{x}$的具体数值通常是无法确定的，但可以设法给出其绝对值的一个上界$x - \dot{x} = \epsilon \leq E$,称$\epsilon = x - \dot{x}$为$\dot{x}$的近似值$x$的绝对误差，$E$为绝对误差限
记$\delta = \frac{x - \dot{x} }{x}$,称$\delta$为近似值$x$的相对误差，若$\frac{x - \dot{x} }{x} \leq \Delta$,则称$\Delta$为x的相对误差限

舍入误差

一个数$\dot{x}$与它经过舍入或者截断产生的近似数$x$之间的误差

截断误差

许多数学计算（微分、积分、无穷级数求和）是通过极限过程定义的，但是在计算机只能完成有限次的运算，用有限过程近似无穷过程，表现为对无穷过程的截断，由此产生的误差

传播误差

许多数值方法都是有递推公式的形式给出的，初始数据往往都是具有误差的，每一步的计算也都会产生舍入误差，这些误差也需要进行运算，会影响后面的计算结果，即这些 误差要向后传播，由此产生的误差

求解一个数学问题可以有多种数值方法，如果一种数值方法的传播误差不太大（或者说是可以控制的），则称方法是稳定的，否则是不稳定的