2.4 误差分析*

2.4.1 LU分解的舍入误差分析

关于 LU 分解的舍入误差分析, 我们有下面的结果 [70].

定理2.20 假定 $A \in \mathbb{R}^{n \times n}$ 的所有顺序主子式都不为 0, 则带舍入误差的 LU 分解可表示为

A = L U + E,

其中误差 $E$ 满足

| E | \leq \gamma_ {n} | L | \cdot | U |.

这里 $\gamma_{n} = \frac{n\varepsilon_{u}}{1 - n\varepsilon_{u}},\varepsilon_{u}$ 表示机器精度 (对于双精度浮点数, $\varepsilon_{u} = 2^{-53}\approx 1.1\times 10^{-16}$ ; 对于单精度浮点数, $\varepsilon_{u} = 2^{-24}\approx 6.0\times 10^{-8})$

由于 $|L|$ 和 $|U|$ 可以是任意大，比如

A = \left[ \begin{array}{c c} 1 0 ^ {- 2 0} & 1 \\ 1 & 1 \end{array} \right] = \left[ \begin{array}{c c} 1 & 0 \\ 1 0 ^ {2 0} & 1 \end{array} \right] \left[ \begin{array}{c c} 1 0 ^ {- 2 0} & 1 \\ 0 & 1 - 1 0 ^ {2 0} \end{array} \right],

因此LU分解是不稳定的.

如果是部分选主元 LU 分解, 则有 $|l_{ij}| \leq 1$ , 因此 $|E|$ 的上界主要取决于 $|U|$ 的大小.

2.4.2 Gauss消去法的舍入误差分析

引理2.21 [70] 设 $\hat{y}$ 和 $\hat{x}$ 是由回代算法2.6计算得到的数值解, 则

(L + \delta L) \hat {y} = b, \quad | \delta L | \leq \gamma_ {n} | L |

(U + \delta U) \hat {x} = \hat {y}, \quad | \delta U | \leq \gamma_ {n} | U |.

该引理表明, $\hat{y}$ 和 $\hat{x}$ 只有很小的误差, 因此向前回代算法和向后回代算法都是稳定的. 于是

\begin{array}{l} b = (L + \delta L) \hat {y} \\ = (L + \delta L) (U + \delta U) \hat {x} \\ = (L U + L \cdot \delta U + \delta L \cdot U + \delta L \cdot \delta U) \hat {x} \\ = (A - E + L \cdot \delta U + \delta L \cdot U + \delta L \cdot \delta U) \hat {x}. \\ \end{array}

记 $\delta A = -E + L\cdot \delta U + \delta L\cdot U + \delta L\cdot \delta U$ ，则 $\hat{x}$ 是扰动方程 $(A + \delta A)x = b$ 精确解，且

\begin{array}{l} | \delta A | = | - E + L \cdot \delta U + \delta L \cdot U + \delta L \cdot \delta U | \\ \leq | E | + | L | \cdot | \delta U | + | \delta L | \cdot | U | + | \delta L | \cdot | \delta U | \\ \leq \left(3 \gamma_ {n} + \gamma_ {n} ^ {2}\right) | L | \cdot | U | \leq \gamma_ {3 n} | L | \cdot | U |, \\ \end{array}

其中 $\gamma_{3n} = \frac{3n\varepsilon_u}{1 - 3n\varepsilon_u}$ . 两边取范数后可得

\left\| \delta A \right\| \leq 3 n \varepsilon_ {u} \left\| L \right\| \cdot \left\| U \right\|

对1-范数， $\infty$ -范数和 $F$ -范数成立(2-范数不成立).

根据算法向后稳定性的定义, 要说明带选主元 Gauss 消去法是向后稳定的, 必须要求 $\| \delta A\|$ 是“小”的, 即

\| \delta A \| = \mathcal {O} (\varepsilon_ {u}) \| A \|.

数值试验表明, 部分选主元 Gauss 消去法几乎总是保持

\| L \| \cdot \| U \| \approx \| A \|.

记

\rho_ {n} \triangleq \frac {\operatorname* {m a x} _ {i , j , k} | a _ {i j} ^ {(k)} |}{\operatorname* {m a x} _ {i , j} | a _ {i j} |}

为部分选主元 Gauss 消去法的增长因子, 其中 $a_{ij}^{(k)}$ 是部分选主元 Gauss 消去法过程第 $k$ 步时 $a_{ij}$ 的值. 由于 $\| L\|_{\infty} \leq n$ , $\| U\|_{\infty} \leq n\rho_n\| A\|_{\infty}$ , 因此 [70]

定理2.22 设 $\hat{x}$ 是由部分选主元Gauss法得到的数值解, 则 $\hat{x}$ 满足

(A + \delta A) \hat {x} = b, \| \delta A \| _ {\infty} \leq n ^ {2} \gamma_ {3 n} \rho_ {n} \| A \| _ {\infty}. \tag {2.25}

所以若 $\rho_{n}$ 比较小或随着 $n$ 变大时增长比较缓慢, 则当 $n$ 不是很大时, 部分选主元 Gauss 消去法是向后稳定的. 遗憾的是, 理论上无法保证 $\rho_{n}$ 比较小 [70, page 166].

定理2.23 部分选主元Gauss消去法能保证 $\rho_{n}\leq 2^{n - 1}$ ，且这个界是可以达到的.

事实上，(2.22)中的界几乎总是远远大于真正的 $\| \delta A\|$
在绝大多数情况下, 部分选主元 Gauss 消去法是向后稳定的, 但理论上也存在失败的例子.
全主元 Gauss 消去法是数值稳定的. 在大部分实际应用中, 部分选主元 Gauss 消去法与全主元 Gauss 消去法具有同样的数值稳定性.

2.4_误差分析

2.4 误差分析*

2.4.1 LU分解的舍入误差分析

2.4.2 Gauss消去法的舍入误差分析