解线性方程组的矩阵三角分解法优秀PPT.ppt
解线性方程组的矩阵解线性方程组的矩阵三角分解法三角分解法现在学习的是第1页，共16页2本讲内容本讲内容n 一般线性方程组一般线性方程组 LU 分解与分解与 PLU 分解分解n 对称正定线性方程组对称正定线性方程组 平方根法平方根法Cholesky 分解分解n 对角占优三对角线性方程组对角占优三对角线性方程组 追赶法追赶法现在学习的是第2页，共16页3LU 分解分解将一个矩阵分解成结构简单的三角形矩阵的乘积将一个矩阵分解成结构简单的三角形矩阵的乘积矩阵的三角分解矩阵的三角分解矩阵的矩阵的 LU(Doolittle)分解分解矩阵的矩阵的 LDR 分解分解克洛脱克洛脱(Crout)分解分解现在学习的是第3页，共16页4计算计算 LU 分解分解利用矩阵乘法直接计算利用矩阵乘法直接计算 LU 分解分解L U =A比较等式两边的比较等式两边的第一行第一行得：得：u1j=a1j比较等式两边的比较等式两边的第一列第一列得：得：比较等式两边的比较等式两边的第二行第二行得：得：比较等式两边的比较等式两边的第二列第二列得：得：(j=1,n)(i=2,n)(j=2,n)(i=3,n)U 的第一行的第一行 L 的第一列的第一列 U 的第二行的第二行 L 的第二列的第二列 现在学习的是第4页，共16页5计算计算 LU 分解分解第第 k 步：此时步：此时 U 的前的前 k-1 行和行和 L 的前的前 k-1 列已经求出列已经求出直到第直到第 n 步，便可求出矩阵步，便可求出矩阵 L 和和 U 的所有元素。的所有元素。比较等式两边的比较等式两边的第第 k 行行得：得：(j=k,n)比较等式两边的比较等式两边的第第 k 列列得：得：(i=k+1,n)现在学习的是第5页，共16页6LU 分解算法分解算法算法算法：(LU 分解分解)for k=1 to nendj=k,ni=k+1,nMatlab程序参见：程序参见：ex51.m乘除法运算量：乘除法运算量：(n3-n)/3为了节省存储空间，通常用为了节省存储空间，通常用 A 的绝对下三角部分来存放的绝对下三角部分来存放 L(对角线元素无需存储对角线元素无需存储)，用，用 A 的上三角部分来存放的上三角部分来存放 U 现在学习的是第6页，共16页7PLU 分解分解矩阵的矩阵的 PLU 分解分解for k=1 to nendi=k,k+1,nj=1,2,ni=k+1,nj=k+1,nMatlab程序：程序：上机练习上机练习 现在学习的是第7页，共16页8Cholesky 分解分解n 对称正定矩阵对称正定矩阵的三角分解的三角分解Cholesky 分解分解定理：定理：设设 A 是对称矩阵，若是对称矩阵，若 A 的所有顺序主子式都不为的所有顺序主子式都不为 0，则，则 A 可唯一分解为可唯一分解为其中其中 L 为单位下三角阵，为单位下三角阵，D 为对角矩阵为对角矩阵A=LDLT定理：（定理：（Cholesky分解）分解）若若 A 对称正定，则对称正定，则 A 可唯一分可唯一分解为解为其中其中 L 为下三角实矩阵，且对角元素都大于为下三角实矩阵，且对角元素都大于 0A=LLT现在学习的是第8页，共16页9计算计算 Cholesky 分解分解n Cholesky 分解的计算分解的计算直接比较等式两边的元素直接比较等式两边的元素n 计算公式计算公式现在学习的是第9页，共16页10Cholesky 分解算法分解算法for j=1 to nendi=j+1,n算法算法：(Cholesky 分解分解)现在学习的是第10页，共16页11平方根法平方根法A 对称正定对称正定算法算法：(解对称正定线性方程组的解对称正定线性方程组的平方根法平方根法)计算计算 A 的的 Cholesky 分解分解解方程：解方程：Ly=b 和和 LTx=yi=2,3,ni=n-1,2,1 现在学习的是第11页，共16页12改进的改进的 Cholesky 分解分解n 计算公式计算公式n 改进的改进的 Cholesky 分解分解现在学习的是第12页，共16页13改进的改进的 Cholesky 分解分解for j=1 to nendi=j+1,n算法算法：(改进的改进的 Cholesky 分解分解)n 优点：优点：避免开方运算避免开方运算现在学习的是第13页，共16页14改进的平方根法改进的平方根法A 对称正定对称正定算法算法：(解对称正定线性方程组的解对称正定线性方程组的改进的平方根法改进的平方根法)计算计算 改进的改进的 Cholesky 分解分解解方程：解方程：Ly=b 和和 DLTx=yi=2,3,ni=n-1,2,1 现在学习的是第14页，共16页15追赶法追赶法n 对角占优的三对角矩阵对角占优的三对角矩阵的的 LU 分解分解n 计算公式计算公式i=2,3,n-1现在学习的是第15页，共16页16追赶法追赶法A 三对角矩阵（对角占优）三对角矩阵（对角占优）算法算法：(追赶法追赶法)i=2,3,ni=n-1,2,1 i=2,3,n-1n 运算量：运算量：5n-42n 3 次次2n 次次n 1 次次现在学习的是第16页，共16页
