|
QR算法求矩阵全部特征值的基本思想是利用矩阵的QR分解通过迭代格式 ![]() 将A=A1化成相似的上三角阵，从而求出矩阵A的全部特征值。 QR方法的计算步骤如下:
下面就依次进行介绍。
一. 将一般矩阵化为上Hessenberg阵 1.定义
一个矩阵如果满足i>j+1时aij=0，则将这个矩阵成为上Hessenberg阵。上Hessenberg阵 的形式如下: ![]() 2. Householder变换将一般矩阵转化为上Hessnberg阵 首先，选取Householder矩阵H1，使得经过H1相似变换后的矩阵H1AH1的元素a21下面的 元素全部为0，即a31, a41, ....., am1均为0，H1取如下形式
![]()
其中 ![]() 为n-1阶HouseHolder矩阵。然后选取Householder矩阵H2，使得经过H2相似变换 之后的矩阵H2(H1AH1)H2第二列中a32下面的a42, ....am2均为0。如此进行n-2次，可以构造 n-2个householder矩阵H1,H2, Hn-2，使得 Hn-2....H2H2AH1H2....Hm-2 = H(H为上Hessenberg矩阵)。
对于一个n*m的矩阵A,第col次的H可以这样构造求得(col从0开始):
![]()
其中，I为n*n的单位矩阵， v'表示矩阵v的转置， sign(x0)表示x0的符号的相反数( 当x0>0时sign=-1,当x<=0时为1), ||x||表示向量x的长度, col等于所求的上hessenberg矩阵的序号，从0开始。
二. 用Givens变换对上hessnberg矩阵作QR分解
此时有 H = R21' * R32' * ... * Rn(n-1)'R = QR。 多次计算H，直到H的变化小于一个较小的阈值时，停止迭代，此时H主对角线上的元素 即为矩阵A的全部特征值。 下面举个例子来说明求解矩阵的全部特征值的过程。 求矩阵![]() 的全部特征值 首先将A化成上hessenberg阵，取 x = [0, 6, 4], 则 ||x|| =![]() = ![]() 则 w = [0, ![]() , 0] ， v = w + 1 * x = [0, 6+![]() , 4] 则 p = v*v'/v'*v = ![]()
于是 H1 = I - 2*p =
所以 H = H1AH1 =
H即为与A相似的上hessenberg矩阵。将H进行QR分解
| 
楼主
标题置顶
标题高亮
