数值分析 第二讲线性方程组的直接解法 Gauss消去法·矩阵分解法 喜目录 2.1 Gauss消去法 2.2 矩阵分解法 2.3 扰动分析 2.4解的改进* 潘建瑜@MATH.ECNU https://math.ecnu.edu.cn/-jypan/Teaching/NA
数值分析 第二讲 线性方程组的直接解法 Gauss 消去法 • 矩阵分解法 2.1 Gauss 消去法 2.2 矩阵分解法 2.3 扰动分析 2.4 解的改进 * 目录 https://math.ecnu.edu.cn/~jypan/Teaching/NA 潘建瑜 @MATH.ECNU
2-1|Gaus消去法 2.1 Gauss消去法 2.1.1 Gauss消去过程（算法描述） 2.1.2运算量统计（计算复杂度） https://math.ecnu.edu.cn/-jypan/Teaching/NA
2-1 Gauss 消去法 2.1 Gauss 消去法 2.1.1 Gauss 消去过程 (算法描述) 2.1.2 运算量统计 (计算复杂度) https://math.ecnu.edu.cn/~jypan/Teaching/NA
Gauss消去法 图Gauss消去法的基本思想是消元 图早在2000年前，中国古代学者就提出了消元思想（记载在公元初《九章算术》方程 章中)，Newton,Lagrange,Gauss,Jacobi等都对此做过研究， 图我们目前采用的算法描述方式是十九世纪三十年代后期才形成的 aussian elimination(GE)is the standard method Nicholas J.Higham Jfor solving a system of linear equations.As such, Royal Society it is one of the most ubiquitous numerical algorithms Royal Academy of Engineering and plays a fundamental role in scientific computation. Academia Europaea GE was known to the ancient Chinese!and is National Academy of Engineering familiar to many school children as the intuitively President of SIAM, natural method of eliminating variables from linear ACM Fellow,SIAM Fellow equations. Nicholas J.Higham.Gaussian elimination.WIREs Computational Statistics.3(2011).230-238. http://math.ecnu.edu.cn/-jypan 3/52
Gauss 消去法 Gauss 消去法的基本思想是消元. 早在 2000 年前, 中国古代学者就提出了消元思想（记载在公元初《九章算术》方程 章中）, Newton, Lagrange, Gauss, Jacobi 等都对此做过研究. 我们目前采用的算法描述方式是十九世纪三十年代后期才形成的. http://math.ecnu.edu.cn/~jypan 3/52
个例子 例求解下面的线性方程组 x1-2x2+2x3=-2 2x1-3x2-3x3=4 4r1+x2+6x3=3. Gauss消去法：先写出增广矩阵，然后通过初等变换将其转换为阶梯形（上三角） 1 -2 2 2 ②-0×2 1-22-2 1 -2 2 -2 ③-×4 ⑥-②x9 2 -3 -3 4 0 1 -7 8 0 1 -7 8 6 3 09-2 11 0 061-61 通过回代求解可得 x3=-1,2=8+7x3=1,x1=-2+2x2-2xg=2. http://math.ecnu.edu.cn/-jypan 4/52
一个例子 例 求解下面的线性方程组 x1 − 2x2 + 2x3 = −2 2x1 − 3x2 − 3x3 = 4 4x1 + x2 + 6x3 = 3. Gauss 消去法: 先写出增广矩阵, 然后通过初等变换将其转换为阶梯形 (上三角) 1 −2 2 − 2 2 −3 −3 4 4 1 6 3 ⃝2 −⃝1 ×2 ⃝3 −⃝1 ×4 −−−−−−→ 1 −2 2 −2 0 1 −7 8 0 9 −2 11 ⃝3 −⃝2 ×9 −−−−−−→ 1 −2 2 −2 0 1 −7 8 0 0 61 −61 通过回代求解可得 x3 = −1, x2 = 8 + 7x3 = 1, x1 = −2 + 2x2 − 2x3 = 2. http://math.ecnu.edu.cn/~jypan 4/52
推广到一般线性方程 a11x1+a12x2+··+a1nxm=b1 a21x1十a22x2+·+a2mxn=b2 an11+an2T2+..+annEn on 高斯消去法的主要思路： 将系数矩阵A化为上三角矩阵，然后回代求解 A → http://nath.ecnu.edu.cn/-jypan 5/52
推广到一般线性方程 a11x1 + a12x2 + · · · + a1nxn = b1 a21x1 + a22x2 + · · · + a2nxn = b2 . . . . . . . . . . . . . . . . an1x1 + an2x2 + · · · + annxn = bn 高斯消去法的主要思路: 将系数矩阵 A 化为上三角矩阵, 然后回代求解 ✍ 高斯消去法是求解线性方程组的经典算法, 是线性代数的重要组成部分, 除了用于线 性方程组求解外, 还用于计算行列式、矩阵的秩、矩阵的逆等. http://math.ecnu.edu.cn/~jypan 5/52