大数据计算方法 课件 chap5-矩阵特征值奇异值

1大数据计算方法Chap5：矩阵的特征值与奇异值计算计算矩阵特征值的基本方法（复习）矩阵的奇异值分解计算特征值/奇异值的QR算法计算特征值/奇异值的Krylov子空间迭代法Outline2计算矩阵特征值的基本方法幂法与反幂法3特征值分解及其计算特征值计算的方法求解特征方程？计算方程中多项式系数的过程是数值敏感的高阶多项式方程(分线性方程)求根:准确度?计算量?例：

,比小一点，准确特征值为1

,但,算出两个根均为1算矩阵特征值的方法可用于解多项式方程幂法(poweriteration)求最大的特征值(主特征值)、及对应的特征向量条件：主特征值是唯一的(对实矩阵它一定是实的)是伴随矩阵Cn的特征多项式roots命令(另,NCM书第10.4节)4~7

10-9

特征值、特征向量的计算

5(PageRank算法)

每步迭代后做正交化矩阵的奇异值分解矩阵的奇异值、奇异向量奇异值分解及证明有关性质奇异值计算的敏感性6

7

到1维子空间的投影矩阵是?(singularvaluedecomposition)

0

矩阵奇异值/奇异向量

8

奇异值分解(SVD)

nn9特征值分解(r<n)(正交阵)线性代数领域的“瑞士军刀”思路:设

,

奇异值分解(SVD)证明(续)要证明的存在性根据补齐正交单位向量得到正交阵所以，存在性得证!且矩阵

唯一确定10U1为m

r列正交阵和唯一吗?非零奇异值对应的,基本上唯一矩阵奇异值/奇异向量

11

v1vrvnvr+1

u1ur

ur+1um

(m-r维)(n-r维)(r维)r维

()

rur

1u1

............奇异值分解(SVD)简化SVD分解若mn,则秩r

n,由于r常

不确定，得简化SVD为矩阵的2-范数12

------------

svd(A,'econ')

Matlab:[U,S,V]=svd(A);

s=svd(A);最大

奇异值

奇异值分解(SVD)

13注:不总成立

(F-范数下的“右逆”)

RogerPenrose,2020Nobel

PrizeforPhysics

奇异值分解(SVD)

14

+…对角阵的

奇异值是什么?

奇异值分解(SVD)eigshow演示(NCM包)2阶方阵的特征向量/奇异向量找正交的两个向量{x,y}，使得

Ax

Ay

(两对向量分别是右/左奇异向量)例子与Matlabs=svd(A);[U,S,V]=svd(A)一般，奇异值与特征值不同15思考:

得到的Ax,Ay为何总沿椭圆的轴方向?>>A=gallery(3)>>[U,S,V]=svd(A)奇异值计算的敏感性敏感性分析

为正交阵，则奇异值的绝对变动量不超过扰动矩阵的2-范数对大奇异值不敏感,对小奇异值(可能是0)仍可能很敏感例子

(奇异阵,特征值全0)>>A=gallery(5)>>formatlonge>>svd(A)(设)svd(A+eps*randn(5,5).*A)反复执行：结果：16详见NCM书第10.7节2-范数~10-11类似地分析特征值分解:

特征值/奇异值计算的QR算法基本QR迭代算法上Hessenberg约化与Givens迭代位移技术与实用的QR算法对称阵奇异值的计算非对称阵17QR算法QR迭代算法“二十世纪十大算法”之一，计算中小规模矩阵所有特征值的稳定、有效的方法实Schur分解:,Q为正交阵,S为仅含1阶/2阶对角块的分块上三角阵(拟上三角阵)QR算法是得到S的一个迭代过程：

,k=0,1,2,…基本QR算法:直接对A(k)做QR分解得到Qk不保证收敛,且每个迭代步计算量大实用的QR算法:1).先将A正交

约化为上Hessenberg阵T;2).,k=0,1,2,…,采用稀疏矩阵技巧算Qk18J.G.F.Francis和V.N.Kublanovskaya各自发明A(k)A(k+1)A(0)=AAT收敛性改善,计算效率高！(2阶块对应非实特征值)QR算法

……19000~10n3/3flops

一个QR迭代步的计算对上Hessenberg矩阵T

变执行QR迭代,得到拟上三角阵S采用Givens旋转(以4阶矩阵为例)T(k+1)仍是上Hessenberg阵!QR算法20若T(k)三对角阵,则T(k+1)也是,一个QR迭代计算量~O(n)(做QR分解),k=0,1,2,…(每个QR迭代步都是一系列正交相似变换)QR算法--实对称阵

21(做QR分解),k=0,1,2,…(变换成它需4n3/3flops)是对角阵处理实对称阵的QR算法(采用Wilkinson位移)

QR算法--实对称阵22

矩阵第i行已收敛!上Hessenberg(三对角)阵的QR迭代Wilkinson位移c为较小的常数

把Householder变换、Givens旋转依次作用到单位阵上即得到特征向量矩阵QR算法--实对称阵

23

演示程序eigsvdgui

(特征值有解析解,见NCM习题10.4)导致

QR算法--实对称阵隐式Q定理设A实对称,Q和V是两个正交阵,QTAQ和VTAV都是三对角阵.若Q的第1列与V的第1列相等,q1=v1,则Q和V本质上相等,即qi=

vi,i=2,…,n隐式位移技术一个QR迭代步Givens旋转实现QR分解,

q1由参数c和s定,它们又由24(显式位移),其中Q是对做QR分解得到c-ss

c11

xxxx11

q1再做后续旋转变为三对角可将G1直接作用于T(k)

QTAQ与VTAV本质相等确定对角元等,其他绝对值等两个场合

,其第1列由决定本质相等,

但更高效

(不存)…QR算法--奇异值奇异值的计算(A的奇异值是ATA的特征值)对A作左/右正交变换不改变奇异值

m

n用QR法求BTB(对称三对角)的特征值基于Givens旋转的隐式位移QR迭代第1个旋转阵考虑

BTB

(及可能的位移)BTB的第1列部分(双对角化)使HAW为双对角阵!

…,

且相当于做了QR迭代QR算法–非对称阵

若求特征向量矩阵,~5n3

flops

25(向后误差分析)Matlab中有关命令及其他eig命令-主要对稠密矩阵d=eig(A);返回所有特征值，使用QR算法[V,D]=eig(A);返回特征值和特征向量矩阵(可能奇异阵)

(内部处理可能会对矩阵元素进行比例调整，提高数值稳定性)可用于中小规模的矩阵eigs命令针对较大型(稀疏)的矩阵(Lanczos/Arnoldi算法)d=eigs(A,k);返回最大的k个特征值(k缺省为6)[V,D]=eigs(A,k);返回最大的k个特征值与相应特征向量hess命令:正交相似变换生成上Hessenberg阵schur命令:矩阵的Schur分解27LAPACK程序包T=schur(A);[U,T]=schur(A);相当于eig没做完还可算最小,或最接近某

值的特征值区分A是

实的或复的Krylov子空间迭代法Arnoldi过程Lanczos过程Lanczos算法非对称矩阵与SVD计算

Krylov子空间方法29比幂法收敛快(迭代步少)、能求更多特征值稀疏矩阵变得稠密!Householder变换Givens旋转矩阵向量乘可以!

Arnoldi过程30...注意：其中

可任意!...nxnnxn

wj=Avjfori=1toj

hij=viTwj

wj

=wj

-hijviend

Arnoldi-MGSv1怎么取值,得到结果与Householder约化方法一致?(隐式Q定理)

若=0,则Hk的特征值是A的特征值！

Lanczos过程--实对称阵31易证明:特征值

是T的k阶顺序主子阵，它的特征值与T的有何关系？

(差)称为Lanczos过程

Lanczos过程--实对称阵32随k增大逼近;一般对

某个k<<n,已足够准!k增大j较大时

收敛慢

Lanczos算法--实对称阵33第j个特征值的残