东大考博数值分析－矩阵特征值与特征向量的计算

null第5章 矩阵特征值与特征向量的计算第5章 矩阵特征值与特征向量的计算 n阶方阵A的特征值是特征方程 det(A-E)=0 的根. Gerschgorin圆盘定理 设矩阵A=(aij)nn ,记复平面上以aii为圆心,以ri= 为半径的n个圆盘为 Ri=aiiri,i=1,2,…,n A的特征向量是齐次线性方程组 (A-E)x=0 的非零解. 则 (1)A的任一特征值至少位于其中一个圆盘内; (2)在m个圆盘相互连通(而与其余n-m个圆盘互不连通) 的区域内,恰有A的m个特征值(重特征值按重数记).例1 设矩阵 试讨论A的特征值的分布. 解 由A确定的3个圆盘分别为所以 315 -2<22 -63<-2例1 设矩阵 R1=-41, R2=2, R3=+42xy0-2-4-62345实际上， 1=4.20308 , 2=-0.442931 , 3=-3.76010null 适当选取非奇异对角矩阵D=diag(d1,d2,…,dn),则矩阵D-1AD与矩阵A有相同的特征值,且对角元素相同. 而矩阵D-1AD对应的n个圆盘为如上例,取D=diag(2,1,1),则有可见，R1是独立的,所以可得3.514.5 .§1 乘幂法和反幂法§1 乘幂法和反幂法 §1.1 乘幂法 乘幂法是用来求矩阵A按模最大的特征值和相应的特征向量的方法. 设A是单构矩阵, 即A有n个线性无关的特征向量. A的n个特征值为 |1  2  n 对应的特征向量为 x1,x2,…xn 线性无关. 我们要求1 和 x1 . null 乘幂法的基本思想是取初始向量v(0)Rn,作迭代 v(k+1) =Av(k) =Ak+1v(0) , k=0,1,2,… 产生迭代序列v(k). 由于x1,x2,…xn 线性无关, 从而有 v(0) =a1x1+a2x2+…+anxn 故有 v(1) = Av(0) v(k) = Av(1) v(k) = Akv(0) =a11kx1+a22kx2+…+annkxn (5.1) …………………………………………… =a11x1+a22x2+…+annxn =a112x1+a222x2+…+ann2xn null 1. 设|1>2n , 这时,(5.1)式可写成若a10, 则对充分大的k有 因而有 或取 而特征向量 x1  v(k).乘幂法的收敛速度取决于|2/1|的大小. 例2 求矩阵A的按模最大的特征值 解 取v(0)=(1,0)T ,计算v(k)=Av(k-1), 结果如下例2 可取0.41263 ,x1(0.017451,0.014190)T .null 对非零向量v,用max(v) 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示v的按绝对值最大的分量,称向量u=v/max(v)为向量v的 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 化向量. 例如, 设向量v=(2,1,-5,-1)T,则max(v)=-5,u=(-0.4,-0.2,1,0.2)T.可见规范化向量u总满足‖u‖=1. 乘幂法的规范化计算公式为: 任取初始向量u(0)=v(0) 0,计算由于null所以又由null其收敛速度由比值|2/1|来确定,其值越小收敛越快.所以因此,当|k-k-1|<时,可取: 1  k , x1  u(k) .例3 设 如用规范化乘幂法解例2,仍取u(0)=v(0)=(1,0)T,则有 故可取 1 0.412627, x1 (1,0.813138)T.用乘幂法求A的按模最大的特征值和相应特征向量.例3 设 解 取初值u(0)=v(0)=(1,1,1)T,计算得null 可取 1 6.000837, x1 (1,0.714316,-0.249895)T. 实际上,A的3个特征值分别为1=6,2=3,3=2.null 2. 设1=2==r,且 |1>r+1n ,这时,(5.1)式可写成若a1,a2,…,ar不全为零, 则对充分大的k有 由于a1x1+a2x2+…+arxr 是对应1的特征向量, 若仍记为x1 ,则有: v(k) 1kx1 ,故前面的结论仍然成立. 3. 设1=-2,且 |1=|2|>3 n ,这时,(5.1)式可写成则对充分大的k有 null v(2i)12i(a1x1+a2x2) , v(2i+1)12i+1(a1x1-a2x2)于是有 x1v(k+1)+1v(k) , x2v(k+1)-1v(k) 对于规范化的幂法，由于 u(k+2)=v(k+2)/k+2=Au(k+1)/k+2 =Av(k+1)/k+1k+2=A2u(k)/k+1k+2于是有例4 用乘幂法求矩阵 x1k+1u(k+1)+1u(k) , x2k+1u(k+1)-1u(k)的按模最大特征值和相应的特征向量。例4 用乘幂法求矩阵 解 取初始向量u(0)=v(0)=(1,1,2)T ,计算可得null§1.2 加速技术§1.2 加速技术由于所以,乘幂法收敛速度取决于比值|2/1|,当|2/1|1时,收敛是很慢的. 1.Aitken 加速方法由(5.2)式可知 x2=13u(13)-1u(12)=(0 , 0.631924 , 0.631924)T. x1=13u(13)+1u(12)=(4.315961, 8.631924, 8.631924)T, 实际上, A的特征值为1=4,2=-4,3=1.null可见,序列k线性收敛于1 .会达到加速收敛的目的. 构造Aitken序列 如把Aitken加速方法用于例3,则有null 2.原点位移法 作矩阵B=A-pE, 则B的特征值为mi=i-p(i=1,2,…,n),而且对应的特征向量相同.例5则对B应用乘幂法可达到加速收敛的目的。 解 由于A的特征值为1=6,2=3,3=2,故取p=2.5,则B的特征值为m1=3.5,m2=0.5,m3=-0.5,则如果选取p,使m1仍然是B的按模最大特征值，且满足取初始向量u(0)=v(0)=(1,1,1)T,由规范化计算公式:例5 用原点位移法求例3中矩阵A的按模最大的特征值和特征向量.null计算可得§1.3 反幂法这是因为|2/1|=1/2,而|m2/m1|=1/7,故对B应用乘幂法远比对A应用乘幂法收敛的快. 反幂法是求矩阵按模最小的特征值和相应特征向量的方法.取,16+2.5=6.000102,x1u(6)=(1,0.714287,0.249995)T§1.3 反幂法 设A是n阶非奇异矩阵, 其特征值为 |1|  |2|  …  |n-1| > |n| > 0对应的特征向量为x1,x2,…,xn, 则有A-1的特征值为对应的特征向量为xn,xn-1,…,x1. 要想求n和xn只需对A-1应用乘幂法,任取初始向量u(0)=v(0)0, 作null也可将上式改写成式(5.3)称为反幂法. 显然有每一步求v(k)需要求解线性方程组, 可采用LU分解法求解.例6 反幂法还可结合原点位移法应用.设已求得矩阵A的特征值i的某个近似值对B应用反幂法可求出精度更高的i和xi. 设已求得例3中矩阵A的特征值的近似值16.003,和相应的特征向量x1(1,0.714405,-0.249579)T, 试用带原点位移的反幂法求1和x1的更精确的值. 作原点位移,令B=A- E, 则B的特征值为 例6 解 取p=6.003, 作矩阵B=A-6.003E,则§2 Jacobi 方法取初始向量u(0)=(1,0.714405,-0.249579)T,对B用反幂法计算可得:可见收敛速度非常快,这是因为B的3个特征值为1=-4.003, 2=-3.003,3=-0.003,|3/2|0.000999很小. Jacobi方法是求实对称矩阵全部特征值和特征向量的一种矩阵变换方法。§2 Jacobi 方法 实对称矩阵A具有下列性质： （1）A的特征值均为实数； （2）存在正交矩阵R，使RTAR=diag(1,2,…,n),而 §2.1 平面旋转矩阵 R的第i个列向量恰为i的特征向量; 直接求正交矩阵R是困难的 . Jacobi提出用一系列所谓平面旋转矩阵逐次将A约化为对角矩阵.平面解析几何中的平面坐标旋转变换表示平面上坐标轴旋转角的变换. （3）若记A1=RTAR,则A1仍为对称矩阵. §2.1 平面旋转矩阵 在三维空间直角坐标系中,ox1y1平面绕着oz1轴旋转角的坐标变换为null Rpq()具有下列性质: 一般地, 在n维向量空间Rn中, 沿着xpyq平面旋转角的变换矩阵为称Rpq()为平面旋转矩阵. null 设实对称矩阵A=(aij)nn ,记B=RpqT()ARpq()=(bij)nn则它们元素之间有如下关系: （1）Rpq()为正交矩阵,即Rpq-1()=RpqT(); （2）如果A为对称矩阵, 则RpqT()ARpq()也为对称矩阵, 且与A有相同的特征值. （3）RpqT()A仅改变A的第p行与第q行元素,ARpq()仅改变A的第p列与第q列元素.null所以有从而有(5.5)、(5.6)式可得 如果apq0, 适当选取角, 使null只需角满足从而 如果取|apq|=若记于是 则上式可记为§2.2 Jacobi 方法 由式(5.7),令t=tan,则t满足方程 t2+2t-1=0 经典Jacobi算法是对A(0)=A施行一系列平面旋转变换:为保证||/4,取绝对值较小的根,有于是§2.2 Jacobi 方法 A(1)=R1TA(0)R1 ,A(2)=R2TA(1)R2 ,…, A(k)=RkTA(k-1)Rk ,…每一步变换选择A(k-1)=(aij(k-1))nn 的非对角线元素中绝对值最大者apq(k-1)(称为主元素)作为歼灭对象, 构造平面旋null 是给定的精度要求,则A的特征值可取为iaii(k),i=1,2,…,n.转矩阵Rk=Rpq(), 经变换得到A(k)=(aij(k))nn ,且apq(k)=0,这时由(5.8)式有从而由此递推得到 当k充分大时,或者(A(k))<,或者 另外,由于 A(k)=RkTA(k-1)Rk=RkTRk-1T…R1TAR1R2…Rk=RTAR 例7 用Jacobi 方法计算对称矩阵的全部特征值. 解 记 A(0)=A,取p=1,q=2,apq(0)=a12(0)=2,于是有因此,R=R1R2…Rk 的列向量xj (j=1,2,…,n)为A的近似特征向量.例7 用Jacobi 方法计算对称矩阵从而有null所以 再取p=2,q=3,apq(1)=a23(1)=2.020190,类似地可得以下依次有nullnull从而A的特征值可取为 12.125825, 28.388761, 34.485401 为了减少搜索非对角线绝对值最大元素时间, 对经典的Jacobi方法可作进一步改进. 1.循环Jacobi方法:按(1,2),(1,3),…,(1,n),(2,3), (2,4),…,(2,n),…,(n-1,n)的顺序, 对每个(p,q)的非零元素apq作Jacobi变换,使其零化,逐次重复扫描下去,直至(A)<为止. 2.过关Jacobi方法: 取单调下降收敛于零的正数序列k,先以1为关卡值,依照1中顺序,将绝对值超过1的非对角元素零化,待所有非对角元素绝对值均不超过1时,再换下一个关卡值2 ,直到关卡值小于给定的精度 .练习 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 练习题第131页 习题5 5-1, 5-5, 5-7, 5-9(2), 5-10 Jacobi方法具有方法简单紧凑,精度高,收敛较快等优点, 是计算对称矩阵全部特征值和相应特征向量的有效方法,但计算量较大,一般适用于阶数不高的矩阵.null课间休息