矩阵论三角分解课件

兰州交通大学数理与软件工程学院3.3 矩阵的三角分解法我们知道对矩阵进行一次初等变换，就相当于用相应的初等矩阵去左乘原来的矩阵。因此我们这个观点来考察Gauss消元法用矩阵乘法来表示，即可得到求解线性方程组的另一种直接法：矩阵的三角分解。兰州交通大学数理与软件工程学院 Gauss消元法的矩阵形式兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院 Doolittle分解兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院Doolittle分解若矩阵A有分解：A=LU，其中L为单位下三角阵，U为上三角阵，则称该分解为Doolittle分解，可以证明，当A的各阶顺序主子式均不为零时，Doolittle分解可以实现并且唯一。兰州交通大学数理与软件工程学院A的各阶顺序主子式均不为零，即兰州交通大学数理与软件工程学院Doolittle分解兰州交通大学数理与软件工程学院Doolittle分解兰州交通大学数理与软件工程学院Doolittle分解兰州交通大学数理与软件工程学院Doolittle分解兰州交通大学数理与软件工程学院Doolittle分解兰州交通大学数理与软件工程学院Doolittle分解兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院Doolittle分解兰州交通大学数理与软件工程学院对称矩阵的Cholesky分解在应用数学中，线性方程组大多数的系数矩阵为对称正定这一性质，因此利用对称正定矩阵的三角分解式求解对称正定方程组的一种有效方法，且分解过程无需选主元，有良好的数值稳定性。兰州交通大学数理与软件工程学院对称矩阵的Cholesky分解 A对称：AT=A A正定：A的各阶顺序主子式均大于零。即兰州交通大学数理与软件工程学院对称矩阵的Cholesky分解由Doolittle分解，A有唯一分解兰州交通大学数理与软件工程学院对称矩阵的Cholesky分解定理3.2.4 设A为对称正定矩阵，则存在唯一分解A=LDLT，其中L为单位下三角阵，D=diag(d1,d2,dn)且di0(i=1,n)兰州交通大学数理与软件工程学院对称矩阵的Cholesky分解证明：兰州交通大学数理与软件工程学院对称矩阵的Cholesky分解兰州交通大学数理与软件工程学院对称矩阵的Cholesky分解兰州交通大学数理与软件工程学院对称矩阵的Cholesky分解推论：设A为对称正定矩阵，则存在唯一分解 其中L为具有主对角元素为正数的下三角矩阵。兰州交通大学数理与软件工程学院证明：兰州交通大学数理与软件工程学院Cholesky分解的求法兰州交通大学数理与软件工程学院Cholesky分解的求法兰州交通大学数理与软件工程学院Cholesky分解的求法兰州交通大学数理与软件工程学院Cholesky分解法Cholesky分解法缺点及优点 优点：可以减少存储单元。缺点：存在开方运算，可能会出现根号下负数。兰州交通大学数理与软件工程学院改进Cholesky分解法改进的cholesky分解A=LDLT兰州交通大学数理与软件工程学院改进Cholesky分解兰州交通大学数理与软件工程学院改进Cholesky分解兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院改进的cholesky分解算法兰州交通大学数理与软件工程学院改进的cholesky分解算法兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院A=LDLT分解，既适合于解对称正定方程组，也适合求解A为对称，而各阶顺序主子式不为零的方程组而对A=LLT只适合于对称正定方程组兰州交通大学数理与软件工程学院 追赶法兰州交通大学数理与软件工程学院追赶法兰州交通大学数理与软件工程学院追赶法兰州交通大学数理与软件工程学院追赶法兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院3.5平方根法在应用数学中，线性方程组大多数的系数矩阵为对称正定这一性质，因此利用对称正定矩阵的三角分解式求解对称正定方程组的一种有效方法，且分解过程无需选主元，有良好的数值稳定性。兰州交通大学数理与软件工程学院平方根法 A对称：AT=A A正定：A的各阶顺序主子式均大于零。即兰州交通大学数理与软件工程学院平方根法由Doolittle分解，A有唯一分解兰州交通大学数理与软件工程学院平方根法定理3.2.4 设A为对称正定矩阵，则存在唯一分解A=LDLT，其中L为单位下三角阵，D=diag(d1,d2,dn)且di0(i=1,n)兰州交通大学数理与软件工程学院平方根法证明：兰州交通大学数理与软件工程学院平方根法兰州交通大学数理与软件工程学院平方根法兰州交通大学数理与软件工程学院平方根法推论：设A为对称正定矩阵，则存在唯一分解 其中L为具有主对角元素为正数的下三角矩阵。兰州交通大学数理与软件工程学院证明兰州交通大学数理与软件工程学院平方根法兰州交通大学数理与软件工程学院平方根法兰州交通大学数理与软件工程学院平方根法兰州交通大学数理与软件工程学院平方根法Cholesky分解法缺点及优点 优点：可以减少存储单元。缺点：存在开方运算，可能会出现根号下负数。兰州交通大学数理与软件工程学院改进平方根法改进的平方根法分解A=LDLT兰州交通大学数理与软件工程学院改进平方根法兰州交通大学数理与软件工程学院改进平方根法兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院改进的平方根法兰州交通大学数理与软件工程学院改进平方根法兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院A=LDLT分解，既适合于解对称正定方程组，也适合求解A为对称，而各阶顺序主子式不为零的方程组而对A=LLT只适合于对称正定方程组兰州交通大学数理与软件工程学院2.6范数与误差估计 用直接方法解n阶线性方程组Ax=b，由于原始数据A、b的误差及计算过程中的舍入误差，一般得不到方程的精确解 ，往往得到 它的近似解x，为了讨论解的精度，即误差向量x-，的大小，也为了讨论用迭代法解线性方程组的收敛性问题，需要引入向量及矩阵的范数。兰州交通大学数理与软件工程学院向量的范数 定义3.1 设是n维向量空间，如果 ，实值函数x满足条件 (1)正定性：x0，当且仅当x=0时，x；(2)齐次性：R,x=|x；(3)三角不等式：x+yx+y，则称x为 上的向量范数(或向量的模)。兰州交通大学数理与软件工程学院在数值计算中，常用的向量范数有三种。设 ，规定 兰州交通大学数理与软件工程学院性质兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院证明：据式(3.25)，只要证明对“”范数结论成立即可。又据定义3.2知：兰州交通大学数理与软件工程学院矩阵的范数兰州交通大学数理与软件工程学院设 常用的矩阵范数：(1)矩阵的列范数：(2)矩阵的行范数：(3)矩阵的欧氏范数：(4)矩阵的谱范数：兰州交通大学数理与软件工程学院例3.6 已知 ，求A的常用范数。解：兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院例题兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院多元函数误差估计兰州交通大学数理与软件工程学院3.7迭代法 解线性方程组的直接法，如Gauss消去法、矩阵的三角分解等，适用于阶数不高的线性方程组。而在实际应用中，常会遇到一类阶数很高，非零元素很少的所谓高阶稀疏方程组(零元素成片分布，数量上绝对占优)。对这类方程组用迭代法求解，可以充分利用稀疏矩阵的特性减少计算工作量，节省存贮量。兰州交通大学数理与软件工程学院迭代法所要解决的几个主要问题是：(1)构造一种迭代格式，把所给方程组Ax=b化成同解的方程组x=Bx+d 从而得迭代公式 (k=0,1,2,)只需要给出初始向量 即可得一向量序列 ,式中B叫迭代矩阵，B不同，则得不同的迭代方法。兰州交通大学数理与软件工程学院(2)研究迭代矩阵B满足什么条件时，迭代序列 必收敛于Ax=b的精确解。(3)讨论如何估计 误差的大小以决定迭代次数N。兰州交通大学数理与软件工程学院Jacobi 迭代法 Jacobi 迭代法是最简单的一种迭代法，是从方程组(3.1)的各个方程中分别解出同序号的未知数。设系数矩阵A非奇异，且 ，则因此，得迭代公式兰州交通大学数理与软件工程学院例 3.7 用Jacobi迭代法求解方程组 解：从原方程组中分别解出 兰州交通大学数理与软件工程学院因此得迭代格式K=1,2,3,。若取初始向量 计算所得向量列于表3.1，其中 兰州交通大学数理与软件工程学院兰州交通大学数理与软件工程学院小 结 本章主要介绍了解线性方程组的直接法和迭代法，以及向量、矩阵的范数和病态方程组的基本概念。直接法的基础是Gauss消去法及其矩阵形式的LU分解。选取主元素是保证消去法计算稳定性及提高精度的有效方法，列主元Gauss消去法以其算法组织简便，计算量不大等优点见长，比较常用，必须熟练掌握。利用三对角矩阵(对角占优)及对称正定矩阵的矩阵形式的特殊性，可以简化LU分解，得到追赶法及平方根法，这两个方法不需选主元便数值稳定，具有较高的计算精度，是解决两类特殊形式方程组的有效方法。兰州交通大学数理与软件工程学院对于大型稀疏方程组可采用迭代法求解，比较简便有效的迭代法是Gauss-Seidel方法，当选取合适的松弛因子，SOR方法可获得较快的收敛速度，被广泛应用。向量或矩阵的范数可以用来描述解的精度、迭代的敛散性，控制迭代次数。应用矩阵范数可以描述方程组性态，识别病态方程组，从而找到解病态方程组的方法。