计算方法 第二章解线性方程组的直接法 §25平方根法
第二章 解线性方程组的直接法 § 2.5 平方根法
§25平方根法 、对称正定矩阵的三角分解( Cholesky分解) 若n阶矩阵A为对称正定矩阵 则det(4)>0,A′=A 且A的顺序主子式detA>0,k=1,2,…,n 因此4可以进行LU分解(或 Doolittle分解) 记为 其中L为单位下三角阵U为上三角阵
§2.5 平方根法 一、对称正定矩阵的三角分解(Cholesky分解) 且A的顺序主子式 det Ak > 0, k = 1,2,L, n 若n阶矩阵A为对称正定矩阵 A A A T 则det( ) > 0, = 因此A可以进行LU分解(或Doolittle分解) 记为 A LU ~ ~ = 其中 L为单位下三角阵 U为上三角阵 ~ , ~ , -------------(1)
且对于ADO的任意6阶价顺序主子式4,E,k LU k k=1,2 let Ak=det lk. det Uk=1. ui>0 det k kh det k-1 det a k ->0(记det4=1) det a k-1 以上k=1,2灬…,n
Ak LkUk ~ ~ = det Ak Õ= = × k i ii u 1 ~ 1 Lk Uk ~ det ~ = det × k = 1,2,L,n > 0 det Ak kk k i ii u u ~ ~ 1 1 = Õ × - = k kk A u ~ det 1 = × - kk u ~ det 1 det - = k k A A > 0 ( det 1) 记 A0 = Ak Lk Uk A L U k ~ , ~ , ~ , ~ 且对于 , 的任意 阶顺序主子式 以上 k = 1,2,L,n
因此 12 In n n nn 11 11 11 2 22 22 22 n-1,n nn n-1,n-1 ≌DU1
÷÷÷÷÷÷øö ççççççèæ = nnnnn u u u u u u u u u u U ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 33 3 22 23 2 11 12 13 1 O M LLL ÷÷÷÷÷÷øö ççççççèæ = unn u u u ~ ~ ~ ~ 33 22 11 O ÷÷÷÷÷÷÷÷÷÷øö ççççççççççèæ× - - -1 ~~ 1 ~~ ~~ 1 ~~ ~~ ~~ 1 1, 1 1, 222 22 23 111 11 13 11 12 n n n n nn uuuu uu uu uu uu O LLL =ˆDU1 因此
D=diag( 11/22 )=[diag( 11V22 agonal对角 U=DU=D2 D2U1 -(2) A=D0=D2D21=(LD2)(D21)=LU 3) L=LD2为非奇异下三角阵且L和U的主对角元 为D2的主对角元, U=D21为非奇异上三角阵并且都是正数
) ~ , , ~, ~( D = diag u11 u22 L unn 1 ~U = DU 1 2 1 2 1 = D D U A LU ~ ~ = 1 2 1 2 1 ~ = LD D U 2 11 22 )] ~ , , ~ , ~ [ ( = diag u u L unn Diagonal:对角 )( ) ~ ( 1 2 1 2 1 = LD D U = ˆLU 2 1 ~ L = LD 为非奇异下三角阵 1 2 1 U = D U 为非奇异上三角阵 并且都是正数 为 的主对角元， 且 和 的主对角元 2 1 D L U ----------(2) --------(3)
由于A=LC唯一A=ED2DU1唯 A=LU唯一 而A为对称正定阵,A=A 因此 LU U·D=LU 所以 LULU=L 综合以上分析,若n阶矩阵A为对称正定矩阵 则有 A=LL
由于 A LU 唯一 ~ ~ = 2 1 唯一 1 2 1 ~ A = LD D U A = LU 唯一 A A A T 而 为对称正定阵 , = T T 因此 A = (LU ) T T = U × L = LU 所以 T T L = U ,U = L 综合以上分析, 若n阶矩阵A为对称正定矩阵 则有 T A = LL -------------(4) -------------(5)
定理1.( Cholesky分解) 设A为对称正定矩阵,则一定存在一个主对角元全是 正数的下三角阵L,使得 A= LL 且该分解式唯 这种关于对称正定矩阵的分解称为 Cholesky分解 11 In 设A=an1 L=|1 n
定理1. (Cholesky分解) 正数的下三角阵 使得 设 为对称正定矩阵 则一定存在一个主对角 元全是 , , L A T A = LL 且该分解式唯一 这种关于对称正定矩阵的分解称为Cholesky分解 ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ = n nr nn r rr l l l l l l L L L M M O L M O 1 1 11 ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ = n nr nn r rr rn r n a a a a a a a a a A L L M M O M L L M O M M L L 1 1 11 1 1 设 aij = aji
11 C 1 a1=111 11 21 21111 1 L的第一列元素ln可以求出」 (6) 假设L的第1~r-1列已求出,考察A的第r列元素an n=∑kk=∑l2+ 7 k=1 ∑k·1k=∑ (8) ik rk +l.· i=r,r+1,…,n k=1
ir 假设L的第1 ~ r - 1列已求出,考察A的第r列元素a ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ = n nr nn r rr l l l l l l L L M M O L M O 1 1 11 ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ n nr nn r rr rn r n a a a a a a a a a L L M M O M L L M O M M L L 1 1 11 1 1 ÷ ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç ç è æ × nn rr nr r n l l l l l l O M L O M M 11 L 1 L 1 11 11 11 a = l ×l 21 21 11 a = l ×l 1 1 11 a l l i i = × i = 1,2,L,n L的第一列元素 l i1可以求出 å= = × r k rr rk rk a l l 1 2 1 1 2 rr r k rk = ål + l - = å= = × r k ir ik rk a l l 1 ir rr r k ik rk = ål ×l + l ×l - = 1 1 i = r,r + 1,L, n -------------(6) -------------(7) -------------(8)
由()~(8)式可得L的元素的计算公式 11 11 ∑k r=2 ik rk k=1 i=r+1,…,n 从公式中可以看出,在计算机上运算时, 当求出后,an的储存地址可以用来存放
由(6) ~ (8)式可得L的元素的计算公式 11 11 l = a 11 1 1 l a l i i = i = 2,3,L,n å - = = - 1 1 2 r k rr rr rk l a l r = 2,L, n rr r k ir ik rk ir l a l l l å - = - × = 1 1 i = r + 1,L, n (9) ij ij ij 当l 求出后 a 的储存地址可以用来存放l 从公式中可以看出 在计算机上运算时 , ,
、对称正定线性方程组的解法 线性方程组 a x= b 10) 其中A为n阶对称正定矩阵 则存在主对角元为正数的下三角阵L,使得 A=LL 线性方程组(10)可化为两个三角形方程组 Ly=b (12) L(L x)=b l x
二、对称正定线性方程组的解法 线性方程组 Ax = b 其中A为n阶对称正定矩阵 则存在主对角元为正数 的下三角阵 L,使得 T A = LL -------------(10) -------------(11) 则线性方程组(10)可化为两个三角形方程组 Ly = b L x y T = L L x b T ( ) = -------------(12) -------------(13)