LU分解教学讲解课件

LU分解法的与特殊方程组的解法LU分解法的与特殊方程组的解法LU分解法的与特殊方程组的解法LU分解法的与特殊方程组的解法假定我们能把矩阵A写成下列两个矩阵相乘的形式：A=LU其中L为下三角矩阵，U为上三角矩阵。这样我们可以把线性方程组Ax=b写成

Ax=（LU)x=L(Ux)=bLy=b令Ux=y,则原线性方程组Ax=bUx=y于是可首先求解向量y使Ly=b然后求解Ux=y,从而求解线性方程组Ax=b的目的.

LU分解法的基本思想假定我们能把矩阵A写成下列两个矩阵相乘的形式：A=LU假定我们能把矩阵A写成下列两个矩阵相乘的形式：A=LU内容:LU分解.关键词:1.LU分解:将系数矩阵A转变成等价两个矩阵L和U的乘积,其中L和U分别是下三角和上三角矩阵,而且要求U的对角元素都是1.2.紧凑格式:由于可以把L和U两个矩阵压缩到一个数组中,而且还可以存储在原来的系数矩阵A的数组中.这种LU分解常被称为紧凑格式.内容:LU分解.内容:LU分解.内容:LU分解.由LU=A及对L和U的要求可以得到分解的计算公式．根据下式(Doolittle分解)：1

l211

l31l321

………ln1ln2…

lnn-11

u11u12u13…u1nu22u23…u2n

…un-1nu(n-1)n

unn=…………aannLUn1an3…a11a12a13…a1na21a22

a23…a2na31a32

a33…

a3n

an2A………由LU=A及对L和U的要求可以得到分解的计算公式．根据下式(由LU=A及对L和U的要求可以得到分解的计算公式．根据下式(第j个分量第i个分量第j个分量第i个分量第j个分量第i个分量第j个分量第i个分量根据矩阵乘法及相等的定义,有

得公式u1j=a1jj=1,2,…,nli1=ai1/u11i=2,3,…,n根据矩阵乘法及相等的定义,有得公式u1j=a1j根据矩阵乘法及相等的定义,有得公式u1j=a1jLU分解教学讲解课件LU分解教学讲解课件在计算机程序中常常用这种方法解线性代数方程组。它的优点是存储量很省。L和U中的三角零元素都不必存储，就是U的对角元素也因为都是1没有必要再记录在程序中，这样只用一个n阶方阵就可以把L和U贮存起来。即：下三角（包括对角元）存储L各元素而上三角存储U的元素。再考察公式S会发现A中任一元素aij只在计算lij（j<=i）和uij（j>i)中用到一次以后就不再出现了，因而完全可以利用原始数组A的单元，一个个逐次贮存L或U中的相应元素，即：

a11

a12a13…a1nu11u12u13…u1na21a22a23…a2nl21u22u23…u2na31a32a33…a3nl31l32u33…u3n

an1an2an3…annln1ln2ln3…unn………...…………......(1)(3)(5)(2n-1)(2)(4)(6)(2n)在计算机程序中常常用这种方法解线性代数方程组。………...…在计算机程序中常常用这种方法解线性代数方程组。………...…采用LU分解有如下特点：（1）LU分解与右端向量无关。先分解，后回代。一般说来，分解的运算次数正比于n回代求解正比与n。求遇到多次回代时，分解的工作不必重新做。这样节省计算时间。（2）分解按步进行，前边分解得到的信息为后边所用。（3）[A]阵的存储空间可利用，节省存储。32采用LU分解有如下特点：32采用LU分解有如下特点：32采用LU分解有如下特点：32特殊方程组的解法1.追赶法2.LDLT分解法特殊方程组的解法1.追赶法特殊方程组的解法1.追赶法特殊方程组的解法1.追1.追赶法追赶法与稀疏线性方程组

追赶法仍然保持LU分解特性,它是一种特殊的LU分解。充分利用了系数矩阵的特点，而且使之分解更简单,得到对三对角线性方程组的快速解法。因三对角矩阵的非零元素呈“带状”，我们也因此将它叫做带状矩阵。1.追赶法追赶法与稀疏线性方程组1.追赶法追赶法与稀疏线性方程组1.追赶法追赶法与稀疏线性方三对角线性方程组：三对角线性方程组：三对角线性方程组：三对角线性方程组：设有方程组Ax=d，其中A为三对角矩阵。假设系数矩阵A满足条件：对A作Crout分解形式为：设有方程组Ax=d，其中A为三对角矩阵。设有方程组Ax=d，其中A为三对角矩阵。设有方程组Ax=d，第i个分量第j个分量第i个分量第j个分量第i个分量第j个分量第i个分量第j个分量追赶法计算公式追赶法计算公式追赶法计算公式追赶法计算公式LU分解教学讲解课件LU分解教学讲解课件定理

如果上带宽为q，下带宽为p的n阶带状矩阵A有Doolittle分解。A=LU，则L是下带宽为p的单位下三角矩阵，U是上带宽为q的上三角矩阵。

定理如果上带宽为q，下带宽为p的n阶带状矩阵A有Dooli定理如果上带宽为q，下带宽为p的n阶带状矩阵A有DooliLU分解教学讲解课件LU分解教学讲解课件下面举实例用追赶法来解三对角方程组。下面举实例用追赶法来解三对角方程组。下面举实例用追赶法来解三对角方程组。下面举实例用追赶法来解三LU分解教学讲解课件LU分解教学讲解课件实际问题中，当求解方程组的系数矩阵是对称矩阵时，则用下面介绍的LDLT分解法可以简化程序设计并减少计算量.

从定理可知,当矩阵A的各阶顺序主子式不为零时,A有唯一的Doolittle分解A=LU.此时,当然有,所以矩阵U的对角线元素uii

0,(i=1,2,,n),将矩阵U的每行依此提出uii2.LDLT分解法实际问题中，当求解方程组的系数矩阵是对称矩阵时，则用下面介绍实际问题中，当求解方程组的系数矩阵是对称矩阵时，则用下面介绍由A=AT，得由分解的唯一性有，即，于是可得下面的结论。

由A=AT，得由A=AT，得由A=AT，得定理3：若对称矩阵A各阶顺序主子式不为零时,

则

A可以唯一分解为A=LDLT

，这里LT为L的转置矩阵。当A有LDLT分解时，利用矩阵运算法则及相等原理易得计算ljk及dk的公式为定理3：若对称矩阵A各阶顺序主子式不为零时,则

A可以唯一定理3：若对称矩阵A各阶顺序主子式不为零时,则

A可以唯一

k=1,2,,n;j=k+1,k+2,,n为减少乘法次数，引入辅助量ujk=ljkdk,则上面公式可写成k=1,2,,n;j=k+1,k+2,,n为减少乘法k=1,2,,n;j=k+1,k+2,,n为减少乘法LU分解教学讲解课件LU分解教学讲解课件LU分解教学讲解课件LU分解教学讲解课件LU分解教学讲解课件LU分解教学讲解课件平方根法设A为正定矩阵，则它的各阶顺序主子式均为正。由前面的定理知，A必有唯一的LDLT分解式

A=LDLT

在解对称正定线性方程组时，系数矩阵A的LDLT分解中D又可分解为D=D1/2D1/2，这里D1/2也是对角矩阵平方根法平方根法平方根法LU分解法的与特殊方程组的解法LU分解法的与特殊方程组的解法LU分解法的与特殊方程组的解法LU分解法的与特殊方程组的解法假定我们能把矩阵A写成下列两个矩阵相乘的形式：A=LU其中L为下三角矩阵，U为上三角矩阵。这样我们可以把线性方程组Ax=b写成

Ax=（LU)x=L(Ux)=bLy=b令Ux=y,则原线性方程组Ax=bUx=y于是可首先求解向量y使Ly=b然后求解Ux=y,从而求解线性方程组Ax=b的目的.

LU分解法的基本思想假定我们能把矩阵A写成下列两个矩阵相乘的形式：A=LU假定我们能把矩阵A写成下列两个矩阵相乘的形式：A=LU内容:LU分解.关键词:1.LU分解:将系数矩阵A转变成等价两个矩阵L和U的乘积,其中L和U分别是下三角和上三角矩阵,而且要求U的对角元素都是1.2.紧凑格式:由于可以把L和U两个矩阵压缩到一个数组中,而且还可以存储在原来的系数矩阵A的数组中.这种LU分解常被称为紧凑格式.内容:LU分解.内容:LU分解.内容:LU分解.由LU=A及对L和U的要求可以得到分解的计算公式．根据下式(Doolittle分解)：1

l211

l31l321

………ln1ln2…

lnn-11

u11u12u13…u1nu22u23…u2n

…un-1nu(n-1)n

unn=…………aannLUn1an3…a11a12a13…a1na21a22

a23…a2na31a32

a33…

a3n

an2A………由LU=A及对L和U的要求可以得到分解的计算公式．根据下式(由LU=A及对L和U的要求可以得到分解的计算公式．根据下式(第j个分量第i个分量第j个分量第i个分量第j个分量第i个分量第j个分量第i个分量根据矩阵乘法及相等的定义,有

得公式u1j=a1jj=1,2,…,nli1=ai1/u11i=2,3,…,n根据矩阵乘法及相等的定义,有得公式u1j=a1j根据矩阵乘法及相等的定义,有得公式u1j=a1jLU分解教学讲解课件LU分解教学讲解课件在计算机程序中常常用这种方法解线性代数方程组。它的优点是存储量很省。L和U中的三角零元素都不必存储，就是U的对角元素也因为都是1没有必要再记录在程序中，这样只用一个n阶方阵就可以把L和U贮存起来。即：下三角（包括对角元）存储L各元素而上三角存储U的元素。再考察公式S会发现A中任一元素aij只在计算lij（j<=i）和uij（j>i)中用到一次以后就不再出现了，因而完全可以利用原始数组A的单元，一个个逐次贮存L或U中的相应元素，即：

a11

a12a13…a1nu11u12u13…u1na21a22a23…a2nl21u22u23…u2na31a32a33…a3nl31l32u33…u3n

an1an2an3…annln1ln2ln3…unn………...…………......(1)(3)(5)(2n-1)(2)(4)(6)(2n)在计算机程序中常常用这种方法解线性代数方程组。………...…在计算机程序中常常用这种方法解线性代数方程组。………...…采用LU分解有如下特点：（1）LU分解与右端向量无关。先分解，后回代。一般说来，分解的运算次数正比于n回代求解正比与n。求遇到多次回代时，分解的工作不必重新做。这样节省计算时间。（2）分解按步进行，前边分解得到的信息为后边所用。（3）[A]阵的存储空间可利用，节省存储。32采用LU分解有如下特点：32采用LU分解有如下特点：32采用LU分解有如下特点：32特殊方程组的解法1.追赶法2.LDLT分解法特殊方程组的解法1.追赶法特殊方程组的解法1.追赶法特殊方程组的解法1.追1.追赶法追赶法与稀疏线性方程组

追赶法仍然保持LU分解特性,它是一种特殊的LU分解。充分利用了系数矩阵的特点，而且使之分解更简单,得到对三对角线性方程组的快速解法。因三对角矩阵的非零元素呈“带状”，我们也因此将它叫做带状矩阵。1.追赶法追赶法与稀疏线性方程组1.追赶法追赶法与稀疏线性方程组1.追赶法追赶法与稀疏线性方三对角线性方程组：三对角线性方程组：三对角线性方程组：三对角线性方程组：设有方程组Ax=d，其中A为三对角矩阵。假设系数矩阵A满足条件：对A作Crout分解形式为：设有方程组Ax=d，其中A为三对角矩阵。设有方程组Ax=d，其中A为三对角矩阵。设有方程组Ax=d，第i个分量第j个分量第i个分量第j个分量第i个分量第j个分量第i个分量第j个分量追赶法计算公式追赶法计算公式追赶法计算公式追赶法计算公式LU分解教学讲解课件LU分解教学讲解课件定理

如果上带宽为q，下带宽为p的n阶带状矩阵A有Doolittle分解。A=LU，则L是下带宽为p的单位下三角矩阵，U是上带宽为q的上三角矩阵。

定理如果上带宽为q，下带宽为p的n阶带状矩阵A有Dooli定理如果上带宽为q，下带宽为p的n阶带状矩阵A有DooliLU分解教学讲解课件LU分解教学讲解课件下面举实例用追赶法来解三对角方程组。下面举实例用追赶法来解三对角方程组。下面举实例用追赶法来解三对角方程组。下面举实例用追赶法来解三LU分解教学讲解课件LU分解教学讲解课件实际问题中，当求解方程组的系数矩