数值的稳定性与条件数

当输入d受到扰动时,输出f(d) 的扰动情况

目的:解决病态问题

条件数

  • A 数据矩阵 n*n
  • b 数据向量 n*1
  • x 未知向量 n*1

在这里我们研究x受A,或者b扰动的影响

A(x+δx)=b+δbAδx=δbδx=A1δb

||AB||<=||A||||B||{||δx||2<=||A1||2||δb||2||b||2<=||A||2||x||21||x||2<=||A||2||b||2

两边相乘

||δx||2||x||2<=||A1||2||A||2||δb||2||b||2

一起考虑A扰动的影响,可以得到

(A+δA)(x+δx)=bδx=(A+δA)1bA1b=A1[A(A+δA)](A+δA)1b=A1(δA)(A+δA)1b||δx||2||x+δx||2<=||A1||||A||2||δA||2||A||2

可以看出噪声(解向量x的误差)与某个数成正比,这个数被称为条件数

cond(A)=||A1||2||A||2

有性质

cond(AHA)=[cond(A)]2

如果矩阵A不是方阵,可以求出最小二乘解

Ax=bx=(AHA)1AHb

求此时的条件数

cond(AHA)=||AHA||2||(AHA)1||2=cond(A)2

条件数平方后变大,所以此时的最小二乘解不稳定

奇异值分解

奇异值分解定理对于矩阵A:m×n,存在正交或者酉矩阵U:m×m,V:n×n使得

A=UΣVHΣ=[Σr000]diag(Σr)=[σ1,σ2...σr]r=rank(A)

$\sigma1,\sigma_2…\sigma_r,\sigma{r+1}=…\sigma_n=0$被称为A的奇异值

AV=UΣAvi={uiσii<=r0i>rUHA=ΣVHuiHA=σiviH

vi为右奇异向量,ui为左奇异向量

  • 矩阵A的奇异值分解式可以改写成向量表达式A=Σi=1rσiuiviH
  • 当矩阵的秩r=rank(A)<min(m,n)
    奇异值分解可以被简化为
A=UrΣrVrH

被称为截断奇异值分解,
只取前r个非0度奇异值

奇异值分解和特征分解的关系

AHA=VΣUHUΣVH=VΣ2VH
  • AHA的特征值是A奇异值的平方,是右奇异向量
  • AAH的特征值是A奇异值的平方,是左奇异向量AAH=U2UH
  • 广义逆A=VΣUH

    奇异值的性质

    范数性质

  • 诱导谱范数||A||spec=||A||2=σi()
  • f范数||A||F=sqrt<A,A>=tr(AH,A)=σi所以特征值之和=奇异值平方和λ1+λ2...+λr=σ12+σ22...+σr2

根据矩阵A的谱范数可以确定最大奇异值

酉不变性

A=UΣVH

在矩阵A的基础上再左乘或者右乘一个酉矩阵

B=PUΣVHQH

B的奇异值不变

奇异值与行列式

因为酉矩阵行列式绝对值为1

所以

|detA|=|det|=σ1σ2...σn

如果detA0表明A是非奇异的,若存在σi=0,datA=0,则A奇异,这是把σ称为奇异值的原因

奇异值与条件数

cond(A)=σ1/σp(p={m,n})

所以条件数总大于1

奇异值的内在含义,如果一个矩阵有一个奇异值为0,对于正方矩阵,代表,矩阵奇异,行列式为0,非正方矩阵代表秩亏缺

秩亏缺矩阵(LS)

应用奇异值分解求解最小二乘问题的方法常简称为奇异值分解方法。

Ax=bUΣVHx=bΣVHx=UHb

x=VHx,y=UHb

得到

Σx=y

我们的目标变为优化问题

min||Σxy||22=i=1r|σixiyi|2+i=r+1N|yi|2=0

得到最小范数解

xLS=i=1r(uiHb/σi)vi

相应的最小残差为

ρLS=||AxLSb||2=||[ur+1,..,um]Hb||2

有效秩的确定

如果要衡量衡量A,B的逼近程度,P,K分别为A、B的秩

A=i=1PσiuiviHB=i=1KσiuiviH
  • 谱范数法||AB||spec=σk+1
  • F范数法||AB||F=i=k+1Pσi2

    衡量标准

对应谱范数

ϵ=σkσ1>=5%

对应F范数(范数比方法)

V(k)=kσ2Pσ2=||Ak||F||A||F>=α

奇异值分解在图像视频压缩中的作用

在矩阵A稀疏的情况下

An×nAk=UkkVkH