נוסחת נסיגה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

במתמטיקה, נוסחת נסיגה היא נוסחה שמגדירה סדרת איברים באופן רקורסיבי. למשל, סדרת פיבונאצ'י מוגדרת על ידי נוסחת הנסיגה \ F_{n+1} = F_n+F_{n-1}, יחד עם תנאי ההתחלה \ F_0 = F_1 = 1.

הגדרה רקורסיבית של סדרה[עריכת קוד מקור | עריכה]

בהגדרה רקורסיבית יש שני חלקים:

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

מעבר מנוסחת נסיגה להצגה מפורשת[עריכת קוד מקור | עריכה]

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

הצבה חוזרת[עריכת קוד מקור | עריכה]

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

דוגמה: נביט בסדרה x_0=a,x_n=q\cdot x_{n-1}. זוהי נוסחה של סדרה הנדסית, שבה המנה של כל שני איברים עוקבים היא \!\, q. כעת ניקח את הנוסחה של \!\, x_n ונציב בה את עצמה שוב ושוב עד אשר נגיע לאיבר \!\, x_0:

x_n=q\cdot x_{n-1}=q\cdot q\cdot x_{n-2}=\dots=q^n\cdot x_0=q^n\cdot a.

ניחוש הפתרון[עריכת קוד מקור | עריכה]

לעתים, ובמיוחד במקרים בהם לא ניתנים תנאי התחלה, אין דרך שיטתית לפתור נוסחת נסיגה, אולם ניתן להעריך את צורתו של הפתרון שיתקבל - למשל, האם יהיה מהצורה \!\, x_n=A+Bn+C^n. כשפותרים בדרך זו, יש להשתמש בתנאי ההתחלה הידועים של נוסחת הנסיגה כדי לחשב את המקדמים של הנוסחה המפורשת, ואז להוכיח (למשל באמצעות אינדוקציה מתמטית) את נכונות הנוסחה המנוחשת.

משוואה אופיינית[עריכת קוד מקור | עריכה]

זוהי דרך שיטתית לפתור נוסחאות מהצורה \!\, x_n=Ax_{n-1}+Bx_{n-2} (סדרת לוקאס) (הערה: נוסחת נסיגה זו, בה יש התייחסות לשני איברים קודמים בסדרה, נקראת "נוסחת נסיגה כפולה"). עבור נוסחה שכזו, יש לפתור את המשוואה הריבועית \!\, r^2-Ar-B=0 ולקבל את השורשים \!\, \lambda_1,\lambda_2.

אם השורשים שונים, האיבר הכללי של נוסחת הנסיגה הוא מהצורה \!\, x_n=C\lambda^n_1+D\lambda^n_2. אם הם זהים, האיבר הכללי הוא \!\, x_n=C\lambda^n+nD\lambda^n. את המקדמים \!\, C,D יש למצוא באמצעות תנאי ההתחלה.

בתור דוגמה נפתור את סדרת פיבונאצ'י, שהיא כזכור מהצורה \!\, x_n=x_{n-1}+x_{n-2}, כלומר אנו מחפשים את שורשי המשוואה \!\, r^2-r-1=0. הפתרונות למשוואה זו הם \!\, \lambda_{1,2}=\frac{1\pm\sqrt{5}}{2}. לכן האיבר הכללי הוא מהצורה \!\, x_n=C\left(\frac{1+\sqrt{5}}{2}\right)^n+D\left(\frac{1-\sqrt{5}}{2}\right)^n.

כעת נמצא את המקדמים. ראשית נציב \!\, n=0 ונקבל \!\,x_0=C+D. כעת נציב \!\, n=1 ונקבל \!\, x_1=C\left(\frac{1+\sqrt{5}}{2}\right)+D\left(\frac{1-\sqrt{5}}{2}\right).

מהמשוואה הראשונה נקבל: \!\,C+D=0 (כי האיבר הראשון הוא 0) ולכן \!\,C=-D. האיבר השני הוא 1, ולכן לאחר שנציב את הנתונים במשוואה השנייה נקבל: \!\, C\left(\frac{1+\sqrt{5}}{2}\right)-C\left(\frac{1-\sqrt{5}}{2}\right)=1.

ממשוואה זו נקבל \!\, C=\frac{1}{\sqrt{5}}. על כן, הנוסחה הכללית של פיבונאצ'י היא: \!\, \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right].

פונקציות יוצרות[עריכת קוד מקור | עריכה]

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