CS205A Lecture 3 More LU; conditioning and sensitivity

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

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

更多的$LU$

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

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

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

敏感性分析

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

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

向量范数和矩阵范数

向量范数

向量范数是一个函数:$||.||:\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$范数:

作为补充,实际中还有$l_\infty $范数:

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

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

等价范数

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

在这个定义下,我们有如下定理:

定理 3.2

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

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

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

诱导范数

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

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

考虑几个特殊的例子:

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

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

    所以我们有

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

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

    所以我们有

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

    我们的目标是最大化

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

最大化

构造拉格朗日乘子:

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

求解(1)可得

带回目标式可得

所以我们有

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

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

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

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

由$\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​$,我们有

条件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 ​$,我们有

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

所以

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

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

证明:首先证明(4),利用等价定义:

那么显然有

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

所以

对左边取最大值可得:

条件数

回到之前介绍的问题:

我们对问题的建模如下:

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

令$\epsilon =0$可得

变形可得

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

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

接下来考虑相对误差:

定义

那么

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

矩阵的条件数

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

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

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

由不等式(3)

可得

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

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

所以

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

可得

本文标题:CS205A Lecture 3 More LU; conditioning and sensitivity

文章作者:Doraemonzzz

发布时间:2019年03月17日 - 09:10:00

最后更新:2019年05月27日 - 15:32:59

原始链接:http://doraemonzzz.com/2019/03/17/CS205A Lecture 3 More LU; conditioning and sensitivity/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。