שבר משולב

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
Nuvola apps edu mathematics blue-p.svg

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

שבר משולב הוא ביטוי מהצורה x = a_0+\frac{1}{a_1+\frac{1}{a_2+\frac{1}{a_3+\frac{1}{\,\cdots+\frac{1}{a_n}}}}} , כאשר המספרים \ a_0,a_1,\dots,a_n הם בדרך כלל מספרים טבעיים, או ביטוי אינסופי בעל מבנה דומה.

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

סימונים והכללות[עריכת קוד מקור | עריכה]

לשם הקיצור, מקובל לסמן את השבר המשולב המופיע במבוא בסימון \ x=[a_0;a_1,\dots,a_n]. שבר כזה, שבו כל המונים שווים ל-1, קרוי לפעמים שבר משולב פשוט, בעוד ששבר משולב מוכלל הוא ביטוי כללי יותר, מן הצורה x = a_0+\frac{b_1}{a_1+\frac{b_2}{a_2+\frac{b_3}{a_3+\,\cdots+\frac{b_n}{a_n}}}} . שברים משולבים כאלה כותבים לפעמים כ- 
x=a_0+
\frac{b_1}{a_1+}\,
\frac{b_2}{a_2+}\,
\frac{b_3}{a_3+}\ldots
.

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

את השבר האינסופי x=a_0+\frac{b_1}{a_1+}\,\frac{b_2}{a_2+}\,\frac{b_3}{a_3+}\ldots אפשר לחקור בעזרת המרכיבים הסופיים שלו, \ x_k=a_0+\frac{b_1}{a_1+}\,\frac{b_2}{a_2+}\,\ldots\,\frac{+b_k}{a_k}\,, שהם מספרים רציונליים.

הבניה של שבר משולב מן הסדרות \ a_n ו- \ b_n היא תהליך אינסופי, שמלכתחילה לא מובן מאליו שהוא מתכנס למספר כלשהו. התכונה הבסיסית ביותר של שברים משולבים היא העובדה שהתהליך מתכנס כל אימת שהסדרות המגדירות אותו חיוביות.

נגדיר סדרות נסיגה על-פי תנאי ההתחלה \ p_{-1}=1, q_{-1}=0; \ p_0=a_0, q_0=1, ונוסחת הנסיגה \!\ q_n=a_nq_{n-1}+b_nq_{n-2} ,\!\ p_n=a_np_{n-1}+b_np_{n-2}.

מתברר שתחת הגדרה זו, המנות \ \frac{p_k}{q_k} מתארות את השלבים הסופיים בפיתוח השבר המשולב, כלומר, \!\ x_k=\frac{p_k}{q_k} לכל k טבעי.

הוכחה לפיתוח בשלבים הסופיים

נוכיח באינדוקציה ש- \!\ x_k=\frac{p_k}{q_k}. כאשר k=1,

\!\ x_1=a_0+\frac{b_1}{a_1}=\frac{a_1a_0+b_1}{a_1}=\frac{a_1p_0+b_1p_{-1}}{a_1q_0+b_1q_{-1}}=\frac{p_1}{q_1}


נניח שהטענה מתקיימת עבור k=n מסוים, ונוכיח שהיא מתקיימת עבור השלב k=n+1:
מההנחה אנו יודעים שמתקיים:

\ x_n=\frac{p_n}{q_n}=\frac{a_np_{n-1}+b_np_{n-2}}{a_nq_{n-1}+b_nq_{n-2}}


על ידי החלפת \!\ a_n ב-\!\ a_n+\frac{b_{n+1}}{a_{n+1}}, נקבל את המנה החלקית \!\ x_{n+1} :

 x_{n+1}=\frac{\left(a_n+\frac{b_{n+1}}{a_{n+1}}\right) p_{n-1}+b_np_{n-2}}{\left(a_n+\frac{b_{n+1}}{a_{n+1}}\right)q_{n-1}+b_nq_{n-2}}

=\frac{a_{n+1}\left(a_np_{n-1}+b_np_{n-2}\right)+b_{n+1}p_{n-1}}
{a_{n+1}\left(a_nq_{n-1}+b_nq_{n-2}\right)+b_{n+1}q_{n-1}}

=\frac{a_{n+1}p_n+b_{n+1}p_{n-1}}{a_{n+1}q_n+b_{n+1}q_{n-1}}=\frac{p_{n+1}}{q_{n+1}}


בכך נשלם שלב האינדוקציה ואיתו ההוכחה כולה.

את נוסחת הנסיגה אפשר לכתוב בעזרת מטריצות, באופן הבא: \ \begin{pmatrix} p_n & q_n \\ p_{n-1} & q_{n-1}\end{pmatrix} 
= \begin{pmatrix} a_n & b_n \\ 1 & 0 \end{pmatrix} \cdot \begin{pmatrix} p_{n-1} & q_{n-1} \\ p_{n-2} & q_{n-2}\end{pmatrix}. מהשוואת הדטרמיננטה בשני האגפים, נובע באינדוקציה ש- \!\ p_kq_{k-1}-p_{k-1}q_k=\left( -1 \right)^{k-1}\prod_{i=1}^k b_i. זוהי זהות חשובה ביותר, שאפשר להסיק ממנה תכונות רבות של הסדרות המעורבות. לדוגמה, בשבר משולב פשוט מתקיים \ b_k=1 לכל k, ואם כך הזהות קובעת שהמספרים \ p_k ו- \ q_k זרים, כך שהשבר \ x_k שהם מציגים הוא שבר מצומצם.

כדי להוכיח את התכנסות התהליך, נחלק את הזהות במכפלה \ q_kq_{k-1}, ונקבל \!\ x_k-x_{k-1} = (-1)^{k-1}\frac{\prod_{i=1}^{k}b_i}{q_kq_{k-1}}, כלומר \!\ x_k = x_0 + \sum_{j=1}^k (-1)^{j-1}\frac{\prod_{i=1}^{j}b_i}{q_jq_{j-1}}. מנוסחת הנסיגה, קל להיווכח כי הסדרה \!\ \frac{b_1\dots b_k}{q_kq_{k-1}} היא סדרה יורדת של מספרים חיוביים, ומשפט לייבניץ מבטיח שהטור המתחלף המגדיר את \ x_k - מתכנס.

למעשה, חישוב בעזרת נוסחת הנסיגה מביא לנוסחה \!\ p_kq_{k-2}-p_{k-2}q_k=( -1)^{k}a_k\prod_{i=1}^{k-1}b_i, שממנה מתקבל היחס \!\ x_k-x_{k-2} = (-1)^{k}\frac{a_k\prod_{i=1}^{k-1}b_i}{q_kq_{k-2}}. מכאן שסדרת הקירובים הזוגיים היא סדרה עולה, וסדרת הקירובים האיזוגיים היא סדרה יורדת. עוד אפשר להוכיח שאברי הסדרה הזוגית תמיד קטנים מאברי הסדרה היורדת.

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

הדיון לעיל מראה שאם המספרים \ a_n טבעיים, אז הביטוי \ x=[a_0;a_1,\dots] הוא תמיד מספר ממשי מוגדר היטב (דהיינו, סדרת המספרים \ x_k מתכנסת). מן האלגוריתם של אוקלידס (או באינדוקציה) נובע שלכל מספר רציונלי יש הצגה כשבר משולב סופי. מאידך, אפשר להוכיח שלכל מספר ממשי שאינו רציונלי קיימת הצגה (יחידה) כשבר משולב אינסופי.

את ההצגה של x כשבר משולב אפשר לחשב על ידי הגדרת סדרת עזר, באופן הבא: \ x_0'=x, ולכל \ n\geq 0, מגדירים \ a_n=[x_n'] (החלק השלם) ו- \ x_{n+1}'=\frac{1}{x_{n}'-a_n}. השבר המשולב \ [a_0;a_1,\dots] שווה במקרה זה ל- x.

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

לדוגמה, השבר המשולב \ x = [1; \overline{1}] = [1;1,1,\dots] מייצג את יחס הזהב \ \frac{1+\sqrt{5}}{2}, משום שלפי ההגדרה \ x=1+\frac{1}{x}. בדומה לזה, \ y=[1; \overline{3,1}] = \frac{3+\sqrt{21}}{6}, כי מ- \ y = 1+\frac{1}{3+\frac{1}{y}} מתקבלת המשוואה \ 3y^2-3y-1=0. הפיתוח של \ \sqrt{D} לשבר משולב מחזורי מאפשר לפתור את משוואת פל \ x^2-Dy^2=1.

ישנם מספרים אירציונליים יוצאי דופן, עבורם הייצוג כשבר משולב ידוע, למרות שאינו מחזורי. למשל, עבור הקבוע \ e ניתן להוכיח כי \ e = [2;1,2,1,1,4,1,1,6,1,\dots]. אם נתיר לחבר אפסים במכנה, נקבל את הייצוג \ e = [1;0,1,1,2,1,1,4,1,1,6,1,\dots] (שכן \ 2 = [1;0,1]) בו החוקיות יותר ניכרת.

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

כידוע, כל מספר אי־רציונלי נתן לקרב על ידי סדרת מספרים רציונליים. למשל, נוכל לקרב את \ \pi באופן דצימלי על ידי הסדרה \ \frac{3}{1},\frac{31}{10},\frac{314}{100},\dots. ניתן להתקרב למספר אי־רציונלי עד למרחק קטן כרצוננו, אולם לשם כך יהא עלינו להגדיל את המכנה בשבר המקרב. לכן מודדים את טיב הקירוב במרחק של השבר הרציונלי מן היעד, יחסית לגודל המכנה.

בניית שבר משולב נותנת טכניקה לקירוב רציונלי של מספרים אי רציונליים. אפשר להציג את \ \pi\ כשבר משולב על ידי \ [3;7,15,\dots]. מתוך תחילת הייצוג נוכל לקבל את הקירוב \ 3+\frac{1}{7 + \frac{1}{15}}=\frac{333}{106} למספר \ \pi. קירוב זה הוא בעל מכנה דומה לקירוב \ \frac{314}{100} אולם מתקים \left| \pi\ - \frac{314}{100} \right|=0.00159, ואילו \left| \pi\ - \frac{333}{106} \right|=0.000083, וכך הקירוב שהתקבל מתוך פיתוח השבר המשולב הוא טוב יותר.

יהא \ \frac{p}{q} שבר המתקבל משלב כלשהו בפיתוח השבר המשולב של מספר אי־רציונלי \ x . שבר זה הוא מיטבי לקירוב, מהבחינות הבאות:

  • אין שבר בעל מכנה קטן יותר המקרב את x טוב יותר. כלומר, עבור, זוג מספרים טבעיים \ a,b , המקיימים \ b\leq\ q נקבל \ |qx-p| \leq\ |bx-a| .
  • כל שבר המקרב היטב את \ x מופיע בשלב כלשהו בפיתוח השבר המשולב שלו. כלומר, אם \ \frac{p}{q} שבר רציונלי מצומצם המקיים \ \left| x-\frac{p}{q} \right|<\frac{1}{2q^2} אז השבר יופיע בשלב כלשהו בפיתוח השבר המשולב של \ x .
  • בהינתן שלושה שברים משלבים רצופים בפיתוח של \ x כשבר משולב, לפחות אחד מהם יקיים \ \left| x-\frac{p}{q} \right|<\frac{1}{\sqrt{5} q^2} . לפי משפט הורוביץ (ראו קירוב דיופנטי), זהו הקירוב המיטבי שניתן להשיג עבור מספר אי־רציונלי כללי.

התנהגות כמעט תמיד[עריכת קוד מקור | עריכה]

כאשר מתאימים מספר ממשי x לפיתוח \ x=[a_0; a_1,a_2,\dots], אפשר לבחון את התנהגות הסדרה \ a_n עבור ערכים שונים של x. למשל, ידוע שכמעט לכל x, הסדרה אינה חסומה; ליתר דיוק, קבוצת הערכים \ 0<x<1 שעבורם הסדרה חסומה היא קבוצה ממידה אפס. המתמטיקאי הרוסי אלכסנדר חינצי'ן (Александр Хинчин) הוכיח בספרו[1] תוצאות רבות מסוג זה, העוסקות בערכים \ a_n ו- \ q_n המתקבלים מהצגת מספר ממשי שנבחר באקראי. להלן כמה מן המשפטים החשובים שהוכיח חינצ'ין.

משפט[2]. תהי \ h_n סדרה כלשהי. אם הטור \ \sum\frac{1}{h_n} מתבדר, אז כמעט תמיד מתקיים אי-השוויון \ a_n\geq h_n עבור אינסוף ערכי n; ואם הטור מתכנס, אז כמעט תמיד מתקיים אי-שוויון זה רק עבור מספר סופי של ערכי n.

(לדוגמה, כמעט לכל x הסדרה \ a_n/n אינה חסומה).

משפט[3]. כמעט לכל x, מתקיים \ \lim_{n\rightarrow\infty}\frac{\log(q_n)}{n} = \frac{\pi^2}{12 \log(2)}. בפרט, הסדרה \ q_n גדלה במהירות אקספוננציאלית (למעשה, קל לראות מן ההגדרה שהסדרה גדלה מהר לפחות כמו סדרת פיבונאצ'י).

חינצ'ין חקר גם את ההתפלגות של המקדמים \ a_n (עבור x בעל התפלגות אחידה בקטע היחידה), והראה[4] שלכל פונקציה f שאינה גדלה מהר מדי (\ f(n)<Cn^{1/2-\epsilon} עבור קבוע מתאים C ו- 0 < \epsilon), הערך הממוצע \ \lim_{n\rightarrow \infty}\frac{1}{n}\sum_{k=1}^{n}f(a_k) של המספרים \ f(a_n) שווה, בהסתברות 1, ל- \ \sum_{k=1}^{\infty}\log_2(1+\frac{1}{k(k+1)})f(k). בפרט, שכיחות ההופעה של קבוע N בסדרה היא \ \log_2(1+\frac{1}{N(N+1)}).

ראו גם[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ A. Ya. Khinchin, Continued Fractions, 1935
  2. ^ משפט 30 בספרו של חינצ'ין
  3. ^ חינצי'ן הוכיח את קיומו של הקבוע; התוצאה המדויקת מופיעה ב- P.Levy, Theorie de l'addition des variables aleatoires, Paris 1937, p. 320
  4. ^ משפט 35 בספרו של חינצ'ין

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

גדי אלכסנדרוביץ', שברים משולבים, ולמה הם מגניבים, באתר "לא מדויק"