هذه المقالة بحاجة لمراجعة خبير مختص في مجالها. يرجى من المختصين في مجالها مراجعتها وتطويرها. (فبراير_2010)

قاعدة روفيني

بيانات عامّة

الصنف	خوارزمية إيجاد الجذور
سمي نسبة لـ	باولو روفيني

تعديل - تعديل مصدري - تعديل ويكي بيانات

في الرياضيات، قاعدة رافيني هي عملية يدوية تسمح بحساب القسمة الأقليدية لمتعددة حدود على ذات حدين على الصورة x − r.^[1] وصفت هذه الطريقة من قبل باولو روفيني عام 1804. قاعدة روفيني هي حالة خاصة من القسمة المصطنعة عندما يكون القاسم معاملا خطيا.

مخطط هورنر هو أحد تطبيقات قاعدة روفيني. طالع أيضا القسمة المطولة لمتعددات الحدود.

تخلق القاعدة طريقة لقسمة كثيرة الحدود

${\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}}$

على ذات الحدين

${\displaystyle Q(x)=x-r\,\!}$

للحصول على حاصل القسمة، كثيرة حدود

${\displaystyle R(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\cdots +b_{1}x+b_{0}}$

وباقي s.

في الحقيقة الخوارزم هو قسمة مطولة لـ P(x) علىQ(x).

لقسمة P(x) على Q(x):

1. نأخذ معاملات P(x) ونكتبها على الترتيب. ثم نكتب r في أسفل الحافة اليسرى, تماما فوق السطور:

    |        an        an-1       ...        a1         a0
    |                                    
  r |                                    
----|----------
    |                                    
    |                                    

2. نمرر المعامل الواقع تماما إلى اليسار (a_n) إلى أسفل, تخت السطر:

    |        an        an-1       ...        a1         a0
    |                                    
  r |                                    
----|----------
    |        an
    |
    |      = bn-1                                
    |

3. نضرب الرقم على اليمين تماما تحت السطر بـ r ونكتبه فوق الخط وحركة واحدة لليمين:

    |        an        an-1       ...        a1         a0
    |
  r |                  bn-1r
----|----------
    |        an
    |
    |      = bn-1                                
    |

4. نضيف القيمتين اللتين وضعتهما في نفس العمود

    |        an        an-1       ...        a1         a0
    |
  r |                  bn-1r
----|----------
    |        an     an-1+(bn-1r)
    |
    |      = bn-1     = bn-2                                
    |

5. نعيد الخطوات 3 و 4 حتى ننتهي من الأعداد

    |        an        an-1       ...        a1         a0
    |
  r |                  bn-1r      ...        b1r        b0r
----|----------
    |        an     an-1+(bn-1r)  ...       a1+b1r       a0+b0r
    |
    |      = bn-1     = bn-2      ...       = b0        = s
    |

قيم b هي معاملات نتيجة كثيرة الحدود (R(x))، الدرجة التي أصبح أقل من سابقتها P(x) بمقدار واحد.القيمة الأخيرة التي نحصل عليها, s, هي الباقي. وكما نرى من نظرية باقي كثيرة الحدود, يكون هذا الباقي مساويا لـ P(r), قيمة كثيرة الحدود عند r.

هناك مثال عددي في الأسفل.

هناك تطبيقات عديدة لقاعدة روفيني، أغلبها يعتمد على القسمة المبسطة (كما هو مبين بالأسفل) أو الامتدادات العامة المعطاة أيضا فيما بعد بالأسفل..

مثال تم العمل عليه في الوصف السابق. لتكن:

${\displaystyle P(x)=2x^{3}+3x^{2}-4\,\!}$

${\displaystyle Q(x)=x+1.\,\!}$

نحن بصدد قسمة P(x) by Q(x) باستعمال قاعدة روفيني. المشكلة الرئيسية هي أن Q(x) ليست كثيرة حدود على الصورة x − r, بل x + r. ينبغي إعادة كتابة Q(x) بالطريقة التالية:

${\displaystyle Q(x)=x+1=x-(-1).\,\!}$

بتطبيق الخوارزم الآن:

1. اكتب الفوارق r. لاحظ أنه, لأن P(x) لم تحو على معامل لـ x, فقد كتبنا 0:

    |     2     3     0     -4
    |                                    
 -1 |                                    
----|--------
    |                                    
    |

2. مرر المعامل الأول في الأسفل:

    |     2     3     0     -4
    |                                    
 -1 |                                    
----|--------
    |     2                              
    |

3. اضرب الأخير الذي حصلنا عليه بـr:

    |     2     3     0     -4
    |                                    
 -1 |          -2                         
----|--------
    |     2                              
    |

4. أضف القيم:

    |     2     3     0     -4
    |
 -1 |          -2
----|--------
    |     2     1
    |

5. كرر الطرق 3 و4 حتى الانتهاء:

    |     2     3     0     -4
    |
 -1 |          -2    -1      1
----|--------
    |     2     1    -1     -3
    |{معاملات النتيجة}{الباقي}

إذن, إذا كان العدد الأصلي = القاسم×حاصل القسمة+الباقي, فإن

${\displaystyle P(x)=Q(x)R(x)+s\,\!}$, حيث

${\displaystyle R(x)=2x^{2}+x-1\,\!}$ و${\displaystyle s=-3.\,\!}$

تخبرنا نظرية الجذر النسبي بأنه لكثيرة الحدود f(x) = a_nxⁿ + a_n−1xⁿ⁻¹ + ... + a₁x + a₀ التي كل معاملاتها (a_n إلى a₀) أعداد صحيحة، الجذور النسبية الحقيقية تكون دائما على الصورة p/q, حيث p هو قاسم صحيح a₀ وqهو قاسم صحيح لـ a_n. بالتالي إذا كانت كثيرة الحدود هي

${\displaystyle P(x)=x^{3}+2x^{2}-x-2=0\,\!,}$

فإن جميع الجذورالنسبية الممكنة تمثل القواسم الصحيحة لـ a₀ (−2):

${\displaystyle {\mbox{Possible roots:}}\left\{+1,-1,+2,-2\right\}.}$

(هذا مثال بسيط لأنه أحادي (i.e. a_n = 1); بالنسبة لكثيرات الحدود الغير أحادية فإن الجذور الممكنة ستحوي بعض الكسور، ولكن عدد محدود منها فقط لأن، a_n وa₀ لها عدد محدود من القواسم الصحيحة.) بأي حال, لكثيرات الحدود الأحادية، فإن كل جذر نسبي هو عدد صحيح، وعليه فإن كل عدد صحيح ليس سوى قاسم للحد الثابت. يمكن إثبات أن هذا التعبير يظل صحيحا لكثيرات الحدود الغير أحادية. بعبارة أخرى ولإيجاد الجذور الصحيحة لأي كثيرة حدود ذات معاملات صحيحة، فإنه يكفي فقط أن تفحص قواسم الحد الثابت.

إذن، بوضع r مساوية لكل جذر من هذه الجذور الممكنة على الدور، فسوف نفحص كثيرة الحدود بـ(x − r). إذا كانت نتيجة حاصل القسمة بدون باقي، فقد أوجدنا الجذر.

بإمكاننا اختيار أحد الطرق الثلاية التالية: وسوف تعطينا جميعها نفس النتيجة، باستثناء أن الطريقة الثانية والثالثة (عند تطبيق قاعدة روفيني لإيجاد تحليل) فقط يمكننا اكتشاف تكرار جذر معطى. تذكر أنه لايمكن لأي من هذه الطرق اكتشاف الجذور الغير نسبية أو المركبة.

سنحاول تقسيم P(x) على ذات الحدين (x − كل جذر ممكن). إذا كان المتبقي 0، فإن العدد المختار يكون جذرا (والعكس صحيح):

    |    +1    +2    -1     -2                      |    +1    +2    -1    -2
    |                                               |
 +1 |          +1    +3     +2                   -1 |          -1    -1    +2
----|--------               ----|-------
    |    +1    +3    +2      0                      |    +1    +1    -2     0

    |    +1    +2    -1     -2                      |    +1    +2    -1    -2
    |                                               |
 +2 |          +2    +8    +14                   -2 |          -2     0    +2
----|--------               ----|-------
    |    +1    +4    +7    +12                      |    +1     0    -1     0

${\displaystyle x_{1}=+1\,\!}$

${\displaystyle x_{2}=-1\,\!}$

${\displaystyle x_{3}=-2\,\!}$

نبدأ تماما كالطريقة الأولى حتى نجد جذرا ممكنا. بعد ذلك، بدلا من إعادة العملية مع باقي الجذور الممكنة، نستمر بفحص الجذور الممكنة عكس قاعدة رافيني عن الجذر المشروع الذي أوجدناه حتى يصبح لدينا معاملا متبقيا (تذكر أن الجذور يمكن أن تتكرر: إن وقعت فحاول مع كل جذر مرتين):

    |    +1    +2    -1    -2                      |    +1    +2    -1    -2
    |                                              |
 -1 |          -1    -1    +2                   -1 |          -1    -1    +2
----|-------               ----|-------
    |    +1    +1    -2   | 0                      |    +1    +1    -2   | 0
    |                                              |
 +2 |          +2    +6                         +1 |          +1    +2
------                      ------
    |    +1    +3   |+4                            |    +1    +2   | 0
                                                   |
                                                -2 |          -2
                                               ----
                                                   |    +1   | 0

${\displaystyle x_{1}=-1\,\!}$

${\displaystyle x_{2}=+1\,\!}$

${\displaystyle x_{3}=-2\,\!}$

• تحقق من مجموعة الجذور الصحيحة أو النسبية لكثيرة الحدود وفقا لنظرية الجذر النسبي.
• لكل جذر ممكن r، بدلا عن إجراء القسمة P(x)/(x -r)، نطبق نظرية باقي كثيرة الحدود, والتي تنص على أن باقي هذه القمسة يكون P(r)،أي كثيرة الحدود اللازمة لتقييم x = r.

لذا، لكل r في مجموعتنا، تكون r جذرا لكثيرة الحدود إذا وإذا كان فقط P(r) = 0

هذا يوضح أن البحث عن الجذور الصحيحة والنسبية لكثيرة الحدود لاتحتاج لقسمة ولا لتطبيق قاعدة روفيني. مع هذا، عند إيجاد جذر مشروع، ليكن r₁: يمكن تطبيق قاعدة روفيني للتحقق من
Q(x) = P(x)/(x-r₁).
هذا يسمح لنا بتحليل كثيرة الحدود جزئيا بالصورة
P(x) = (x -r₁)·Q(X)

أي جذر (نسبي) إضافي لكثيرة الحدود هو أيضا جذر لـ Q(x) وبالطبع، ما زال بالإمكان إيجاده بين الجذور الممكنة التي تم التحقق من سلفا والتي لم تفحص بعد (أي قيمة تم التحقق من أنها لن تكون جذرا لـ P(x) ليست جذرا لـ Q(x) أيضا; وبتعبير أدق, P(r)≠0 → Q(r)≠0).

لذا، يمكن الاستمرار بتقييم Q(r) بدلا عن P(r), و(طالما أمكننا إيجاد جذر آخر r₂) بقسمة Q(r) على(x-r₂).

حتى ولو كنا نبحث عن الجذور فقط، فهذا يسمح لنا بتقييم كثيرات الحدود ذات الدرجات الأدنى تعاقبيا، طالما استمر التحليل.

إذا كما هي الحال غالبا، كنا نحلل كثيرة الحدود من الدرجة n، فإنه:

• إذا وجدنا p=n جذور نسبية فإننا ننتهي بتحليل كامل (كما في الأسفل) إلى p=n عوامل خطية;
• إذا وجدنا p<n حلول نسبية فإننا ننتهي بتحليل جزئي (كما بالأسفل) إلى p عوامل خطية وأخرى غير خطية من الدرجة n-pوالتي بدورها يمكن أن يكون لها جذور غير نسبية أو مركبة.

تذكر أن تفحص القيود للإجراء الكامل.

أمثلة:

P(x) = x³ +2x² -x -2

الجذور الممكنة = {1, -1, 2, -2}

• P(1) = 0 → x₁ = 1
• P(-1) = 0 → x₂ = -1
• P(2) = 12 → 2 ليس جذرا لكثيرة الحدود

وباقي (x³ +2x² -x -2)/(x-2) هو 12

• P(-2) = 0 → x₃ = -2

P(x) = x³ +2x² -x -2

الجذور الممكنة = {1, -1, 2, -2}

• P(1) = 0 → x₁ = 1

إذن وبتطبيق قاعدة روفيني:

(x³ +2x² -x -2) / (x -1) = (x² +3x +2) →

→ x³ +2x² -x -2 = (x-1)(x² +3x +2)

هنا, r₁=-1 وQ(x) = x² +3x +2

• Q(-1) = 0 → x₂ = -1

مرة أخرى، بتطبيق قاعدة روفيني:

(x² +3x +2) / (x +1) = (x +2) →

→ x³ +2x² -x -2 = (x-1)(x² +3x +2) = (x-1)(x+1)(x+2)

Having used the "p/q" result above (or, to be fair, any other means) to find all the real rational roots of a particular polynomial, it is but a trivial step further to partially تحليل إلى عوامل that polynomial using those roots. As is well-known, each linear factor (x − r) which divides a given polynomial corresponds with a root r, and vice versa.

So if

${\displaystyle P(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}\,\!}$ is our polynomial; and

${\displaystyle R=\left\{{\mbox{roots of }}P(x)\in \mathbb {Q} \right\}\,\!}$ are the roots we have found, then consider the product

${\displaystyle R(x)=a_{n}{\prod (x-r)}{\mbox{ for all }}r\in R.\,\!}$

By the المبرهنة الأساسية في الجبر, R(x) should be equal to P(x), if all the roots of P(x) are rational. But since we have been using a method which finds only rational roots, it is very likely that R(x) is not equal to P(x); it is very likely that P(x) has some irrational or complex roots not in R. So consider

${\displaystyle S(x)={\frac {P(x)}{R(x)}}\,\!}$, which can be calculated using قسمة متعددات الحدود.

If S(x) = 1, then we know R(x) = P(x) and we are done. Otherwise, S(x) will itself be a polynomial; this is another factor of P(x) which has no real rational roots. So write out the right-hand-side of the following equation in full:

${\displaystyle P(x)=R(x)\cdot S(x).\,\!}$

We can call this a complete factorization of P(x) over Q (the rationals) if S(x) = 1. Otherwise, we only have a partial factorization of P(x) over Q, which may or may not be further factorable over the rationals; but which will certainly be further factorable over the reals or at worst the complex plane. (Note: by a "complete factorization" of P(x) over Q, we mean a factorization as a product of polynomials with rational coefficients, such that each factor is irreducible over Q, where "irreducible over Q" means that the factor cannot be written as the product of two non-constant polynomials with rational coefficients and smaller degree.)

Let

${\displaystyle P(x)=x^{3}+2x^{2}-x-2.\,\!}$

Using the methods described above, the rational roots of P(x) are:

${\displaystyle R=\left\{+1,-1,-2\right\}.\,\!}$

Then, the product of (x − each root) is

${\displaystyle R(x)=1(x-1)(x+1)(x+2).\,\!}$

And P(x)/R(x):

${\displaystyle S(x)=1.\,\!}$

Hence the factored polynomial is P(x) = R(x) · 1 = R(x):

${\displaystyle P(x)=(x-1)(x+1)(x+2).\,\!}$

Let

${\displaystyle P(x)=2x^{4}-3x^{3}+x^{2}-2x-8.\,\!}$

Using the methods described above, the rational roots of P(x) are:

${\displaystyle R=\left\{-1,+2\right\}.\,\!}$

Then, the product of (x − each root) is

${\displaystyle R(x)=(x+1)(x-2).\,\!}$

And P(x)/R(x)

${\displaystyle S(x)=2x^{2}-x+4.\,\!}$

As ${\displaystyle S(x){\neq }1}$, the factored polynomial is P(x) = R(x) · S(x):

${\displaystyle P(x)=(x+1)(x-2)(2x^{2}-x+4).\,\!}$

To completely factor a given polynomial over C, the complex numbers, we must know all of its roots (and that could include irrational and/or complex numbers). For example, consider the polynomial above:

${\displaystyle P(x)=2x^{4}-3x^{3}+x^{2}-2x-8.\,\!}$

Extracting its rational roots and factoring it, we end with:

${\displaystyle P(x)=(x+1)(x-2)(2x^{2}-x+4).\,\!}$

But that is not completely factored over C. If we need to factor our polynomial to a product of linear factors, we must deal with that quadratic factor

${\displaystyle {2x^{2}-x+4}=0.\,\!}$

The easiest way is to use quadratic formula, which gives us

${\displaystyle x={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}={\frac {1\pm {\sqrt {(-1)^{2}-4\cdot 2\cdot 4}}}{2\cdot 2}}={\frac {1\pm {\sqrt {-31}}}{4}}\,\!}$

and the solutions

${\displaystyle x_{1}={\frac {1+{\sqrt {-31}}}{4}}\,\!}$

${\displaystyle x_{2}={\frac {1-{\sqrt {-31}}}{4}}.\,\!}$

So the completely-factored polynomial over C will be:

${\displaystyle P(x)=2(x+1)(x-2)(x-{\frac {1+i{\sqrt {31}}}{4}})(x-{\frac {1-i{\sqrt {31}}}{4}}).\,\!}$

However, it should be noted that we cannot in every case expect things to be so easy; the quadratic formula's analogue for fourth-order polynomials is very messy and no such analogue exists for 5th-or-higher order polynomials. See نظرية غالوا for a theoretical explanation of why this is so, and see تحليل عددي for ways to approximate roots of polynomials numerically.

It is entirely possible that, when looking for a given polynomial's roots, we might obtain a messy higher-order polynomial for S(x) which is further factorable over the rationals even before considering irrational or complex factorings. Consider the polynomial x⁵ − 3x⁴ + 3x³ − 9x² + 2x − 6. Using Ruffini's method we will find only one root (x = 3); factoring it out gives us P(x) = (x⁴ + 3x² + 2)(x − 3).

As explained above, if our assignment was to "factor into irreducibles over C" we know that would have to find some way to dissect the quartic and look for its irrational and/or complex roots. But if we were asked to "factor into irreducibles over Q", we might think we are done; but it is important to realize that this might not necessarily be the case.

For in this instance the quartic is actually factorable as the product of two quadratics (x² + 1)(x² + 2). These, at last, are irreducible over the rationals (and, indeed, the reals as well in this example); so now we are done; P(x) = (x² + 1)(x² + 2)(x − 3). In this instance it is in fact easy to factor our quartic by treating it as a معادلة رباعية; but finding such factorings of a higher degree polynomial can be very difficult.

اخترعت هذه الطريقة من طرف باولو روفيني عندما شارك في منافسة نظمتها الجمعية العلمية الإيطالية (ذات الأربعين). تمثل السؤال فيمن يستطيع أن يجد حلحلة لمعادلة حدودية ما. فاز روفيني في هذه المنافسة ولقد كان ذلك في عام 1804. في عامي 1807 و 1813، نشر روفينيي تعديلات لطريقته هذه.

طريقة هورنر نشرت في عام 1819 ثم عدلت في عام 1845.

• طريقة هورنر

• Synthetic Division, an article by Elizabeth Stapel on Purple Math

في كومنز صور وملفات عن Ruffini's rule.