当前位置:   article > 正文

可逆矩阵的特征值和原来矩阵_经典Jacobi方法用于求解矩阵特征值

svd的经典算法有golub-kahan算法、分治法、jacobi法几种

1、引言

求解线性方程组在许多领域中都有重要应用,写成矩阵的形式:

求解

可以写成:
,这里需要求解矩阵
的逆。《线性代数》中给出的方法主要有两类:

1、设置增广矩阵,利用高斯消元法,通过初等行列变换可以求

但这种方法不利于使用计算机计算。

2、利用矩阵对角化求

这种方法关键在于求解矩阵

的特征值和特征向量,根据《线性代数》中给出求特征值和特征向量的方法,其复杂度大概是
,其中
是矩阵的行数,有个著名的算法SVD(singular value decomposition)。关于SVD的介绍已经很多了,今天我们想要更近一步,介绍另一种著名的矩阵对角化方法——
Jacobi方法

2、经典Jacobi方法

1846年数学家Jacobi提出的经典Jacobi方法用于求解实对称矩阵的特征值。它的核心思想是采用一些列的Jacobi平面旋转矩阵将对称阵

变为对角阵

左右的Jacobi旋转矩阵乘起来就是特征向量组成的特征矩阵,
为特征值组成的对角阵。Jacobi希望每通过一个Jacobi旋转矩阵都能消去矩阵
中的

Jacobi旋转矩阵定义如下:

一个Jacobi旋转矩阵,对角线上只有第i行i列,j行j列为c,其余为1,未标出的元素均为0。

表示消去元素在矩阵
中的位置,其中
,
被称为旋转角,我们的目的就是找到一个合适的
,使得非对角元上的两个元素变为0。由于
仅影响
行列的元素,故写为二阶主子式来表示旋转变换过程:

其中

解得:

当一次变换结束后,

同时为0,而矩阵
的非对角元素的Frobenius norm的平方和将减少
[2]

其中

表示取A的对角线元素组成的对角矩阵。Frobenius norm的定义为:

3、复杂度分析

时,说明
被对角化了,其中
为精度要求。从贪心算法的角度来说,每次做旋转都希望尽可能减少Frobenius norm,因此
的选择矩阵
中最大的非对角元做旋转变换。

但由于每次做旋转变换后会影响矩阵

两行两列的数据,这会导致前面变成0的非对角元素在后续的变换中变为非0因此旋转矩阵个数并不是
,同时在矩阵中寻找绝对值最大非对角元的复杂度也是
,而合并旋转变换矩阵的部分复杂度为
,这在大规模矩阵中,遍历元素将占绝大部分时间。

可能的改进方法

(1)循环Jacobi方法[3]

按照行顺序或者列顺序依次做Jacobi旋转变换,持续多轮,直到满足收敛条件。

1fe62e88003b212083e26aaa11ce672a.png
图1:循环遍历的Jacobi方法

(2)过关Jacobi方法[4]

在顺序遍历的基础上,在加入门限值,大于某个门限值,才做旋转变换,其中门限值与

的Frobenius norm有关。

4、非对称矩阵的Jacobi方法

对于非对称矩阵

,可以将其构造为对称矩阵

5、讨论

高效使用Jacobi方法的关键在于,如何使用尽量少的旋转角度完成对角化矩阵,贪心算法是否是最优方法还值得进一步探讨。是否在矩阵中存在一个固定的最优的

的顺序组合,还是说这与矩阵元素的具体取值有关。

参考文献

[1] 郭强. 并行JACOBI方法求解矩阵奇异值的研究[D]. 苏州大学.

[2] C.F. Van Loan G. H. Golub. Matrix COmputations[M]. John Hopkins University Press, Baltimore and London, second edition, 1993.

[3] E. R. Hansen. On Cyclic Jacobi Methods[J]. J.Soc,Indust.Appl.Math, 1963, 11(2): 448–459.

[4] B. N. Parlett. The Symmetric Eigenvalue Problem[M]. Prentice-Hall, 1980.

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/78163
推荐阅读
相关标签
  

闽ICP备14008679号