中国矿业大学：《数值分析》课程教学课件（讲稿，研究生）第十章 矩阵特征值问题的数值解法

第九章特征值问题的数值解法81幂法与反幂法s2 对称Jacobi迭代法S3.QR迭代法1

-1- 第九章 特征值问题的数值解法 §1 幂法与反幂法 §2 对称Jacobi迭代法 §3 QR迭代法

s1幂法与反幂法口回顾/设A是n阶方阵，若数2和非零向量x满足Ax=2x则称2的A的特征值，x为A的对应于2特征向量。Va是A的特征值台(aE-A)x=0，其中x±0台方程(aE-A)x=0有非零解2-aia2ain-a22a21azn特征多项式：f(a)=aE-Al.........-annanian2=a" -c,an-1 +... +(-1)n-' c,-,a +(-1)"c,特征方程：f()=aE-A=0

回顾 A n x Ax x A x A     设 是 阶方阵，若数 和非零向量 满足  则称 的 的特征值， 为 的对应于 特征向量。 .     ( ) 0 0 E A x x ，其中    方程( ) 0 E A x 有非零解 .是A的特征值    E A 0 11 12 1 21 22 2 1 2 1 1 1 1 ( ) ( 1) ( 1) ( ) 0 n n n n nn n n n n n n a a a a a a f E A a a a c c c f E A                             特征多项式： 特征方程 = ： . §1 幂法与反幂法

元/矩阵相似对角化：3可逆矩阵P,使得P-IAP：2其中(a,α,)为A的特征对，P=[α,α2,,α,]A可相似对角化台A有n个线性无关的特征向量(可构成R"的基底）。／实对称矩阵一定相似对角化：3正交矩阵Q,使得[2QTAQ=Q-AQ=元

1 1 1 2 P, ( , ) [ , , , ]. n i i n P AP A P                      矩阵相似对角化： 可逆矩阵 使得 其中 为 的特征对，  . n R A A n 可相似对角化  有 个线性无关的特征向量 (可构成 的基底)。  . 1 1 Q, T n Q AQ Q AQ                 实对称矩阵一定相似对角化： 正交矩阵 使得 

口幂法假设AeR"xn有n个线性无关的特征向量，A的n个特征值按模大小排列1, > ... ≥, 1对应的特征向量为x,x,,,x,(R"的一个基底)任取vER"(v≠0)，并设v在基底xj,x,,x,下的坐标为Vo =αxi +α,x, +...αa,xn (α, ±0)考察：V=Avoa,a'x,+a,a,x,+...+a,a,x,[ax +a,()x a,()=2kkx2k (α)x, +8k)X2k充分大x～Vk故8k→0(k→80)

1 2 1 2 | | | | | | , , , ( ) n n n n n A R n A n x x x R         假设 有 个 的特征向量， 的 个特征值按模大小排列 对应的特征 线性无关 向量为 的一个基底 0 0 0 1 2 ( 0) , , , n n 任取v R v v x x x   ，并设 在基底 下的坐标为 考察： 0 k k v A v  1 1 1 2 2 2 k k k n n n           x x x 1 2 2 1 1 1 2 1 ( ) ( ) k k k n n n x x x                   1 1 1   k k   x   由于 1 | | 1( 2, , ) i i n     故 0( ) k     k 1 1 k k k v x k x v     充分大 0 1 1 2 2 1 ( ) 0 n n v x x x         幂法

V,=Av=...=a(αx+&)Ax, = a,xi又因为x/Ax, =xT(ax)=a,x, x两边左乘x!x[ AxVTAV所以2.x;xVeVk问题福V如果|,>1,则=Av→(a→80),产生计算溢出V如果|,1,则=A→0(ak→0),V=0:非特征向量

又 因 为 1 1 1 1 1 1 1 1   T T T x Ax x x x x     所以 1 1 1 1 1 TT x Ax x x   T k k T k k v Av v v  Ax x 1 1 1   1T 两边左乘x 0 1 1 1 .   k k k k v A v x        问 题 1 0 1 | | 1, ( ), k k k  . 如果         则v A v 产生计算溢出； 1 0 1 | | 1, 0( 0), 0 : k k k k  . 如果        则v A v v 非特征向量；

具体算法u=Avuk1 取vR"，满足|vll,=1(要求α, 0)k =1,2,..m, = v, AvX则有limyk和 lim m, = ^,十k→xill2k→0UkAvk-YP.证明ukukbAkyu,uk-而 Av =(αx +), →0a*(α,x +e)x即→Xi[2]- ,x, + 8 ll22k+1aix(x, +5ka'(αx, +6r)ak+ (ax, +8k+1)2m =VAV, :[2"-ax+8xl -ax +=22kaixx +nk

具体算法 0 0 1 2 1 1( 0) n 取v R v    ，满足 要求 1 2 , 1,2, k k k k k T k k k u Av u v k u m v Av             1 1 1 2 lim lim . k k k k x v m x    则有    和 证明 2 k k k u v u  1 k 2 A k v u   0 0 2 k k A v A v   2 2 k 2 1 2 k k v u A u     0 1 1 1 ( ) 0 k k 而 A v x        k k ， 1 1 1 1 1 1 1 1 2 1 2 ( ) . k k k k k k x x v v x x x               ，即 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 2 2 ( ) ( ) k T k T k T k k k k k k k k k T k k k x x x x m v Av x x x x                                    

2选代结束标准:AV-mll,<83收敛速度：8,=0Z2为收敛因子，如果～1，则收敛很慢；2元4其他格式任取vE R"(α, 0)u, = Avk-1则 →X, m→±,(Im/ )。m, = max(u,)WkVLmk

k k k 2 2 迭代结束标准：Av m v    2 1 k k O             3 收敛速度： 2 2 1 1 1     为收敛因子，如果  ，则收敛很慢； 4 其他格式 1 max( ) k k k k k k k u Av m u u v m            0 1 ( 0) n 任取v R    1 1 1 (| | | |) k k k 则 v x m m     ，  

口反幂法1假设可逆矩阵A的值[,,…≥,，则A-的特征值≥…，将幂法用于A-，则可求得A的按模最小的特征值。>172位移反幂法假设是的近似值，求.及其对应的特征向量一般地,0.-.<-,l,(im),考虑矩阵A一元.的特征值，一元按模最小的特征值.一元对A-元,I应用反幂法：取v(α,+0)，u, =(A-mI)-'vk-1 (A-mI)u, = Vk-IUk,k =1,2,..ukll1mk=vTAVk→am则当k充分大时，V,是(A一元.I)-的近似特征向量，也是A的近似特征向量

1 2 1 1 1 1 | | | | | | | | 1 1 1 n n n n A A A A                 假设可逆矩阵 的值 ，则 的特征值 ，将幂法用于 ，则可求得 的按模最小的特征值。 2 位移反幂法 0 | | | |,( ) m m m i 一般地，         i m ， 考虑矩阵A I         m i m m m 的特征值 按模最小的特征值 对A I  m 应用反幂法： 假设   m m m 是 的近似值，求 及其对应的特征向量 反幂法 0 1 取v ( 0)   ， 1 1 1 2 ( ) ( ) , 1,2, k m k m k k k k k T k k k u A I v A I u v u v k u m v Av                     1 ( ) k m k v A I A   则当 充分大时, 是  的近似特征向量,也是 的近似特征向量。   m

82对称Jacobi迭代法口问题设A是n阶实对称矩阵，求A的所有特征值和对应的特征向量。口基本结论n阶实对称矩阵A一定可以正交相似对角化，即Q(QrQ=I),使得()22QTAQ=其中，2，…，入,是A的n个特征值

问题 §2 对称Jacobi迭代法 设A n A 是 阶实对称矩阵,求 的所有特征值和对应的特征向量。 基本结论 1 1 2 2 Q( ), Q Q=I T n T n n A Q A A Q    n                 阶实对称矩阵 一定可以正交相似对角化,即 使得 其中 ， ， ， 是 的 个特征值

口计算公式√2阶是对称矩阵的相似对角化aapppqA=(a±0a.pqapaaqpee利用Givens变换矩阵sinecosOCQ=cosO-sineS使得OAO变成对角矩阵，经计算c'ap -2csa p + sa,camμ + cs(ap-am)-s'apAQTAQ :c'am + cs(ap-a)-s'aca.. + 2csan + s'aDod0ppDO令c'ap + cs(ap -aqg)-s'apg = 0

计算公式 2 . 阶是对称矩阵的相似对角化 ( 0) pp pq pq qp qp qq a a A a a a a            利用Givens变换矩阵 cos sin sin cos c s Q s c                     T 使得Q AQ变成对角矩阵，经计算 2 2 2 2 2 2 2 2 ( ) ( ) 2 2 pq pp qq pq pq pp qq pq T pp pq qq qq pq pp c a cs a a s a c a cs a a c a csa s a Q AQ s a c a csa s a                    令 2 2 ( ) 0 pq pp qq pq c a cs a a s a    