§3矩阵的LU分解 ◆矩阵的LU分解 ◆对称矩阵的平方根法 改进的平方根法 ◇解三对角方程组的追赶法
§3 矩阵的LU分解 ❖矩阵的LU分解 ❖对称矩阵的平方根法 ❖改进的平方根法 ❖解三对角方程组的追赶法
二、平方根法 工程实际计算中,线性方程组的系数矩阵常常 具有对称正定性,即其各阶顺序主子式及全部特征 值均大于零。矩阵的这一特性使它的三角分解也有 更简单的形式,从而导出一些特殊的解法,如平方 根法与改进的平方根法
二、平方根法 工程实际计算中,线性方程组的系数矩阵常常 具有对称正定性,即其各阶顺序主子式及全部特征 值均大于零。矩阵的这一特性使它的三角分解也有 更简单的形式,从而导出一些特殊的解法,如平方 根法与改进的平方根法
定理:设A是对称正定矩阵,则存在唯 的非奇异下三角阵L,使得 A= LL 且L的对角元素皆为正。 证明1;证明2
, A L T A LL L = 定理:设 是对称正定矩阵,则存在唯一 的非奇异下三角阵 使得 且 的对角元素皆为正。 证明1 ;证明2
定狸证明(1) 证:因A对称正定,其各阶顺序主子式均大于零,故有 A=LU其中L为单位下三角矩阵,U为上三角阵。 令D=dig(u12…,umn),P=DU,则P为单位上三角阵。 U DP 故A=LU=LDP=A=PDL 由LU分解的唯一性→P=L→A=PDP
定理证明(1) 11 22 1 11 11 12 1 12 1 11 11 1, 1, 2 1 2 1 ( , , , 1 ), nn n n n nn n nn n n u u u A u u A L U L D diag u u P D U u u u u U u u U P u u u − − − − = = = = = 证:因 对称正定,其各阶顺序主子式均大于零,故有 其中 为单位下三角矩阵, 为上三角阵。 令 则 为单位上三角阵。 T T T T T A LU LDP A P DL A P D D P P LU L P = = = = = = = 故 由 分解的唯一性
定理证明(2) 证明:(存在性)由于A是对称正定的,其顺序主子 式均大于零。故 41=D1>0,n=D/D1>0(=2,3,…,n) d= diag(u, D=DD A=P DP=P D DP=(DP) DP=LL 其中L=(DP)为非奇异下三角阵,且对角元素皆 为正数
定理证明(2) 11 1 1 11 0, / 0 ( 2,3, , ) ( , , , ( ( ) , ) ) ii i i T n T n T T T T T u D u D D i n D diag DP D u u D D D A A L DP P DP P P D D P LL = = = − = = = = = = = 证明: 由于 是对称正定的 其顺序主子 式均大于零。故 令 则 其中 为非奇异下三角阵 且对角元素皆 (存在性) 为正数
唯一性:假定存在非奇异下三角阵G≠L,其对角元 素皆为正数,且使得=L=GG7于是有 L(G)=LLL(G)=LGG(G=LG 因Z(G)为上三角阵,LG为下三角阵,故由上式得 L(G)=LG=I 即G=L,与假设矛盾
1 1 1 1 1 1 1 1 1 1 , ( ( ) ( , ) ( ) ( ) ) T T T T T T T T T T T T L G L LL G G L A LL GG L G L G L GG G L L G L G G L G I − − − − − − − − − − = = = = = = = = :假定存在非奇异下三角阵 其对角元 素皆为正数,且使得 于是有 因 为上三角阵, 为下三角阵,故由上式得 即 与假 唯一性 设矛盾
平方根( Cholesky分解法)法 由A=L 0l2 2 0 其中>0(=1,2,…,n)由矩阵乘法及/k=0(当<时 (a jk 得 =(a-∑1k)2(=j+1…,n)
平方根(Cholesky分解法)法 11 11 12 1 21 22 22 2 1 2 1 1 2 2 1 0 0 0 0 0 0 0 ( 1 ( ) ( 1, , 2, , ). 0 ( ), , , ( 2 ), n T n n n nn nn ii j j jj jj jk k ij ij i k k j l l l l l l l l A LL l l l l l i n l l a l j n l a l j k l − = = = = = − = − = = 由 其中 由矩阵乘法及 当 时 得 1 1 ) / ( 1, , ); j k jj k l i j n − = = +
这里规定>·=0。计算顺序是按列进行,即 1→>hn(t=2,3,…,n)→>l2→>l2(i=3,…,n)>… 当矩阵A完成平方根分解后,求解 Ax=L(L x)=b, 即求解两个三角形方程组 1)Ly=b,求y (2)x=y,求x y=(b-2yk)/(=1 x=(y-∑lx)/(=n,n-1…,1) k=i+1
0 11 1 22 2 1 ( 2,3, , ) ( 3 , ) 0 , i k i l l i n l l i n = → = → → = = → 这里规定 。计算顺序是按列进行,即 。 ( ) 1 1 1 ( ) / ( 1 ,2, , ). ( ) / ( , , ; 1, ,1) 2 . . T i i i ik k ii k n i i ki k ii k T i A Ly b y L Ax L L x x y x b y b l y l i n x y l x l i n n − = = + = = − = = − = − = = 当矩阵 完成平方根分解后,求解 即求解两个三角形方程组 (1) 求 ( ) ,求 =
由于的对称性,平方根法的乘除运算量 为n3/6数量级,约是Ga消去法的一半。上 机计算时,所需存储单元也少,只要存储的 下三角部分和右端项b,计算中L存放在A存 储单元,y,x存储在冽存储单元。 但这种方法在求时需作n次开方运算,这 样又增加了计算量。为了避免开方,可使用改 进的平方根方法
3 , n / 6 A Gauss A L n b L A y x b 由于 的对称性,平方根法的乘除运算量 为 数量级,约是 消去法的一半。上 机计算时,所需存储单元也少,只要存储 的 下三角部分和右端项 ,计算中 存放在 的存 储单元, 存储在 的存储单元。 但这种方法在求 时需作 次开方运算,这 样又增加了计算量。为了避免开方,可使用改 进的平方根方法
改进平方根法 A=LDIT= I 221 其中=1k=0(<k,由比较法得
改进平方根法 1 21 2 1 2 21 1 2 1 1 1 1 1 1 ) ( , 1 jj jk , 0 T n n n n n l d l d A LDL l l d l l l l j k = = = = 其中 由比较法得