第8章 矩陣特征值與特征向量的計(jì)算.ppt

研究生學(xué)位課程數(shù)值分析 1 第8章矩陣特征值和特征向量的計(jì)算 很多工程計(jì)算中 會(huì)遇到特征值和特征向量的計(jì)算 如 機(jī)械 結(jié)構(gòu)或電磁振動(dòng)中的固有值問(wèn)題 物理學(xué)中的各種臨界值等 這些特征值的計(jì)算往往意義重大 求解線性方程組的迭代法 重要一點(diǎn)是判斷迭代法的收斂性 判斷方法之一就是看迭代矩陣的特征值的模是否都小于1 研究生學(xué)位課程數(shù)值分析 2 PA 是 的高次的多項(xiàng)式 它的求根是很困難的 設(shè)法通過(guò)數(shù)值方法是求它的根 通常對(duì)某個(gè)特征值 可以用些針對(duì)性的方法來(lái)求其近似值 若要求所有的特征值 則可以對(duì)A做一系列的相似變換 收斂 到對(duì)角陣或上 下 三角陣 從而求得所有特征值的近似 n階方陣A的特征值是特征方程PA det A E 0的根 A的特征向量是齊次線性方程組 A E x 0的非零解 研究生學(xué)位課程數(shù)值分析 3 定理1 A Rn n 1 n為A的特征值 則 2 A的行列式值等于全體特征值之積 即 1 A的跡數(shù)等于特征值之和 即 特征根和特征向量的基本結(jié)論 定理2設(shè) 為A Rn n的特征值且Ax x 其中x不為0 則 1 c 為cA的特征值 c為常數(shù)且不為0 2 p為A pI的特征值 即 A pI x p x 3 k為Ak的特征值 4 設(shè)A為非奇異陣 那么且為特征值 即 研究生學(xué)位課程數(shù)值分析 4 定義設(shè)矩陣A B Rn n 若有可逆陣P 使則稱A與B相似 定理若矩陣A B Rn n且相似 則 1 A與B的特征值完全相同 2 若x是B的特征向量 則Px便為A的特征向量 研究生學(xué)位課程數(shù)值分析 5 8 1冪法和反冪法 8 1 1冪法 冪法是用來(lái)求矩陣A按模最大的特征值和相應(yīng)的特征向量的方法 也稱為主特征值和主特征向量 設(shè)A是單構(gòu)矩陣 即A有n個(gè)線性無(wú)關(guān)的特征向量 A的n個(gè)特征值為 1 2 n 對(duì)應(yīng)的特征向量為 1 2 n線性無(wú)關(guān) 我們要求 1和 1 冪法的基本思想是取初始非零向量x0 Rn 作迭代xk 1 Axk Ak 1x 0 k 0 1 2 產(chǎn)生迭代序列 xk 由于 1 2 n線性無(wú)關(guān) 從而有x0 1 1 2 2 n n 8 3 研究生學(xué)位課程數(shù)值分析 6 故有xk Akx0 1 1k 1 2 2k 2 n nk n 設(shè) 1 2 n 這時(shí) 上式可寫成 若 1 0 則對(duì)充分大的k有 因而有 從而特征向量 1 xk 乘冪法的收斂速度取決于 2 1 的大小 研究生學(xué)位課程數(shù)值分析 7 實(shí)際計(jì)算時(shí) 常把每一步計(jì)算的迭代向量xk規(guī)范化 對(duì)非零向量x 用max x 表示x的按絕對(duì)值最大的分量 稱向量y x max x 為向量x的規(guī)范化向量 例如 設(shè)向量x 2 1 5 1 T 則max x 5 y 0 4 0 2 1 0 2 T 可見(jiàn)規(guī)范化向量y總滿足 y 1 冪法的規(guī)范化計(jì)算公式為 任取初始向量x0 y0 0 計(jì)算 可得 研究生學(xué)位課程數(shù)值分析 8 所以 其收斂速度由比值 2 1 來(lái)確定 又由于 所以 因此 當(dāng)k充分大時(shí)可取 1 mk 1 xk 研究生學(xué)位課程數(shù)值分析 9 用乘冪法求A的按模最大的特征值和相應(yīng)特征向量 例8 1設(shè) 解取初值x0 y0 1 1 1 T 計(jì)算得 可取 1 6 000837 1 1 0 714316 0 249895 T 實(shí)際上 A的3個(gè)特征值分別為 1 6 2 3 3 2 研究生學(xué)位課程數(shù)值分析 10 8 1 2加速技術(shù) 由于 所以 乘冪法收斂速度取決于比值 2 1 當(dāng) 2 1 1時(shí) 收斂是很慢的 1 Aitken加速方法 由上式可知 可見(jiàn) 序列 mk 線性收斂于 1 構(gòu)造Aitken序列 會(huì)達(dá)到加速收斂的目的 研究生學(xué)位課程數(shù)值分析 11 2 原點(diǎn)位移法 作矩陣B A pE 則B的特征值為qi i p i 1 2 n 而且對(duì)應(yīng)的特征向量相同 如果選取p 使q1仍然是B的按模最大特征值 且滿足 則對(duì)B應(yīng)用乘冪法可達(dá)到加速收斂的目的 程序見(jiàn)P170 例8 2 研究生學(xué)位課程數(shù)值分析 12 反冪法是求矩陣按模最小的特征值和相應(yīng)特征向量的方法 8 1 3反冪法 設(shè)A是n階非奇異矩陣 其特征值為 1 2 n 1 n 0 對(duì)應(yīng)的特征向量為 1 2 n 則有A 1的特征值為 對(duì)應(yīng)的特征向量為 n n 1 1 要想求 n和 n只需對(duì)A 1應(yīng)用乘冪法 任取初始向量x0 y0 0 作 研究生學(xué)位課程數(shù)值分析 13 也可將上式改寫成 式 8 8 稱為反冪法 顯然有 每一步求xk需要求解線性方程組 可采用LU分解法求解 研究生學(xué)位課程數(shù)值分析 14 8 9 研究生學(xué)位課程數(shù)值分析 15 Jacobi方法是求實(shí)對(duì)稱矩陣全部特征值和特征向量的一種矩陣變換方法 8 2Jacobi方法 實(shí)對(duì)稱矩陣A具有下列性質(zhì) 1 A的特征值均為實(shí)數(shù) 其對(duì)應(yīng)的特征向量線性無(wú)關(guān)且兩兩正交 2 存在正交矩陣Q 使QTAQ diag 1 2 n 而且 Q的第i個(gè)列向量恰為 i的特征向量 3 若記A1 QTAQ 則A1仍為對(duì)稱矩陣 直接找Q不大可能 我們可以構(gòu)造一系列特殊形式的正交陣Q1 Qn對(duì)A作正交變換 使得對(duì)角元素比重逐次增加 非對(duì)角元變小 當(dāng)非對(duì)角元已經(jīng)小得無(wú)足輕重時(shí) 可以近似認(rèn)為對(duì)角元就是A的所有特征值 Jacobi方法就是這樣一類方法 研究生學(xué)位課程數(shù)值分析 16 平面解析幾何中的平面坐標(biāo)旋轉(zhuǎn)變換 表示平面上坐標(biāo)軸旋轉(zhuǎn)角 的變換 8 2 1平面旋轉(zhuǎn)矩陣 旋轉(zhuǎn)正交相似變換 在三維空間直角坐標(biāo)系中 ox1y1平面繞著oz1軸旋轉(zhuǎn) 角的坐標(biāo)變換為 一般地 在n維向量空間Rn中 沿著xiyj平面旋轉(zhuǎn) 角的變換矩陣為 研究生學(xué)位課程數(shù)值分析 17 稱Rij 為平面旋轉(zhuǎn)矩陣或Givens變換矩陣 Rij 具有下列性質(zhì) ij 研究生學(xué)位課程數(shù)值分析 18 研究生學(xué)位課程數(shù)值分析 19 研究生學(xué)位課程數(shù)值分析 20 設(shè)實(shí)對(duì)稱矩陣A apq n n 記B RijT ARij bpq n n則它們?cè)刂g有如下關(guān)系 2 Rij 為正交矩陣 即Rij 1 RijT 3 如果A為對(duì)稱矩陣 則RijT ARij 也為對(duì)稱矩陣 且與A有相同的特征值 4 RijT A僅改變A的第i行與第j行元素 ARij 僅改變A的第i列與第j列元素 研究生學(xué)位課程數(shù)值分析 21 所以有 從而 由上面兩式可得 如果aij 0 適當(dāng)選取角 使 研究生學(xué)位課程數(shù)值分析 22 只需角 滿足 由式 8 15 令t tan 則t滿足方程 t2 2dt 1 0 為保證 4 取絕對(duì)值較小的根 有 于是 且 研究生學(xué)位課程數(shù)值分析 23 非對(duì)角線元素的平方和 由可知 研究生學(xué)位課程數(shù)值分析 24 我們有以下的收斂性定理保證上述計(jì)算過(guò)程 8 2 2Jacobi方法 研究生學(xué)位課程數(shù)值分析 25 收斂性定理 證 則有 反復(fù)利用上式 即得 研究生學(xué)位課程數(shù)值分析 26 設(shè)k充分大時(shí) 有 這里需要說(shuō)明一點(diǎn) 并不是對(duì)矩陣A的每一對(duì)非對(duì)角線非零元素進(jìn)行一次這樣的變換就能得到對(duì)角陣 因?yàn)樵谟米儞Q消去的時(shí)候 只有第i行 第j行 第i列 第j列元素在變化 如果或?yàn)榱?經(jīng)變換后又往往不是零了 因此 Qk RT1RT2 RTk的列向量xj j 1 2 n 為A的近似特征向量 研究生學(xué)位課程數(shù)值分析 27 的全部特征值 解記A0 A 取i 1 j 2 aij 0 a12 0 2 于是有 例用Jacobi方法計(jì)算對(duì)稱矩陣 從而有 研究生學(xué)位課程數(shù)值分析 28 所以 再取i 2 j 3 aij 1 a23 1 2 020190 類似地可得 以下依次有 研究生學(xué)位課程數(shù)值分析 29 從而A的特征值可取為 1 2 125825 2 8 388761 3 4 485401 特征向量為R1TR2T RkT 研究生學(xué)位課程數(shù)值分析 30 為了減少搜索非對(duì)角線絕對(duì)值最大元素時(shí)間 對(duì)經(jīng)典的Jacobi方法可作進(jìn)一步改進(jìn) 1 循環(huán)Jacobi方法 按 1 2 1 3 1 n 2 3 2 4 2 n n 1 n 的順序 對(duì)每個(gè) i j 的非零元素aij作Jacobi變換 使其零化 逐次重復(fù)掃描下去 直至S A 為止 2 過(guò)關(guān)Jacobi方法 取單調(diào)下降收斂于零的正數(shù)序列 k 先以 1為關(guān)卡值 依照1中順序 將絕對(duì)值超過(guò) 1的非對(duì)角元素零化 待所有非對(duì)角元素絕對(duì)值均不超過(guò) 1時(shí) 再換下一個(gè)關(guān)卡值 2 直到關(guān)卡值小于給定的精度 研究生學(xué)位課程數(shù)值分析 31 用Jacobi方法求得的結(jié)果精度一般都比較高 特別是求得的特征向量正交性很好 所以Jacobi方法是求實(shí)對(duì)稱矩陣全部特征值和特征向量的一個(gè)較好的方法 它的弱點(diǎn)是計(jì)算量大 對(duì)原矩陣是稀疏矩陣 旋轉(zhuǎn)變換后不能保持其稀疏的性質(zhì) 一般適用于階數(shù)不高的矩陣 研究生學(xué)位課程數(shù)值分析 32 8 3QR方法 60年代出現(xiàn)的QR算法是目前計(jì)算中小型矩陣的全部特征值與特征向量的最有效方法 實(shí)矩陣 非奇異 理論依據(jù) 任一非奇異實(shí)矩陣都可分解成一個(gè)正交矩陣Q和一個(gè)上三角矩陣R的乘積 而且當(dāng)R的對(duì)角元符號(hào)取定時(shí) 分解是唯一的 同理可得 Ak相似于A k 2 3 故他們有相同特征根 研究生學(xué)位課程數(shù)值分析 33 QR算法的收斂性 定理 設(shè)n階矩陣A的n個(gè)特征值滿足 n 0 其相應(yīng)的n個(gè)線性無(wú)關(guān)特征向量為x1 x2 xn 記X x1 x2 xn Y X 如果Y存在LU分解 那么 矩陣序列Ak基本收斂于上三角矩陣R 這里 基本收斂的含義指 Ak 的對(duì)角元均收斂 且嚴(yán)格下三角部分的元素均收斂于零 但嚴(yán)格上三角部分的元素沒(méi)有收斂的要求 定理設(shè)n階矩陣A非奇異實(shí)對(duì)稱矩陣 則矩陣序列 Ak 收斂于對(duì)角陣 研究生學(xué)位課程數(shù)值分析 34 QR方法收斂性 研究生學(xué)位課程數(shù)值分析 35 QR方法收斂性 研究生學(xué)位課程數(shù)值分析 36 QR方法運(yùn)算量很大 為了減少運(yùn)算量 常在使用QR方法之前把矩陣A簡(jiǎn)化為擬上三角矩陣 或稱之為海森伯格矩陣 次對(duì)角元以下的元素全為零 8 3 2化一般矩陣為擬上三角矩陣 形狀為 研究生學(xué)位課程數(shù)值分析 37 為鏡面反射矩陣 或Householder變換矩陣 Houholder矩陣H H v 有如下性質(zhì) 1 2 3 記S為以v為法向量的平面 則幾何上x與y Hx關(guān)于平面S對(duì)稱 因?yàn)?研究生學(xué)位課程數(shù)值分析 38 x 據(jù)前面定義和性質(zhì) 有下面的定理 證 研究生學(xué)位課程數(shù)值分析 39 由此可得 定理得證 研究生學(xué)位課程數(shù)值分析 40 與平面旋轉(zhuǎn)不同的是 鏡面反射變換可成批的消去向量的非零元 程序見(jiàn)P187 研究生學(xué)位課程數(shù)值分析 41 與平面旋轉(zhuǎn)變換不同的是 鏡面反變換可成批的消去向量的非零元 將任意矩陣A簡(jiǎn)化為海森伯格矩陣的步驟如下 研究生學(xué)位課程數(shù)值分析 42 研究生學(xué)位課程數(shù)值分析 43 研究生學(xué)位課程數(shù)值分析 44 研究生學(xué)位課程數(shù)值分析 45 研究生學(xué)位課程數(shù)值分析 46 研究生學(xué)位課程數(shù)值分析 47 研究生學(xué)位課程數(shù)值分析 48 研究生學(xué)位課程數(shù)值分析 49 用Household方法對(duì)矩陣A作正交相似變換 使A相似與上Hessenberg陣 算法如下 研究生學(xué)位課程數(shù)值分析 50 研究生學(xué)位課程數(shù)值分析 51 用Givens變換對(duì)上Hessenberg陣作QR分解 研究生學(xué)位課程數(shù)值分析 52 研究生學(xué)位課程數(shù)值分析 53 研究生學(xué)位課程數(shù)值分析 54 研究生學(xué)位課程數(shù)值分析