第2章:误差分析 33约当消去法 大概是由于以前人们使用计算工具非常落后,所以计 算量较小的计算方法更受欢迎 解线性方程组的约当消去法的计算量比高斯消去法 稍大一些,这对于我们现在使用的计算机来说,完全 算不了什么。 约当消去法算法更简单,编程的方式更灵活,还可用 来求解有无数组解的线性方程组,还可用来求矩阵的 逆。所以约当消去法的价值超过了高斯消去法。 高斯消去法的回顾 高斯消去法的的关键是把线性方程组化为上三角形 线性方程组,也就是利用aKk不为零来消去 aK+1K,…aNK,不急于消去a1K;…,aK1仅仅是为了减 少计算量,并非一定要留下一个回代过程 结论,我们当然可以利用aKK不为零来同时消去 a1K,…,aKK,方法与消去ak+1K;…,aNK是类似的, 从而可以兔去回代过程 牢记:如果aKk不为零我们可以从第K个方程中解 出xK从而可以从其它方程中消去xk,这就是约当消去 法的核心思想
第 2 章：误差分析 - 1 - 1/11 3.3 约当消去法 大概是由于以前人们使用计算工具非常落后，所以计 算量较小的计算方法更受欢迎。 解线性方程组的约当消去法的计算量比高斯消去法 稍大一些，这对于我们现在使用的计算机来说，完全 算不了什么。 约当消去法算法更简单，编程的方式更灵活，还可用 来求解有无数组解的线性方程组，还可用来求矩阵的 逆。所以约当消去法的价值超过了高斯消去法。 高斯消去法的回顾 高斯消去法的的关键是把线性方程组化为上三角形 线性方程 组，也 就是利用 aK K 不为零来 消去 aK+1,K,…,aN,K,不急于消去 a1,K,…,aK-1,K 仅仅是为了减 少计算量，并非一定要留下一个回代过程。 结论，我们当然可以利用 aK K 不为零来同时消去 a1,K，…,a-K-1,K，方法与消去 aK+1,K,…,aN,K 是类似的， 从而可以免去回代过程。 牢记：如果 aK K不为零,我们可以从第 K 个方程中解 出 xK 从而可以从其它方程中消去xK,这就是约当消去 法的核心思想
第2章:误差分析 2.算法说明 对K=1,2,…,M 1.将第K个方程两边同时除以xk项的系数aK; 2对l=1;…M A如果|= K CONTINUE; B方程()=方程()D程(K】ax; 计算量的估计: 第K步计算量为: M (M+1-KO(M--MK+M=O(M+MK) 总计算量为:o(0.5M) 参看并测试C语言代码 4.推广应用:矩阵求逆 用约当消去法解线性方程组Ax=b的实际效果是将原 方程组两边同时左乘以A的逆A1,从而直接得到 x=A1b问题是如何将A保存下来 对于MxM可逆矩阵A我们可以构造Mx2M矩阵 T=(A那么用约当消去法把T的左边M列化为单位 矩阵后,其效果相当于用A左乘T从而得到A(A =(A),所以T的后面的M列就是我们所要求的A1
第 2 章：误差分析 - 2 - 2/11 2.算法说明 对 K=1,2,…,M: 1.将第 K 个方程两边同时除以 xK 项的系数 aKK;; 2.对 I=1,…,M: A.如果 I==K,CONTINUE; B.方程(I)=方程(I)-[方程(K)]* aI K; 计算量的估计： 第 K 步计算量为： M·(M+1-K)=O(M2 -MK+M)=O(M2+MK) 总计算量为：O(0.5M3 ) 参看并测试 C 语言代码 4.推广应用：矩阵求逆 用约当消去法解线性方程组 Ax=b 的实际效果是将原 方程组两边同时左乘以 A 的逆 A -1 ,从而直接得到 x=A-1b,问题是如何将 A -1 保存下来。 对于 M×M 可逆矩阵 A,我们可以构造 M×2M 矩阵 T=(A I),那么用约当消去法把 T 的左边 M 列化为单位 矩阵后，其效果相当于用 A -1 左乘 T,从而得到 A -1 (A I)=(I A-1 ),所以 T 的后面的 M 列就是我们所要求的 A -1
第2章:误差分析 5.两个算法的对比分析 计算量:高斯消去法为O(0.33N3),约当消去法为 O(0.5N)从现代的观点看,两者的数量级相同; 算法简单:约当消去法占优; 通用性:约当消去法占优; 数宇稳定性:约当消去法更易于与解决。 结论:如果用手工或计算器求解线性方程组(比如应 付考试),用高斯消去法较好,如果编程用计算机求 解线性方程组,则用约当消去法更好。 4选主元消去法 无论是高斯消去法还是约当消去法解线性方程组,我 们都要进行除法运算当某个akK的绝对值非常小时 这两种方法的数值稳定性可能不好,为此。我们可用 选主元消去法。 选主元的思想就是把akK;ak+K;…,aMκ中绝对值最大 的元素移到主对角线上来 1,找到主元,并记下它的位置 这个问题看起来很简单,编程又有点麻烦,又由于很 多场合都有这类问题,所以我们首先进行一般性讨 论
第 2 章：误差分析 - 3 - 3/11 5.两个算法的对比分析 计算量：高斯消去法为 O(0.33N3 ),约当消去法为 O(0.5N3 ),从现代的观点看，两者的数量级相同； 算法简单：约当消去法占优； 通用性： 约当消去法占优； 数字稳定性：约当消去法更易于与解决。 结论：如果用手工或计算器求解线性方程组（比如应 付考试），用高斯消去法较好，如果编程用计算机求 解线性方程组，则用约当消去法更好。 3.4 选主元消去法 无论是高斯消去法还是约当消去法解线性方程组，我 们都要进行除法运算。当某个 aKK 的绝对值非常小时， 这两种方法的数值稳定性可能不好，为此。我们可用 选主元消去法。 选主元的思想就是把 aKK,aK+1K,…,aMK 中绝对值最大 的元素移到主对角线上来。 1，找到主元，并记下它的位置 这个问题看起来很简单，编程又有点麻烦，又由于很 多场合都有这类问题，所以我们首先进行一般性讨 论
第2章:误差分析 假如X是一般的N维数组,我们要找出Ⅹ的绝对 值最大的成员,并记住它的下标值,可按下面方式完 成 j0=0 x0=fabs(x[0D; for(=1:j<N++) i if(fabs(x[<x0) continue; x0=fabs(x[j: j0=j; 类似地,我们也可以找出多维数组中的绝对值最大元 以及所在位置 2.选列主元方法 无论那种消元方法,我们都可以选列主元进行消元。 选列主元算法相对说来简单,而且也很有效,所以提 倡采用。假如算法进行到第K步,选列主元的方法可 表述为 找出aK,a+1k…,ahk中绝对值最大者aMK 把第K个方程和第M个方程的位置互换; 参看(类似)C语言的源代码
第 2 章：误差分析 - 4 - 4/11 假如 X 是一般的 N 维数组，我们要找出 X 的绝对 值最大的成员，并记住它的下标值，可按下面方式完 成： j0=0; x0=fabs(x[0]); for(j=1;j<N;j++) { if(fabs(x[j])<x0) continue; x0=fabs(x[j]); j0=j; } 类似地，我们也可以找出多维数组中的绝对值最大元 以及所在位置。 2．选列主元方法 无论那种消元方法，我们都可以选列主元进行消元。 选列主元算法相对说来简单，而且也很有效，所以提 倡采用。假如算法进行到第 K 步，选列主元的方法可 表述为 找出 aKK，aK+1K,…, anK中绝对值最大者 aMK; 把第 K 个方程和第 M 个方程的位置互换； 参看（类似）C 语言的源代码
第2章:误差分析 提示:虽然还可以进一步形成全组元消去法,实际已 经没有必要了。大家再多用点功也不难变出来,不过 更麻烦些。也就是说不难,但挺麻烦,而且没多大实 际用处。 35解三对角方程的追赶法 如果线性方程组Ax=b的系数矩阵除了主对角限和次 主对角线上的元素外,其余的元素均为零,则称为是 三对角线性方程组。三对角线性方程组的一般形式为 (b, x,+c,r2 a,x,+b,x,+C,x, ax+bx +cx +.x.tc ar+by r,=d 许多大规模的线性方程组正好是三对角形式,所以利 用它的特殊性而形成更有效的方法就很有意义
第 2 章：误差分析 - 5 - 5/11 提示：虽然还可以进一步形成全组元消去法，实际已 经没有必要了。大家再多用点功也不难变出来，不过 更麻烦些。也就是说不难，但挺麻烦，而且没多大实 际用处。 3.5 解三对角方程的追赶法 如果线性方程组 Ax=b 的系数矩阵除了主对角限和次 主对角线上的元素外，其余的元素均为零，则称为是 三对角线性方程组。三对角线性方程组的一般形式为 + = + + = + + = + + = + = − − − − − − − N N N N N N N N N N N N a x b x d a x b x c x d a x b x c x d a x b x c x d b x c x d 1 1 2 1 1 1 1 3 2 3 3 3 4 3 2 1 2 2 2 3 2 1 1 1 2 1 许多大规模的线性方程组正好是三对角形式，所以利 用它的特殊性而形成更有效的方法就很有意义