3.3 约当消去法.doc

《3.3 约当消去法.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、3.3约当消去法大概是由于以前人们使用计算工具非常落后，所以计算量较小的计算方法更受欢迎。解线性方程组的约当消去法的计算量比高斯消去法稍大一些，这对于我们现在使用的计算机来说，完全算不了什么。约当消去法算法更简单，编程的方式更灵活，还可用来求解有无数组解的线性方程组，还可用来求矩阵的逆。所以约当消去法的价值超过了高斯消去法。高斯消去法的回顾高斯消去法的的关键是把线性方程组化为上三角形线性方程组，也就是利用aKK不为零来消去aK+1,K,…,aN,K,不急于消去a1,K,…,aK-1,K仅仅是为了减少计算量，并非一定要留下一个回代过程。结论，我们当然可以利用aKK不

2、为零来同时消去a1,K，…,a-K-1,K，方法与消去aK+1,K,…,aN,K是类似的，从而可以免去回代过程。牢记：如果aKK不为零,我们可以从第K个方程中解出xK从而可以从其它方程中消去xK,这就是约当消去法的核心思想。2.算法说明对K=1,2,…,M:1.将第K个方程两边同时除以xK项的系数aKK;;2.对I=1,…,M:A.如果I==K,CONTINUE;B.方程(I)=方程(I)-[方程(K)]*aIK;计算量的估计：第K步计算量为：M·(M+1-K)=O(M2-MK+M)=O(M2+MK)总计算量为：O(0.5M3)参看并测试C语言代码4.推广应用：矩

3、阵求逆用约当消去法解线性方程组Ax=b的实际效果是将原方程组两边同时左乘以A的逆A-1,从而直接得到x=A-1b,问题是如何将A-1保存下来。对于M×M可逆矩阵A,我们可以构造M×2M矩阵T=(AI),那么用约当消去法把T的左边M列化为单位矩阵后，其效果相当于用A-1左乘T,从而得到A-1(AI)=(IA-1),所以T的后面的M列就是我们所要求的A-15.两个算法的对比分析计算量：高斯消去法为O(0.33N3),约当消去法为O(0.5N3),从现代的观点看，两者的数量级相同；算法简单：约当消去法占优；通用性：约当消去法占优；数字稳定性：约当消去法更易于与解决。结论

4、：如果用手工或计算器求解线性方程组（比如应付考试），用高斯消去法较好，如果编程用计算机求解线性方程组，则用约当消去法更好。3.4选主元消去法无论是高斯消去法还是约当消去法解线性方程组，我们都要进行除法运算。当某个aKK的绝对值非常小时，这两种方法的数值稳定性可能不好，为此。我们可用选主元消去法。选主元的思想就是把aKK,aK+1K,…,aMK中绝对值最大的元素移到主对角线上来。1，找到主元，并记下它的位置这个问题看起来很简单，编程又有点麻烦，又由于很多场合都有这类问题，所以我们首先进行一般性讨论。假如X是一般的N维数组，我们要找出X的绝对值最大的成员，并记住它的下

5、标值，可按下面方式完成：j0=0;x0=fabs(x[0]);for(j=1;j

6、已经没有必要了。大家再多用点功也不难变出来，不过更麻烦些。也就是说不难，但挺麻烦，而且没多大实际用处。3.5解三对角方程的追赶法如果线性方程组Ax=b的系数矩阵除了主对角限和次主对角线上的元素外，其余的元素均为零，则称为是三对角线性方程组。三对角线性方程组的一般形式为许多大规模的线性方程组正好是三对角形式，所以利用它的特殊性而形成更有效的方法就很有意义。三对角线性方程组的存贮方式对于N个变元利用三对角线性方程组，我们可以说明4个长度为N的一维数组A[N],B[N],C[N],D[N]来存贮所有的非零元素。注意到方程组中的a1和cN没有定义，我们可以简单地把数组中相

7、应的元素设为零。由于C语言数组的下标是从零开始的，所以我们编程时也要作相应的调整。解的递推形式为了讨论，计算，编程的方便，我们再定义两个数组U[N]和V[N],计算格式为：结论：对于上面定义的向量U,V，我们有xk=uk-vk·xk+1,K=1,2,…,N-1.从而可以形成一个算法。解下来我们将用数学归纳法推出上面的公式，为此用n来指示所考虑的是那一个方程。当n=1时，由得记得所以结论成立。为了简化我们的讨论，我们假定原始问题会使得所出现的所有表达式都有意义，具体说来就是分母不会为零。当n=2时由得记得所以结论对于n=2也是成立的。作为数学归纳法来说，这一步也可以

8、不要，我们