אנליזה נומרית

אַנַלִיזָה נוּמֶרִית היא ענף של המתמטיקה השימושית, אשר עוסק בשיטות יעילות לפתרון מקורב של בעיות מספריות של המתמטיקה הרציפה, כולל הערכת השגיאה הכרוכה בחישובים מקורבים שכאלה.

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

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

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

הקדמה כללית

היסטוריה

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

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

שיטות ישירות ואיטרטיביות

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

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

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

שיטה טובה מקיימת את שלוש התכונות הבאות:

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

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

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

תחומי מחקר

אינטרפולציה, אקסטרפולציה ורגרסיה

ערכים מורחבים – אינטרפולציה, אקסטרפולציה, רגרסיה

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

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

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

חישוב אינטגרלים

ערך מורחב – שיטות נומריות לחישוב אינטגרלים מסוימים

בעוד שחלק מהאינטגרלים ניתן לחשב באמצעות שיטות אנליטיות הרי יש אינטגרלים אותם לא ניתן לחשב בצורה כזאת. לדוגמה לא קיים פתרון אנליטי לאינטגרל $\int \limits _{a}^{b}e^{-x^{2}}dx$, אולם למרות זאת הוא ניתן לחישוב בצורה נומרית.

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

פתרון משוואות ומערכות משוואות

בעיה בסיסית אחרת היא חישוב פתרון למשוואה נתונה. שני המקרים העיקריים הם משוואות ליניאריות, ומשוואות לא ליניאריות. לדוגמה $5x+6=11$ היא משוואה ליניארית, בעוד $3x^{2}-5=4$ אינה ליניארית.

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

שיטות לפתרון משוואות לא ליניאריות כוללות את שיטת ניוטון רפסון, וכדי לפתור מערכת משוואות לא ליניארית קיימות שיטות כמו Gradient descent.

פתרון משוואות דיפרנציאליות

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

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

אופטימיזציה

ערך מורחב – אופטימיזציה

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

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

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

שימושים

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

דוגמה

אנליזה נומרית מאפשרת להפוך תוצאות מתמטיות אבסטרקטיות (למשל $\sin \left({\frac {\pi }{4}}\right)$) לתוצאות עשרוניות. אנליזה נומרית אפשרה למשל למחשב (ל-Word ליתר דיוק) לצייר את העיגול הבא:

קוטרו של העיגול הוא 4.76 ס"מ והנקודה הכחולה ממוקמת ב-45 מעלות יחסית למרכז העיגול (הנקודה השחורה).

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

• קובעים זווית=0
• משתמשים בפיתוח טיילור עד לסדר רביעי (או אחר) על מנת לחשב את החישובים הבאים ($x,y$ מייצגים את הפיקסל שבהם רוצים לצייר, $r$ מייצג את רדיוס המעגל, $\theta$ מייצגת את הזווית, הסוגריים המרובעים מציינים לקחת ערך שלם, החישובים נעשים ברדיאנים):

${\begin{aligned}&x=\left\lfloor r\cos(\theta )\right\rfloor \\&y=\left\lfloor r\sin(\theta )\right\rfloor \end{aligned}}$

• מגדילים את הזווית ב-${\frac {\pi }{100}}$, מחשבים את הנוסחאות הקודמות וחוזרים על סעיף זה 200 פעמים.

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

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

$\sin \left({\frac {\pi }{4}}\right)=\cos \left({\frac {\pi }{4}}\right)={\frac {1}{\sqrt {2}}}$

אולם המחשב איננו יכול לעבוד עם סימולים כמו ${\frac {1}{\sqrt {2}}}$ על מנת להציבם ב-$x,y$ שהופיעו בחישוב המעגל אלא הוא זקוק לייצוג בינארי של הסימולים, ייצוג המושג על ידי אנליזה נומרית מאפשר למחשב (לאחר הכפלה ברדיוס המעגל) לצייר את הנקודה.

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

• אנליזה נומרית, באתר אנציקלופדיה בריטניקה (באנגלית)
• אנליזה נומרית, דף שער בספרייה הלאומית