المبدأ

• هذه الطريقة خطية مرتبطة بتفكيك المصفوفة A الى مصفوفتين M  وN بحيث A = M+N :

 x⁽⁰⁾ ومتجهة اعتباطية للانطلاقة.

 x^(k+1) = M^-1b - M^-1N x^(k)    k = 0,....

• M هو الجزء القطري للمصفوفة A.

الخوارزم

التهيئة :  x⁽⁰⁾اعتباطية

 تكرار :

مثال

لنحل النظمة  Ax=b بحيث:

   و    

(نعتبر اعتباطيا المتجهة    )

صيغة التكراريتين الأوليتين:

الكرة x⁽¹⁾ :

x⁽¹⁾₁ = (-19)/(-16) = 19/16
x⁽¹⁾₂ = (1-3(19/16))/10 = -41/160
x⁽¹⁾₃ = (12+4(19/16)-(-41/160))/18 = 907/960
x⁽¹⁾₄ = (1-(19/16)-2(-41/160)-2(907/960))/(-14) = 751/6720

الكرة x⁽²⁾ :

x⁽²⁾₁ = (-19-6(-41/160)+2(907/960)+5(751/6720))/(-16) = 20179/21504
x⁽²⁾₂ = (1-3(20179/21504)+5(907/960)-(751/6720))/10 = 300739/1075200
x⁽²⁾₃ = (12+4(20179/21504)-(300739/1075200)-2(751/6720))/18 = 16397141/19353600
x⁽²⁾₄ = (1-(20179/21504)-2(300739/1075200)-2(16397141/19353600))/(-14)

البرمجة

• #include <math.h>
  #include <conio.h>
  #define NMAX 5
  #define ITERMAX 21
  
  double al_norme_vect(double x[NMAX],int n);
  
  void sl_gauss_seidel(double a[NMAX][NMAX],double b[NMAX],double x1[NMAX],
                       int n,int iter,double eps,double t[NMAX][ITERMAX]);
  
  main()
  {
   double eps;
   double x[NMAX],b[NMAX],sol[NMAX];
   double a[NMAX][NMAX];
   double t[NMAX][ITERMAX];
   int i,j,n;
   clrscr();
   printf("Méthode de Gauss-Seidel\n");
   printf("                           A                                     b\n");
   eps=1e-18;
   n=4;
   a[1][1]=-16;a[1][2]=6;a[1][3]=-2;a[1][4]=-5;b[1]=-19;
   a[2][1]=3;a[2][2]=10;a[2][3]=-5;a[2][4]=1;b[2]=1;
   a[3][1]=-4;a[3][2]=1;a[3][3]=18;a[3][4]=2;b[3]=12;
   a[4][1]=1;a[4][2]=2;a[4][3]=2;a[4][4]=-14;b[4]=1;
   sol[1]=53141.0/48309.0;sol[2]=9424.0/48309.0;
   sol[3]=14209.0/16103.0;sol[4]=7781.0/48309.0;
   for(i=1;i<=n;i++)
   {
    for(j=1;j<=n;j++)
    printf("%12.6e  ",a[i][j]);
    printf(" I  %12.6e\n",b[i]);
    x[i]=0;
   }
   printf("Solution exacte :\n");
   for(i=1;i<=n;i++)
   printf("%22.16e\n",sol[i]);
   printf("Itérations :\n");
   sl_gauss_seidel(a,b,x,n,ITERMAX-1,eps,t);
   for(j=1;j<=ITERMAX-1;j++)
   {
    printf("x(%2d)= (",j);
    for(i=1;i<=n;i++)
    {
     x[i]=t[i][j]-sol[i];
     printf("%12.6e ",t[i][j]);
    }
    printf(")    err= %.3e\n",al_norme_vect(x,n));
   }
   printf("Dernier itéré :\n");
   for(i=1;i<=n;i++)
   printf("%22.16e\n",t[i][ITERMAX-1]);
  }
  

  ---

  نتائج البرنامج

  في كل كرة البرنامج يظهر:

  • الكرة ؛x^(k)

  • الارتياب (الفرق بين الكرة x^(k)  والقيمة المضبوطة)

     A                                     b
  -1.60000e+01   6.00000e+00  -2.00000e+00  -5.00000e+00   I  -1.90000e+01
   3.00000e+00   1.00000e+01  -5.00000e+00   1.00000e+00   I   1.00000e+00
  -4.00000e+00   1.00000e+00   1.80000e+01   2.00000e+00   I   1.20000e+01
   1.00000e+00   2.00000e+00   2.00000e+00  -1.40000e+01   I   1.00000e+00
  Solution exacte :
   1.100022770084249e+00
   1.950775217868306e-01
   8.823821648140098e-01
   1.610672959489950e-01
  Itérations :
  x( 1)= ( 1.18750e+00 -2.56250e-01  9.44792e-01  1.11756e-01 )    err= 4.67e-01
  x( 2)= ( 9.38384e-01  2.79705e-01  8.47240e-01  1.56591e-01 )    err= 1.86e-01
  x( 3)= ( 1.13755e+00  1.66696e-01  8.92796e-01  1.61181e-01 )    err= 4.82e-02
  x( 4)= ( 1.08804e+00  2.03867e-01  8.79219e-01  1.61015e-01 )    err= 1.52e-02
  x( 5)= ( 1.10373e+00  1.92389e-01  8.83361e-01  1.61088e-01 )    err= 4.68e-03
  x( 6)= ( 1.09889e+00  1.95906e-01  8.82081e-01  1.61061e-01 )    err= 1.44e-03
  x( 7)= ( 1.10037e+00  1.94823e-01  8.82475e-01  1.61069e-01 )    err= 4.43e-04
  x( 8)= ( 1.09992e+00  1.95156e-01  8.82354e-01  1.61067e-01 )    err= 1.36e-04
  x( 9)= ( 1.10006e+00  1.95053e-01  8.82391e-01  1.61067e-01 )    err= 4.20e-05
  x(10)= ( 1.10001e+00  1.95085e-01  8.82379e-01  1.61067e-01 )    err= 1.29e-05
  x(11)= ( 1.10003e+00  1.95075e-01  8.82383e-01  1.61067e-01 )    err= 3.97e-06
  x(12)= ( 1.10002e+00  1.95078e-01  8.82382e-01  1.61067e-01 )    err= 1.22e-06
  x(13)= ( 1.10002e+00  1.95077e-01  8.82382e-01  1.61067e-01 )    err= 3.76e-07
  x(14)= ( 1.10002e+00  1.95078e-01  8.82382e-01  1.61067e-01 )    err= 1.16e-07
  x(15)= ( 1.10002e+00  1.95078e-01  8.82382e-01  1.61067e-01 )    err= 3.56e-08
  x(16)= ( 1.10002e+00  1.95078e-01  8.82382e-01  1.61067e-01 )    err= 1.10e-08
  x(17)= ( 1.10002e+00  1.95078e-01  8.82382e-01  1.61067e-01 )    err= 3.37e-09
  x(18)= ( 1.10002e+00  1.95078e-01  8.82382e-01  1.61067e-01 )    err= 1.04e-09
  x(19)= ( 1.10002e+00  1.95078e-01  8.82382e-01  1.61067e-01 )    err= 3.20e-10
  x(20)= ( 1.10002e+00  1.95078e-01  8.82382e-01  1.61067e-01 )    err= 9.84e-11
  Dernier itéré :
   1.100022770006489e+00
   1.950775218434505e-01
   8.823821647934380e-01
    1.610672959485904e-01
  

double al_norme_vect(double x[NMAX],int n)
{
 double t;
 int i;
 t=0;
 for(i=1;i<=n;i++) t += x[i]*x[i];
 t=sqrt(t);
 return(t); 
}  

الدالة الرئيسية sl_gauss_seidel

• • معايير الدالة
  a : المصفوفة
  b : العنصر الثاني
  n : درجة المصفوفة
  x1: متجهة البداية
  iter: عدد مرات التكرار
  eps: الدقة المعطاة
  t: جدول مثلثي
  
  
  القيمة الرجعية
  
  ترجع الدالة القيم المكررة لهذه الطريقة في الجدول t.
  
  تساوي الثابتة NMAX البعد القصوي للمصفوفة زائد 1، وتساوي الثابتة ITERMAX القيمة القصوى لعدد مرات التكرار زائد 1.

void sl_gauss_seidel(double a[NMAX][NMAX],double b[NMAX],double x1[NMAX],
 int n,int iter,double eps,double t[NMAX][ITERMAX])
{
 int i,j,k;
 double alfa,d,s;
 for(i=1;i<=n;i++)
 for(j=1;j<=ITERMAX-1;j++)
 t[i][j]=0.0;
 alfa=1.0;
 k=1;
 while(k<=iter && alfa>eps)
 {
 alfa=0.0;
 for(i=1;i<=n;i++)
 {
 d=x1[i];
 s=b[i];
 for(j=1;j<=n;j++)
 if(i!=j)
 s -= a[i][j]*x1[j];
 x1[i]=s/a[i][i];
 d-=x1[i];
 alfa+=d*d;
 }
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=ITERMAX-2;j++)
 t[i][j]=t[i][j+1];
 t[i][ITERMAX-1]=x1[i];
 }
 k++;
 }
}