CS205A Lecture 3 More LU; conditioning and sensitivity

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第三讲，这一讲结束了LU分解的内容，介绍敏感性和病态性。

更多的$LU$

上一次的讨论中我们介绍了$LU$分解，但实际中并不是每个矩阵都能进行$LU$分解，实际中可能会交换列，于是有如下恒等式：

$$\underbrace {(E_k...E_1)}_{消除矩阵}.A.\underbrace {(P_1...P_l)}_{置换矩阵} .\underbrace {(P_l^T...P_1^T)}_{置换矩阵的逆} \vec x = (E_k...E_1) \vec b$$

经过操作后，${(E_k…E_1)}.A.{(P_1…P_l)}$为上三角矩阵，于是

$$A=LUP$$

其中$L$是下三角矩阵，$U$是上三角矩阵，$P$是置换矩阵。

敏感性分析

这一部分主要讨论扰动对于线性方程组的影响，具体来说，我们考虑

$$(A+\delta A)\vec x = \vec b +\delta \vec b$$

讨论这个问题，我们需要度量大小的工具，这就引入了向量范数的概念。

向量范数和矩阵范数

向量范数：

向量范数是一个函数：$||.||:\mathbb R^n \to [0, \infty)$，满足如下条件

1. $||\vec x || =0 \Leftrightarrow \vec x = 0​$
2. $\forall c \in \mathbb R, \vec x \in \mathbb R^n, ||c\vec x||=|c|||\vec x||​$
3. $\forall \vec x ,\vec y \in \mathbb R^n ,||\vec x +\vec y|| \le ||\vec x|| +||\vec y||​$

我们这里讨论的一般都是$l_p$范数：

$$||\vec x ||_p = (\sum_{i=1}^n |x_i|^p)^{1/p}$$

作为补充，实际中还有$l_\infty $范数：

$$||\vec x ||_\infty =\max_{1\le i\le n}|x_i|$$

那么上述定义的函数是否是范数呢？实际上，条件1，2很好验证，条件3需要使用Holder不等式，具体的证明可以参考我的另一篇博客（传送门）。

在某种程度上，上述范数都是等价的，这里给出等价范数的概念。

等价范数

两个范数$||.||, ||.||’​$等价，如果存在常数$c_{low},c_{high}​$，使得对所有的$\vec x \in \mathbb R^n​$，下式成立

$$c_{low}||\vec x || \le ||\vec x||' \le c_{high}||\vec x||$$

在这个定义下，我们有如下定理：

定理 3.2

$$\mathbb R^n上所有范数都等价。$$

这个定理告诉我们$l_ p$范数都等价，但实际中用处不大，因为常数$c_{low},c_{high}$可能非常大。

这里补充介绍矩阵范数，对于$A\in \mathbb R^{m\times n}$，我们定义如下范数：

$$||A||_{\text{Fro}} = \sqrt{\sum_{ij}a_{ij}^2}$$

实际中，上述定义的范数很少使用，因为理解矩阵$A$的结构的优先方式是它对向量的作用，即当$A$乘以任意的$\vec x ​$时可能的结果，在这种想法下，我们给出诱导范数的定义。

诱导范数：

$\mathbb R^{m\times n}$上的范数由$\mathbb R^n$上的范数$||.||$诱导：

$$||A|| \equiv \max \{||A\vec x||: ||\vec x||=1 \}$$

注意到$||c\vec x || =|c|||\vec x||$，所以上述定义等价于

$$||A|| =\max_{\vec x \in \mathbb R^n \setminus \{0\}} \frac{||A\vec x||}{||\vec x||}$$

考虑几个特殊的例子：

1. $l_1​$范数的诱导范数，使用原始定义，我们有

   $$\sum_{i=1}^n |x_i|=1$$

   计算$||A\vec x||_1​$可得：

   $$\begin{aligned} ||A\vec x||_1 &=\sum_{i=1}^m \sum_{j=1}^n |a_{ij}||x_j|\\ &=\sum_{j=1}^n\sum_{i=1}^m |a_{ij}||x_j|\\ &\le \sum_{j=1}^n (\max_{1\le j\le n} \sum_{i=1}^m |a_{ij}|)|x_j| \\ &=(\max_{1\le j\le n} \sum_{i=1}^m |a_{ij}|)\sum_{j=1}^n |x_j| \\ &=\max_{1\le j\le n} \sum_{i=1}^m |a_{ij}| \end{aligned}$$

   所以我们有

   $$||A||_1 =\max_{1\le j\le n} \sum_{i=1}^m |a_{ij}|$$

2. $l_ \infty ​$范数的诱导范数，使用原始定义，我们有

   $$\max_{1\le i \le n} |x_i|=1$$

   计算$||A\vec x||_\infty $可得：

   $$\begin{aligned} ||A\vec x||_\infty &=\max_{1\le i\le m} \sum_{j=1}^n |a_{ij}||x_j|\\ &\le \max_{1\le i\le m} \sum_{j=1}^n |a_{ij}| \end{aligned}$$

   所以我们有

   $$||A||_{\infty} =\max_{1\le i\le m} \sum_{j=1}^n |a_{ij}|$$

3. $l_2​$范数，使用原始定义，我们有

   $$||\vec x ||_2 =1$$

   我们的目标是最大化

   $$||A\vec x ||_2$$

   由$l_2$范数的定义可知，上述问题等价于在如下条件

   $$\vec x ^T x =1$$

最大化

$$\vec x ^T A^T A\vec x$$

构造拉格朗日乘子：

$$L(\vec x ,\lambda )= \vec x ^T A^T A\vec x -\lambda(\vec x^T \vec x -1)$$

分别关于$\lambda ,\vec x $求梯度可得：

$$\begin{eqnarray*} \nabla_{\vec x } L(\vec x ,\lambda ) &&= 2A^TA \vec x -2\lambda \vec x \tag1 \\ \nabla_{\lambda } L(\vec x ,\lambda ) &&=\vec x^T \vec x - 1\tag2 \end{eqnarray*}$$

求解(1)可得

$$A^T A \vec x =\lambda \vec x$$

带回目标式可得

$$||A\vec x ||_2^2 =\vec x ^T A^T A\vec x = \lambda \vec x ^T \vec x =\lambda$$

所以我们有

$$||A||_2^2 =\max \{A^TA的特征值\}$$

还有一个问题，这样定义的$||A||$是否是范数呢？只要验证是否满足三个性质即可。

条件1：$||A || =0 \Leftrightarrow A = 0​$

$||A||=0$ 等价于任取$\vec x \in \mathbb R^n $，我们有

$$||A\vec x ||=0$$

因为$||.||$是范数，所以必然有

$$A\vec x \equiv0$$

由$\vec x​$的任意性，这说明$A=0​$。

条件2：$\forall c \in \mathbb R,A \in \mathbb R^{m\times n}, ||cA||=|c|.||A||$

$\forall c \in \mathbb R​$，我们有

$$\begin{aligned} ||c A||& =\max \{||cA\vec x||: ||\vec x||=1 \}\\ &=\max \{|c|||A\vec x||: ||\vec x||=1 \}\\ &=|c|\max \{||A\vec x||: ||\vec x||=1 \}\\ &=|c|||A|| \end{aligned}$$

条件3：$\forall A,B \in \mathbb R^{m\times n} ,||A +B|| \le ||A|| +||B||​$

$\forall A,B \in \mathbb R^{m\times n}​$，以及满足$||\vec x||=1 ​$的$\vec x ​$，我们有

$$\begin{aligned} ||(A+B)\vec x || &=||A \vec x + B\vec x||\\ &\le ||A \vec x|| + ||B\vec x|| \\ &\le ||A|| + ||B|| \end{aligned}$$

其中最后一个不等号是由$||A||​$的定义。

所以

$$||A+B||= \max \{||(A+B)\vec x||: ||\vec x||=1 \} \le ||A||+||B||$$

这说明上述定义的函数为范数。为了后续讨论，这里补充两个性质：

$$\begin{eqnarray*} ||AB||&&\le ||A||.||B|| \tag 3 \\ ||A\vec x|| && \le ||A||.||\vec x|| \tag 4 \end{eqnarray*}$$

其中$\vec x$是任意向量。

证明：首先证明(4)，利用等价定义：

$$||A|| =\max_{\vec x \in \mathbb R^n \setminus \{0\}} \frac{||A\vec x||}{||\vec x||}$$

那么显然有

$$\begin{aligned} \frac{||A\vec x||}{||\vec x||}& \le ||A|| \\ ||A\vec x||&\le ||A||.||\vec x|| \end{aligned}$$

因此(4)得证。接下来利用(4)证明(3)，任取$\vec x ​$：

$$\begin{aligned} ||AB \vec x || &=||A(B\vec x) ||\\ &\le ||A|| .||B\vec x|| \\ &\le ||A|| .||B||. ||\vec x|| \end{aligned}$$

所以

$$\frac{||AB \vec x ||}{||\vec x||} \le ||A|| .||B||$$

对左边取最大值可得：

$$||AB|| \le ||A|| .||B||$$

条件数

回到之前介绍的问题：

$$(A+\delta A)\vec x = \vec b +\delta \vec b$$

我们对问题的建模如下：

$$(A+ \epsilon.\delta A)\vec x(\epsilon) = \vec b +\epsilon.\delta \vec b \tag 5$$

两边关于$\epsilon ​$取微分可得

$$\delta A.\vec x +(A+ \epsilon.\delta A) \frac{d\vec x }{d \epsilon} =\delta \vec b$$

令$\epsilon =0$可得

$$\delta A.\vec x(0) + A\frac{d\vec x }{d \epsilon} \lvert_{\epsilon =0} =\delta \vec b$$

变形可得

$$\frac{d\vec x }{d \epsilon} \lvert_{\epsilon =0} =A^{-1}(\delta \vec b-\delta A.\vec x (0)) \tag 6$$

对$\vec x (\epsilon ) $进行泰勒展开可得

$$\vec x (\epsilon)= \vec x (0) +\epsilon \vec x'(0) +O(\epsilon^2)$$

在(5)中令$\epsilon =0$可得

$$A\vec x (0)= \vec b \tag 7$$

接下来考虑相对误差：

$$\begin{eqnarray*} \frac{||\vec x(\epsilon) -\vec x(0)||}{||\vec x(0)||} &&= \frac{||\epsilon \vec x'(0) +O(\epsilon^2)||}{||\vec x(0)||}&& (泰勒展开) \\ &&= \frac{||\epsilon A^{-1}(\delta \vec b-\delta A.\vec x (0)) +O(\epsilon^2)||}{||\vec x(0)||} &&(带入(4)) \\ &&\le \frac \epsilon {||\vec x(0)||} {(|| A^{-1}\delta \vec b||+||A^{-1}\delta A.\vec x (0)||) +O(\epsilon^2)} &&(||A+B||\le ||A||+||B||) \\ &&\le \frac \epsilon {||\vec x(0)||} {(|| A^{-1}||.||\delta \vec b||+||A^{-1}||.||\delta A||.||\vec x (0)||) +O(\epsilon^2)} &&(||AB||\le ||A||.||B||) \\ &&\le \epsilon || A^{-1}|| {\Big(\frac{||\delta \vec b||}{||\vec x(0)||}+||\delta A||\Big) +O(\epsilon^2)}\\ &&= \epsilon || A^{-1}||.||A|| \Big(\frac{||\delta \vec b||}{||\vec x(0)||.||A||}+ \frac{||\delta A||}{||A||}\Big)+O(\epsilon^2) \\ && \le \epsilon || A^{-1}||.||A|| \Big(\frac{||\delta \vec b||}{||\vec b||}+ \frac{||\delta A||}{||A||}\Big)+O(\epsilon^2) &&(A\vec x (0)= \vec b\Rightarrow ||A\vec x (0)||=||\vec b|| \le ||A||.||\vec x (0)||) \end{eqnarray*}$$

定义

$$\kappa = ||A||.||A^{-1}||, D= \frac{||\delta \vec b||}{||\vec b||}+ \frac{||\delta A||}{||A||}$$

那么

$$\frac{||\vec x(\epsilon) -\vec x(0)||}{||\vec x(0)||} \le \epsilon.D .\kappa +O(\epsilon^2)$$

这说明$\vec x $的相对误差由两项控制，一是$A,\vec b$的相对误差之和$D$，二是$\kappa $，$\kappa $也被称为$A$的条件数，具体定义如下。

矩阵的条件数：

$A\in \mathbb R^{n\times n}​$在范数$||.||​$下的条件数为：

$$\text{cond} A = ||A||.||A^{-1}||$$

如果$A$不可逆，那么定义

$$\text{cond} A = \infty$$

考虑矩阵条件数的一些性质：

由不等式(3)

$$||AB|| \le ||A||.||B||$$

可得

$$\begin{aligned} \text{cond} A &= ||A||.||A^{-1}|| \\ &\ge ||A.A^{-1}||\\ &=||I_n|| \\ & =\max_{\vec x \in \mathbb R^n \setminus \{0\}} \frac{||I_n\vec x||}{||\vec x||}\\ &=1 \end{aligned}$$

这说明矩阵的条件数都大于等于$1$。

我们对$||A^{-1}||​$变形可得：

$$\begin{aligned} ||A^{-1}|| & =\max_{\vec x \in \mathbb R^n \setminus \{0\}} \frac{||A^{-1}\vec x||}{||\vec x||}\\ &=\max_{\vec y \in \mathbb R^n \setminus \{0\}} \frac{||\vec y||}{||A\vec y||}& (\vec y = A^{-1}\vec x ) \\ &= \Big( \min_{\vec y \in \mathbb R^n \setminus \{0\}} \frac{||A\vec y||}{||\vec y||} \Big)^{-1} \end{aligned}$$

所以

$$\text{cond} A = \Big(\max_{\vec x \in \mathbb R^n \setminus \{0\}} \frac{||A\vec x||}{||\vec x||}\Big) \Big( \min_{\vec y \in \mathbb R^n \setminus \{0\}} \frac{||A\vec y||}{||\vec y||} \Big)^{-1}$$

注意到矩阵的条件数涉及到计算$A^{-1}$，但这正是我们要避免的，所以实际中要对条件数进行估计：利用

$$||A^{-1} \vec x || \le ||A^{-1}||.|| \vec x ||$$

可得

$$\text{cond} A = ||A||.||A^{-1}|| \ge \frac{||A||.||A^{-1} \vec x ||}{||\vec x ||}$$