第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 许多大规模的线性方程组正好是三对角形式，所以利 用它的特殊性而形成更有效的方法就很有意义
第2章:误差分析 三对角线性方程组的存贮方式 对于N个变元利用三对角线性方程组我们可以说明 4个长度为N的一维数组AN],BN],cN],DN来存 贮所有的非零元素注意到方程组中的a1和cN没有 定义,我们可以简单地把数组中相应的元素设为零 由于c语言数组的下标是从零开始的,所以我们编程 时也要作相应的调整。 解的递推形式 为了讨论,计算,编程的方便,我们再定义两个数组 UN]和VN]计算格式为: a,v d.-akvk-l Vk=1,2,…,N b 结论:对于上面定义的向量U,,我们有 Xk=uk-k°Xk+1,K=1,2,…,N-1
第 2 章：误差分析 - 6 - 6/11 三对角线性方程组的存贮方式 对于 N 个变元利用三对角线性方程组，我们可以说明 4 个长度为 N 的一维数组 A[N],B[N],C[N],D[N]来存 贮所有的非零元素。注意到方程组中的 a1 和 cN 没有 定义，我们可以简单地把数组中相应的元素设为零。 由于 C 语言数组的下标是从零开始的，所以我们编程 时也要作相应的调整。 解的递推形式 为了讨论，计算，编程的方便，我们再定义两个数组 U[N]和 V[N],计算格式为： k N b a v d a v v b a v d a u u b c v b d u k k k k k k k k k k k k k k , 1,2, , 1 1 1 1 1 1 1 1 1 1 = − − = − − = = = − − − − 结论：对于上面定义的向量 U,V，我们有 xk=uk-vk·xk+1,K=1,2,…,N-1
第2章:误差分析 从而可以形成一个算法。解下来我们将用数学归纳法 推出上面的公式,为此用n来指示所考虑的是那一个 方程 当n=1时, 由b x,+ Crx d得x1=4-5x2 6. b 记4=,"=h得x=1-2 b 所以结论成立。 为了简化我们的讨论,我们假定原始问题会使得所出 现的所有表达式都有意义,具体说来就是分母不会为 当n=2时 由{x=“w 得式2x=dcx2 记u 三8:b2-ae b2 得x2=2-V2x3 所以结论对于n=2也是成立的。作为数学归纳法来 说,这一步也可以不要,我们只是先熟悉推导的思路。 FOR N=K-1 K<N) 假如当n=K-1(K<N)时我们推得了
第 2 章：误差分析 - 7 - 7/11 从而可以形成一个算法。解下来我们将用数学归纳法 推出上面的公式，为此用 n 来指示所考虑的是那一个 方程。 当 n=1 时， 由 1 1 1 2 d1 b x + c x = 得 2 1 1 1 1 1 x b c b d x = − 记 1 1 1 1 1 1 , b c v b d u = = 得 1 1 1 2 x = u − v x 所以结论成立。 为了简化我们的讨论，我们假定原始问题会使得所出 现的所有表达式都有意义，具体说来就是分母不会为 零。 当 n=2 时 由 + + = = + 2 1 2 2 2 3 1 1 1 1 2 a x b x c x d x u v x 得 2 2 2 1 2 2 2 1 2 2 1 2 x b a v c b a v d a u x − − − − = 记 2 2 1 2 2 2 2 1 2 2 1 2 , b a v c v b a v d a u u − = − − = 得 2 2 2 3 x = u − v x 所以结论对于 n=2 也是成立的。作为数学归纳法来 说，这一步也可以不要，我们只是先熟悉推导的思路。 FOR N=K-1(K<N) 假如当 n=K-1(K<N)时我们推得了
第2章:误差分析 K-1K-2 l K-1MK-1K-2 x 那么当n=K时 由x-=-+"-x daxxk +boxx+Ckxk=d 可推得x=-,xk1 得
第 2 章：误差分析 - 8 - 8/11 = − − = − − = − − − − − − − − − − − − − K K K K K K K K K K K K K K K K x u v x b a v c v b a v d a u u 1 1 1 2 1 1 1 1 2 1 1 2 1 那么当 n=K 时 由 可推得 1 1 1 1 + − − − − − − − = K K K K K K K K K K K K x b a v c b a v d a u x 记 1 1 1 , − − − − = − − = K K K K k K K K K K K K b a v c v b a v d a u u 得 K = K − K K+1 x u v x + + = = + + − − − K K K K K K K K K K K a x b x c x d x u v x 1 1 1 1
第2章:误差分析 当K-N时, u,+v, 由 +bx =d d -aN.uN-I 可推得xNb-axV=1 重要结论 首先我们可以利用下面一组递推公式 d-a.u bbk=1,2,…,N 计算并保存{ukwk=1,2,…N},接下来再利用递推 公式 Xy=l xk=l4+v4x1,Vk=N-1,N-2,…,1 即可求出诸{x12x2…,x},从而完成问题求解。 我们把上面的第一个过程称为追过程,而把第二个过 程称为赶过程,而把所形成的方法称为追赶法
第 2 章：误差分析 - 9 - 9/11 当 K=N 时， 由 + = = + − − − − N N N K N N N N N a x b x d x u v x 1 1 1 1 可推得 1 1 − − − − = N N N N N N N b a v d a u x 重要结论 首先我们可以利用下面一组递推公式 k N b a v d a v v b a v d a u u b c v b d u k k k k k k k k k k k k k k , 1,2, , 1 1 1 1 1 1 1 1 1 1 = − − = − − = = = − − − − 计算并保存{(uk,vk),k=1,2,…,N}，接下来再利用递推 公式 = + = − − = x u v x +1 , k N 1,N 2,,1 x u k k k k N N 即可求出诸 { , , , } 1 2 N x x x ，从而完成问题求解。 我们把上面的第一个过程称为追过程，而把第二个过 程称为赶过程，而把所形成的方法称为追赶法
第2章:误差分析 算法说明 STEPI:输入数组 aN bnI cn, d|N 定义数组uNl,vN STEP2:(执行追过程) , ul=dlbl 2v[1]=c1]/b[1] 3对k=23,…N 1, w=b[k]-a[k]*v[k-1 2, u[k]=(d[k]-a[k]*u[k-11)/w 3, vk]=c[k]/w sTEP3:(执行赶过程) , XNFUNI 2对=N-1,N-2,,1 l, xk=uk+vk*x k STEP4输出{(xk],uk,vk]),k=1,2,…N},停机 注:数组中没有定义的元素都设为零比较好
第 2 章：误差分析 - 10 - 10/ 11 算法说明 STEP1:输入数组 a[N],b[N],c[N],d[N] 定义数组 u[N],v[N] STEP2: （执行追过程） 1,u[1]=d[1]/b[1] 2,v[1]=c[1]/b[1] 3,对 k=2,3,…,N 1,w=b[k]-a[k]*v[k-1] 2,u[k]=(d[k]-a[k]*u[k-1])/w 3,v[k]=c[k]/w STEP3:（执行赶过程） 1,x[N]=u[N] 2,对=N-1,N-2,…,1 1,x[k]=u[k]+v[k]*x[k] STEP4:输出{(x[k],u[k],v[k])t ,k=1,2,…,N},停机 注：数组中没有定义的元素都设为零比较好