נוסחת נסיגה

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

הגדרה רקורסיבית של סדרה

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

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

מעבר מנוסחת נסיגה להצגה מפורשת

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

הצבה חוזרת

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

דוגמה: נביט בסדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_0=a,x_n=q\cdot x_{n-1}} . זוהי נוסחה של סדרה הנדסית, שבה המנה של כל שני איברים עוקבים היא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, q} . כעת ניקח את הנוסחה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, x_n} ונציב בה את עצמה שוב ושוב עד אשר נגיע לאיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, x_0} :

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n=q\cdot x_{n-1}=q\cdot q\cdot x_{n-2}=\dots=q^n\cdot x_0=q^n\cdot a} .

ניחוש הפתרון

לעיתים, ובמיוחד במקרים בהם לא ניתנים תנאי התחלה, אין דרך שיטתית לפתור נוסחת נסיגה, אולם ניתן להעריך את צורתו של הפתרון שיתקבל - למשל, האם יהיה מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, x_n=A+Bn+C^n} . כשפותרים בדרך זו, יש להשתמש בתנאי ההתחלה הידועים של נוסחת הנסיגה כדי לחשב את המקדמים של הנוסחה המפורשת, ואז להוכיח (למשל באמצעות אינדוקציה מתמטית) את נכונות הנוסחה המנוחשת.

משוואה אופיינית

זוהי דרך שיטתית לפתור נוסחאות מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, x_n=Ax_{n-1}+Bx_{n-2}} (סדרת לוקאס) (הערה: נוסחת נסיגה זו, בה יש התייחסות לשני איברים קודמים בסדרה, נקראת "נוסחת נסיגה כפולה"). עבור נוסחה שכזו, יש לפתור את המשוואה הריבועית $\!\,r^{2}-Ar-B=0$ ולקבל את השורשים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, \lambda_1,\lambda_2} .

אם השורשים שונים, האיבר הכללי של נוסחת הנסיגה הוא מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, x_n=C\lambda^n_1+D\lambda^n_2} . אם הם זהים, האיבר הכללי הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, x_n=C\lambda^n+nD\lambda^n} . את המקדמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, C,D} יש למצוא באמצעות תנאי ההתחלה.

בתור דוגמה נפתור את סדרת פיבונאצ'י, שהיא כזכור מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, x_n=x_{n-1}+x_{n-2}} , כלומר אנו מחפשים את שורשי המשוואה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, r^2-r-1=0} . הפתרונות למשוואה זו הם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, \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}$.

כעת נמצא את המקדמים. ראשית נציב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, n=0} ונקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\,x_0=C+D} . כעת נציב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, n=1} ונקבל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, x_1=C\left(\frac{1+\sqrt{5}}{2}\right)+D\left(\frac{1-\sqrt{5}}{2}\right)} .

מהמשוואה הראשונה נקבל: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\,C+D=0} (כי האיבר הראשון הוא 0) ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\,C=-D} . האיבר השני הוא 1, ולכן לאחר שנציב את הנתונים במשוואה השנייה נקבל: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, C\left(\frac{1+\sqrt{5}}{2}\right)-C\left(\frac{1-\sqrt{5}}{2}\right)=1} .

ממשוואה זו נקבל $\!\,C={\frac {1}{\sqrt {5}}}$. על כן, הנוסחה הכללית של פיבונאצ'י היא: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \!\, \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]} .

פונקציות יוצרות

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

סדרה ליניארית לא הומוגנית

אם נתון יחס הנסיגה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{n} = a_1 y_{n-1} + a_2 y_{n-2} + ... + a_k y_{n-k} + b} עם תנאי התחלה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (y_1,...,y_k) \in \mathbb{R}^k} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b \ne 0} אומרים שזו סדרת נסיגה ליניארית לא-הומוגנית. לפני שניגשים לפתור אותה בשיטות שתוארו קודם יש לבצע לה הומוגניזציה. אם לסדרה יש מצב יציב או גבול של סדרה אז הדבר אפשרי. נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{\infty} = \lim_{n \to \infty} y_n = \frac{b}{1 - a_1 - ... - a_k}} זהו הגבול של הסדרה וקיים רק אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1 + ... + a_k \ne 1} (נוסחה זו מתקבלת על ידי החלפת כל ה-y-ים בגבול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{\infty}} ). כעת נגדיר סדרה חדשה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_n = y_n - y_{\infty}} . סדרה זו מקיימת את היחס הבא:

$$z_{n}=a_{1}z_{n-1}+a_{2}z_{n-2}+...+a_{k}z_{n-k}$$

ומכאן אפשר להמשיך כמו מקודם. מוצאים את k השורשים של הפולינום האופייני הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda^k - a_1 \lambda^{n-1} - ... - a_{k-1} \lambda^1 - a_k = 0} . אם יש k שורשים שונים, הפתרון הכללי יהיה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle z_n = c_1 \lambda_1^n + ... + c_k \lambda_k^n} כאשר את המקדמים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_1,...,c_k} מוצאים באמצעות תנאי ההתחלה. אם יש שורש מריבוי m אז במקום m מופעים שלו רושמים את הביטוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tilde{c}_1 \lambda_m^n + \tilde{c}_2 n \lambda_m^n + ... + \tilde{c}_{m} n^{m-1}\lambda_m^n} . אם יש שורש מרוכב, אז הוא בא עם שורש צמוד. נרשום את שני השורשים כך הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda_{\pm} = \alpha \pm i \beta = r \cdot e^{i \theta} = r \cdot (\cos\theta + i\sin\theta)} ואז נשתמש בנוסחת אוילר (אנליזה מרוכבת) ונוסחת דה-מואבר כדי לרשום אותם בצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_{+} \lambda_{+}^n + c_{-} \lambda_{-}^n = k_1 r^n \cos(n \theta) + k_2 r^n \sin(n \theta)} כאשר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k_1, k_2} הם קבועים ממשיים אותם מוצאים מתנאי ההתחלה (ביחד עם שאר מקדמי הצירוף הליניארי).

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

• נוסחת נסיגה, באתר MathWorld (באנגלית)
• משוואות פרש, דף שער בספרייה הלאומית

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

נוסחת נסיגה35676577Q740970