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

第二讲 线性方程组直接解法 Gauss消去法和LU分解 2 特殊方程组的求解 3 扰动分析* 4 解的改进* 现代数位分析（数位线性代数），潘建瑜 http://math.ecnu.edu.cn/~jypan

第二讲 线性方程组直接解法 1 Gauss 消去法和 LU 分解 2 特殊方程组的求解 3 扰动分析 ∗ 4 解的改进 ∗ 现代数值分析（数值线性代数）, 潘建瑜 http://math.ecnu.edu.cn/~jypan

2 秦 特殊方程组的求解 2.1对称正定线性方程组 2.2对称不定线性方程组* 2.3三对角线性方程组 2.4带状线性方程组* http://math.ecnu.edu.cn/~jypan 2/42

2 特殊方程组的求解 2.1 对称正定线性方程组 2.2 对称不定线性方程组 ∗ 2.3 三对角线性方程组 2.4 带状线性方程组 ∗ http://math.ecnu.edu.cn/~jypan 2/42

秦 2.1对称正定线性方程组 我们首先给出对称正定矩阵的几个基本性质 ·A对称正定当且仅当A对称且所有特征值都是正的； ·A对称正定当且仅当XTAX对称正定，其中X∈Rnxm是一个任意的非 奇异矩阵： ·若A对称正定，则A的任意主子矩阵都对称正定： ·若A对称正定，则A的所有对角线元素都是正的，且 maxlai)<maxfai}, 即绝对值最大的元素出现在对角线上. http://math.ecnu.edu.cn/~jypan 3/42

2.1 对称正定线性方程组 我们首先给出对称正定矩阵的几个基本性质. • A 对称正定当且仅当 A 对称且所有特征值都是正的; • A 对称正定当且仅当 X ⊺AX 对称正定, 其中 X ∈ R n×n 是一个任意的非 奇异矩阵; • 若 A 对称正定, 则 A 的任意主子矩阵都对称正定; • 若 A 对称正定, 则 A 的所有对角线元素都是正的, 且 max i̸=j {|aij |} < max i {aii}, 即绝对值最大的元素出现在对角线上. http://math.ecnu.edu.cn/~jypan 3/42

秦 Cholesky分解 定理(Cholesky分解)设A∈Rnxn对称正定，则存在唯一的对角线元素为正 的下三角矩阵L,使得 A=LLT. 该分解称为Cholesky分解. (板书) http://math.ecnu.edu.cn/~jypan 4/42

Cholesky 分解 定理 (Cholesky 分解) 设 A ∈ R n×n 对称正定, 则存在唯一的对角线元素为正 的下三角矩阵 L, 使得 A = LL⊺ . 该分解称为 Cholesky 分解. (板书) http://math.ecnu.edu.cn/~jypan 4/42

秦 Cholesky分解的实现 设A=LLT,即 a11 a12 01m l11l21 …lnl a21 a22 ···a2n l22 l21 122 …n2 ++ am1an2··· ann Inn 直接比较等式两边的元素可得 j-1 0i= =+ i,j=1,2,.,n. k=】 http://math.ecnu.edu.cn/~jypan 5/42

Cholesky 分解的实现 设 A = LL⊺ , 即         a11 a12 · · · a1n a21 a22 · · · a2n . . . . . . . . . an1 an2 · · · ann         =         l11 l21 l22 . . . . . . . . . ln1 ln2 · · · lnn                 l11 l21 · · · ln1 l22 · · · ln2 . . . . . . lnn         . 直接比较等式两边的元素可得 aij = ∑n k=1 likljk = ljj lij + ∑ j−1 k=1 likljk, i, j = 1, 2, . . . , n. http://math.ecnu.edu.cn/~jypan 5/42

根据上面的计算公式，可得下面的算法： 秦 算法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