第二讲 线性方程组直接解法 Gauss消去法和LU分解 2 特殊方程组的求解 3 扰动分析* 4 解的改进* 现代数值分析（数值线性代数），潘建瑜 http://math.ecnu.edu.cn/~jypan
第二讲 线性方程组直接解法 1 Gauss 消去法和 LU 分解 2 特殊方程组的求解 3 扰动分析 ∗ 4 解的改进 ∗ 现代数值分析（数值线性代数）, 潘建瑜 http://math.ecnu.edu.cn/~jypan
线性方程组的求解方法 ●直接法：LU分解，Cholesky分解， ·选代法：定常迭代法（古典迭代法），Krylov子空间迭代法 本讲介绍直接法，即Gauss消去法或LU分解 直接法优点：稳定可靠→在工程界很受欢迎 直接法缺点：运算量大O(3)→不适合大规模稀疏线性方程组 (针对特殊结构矩阵的快速方法除外)
线性方程组的求解方法 • 直接法: LU 分解, Cholesky 分解, ... • 迭代法: 定常迭代法（古典迭代法），Krylov 子空间迭代法 本讲介绍直接法, 即 Gauss 消去法 或 LU 分解 直接法优点: 稳定可靠 → 在工程界很受欢迎 直接法缺点: 运算量大 O(n 3 ) → 不适合大规模稀疏线性方程组 (针对特殊结构矩阵的快速方法除外)
1 秦 Gauss消去法和LU分解 1.1LU分解 1.2LU分解的实现 1.3IK型LU分解 1.4待定系数法计算LU分解 1.5三角方程求解 1.6选主元LU分解 http://math.ecnu.edu.cn/~jypan 3/30
1 Gauss 消去法和 LU 分解 1.1 LU 分解 1.2 LU 分解的实现 1.3 IKJ 型 LU 分解 1.4 待定系数法计算 LU 分解 1.5 三角方程求解 1.6 选主元 LU 分解 http://math.ecnu.edu.cn/~jypan 3/30
秦 1.1U分解 考虑线性方程组 Ax=b (2.1) 其中A∈Rnxn非奇异，b∈Rn为给定的右端项. Gauss消去法本质上就是对系数矩阵A进行LU分解： A=LU (2.2） 其中工是单位下三角矩阵，U为非奇异上三角矩阵。 http://math.ecnu.edu.cn/~jypan 4/30
1.1 LU 分解 考虑线性方程组 Ax = b (2.1) 其中 A ∈ R n×n 非奇异, b ∈ R n 为给定的右端项. Gauss 消去法本质上就是对系数矩阵 A 进行 LU 分解: A = LU (2.2) 其中 L 是单位下三角矩阵, U 为非奇异上三角矩阵. http://math.ecnu.edu.cn/~jypan 4/30
秦 Ly=b, Ax=b→ →只需求解两个三角方程组 Ux=y. 算法1.1 Gauss消去法 1:将A进行LU分解：A=LU; 2:向前回代：求解Ly=b,即得y=L-1b; 3: 向后回代：求解Ux=,即得x=U-1y=(LU)-1b=A-16. http://math.ecnu.edu.cn/~jypan 5/30
Ax = b ⇐⇒ Ly = b, Ux = y. =⇒ 只需求解两个三角方程组 算法 1.1 Gauss 消去法 1: 将 A 进行 LU 分解: A = LU; 2: 向前回代: 求解 Ly = b, 即得 y = L −1 b; 3: 向后回代: 求解 Ux = y, 即得 x = U −1y = (LU) −1 b = A−1 b. http://math.ecnu.edu.cn/~jypan 5/30
秦 白A非奇异，则解存在唯一，但并不一定存在LU分解剧 定理①U分解的存在性唯一性)设A∈Rnxn.则存在唯一的单位下三角 矩阵L和非奇异上三角矩阵U,使得A=LU的充要条件是A的所有顺序主 子矩阵Ak=A(1:k,1:k)都非奇异，k=1,2,·,n. (板书) http://math.ecnu.edu.cn/~jypan 6/30
✍ A 非奇异, 则解存在唯一, 但并不一定存在 LU 分解! 定理 (LU 分解的存在性和唯一性) 设 A ∈ R n×n . 则存在唯一的单位下三角 矩阵 L 和非奇异上三角矩阵 U, 使得 A = LU 的充要条件是 A 的所有顺序主 子矩阵 Ak = A(1:k, 1:k) 都非奇异, k = 1, 2, . . . , n. (板书) http://math.ecnu.edu.cn/~jypan 6/30
秦 1.2 U分解的实现一矩阵初等变换 给定一个矩阵 a11 a12 ain a21 a22 a2n A= a31 a32 a3n ∈Rnxn anl an2 ann http://math.ecnu.edu.cn/~jypan 7/30
1.2 LU 分解的实现 — 矩阵初等变换 给定一个矩阵 A = a11 a12 · · · a1n a21 a22 · · · a2n a31 a32 · · · a3n . . . . . . an1 an2 · · · ann ∈ R n×n . http://math.ecnu.edu.cn/~jypan 7/30
秦 ·第一步：假定a11≠0，构造矩阵 1 00 0 l21 1 0. 0 L1= l31 01.. 0 其中1= a1,i=2,3,n a11 ln 00…1 易知L1的逆为 1 0 0 0 -l21 1 0 0 L= -l31 0 1 0 -ln10 0 1 http://math.ecnu.edu.cn/-jypan 8/30
• 第一步: 假定 a11 ̸= 0, 构造矩阵 L1 = 1 0 0 · · · 0 l21 1 0 · · · 0 l31 0 1 · · · 0 . . . . . . ln1 0 0 · · · 1 , 其中 li1 = ai1 a11 , i = 2, 3, . . . , n. 易知 L1 的逆为 L −1 1 = 1 0 0 · · · 0 −l21 1 0 · · · 0 −l31 0 1 · · · 0 . . . . . . −ln1 0 0 · · · 1 . http://math.ecnu.edu.cn/~jypan 8/30
秦 用L1左乘A,并将所得到的矩阵记为A),则 a11 a12 0 A四=1A= 0 a嗯 a http://math.ecnu.edu.cn/~jypan 9/30
用 L −1 1 左乘 A, 并将所得到的矩阵记为 A(1) , 则 A (1) = L −1 1 A = a11 a12 · · · a1n 0 a (1) 22 · · · a (1) 2n . . . . . . . . . 0 a (1) n2 · · · a (1) nn . http://math.ecnu.edu.cn/~jypan 9/30
秦 ●第二步：将上面的操作作用在A1的子矩阵A(2:n.2:n)上，将其第一 列除第一个元素外都变为0：假定a≠0，构造矩阵 100.0 010…0 (1) L2= 0321… 0 其中 l2= 00,i=3,4,,n 0ln20…】 用L21左乘A1),并将所得到的矩阵记为A②)，则 a11 a12 a13 ，* ain 0 品 A②=L1A=L2L1A= 0 0 0 0 (2) http://math.ecnu.edu.cn/~jypan 10/30
• 第二步: 将上面的操作作用在 A(1) 的子矩阵 A(1)(2 : n, 2 : n) 上, 将其第一 列除第一个元素外都变为 0: 假定 a (1) 22 ̸= 0, 构造矩阵 L2 = 1 0 0 · · · 0 0 1 0 · · · 0 0 l32 1 · · · 0 . . . . . . . . . 0 ln2 0 · · · 1 , 其中 li2 = a (1) i2 a (1) 22 , i = 3, 4, . . . , n. 用 L −1 2 左乘 A(1) , 并将所得到的矩阵记为 A(2) , 则 A (2) = L −1 2 A = L −1 2 L −1 1 A = a11 a12 a13 · · · a1n 0 a (1) 22 a (1) 23 · · · a (1) 2n 0 0 a (2) 33 · · · a (2) 3n . . . . . . . . . . . . 0 0 a (2) n3 · · · a (2) nn . http://math.ecnu.edu.cn/~jypan 10/30
