חישוב קוונטי – ועכשיו פורמלית

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

מבוא לאפקטים קוונטיים על קצה המזלג

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

חישוב קוונטי – מה זה אומר ומה זה לא אומר?

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

בניות בסרגל ומחוגה – המשחק!

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

מכפלות טנזוריות (של מרחבים וקטוריים)

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

התמרת פורייה המהירה

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

התמרת פורייה הבדידה – מה זה בכלל?

עד עכשיו ראינו שני סוגים של התמרות פורייה: אחת עבור פונקציות מחזוריות מעל הממשיים, כלומר פונקציות שמוגדרות מעל הקטע \(\left[-\pi,\pi\right]\) ואנחנו יכולים "להרחיב" אותן לכל \(\mathbb{R}\) באופן מחזורי; ופונקציות שהוגדרו מראש על כל \(\mathbb{R}\). להתמרה במקרה הראשון קראנו "טורי פורייה" … להמשיך לקרוא

התמרת פורייה – מה זה בכלל?

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

טורי פורייה – מה זה בכלל?




יש עוד נקודה שכדאי לתת עליה את הדעת בדוגמה שלי. אמרנו שטור פורייה הוא טור של סינוסים וקוסינוסים, אז איפה הקוסינוסים? ובכן, בחישוב הפורמלי ראינו שהמקדמים של כולם יצאו 0, אבל האם זה מקרי? כמובן שלא. \(f\) שלנו היא בבירור פונקציה אנטי-סימטרית סביב \(x=0\) כמעט בכל נקודה, בדיוק כמו סינוס עצמה. זה מבטיח שהמקדמים של \(\cos x\) עבורה יצאו 0 ונקבל טור טיילור שהוא טור סינוסים בלבד. באופן דומה, פונקציה סימטרית תהיה בעלת טור קוסינוסים בלבד. בשני המקרים הסימטריה או האנטי-סימטריה לא חייבות להיות מושלמות – גם אם הן נכשלות במספר סופי של נקודות זה לא ישפיע על כלום כי אינטגרל של פונקציה לא משתנה אם משנים את הפונקציה במספר סופי של נקודות. יותר מכך, אם \(f\) היא אנטיסימטרית אז \(f\left(x\right)\sin nx\) היא סימטרית, ואם \(f\) סימטרית כך גם \(f\left(x\right)\cos nx\). זה אומר שאפשר לפשט טיפה את נוסחת האינטגרל ולהתעסק רק עם חצי מהתחום:

אם \(f\) אנטיסימטרית אז \(f\left(x\right)=\sum b_{n}\sin nx\) כאשר \(b_{n}=\frac{2}{\pi}\int_{0}^{\pi}f\left(x\right)\sin nxdx\)

אם \(f\) סימטרית אז \(f\left(x\right)=\sum a_{n}\cos nx\) כאשר \(a_{n}=\frac{2}{\pi}\int_{0}^{\pi}f\left(x\right)\cos nxdx\)

באופן כללי, כל פונקציה ניתן לתאר בתור סכום של פונקציה זוגית ופונקציה אי זוגית: אם \(f\) היא פונקציה כלשהי, אז \(\frac{f\left(x\right)+f\left(-x\right)}{2}\) היא פונקציה זוגית, \(\frac{f\left(x\right)-f\left(-x\right)}{2}\) היא פונקציה אי זוגית, ומתקיים \(f\left(x\right)=\frac{f\left(x\right)+f\left(-x\right)}{2}+\frac{f\left(x\right)-f\left(-x\right)}{2}\) (תרגיל נחמד: להוכיח שזה הייצוג היחיד של \(f\) כסכום של פונקציה זוגית ופונקציה אי זוגית). אז אפשר לחשוב על הסינוסים בטור הפורייה בתור הייצוג של החלק האנטי סימטרית ועל הקוסינוסים בתור הייצוג של החלק הסימטרי.

עכשיו בואו נעבור לדבר קצת על שאלת ההתכנסות הנקודתית. נניח ש-\(f\left(x\right)=\frac{a_{0}}{2}+\sum a_{n}\cos nx+\sum b_{n}\sin nx\), כשהשוויון מייצג, כרגיל, התכנסות בנורמה. מה בעצם הבעיה המרכזית שמונעת מאיתנו להיות בטוחים שיש גם התכנסות נקודתית? פשוט מאוד, העובדה שציינתי כבר קודם: המקדמים נקבעים על ידי חישוב של אינטגרל שכולל את \(f\); אבל אם נשנה את הערך של \(f\) בנקודה אחת, זה לא ישנה את הערך של האינטגרלים. בעצם, לכל טור פורייה \(\frac{a_{0}}{2}+\sum a_{n}\cos nx+\sum b_{n}\sin nx\) אנחנו מסוגלים למצוא מחלקה לא קטנה של פונקציות שמתוארות על ידו. אם תחשבו על זה רגע, תשימו לב שכל הפונקציות הללו יהיו במרחק 0 אחת מהשניה כשאנחנו מודדים מרחקים עם הנורמה שנובעת מהמכפלה הפנימית שלנו, וזה לא הכי תקין מתמטית כי פונקציית מרחק ("מטריקה") אמורה להבטיח ששני איברים הם במרחק 0 אחד מהשני רק אם הם זהים. למטריקה שכושלת בעניין הזה קוראים "פסאודומטריקה" והדרך המקובלת "לתקן" אותה היא להגדיר יחס שקילות על אברי המרחב שלנו – שני איברים הם שקולים אם המרחק ביניהם הוא 0. עכשיו אפשר לעבור מהמרחב שלנו למרחב חדש, שהוא מרחב המנה שמתקבל מיחס השקילות הזה, ובו המטריקה תהיה תקינה. ועכשיו, איזה נציג אנחנו רוצים לבחור לכל מחלקת שקילות?

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

מה על פונקציות שהן "סתם" רציפות, בלי הנחות מיוחדות לגבי הנגזרת שלהן? רציפות היא תכונה מאוד נחמדה מצד אחד, שמונעת מאיתנו "לקלקל" פונקציות בצורה נקודתית כדי להבטיח שטור הפורייה שלהן יטעה באותן נקודות – אבל עדיין, אם אין לנו שליטה על גודל הנגזרת, הפונקציה יכולה להיות די משוגעת. לא אתן דוגמאות נגדיות מפורשות, אבל ניתן לבנות פונקציות רציפות שטור הפורייה שלהן בכלל לא מתכנס נקודתית בשום מקום. אז מה עושים? ובכן, מסתבר שגרסה יותר כללית של התכנסות עדיין עובדת כאן. בואו נסתכל שניה על סדרת הסכומים החלקיים של טור פורייה כלשהו, כלומר נגדיר \(S_{m}\left(x\right)=\frac{a_{0}}{2}+\sum_{n=1}^{m}\left(a_{n}\cos nx+b_{n}\sin nx\right)\). ייתכן, כאמור, שהסדרה \(S_{0}\left(x\right),S_{1}\left(x\right),S_{2}\left(x\right),\dots\) לא מתכנסת בכלל עבור ערכים מסויימים של \(x\), אבל אפשר להסתכל על סדרת הממוצעים שלה:

\(\sigma_{m}\left(x\right)=\frac{S_{0}\left(x\right)+\dots+S_{m}\left(x\right)}{m+1}\)

ניתן להוכיח – ושוב, לא אעשה זאת כרגע – שאם \(f\) היא פונקציה רציפה ואנו סוכמים את טור הפורייה שלה בצורה הזו של סדרת הממוצעים, אז הסכום הזה מתכנס לערך של \(f\) בכל נקודה שבה \(f\) רציפה. שיטת הסכימה הזו – סכימה של הממוצעים – נקראת "סכימת צזארו" והזכרתי אותה לא מזמן בפוסט שעסק בשוויון המוזר \(1+2+3+\dots=-\frac{1}{12}\). שם הסכימה הזו נתנה את הסכום הלא אינטואיטיבי \(1-1+1-1+1-\dots=\frac{1}{2}\), ולא מעט אנשים התקשו לקבל אותו כלגיטימי; אני מקווה שהשימוש הנוכחי של סכימת צזארו, שמראה שאפשר עם קצת תושייה לשחזר את הפונקציה המקורית גם מתוך טור פורייה שאינו מתכנס נקודתית, יסייע קצת להפחתת הסקפטיות בנוגע לשיטת הסכימה הנחמדה הזו.

לסיום הפוסט הזה אני רוצה לחשב את טור הפורייה של עוד פונקציה פשוטה – מכיוון שהחישוב הזה יניב תוצאה יפה ולא טריוויאלית (שכבר הראיתי בבלוג בדיוק באותו האופן אבל מי זוכר). הפונקציה היא \(f\left(x\right)=x\) בתחום \(\left[-\pi,\pi\right]\). זו פונקציה אנטיסימטרית ולכן הפיתוח שלה הוא לטור סינוסים \(f\left(x\right)=\sum b_{n}\sin nx\) כאשר \(b_{n}\) נתון על ידי האינטגרל \(\frac{2}{\pi}\int_{0}^{\pi}x\sin nxdx\). זה לא אינטגרל מסובך, אבל צריך להשתמש בתעלול אינטגרציה בסיסי בשבילו – אינטגרציה בחלקים. נקבל:

\(\int_{0}^{\pi}x\sin nxdx=\left[-\frac{x\cos nx}{n}\right]_{0}^{\pi}-\int_{0}^{\pi}\frac{\cos nx}{n}dx=\left(-1\right)^{n+1}\frac{\pi}{n}\)

(האינטגרל עם הקוסינוס מתאפס, כפי שכבר ראינו לא מעט בפוסט)

מסקנה, אחרי שנכפול מחדש ב-\(\frac{2}{\pi}\): \(b_{n}=\frac{2}{n}\left(-1\right)^{n+1}\). כלומר, ניתן לכתוב את הטור במפורש כך:

\(x=2\sin x-\sin2x+\frac{2}{3}\sin3x-\frac{1}{2}\sin4x+\dots\)

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

\(\|x\|^{2}=\frac{1}{\pi}\int_{-\pi}^{\pi}x^{2}dx=\frac{1}{\pi}\left[\frac{x^{3}}{3}\right]_{-\pi}^{\pi}=\frac{1}{\pi}\frac{\pi^{3}+\pi^{3}}{3}=\frac{2}{3}\pi^{2}\)

עדיין לא נראה מעניין במיוחד, אבל אפשר להשתמש ב"משפט פיתגורס" של מרחבי מכפלה פנימית אינסוף ממדיים – שוויון פרסבל, שאומר שאם \(f=\sum a_{n}e_{n}\) כאשר \(e_{n}\) הם אברי בסיס אורתונורמלי, אז \(\|f\|^{2}=\sum a_{n}^{2}\). במקרה שלנו, \(b_{n}^{2}=\frac{4}{n^{2}}\), אז קיבלנו את השוויון הבא:

\(\frac{2}{3}\pi^{2}=\sum_{n=1}^{\infty}\frac{4}{n^{2}}\)

ועל ידי חלוקה ב-4 של שני האגפים נקבל:

\(\sum_{n=1}^{\infty}\frac{1}{n^{2}}=\frac{\pi^{2}}{6}\)

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

-->

מתמטיקאים אוהבים לפרק דברים לגורמים. כל מספר טבעי קל יותר להבין אם מפרקים אותו למכפלה של ראשוניים. גם עם פונקציות ממשיות זה עובד כך – אחד מהדברים האהובים על מתמטיקאים הוא לקחת פונקציה ממשית \(f\left(x\right)\) ולכתוב אותה בתור טור חזקות: … להמשיך לקרוא

פוסט של בעיית ההתאמה של פוסט

"בעיית ההתאמה של פוסט" – Post Correspondence Problem, ובקיצור PCP – היא בעיה נחמדה במדעי המחשב שנקראת על שם אמיל פוסט, אחד מחלוצי מדעי המחשב (ואינה קשורה לדואר, כמו שחשבתי הרבה זמן) שתיאר אותה ב-1946. מה שנחמד בבעיה הזו הוא … להמשיך לקרוא

על גבולות עליונים ותחתונים של קבוצות וממשיים

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

משפט ארבעת הריבועים של לגראנז'

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

פרוייקט "התלמיד והמחשב", בעיה 25

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

פרוייקט "התלמיד והמחשב", בעיות 21-24

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

המחט של בופון

היום חל "יום פאי", כלומר תאריך היום הוא ה-14/3, שבארצות פחות מתוקנות נכתב כ-3.14, כלומר כמו התחלת הפיתוח העשרוני של הקבוע \(\pi\), פאי (היחס בין היקף מעגל לקוטרו בגאומטריה האוקלידית) – ומכאן, תירוץ לחגוג ולאכול פאי עם פאי. מבחינתי זה … להמשיך לקרוא

אמי נתר (או: על נשים ומתמטיקה וחוקי שימור טובים פחות וטובים יותר)

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

בסיסים אורתונורמליים במרחבי הילברט

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

אז מה זה מרחב הילברט?

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

פותרים את SAT – אלגוריתם CDCL

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

המניפולציה המתמטית של ההמבורגר

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