חוק רופיני

במתמטיקה, חוק רוּפִינִי הוא שיטה לחישוב החלוקה האוקלידית של פולינום בבינום שצורתו x – r . השיטה הומצאה על ידי פַּאוּלוֹ רוּפִינִי, שהשתתף בתחרות שארגנה החברה המדעית האיטלקית. האתגר היה לתכנן שיטה כדי למצוא את השורשים של כל פולינום. התקבלו חמש הגשות. בשנת 1804 זכה רופיני במקום הראשון ושיטתו פורסמה. מאוחר יותר הוא פרסם חידודים של עבודתו ב-1807 ושוב ב-1813. החוק הוא מקרה מיוחד של תבנית:קישור שפה שבו המחלק הוא גורם ליניארי.

אלגוריתם

החוק קובע שיטה לחלוקת הפולינום:

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

בבינום:

$Q(x)=x-r$

כדי לקבל את פולינום המנה:

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

האלגוריתם הוא למעשה החלוקה הארוכה של $P(x)$ ב-$Q(x)$.

כדי לחלק את $P(x)$ ב-$Q(x)$:

1. קח את המקדמים של $P(x)$ ורשום אותם לפי הסדר. לאחר מכן, כתוב r בקצה השמאלי התחתון ממש מעל השורה:

   $\begin{array}{cccccc}& a_n& a_{n-1}& \dots & a_1& a_0\\ r& & & & & \\ & & & & & \end{array}$

2. העבר את המקדם השמאלי ביותר (a_n) לתחתית ממש מתחת לקו.

   $\begin{array}{cccccc}& a_n& a_{n-1}& \dots & a_1& a_0\\ r& & & & & \\ & a_n& & & & \\ & =b_{n-1}& & & & \end{array}$

3. הכפל את המספר הימני ביותר מתחת לשורה ב-r, וכתוב אותו מעל השורה ומיקום אחד מימין.

   $\begin{array}{cccccc}& a_n& a_{n-1}& \dots & a_1& a_0\\ r& & b_{n-1}\cdot r& & & \\ & a_n& & & & \\ & =b_{n-1}& & & & \end{array}$

4. הוסף את שני הערכים שהוצבו זה עתה באותה עמודה.

   $\begin{array}{cccccc}& a_n& a_{n-1}& \dots & a_1& a_0\\ r& & b_{n-1}\cdot r& & & \\ & a_n& b_{n-1}\cdot r+a_{n-1}& & & \\ & =b_{n-1}& =b_{n-2}& & & \end{array}$

5. חזור על שלבים 3 ו-4 עד שלא נשארו מספרים.

   $\begin{array}{cccccc}& a_n& a_{n-1}& \dots & a_1& a_0\\ r& & b_{n-1}\cdot r& \dots & b_1\cdot r& b_0\cdot r\\ & a_n& b_{n-1}\cdot r+a_{n-1}& \dots & b_1\cdot r+a_1& a_0+b_0\cdot r\\ & =b_{n-1}& =b_{n-2}& \dots & =b_0& =s\end{array}$

ערכי b הם המקדמים של פולינום התוצאה ($R(x)$), שמעלתו קטנה באחד מזו של $P(x)$. הערך הסופי שהתקבל, s, הוא השארית. משפט שארית הפולינום קובע שהשארית שווה ל- $P(r)$, ערכו של הפולינום ב-r .

דוגמה

הנה דוגמה לחלוקה פולינומית כמתואר לעיל.

נתון:

$P(x)=2x^3+3x^2-4$

$Q(x)=x+1.$

$P(x)$ יחולק ב-$Q(x)$ באמצעות חוק רופיני. הבעיה העיקרית היא ש-$Q(x)$ אינו בינום בצורת x − r, אלא x + r .

$Q(x)$ חייב להיכתב מחדש בצורה:

$Q(x)=x+1=x-(-1).$

כעת האלגוריתם מיושם:

1. רשום את המקדמים ו-r. שים לב שכיוון ש-$P(x)$ לא הכיל מקדם עבור x, נכתָב 0:

$\begin{array}{cccccc}& 2& 3& 0& & -4\\ \\ -1\\ \\ \end{array}$

2. העבירו את המקדם הראשון למטה:

$\begin{array}{cccccc}& 2& 3& 0& & -4\\ \\ -1\\ & 2\\ \end{array}$

3. הכפל את הערך האחרון שהתקבל ב-r:

$\begin{array}{cccccc}& 2& 3& 0& & -4\\ \\ -1& & -2\\ & 2\\ \end{array}$

4. הוסף את הערכים:

$\begin{array}{cccccc}& 2& 3& 0& & -4\\ \\ -1& & -2\\ & 2& 1\\ \end{array}$

5. חזור על שלבים 3 ו-4 עד שתסיים:

$\begin{array}{cccccc}& 2& 3& 0& & -4\\ \\ -1& & -2& -1& & 1\\ & 2& 1& -1& & -3\\ & [result& coefficients]& & & [remainder]\end{array}$

לכן, אם מספר מקורי = מחלק × מנה + שארית, אז:

$P(x)=Q(x)R(x)+s$, איפה ש...

$R(x)=2x^2+x-1$ ו...

$s=-3;\Rightarrow 2x^3+3x^2-4=(2x^2+x-1)(x+1)-3$

יישום לפירוק פולינום

ניתן להשתמש בחוק רופיני כאשר צריך את המנה של פולינום תבנית:Mvar על ידי בינום של הצורה $.x-r$ (כאשר צריך רק את השארית, משפט השאריות הפולינומי מספק שיטה פשוטה יותר.)

דוגמה טיפוסית, שבה צריך את המנה, היא הפירוק לגורמים של פולינום $p(x)$ שעבורו יודעים שורש תבנית:Mvar :

שארית החלוקה האוקלידית של $p(x)$ לפי תבנית:Mvar הוא תבנית:נוסחה, וכן, אם המנה היא $,q(x)$ החלוקה האוקלידית כתובה כ:

$p(x)=q(x)(x-r).$

זה נותן פירוק (אולי חלקי) של $,p(x)$ שניתן לחשב עם חוק רופיני. לאחר מכן, ניתן לפרק את $p(x)$ עוד יותר על ידי פירוק של $.q(x)$

המשפט היסודי של האלגברה קובע שלכל פולינום בעל מעלה חיובית יש לפחות שורש מרוכב אחד. התהליך שלמעלה מראה שהמשפט היסודי של האלגברה מרמז שכל פולינום תבנית:נוסחה ניתן לפרק לגורמים כ:

$p(x)=a_n(x-r_1)\cdots (x-r_n),$

כאשר $r_1,\dots ,r_n$ הם מספרים מרוכבים.

ראו גם

• השיטה של ליל (Lill's method)
• השיטה של הורנר (Horner's method)

קישורים חיצוניים

• תבנית:MathWorld