华东师范大学：《现代数值分析》课程教学课件（数值线性代数）第二讲 线性方程组的直接解法（二）特殊方程组求解、扰动分析、解的改进

根据上面的计算公式，可得下面的算法： 秦 算法2.1 Cholesky分解算法 1:for j=1 to n do 1/2 2: 3: fori=j+1 to n do 1-1 5: end for 6:end for http://math.ecnu.edu.cn/~jypan 6/42

根据上面的计算公式, 可得下面的算法: 算法 2.1 Cholesky 分解算法 1: for j = 1 to n do 2: ljj = ( ajj − ∑ j−1 k=1 l 2 jk)1/2 3: for i = j + 1 to n do 4: lij = ( aij − ∑ j−1 k=1 likljk) /ljj 5: end for 6: end for http://math.ecnu.edu.cn/~jypan 6/42

秦 几点说明 ·与LU分解一样，可以利用A的下三角部分来存储工 ·Choleky分解算法的运算量为303+0(n2),大约为LU分解的一半 ·Cholesky分解算法是稳定的，稳定性与全主元Gauss消去法相当，故不需要 选主元 ·基于Cholesky分解的求解方法称为 平方根法 http://math.ecnu.edu.cn/~jypan 7/42

几点说明 • 与 LU 分解一样, 可以利用 A 的下三角部分来存储 L • Cholesky 分解算法的运算量为 1 3 n 3 + O(n 2 ), 大约为 LU 分解的一半 • Cholesky 分解算法是稳定的, 稳定性与全主元 Gauss 消去法相当, 故不需要 选主元 • 基于 Cholesky 分解的求解方法称为 平方根法 http://math.ecnu.edu.cn/~jypan 7/42

秦 改进的Cholesky分解算法 为了避免开方运算，我们可以将A分解为：A=LDLT,即 a11a12 1 d 121 …lnl a21 022··· a2n l21 1 d2 In2 .. am1an2·· ann ln1…ln,n-11 dn 通过待定系数法可得 j-1 lkd4lk=dl+】 likdklik: i,j=1,2,,n. 基于该分解的求解对称正定线性方程组的算法称为 改进的平方根法 http://math.ecnu.edu.cn/~jypan 8/42

改进的 Cholesky 分解算法 为了避免开方运算, 我们可以将 A 分解为: A = LDL⊺ , 即         a11 a12 · · · a1n a21 a22 · · · a2n . . . . . . . . . an1 an2 · · · ann         =         1 l21 1 . . . . . . ln1 · · · ln,n−1 1                 d1 d2 . . . dn                 1 l21 · · · ln1 1 · · · ln2 . . . . . . 1         通过待定系数法可得 aij = ∑n k=1 likdkljk = dj lij + ∑ j−1 k=1 likdkljk, i, j = 1, 2, . . . , n. 基于该分解的求解对称正定线性方程组的算法称为 改进的平方根法 http://math.ecnu.edu.cn/~jypan 8/42

秦 算法2.2改进的平方根法 1:forj=1 ton do%先计算分解 2 4,=a-∑d4 3: for i=j+1 to n do 4: l6=(a-∑1 likdkljk)/d 5: end for 6:end for 7:=b1 %解方程组：Ly=b和DLTx=y 8:for i=2 to n do 9:： =b:-∑1lk张 10:end for 11:In =yn/dn 12:for i=n-1 to 1 do 13: xi=/d-∑k=i+1lktk 14:end for http://math.ecnu.edu.cn/~jypan 9/42

算法 2.2 改进的平方根法 1: for j = 1 to n do % 先计算分解 2: dj = ajj − ∑ j − 1 k=1 l 2 jk d k 3: for i = j + 1 to n do 4: lij = ( aij − ∑ j − 1 k=1 lik d k ljk)/ dj 5: end for 6: end for 7: y 1 = b 1 % 解方程组 : Ly = b 和 DL ⊺ x = y 8: for i = 2 to n do 9: y i = b i − ∑ i − 1 k=1 lik y k 10: end for 11: x n = y n / d n 12: for i = n − 1 to 1 do 13: x i = y i / d i − ∑ nk = i+1 lki x k 14: end for http://math.ecnu.edu.cn/~jypan 9/42

秦 2.2 对称不定线性方程组 A→非奇异，对称但不定 若A存在LU分解，即A=LU,则可写成 A=LDLT 然而，当A不定时，其LU分解不一定存在 若采用选主元LU分解，则其对称性将被破坏 *本小节内容只需了解。 http://math.ecnu.edu.cn/~jypan 10/42

2.2 对称不定线性方程组 ∗ A → 非奇异, 对称 但 不定 若 A 存在 LU 分解, 即 A = LU, 则可写成 A = LDL⊺  然而, 当 A 不定时, 其 LU 分解不一定存在. 若采用选主元 LU 分解, 则其对称性将被破坏. ∗ 本小节内容只需了解。 http://math.ecnu.edu.cn/~jypan 10/42