1、 9 矩阵特征值的数值计算矩阵特征值的数值计算（Numerical Computation of Eigenvalues of Matrix）n 本章主要内容本章主要内容n 9.1 特征值估计特征值估计 n 9.2 幂法与原点平移法幂法与原点平移法 n 9.3 矩阵的矩阵的QR分解分解n 9.4 QR算法算法 n 重点：重点：矩阵的两种正交变换、幂法矩阵的两种正交变换、幂法n 难点：难点：QR分解与分解与QR算法算法9.1 特征值的基本知识与估计特征值的基本知识与估计n9.1.1 特征值的基本知识特征值的基本知识 特征值定义特征值定义xAx)0(1122xxAxxA则则 特征向量特征向量 x1
2、,x2,xn 线性无关是矩阵线性无关是矩阵A可对角化的充要条件。可对角化的充要条件。此时称其为此时称其为A的的完全特征向量组完全特征向量组。Aaniiniiinii111 相似矩阵有相同的相似矩阵有相同的特征值。特征值。实对称矩阵的实对称矩阵的特征值为实数。特征值为实数。9.1 特征值的基本知识与估计特征值的基本知识与估计n9.1.2 特征值估计特征值估计 定义定义9-1 盖尔圆盖尔圆nijjijiiiiaRRaz1,定理定理9-1 盖尔圆定理盖尔圆定理 例例9-1 估计特估计特征值范围。征值范围。结论：结论：各个盖尔圆相互分离是最好不过了各个盖尔圆相互分离是最好不过了。1(1,2,)nijj
3、Gin定理定理9-2 第第2盖尔圆定理。盖尔圆定理。例例9-2 估计特估计特征值范围。征值范围。盖尔圆分离的方法盖尔圆分离的方法：构造相似变换：构造相似变换B=DAD-1。其中，其中，D为第为第2种形式的初等方阵。种形式的初等方阵。例例9-3 盖尔圆分离。盖尔圆分离。例例9-4 设设A按行严格对角占优，则按行严格对角占优，则A可逆（特征值不为可逆（特征值不为0）。）。9.2 幂法及原点平移法幂法及原点平移法9.2.1 幂法幂法 幂法的基本思想：幂法的基本思想：是构造一个向量序列使之逼近主特征向量，据此求是构造一个向量序列使之逼近主特征向量，据此求出主特征向量和主特征值的近似值。是一种迭代的方法
4、，又称出主特征向量和主特征值的近似值。是一种迭代的方法，又称乘幂法乘幂法。9.2 幂法及原点平移法幂法及原点平移法9.2.1 幂法幂法 9.2 幂法及原点平移法幂法及原点平移法9.2.1 幂法幂法 幂法的算法步骤：幂法的算法步骤：例例9-5 幂法计算结果幂法计算结果。幂法的特点：幂法的特点：优点优点：算法简单、便于机器实现，适合大型稀疏矩阵的最大特征值。算法简单、便于机器实现，适合大型稀疏矩阵的最大特征值。缺点缺点：算法效率低，收敛速度取决于次特征值与主特征值的比值。算法效率低，收敛速度取决于次特征值与主特征值的比值。9.2 幂法及原点平移法幂法及原点平移法9.2.2 反反幂法幂法 反反幂法原
5、理：幂法原理：通过求通过求A-1的按模最大的特征值，来获得的按模最大的特征值，来获得A的按模最小的的按模最小的特征值特征值 。因为在工程应用中，按模最大和最小的特征值和特征向。因为在工程应用中，按模最大和最小的特征值和特征向量是关注的重点。量是关注的重点。n 反幂法算法步骤：反幂法算法步骤：反幂法是对幂法的补充，其困难在于每迭代一步相当于求解一个反幂法是对幂法的补充，其困难在于每迭代一步相当于求解一个线性方程组，计算量较大。线性方程组，计算量较大。9.2 幂法及原点平移法幂法及原点平移法9.2.3 原点平移法原点平移法 1 原点平移加速原点平移加速 原点平移加速的原理原点平移加速的原理是令是令
6、B=A-pE，在保证，在保证B的主特征值与的主特征值与A的主特的主特征值对应的基础上，使征值对应的基础上，使B的次特征值与主特征值之比减小或达到最小，的次特征值与主特征值之比减小或达到最小，从而起到加速求主特征值的目的。不难得到：从而起到加速求主特征值的目的。不难得到：幂法与反幂法可以求矩阵的最大和最小特征值，对其他特征值就无幂法与反幂法可以求矩阵的最大和最小特征值，对其他特征值就无能为力了。但是可以将原点平移技术与反幂法结合起来，就可求能为力了。但是可以将原点平移技术与反幂法结合起来，就可求出任一个特征值（如果对所有的特征值有大概的估计的话）。出任一个特征值（如果对所有的特征值有大概的估计的
7、话）。具体的作法：假设具体的作法：假设A在在p附近有一个特征值，做附近有一个特征值，做原点平移原点平移B=A-pE，用用反幂法反幂法求求B的最小特征值，给其加上的最小特征值，给其加上p，就是要求的特征值。，就是要求的特征值。最小。时，,max21122*pppprpnBn 例例9-6，例，例9-7 原点平移加速。原点平移加速。2 原点平移的反幂法原点平移的反幂法 例例9-8，例，例9-9 原点平移加速。原点平移加速。9.3 矩阵的矩阵的QR分解分解 9.3.1 矩阵的初等反射变换矩阵的初等反射变换 矩阵的初等反射变换，又称矩阵的初等反射变换，又称镜面反射变换镜面反射变换，或，或Househol
8、der（豪斯荷豪斯荷尔德尔德）变换，是一种正交变换。）变换，是一种正交变换。显然，初等反射矩阵显然，初等反射矩阵H具有对称性和正交性，这样具有对称性和正交性，这样y=Hx是一个正交变换。是一个正交变换。初等反射变换主要用在以下两个方面：初等反射变换主要用在以下两个方面：等模反射变换等模反射变换 向量的约化消元向量的约化消元9.3 矩阵的矩阵的QR分解分解 9.3.1 矩阵的初等反射变换矩阵的初等反射变换等模反射变换等模反射变换 定理定理9-3（等模反射定理）（等模反射定理）设设x,y是两个互异的是两个互异的n维列向量，且维列向量，且2范数范数相等，则存在一个初等反射阵相等，则存在一个初等反射阵
9、H，使得，使得Hx=y。例例9-11 等模反射变换。注意不唯一性。等模反射变换。注意不唯一性。向量的约化消元向量的约化消元 9.3 矩阵的矩阵的QR分解分解 9.3.2 矩阵的平面旋转变换矩阵的平面旋转变换 矩阵的平面旋转变换，又称矩阵的平面旋转变换，又称Givens（吉文斯吉文斯）变换，也一种正交变换。）变换，也一种正交变换。显然，选取合适的显然，选取合适的c，s使经使经Givens变换后的向量的第变换后的向量的第j个分量为个分量为0。起到对向量的约化消元的目的。起到对向量的约化消元的目的。例例9-12 用平面旋转变换对向量约化消元用平面旋转变换对向量约化消元。9.3 矩阵的矩阵的QR分解分
10、解 9.3.3 矩阵的矩阵的QR分解分解定理定理9-4 对于任一对于任一n阶实方阵阶实方阵A,有有A=QR。其中其中Q,R分别为正交阵及上三角阵。分别为正交阵及上三角阵。定理定理9-5 （矩阵的（矩阵的QR分解）若分解）若n阶实方阵阶实方阵A可逆有，则可逆有，则A的的QR分解是分解是唯一的（当的对角线元素为正数时）。唯一的（当的对角线元素为正数时）。例例9-13 分别用两种方法求矩阵的分别用两种方法求矩阵的QR分解分解。方法一：利用初等反射变换方法一：利用初等反射变换方法二：利用平面旋转变换方法二：利用平面旋转变换 例例9-14 用用QR分解求解线性方程组分解求解线性方程组。9.4 QR算法算
11、法 9.4.1 基本基本QR算法算法 在极限状态下，在极限状态下，Ak逼近一个上三角阵，从而求得逼近一个上三角阵，从而求得A的特征值（这里的特征值（这里的的Ak之间是相似的）。之间是相似的）。QR算法实质上是对算法实质上是对Ak进行进行QR分解。分解。定理定理9-6 任意实方阵都可以通过正交相似变换与上海森伯格矩阵相似。任意实方阵都可以通过正交相似变换与上海森伯格矩阵相似。例例9-16 用初等反射变换化矩阵为上海森伯格矩阵用初等反射变换化矩阵为上海森伯格矩阵。QR分解分解：Ak=QkRk交换相乘交换相乘：Ak+1=RkQk=QTkAkQk 例例9-15 试证矩阵与其约化成为的上试证矩阵与其约化
12、成为的上Hessenberg阵有相同的特征值。阵有相同的特征值。QR算法是求解矩阵全部特征值的有效方法算法是求解矩阵全部特征值的有效方法 QR算法是一个迭代过程。主要分为一下两步算法是一个迭代过程。主要分为一下两步9.4.2 两步两步QR算法算法1.1.矩阵与上矩阵与上HessenbergHessenberg矩阵的正交相似矩阵的正交相似 定义定义9-5 上海森伯格（上海森伯格（Hessenberg）矩阵。）矩阵。推论推论 实对称矩阵与三对角阵正交相似。实对称矩阵与三对角阵正交相似。9.4 QR算法算法 9.4.2 两步两步QR算法算法2.2.矩阵与上矩阵与上HessenbergHessenbe
13、rg矩阵的正交相似矩阵的正交相似 引入上引入上Hessenberg阵的原因是，若对上阵的原因是，若对上Hessenberg阵进行分解，由阵进行分解，由于的次对角线以下元素均为零，只需使用次构造方便的平面旋转变换于的次对角线以下元素均为零，只需使用次构造方便的平面旋转变换即可完成分解，显然这要比对一般矩阵进行分解简便得多。利用这个即可完成分解，显然这要比对一般矩阵进行分解简便得多。利用这个特点给出的两步算法，可以降低基本算法的计算过程中对矩阵做分解特点给出的两步算法，可以降低基本算法的计算过程中对矩阵做分解的计算量。的计算量。3.3.两步两步QR算法算法 两步算法的思路就是先利用初等反射阵批量约化消元的特点，将原始两步算法的思路就是先利用初等反射阵批量约化消元的特点，将原始矩阵用有限次的初等反射变换约化为与之正交相似的上矩阵用有限次的初等反射变换约化为与之正交相似的上HessenbergHessenberg阵阵，然后使用然后使用平面旋转变换平面旋转变换对实施算法构造相似矩阵序列，以求出亦即的对实施算法构造相似矩阵序列，以求出亦即的全部特征值。全部特征值。4.4.两步两步QR算法计算步骤算法计算步骤
