附录A应用举例 A.3应用：Gauss消去法求解线性方程组 首先看一个例子 例A1求解下面的线性方程组 T1-2x2+2x=-2 2红1-3r2-33=4 4x1+2+63=3. 解.利用Gss消去法求解：先写出增广矩阵，然后通过初等变换将其转换为阶梯形，最后通过回代求 解.具体过程可写为 09-211 通过回代求解可得 x3=-1, 2=8+73=1, 1=-2+2x2-2r3=2 将以上的做法推广到一般线性方程Ax=b,即 +a12r2+...+ainin =bi a211+a222+.+a2nIn =b2 … 高斯消去法的主要思路：将系数矩阵A化为上三角矩阵，然后回代求解 AI→-1
附录 A 应用举例 A.3 应用: Gauss 消去法求解线性方程组 首先看一个例子. 例 A.1 求解下面的线性方程组 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. □ 将以上的做法推广到一般线性方程 Ax = b, 即 a11x1 + a12x2 + · · · + a1nxn = b1 a21x1 + a22x2 + · · · + a2nxn = b2 . . . . . . . . . . . . . . . . an1x1 + an2x2 + · · · + annxn = bn 高斯消去法的主要思路: 将系数矩阵 A 化为上三角矩阵, 然后回代求解: 1
2 附录A应用举例 A3.1 Gauss消去过程 本节给出Gus消去过程的详细执行过程，写出相应算法，并编程实现 记A)-[]nxn-A,b四=[b9,b,,bT-b,即 a9=a,0=m,i,j=1,2,n. 第1步：消第1列. ”平0计算m1三哥=23n对增广矩阵进行n-1次初等变换，即依次 阵的第i行减去第1行的m1倍，将新得到的矩阵记为A②)，即 [aa…ab … a 2 a2·a恩b2 其中 a2=9-m1a9,b2=b0-m1b,i,j=2,3.,n 第2步：消第2列. 设a唱≠0，计算m2 =34…n低次将49的第行减去第2行的ma院将新得到 a2) 的矩阵记为A③)，即 … 2 A(3) a … a …a 其中 a8=a2-m22,b3=b2-m2b2,i,j=3,4,,n 依此类推，经过k-1步后，可得新矩阵Ak): … a A) 第k步：消第k列 设盥≠0计算m6= ，i=k+1,k+2,,n.依次将A的第i行减去第k行的m倍 将新得到的矩阵记为4号，矩阵元素的更新公式为 a5+)=a-mt喝，6+)=6-mb,ij=k+1,k+2,n.A http://math.ecnu.edu.cn/-jypan
· 2 · 附录 A 应用举例 A.3.1 Gauss 消去过程 本节给出 Gauss 消去过程的详细执行过程, 写出相应算法, 并编程实现. 记 A(1) = [a (1) ij ]n×n = A, b (1) = [b (1) 1 , b(1) 2 , . . . , b(1) n ] ⊺ = b, 即 a (1) ij = aij , b(1) i = bi , i, j = 1, 2, . . . , n. 第 1 步: 消第 1 列. 设 a (1) 11 ̸= 0, 计算 mi1 = a (1) i1 a (1) 11 , i = 2, 3, . . . , n. 对增广矩阵进行 n − 1 次初等变换, 即依次将增广矩 阵的第 i 行减去第 1 行的 mi1 倍, 将新得到的矩阵记为 A(2) , 即 A (2) = a (1) 11 a (1) 12 · · · a (1) 1n b (1) 1 a (2) 22 · · · a (2) 2n b (2) 2 . . . . . . . . . . . . a (2) n2 · · · a (2) nn b (2) n , 其中 a (2) ij = a (1) ij − mi1a (1) 1j , b(2) i = b (1) i − mi1b (1) 1 , i, j = 2, 3, . . . , n. 第 2 步: 消第 2 列. 设 a (2) 22 ̸= 0, 计算 mi2 = a (2) i2 a (2) 22 , i = 3, 4, . . . , n. 依次将 A(2) 的第 i 行减去第 2 行的 mi2 倍, 将新得到 的矩阵记为 A(3) , 即 A (3) = a (1) 11 a (1) 12 a (1) 13 · · · a (1) 1n b (1) 1 a (2) 22 a (2) 23 · · · a (2) 2n b (2) 2 a (2) 33 · · · a (2) 3n b (3) 3 . . . . . . . . . . . . a (3) n3 · · · a (3) nn b (3) n , 其中 a (3) ij = a (2) ij − mi2a (2) 2j , b(3) i = b (2) i − mi2b (2) 2 , i, j = 3, 4, . . . , n. 依此类推, 经过 k − 1 步后, 可得新矩阵 A(k) : A (k) = a (1) 11 · · · a (1) 1k · · · a (1) 1n b (1) 1 . . . . . . . . . . . . a (k) kk · · · a (k) kn b (k) k . . . . . . . . . . . . a (k) nk · · · a (3k) nn b (k) n , 第 k 步: 消第 k 列. 设 a (k) kk ̸= 0, 计算 mik = a (k) ik a (k) kk , i = k + 1, k + 2, . . . , n. 依次将 A(k) 的第 i 行减去第 k 行的 mik 倍, 将新得到的矩阵记为 A(k+1) , 矩阵元素的更新公式为 a (k+1) ij = a (k) ij − mika (k) kj , b(k+1) i = b (k) i − mikb (k) k , i, j = k + 1, k + 2, . . . , n. (A.1) http://math.ecnu.edu.cn/~jypan
A3应用：Gaus消去法求解线性方程组 …3 这样，经过n-1步后，即可得到一个上三角矩阵A: 最后，回代求解 1 = i=n-1,n-2,1. 白注记：由上面的求解过程可知，Gus消去法能顺利进行下去的充要条件是a≠0，i=1,2,,n 这些元素被称为主元 定理A】所有主元都不为零的充要条件是A的所有顺序主子式都不为零】 推论A2Gaus消去法能顺利完成的充要条件是A的所有顺序主子式都不为零 Gaus消去法的运算量 下面统计整个Gaus消去法的乘除运算的次数. 在第k步中，我们需要计算 mk=k/a限，i=k+1,,n→n-k次 +=9-m4喝，i=k+1n→a-k次 6+)=6的-mb,i=k+1,,n→n-k次 所以整个消去过程的乘除运算为 2m-+a-r-2+e=a-+a-2-到 易知，回代求解过程的乘除运算为 1+∑n-i+1=nn+) -1 2 所以整个Gaus消去法的乘除运算为 3 +2-号 同理，也可统计出，Gaus消去法中的加诚运算次数为 http://math.ecnu.edu.cn/-jypan
A.3 应用: Gauss 消去法求解线性方程组 · 3 · 这样, 经过 n − 1 步后, 即可得到一个上三角矩阵 A(n) : A (n) = a (1) 11 a (1) 12 · · · a (1) 1n b (1) 1 a (2) 22 · · · a (2) 2n b (2) 2 . . . . . . . . . a (n) nn b (n) n . 最后, 回代求解 xn = b (n) n a (n) nn , xi = 1 a (i) ii b (i) i − Xn j=i+1 a (i)xj ij , i = n − 1, n − 2, . . . , 1. b 注记：由上面的求解过程可知, Gauss消去法能顺利进行下去的充要条件是 a (i) ii ̸= 0, i = 1, 2, . . . , n, 这些元素被称为 主元. 定理 A.1 所有主元都不为零的充要条件是 A 的所有顺序主子式都不为零. 推论 A.2 Gauss 消去法能顺利完成的充要条件是 A 的所有顺序主子式都不为零. Gauss 消去法的运算量 下面统计整个 Gauss 消去法的乘除运算的次数. 在第 k 步中, 我们需要计算 mik = a (k) ik /a (k) kk , i = k + 1, . . . , n → n − k 次 a (k+1) ij = a (k) ij − mika (k) kj , i = k + 1, . . . , n → (n − k) 2 次 b (k+1) i = b (k) i − mikb (k) k , i = k + 1, . . . , n → n − k 次 所以整个消去过程的乘除运算为 nX−1 k=1 2(n − k) + (n − k) 2 = nX−1 ℓ=1 2ℓ + ℓ 2 = n(n − 1) + n(n − 1)(2n − 3) 6 . 易知, 回代求解过程的乘除运算为 1 + nX−1 i=1 n − i + 1 = n(n + 1) 2 . 所以整个 Gauss 消去法的乘除运算为 n 3 3 + n 2 − n 3 . 同理, 也可统计出, Gauss 消去法中的加减运算次数为 n 3 3 + n 2 2 − 5n 6 . http://math.ecnu.edu.cn/~jypan
附录A应用举例 凸注记：评价算法的一个主要指标是执行时间，但这依赖于计算机硬件和编程技巧等，国此直接给 出算法执行时问是不太现实的.所以我们通常是统计算法中算术运算（加减来除）的次数在数值 算法中，大多仅仅涉及加减乘除和开方运算.一般地，加减运算次数与来法运算次数具有相同的 量级，而除法运算和开方运算次数具有更低的量级。 白注记：为了尽可能地减少运算量，在实际计算中，数，向量和矩阵做乘法运算时的先后执行次序 为：先计算数与向量的来法，然后计算矩阵与向量的来法，最后才计算矩阵与矩阵的来法。 A3.2选主元Gauss消去法 我们知道，只要系数矩阵A非奇异，则线性方程组就存在唯一解，但Guss消去法却不一定有效. 例A2求解线性方程组A红=，其中A= -间 由于主元a41=0,因此Gaus消去法无法顺利进行下去 在实际计算中，即使主元都不为零，但如果主元的值很小，由于舍入误差的原因，也可能会给计算结 果带来很大的误差。 解决这个问题的一个有效方法就是选主元，具体做法就是：在执行Gaus消去过程的第k步之前 插人下面的选主元过程 ①选取列主元-=器{} @交换：如果k≠，则交换第k行与第行，相应地，也要交换b的第k个与第i,个元素。 上面选出的就称为列主元.加入这个选主元过程后，就不会出现主元为零的情况（除非A是奇异 的.由此，Gaus消去法就不会失效.这种带选主元的Gaus消去法就称为列主元Gaus消去法或部分 选主元Gaus消去法(Gaussian Elimination with Partial Pivoting,GEPP).这是当前求解中小规模线性方程 组的首选方法. http://math.ecnu.edu.cn/-jypan
· 4 · 附录 A 应用举例 b 注记：评价算法的一个主要指标是执行时间, 但这依赖于计算机硬件和编程技巧等, 因此直接给 出算法执行时间是不太现实的. 所以我们通常是统计算法中算术运算 (加减乘除) 的次数. 在数值 算法中, 大多仅仅涉及加减乘除和开方运算. 一般地, 加减运算次数与乘法运算次数具有相同的 量级, 而除法运算和开方运算次数具有更低的量级. b 注记：为了尽可能地减少运算量, 在实际计算中, 数, 向量和矩阵做乘法运算时的先后执行次序 为: 先计算数与向量的乘法, 然后计算矩阵与向量的乘法, 最后才计算矩阵与矩阵的乘法. A.3.2 选主元 Gauss 消去法 我们知道, 只要系数矩阵 A 非奇异, 则线性方程组就存在唯一解, 但 Gauss 消去法却不一定有效. 例 A.2 求解线性方程组 Ax = b, 其中 A = " 0 1 1 0# , b = " 1 1 # . 由于主元 a11 = 0, 因此 Gauss 消去法无法顺利进行下去. 在实际计算中, 即使主元都不为零, 但如果主元的值很小, 由于舍入误差的原因, 也可能会给计算结 果带来很大的误差. 解决这个问题的一个有效方法就是选主元, 具体做法就是: 在执行 Gauss 消去过程的第 k 步之前, 插入下面的选主元过程. ⃝1 选取 列主元: a (k) ik,k = max k≤i≤n n a (k) i,k o ⃝2 交换: 如果 ik ̸= k, 则交换第 k 行与第 ik 行, 相应地, 也要交换 b 的第 k 个与第 ik 个元素. 上面选出的 a (k) ik,k 就称为 列主元. 加入这个选主元过程后, 就不会出现主元为零的情况 (除非 A 是奇异 的). 由此, Gauss 消去法就不会失效. 这种带选主元的 Gauss 消去法就称为 列主元 Gauss 消去法 或 部分 选主元 Gauss 消去法 (Gaussian Elimination with Partial Pivoting, GEPP). 这是当前求解中小规模线性方程 组的首选方法. http://math.ecnu.edu.cn/~jypan