数值分析基础第1章：引论

本文的内容主要来自关治的《数值分析基础（第3版）》第1章《引论》和老师的PPT。

数值分析的研究对象

（略）

数值计算的误差

误差的来源与分类

误差大致分为4类：

输入数据的误差；
舍入误差：来源于计算机的数字是有限的；
截断误差：用有限的过程代替无限的过程，或用简化的问题代替不易计算的原问题；
误差在计算过程中的传播。

绝对误差和相对误差、有效数字

定义2.1 设$x$是精确值，$x_A$是一个近似值。$e(x)=|x-x_A|$称为$x_A$的绝对误差，而$e_r(x)=\frac{|x-x_A|}{x}$称为$x_A$的相对误差。

定义2.2 因为$x$通常是未知的，一般只能给出$|x-x_A|$的上界$\epsilon_A$。$|x-x_A|\leq\epsilon_A$称为$x_A$的绝对误差界，而$\epsilon_r(x)=\frac{\epsilon_A}{x}$称为$x_A$的相对误差界。

对于一个实数，取有限位数作为近似值，采用四舍五入的方法。这样得到的近似值，绝对误差界为最后数位的半个单位。因此引入了有效数字概念。

定义2.3 设$x_A$是$x$的一个近似值，$x_A=\pm0.a_1a_2\cdots a_i\cdots\times 10^k$，其中$k$为整数，$a_i\in{0,1,2,\cdots,9}$，$a_1\neq 0$。如果有$|x-x_A|\leq\frac{1}{2}\times 10^{k-n}$，则称$x_A$具有$n$位有效数字：$a_1,a_2,\cdots,a_n$。

有效数字就是寻找误差在$5$以内（包括$5$）的那位，计数之前数字的个数。

设$x$的近似值$x_A=\pm0.a_1a_2\cdots a_i\cdots\times 10^k$，则：

如果$x_A$有$n$位有效数字，则：

$$\frac{|x-x_A|}{x_A}\leq\frac{1}{2a_1}\times 10^{1-n}$$
如果：

$$\frac{|x-x_A|}{x_A}\leq\frac{1}{2(a_1+1)}\times 10^{1-n}$$

则$x_A$至少有$n$位有效数字。

1的证明比较简单，这里证明2，由$|x_A|=0.a_1a_2\cdots\times 10^k\leq0.(a_1+1)\times 10^k=(a_1+1)\times 10^{k-1}$可以证明。

求函数值和算术运算的误差估计

向前误差分析 设$x$的浮点数表示为$x^*$。则：

$$\begin{aligned} x^*&=x(1+\delta)\\ (x^*)^2&=x^2(1+2\delta) \end{aligned}$$

因而，每次乘法相对误差加倍。这里，$\delta^2$由于超出浮点数表示能力而被忽略。

向后误差分析 把计算结果的误差归结为原始数据经扰动之后的精确的计算结果的误差分析叫做后向误差分析。

设$y=f(x_1,x_2,\cdots,x_n)$，如果参量$x_i,1\leq i\leq n$有误差，则$y$也会有误差。若$x_i,1\leq i\leq n$的近似值为$\tilde{x}_i,1\leq i\leq n$，相应的解为$\tilde{y}$，则$\tilde{y}$的绝对误差和相对误差分别为：

$$\begin{aligned} |y-\tilde{y}|&\leq\sum\limits_{i=1}^n\left|\frac{\partial f}{\partial x_i}\right||x_i-\tilde{x_i}|\\ \frac{|y-\tilde{y}|}{|y|}&\leq\sum\limits_{i=1}^n\left|\frac{x_i}{y}\frac{\partial f}{\partial x_i}\right|\frac{|x_i-\tilde{x_i}|}{|x_i|} \end{aligned}$$

把两个数$a,b$的$+,-,\times,\div$看成二元函数，则有：

$$\begin{aligned} e(a\pm b)&\leq e(a)+e(b)\\ e(ab)&\leq|b|e(a)+|a|e(b)\\ e_r(a\pm b)&\leq\frac{|a|e_r(a)+|b|e_r(b)}{|a\pm b|}\\ e_r(ab)&\leq e_r(a)+e_r(b)\\ e(\frac{a}{b})&\leq \frac{e(a)}{|b|}+\left|\frac{a}{b^2}\right|e(b)\\ e_r(\frac{a}{b})&\leq e_r(a)+e_r(b) \end{aligned}$$

计算机的浮点数表示和舍入误差

在计算机上，实数系统$\mathbb{R}$是用浮点数系统$\mathbb{F}$来近似的。实数$x$在$\beta$进制浮点数系统下的表示为：

$$x=(-1)^s\cdot(0.a_1a_2\cdots a_t)\cdot\beta^e=(-1)^s\cdot m\cdot \beta^{e-t}$$

其中：

$s$：符号位，$1$为负数，$0$为正数；
$m=a_1a_2\cdots a_t,0\leq a_i\leq\beta-1$：尾数，$t$称为字长；
$e,L\leq e\leq U$：指数。

二进制浮点数系统$\mathbf{F}$为：

$$\mathbb{F}={\pm 0.d_1d_2\cdots d_t\times 2^k}\cup{0}$$

其中$d_1=1$。

浮点数的近似$\mathrm{fl}(x)$，有两种：

截断；
舍入：IEEE属于这种。

定义$\epsilon_{mach}$为机器精度：

$$\begin{aligned} \left|\frac{x-\mathrm{fl}(x)}{x}\right|&=\left|\frac{0.1d_2\cdots d_td_{t+1}\cdots\times 2^k-0.1d_2\cdots d_t\times 2^k}{0.1d_2\cdots\times 2^k}\right|\\ &\leq\left|\frac{0.d_{t+1}d_{t+2}\cdots\times 2^k}{0.1d_2\cdots\times 2^k}\right|\times 2^{-t} \leq 2^{-t}=\epsilon_{mach} \end{aligned}$$

病态问题、数值稳定性与避免误差危害

病态问题与条件数

敏度分析是研究$x$有微小变化$\delta x$时，函数值$f$会发生多大的变化：

$$\frac{|f(x+\delta x)-f(x)|}{f(x)}\leq\kappa(x)\frac{|\delta x|}{|x|}$$

称$\kappa(x)$为$f$在$x$的条件数。

当$\kappa(x)$很大时，自变量的微小变化就可能引起函数值的巨大变化，则称$f$在$x$点是病态的；否则称$f$在$x$点是良态的。

一个计算问题是否病态是问题本身的固有属性。

$$\begin{aligned} \kappa(x)&=\lim_{x_A\to x}\frac{\left|\frac{f(x)-f(x_A)}{f(x)}\right|}{\left|\frac{x-x_A}{x}\right|}\\ &=\left|\frac{x}{f(x)}\right|\lim_{x_A\to x}\left|\frac{f(x)-f(x_A)}{x-x_A}\right|\\ &=\left|\frac{xf’(x)}{f(x)}\right| \end{aligned}$$

例如：Wilkinson多项式$\prod\limits_{i=1}^n(x-i)$求根就属于病态问题，用特征值的定义求求解特征值同样是病态问题。

数值方法的稳定性

一个数值方法，如果初始数或计算过程某一不有微小的改变，由此引发的计算结果也只是微小的变化，则称该方法是数值稳定的，否则称为数值不稳定的。

一般来说，如果具有初始误差$\epsilon_0>0$，计算$n$步后的误差为$\epsilon_n$，若方法是数值稳定的，则存在与$n$无关的常数$C$使得$\epsilon_n\leq C\epsilon_0$。

$|\epsilon|\approx Cn\epsilon_0$，线性型的误差增长；
$|\epsilon|\approx C^n\epsilon_0$，指数型的误差增长。$|C|\leq 1$稳定，$|C|>1$不稳定。

TODO: 给个例子。

避免误差危害

避免相近的数相减；
避免和绝对值大的数相乘；
避免和绝对值小的除数相除。

数学上等价$\neq$计算上等价：例如对于$ax^2+2bx+c=0$，采用$x_1=\frac{-b-\mathrm{sgn}(b)\sqrt{b^2-ac}}{a}, x_2=\frac{c}{ax_1}$，可以解决$b^2\gg|ac|$情况下的问题；使用$\frac{x^2}{\sqrt{1+x^2}+1}$替代$\sqrt{1+x^2}-1$可以避免$|x|\ll 1$时精度的损失。同时对于求解$n$次多项式，可以利用分配律合并多项式，达到$n$次乘法和$n$次加法。

选用公式也很重要，对于无穷级数毕竟求解的情况，通常选用同号数列求和极限比交替数列求和极限收敛速度更快。

线性代数的一些基本概念

矩阵乘法的定义 定义$\mathbb{F}^{m\times p}\times\mathbb{F}^{p\times n}=\mathbb{F}^{m \times n}$的一个运算，称为矩阵乘法，$\mathbf{A}\mathbf{B}=\mathbf{C}$，其中$c_{ij}=\sum\limits_{k=1}^p a_{ik}b_{kj}$。

矩阵迹的定义 设$\mathbf{A}=(a_{ij})_{i,j=1}^n\in\mathbf{F}^{n\times n}$，矩阵$\mathbf{A}$的迹是其所有对角元素之和。$\mathrm{tr}(\mathbf{A})=\sum\limits_{i=1}^na_{ii}$。

定理若$\mathbf{A}\in\mathbb{F}^{n\times m},\mathbf{B}\in\mathbb{F}^{m\times n}$，则$\mathrm{tr}(\mathbf{A}\mathbf{B})=\mathrm{tr}(\mathbf{B}\mathbf{A})$。

证明：

$$\mathrm{tr}(\mathbf{A}\mathbf{B})=\sum_{i=1}^n(\mathbf{A}\mathbf{B})_{ii}=\sum_{i=1}^n\sum_{j=1}^m\mathbf{A}_{ij}\mathbf{B}_{ji}=\sum_{j=1}^m\sum_{i=1}^n\mathbf{B}_{ji}\mathbf{A}_{ij}=\sum_{j=1}^m(\mathbf{A}\mathbf{B})_{jj}=\mathrm{tr}(\mathbf{B}\mathbf{A})$$

非奇异矩阵的定义 矩阵$\mathbf{A}\in\mathbb{R}^{n\times n}$称为非奇异的...

本文的内容主要来自关治的《数值分析基础（第3版）》第1章《引论》和老师的PPT。

数值分析的研究对象

（略）

数值计算的误差

误差的来源与分类

误差大致分为4类：

输入数据的误差；

舍入误差：来源于计算机的数字是有限的；

截断误差：用有限的过程代替无限的过程，或用简化的问题代替不易计算的原问题；

误差在计算过程中的传播。

绝对误差和相对误差、有效数字

定义2.1 设$x$是精确值，$x_A$是一个近似值。$e(x)=|x-x_A|$称为$x_A$的绝对误差，而$e_r(x)=\frac{|x-x_A|}{x}$称为$x_A$的相对误差。

定义2.2 因为$x$通常是未知的，一般只能给出$|x-x_A|$的上界$\epsilon_A$。$|x-x_A|\leq\epsilon_A$称为$x_A$的绝对误差界，而$\epsilon_r(x)=\frac{\epsilon_A}{x}$称为$x_A$的相对误差界。

对于一个实数，取有限位数作为近似值，采用四舍五入的方法。这样得到的近似值，绝对误差界为最后数位的半个单位。因此引入了有效数字概念。

定义2.3 设$x_A$是$x$的一个近似值，$x_A=\pm0.a_1a_2\cdots a_i\cdots\times 10^k$，其中$k$为整数，$a_i\in{0,1,2,\cdots,9}$，$a_1\neq 0$。如果有$|x-x_A|\leq\frac{1}{2}\times 10^{k-n}$，则称$x_A$具有$n$位有效数字：$a_1,a_2,\cdots,a_n$。

有效数字就是寻找误差在$5$以内（包括$5$）的那位，计数之前数字的个数。

设$x$的近似值$x_A=\pm0.a_1a_2\cdots a_i\cdots\times 10^k$，则：

如果$x_A$有$n$位有效数字，则：

$$\frac{|x-x_A|}{x_A}\leq\frac{1}{2a_1}\times 10^{1-n}$$

如果：

$$\frac{|x-x_A|}{x_A}\leq\frac{1}{2(a_1+1)}\times 10^{1-n}$$

则$x_A$至少有$n$位有效数字。

1的证明比较简单，这里证明2，由$|x_A|=0.a_1a_2\cdots\times 10^k\leq0.(a_1+1)\times 10^k=(a_1+1)\times 10^{k-1}$可以证明。

求函数值和算术运算的误差估计

向前误差分析 设$x$的浮点数表示为$x^*$。则：

$$\begin{aligned} x^*&=x(1+\delta)\\ (x^*)^2&=x^2(1+2\delta) \end{aligned}$$

因而，每次乘法相对误差加倍。这里，$\delta^2$由于超出浮点数表示能力而被忽略。

向后误差分析 把计算结果的误差归结为原始数据经扰动之后的精确的计算结果的误差分析叫做后向误差分析。

设$y=f(x_1,x_2,\cdots,x_n)$，如果参量$x_i,1\leq i\leq n$有误差，则$y$也会有误差。若$x_i,1\leq i\leq n$的近似值为$\tilde{x}_i,1\leq i\leq n$，相应的解为$\tilde{y}$，则$\tilde{y}$的绝对误差和相对误差分别为：

$$\begin{aligned} |y-\tilde{y}|&\leq\sum\limits_{i=1}^n\left|\frac{\partial f}{\partial x_i}\right||x_i-\tilde{x_i}|\\ \frac{|y-\tilde{y}|}{|y|}&\leq\sum\limits_{i=1}^n\left|\frac{x_i}{y}\frac{\partial f}{\partial x_i}\right|\frac{|x_i-\tilde{x_i}|}{|x_i|} \end{aligned}$$

把两个数$a,b$的$+,-,\times,\div$看成二元函数，则有：

$$\begin{aligned} e(a\pm b)&\leq e(a)+e(b)\\ e(ab)&\leq|b|e(a)+|a|e(b)\\ e_r(a\pm b)&\leq\frac{|a|e_r(a)+|b|e_r(b)}{|a\pm b|}\\ e_r(ab)&\leq e_r(a)+e_r(b)\\ e(\frac{a}{b})&\leq \frac{e(a)}{|b|}+\left|\frac{a}{b^2}\right|e(b)\\ e_r(\frac{a}{b})&\leq e_r(a)+e_r(b) \end{aligned}$$

计算机的浮点数表示和舍入误差

在计算机上，实数系统$\mathbb{R}$是用浮点数系统$\mathbb{F}$来近似的。实数$x$在$\beta$进制浮点数系统下的表示为：

$$x=(-1)^s\cdot(0.a_1a_2\cdots a_t)\cdot\beta^e=(-1)^s\cdot m\cdot \beta^{e-t}$$

其中：

$s$：符号位，$1$为负数，$0$为正数；

$m=a_1a_2\cdots a_t,0\leq a_i\leq\beta-1$：尾数，$t$称为字长；

$e,L\leq e\leq U$：指数。

二进制浮点数系统$\mathbf{F}$为：

$$\mathbb{F}={\pm 0.d_1d_2\cdots d_t\times 2^k}\cup{0}$$

其中$d_1=1$。

浮点数的近似$\mathrm{fl}(x)$，有两种：

截断；

舍入：IEEE属于这种。

定义$\epsilon_{mach}$为机器精度：

$$\begin{aligned} \left|\frac{x-\mathrm{fl}(x)}{x}\right|&=\left|\frac{0.1d_2\cdots d_td_{t+1}\cdots\times 2^k-0.1d_2\cdots d_t\times 2^k}{0.1d_2\cdots\times 2^k}\right|\\ &\leq\left|\frac{0.d_{t+1}d_{t+2}\cdots\times 2^k}{0.1d_2\cdots\times 2^k}\right|\times 2^{-t} \leq 2^{-t}=\epsilon_{mach} \end{aligned}$$

病态问题、数值稳定性与避免误差危害

病态问题与条件数

敏度分析是研究$x$有微小变化$\delta x$时，函数值$f$会发生多大的变化：

$$\frac{|f(x+\delta x)-f(x)|}{f(x)}\leq\kappa(x)\frac{|\delta x|}{|x|}$$

称$\kappa(x)$为$f$在$x$的条件数。

当$\kappa(x)$很大时，自变量的微小变化就可能引起函数值的巨大变化，则称$f$在$x$点是病态的；否则称$f$在$x$点是良态的。

一个计算问题是否病态是问题本身的固有属性。

$$\begin{aligned} \kappa(x)&=\lim_{x_A\to x}\frac{\left|\frac{f(x)-f(x_A)}{f(x)}\right|}{\left|\frac{x-x_A}{x}\right|}\\ &=\left|\frac{x}{f(x)}\right|\lim_{x_A\to x}\left|\frac{f(x)-f(x_A)}{x-x_A}\right|\\ &=\left|\frac{xf’(x)}{f(x)}\right| \end{aligned}$$

例如：Wilkinson多项式$\prod\limits_{i=1}^n(x-i)$求根就属于病态问题，用特征值的定义求求解特征值同样是病态问题。

数值方法的稳定性

一个数值方法，如果初始数或计算过程某一不有微小的改变，由此引发的计算结果也只是微小的变化，则称该方法是数值稳定的，否则称为数值不稳定的。

一般来说，如果具有初始误差$\epsilon_0>0$，计算$n$步后的误差为$\epsilon_n$，若方法是数值稳定的，则存在与$n$无关的常数$C$使得$\epsilon_n\leq C\epsilon_0$。

$|\epsilon|\approx Cn\epsilon_0$，线性型的误差增长；

$|\epsilon|\approx C^n\epsilon_0$，指数型的误差增长。$|C|\leq 1$稳定，$|C|>1$不稳定。

TODO: 给个例子。

避免误差危害

避免相近的数相减；

避免和绝对值大的数相乘；

避免和绝对值小的除数相除。

数学上等价$\neq$计算上等价：例如对于$ax^2+2bx+c=0$，采用$x_1=\frac{-b-\mathrm{sgn}(b)\sqrt{b^2-ac}}{a}, x_2=\frac{c}{ax_1}$，可以解决$b^2\gg|ac|$情况下的问题；使用$\frac{x^2}{\sqrt{1+x^2}+1}$替代$\sqrt{1+x^2}-1$可以避免$|x|\ll 1$时精度的损失。同时对于求解$n$次多项式，可以利用分配律合并多项式，达到$n$次乘法和$n$次加法。

选用公式也很重要，对于无穷级数毕竟求解的情况，通常选用同号数列求和极限比交替数列求和极限收敛速度更快。

线性代数的一些基本概念

矩阵乘法的定义 定义$\mathbb{F}^{m\times p}\times\mathbb{F}^{p\times n}=\mathbb{F}^{m \times n}$的一个运算，称为矩阵乘法，$\mathbf{A}\mathbf{B}=\mathbf{C}$，其中$c_{ij}=\sum\limits_{k=1}^p a_{ik}b_{kj}$。

矩阵迹的定义 设$\mathbf{A}=(a_{ij})_{i,j=1}^n\in\mathbf{F}^{n\times n}$，矩阵$\mathbf{A}$的迹是其所有对角元素之和。$\mathrm{tr}(\mathbf{A})=\sum\limits_{i=1}^na_{ii}$。

定理若$\mathbf{A}\in\mathbb{F}^{n\times m},\mathbf{B}\in\mathbb{F}^{m\times n}$，则$\mathrm{tr}(\mathbf{A}\mathbf{B})=\mathrm{tr}(\mathbf{B}\mathbf{A})$。

证明：

$$\mathrm{tr}(\mathbf{A}\mathbf{B})=\sum_{i=1}^n(\mathbf{A}\mathbf{B})_{ii}=\sum_{i=1}^n\sum_{j=1}^m\mathbf{A}_{ij}\mathbf{B}_{ji}=\sum_{j=1}^m\sum_{i=1}^n\mathbf{B}_{ji}\mathbf{A}_{ij}=\sum_{j=1}^m(\mathbf{A}\mathbf{B})_{jj}=\mathrm{tr}(\mathbf{B}\mathbf{A})$$

非奇异矩阵的定义 矩阵$\mathbf{A}\in\mathbb{R}^{n\times n}$称为非奇异的...

本文的内容主要来自关治的《数值分析基础（第3版）》第1章《引论》和老师的PPT。