第七章__矩阵分解.ppt

第七章矩阵分解类似于多个因子分解、代数方程的因子分解，矩阵的各种分解在矩阵计算中也起到了相当重要的作用。 由于变换是一个矩阵，所以各种分解基本上是一种各种变换，其目的是把矩阵变换为特征量分解的对角矩阵、Jordan分解的Jordan矩阵、Schur分解的上三角矩阵等特殊的矩阵。 将分解用于数值计算是在电子计算机诞生后慢慢出现的。 最初是Dwyer(1951 )，Householder(1964 )和Wilkinson(1965 )，1，矩阵的LU分解，很多分解来源于19世纪的二次型和双线性型的研究。 LU分解来源于Gauss处理表示最小二乘问题的对称正定系统，具体而言Grass使用分解。 关于双线性型，多亏了雅可比(1857 )。 Dwyer(1944 )最初关注消元法和矩阵表现的关联。 例1，求解线性方程式，解：一，从Gauss消元法来说，用矩阵形式表示的系数矩阵，因此，Gauss提出消元法100多年后Dwyer注意到了分解：从而求解线性方程式，这是数值软件所采用的方法。 则称为LU分解或三角分解。 二、如果矩阵的LU分解，定义2平方矩阵能分解成一个单位的下三角矩阵和一个上三角矩阵的积，哪个矩阵进行LU分解？ 我们首先考虑可逆方阵。 因为总是块，所以考虑到块矩阵的阶数的任意性，上述结论对于矩阵的任何顺序，主公式成立。 那么，这个结论也充分吗？如果存在定理3(LU分解定理)正方矩阵的各阶顺序的主式，则存在唯一的主对角线上的元素都为1的下三角矩阵(称为单位下三角矩阵)和唯一的非特异上三角矩阵，所以根据LU定理，如果存在分解，则矩阵是可逆的，即存在可逆矩阵，所以行初等变换中例4，求以下矩阵的LU分解：解：由此，由此得到，所以推论5(LDU分解定理)中，如果正方矩阵的顺序为主君式，则存在唯一的单位下三角矩阵、唯一的单位上三角矩阵、对角矩阵，所以矩阵只有可逆方矩阵时，我们首先将矩阵重新排列行定理6 (列主元LU分解定理)对于可逆正方矩阵，存在阵列矩阵、单位下三角矩阵和上三角矩阵，因此例7，求以下矩阵的LU分解：请注意。 解：(为什么选择这样的数组矩阵p对a进行排序？ )，由此得到了这里，所以需要指出，在Matlab中使用函数lu计算的例4和例7、例7的结果一致，但例4的结果不同。 这是因为Matlab中的lu函数实现算法是列选择的主要元素方法，而在之前示例4的算法中没有选择主要元素。 任意正方形矩阵，甚至长正方形矩阵都有同样的结论。 例如，对于长正方形矩阵，存在列主元LU分解，并且示例8验证块矩阵的LDU分解(即，Schur互补)，如果(1)主矩阵可逆成立，(2)右下子矩阵可逆成立，且存在定理9(Cholesky分解定理) helmite矩阵的顺序主公式，则： 存在唯一的单位下三角矩阵和唯一的实对角矩阵，也就是说存在唯一的下三角矩阵，2、矩阵的QR分解、QR分解在矩阵计算中占有相当重要的地位。 通过使用QR分解，也可以解决在各种应用(例如工程力学、流体力学、图像压缩处理、结构分析等)中发生的最小二乘问题、特征值问题等的矩阵计算中的核心问题。 特别是基于QR分解的QR算法是解决小型稠密矩阵的特征量问题的最主要的数值稳定算法。 另一方面，关于Gram-Schmidt法，可逆排列的列向量组构成欧几里得空间的一个基。另外，Gram-Schmidt方法实际上通过查找正交向量序列，使用矩阵语言是QR分解：这里是酉矩阵或正交矩阵，在是上三角矩阵的情况下，线性方程式成为三角方程式，如从Gram-Schmidt过程可知，可以用矩阵表现是矩阵例1使用gram-schmidt法将以下矩阵QR分解：解：所以QR分解：gram-schmidt法基本上是将正交投影到空间上的投影系统法。 标准Gram-Schmidt方法分阶段计算，仅在需要计算时使用，并不需要更改的值。 遗憾的是，Gram-Schmidt迭代法在数值上是不稳定的。 另外，修改gram-Schmidt方法的想法是：每当产生新的东西时重新计算后续向量，删除其中包含的分量(即平行的分量)，并使这些变化后的后续向量为所计算出的正交性。 因此，本质上也是投影系统的方法，是处理大规模矩阵问题的Krylov子空间投影系统的方法的基础。 幸运的是，修改gram-Schmidt (MGS )方法通过简单的修改改进了问题。 例2用修改gram-Schmidt法将以下矩阵设为QR分解：解：所以QR分解：二，矩阵的QR分解，定理3 (约化QR分解)中将次数矩阵设为列全秩阵列，则一定存在次数列正交矩阵和非特异性的三角矩阵，矩阵具有约化QR分解，注意的QR分解是唯一的啊！ 因此，从问题上证明，对于任意，矩阵是正定埃尔米特矩阵。 因此，只要存在唯一的上三角矩阵，所以命令且因此是列正交单元矩阵并且定理4 (完全QR分解)设定阶矩阵是列全秩矩阵，那么即使存在阶非特异性的上三角矩阵和酉矩阵或正交矩阵，且矩阵具有完全QR分解，且列全秩长的正方形矩阵也是如此然后，对于任何矩阵也存在QR分解：并且定理5(QR分解)在本文处于开头，使得在给定阶数矩阵的秩上，一定存在阶数矩阵和阶数酉矩阵或正交矩阵，并且该矩阵具有QR分解。 将定义6变换为单位向量、对称矩阵、求三、QR分解的Householder变换法，Householder变换是将向量变换为相对于“与单位向量正交的维子空间”对称的向量的镜像变换。 其中Householder矩阵(初等反射矩阵)，对应的变换是Householder变换，定理7Householder矩阵具有以下性质： (Hermite矩阵，(2)是对称矩阵，(3)是特征值(重)和(重) : (3)被设定为，因此若将与固有值的重量分别设为，则得到解，(4)被设定为，则显然结论成立。 的双曲馀弦值。 其中是标准单位向量。 显然定理8对任意，存在Householder矩阵，能够取得Householder变换后的像。 在计算上，Householder第一次认识到Householder变换也可以使非零向量的下一个分量为零。 证明：因为如果是，则取正交的单位列向量，所以注意，在数学上，前两个符号是可满足的。 但是，为了数值稳定性的目的，向量优选不太接近大小和方向，不然在几何上都接近零。 因此，可以将算法实现时要采取的符号与第一个分量的符号相同，即加以规定。 因此，根据定理8，可以将任何方矩阵用一系列的Householder变换变换成上三角矩阵，因为在第一步骤中存在Householder矩阵，为了便于说明，可以采用负码，如果是，则处理进行到下一步骤。 因此，第二步，是的，因为当时存在Householder矩阵，如果存在，则进到下一步。由此，在第三步骤中，可以找到继续相似变换最多的步骤，即最多为矩阵，这意味着算法确实是一个酉矩阵，并且示例9使用Householder变换对以下矩阵进行QR分解：ver 通过得到Household矩阵，可以得到(注意：被反射，实际上是镜面的法线向量)、向量、命令(实际上是平面的法线向量) Householder矩阵，所以求出的QR四被分解为特征值问题的QR算法*， QR算法是二十世纪十大算法之一，基本思想基于QR迭代：(1)命令(2)对，重复qr分解：直到收敛。 另外，因为知道，重复序列保持特征值，并且如果是命令，则QR重复实际上也是QR分解。 已证明，在一定条件下重复序列几乎收敛于上三角矩阵，即QR重复也可视为Schur分解。 特别是埃尔米特矩阵，上三角矩阵是三对角矩阵。 为了计算成本，在数值实现中通常首先将矩阵转换为顶部Hessenberg矩阵(第一对角线以下为零的矩阵)，并使用QR重复。 3、矩阵奇异值分解自Beltrami(1873 )和Jordan(1874 )提出奇异值分解(SVD )以来，SVD及其推广已经成为矩阵计算中最有效的工具之一，最小二乘问题、优化、统计分析、信号和图像处理、系统理论和控制另一方面，从几何观测来说，圆被转换成椭圆。 圆的正交方向为椭圆的长轴、短轴方向，假设矩阵为列全秩矩阵。 一般来说，二维空间中单位球面变换为超椭圆。 正交方向为超椭圆的主轴半轴方向。 称为主轴的长度为的奇异值，对应的单位向量为的左奇异向量，对应的原象为的右奇异向量。 对应的空间被称为奇异空间，二、矩阵奇异值分解(SVD )已经指出：矩阵形式，其中矩阵是列正交矩阵。 如此获得的约化奇异值分解类似地将矩阵扩展为阶酉矩阵，然后命令，在获得的完全奇异值分解、定理1对任意矩阵中存在完全奇异值分解。 奇异值是唯一确定的。 也就是说，任意矩阵酉等效于对角矩阵，酉变换保持球面，对角矩阵将球面延伸为具有标准基础的超椭圆，最后酉变换旋转或反射该超椭圆，但其形状不变。 因此，解是从三、SVD导出的矩阵的性质，表示该结论可以用SVD计算矩阵的秩(数值秩)。 定理2对矩阵，表示矩阵的非零奇异值的数目，则定理3对矩阵，表示矩阵的非零奇异值，则定理4对任意矩阵，矩阵的非零奇异值的数目是矩阵的SVD分解。 因此，在分块SVD分解时，定理5对任意矩阵，矩阵的非零奇异值是矩阵或非零特征值的平方根。 矩阵在多元统计分析中被称为协方差矩阵。 这说明SVD能在其中大显身手，事实上是如此。 矩阵的非零奇异值与将球面拉伸为超椭圆时的各主轴半轴的增长率相对应，由于特征值也表示某个伸长的倍数，因此两者之间有什么关系呢？如果将SVD进一步分解，则类似，但对角矩阵的特征量与其他特征量有类似的计算定理6对于任何Hermite矩阵，矩阵的奇异值是矩阵特征值的绝对值。 其中，证明了埃尔米特矩阵的特征值在此分解为实对角矩阵。 那么，因为矩阵是酉矩阵，所以是SVD。 根据定理5，结论成立。 至此，可以给出定理1的一个证明法：这里是半正则的Hermite矩阵。 另外，由于与方程式同解，在Schur分解： Schur分解中，可以看出，这说明的列相互正交，同时列是零向量。另外，当将其扩展为正交基时，因此，在第二步骤：作为非负对角的平方根，计算，四，SVD的算法是定理4和5，任何矩阵的SVD分解算法是在第一步骤：形成，并计算特征值分解，以及在第三步骤： 例7是用于获得以下矩阵的(完全) SVD分解：解： (1)的矩阵的特征量是与上述结果相同的，因为获得计算和解并且其基础解系数是。 解： (2)对于矩阵的特征量，由于对应的特征向量为，能够得到计算、解、其基础解系，因此求SVD，很明显，上述算法将SVD问题约束为特征量问题，遗憾的是，特征量问题对扰动具有更高的灵敏度Hermite特征量问题的变换算法分为两个阶段：首先将矩阵近似为三对角矩阵，然后将三对角矩阵对角化。 因此，在SVD中，将矩阵化形成对角形式(Golub_Kahan对角化)，然后对对角矩阵进行对角化(例如，QR算法)。 Golub_Kahan双对角化的思想是通过在矩阵的两侧交替进行Householder变换，即寻找酉等价的双对角矩阵，对双对角矩阵通常用QR算法的变化来对角化，即计算SVD :等等这里，如果基于矩阵的秩1矩阵分解式对矩阵的SVD中的对角矩阵进行分解，则可以说明在所有秩的矩阵中，矩阵最接近矩阵的“距离”，即矩阵为矩阵的最佳秩近似，即中的“能量”最多。 定理8因为我知道，用于任何矩阵是矩阵的SVD，其中是非零奇异值，所以如果对于任何满足的矩阵存在单位正交向量，并且在零空间中存在二范数单位向量，则可以从维度中看出如果您使用椭球作为轴，证明在所有椭圆中最接近与矩阵对应的超椭圆“距离”，则可以获得在所有椭球中最接近与矩阵对应的超椭圆“距离”的椭球。 这样，步骤后得到的所有信息。 但是