المبدأ

تحديد جذور لحدودية ذات معاملات حقيقية.

P(x) = a₀xⁿ + a₁x^n-1 + ... + a_n

الطريقة تنبني على حساب جميع المعاملات التربيعية لـ.

إذا كانت P حدودية درجتها 2n.

 إذا كانت P  حدودية درجتها 1+ 2n.

ثم نحسب جذور معاملاتها (وبهذا نحصل على الجذور الحقيقية و العقدية ل P)

الخوارزم

تهيئ :(p₀, q₀) اعتباطي، مثال (0, 0), (0, 1), (1, 0) أو (1, 1).

الكرة:

النتائج : ايكن

p نهاية المتتاليةp⁽ⁱ⁾  و q نهاية المتتالية   q⁽ⁱ⁾

b_k نهاية المتتالية b_k⁽ⁱ⁾ و c_k نهاية المتتالية  c_k⁽ⁱ⁾

P(x) = (x² + px + q) (b₀x^n-1 + b₁x^n-2 + ... + b_n-1)

نعيد العملية بتبديل a_i  بـ b_i, باعتبار القيم p و q المحصل عليها، كقيم الانطلاق في المرحلة الجديدة، وهكذا حتى يتم تحديد جميع المعاملات اتربيعية لـ P، ومنه نحدد الجذور. 

مثال

حساب  جذور الحدودية :

P(x) = 3x⁵ - 29x⁴ + 57x³ + 241x² - 700x + 348

الحل المضبوط

P(x) = (x² + (7/3)x - 2) (x² - 10x + 29) (3x - 6)

جذور  x² + (7/3)x - 2   هي :  2/3   و  -3

جذور x² - 10x + 29              هي :  5 + 2i  و  5 - 2i

جذر  3x - 6                            هو :  2

البرمجة

#include <math.h>
#include <conio.h>
#define NMAX 6

void eq_trinome(double p,double q,double *x1,double *y1,double *x2,double *y2);

void eq_bairstow(int n,double a[NMAX],double reel[NMAX],
                 double imaginaire[NMAX],double p0,double q0,double eps)

double imaginaire[NMAX],double p0,double q0,double eps);

main()
{
 double a[NMAX],reel[NMAX],imaginaire[NMAX];
 double p0,q0,eps;
 int i,n;
 n=5;
 clrscr();
 printf("Méthode de Bairstow\n");
 a[5]=348;a[4]=-700;a[3]=241;a[2]=57;a[1]=-29;a[0]=3;
 printf("  Polynôme:\n");
 for(i=1;i<=n;i++)
 printf(" a%d = %11.5e\n",i,a[i]);
 eps=1e-15;
 p0=1;q0=-1;
 eq_bairstow(n,a,reel,imaginaire,p0,q0,eps);
 printf("  Racines:\n");
 for(i=1;i<=n;i++)
 printf("(%23.16e ) + (%23.16e ) i\n",reel[i],imaginaire[i]);
}

ملاحظة: ليظهر البرنامج في كل مرحلة  ، نحدق التعليقات/*  و*/ من الدالة eq_bairstow .

ويظهر بعد ذلك جذور معاملات التربع (بالترتيب الذي حصلت عليه)، ثم الجذور آخر خارج.

الحدودية:
 a1 = -2.9000e+01
 a2 =  5.7000e+01
 a3 =  2.4100e+02
 a4 = -7.0000e+02
 a5 =  3.4800e+02

معامل التربع 1 :                                                                      p = 2.3333e+00   q = -2.0000e+00
الباقي:       b0 = 3.0000e+00  b1 = -3.6000e+01  b2 = 1.4700e+02  b3 = -1.7400e+02
معامل التربع 2 :                                                                        p = -1.0000e+01  q = 2.9000e+01
الباقي:                                          b0 = 3.0000e+00  b1 = -6.0000e+00
 لجذور:                                                                           
(  6.666666666666665e-01 ) + (  0.000000000000000e+00 ) i
( -3.000000000000000e+00 ) + (  0.000000000000000e+00 ) i
(  5.000000000000000e+00 ) + (  1.999999999999998e+00 ) i
(  5.000000000000000e+00 ) + ( -1.999999999999998e+00 ) i
(  2.000000000000000e+00 ) + (  0.000000000000000e+00 ) i

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

معايير هذه الدالة هي كالتالي:

n: درجة الحدودية.
a : جدول ذي الدرجة NMAX، تحتوي على معاملات الحدودية.
reel : جدول ذي الدرجة NMAX.
imaginaire:  جدول ذي الدرجة NMAX.
p0 و q0: قيمتي الإنطلاق.
eps: الدقة المطلوبة.

تستدعي الدالة التالية:

void eq_trinome(double p,double q,double *x1,double *y1,double *x2,double *y2)
{
 double delta,pr,pi;
 delta=p*p-4*q;
 pr=-p/2;
 pi=sqrt(fabs(delta))/2;
 if(delta>=0)
 {
 *x1=pr+pi;
 *x2=pr-pi;
 *y1=0;
 *y2=0;
 }
 else
 {
 *x1=pr;
 *x2=pr;
 *y1=pi;
 *y2=-pi;
 }
}

 يجب على هذه الدالة أن تعرف في البرنامج الرئيسي

ترجع الدالة الرئيسية الجدولين reel و imaginaire، على التوالي، الجزء الحقيقي والجزء التخيلي لجذور الحدودية، محسوبة من طرف خوارزم بيرستو.

الثابتة الصحيحة NMAX تساوي الدرجة القصوى للحدودية (+1).

void eq_bairstow(int n,double a[NMAX],double reel[NMAX],double imaginaire[NMAX],
                 double p0,double q0,double eps)
{
 double b[NMAX],c[NMAX];
 int i,j,k;
 double p,q,d,dp,dq;
 k=1;
 p=p0;q=q0;
 b[0]=a[0];c[0]=a[0];
 do
 {
 do
 {
 b[1]=a[1]-p*b[0];
 c[1]=b[1]-p*c[0];
 for(i=2;i<=n;i++)
 b[i]=a[i]-p*b[i-1]-q*b[i-2];
 for(j=2;j<=n;j++)
 c[j]=b[j]-p*c[j-1]-q*c[j-2];
 d=c[n-2]*c[n-2]+(b[n-1]-c[n-1])*c[n-3];
 dp=(b[n-1]*c[n-2]-b[n]*c[n-3])/d;
 dq=(b[n]*c[n-2]+b[n-1]*(b[n-1]-c[n-1]))/d;
 p += dp;
 q += dq;
 }
 while ((fabs(dp)+fabs(dq))/(fabs(p)+fabs(q))>eps);
 /*
 printf("%de facteur quadratique: p = %.5e q = %.5e\n",(k+1)/2,p,q);
 printf("Reste: ");
 for (i=0;i<=n-2;i++)
 printf(" b%d = %.5e ",i,b[i]);
 printf("\n");
 */
 eq_trinome(p,q,&reel[k],&imaginaire[k],&reel[k+1],&imaginaire[k+1]);
 k += 2;
 n -= 2;
 for(i=1;i<=n;i++)
 a[i]=b[i];
 }
 while(n>2);
 if(n==2)
 {
 p=b[1]/b[0];
 q=b[2]/b[0];
 eq_trinome(p,q,&reel[k],&imaginaire[k],&reel[k+1],&imaginaire[k+1]);
 }
 else
 {
 reel[k]=-b[1]/b[0];
 imaginaire[k]=0;
 }
}