מתמטיקה דיסקרטית ח (2023 — מרחב למידה אישי

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

מבוא ליחסי חזרה

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

יחס חזרה (Recurrence Relation): משוואה המגדירה סדרה $a_n$ באופן רקורסיבי, כאשר כל איבר $a_n$ (עבור $n \ge k$) מוגדר כפונקציה של איברים קודמים $a_{n-1}, a_{n-2}, \dots, a_{n-k}$.

תנאי התחלה (Initial Conditions): ערכים ספציפיים של האיברים הראשונים בסדרה ($a_0, a_1, \dots, a_{k-1}$), ההכרחיים לקביעת פתרון יחיד ליחס חזרה.

סיווג יחסי חזרה

לינאריים מול לא-לינאריים: יחס חזרה הוא לינארי אם כל האיברים $a_i$ מופיעים בחזקה 1 ואינם מוכפלים זה בזה.
הומוגניים מול לא-הומוגניים: יחס חזרה הוא הומוגני אם אין בו איבר חופשי שאינו תלוי באיברי הסדרה. אם קיים איבר כזה, $F(n)$, היחס הוא לא-הומוגני.
עם מקדמים קבועים מול משתנים: המקדמים של איברי הסדרה (למשל, $c_1$ ב-$a_n = c_1 a_{n-1} + \dots$) קבועים או תלויים ב-$n$. בקורס זה נתמקד בעיקר במקדמים קבועים.

פתרון יחסי חזרה לינאריים עם מקדמים קבועים

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

1. פתרון יחס חזרה הומוגני ($a_n = c_1 a_{n-1} + \dots + c_k a_{n-k}$)

הפתרון מתבסס על המשוואה האופיינית:

$r^k - c_1 r^{k-1} - \dots - c_k = 0$

שורשים ממשיים שונים: אם למשוואה יש שורשים $r_1, r_2, \dots, r_k$ שונים, הפתרון הכללי הוא $a_n = A_1 r_1^n + A_2 r_2^n + \dots + A_k r_k^n$.
שורשים ממשיים חוזרים: אם שורש $r$ מופיע $m$ פעמים, התרומה שלו לפתרון הכללי היא $(A_1 + A_2 n + \dots + A_m n^{m-1}) r^n$.
שורשים מרוכבים: אם $r = \alpha \pm i\beta = \rho e^{\pm i\theta}$ הם זוג שורשים מרוכבים צמודים, התרומה שלהם היא $\rho^n (A_1 \cos(n\theta) + A_2 \sin(n\theta))$.

2. פתרון יחס חזרה לא-הומוגני ($a_n = c_1 a_{n-1} + \dots + c_k a_{n-k} + F(n)$)

הפתרון הכללי הוא סכום הפתרון ההומוגני ($a_n^{(h)}$) והפתרון הפרטי ($a_n^{(p)}$): $a_n = a_n^{(h)} + a_n^{(p)}$.

פתרון הומוגני ($a_n^{(h)}$)

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

פתרון פרטי ($a_n^{(p)}$)

נמצא לרוב באמצעות "שיטת הניחוש המושכל" (Method of Undetermined Coefficients), בה מנחשים פתרון פרטי בצורה דומה ל-$F(n)$.

שיטת הניחוש המושכל

מנחשים את צורת $a_n^{(p)}$ בהתאם לצורת $F(n)$: אם $F(n)$ פולינום, ננחש פולינום; אם אקספוננט, ננחש אקספוננט; אם טריגונומטרי, ננחש טריגונומטרי. יש לזכור להתאים את הניחוש במקרה של חפיפה עם שורשי המשוואה האופיינית.

3. שימוש בתנאי התחלה

לאחר מציאת הפתרון הכללי (הומוגני + פרטי), נשתמש בתנאי ההתחלה הנתונים כדי למצוא את הקבועים $A_1, A_2, \dots$ בפתרון. יש להציב את ערכי $n$ המתאימים (לרוב $0, 1, \dots, k-1$) וליצור מערכת משוואות לינאריות.

דגשים חשובים לבחינה ונושאים מתקדמים

חפיפה בין הפתרון הפרטי לשורשי המשוואה האופיינית: זהו מלכוד נפוץ בבחינות הטכניון. כאשר צורת הניחוש הראשונית לפתרון הפרטי ($a_n^{(p)}$) חופפת לשורש של המשוואה האופיינית (או שילוב שלהם), יש לכפול את הניחוש בפולינום $n^m$, כאשר $m$ הוא ריבוי השורש. לדוגמה, אם $F(n)=c \cdot r^n$ ו-$r$ הוא שורש של המשוואה האופיינית בריבוי $m$, הניחוש יהיה $A \cdot n^m \cdot r^n$. אי-טיפול נכון במקרה זה מוביל לפתרון שגוי לחלוטין.

נושאים נוספים

משפט המאסטר (Master Theorem): כלי חיוני לניתוח סיבוכיות זמן ריצה של אלגוריתמים רקורסיביים מסוג "הפרד ומשול". יש לזהות את הצורה $T(n) = aT(n/b) + f(n)$ וליישם את המקרים השונים של המשפט.
פונקציות יוצרות (Generating Functions): שיטה אלטרנטיבית לפתרון יחסי חזרה, במיוחד במקרים מורכבים יותר או כאשר היחס מתאר בעיות ספירה. בבחינות לעיתים קרובות מופיעות שאלות הדורשות שימוש בפונקציות יוצרות.
שינוי משתנים: לעיתים יחס חזרה אינו לינארי או עם מקדמים משתנים, אך ניתן להפוך אותו לצורה מוכרת באמצעות שינוי משתנים מתאים (לדוגמה, $b_n = \log a_n$).

שאלות לדיון

כיצד תבחינו בין יחס חזרה הדורש שימוש במשפט המאסטר לבין יחס חזרה הדורש פתרון מלא באמצעות המשוואה האופיינית?
מהם היתרונות והחסרונות של שיטת הפונקציות היוצרות לעומת שיטת המשוואה האופיינית לפתרון יחסי חזרה?
תארו מצב שבו תנאי ההתחלה ניתנים עבור אינדקסים שאינם $0, 1, \dots, k-1$ (לדוגמה, $a_1, a_2$ עבור יחס מסדר 2). כיצד תטפלו בכך?
כיצד ניתן למדל בעיה מעשית (למשל, גידול אוכלוסייה, חישוב ריבית דריבית) באמצעות יחס חזרה, ומהם השיקולים בבחירת סוג היחס?

נקודות לתשובת מודל

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

מצאתם טעות או שחסר משהו?