绪论

数值分析概括为用计算机求解数学问题的数值方法和理论。

在工程计算和科学实验中会遇到诸如线性方程组的求解、微分、积分、微分方程的求解等常见的数学问题。

求解数学问题思维方式：

（1）利用数学方法求出（或推导出）结果的解析表达式（又称解析解）

（2）若实际中结果的解析表达式难以给出，例如满足某个微分方程的函数不易求得，采用数学理论与计算机相结合，寻求(设计)合适的算法以期得到问题的近似数值解——数值分析研究的主要问题。

下面是两种思维过程的对比：

• 通常解决数学问题的思维方式：实际问题 → 数学模型 → 解析表达式 → 结果

• 数值分析的思维方式：实际问题 → 数学模型 → 算法设计 → 编程计算结果

  后者也正是利用计算机进行科学计算的过程。科学计算=数值方法+计算机

电子计算机实质上只会做加减乘除等基本运算，研究怎样通过计算机所能执行的基本运算，求得各类数学问题的数值解或近似解就是数值计算（科学计算）的根本课题。由基本运算及运算顺序的规定所构成的完整的解题步骤，称为算法。数值计算的根本任务就是研究算法。

学习数值分析课程的基本要求：

• 掌握算法(数值方法)的基本思想和原理
• 注意方法处理的技巧与计算机的结合，重视误差、稳定性、收敛性等基本理论
• 通过例子，编程实现各种数值方法，并利用其解决实际问题

误差

误差的背景介绍

误差：一个物理量的真实值与计算值之间的差异

来源与分类：

• 从实际问题中抽象出数学模型 —— 模型误差
• 通过测量得到模型中参数的值 —— 观测误差
• 求近似解 —— 方法误差 (截断误差)
• 机器字长有限 —— 舍入误差

传播与积累：计算 $\frac{1}{e}\int^1_0 x^ne^xdx,n=0,1,2,......$

• 公式一：$I_n=1-nI_{n-1}$ (此公式精确成立)

  $I_0=\frac{1}{e}\int^1_0 e^xdx=1-\frac{1}{e}≈0.63212056~记为I_0^*$ (舍入误差)

  则初始误差 $|E_0|=|I_0-I_0^*|<0.5×10^{-8}$， $\frac{1}{e}\int^1_0 x^ne^0dx<I_n<\frac{1}{e}\int^1_0 x^ne^1dx$ 所以 $\frac{1}{e(n+1)}<I_n<\frac{1}{n+1}$

  $I^*_{1}=1-1×I^*_{0}=0.36787944$ ...... $I^*_{10}=0.08812800$, $I^*_{11}=0.03059200$, $I^*_{12}=0.63289600$, $I^*_{13}=-7.2276480$, $I^*_{14}=94.959424$, $I^*_{15}=-1423.3914$

  考察第n步的误差 $|E_n|=|I_n-I_n^*|=|(1-nI_{n-1})-(1-nI_{n-1}^*)|=n|E_{n-1}|=...=n!|E_0|$

  可见初始的小扰动 $|E_0|<0.5*10^{-8}$ 迅速积累，误差呈递增走势。造成这种情况的是不稳定的算法。

• 公式二：$I_{n-1}=\frac{1}{n}(1-I_n)$ 先估计一个$I_N$，再反推要求的$I_n$(n<<N)。此公式与公式一理论上等价。

  可取 $I^*_N=\frac{1}{2}[\frac{1}{e(N+1)}+\frac{1}{N+1}]≈I_N$，当 $N\to+\infty$ 时，$|E_N|=|I_N-I_N^*|\to0$

  取 $I^*_{15}=\frac{1}{2}[\frac{1}{e*16}+\frac{1}{16}]≈0.042746233$ 得 $I^*_{14}≈0.063816918$, $I^*_{13}≈0.066870220$, $I^*_{12}≈0.071779214$,......, $I^*_{1}≈0.36787944$, $I^*_{0}≈0.63212056$

  考察反推一步的误差：$|E_{N-1}|=|\frac{1}{N}(1-I_N)-\frac{1}{N}(1-I_N^*)|=\frac{1}{N}|E_N|$

  以此类推，对 n<N 有：$|E_N|=\frac{1}{N(N-1)...(n+1)}|E_N|$，误差逐步递减, 这样的算法称为稳定的算法。

误差与有效数字

绝对误差：$e^*=x^*-x$ 其中x为精确值，$x^*$为x的近似值。$|e^*|$ 的上限记为 $\epsilon^*$，称为绝对误差限。工程上常记为 $\Large x=x^*\pm\epsilon^*$

$e^*$理论上讲是唯一确定的，可能取正，也可能取负。$\epsilon^*>0$ 不唯一，当然 $\epsilon^*$ 越小越具有参考价值。

相对误差：$e^*_r=\frac{e^*}{x}$ 由于x通常未知，故 $\Large e^*_r=\frac{e^*}{x}=\frac{e^*}{x^*}$。x的相对误差上限定义为 $\Large\epsilon^*_r=\frac{\epsilon^*}{|x^*|}$

有效数字：若近似值$x^*$的误差限是某一位的半个单位，该位到$x^*$的第一位非零数字共有n位，则$x^*$有n位有效数字。用科学计数法，记$x^*=\pm0.a_1a_2…a_n×10^m$(其中$a_1≠0$)。若$|x-x^*|≤0.5×10^{m-n}$(即$a_n$的截取按四舍五入规则)，则称$x^*$为有n位有效数字，精确到$10^{m-n}$。

$\pi=3.14159265...$，按四舍五入原则若取四位小数得$\pi\approx3.1416$（五位有效数值），取五位小数则有$\pi\approx3.14159$（六位有效数值），它们的绝对误差不超过末位数的半个单位，即$|\pi-3.1416|\leq\frac{1}{2}×10^{-4}$，$|\pi-3.14159|\leq\frac{1}{2}×10^{-5}$

数字末尾的0不可随意省去

有效数字与相对误差的关系：

• 有效数字$\Rightarrow$相对误差限：已知$x^*$有n位有效数字，则其相对误差限为 $\Large\epsilon^*_r=|\frac{\epsilon^*}{x^*}|=\frac{0.5×10^{m-n}}{0.a_1a_2…a_n×10^m}=\frac{10^{-n}}{2×0.a_1...}\leq\frac{1}{2a_1}×10^{-n+1}$
• 相对误差限$\Rightarrow$有效数字：已知$x^*$的相对误差限可写为 $\Large\epsilon^*_r=\frac{1}{2(a_1+1)}×10^{-n+1}$，则 $\Large|x-x^*|\leq\epsilon^*_r·|x^*|=\frac{10^{-n+1}}{2(a_1+1)}×0.a_1a_2...×10^m<\frac{10^{-n+1}}{2(a_1+1)}×(a_1+1)×10^{m-1}=0.5×10^{m-n}$，可见$x^*$至少有n位有效数字。

函数的误差估计

问题：对于 A=f(x)，若用$x^*$取代x，将对A产生什么影响？

分析：$e^*(x)=x^*-x$，$e^*(A)=f(x^*)-f(x)=f'(\xi)(x^*-x)$。$x^*$与x非常接近时，可认为$f'(\xi)\approx f'(x^*)$，则有：$|e^*(A)|\approx|f’(x^*)|·|e^*(x)|$

即：$x^*$产生的误差经过f作用后被放大/缩小了$|f’(x^*)|$倍。故称$|f’(x^*)|$为放大因子或绝对条件数。

$\large |e^*_r(x)|=|\frac{e^*(x)}{x^*}|$

$\large |e^*_r(A)|=|\frac{e^*(A)}{f(x^*)}|=|\frac{f(x^*)-f(x)}{x^*-x}·\frac{x^*}{f(x^*)}·\frac{x^*-x}{x^*}|\approx|\frac{x^*·f’(x^*)}{f(x^*)}|·|e^*_r(x)|$

$\Large|\frac{x^*·f’(x^*)}{f(x^*)}|$ 称为相对误差条件数。f的条件数在某一点是小\大，则称f在该点是好条件的\ 坏条件的。

几点注意事项

• 避免相近二数相减：例如 $a_1=0.12345$，$a_2=0.12346$，各有5位有效数字。而 $a_2-a_1=0.00001$，只剩下1位有效数字。几种经验性避免方法：$\Large\sqrt{x+\epsilon}-\sqrt{x}=\frac{\epsilon}{\sqrt{x+\epsilon}+\sqrt{x}}$；$ln(x+\epsilon)-lnx=ln(1+\frac{\epsilon}{x})$；当 |x|<<1 时，$1-cosx=2sin^2\frac{x}{2}$

• 避免小分母：分母小会造成浮点溢出

• 避免大数吃小数：例如，用单精度计算$x^2-(10^9+1)x+10^9=0$的根。精确解为$x_1=10^9,x_2=1$

  算法1：利用求根公式 $x=\frac{-b\pm\sqrt{b^2-4ac}}{2a}$。在计算机内，$10^9$存为$0.1×10^{10}$，1存为$0.1×10^1$。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1的指数部分须变为$10^{10}$，则 $1=0.0000000001×10^{10}$，取单精度时就成为 $10^9+1=0.10000000×10^{10}+0.00000000×10^{10}=0.10000000×10^{10}$。解得$x_1=10^9,x_2=0$

  算法2：先解出 $x_1=\frac{-b-sign(b)\sqrt{b^2-4ac}}{2a}=10^9$，再利用 $x_1×x_2=\frac{c}{a}\Rightarrow x_2=\frac{c}{a·x_1}=\frac{10^9}{10^9}=1$

  求和时从小到大相加，可使和的误差减小。

• 先化简再计算，减少步骤，避免误差积累。一般来说，计算机处理下列运算的速度为(+,-)>(×,÷)>(exp)

• 选用稳定的算法。