文章目录

1. 残向量
2. 误差向量和范数

误差向量
范数

向量范数

常用的向量范数

矩阵范数

常用的矩阵范数

谱半径

3. 误差的代数表征

条件数

条件数的应用
估计条件数

对于线型方程组：

Ax=b

我们能够使用计算机解出线型方程组，但是这仍然不够。因为不知道这个解是否是正确的。在之前的学习中，我们解出一个方程之后要把答案带入进行检验。

对于一次方程 $ax=b$ 来说，设 $x^*$ 是 $ax=b$ 的精确解， $\tilde x$ 是其计算解，
若 $|b-a\tilde x|<\varepsilon$ ,则 $\tilde x$ 是 $ax=b$ 的近似解。
证明：
$\tilde x$ 是 $ax=b$ 的近似解指的是 $\tilde x-x^*<\varepsilon$
$|b-a\tilde x|=|ax^*-a\tilde x|=|a|\cdot|\tilde x-x^*|<\varepsilon$
$|\tilde x-x^*|<\frac {\varepsilon} {|a|}$

那下面的说法能否成立呢？
设 $x^*$ 是 $Ax=b$ 的精确解， $\tilde x$ 是其计算解，若 $|b-A\tilde x|<\varepsilon$ ,则 $\tilde x$ 是 $ax=b$ 的近似解。

1. 残向量

同样为了检验方程组的计算解是否为原方程组的近似解，可以尝试将计算解代入方程组中，假设计算解为 $\tilde x$ ，则残向量为： $r=b-A\tilde x$ ，我们使用残向量来评价解的误差。

例如：

对于以下线性方程组：
$\left( {\begin{matrix} {1.000}&{2.000}\\ {0.499}&{1.001} \end{matrix}} \right)\left( {\begin{matrix} {{x_1}}\\ {{x_2}} \end{matrix}} \right) = \left( {\begin{matrix} {3.000}\\ {1.500} \end{matrix}} \right)$
求出的计算解为 $\tilde x = {(2.000,0.500)^T}$ ，该解是否可靠？

准确解是 ${x^*} = {(1,1)^T}$ ，但是求出的计算解为 $\tilde x = {(2.000,0.500)^T}$ ，残向量为 $r = {(0.000,0.0015)^T}$ ，但是误差向量并不是一个很小的量 $e = {x^*} - \tilde x = \left( {\begin{matrix} 1\\ 1 \end{matrix}} \right) - \left( {\begin{matrix} {2.0}\\ {0.5} \end{matrix}} \right) = \left( {\begin{matrix} { - 1}\\ {0.5} \end{matrix}} \right)$

故而，残向量很小时，计算解与准确解之间仍会相差很大。 所以不能只根据残向量的大小判断解的可靠性。

2. 误差向量和范数

误差向量

误差向量定义： $e = {x^*} - \tilde x = \left( {\begin{matrix} {{\varepsilon _1}}\\ {{\varepsilon _2}}\\ \vdots \\ {{\varepsilon _n}} \end{matrix}} \right) = \left( {\begin{matrix} {x_1^* - {{\tilde x}_1}}\\ {x_2^* - {{\tilde x}_2}}\\ \vdots \\ {x_n^* - {{\tilde x}_n}} \end{matrix}} \right)$

范数

向量范数

我们想要说明上述检验方程组解的可靠性的方法是否成立，必须要定义 $|b-A\tilde x|$ ，这是一个向量，回想常量的绝对值定义：
$\varphi (x) = \left| x \right| = \left\{ {\begin{matrix} {x{\rm{ }},x > 0}\\ {0{\rm{ }},x = 0}\\ { - x{\rm{ }},x < 0} \end{matrix}} \right.$
这个绝对值函数有以下性质：

非负性
齐次性
对于任意实数 $\alpha$ ，有 $|\alpha x|=|\alpha||x|$
三角不等式
$\left| {x + y} \right| \le \left| x \right| + \left| y \right|$

我们对于向量的“绝对值”的定义也必须满足上面三个性质，只要满足上面的三个性质，那这个向量“绝对值”的定义就是有效的，我们称为范数。

定义：对向量 $x = {({x_1},{x_2},...,{x_n})^T}$ ，具有如下类似性质的函数 $\varphi (x) = \varphi ({x_1},{x_2},...,{x_n})$ ，成为向量 x 的范数或模或长度,记为 $\left\| x \right\| = \varphi (x)$
《计算方法》笔记之（四）线性代数方程组之线性代数方程组解的可靠性

常用的向量范数

因为满足以上三个性质的定义就是向量的范数，所以向量的范数可以有多种定义，常用的有如下三种：

1 范数
${\left\| x \right\|_1} = \left| {{x_1}} \right| + \left| {{x_2}} \right| + \cdots + \left| {{x_n}} \right|$
2 范数
${\left\| x \right\|_2} = {(x_1^2 + x_2^2 + \cdots + x_n^2)^{1/2}}$
无穷范数
${\left\| x \right\|_\infty } = \mathop {\max }\limits_{1 \le i \le n} \left| {{x_i}} \right|$

向量是二维的时候范数的几何意义：
《计算方法》笔记之（四）线性代数方程组之线性代数方程组解的可靠性
n=3 的时候类似。

既然向量范数有多种定义，那么是否会出现一种范数使得 $|b-A\tilde x|<\varepsilon$ ，而另一种范数不满足这个不等式呢？所以我们需要探究向量的不同范数之间是否有什么关系。

向量范数之间的等价关系
${\rm{ }}\left\{ \begin{matrix}{l} {\left\| x \right\|_\infty } \le {\left\| x \right\|_1} \le n{\left\| x \right\|_\infty }\\ {\left\| x \right\|_\infty } \le {\left\| x \right\|_2} \le \sqrt n {\left\| x \right\|_\infty }\\ \frac{1}{{\sqrt n }}{\left\| x \right\|_1} \le {\left\| x \right\|_2} \le {\left\| x \right\|_1} \end{matrix} \right.$
它表明一个向量，若按某种范数是一个小量，那按其他任意一种范数都是一个小量。

如果无穷范数是一个小量，那根据第一个式子， 1 范数也是一个小量，根据第二个式子， 2 范数也是一个小量。

如果 1 范数是一个小量，根据第三个式子， 2 范数也是一个小量，根据第一个式子（可以变为 ${\frac 1 n\left\| x \right\|_1 } \le {\left\| x \right\|_\infty} \le {\left\| x \right\|_1 }$ ）,无穷范数也是一个小量。

同理，若 2 范数是一个小量，其他两个范数也是一个小量。

矩阵范数

为了用范数表示线型方程组解的精确度，还需要对矩阵的大小有类似的数量表征。所以引入了矩阵的范数。与向量范数的定义类似：

定义：对于 n 阶矩阵 A ，具有如下性质的函数 $\varphi(A)$ ，称为矩阵 A 的范数,记为 $\left\| A \right\|=\varphi(A)$
《计算方法》笔记之（四）线性代数方程组之线性代数方程组解的可靠性

常用的矩阵范数

1 范数 ( 最大列和)
$\|A\|_1=\mathop {\max }\limits_{1 \le j \le n} {{\sum}_{i=1}^n}\left| {{a_{ij}}} \right|$
2 范数
无穷范数 ( 最大行和)
$\|A\|_1=\mathop {\max }\limits_{1 \le i \le n} {{\sum}_{j=1}^n}\left| {{a_{ij}}} \right|$
F 范数 (Frobrnious 范数)
$\|A\|_F=\left(\sum_{i=1}^n\sum_{j=1}^n|a_{ij}|^2\right)^{1/2}$

谱半径

定义：对于 n 阶矩阵 A ，具有 n 个特征值为 ${\lambda _1},{\lambda _2},...,{\lambda _n}$ ，称数 $\rho (A) = \mathop {max}\limits_{1 \le i \le n} \left| {{\lambda _i}} \right|$ 为矩阵 A 的谱半径。

推论：对于矩阵 A 的任意一种范数，都有 $\rho (A) \le \left\| A \right\|$

原因：设 $\bm \lambda$ 为矩阵 A 相应于特征向量 $\bm \mu$ 的特征值，则
$\bm A\bm \mu=\lambda \bm \mu$
$\|\bm A\bm \mu\| \le \|\bm A\|\cdot\|\bm \mu\|$
$\|\bm A\bm \mu\| =\|\lambda \bm \mu\|=|\lambda|\cdot \| \bm \mu\|$
所以 $|\lambda|\le \|\bm \mu\|$

3. 误差的代数表征

条件数

我们很容易计算残向量，但是一般无法得到真正解，也就是不能得到误差项量。所以希望在他们之间建立某种关系，以便使用残向量估计误差。

残向量定义：
$r = b - A\tilde x{\rm{ }}$
可以改写为：
$A\tilde x = b - r$
可以把计算解 $\tilde x$ 看做 $Ax = b - r$ 的准确解。问题变为讨论 $Ax=b$ 的右端向量发生变化-r ，导致的解的变化 ${x^*} - \tilde x$ 的关系。

由于： $A\tilde x = b - r,Ax^*=b$
$\tilde x = {A^{ - 1}}(b - r){\rm{,}}{x^*} = {A^{ - 1}}b$
$e = {x^*} - \tilde x = {A^{ - 1}}r$
$\left\| e \right\| = \left\| {{A^{ - 1}}r} \right\| \le \left\| {{A^{ - 1}}} \right\| \cdot \left\| r \right\|$
$A{x^*} = b\Rightarrow \left\| b \right\| \le \left\| A \right\|\left\| {{x^*}} \right\|$
$\therefore \frac{1}{{\left\| {{x^*}} \right\|}} \le \frac{{\left\| A \right\|}}{{\left\| b \right\|}}$
因此有：
$\frac{{\left\| e \right\|}}{{\left\| {{x^*}} \right\|}} \le \left( {\left\| A \right\| \cdot \left\| {{A^{ - 1}}} \right\|} \right)\frac{{\left\| r \right\|}}{{\left\| b \right\|}}$
即 $\frac{{\left\| {{x^*} - \tilde x} \right\|}}{{\left\| {{x^*}} \right\|}} \le \left( {\left\| A \right\| \cdot \left\| {{A^{ - 1}}} \right\|} \right)\frac{{\left\| r \right\|}}{{\left\| b \right\|}}$
意义：解向量的相对误差不超过右端向量误差的一个倍数 $k={\left\| A \right\| \cdot \left\| {{A^{ - 1}}} \right\|}$

定义：矩阵 A 的条件数定义为 $cond(A) = \left\| A \right\|\left\| {{A^{ - 1}}} \right\|$ 。
条件数用于估计计算解的误差。有了条件数和右端向量误差就可以估计解向量的相对误差。
因为 $I=AA^{-1}$ 所以 $\|I\|=\|AA^{-1}\|\leq \|A\|\cdot\|A^{-1}\|$
$Cond(A) \ge 1$
可知误差向量的相对误差不会比残向量的相对误差要小

例如：
对于线型方程组：
$\left( {\begin{matrix} {1.000}&{2.000}\\ {0.499}&{1.001} \end{matrix}} \right)\left( {\begin{matrix} {{x_1}}\\ {{x_2}} \end{matrix}} \right) = \left( {\begin{matrix} {3.000}\\ {1.500} \end{matrix}} \right)$

其中：
$A = \left( {\begin{matrix} {1.000}&{2.000}\\ {0.499}&{1.001} \end{matrix}} \right)$
${A^{ - 1}} = \left( {\begin{matrix} {333.67}&{ - 666.67}\\ { - 166.67}&{333.33} \end{matrix}} \right)$
${\left\| A \right\|_\infty } = 3$
${\left\| {{A^{ - 1}}} \right\|_\infty } = 1000.34$
$k = {\left\| A \right\|_\infty }{\left\| {{A^{ - 1}}} \right\|_\infty } = 3001.02$
求出的计算解为 $\tilde x = {(2.000,0.500)^T}$ ，残向量为 $r = {(0.000,0.0015)^T}$ ，但是误差向量并不是一个很小的量 $e = {x^*} - \tilde x = \left( {\begin{matrix} 1\\ 1 \end{matrix}} \right) - \left( {\begin{matrix} {2.0}\\ {0.5} \end{matrix}} \right) = \left( {\begin{matrix} { - 1}\\ {0.5} \end{matrix}} \right)$

$\frac{{\left\| r \right\|}}{{\left\| b \right\|}} = \frac{{0.0015}}{3} = 0.0005$
$\frac{{\left\| e \right\|}}{{\left\| {{x^*}} \right\|}} = 1$
$\therefore {\rm{ }}\frac{{\left\| e \right\|}}{{\left\| {{x^*}} \right\|}} \le \left\| A \right\|\left\| {{A^{ - 1}}} \right\|\frac{{\left\| r \right\|}}{{\left\| b \right\|}} = 3001.02*0.0005 = 1.50101$
因为条件数过大，所以小的残向量不能保证计算解有小的误差。

条件数的应用

矩阵的条件数，刻画了方程组的性态：

条件数比较大时，称矩阵为病态矩阵，相应方程组为病态方程组。
条件数比较小时，称矩阵为良态矩阵，相应方程组为良态方程组。

病态方程组的特征及判别:

系数矩阵的行或列近似线性相关
系数矩阵的元素数量级相差悬殊
解对系数矩阵元素的变化比较敏感
在 Gauss 消去法求解过程中，出现数量级较小的主元
求出的解与预期的解相差较大

求解病态方程组的措施：

采取高精度计算，以减少舍入误差的影响
采用稳定性好的列主元高斯消去算法
采用平衡措施，将整个方程组的系数平衡化
采用迭代改善技术，通过对得到的解不断地修正，得到更好的近似解

估计条件数

计算条件数需要知道 $A^{-1}$ ，它的计算非常耗时，我们可以估计条件数。
估计方法：

《计算方法》笔记之（四）线性代数方程组之线性代数方程组解的可靠性

《计算方法》笔记之（四）线性代数方程组之 线性代数方程组解的可靠性