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.算法说明对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
5.两个算法的对比分析计算量：高斯消去法为O(0.33N3),约当消去法为O(0.5N3),从现代的观点看，两者的数量级相同；
算法简单：约当消去法占优；
通用性,约当消去法占优；
数字稳定性：约当消去法更易于与解决。
结论：如果用手工或计算器求解线性方程组（比如应付考试），用高斯消去法较好，如果编程用计算机求解线性方程组，则用约当消去法更好。
3.4选主元消去法无论是高斯消去法还是约当消去法解线性方程组，我们都要进行除法运算。当某个aKK的绝对值非常小时，这两种方法的数值稳定性可能不好，为此。我们可用选主元消去法。
选主元的思想就是把aKK,aK+1K,…,aMK中绝对值最大的元素移到主对角线上来。
1，找到主元，并记下它的位置这个问题看起来很简单，编程又有点麻烦，又由于很多场合都有这类问题，所以我们首先进行一般性讨论。
假如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语言的源代码提示：虽然还可以进一步形成全组元消去法，实际已经没有必要了。大家再多用点功也不难变出来，不过更麻烦些。也就是说不难，但挺麻烦，而且没多大实际用处。
3.5 解三对角方程的追赶法如果线性方程组Ax=b的系数矩阵除了主对角限和次主对角线上的元素外，其余的元素均为零，则称为是三对角线性方程组。三对角线性方程组的一般形式为
许多大规模的线性方程组正好是三对角形式，所以利用它的特殊性而形成更有效的方法就很有意义。
三对角线性方程组的存贮方式对于N个变元利用三对角线性方程组，我们可以说明4个长度为N的一维数组A[N],B[N],C[N],D[N]来存贮所有的非零元素。注意到方程组中的a1和cN没有定义，我们可以简单地把数组中相应的元素设为零。
由于C语言数组的下标是从零开始的，所以我们编程时也要作相应的调整。
解的递推形式为了讨论，计算，编程的方便，我们再定义两个数组U[N]和V[N],计算格式为：
结论：对于上面定义的向量U,V，我们有
xk=uk-vk·xk+1,K=1,2,…,N-1.
从而可以形成一个算法。解下来我们将用数学归纳法推出上面的公式，为此用n来指示所考虑的是那一个方程。
当n=1时，
由 得
记 得
所以结论成立。
为了简化我们的讨论，我们假定原始问题会使得所出现的所有表达式都有意义，具体说来就是分母不会为零。
当n=2时由
得
记
得
所以结论对于n=2也是成立的。作为数学归纳法来说，这一步也可以不要，我们只是先熟悉推导的思路。
FOR N=K-1(K<N)
假如当n=K-1(K<N)时我们推得了
那么当n=K时由
可推得
记
得
当K=N时，
由
可推得
重要结论首先我们可以利用下面一组递推公式
计算并保存{(uk,vk),k=1,2,…,N}，接下来再利用递推公式
即可求出诸，从而完成问题求解。
我们把上面的第一个过程称为追过程，而把第二个过程称为赶过程，而把所形成的方法称为追赶法。
算法说明
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},停机注：数组中没有定义的元素都设为零比较好。
关于算法的讨论把追赶法与高斯消去法对比分析可知，追赶法实际就是高斯消去法在特殊条件下的应用。
不难看出，追赶法的计算量特别小，它仅与N成正比，而高斯消去法的计算量是与N的三次方成正比。
可以证明，如果所有的，则所给的方程组是主对角线占优的，此时算法的稳定性能好。
解线性方程组的约当消去法的计算量比高斯消去法稍大一些，这对于我们现在使用的计算机来说，完全算不了什么。
约当消去法算法更简单，编程的方式更灵活，还可用来求解有无数组解的线性方程组，还可用来求矩阵的逆。所以约当消去法的价值超过了高斯消去法。
高斯消去法的回顾高斯消去法的的关键是把线性方程组化为上三角形线性方程组，也就是利用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.算法说明对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
5.两个算法的对比分析计算量：高斯消去法为O(0.33N3),约当消去法为O(0.5N3),从现代的观点看，两者的数量级相同；
算法简单：约当消去法占优；
通用性,约当消去法占优；
数字稳定性：约当消去法更易于与解决。
结论：如果用手工或计算器求解线性方程组（比如应付考试），用高斯消去法较好，如果编程用计算机求解线性方程组，则用约当消去法更好。
3.4选主元消去法无论是高斯消去法还是约当消去法解线性方程组，我们都要进行除法运算。当某个aKK的绝对值非常小时，这两种方法的数值稳定性可能不好，为此。我们可用选主元消去法。
选主元的思想就是把aKK,aK+1K,…,aMK中绝对值最大的元素移到主对角线上来。
1，找到主元，并记下它的位置这个问题看起来很简单，编程又有点麻烦，又由于很多场合都有这类问题，所以我们首先进行一般性讨论。
假如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语言的源代码提示：虽然还可以进一步形成全组元消去法，实际已经没有必要了。大家再多用点功也不难变出来，不过更麻烦些。也就是说不难，但挺麻烦，而且没多大实际用处。
3.5 解三对角方程的追赶法如果线性方程组Ax=b的系数矩阵除了主对角限和次主对角线上的元素外，其余的元素均为零，则称为是三对角线性方程组。三对角线性方程组的一般形式为
许多大规模的线性方程组正好是三对角形式，所以利用它的特殊性而形成更有效的方法就很有意义。
三对角线性方程组的存贮方式对于N个变元利用三对角线性方程组，我们可以说明4个长度为N的一维数组A[N],B[N],C[N],D[N]来存贮所有的非零元素。注意到方程组中的a1和cN没有定义，我们可以简单地把数组中相应的元素设为零。
由于C语言数组的下标是从零开始的，所以我们编程时也要作相应的调整。
解的递推形式为了讨论，计算，编程的方便，我们再定义两个数组U[N]和V[N],计算格式为：
结论：对于上面定义的向量U,V，我们有
xk=uk-vk·xk+1,K=1,2,…,N-1.
从而可以形成一个算法。解下来我们将用数学归纳法推出上面的公式，为此用n来指示所考虑的是那一个方程。
当n=1时，
由 得
记 得
所以结论成立。
为了简化我们的讨论，我们假定原始问题会使得所出现的所有表达式都有意义，具体说来就是分母不会为零。
当n=2时由
得
记
得
所以结论对于n=2也是成立的。作为数学归纳法来说，这一步也可以不要，我们只是先熟悉推导的思路。
FOR N=K-1(K<N)
假如当n=K-1(K<N)时我们推得了
那么当n=K时由
可推得
记
得
当K=N时，
由
可推得
重要结论首先我们可以利用下面一组递推公式
计算并保存{(uk,vk),k=1,2,…,N}，接下来再利用递推公式
即可求出诸，从而完成问题求解。
我们把上面的第一个过程称为追过程，而把第二个过程称为赶过程，而把所形成的方法称为追赶法。
算法说明
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},停机注：数组中没有定义的元素都设为零比较好。
关于算法的讨论把追赶法与高斯消去法对比分析可知，追赶法实际就是高斯消去法在特殊条件下的应用。
不难看出，追赶法的计算量特别小，它仅与N成正比，而高斯消去法的计算量是与N的三次方成正比。
可以证明，如果所有的，则所给的方程组是主对角线占优的，此时算法的稳定性能好。
