第十讲矩阵的三角分解 Gauss消元法的矩阵形式 n元线性方程组 a1,1+a132+…+a1n5n=b A=(a a2351+a252+…+a2p5 b x=[l2…nJ an1+an252+…+an5n=bn b=[b1b2…bnJ 设A=A=(),设A的k阶顺序主子式为A,若A=a≠0,可 以令c1= 并构造 Frobenius矩阵 0 nXn 计算可得 A=L 0 该初等变换不改变行列式,故么2=aa2,若A2≠0,则a≠0,又 可定义 g2=(=34…“m),并构造 Frobenius矩阵
第十讲 矩阵的三角分解 一、 Gauss 消元法的矩阵形式 n 元线性方程组 11 1 12 2 1n n 1 21 1 22 2 2n n 2 n1 1 n2 2 nn n n a ξ + a ξ + + a ξ = b a ξ + a ξ + + a ξ = b a ξ + a ξ + + a ξ = b → Ax = b ij T 1 2 n T 1 2 n A =(a ) x =[ξ ξ ξ] b =[b b b ] 设 0 ij ( )n×n A = A = a ,设 A 的 k 阶顺序主子式为 Δk ，若 (0) Δ1 11 = a ≠0 ，可 以令 (0) i1 i1 (0) 11 a c = a 并构造 Frobenius 矩阵 21 1 n1 n×n 1 0 c 1 L = c 0 1 → -1 21 1 n1 1 0 -c 1 L = -c 0 1 计算可得 (0) (0) (0) 11 12 1n (1) (1) (1) -1 (0) 22 2n 1 (1) (1) n2 nn a a a a a A = L A = 0 a a → (0) (1) 1 A = L A 该初等变换不改变行列式，故 (0) (1) Δ2 11 22 = a a ，若 Δ2 ≠0 ，则 (1) 22 a ≠0 ，又 可定义 (1) i2 i2 (1) 22 a c = (i= 3,4, ,n) a ，并构造 Frobenius 矩阵
A四=LA (1 A=LA 依此类推,进行到第(r-1)步,则可得到 (r2)(r2) A们)= a( 2) Mr (r=2,3,…,n1) 则A的r阶顺序主子式4=aa2…aa0,若4≠0,则a0≠0 (r1) 可定义cn= 并构造 frobenius矩阵 r+1
2 32 n2 1 1 L = c c 1 → -1 2 32 n2 1 1 L = -c -c 1 (0) (0) (0) (0) 11 12 13 1n (1) (1) (1) 22 23 2n (2) -1 (1) (2) (2) 2 33 3n (2) (2) n3 nn a a a a a a a A = L A = a a a a → (1) (2) 2 A = L A 依此类推，进行到第(r-1)步，则可得到 (0) (0) (0) (0) 11 1r-1 1r 1n (r-2) (r-2) (r-2) (r-1) r-1r-1 r-1r r-1n (r-1) (r-1) rr rn (r-1) (r-1) nr nn a a a a a a a A = a a a a （r＝2,3, ,n-1） 则 A 的 r 阶顺序主子式 (0) (1) (r-2) (r-1) Δr 11 22 r-1r-1 rr = a a a a ，若 Δ r ≠0 ，则 (r-1) rr a ≠0 可定义 (r-1) ir ir (r-1) rr a c = a ，并构造 Frobenius 矩阵 r r+11 nr 1 1 L = c 1 c 1 → -1 r r+11 nr 1 1 L = -c 1 -c 1
AR=L-A= LAG (r=2,3,…,n1) 直到第(n-1)步,得到 n-1) A 则完成了消元的过程 而消元法能进行下去的条件是A≠0(r=1,2,…,n1) 二、LU分解与LDU分解 A=AO=LA=LLA=L=LLLa LA-1 容易求出 L=LLr LLm 为下三角矩阵 M1 C12 n2 令U=A为上三角矩阵,则 A=LU (L: I ower U: upper L: left R: right) 以上将A分解成一个单位下三角矩阵与上三角矩阵的乘积就称 为LU分解或LR分解。 Ax=b AELU
(0) (0) (0) (0) 11 1r 1r+1 1n (r-1) (r-1) (r-1) (r) -1 r-1 rr rr+1 rn r (r) (r) r+1r+1 r+1n (r) (r) nr+1 nn a a a a a a a A = L A = a a a a → (r-1) (r) r A = L A （r＝2,3, ,n-1） 直到第（n－1）步，得到 (0) (0) (0) 11 12 1n (1) (1) (n-1) 22 2n n-1 nn a a a a a A = a 则完成了消元的过程 而消元法能进行下去的条件是 Δ r ≠0 （r＝1,2, ,n-1） 二、 LU 分解与 LDU 分解 (0) (1) (2) (n-1) 1 1 2 1 2 3 n-1 A = A = L A = L L A = L = L L L L A 容易求出 21 1 2 n-1 n-11 n-12 n1 n2 nn-1 1 c 1 L = L L L L = c c 1 c c c 1 为下三角矩阵 令 (n-1) U = A 为上三角矩阵，则 A = LU （L: lower U: upper L: left R: right） 以上将 A 分解成一个单位下三角矩阵与上三角矩阵的乘积，就称 为 LU 分解或 LR 分解。 Ax = b A = LU
Ly =b lUx=y ←两个三角方程回代即可 LU分解不唯一,显然,令D为对角元素不为零的n阶对角阵, 则 AELUELDDUELU 可以采用如下的方法将分解完全确定,即要求 (1)L为单位下三角矩阵 (2)U为单位上三角矩阵 (3)将A分解为LDU,其中L、U分别为单位下三角、单位上三角矩 阵,D为对角阵D=dag[d,2…,d],而dk AA (k=1,2,“n) △=1 阶非奇异矩阵A有三角分解山或LDU的冲要条件是A的顺序 主子式4≠0(r=1,2,…n) n个顺序主子式全不为零的条件实际上是比较严格的,特别是在 数值计算中,a很小时可能会带来大的计算误差。因此,有必要采 取选主元的消元方法,这可以是列主元(在a,,a”中选 取模最大者作为新的a)、行主元(在a?,a,…B中选取 模最大者作为新的a)全主元(在所有a?(k≤isn)中选模 最大者作为新的a)。之所以这样做,其理论基础在于对于任何可 逆矩阵A,存在置换矩阵P使得PA的所有顺序主子式全不为零。 列主元素法:在矩阵的某列中选取模值最大者作为新的对角元 素,选取范围为对角线元素以下的各元素。比如第一步:找第一个未
Ly = b Ux = y 两个三角方程回代即可 LU 分解不唯一，显然，令 D 为对角元素不为零的 n 阶对角阵， 则 -1 A = LU = LDD U = LU 可以采用如下的方法将分解完全确定，即要求 （1）L 为单位下三角矩阵 （2）U 为单位上三角矩阵 （3）将 A 分解为 LDU，其中 L、U 分别为单位下三角、单位上三角矩 阵，D 为对角阵 D＝diag[ , 1 2 n d ,d , d ]，而 k k k-1 Δ d = Δ （k=1,2,…n）, Δ Δ0 =1。 n 阶非奇异矩阵 A 有三角分解 LU 或 LDU 的冲要条件是 A 的顺序 主子式 Δ r ≠0 （r=1,2， ,n） n 个顺序主子式全不为零的条件实际上是比较严格的，特别是在 数值计算中， (k-1) kk a 很小时可能会带来大的计算误差。因此，有必要采 取选主元的消元方法，这可以是列主元（在 (k-1) kk a ， (k-1) k+1 k a ，… (k-1) nk a 中选 取模最大者作为新的 (k-1) kk a ）、行主元（在 (k-1) kk a ， (k-1) k k+1 a ，… (k-1) kn a 中选取 模最大者作为新的 (k-1) kk a ）全主元（在所有 (k-1) ij a （ k i,j n ）中选模 最大者作为新的 (k-1) kk a ）。之所以这样做，其理论基础在于对于任何可 逆矩阵 A，存在置换矩阵 P 使得 PA 的所有顺序主子式全不为零。 列主元素法：在矩阵的某列中选取模值最大者作为新的对角元 素，选取范围为对角线元素以下的各元素。比如第一步：找第一个未
知数前的系数|a1|最大的一个,将其所在的方程作为第一个方程,即 交换矩阵的两行,自由项也相应变换;第二步变换时,找|B2|(i≤2) 中最大的一个,然后按照第一步的方法继续。 行主元素法:在矩阵的某行中选取模值最大者作为新的对角元 素,选取范围为对角线元素以后的各元素,需要记住未知数变换的顺 序,最后再还原回去。因此需要更多的存储空间,不如列主元素法方 便 全主元素法:若某列元素均较小或某行元素均较小时,可在各行 各列中选取模值最大者最为对角元素。与以上两种方法相比,其计算 稳定性更好,精度更高,计算量增大。 其他三角分解 1.定义设A具有唯一的LDU分解 (1)若将D、U结合起来得A=LU(U=DU),则称为A的 Doolittle 分解 (2)若将L、D结合起来得A=LU(L=LD),则称为A的 Crout分 解 2.算法 (1) Crout分解,设 12 U
知数前的系数 i1 |a | 最大的一个，将其所在的方程作为第一个方程，即 交换矩阵的两行，自由项也相应变换；第二步变换时，找 |a |(i 2) i2 中最大的一个，然后按照第一步的方法继续。 行主元素法：在矩阵的某行中选取模值最大者作为新的对角元 素，选取范围为对角线元素以后的各元素，需要记住未知数变换的顺 序，最后再还原回去。因此需要更多的存储空间，不如列主元素法方 便。 全主元素法：若某列元素均较小或某行元素均较小时，可在各行 各列中选取模值最大者最为对角元素。与以上两种方法相比，其计算 稳定性更好，精度更高，计算量增大。 三、其他三角分解 1. 定义 设 A 具有唯一的 LDU 分解 （1）若将 D、U 结合起来得 A = LU （ U = DU ），则称为 A 的 Doolittle 分解 （2）若将 L、D 结合起来得 A = LU （ L = LD ），则称为 A 的 Crout 分 解 2. 算法 （1）Crout 分解，设 11 21 22 n1 n2 nn l l l L = l l l ， 12 1n 3n 1 u u 1 u U = 1
由A=LU乘出得 ①1=a1(第1列(i=1,2,3,…n)(AL第1列 (第1行)(j=2,3,,n)(A,U第1行) ③L2=a2-142(第2列(i=23,,n)(AL第2列 )(j=34…m)(AU第2行) ⑤一般地,对AL的第k列运算,有 (k=1,2,n;=k+1,k+2,…n) ⑥对A,U的第k行运算,有 (k=12,…,n-1;j=k+1,k+2,…n) 直至最后,得到的马恰可排成 12 先算列后算行 3.厄米正定矩阵的LU分解( Cholesky分解) A=GG 其中G为下三角矩阵,G=(g1)
由 A = LU 乘出得 ① i1 i1 l = a (第1列) （i= 1,2,3, ,n） (A,L第1列) ② 1j 1j 11 a u = (第1行) （j = 2,3, ,n） (A,U第1行) l ③ i2 i2 i1 12 l = a -l u (第2列) (i= 2,3, ,n) (A,L第2列) ④ 2j 2j 21 1j ( ) 22 1 u = a -l u （j = 3,4, ,n） (A,U第2行) l ⑤ 一般地，对 A, L 的第 k 列运算，有 k-1 ik ik im mk m=1 l = a - l u (k = 1,2, ,n;i= k +1,k + 2, ,n) ⑥ 对 A，U 的第 k 行运算，有 k-1 kj kj km mj kk m=1 1 u = (a - l u ) (k = 1,2, ,n - 1;j = k +1,k + 2, ,n) l 直至最后，得到的 ij ij l ,u 恰可排成 11 12 13 1n 21 22 23 2n 31 32 33 3n n1 n2 n3 nn l u u u l l u u l l l u l l l l 先算列后算行 3. 厄米正定矩阵的 LU 分解（Cholesky 分解） H A = GG 其中 G 为下三角矩阵， ij G =(g )
ka1 Bij gik gi g 0 i< 理论上, nolesky具有中间量g可以控制(gls√同)的 好处,应较稳健,但实际计算中发现,对希尔伯特矩阵问题,不 如全主元方法。 作业:p1952、3
1 i-1 2 2 ii ik k=1 j-1 ij ij ik ik jj k=1 a - g i= j 1 g = (a - g g ) i> j g 0 i< j 理论上，Cholesky 具有中间量 ij g 可以控制（ g a ij ii ）的 好处，应较稳健，但实际计算中发现，对希尔伯特矩阵问题，不 如全主元方法。 作业：p195 2、3
