网站开发怎么使用sharepoint,长沙在线注册公司,企业网站建设有没有模板,西安网约车公司排行榜1、引言求解线性方程组在许多领域中都有重要应用#xff0c;写成矩阵的形式#xff1a; 。求解 可以写成#xff1a; #xff0c;这里需要求解矩阵 的逆。《线性代数》中给出的方法主要有两类#xff1a;1、设置增广矩阵#xff0c;利用高斯消元法#xff0c;通过初等行…1、引言求解线性方程组在许多领域中都有重要应用写成矩阵的形式 。求解 可以写成 这里需要求解矩阵 的逆。《线性代数》中给出的方法主要有两类1、设置增广矩阵利用高斯消元法通过初等行列变换可以求 但这种方法不利于使用计算机计算。2、利用矩阵对角化求 这种方法关键在于求解矩阵 的特征值和特征向量根据《线性代数》中给出求特征值和特征向量的方法其复杂度大概是 其中 是矩阵的行数有个著名的算法SVDsingular 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旋转变换持续多轮直到满足收敛条件。图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.
