خوارزميات حل المعادلات الرياضية

حل المعادلات هي من المسائل الشائعة في الرياضيات، وهناك بحث مستمر عن طرق جديدة وسريعة لحل المعادلات عبر الحاسوب، وسنستعرض في هذه المقالة بعض خوارزميات حل المعادلات الخطية وغير الخطية.

المعادلات الخطية Linear Equations

هناك نوعان من الطرق لحل المعادلات الخطية:

الطرق المباشرة: يسعى هذا النوع من الطرق إلى تحويل المعادلة الأصلية إلى معادلة مكافئة أيسر حلًّا، أي أنّنا نسعى في هذا النوع إلى إيجاد الحل مباشرة من معادلة.
الطرق التكرارية Iterative Method: تبدأ هذه الطرق بتخمين قيمة أولية للحل، ثم تُجري عمليات تكرارية تقرِّب من الحل، وتستمر إلى حين الاقتراب من الحل بمقدار محدّد سلفًا.

تعدّ الطرق التكرارية أقل فعالية على العموم من نظيراتها المباشرة لأنّها تجري الكثير من العمليات الإضافية، ولدينا بعض الأمثلة على الطرق التكرارية مثل طريقة جاكوبي التكرارية Jacobi's Iteration Method، وطريقة جاوس - سيدل Gauss-Seidal.

إليك تطبيق لطريقة جاكوبي بلغة C:

// تطبيق لطريقة جاكوبي
void JacobisMethod(int n, double x[n], double b[n], double a[n][n]){
   double Nx[n]; // شكل مُعدَّل من المتغيرات
   int rootFound=0; // راية
   int i, j;
   while(!rootFound){
       for(i=0; i<n; i++){      
           Nx[i]=b[i];
           for(j=0; j<n; j++){
               if(i!=j) Nx[i] = Nx[i]-a[i][j]*x[j];
           }
           Nx[i] = Nx[i] / a[i][i];
       }
       rootFound=1;                    // التحقق من قيمة الراية
       for(i=0; i<n; i++){
           if(!( (Nx[i]-x[i])/x[i] > -0.000001 && (Nx[i]-x[i])/x[i] < 0.000001 )){
               rootFound=0;
               break;
           }
       }
       for(i=0; i<n; i++){             // تقييم
           x[i]=Nx[i];
       }
   }
   return ;
}

وإليك تطبيق لطريقة جاوس-سيدل بلغة C أيضًا:

// تطبيق لطريقة جاوس سيدل
void GaussSeidalMethod(int n, double x[n], double b[n], double a[n][n]){
   double Nx[n]; // شكل معدّل من المتغيرات
   int rootFound=0; // راية
   int i, j;
   for(i=0; i<n; i++){                  //تهيئة
       Nx[i]=x[i];
   }
   while(!rootFound){
       for(i=0; i<n; i++){      
           Nx[i]=b[i];
           for(j=0; j<n; j++){
               if(i!=j) Nx[i] = Nx[i]-a[i][j]*Nx[j];
           }
           Nx[i] = Nx[i] / a[i][i];
       }
       rootFound=1;                    // التحقق من قيمة الراية
       for(i=0; i<n; i++){
           if(!( (Nx[i]-x[i])/x[i] > -0.000001 && (Nx[i]-x[i])/x[i] < 0.000001 )){
               rootFound=0;
               break;
           }
       }
       for(i=0; i<n; i++){             // تقييم
           x[i]=Nx[i];
       }
   }
   return ;
}
// طباعة المصفوفة
void print(int n, double x[n]){
   int i;
   for(i=0; i<n; i++){
       printf("%lf, ", x[i]);
   }
   printf("\n\n");
   return ;
}
int main(){
   // تهيئة المعادلة
   int n=3;    // عدد المتغيرات
   double x[n];    // المتغيرات
   double b[n],    // الثوابت
       a[n][n];    // المعاملات
   //تعيين القيم
   a[0][0]=8;   a[0][1]=2;   a[0][2]=-2; b[0]=8;    //8x₁+2x₂-2x₃+8=0    
   a[1][0]=1;   a[1][1]=-8;  a[1][2]=3; b[1]=-4;    //x₁-8x₂+3x₃-4=0    
   a[2][0]=2;   a[2][1]=1;   a[2][2]=9; b[2]=12;    //2x₁+x₂+9x₃+12=0

   int i;
   for(i=0; i<n; i++){                         //  تهيئة
       x[i]=0;
   }
   JacobisMethod(n, x, b, a);
   print(n, x);
   for(i=0; i<n; i++){                         //تهيئة
       x[i]=0;
   }
   GaussSeidalMethod(n, x, b, a);
   print(n, x);
   return 0;
}

المعادلات غير الخطية Non-Linear Equations

تُصنَّف المعادلات من النوع ‎‎f(x)= 0 إلى صنفين: إما جبرية أو غير جبرية -أو متسامية transcendental- ويمكن حل المعادلات غير الخطية باستخدام أحد أسلوبين:

الأسلوب المباشر: يعطي هذا الأسلوب القيمة الدقيقة لكل جذور f (حلول المعادلة) مباشرة في عدد محدود من الخطوات.
الأسلوب غير المباشر أو التكراري: هذا النوع أصلح من النوع الأول لحل المعادلات عبر الحاسوب، ويُبنى على مبدأ التقريب المتتالي، ولدينا طريقتين لحل المعادلة في الأسلوب التكراري:
- طريقة الحصار Bracketing Method: نأخذ نقطتين أوليّتين نعلم أنّ الجذر يقع بينهما، ثم نستمر في تضييق طول المجال الذي يحاصر الجذر إلى أن نصل إلى طول تقريبي معيّن. تُعد خوارزمية التنصيف من أشهر الخوارزميات التي تستخدم طريقة الحصار.
- طريقة النهاية المفتوحة Open End Method: نأخذ قيمة أولية أو قيمتين، ولا يُشترط أن تحاصر هاتان القيمتان جذر المعادلة، ثم نكرّر إجراء عمليات حسابية على هاتين القيمتين. وعادة ما يحدث هنا أحد أمرين، إمّا أن تتباعد القيمتان مع تكرار العمليات، أو تتقاربان -أي تؤُولان إلى نقطة واحدة، فإن كانتا متقاربتين فإنّ نقطة التقارب ستكون هي الحل. هذه الطريقة أسرع عمومًا من طريقة الحصار، ويُعد أسلوب نيوتن-رافسون Newton-Raphson، وأسلوب التقريب المتتالي Successive Approximation Method، وأسلوب القاطع Secant Method من الأمثلة على هذه الطريقة.

هذا تطبيق بلغة C للحلول السابقة كلها على معادلات وضعناها في بداية الشيفرة:

// دوال مساعدة
#define f(x) ( ((x)*(x)*(x)) - (x) - 2 )
#define f2(x) ( (3*(x)*(x)) - 1 )
#define g(x) ( cbrt( (x) + 2 ) )
/**
* نأخذ قيمتية أوليتين ونقصّر المسافة من كلا الجانبين
**/
double BisectionMethod(){
   double root=0;
   double a=1, b=2;
   double c=0;
   int loopCounter=0;
   if(f(a)*f(b) < 0){
       while(1){
           loopCounter++;
           c=(a+b)/2;
           if(f(c)<0.00001 && f(c)>-0.00001){
               root=c;
               break;
           }
           if((f(a))*(f(c)) < 0){
               b=c;
           }else{
               a=c;
           }
       }
   }
   printf("It took %d loops.\n", loopCounter);
   return root;
}
/**
* نأخذ قيمتية أوليتين ونقصّر المسافة من جانب واحد
**/
double FalsePosition(){
   double root=0;
   double a=1, b=2;
   double c=0;
   int loopCounter=0;
   if(f(a)*f(b) < 0){
       while(1){
           loopCounter++;
           c=(a*f(b) - b*f(a)) / (f(b) - f(a));
           /*/printf("%lf\t %lf \n", c, f(c));/**////test
           if(f(c)<0.00001 && f(c)>-0.00001){
               root=c;
               break;
           }
           if((f(a))*(f(c)) < 0){
               b=c;
           }else{
               a=c;
           }
       }
   }
   printf("It took %d loops.\n", loopCounter);
   return root;
}
/**
* نستخدم قيمة أولية واحدة، ثمّ نتدرّج نحو القيمة الصحيحة
**/
double NewtonRaphson(){
   double root=0;
   double x1=1;
   double x2=0;
   int loopCounter=0;
   while(1){
       loopCounter++;
       x2 = x1 - (f(x1)/f2(x1));
       /*/printf("%lf \t %lf \n", x2, f(x2));/**////test
       if(f(x2)<0.00001 && f(x2)>-0.00001){
           root=x2;
           break;
       }
       x1=x2;
   }
   printf("It took %d loops.\n", loopCounter);
   return root;
}
/**
* نستخدم قيمة أولية واحدة، ثمّ نتدرّج نحو القيمة الصحيحة
**/
double FixedPoint(){
   double root=0;
   double x=1;
   int loopCounter=0;
   while(1){
       loopCounter++;
       if( (x-g(x)) <0.00001 && (x-g(x)) >-0.00001){
           root = x;
           break;
       }
       /*/printf("%lf \t %lf \n", g(x), x-(g(x)));/**////test
       x=g(x);
   }
   printf("It took %d loops.\n", loopCounter);
   return root;
}
/**
*استخدام قيمتين أوليتين، بحيث تقترب كلاهما من الحل الصحيح
**/
double Secant(){
   double root=0;
   double x0=1;
   double x1=2;
   double x2=0;
   int loopCounter=0;
   while(1){
       loopCounter++;
       /*/printf("%lf \t %lf \t %lf \n", x0, x1, f(x1));/**////test
       if(f(x1)<0.00001 && f(x1)>-0.00001){
           root=x1;
           break;
       }
       x2 = ((x0*f(x1))-(x1*f(x0))) / (f(x1)-f(x0));
       x0=x1;
       x1=x2;
   }
   printf("It took %d loops.\n", loopCounter);
   return root;
}
int main(){
   double root;
   root = BisectionMethod();
   printf("Using Bisection Method the root is: %lf \n\n", root);

   root = FalsePosition();
   printf("Using False Position Method the root is: %lf \n\n", root);

   root = NewtonRaphson();
   printf("Using Newton-Raphson Method the root is: %lf \n\n", root);

   root = FixedPoint();
   printf("Using Fixed Point Method the root is: %lf \n\n", root);

   root = Secant();
   printf("Using Secant Method the root is: %lf \n\n", root);
   return 0;
}