直接三角分解法课件

矩阵的三角分解n一、LU分解(Doolittle分解)1.LU分解分解用用n=3来举例说明。三元方程组来举例说明。三元方程组Ax=b的增广矩阵为的增广矩阵为,用初等行变换变换为用初等行变换变换为这相当于将这相当于将A矩阵左乘初等行变换矩阵矩阵左乘初等行变换矩阵 矩阵的三角分解一、LU分解(Doolittle分解)1.L和和使使M2M1A b=A(1)b(1),其中其中l21=a21/a11,l31=a31/a11再将再将进行初等行变换进行初等行变换,得到得到 这相当于左乘初等行变换矩阵这相当于左乘初等行变换矩阵 和再将进行初等行变换,得到 这相,其中其中,则则。记。记,则则U是一个上三角矩阵是一个上三角矩阵,有有。则。则。其中。其中,。记记L是下三角矩阵。这就是矩阵是下三角矩阵。这就是矩阵A的的LU分解分解:A=LU。,其中,则。记,则U是一个上三角矩阵,有。则。其中,。3.分解的充要条件分解的充要条件定理定理1:A能分解为能分解为的充分必要条件是的充分必要条件是A的各的各阶顺序主子式均不为零。即阶顺序主子式均不为零。即,。4、LU分解的紧凑格式分解的紧凑格式我们不必在高斯消去法过程中产生我们不必在高斯消去法过程中产生L和和U,而而是直接用矩阵是直接用矩阵A来进行来进行LU分解。分解。下面导出计算公式下面导出计算公式因因A=LU则则 3.分解的充要条件定理1:A能分解为的充分必要条件是A的4、LU分解的紧凑格式分解的紧凑格式我们不必在高斯消去法过程中产生我们不必在高斯消去法过程中产生L和和U,而而是直接用矩阵是直接用矩阵A来进行来进行LU分解。分解。下面导出计算公式下面导出计算公式因因A=LU则则 4、LU分解的紧凑格式我们不必在高斯消去法过程中产生L和利用矩阵乘法利用矩阵乘法,得得利用矩阵乘法,得综合以上分析,有因此可以推导出U的第一行L的第一列-(1)-(2)综合以上分析,有因此可以推导出U的第一行L的第一列-U的第r行L的第r列-(3)-(4)称上述(1)(4)式所表示的分解过程为Doolittle分解分解由此可以得到由此可以得到和和的计算公式的计算公式:。在。在U的第的第行和行和L的第的第列计算出来后再列计算出来后再先计算先计算U的第一行的第一行计算计算L的第的第j列列:U的第r行L的第r列-(3)-(4)称上在在U的第的第行和行和L的的再计算再计算U的第的第i行行:计算的过程是计算的过程是:U第第1行行,L第第1列列,U第第2行行,L第第2列列,顺序计算。顺序计算。第第列均计算出来后列均计算出来后在U的第行和L的再计算U的第i行:计算的过程是:U第1行,L1.计算流程计算流程1.计算流程2.存储问题和全部流程U可以存储在可以存储在A的上三角部分的上三角部分,L可以存储在可以存储在A的下的下三角部分三角部分,对角元存对角元存U的对角元的对角元,A的对角元为的对角元为1而而不必存储不必存储,如下图如下图:2.存储问题和全部流程U可以存储在A的上三角部分,L可以存储用LU分解来解线性方程组的全部流程如下:用LU分解来解线性方程组的全部流程如下:例1:利用LU分解求解线性方程组解解:第一步第一步,A的的LU分解分解例1:利用LU分解求解线性方程组解:第一步,A的LU分解第二步第二步,求解求解解得解得:,。第二步第二步,求解求解解得解得:,。第二步,求解解得:,。第二步,求解解得:,矩阵的三种形式的分解:Doolittle分解:A=LU (单位下三角与上三角)Crout分解:(下三角与单位上三角)LDU分解:A=LDU (单位下三角,对角及单位上三角)矩阵的三种形式的分解:Doolittle分解:A=LU二、追赶法1.三对角矩阵三对角矩阵:在实际问题中在实际问题中,经常会遇到如下经常会遇到如下形式的方程组形式的方程组,其系数矩阵为其系数矩阵为二、追赶法1.三对角矩阵:在实际问题中,经常会遇到如下形式没有写的部分均为零没有写的部分均为零(下同下同),对角元为对角元为 后次后次对角线上的元素为对角线上的元素为,前次对角线上的元素为前次对角线上的元素为。我们称矩阵我们称矩阵A为三对角矩阵为三对角矩阵,相应的方程组称三对相应的方程组称三对角方程组。如果对角方程组。如果对A进行进行LU分解分解,则将有如下形式则将有如下形式:并称它们为二对角矩阵。并称它们为二对角矩阵。没有写的部分均为零(下同),对角元为 定理3:设上述三对角矩阵A满足 且且 则对矩阵则对矩阵A的的LU分解能进行分解能进行,且分解是唯一的。且分解是唯一的。3.追赶法的计算公式追赶法的计算公式利用矩阵乘法可得利用矩阵乘法可得:从而可以得到从而可以得到:解解得得:解解得得:,定理3:设上述三对角矩阵A满足 且 则对矩阵A的LU分解能进4.追赶法的计算流程,第一个循环称之为追的过程第一个循环称之为追的过程,相当于消元过程相当于消元过程;第二个循环称之为赶的过程第二个循环称之为赶的过程,相当于回代过程。相当于回代过程。4.追赶法的计算流程,第一个循环称之为追的过程,相当于消元过20总结u 事实上，追赶法的求解过程就是将系数矩阵分解两个简单的二对角线矩阵，从而归结为求解两个简单三角形方程组的过程。u 追赶法的原理和高斯消去法相同，但考虑到方程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。也称Thomas法法20总结 事实上，追赶法的求解过程就是将系数矩阵分解两个简单例2:用追赶法求解方程组解解:追的过程追的过程:,;,;,;,。赶的过程赶的过程:,。例2:用追赶法求解方程组解:追的过程:,;,;,;,。22定理定理1.(Cholesky分解分解)且该分解式唯一且该分解式唯一。这种关于对称正定矩阵的分解称为Cholesky分解分解22定理1.(Cholesky分解)且该分解式唯一。这种关三、解正定矩阵方程组的平方根法 如果方程组的系数矩阵如果方程组的系数矩阵A的对称正定矩的对称正定矩阵阵,可以证明可以证明:A可以唯一分解为可以唯一分解为 ,其中其中L是下三角矩阵是下三角矩阵,是是L的转置的转置,即即 A=L。由矩阵乘法可知由矩阵乘法可知,在对角元上在对角元上;在第在第列均计算完后得列均计算完后得;在在时时,;三、解正定矩阵方程组的平方根法 如果方程组在在1,2,j-1列均计算完后列均计算完后计算是按计算是按L的第的第1列列,第第2列列,.,第第n列的次序进行的。列的次序进行的。计算流程如下计算流程如下:,(解解)在1,2,j-1列均计算完后计算流程如下:,(解)例例3.用平方根法求解方程组用平方根法求解方程组解解:,则则 解解得得:,解解得得:,平方根法不需要选主元平方根法不需要选主元(矩阵正定矩阵正定)约需约需次乘法的工作量次乘法的工作量,是高斯消去法的一半是高斯消去法的一半(由对称性引由对称性引起起),且具有算法稳定性且具有算法稳定性,但其要进行但其要进行n次开方运算。次开方运算。例3.用平方根法求解方程组解:,则 解得:,