8矩阵特征值

第八章矩阵特征值计算数值分析22:30:52NumericalAnalysis2本章内容特征值基本性质幂法与反幂法正交变换与矩阵分解QR方法22:30:52NumericalAnalysis3本讲内容特征值基本性质幂法幂法的加速反幂法22:30:52NumericalAnalysis4特征值性质Ax=x(C,x0)性质(1)特征值与特征向量()()AxxAIxx(2)kkAxxAxx(3)11,,BPAPAxxByyyPx(4)若A对称，则存在正交矩阵Q，使得12diag(,,,)TnQAQ22:30:52NumericalAnalysis5圆盘定理定理：(Gerschgorin圆盘定理)设是A的特征值，则i=1,2,...,n设A=(aij)Rnn，记1,C||niiiijjjiDaaGerschgorin圆盘1niiD若有m的圆盘互相连通，且与其它圆盘都不相连，则这m个圆盘内恰好包含m个特征值。22:30:52NumericalAnalysis6Rayleigh商定理：设A是n阶实对称矩阵，其特征值为则对任意非零向量x，有1(,)(,)nAxxxx100(,)(,)max,min(,)(,)nxxAxxAxxxxxx12n且称为矩阵A关于x的Rayleigh商。(,)()(,)AxxRxxx22:30:52NumericalAnalysis7(1)任取一个非零向量v0，要求满足(x1,v0)0(2)对k=1,2,...，直到收敛，计算幂法计算矩阵的主特征值（按模最大）及其特征向量假设：(1)|1||2|…|n|0(2)对应的n个线性无关特征向量为：x1,x2,...,xn计算过程：幂法（乘幂法，幂迭代）1kkvAv22:30:52NumericalAnalysis8幂法的收敛性收敛性分析012112(0)nnvxxx10111222nnnvAvxxx1111222kkkkknnnvAvxxx21112211kkknnnxxx111kx设21越小，收敛越快22:30:52NumericalAnalysis9幂法的收敛性当k充分大时，有111kkvx11111kkvx11kkvv又1kkvAv1kkAvv11kjkjvv(j=1,2,...,n)vk为1的近似特征向量22:30:52NumericalAnalysis10幂法的收敛性定理：设A有n个线性无关的特征向量，其特征值满足则由幂法生成的向量满足11111()lim,lim()kjkkkkkjvvxv123n注：幂法的收敛速度取决于的大小2122:30:52NumericalAnalysis11幂法111kkvx1||1,1|10,|改进方法：规范化1,kkkkkvuvAuv1kkvAv幂法中存在的问题11limkkxux22:30:52NumericalAnalysis12幂法1的计算1limkkv00kkkkkvAvuvAv1111112101011121knkiiikikkkknkiiiixxAvvAuAvxx22:30:52NumericalAnalysis13改进的幂法定理：设A有n个线性无关的特征向量，其特征值满足则由改进的幂法生成的向量满足111lim,limkkkkxuvx123n(1)任取一个非零向量v0，要求满足(x1,v0)0(2)对k=1,2,...，直到收敛，计算改进的幂法1,kkkkkvuvAuv22:30:52NumericalAnalysis14举例例：用改进的幂法计算下面矩阵的主特征值和对应的特征向量1.01.00.51.01.00.250.50.252.0A%改进的幂法clear;A=[1.0,1.0,0.5;1.0,1.0,0.25;0.5,0.25,2.0];v=[1,1,1].';tt=norm(v,inf);u=v/tt;fprintf('v0''=[%.4f,%.4f,%.4f]\n',v(1),v(2),v(3));n=20;fork=1:nv=A*u;tt=norm(v,inf);u=v/tt;fprintf('iter=%2d,u''=[%.4f,%.4f,%.4f],norm(v)=%.7f\n',...k,u(1),u(2),u(3),tt);end22:30:52NumericalAnalysis15幂法的加速幂法的收敛速度取决于的大小21r当r接近于1时，乘幂法收敛会很慢！幂法的加速：原点平移法令B=A–pI，则B的特征值为：i-p选择适当的p满足：(1)(j=2,...,n)1||||jpp2211maxjjnpp(2)用幂法计算矩阵B的主特征值：1-p保持主特征值加快收敛速度带位移的幂法22:30:52NumericalAnalysis16举例例：用带位移的幂法计算下面矩阵的主特征值和对应的特征向量，取p=0.751.01.00.51.01.00.250.50.252.0A%幂法的加速－－原点平移法clear;A=[1.0,1.0,0.5;1.0,1.0,0.25;0.5,0.25,2.0];p=0.75;v=[1,1,1].';tt=norm(v,inf);u=v/tt;fprintf('v0''=[%.4f,%.4f,%.4f]\n',v(1),v(2),v(3));n=20;fork=1:nv=A*u-p*u;tt=norm(v,inf);u=v/tt;fprintf('iter=%2d,u''=[%.4f,%.4f,%.4f],norm(v)+p=%.7f\n',...k,u(1),u(2),u(3),tt+p);end22:30:52NumericalAnalysis17反幂法计算矩阵的按模最小的特征值及其特征向量假设：(1)|1||2|…|n-1||n|0反幂法(2)对应的n个线性无关特征向量为：x1,x2,...,xnA-1的特征值为：1211111nn对应的特征向量仍然为x1,x2,...,xn反幂法：对矩阵A-1使用幂法22:30:52NumericalAnalysis18反幂法定理：设A有n个线性无关的特征向量，其特征值满足则由反幂法生成的向量满足1lim,limnkkkknnxuvx1210nn(1)任取一个非零向量v0，要求满足(x1,v0)0(2)对k=1,2,...，直到收敛，计算反幂法11,kkkkkvuvuvA22:30:52NumericalAnalysis19反幂法的加速反幂法的收敛速度取决于的大小1nnr当r接近于1时，反乘幂法收敛会很慢！可以使用原点平移法对反幂法进行加速问题：如何选择参数p？离n越近越好（但不能相等）22:30:52NumericalAnalysis20Rayleigh商加速Rayleigh商加速(1)任取一个非零向量v0，要求满足(x1,v0)0(2)对k=1,2,...，直到收敛，计算11(,),(,)kkkkkkkkkkkvuAuApIupvuuvulimnkknxux(,)(,)lim(,)(,)kknnnkkknnuAuxAxuuxx22:30:52NumericalAnalysis21几点注记带位移的反幂法中需要计算11kkkApvuI1kkkuIvAp带位移的反幂法可以用于计算任何一个特征值k将参数p取为k附近若已知特征值，计算特征向量时，可使用带位移的反幂法令p足够靠近k22:30:52NumericalAnalysis22本讲内容正交变换QR迭代Householder变换Givens变换QR分解Schur分解Hessenberg矩阵Householder变换1.引言讨论两个问题:.)1(伯格矩阵海森似变换约化实矩阵为上用初等反射阵作正交相.)2(对角矩阵的问题对称似变换约化对称矩阵为用初等反射阵作正交相.值问题或对称对角矩阵的特征格矩阵题就转化为求上海森伯于是，原矩阵特征值问阶矩阵则且设nRTn,1,.rHouseholde,)(矩阵也称矩阵或镜面反射称为初等反射都有初等反射阵对于因此,0u,.2)(22uuuIuHT,,)0,,0,1(0),,,(11121，使得则总存在初等反射阵，设约化定理σeHxuuIHexTTTnxxx)定理14(其中.)(,),,,(,)sgn(1222121121xxxxxTnuexux般矩阵为上海森伯格阵用正交相似变换约化一2..),,,(,1131211)1(221)1(12112122221112111TnnnnnnnaaaaaaaaaaaaacAcAAA其中步约化：设第),1否则这步不需做不妨0(c,111111111，使得取初等反射阵ecRuuIRσT其中.)(,),,,(,)sgn(2111221211131121111121211aaaaaσTnuecuc,00)2(222)2(12)2(11)2()2(3)2(2)2(3)2(33)2(32)2(2)2(23)2(221)2(1)2(13)2(12111)1(221111)1(12111112AcAARARcRRAUAUA0nnnnnnnaaaaaaaaaaaaaa，则令111RU.),,()2(2)2(322Tnaac其中)()(1,)(,)(,1)(1,1)(,1)(,1)1(1,12)(2)(1,2)(2)1(1,2)2(221)(1)(1,1)(1)1(1,1)2(12)1(1111111111121,,,,1,,1knnkknkknknkkkkkkkkkkkkkkknkkkkkkknkkkkkkkkkkkkkaaaaaaaaaaaaaaaaaaakkUUAUUUAUAUUU使得步，即有步约化：假定已完成第第,)(22)(12)(11knkkkkkAcAA0.)(11阶上海森伯格矩阵是其中kkA,,11，使取初等反射阵不妨ecRuuIRckkkTkkkkkσ0其中.)(,),,,(,)sgn()(,12221)(,)(,2)(,112)(,1kkkkkkkTkknkkkkkkkkkkkkkkkaaaaaσuecuc.)1(221)1(12)1(11)(22)(12)(111kkkkkkkkkkkkkkkkkkkAcAARARcRRAAUAUARIU0000，则令.1)1(11阶上海森伯格矩阵是其中kkA