1.3 数值代数研究中的基本技术

1. 矩阵分解 (matrix factorizations)
2. 扰动理论和条件数 (Perturbation and condition numbers)
3. 舍入误差对算法的影响 (effects of roundoff error on algorithms)
4. 算法速度的分析 (analysis of the speed of algorithm)
5. 数值软件工程 (engineering numerical software)

1.3.1 矩阵分解

矩阵分解就是把复杂的矩阵分解为多个简单矩阵乘积的形式， 从而更有利于问题的求解 。

例1.1 假如要求解 $Ax = b$， 其中 $$\begin{bmatrix} a_{11} \\ a_{21} & a_{22} \\ \vdots & & \ddots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}$$

若 $A$ 是下三角矩阵，利用前向替换(forward substitutions)很容易求解:

定理1.1 若 $n\times n$ 阶矩阵 $A$ 非奇异，则存在一个置换矩阵 $P$ (对单 位矩阵进行行置换后得到的矩阵)、一个非奇异下三角矩阵 $L$ 和一个非奇异上三角阵 $U$，使得 $A = P\cdot L\cdot U$。 求解 $Ax = b$ 可转化为求解 等价方程组 $PLUx = b$, 求解过程如下:

$$\begin{aligned} LUx = & P^{-1}b = P^Tb \\ Ux = &L^{-1}(P^{-1}b) \\ x = &U^{-1}(L^{-1}P^{-1}b) \end{aligned}$$

讲课笔记

1. 代码演示
2. 置换矩阵

Jordan 标准分解: $A = VJV^{-1}$

1. $J$ 的主对角线为 $A$ 的特征值
2. $V$ 的列向量为对应的特征向量
3. $V$ 非奇异

Schur 分解: $A = UTU^*$。

1. $U$ 是酉矩阵(unitary matrix), 它的列向量正交 $UU^* = I$
2. $T$ 的对角线元素为 $A$ 的特征值

讲课笔记

1. 解释比较两种分解

1.3.2 扰动理论与条件数

数值算法算出的结果一般有两类误差来源：

1. 输入数据误差
2. 算法逼近误差

问题： 给定一个算法，如果输入数据存在一个小小的扰动，会给输出结果带来多大的 改变或扰动。

例 1.3 设 $f(x)$ 是关于实变量 $x$ 的一个实值可微函数。给定一个带扰动的输入 $x + \delta x$, 且知道 $\delta x$ 上界，问函数值 $f(x)$ 的扰动有多大。

分析： 要计算 $f(x)$, 但实际计算的是 $f(x + \delta x)$， 并试图给出绝对 误差 $|f(x + \delta x)-f(x)|$ 的界.

对 $f$ 进行简单的线性近似可得

$$f(x + \delta x) \approx f(x) + \delta xf'(x),$$

$$|f(x + \delta x) - f(x)| \approx |\delta x|\cdot |f'(x)|.$$

称 $|f'(x)|$ 为 $f$ 在 $x$ 上的绝对条件数。

若 $|f'(x)|$ 足够大，即使 $\delta x$ 很小，函数值的扰动也可能很大, 即误差很 大。 此时，称 $f$ 于 $x$ 处是病态的。

通常也可以用下面的表达式来界定误差:

$$\frac{|f(x+\delta x) - f(x)|}{|f(x)|} \approx \frac{|\delta x|}{| x|}\cdot\frac{|f'(x)|\cdot|x|}{|f(x)|}$$

上式左端称为计算结果的相对误差, 它的大小可由右端的相对输入误差 $$\frac{|\delta x|}{| x|}$$ 和相对条件数 $\frac{|f'(x)|\cdot|x|}{|f(x)|}$ 的乘积来界定。

对每一个代数计算的问题，都会给出相应的条件数。

讲课笔记

1. 举例解释为什么要引入相对误差

1.3.3 舍入误差对算法的影响(Effects of Roundoff Error on Algorithms)

设 $alg(x)$ 是含有舍入误差影响的计算 $f(x)$ 的算法， 若对一切 $x$ 存在一个 “小的” $\delta x$, 使得 $alg(x) = f(x + \delta x)$, 则称 $alg(x)$ 为 $f(x)$ 的向后稳定算法 (backward stable algorithm), $\delta x$ 称为相应的 向后误差 (backward error)。

$$\text{error} = |alg(x) - f(x)| = |f(x + \delta x) - f(x)| \approx |f'(x)|\cdot|\delta x|$$

讲课笔记

1. 解释向后稳定的意义
2. 要选择向后稳定的算法
3. 向后稳定的算法也可以误差很大

1.3.4 分析算法的速度（Analyzing the Speed of Algorithms）

选择算法时，除了要考虑向后稳定性，还要考虑算法的执行速度(speed), 有以下三种 常用的估计速度的方法：

1. 实现算法在机器上跑一遍
2. 浮点数操作的数目 (flops, floating point operations)
3. 迭代法中估计误差的下降率 $0 < c < 1$
   • 线性：$|\text{error}_i| < c\cdot |\text{error}_{i-1}|$
   • 二次：$|\text{error}_i| < c\cdot |\text{error}_{i-1}|^2$

讲课笔记

1. 解释三种方法
2. 三种方法各自的局限

1.3.5 工程数值计算软件(Engineering Numerical Software)

设计或选择一个数值软件的常用标准：

1. 易用性 (easy of use)
2. 可靠性 (reliablility)
3. 速度 (speed)

讲课笔记

1. 解释何种情况下，易用性比其它标准，更重要

使用其它专家的数值代数软件的三种基本方式：

1. 软件库，如 Netlib 上的 LAPACK
2. 算法集成环境，如 Matlab, 更易用，在某种程度上牺牲了执行效率
3. 模板 (template)

讲课笔记

1. 解释 Matlab 为什么会降低了算法的执行效率
2. 解释模板库的应用环境。

扩展学习

模板

模板是一个一般算法的描述，而不是像通常软件库中的可执行程序或代码片断