חלוקת פולינומים – הבדלי גרסאות
מ הוספת קטגוריה:אלגוריתמים באמצעות HotCat |
|||
שורה 3: | שורה 3: | ||
האלגוריתם מיישם הלכה למעשה את תכונת הפולינומים הבאה. בהינתן <math>P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0</math> (מחולק) ו-<math>D(x)=b_kx^k+b_{k-1}x^{k-1}+...+b_1x+b_0</math> (מחלק) כך ש-<math>k\le n</math> ובניסוח מדויק, <math>\deg(D(x))\le\deg(P(x))</math>, ניתן לבטא את <math>P(x)</math> כ-<math>P(x)=D(x)Q(x)+R(x)</math> עבור <math>Q(x)</math> פולינום שיקרא המנה ועבור <math>R(x)</math> פולינום שיקרא שארית החלוקה, כך שדרגת השארית <math>R(x)</math> קטנה (ממש) מדרגת המחלק <math>D(x)</math>, כלומר <math>\deg(R(x))<\deg(D(x))</math>. |
האלגוריתם מיישם הלכה למעשה את תכונת הפולינומים הבאה. בהינתן <math>P(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0</math> (מחולק) ו-<math>D(x)=b_kx^k+b_{k-1}x^{k-1}+...+b_1x+b_0</math> (מחלק) כך ש-<math>k\le n</math> ובניסוח מדויק, <math>\deg(D(x))\le\deg(P(x))</math>, ניתן לבטא את <math>P(x)</math> כ-<math>P(x)=D(x)Q(x)+R(x)</math> עבור <math>Q(x)</math> פולינום שיקרא המנה ועבור <math>R(x)</math> פולינום שיקרא שארית החלוקה, כך שדרגת השארית <math>R(x)</math> קטנה (ממש) מדרגת המחלק <math>D(x)</math>, כלומר <math>\deg(R(x))<\deg(D(x))</math>. |
||
התוצאה <math>R=0</math> תופיע [[אם ורק אם]] <math>D(x)</math> הוא גורם של <math>P(x)</math>, כלומר, ניתן לרשום את <math>P(x)</math> כמכפלה של הפולינום <math>D(x)</math> בפולינום אחר. בנוסף, על פי [[המשפט הקטן של בזו]], אם <math>a</math> הוא שורש של <math>P(x)</math>, דהיינו <math>P(a)=0</math>, אזי <math>(x-a)</math> הוא גורם של <math>P(x)</math>. לכן, נעשה שימוש נרחב בחלוקת פולינומים הן על מנת לפרק את הפולינום לגורמים והן על מנת לפשט את הליך מציאת השורשים הנוספים שלו, אם אחד מהם כבר ידוע{{הערה|https://math-wiki.com/images/1/12/חילוק_פולינומים_הסבר.PDF}}. |
התוצאה <math>R(x)=0</math> תופיע [[אם ורק אם]] <math>D(x)</math> הוא גורם של <math>P(x)</math>, כלומר, ניתן לרשום את <math>P(x)</math> כמכפלה של הפולינום <math>D(x)</math> בפולינום אחר. בנוסף, על פי [[המשפט הקטן של בזו]], אם <math>a</math> הוא שורש של <math>P(x)</math>, דהיינו <math>P(a)=0</math>, אזי <math>(x-a)</math> הוא גורם של <math>P(x)</math>. לכן, נעשה שימוש נרחב בחלוקת פולינומים הן על מנת לפרק את הפולינום לגורמים והן על מנת לפשט את הליך מציאת השורשים הנוספים שלו, אם אחד מהם כבר ידוע{{הערה|https://math-wiki.com/images/1/12/חילוק_פולינומים_הסבר.PDF}}. |
||
==דוגמה== |
==דוגמה== |
גרסה מ־19:22, 30 במרץ 2021
באלגברה, חלוקת פולינומים או חלוקת פולינומים עם שארית או חלוקה אוקלידית, היא אלגוריתם לחלוקת פולינום בפולינום אחר שדרגתו[1] קטנה מזו של המחולק או שווה לשלו. למעשה, אלגוריתם זה מהווה הכללה לאלגוריתם החילוק הארוך באריתמטיקה. בדומה לחילוק האריתמטי, גם חילוק פולינומים מפרק בעיה מתמטית, העשויה להיות מסובכת, לתתי-בעיות פשוטות יותר, ולכן, הוא פשוט ונוח לשימוש באופן יחסי. זאת ועוד, קיימות גם שיטות המקצרות את תהליך חלוקה זה, כדוגמת חלוקה סינתטית[2].
האלגוריתם מיישם הלכה למעשה את תכונת הפולינומים הבאה. בהינתן (מחולק) ו- (מחלק) כך ש- ובניסוח מדויק, , ניתן לבטא את כ- עבור פולינום שיקרא המנה ועבור פולינום שיקרא שארית החלוקה, כך שדרגת השארית קטנה (ממש) מדרגת המחלק , כלומר .
התוצאה תופיע אם ורק אם הוא גורם של , כלומר, ניתן לרשום את כמכפלה של הפולינום בפולינום אחר. בנוסף, על פי המשפט הקטן של בזו, אם הוא שורש של , דהיינו , אזי הוא גורם של . לכן, נעשה שימוש נרחב בחלוקת פולינומים הן על מנת לפרק את הפולינום לגורמים והן על מנת לפשט את הליך מציאת השורשים הנוספים שלו, אם אחד מהם כבר ידוע[3].
דוגמה
חלוקת פולינומים
נמצא את מנת החלוקה ואת השארית שלה עבור חלוקת הפולינום (המחולק) בפולינום (המחלק).
תחילה, נכתוב מחדש את המחולק באופן הבא:
.
כעת, נבצע את התהליך דלהלן:
נחלק את האיבר הראשון של באיבר הראשון של , דהיינו, את האיבר בעל החזקה המקסימלית של באיבר בעל החזקה המקסימלית של . במקרה זה, מדובר ב-. את התוצאה, נכתוב מעל לקו האופקי:
הפולינום שהתקבל מעל לקו האופקי הוא המנה והפולינום, במקרה זה ממעלה 0[4], שנותר אחרי הפעולה האחרונה, הוא השארית .
שימושים
פירוק פולינומים לגורמים
בהינתן פולינום, לעיתים, שורש אחד או יותר שלו כבר ידועים אך ייתכן כי קיימים לו כאלו נוספים. אם ידוע כי הוא שורש של פולינום - פולינום ממעלה , כלומר מתקיים כי , ניתן לחלק את ב- ומהמשפט הקטן של בזו נובע כי שארית החלוקה היא 0. לכן, נקבל במקרה זה כי עבור , כלומר דרגת המנה היא . בחלק מהמקרים, הפולינום הוא כזה שקל יותר למצוא את שורשיו. מאחר שכל שורש שלו הוא גם שורש של , הרי שבכך יועל תהליך מציאת השורשים של הפולינום המקורי.
באופן דומה, אם ידועים יותר משורש אחד של הפולינום, לדוגמה, ידוע כי שורשים שלו, ניתן לחלק את הפולינום ב- ולקבל . כעת, ניתן לחלק את ב- ולקבל כי כך שדרגתו של קטנה מהדרגה של . לכן, . כעת, ניתן להמשיך את התהליך, עד שבסופו של דבר יתקבל כי כך שדרגת קטנה מ-.
מציאת ישר משיק לנקודה על גרף של פונקציה פולינומית
ניתן להשתמש בחלוקת פולינומים גם למציאת משוואת הישר המשיק לנקודה הנמצאת על גרף של פונצקייה פולינומית. בהינתן פונקציה ונקודה , משוואת המשיק לגרף בנקודה תהיה שארית החלוקה של ב-.
דוגמה
נמצא את משוואת הישר המשיק לפונקציה בנקודה .
- נחלק את הפולינום ב-:
לכן, משוואת המשיק המבוקשת היא .
בדיקת יתירות מחזורית
בבדיקת יתירות מחזורית משתמשים בשארית החלוקה של פולינומים עבור ניטור שגיאות בהעברת מסרים.
ראו גם
קישורים חיצוניים
- פולינומים, שורשים ופונקציות רציונליות - 8 - חלוקת פולינומים - שיעור בקורס ההכנה במתמטיקה של הטכניון בנושא חלוקת פולינומים המועבר על ידי ד"ר אביב צנזור, סרטון באתר יוטיוב (אורך: 20:33)
הערות שוליים
- ^ דרגת פולינום מוגדרת כחזקה המקסימלית של איבר עם מקדם שאיננו 0. למשל, דרגת הפולינום היא 3.
- ^ איך לנחש ולבדוק שורשים אמיתיים - 3 - בדיקות שורשים על ידי חלוקת פולינומים מחלקה סינתטית - Dummies 2021, באתר No dummy
- ^ https://math-wiki.com/images/1/12/חילוק_פולינומים_הסבר.PDF
- ^ ניתן להתייחס לכל מספר קבוע שאיננו אפס כאל פולינום ממעלה 0.