追赶法(经典计算)

一、算法理论在一些实际问题中，例如解常微分方程边值问题，解热传导方程以及船体数学放样中建立三次样条函数等，都会要求解系数矩阵为对角占优的三对角线方程组nnnnnnnnnffffxxxxbacbacbacb12112111122211，简记为fAx.求解fAx等价于解两个三角形方程组：yfLy求,；xyUx求,.从而得到解三对角线方程组的追赶法公式：(1)计算i的递推公式;1,,3,2,/,/111niabcbciiiii(2)解fLy;,,3,2,/,/11111niabyafybfyiiiiiii(3)解yUx.1,2,2,1,,1nnixyxyxiiiinn我们将计算系数的过程称为追的过程，及nnyyy21121将计算方程组的解的过程称为赶的过程。11xxxnn二、算法框图if2i≥n+1c1c1/b1f1f1/b1ifi+1iiiiitfaff1)1,...,2(nitcciii1iiiiuabt11nnnnnnncabfaff)1,...,1(1nifuffiiii输出f1,f2,,fn输入ai,bi,ci,fiFT三、算法程序#includestdio.h#includemath.h#includestdlib.h#defineN20doublea[N],b[N],c[N-1],f[N],r[N];intn;voidLUDecompose();//LU分解voidbackSubs();//回代voidmain(){printf(请输入方程的维数n＝);scanf(%d,&n);getchar();if(nN||n=0){printf(由于该维数过于犀利,导致程序退出!);return;}printf(\n输入下三角元素\n);printf(输入%d个a值:,n-1);for(inti=1;in;i++)scanf(%lf,&a[i]);getchar();printf(\n输入主对角线元素\n);printf(输入%d个b值:,n);for(i=0;in;i++)scanf(%lf,&b[i]);getchar();printf(\n输入上三角元素\n);printf(输入%d个c值:,n-1);for(i=0;in-1;i++)scanf(%lf,&c[i]);getchar();printf(\n输入%d个方程组右端项:\n,n);for(i=0;in;i++)scanf(%lf,&f[i]);getchar();LUDecompose();backSubs();printf(\n线性方程组的解为:\n);for(i=0;in;i++)printf(x%d=%lf\n,i+1,f[i]);}voidLUDecompose(){//α被b取代,β被c取代,以节省存储空间c[0]=c[0]/b[0];for(inti=1;in-1;i++){r[i]=a[i];b[i]=b[i]-r[i]*c[i-1];c[i]=c[i]/b[i];}r[i]=a[i];b[i]=b[i]-r[i]*c[i-1];}voidbackSubs(){//y被f取代,x也被f取代,以节省存储空间f[0]=f[0]/b[0];for(inti=1;in;i++)f[i]=(f[i]-r[i]*f[i-1])/b[i];f[n-1]=f[n-1];for(i=n-2;i=0;i--)f[i]=f[i]-c[i]*f[i+1];}四、算法实现例1．用该程序计算三对角线方程组2100012100012100012100012A－－－－－－－－＝，00001b计算其方程组的解。解：运行程序（1）显示出请输入方程组的维数：n=5.，回车。（2）显示出请输入下三角元素输入4个a值：-1-1-1-1，回车。（3）显示出请输入主对角线元素输入5个b值：22222，回车。（4）显示出请输入上三角元素输入4个c值：-1-1-1-1，回车。（5）显示出请输入5个方程组右端顶：10000，回车。其解为166667.0333333.0500000.0666667.0833333.0例2．用该程序计算三对角线方程组3100013100013100013100013A＝，00011b计算其方程组的解。解：运行程序（1）显示出请输入方程组的维数：n=5.，回车。（2）显示出请输入下三角元素输入4个a值：1111，回车。（3）显示出请输入主对角线元素输入5个b值：33333，回车。（4）显示出请输入上三角元素输入4个c值：1111，回车。（5）显示出请输入5个方程组右端顶：11000，回车。其解为013889.0041167.0111111.0291667.0236111.0