חלוקת פולינומים

באלגברה, חלוקת פולינומים או חלוקת פולינומים עם שארית או חלוקה אוקלידית, היא אלגוריתם לחלוקת פולינום בפולינום אחר שדרגתו[1] קטנה מזו של המחולק או שווה לשלו. למעשה, אלגוריתם זה מהווה הכללה לאלגוריתם החילוק הארוך באריתמטיקה. בדומה לחילוק האריתמטי, גם חילוק פולינומים מפרק בעיה מתמטית, העשויה להיות מסובכת, לתתי-בעיות פשוטות יותר, ולכן, הוא פשוט ונוח לשימוש באופן יחסי. זאת ועוד, קיימות גם שיטות המקצרות את תהליך חלוקה זה, כדוגמת חלוקה סינתטית[2].

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

התוצאה תופיע אם ורק אם הוא גורם של , כלומר, ניתן לרשום את כמכפלה של הפולינום בפולינום אחר. בנוסף, על פי המשפט הקטן של בזו, אם הוא שורש של , דהיינו , אזי הוא גורם של . לכן, נעשה שימוש נרחב בחלוקת פולינומים הן על מנת לפרק את הפולינום לגורמים והן על מנת לפשט את הליך מציאת השורשים הנוספים שלו, אם אחד מהם כבר ידוע[3].

דוגמה לאופן פעולת האלגוריתםעריכה

נמצא את מנת החלוקה ואת השארית שלה עבור חלוקת הפולינום   (המחולק) בפולינום   (המחלק).

תחילה, נכתוב מחדש את המחולק באופן הבא:

. 

כעת, נבצע את התהליך דלהלן:

נחלק את האיבר הראשון של   באיבר הראשון של  , דהיינו, את האיבר בעל החזקה המקסימלית של   באיבר בעל החזקה המקסימלית של  . במקרה זה, מדובר ב- . את התוצאה, נכתוב מעל לקו האופקי:

 
  • נכפול את כל איברי המחלק בתוצאה שקיבלנו זה עתה, ונקבל  . נכתוב את התוצאה תחת האיברים הראשונים של המחולק:
     
  • נחסר את התוצאה שרשמנו מהאיברים שמעליה ומיד לאחר מכן, נעתיק מטה את האיבר הראשון מימין לאיברי המחלק שביצענו עליהן כעת פעולה.
     
  • נבצע כעת שוב את אותה סדרת פעולות עבור הפולינום החדש שהתקבל מההפרש ומהוספת האיבר הנוסף.
     
  • כעת, לא ניתן להעתיק מטה אף איבר. נסיים את התהליך.
     
  • הפולינום שהתקבל מעל לקו האופקי הוא המנה   והפולינום, במקרה זה ממעלה 0[4], שנותר אחרי הפעולה האחרונה, הוא השארית  . לכן, קיבלנו כי  .

    שימושיםעריכה

    פירוק פולינומים לגורמיםעריכה

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

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

    מציאת ישר משיק לנקודה על גרף של פונקציה פולינומיתעריכה

    ניתן להשתמש בחלוקת פולינומים גם למציאת משוואת הישר המשיק לנקודה הנמצאת על גרף של פונצקייה פולינומית. בהינתן פונקציה   ונקודה  , משוואת המשיק לגרף בנקודה   תהיה שארית החלוקה של   ב- .

    דוגמהעריכה

    נמצא את משוואת הישר המשיק לפונקציה   בנקודה  .

    נחלק את הפולינום ב- :
     

    לכן, משוואת המשיק המבוקשת היא  .

    בדיקת יתירות מחזוריתעריכה

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

    ראו גםעריכה

    קישורים חיצונייםעריכה

    הערות שולייםעריכה

    1. ^ דרגת פולינום מוגדרת כחזקה המקסימלית של איבר עם מקדם שאיננו 0. למשל, דרגת הפולינום   היא 3.
    2. ^ איך לנחש ולבדוק שורשים אמיתיים - 3 - בדיקות שורשים על ידי חלוקת פולינומים מחלקה סינתטית - Dummies 2021, No dummy
    3. ^ https://math-wiki.com/images/1/12/חילוק_פולינומים_הסבר.PDF
    4. ^ ניתן להתייחס לכל מספר קבוע שאיננו אפס כאל פולינום ממעלה 0.