ראשי > כללי > גדי כבר היה שם, אבל מזווית מעט שונה – על פתרון משוואת הפרשים

גדי כבר היה שם, אבל מזווית מעט שונה – על פתרון משוואת הפרשים

נפתח הפעם בשאלה: מהו ערכו של האיבר ה-152 בסדרת פיבונצ'י?

***

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

0, 1, 1, 2, 3, 5, 8, 13…

כדי לבצע בסדרה 'טיפול שורש' נצמיד לכל איבר בה מספר סידורי המצביע על מקומו בטור. נסמן את המספר באות n, כפי שניתן לראות בטבלה הבאה:

1

אם האות a מסמלת איבר כלשהו בטור אז נוכל לרשום למשל :

2

וכך הלאה.

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

3

כלומר, כל איבר בטור הוא סכום של שני האיברים שבאו לפניו.

וכעת חזרה שאלה: מהו ערכו של האיבר ה-152? כיצד תתמודדו עם שאלה זאת? האם יש צורך לחשב את כל המספרים בכל המקומות עד למקום הרצוי?

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

4

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

מהיכן נולדה הנוסחה? האם היא קסם חד פעמי? האם מאחוריה עומד משהו כללי יותר?

***

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

כדי לנסות ולהבין כיצד נולדה הנוסחה נחזור לקשר שמגדיר את כל הסדרה:

5

בואו ונניח שמישהו גילה לנו שהפתרון של המשוואה הוא מהצורה של שבר כלשהו בחזקת n:

6

נציב את הצורה הכללית הזאת במשוואה ונקבל:

7

כעת נחלק ב-rn את המשוואה ונקבל משוואה ריבועית פשוטה:

8

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

9

כאשר A ו-B הם קבועים שאותם נמצא על ידי הצבת תנאי ההתחלה של הטור כלומר נדרוש A ו-B כך שיתקיים:

10

ונקבל את הפתרון הכללי לסדרת פיבונצ'י שצוטט בחלק הקודם.

שימו לב שיכולנו לבחור תנאי התחלה שונים ולקבל פתרון שונה, אך לא באופן מהותי. השינוי היה רק בקבועים A ו-B.

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

***

הפתרון שקיבלנו אינו מקרי. המשוואה המקורית מכונה בעגה 'משוואת הפרשים' וצורת הפתרון שהוצגה היא צורה כללית שעובדת עבור כל משוואה מהסוג הזה (תחת מגבלות כאלה ואחרות).

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

למה זה טוב?

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

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

משוואות הפרשים (וגם משוואות דיפרנציאליות) יכולות לשמש אותנו גם ביצירת מודלים של ריבוי אוכלוסיות, למשל בגידול חיידקים וכדומה.

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

ניתן גם לקרא תיאור מתמטי מפורט יותר ופורמלי הרבה יותר בבלוג 'לא מדויק'. ד"ש לגדי.

מודעות פרסומת
  1. אסף
    01/08/2015 בשעה 12:03 am

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

    • 01/08/2015 בשעה 12:09 am

      אחלה. תודה על התיקון!
      בכל זאת עברו איזה 200 שנה מאז סיימתי את (מעט) חובותי האקדמיים בתכנות ואלגוריתמיקה וזה כנראה כל מה שנשאר 🙂

  2. מישהו 24
    01/08/2015 בשעה 7:00 pm

    אני די בטוח שהתכוונת לאיטרטיבי ולא לדינאמי…

    • נעם
      01/08/2015 בשעה 10:22 pm

      הוא התכוון לדינאמי. העיקר במשפט עליו הוא כתב את זה הוא "ע"י שמירת זכרון".

  3. 01/08/2015 בשעה 7:12 pm

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

  1. No trackbacks yet.

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

%d בלוגרים אהבו את זה: