NUM1_E2022WA 2022 חורף מועד א

חורף 2022 מועד א’

תרגיל 1

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

נניח שכל המספרים מיוצגים ע”י נקודה צפה.

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

סעיף א’

נבצע אלימינציית גאוס:

נמשיך למצוא את :

לסיכום:

סעיף ב’

מאלימינציית גאוס קיבלנו:

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

הפתרון האמיתי:

ולכן השגיאה האבסולוטית:

עבור :

הפתרון האמיתי:

ולכן השגיאה האבסולוטית:

עבור :

הפתרון האמיתי:

ולכן השגיאה האבסולוטית:

סעיף ג’

נבצע שוב אלימינציית גאוס, אבל הפעם נחליף בין השורות ו-:

נמצא את ו-:

עבור :

ולכן השגיאה:

עבור :

ולכן השגיאה:

עבור :

ולכן השגיאה:

סעיף ד’

את המספר מצב נמצא ע”י ההגדרה:

נעשה זאת בעזרת נורמה-. עבור :

נחשב את :

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

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

נחשב את :

קיבלנו ש- . נסיק ש:

נציב בהגדרת המספר מצב:

ולכן:

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

תרגיל 2

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

1. מצאו את פולינום האינטרפולציה עבור 3 הנקודות הנתונות.
2. פתחו שיטת אינטגרציה המבוססת על 3 הנקודות הנ”ל (מומלץ באמצעות הפולינום).
3. העריכו את שגיאת האינטגרציה כאשר קטן. השוו את השיטה מבחינת דיוק, לשיטות אחרות עם אותו מספר דגימות של .
4. נשתמש בשיטה באינטגרציה מורכבת (מוכללת) כדי להעריך את האינטגרל בתחום . רשמו ביטוי להערכה של האינטגרל ושל השגיאה.
5. בצעו אינטרפולציית ריצ’רדסון לאינטגרציה בתחום לשיפור הדיוק עבור ו-. יש לבטא את הפתרון בעזרת ו-. מהו סדר השגיאה?

סעיף א’

נמצא את פולינום האינטגרציה ע”י אינטרפולציית לגרנג’:

כאשר סימנו . הפולינום שלנו:

נמצא את הפולינומי לגרנג’:

סעיף ב’

נחשב את האינטגרל של כל אחד מפולינומי לגרנג’:

נוכל כעת לבנות את הקירוב שלנו לאינטגרל:

נציב את האינטגרלים שקיבלנו:

סעיף ג’

נפתח לטור טיילור את האינטגרנד שלנו (סביב ):

נפתח לטור טיילור את ה- (סביב ) בקירוב לאינטגרל:

נציב בהגדרת השגיאה כדי לקבל:

נסכם:

כאשר .

סעיף ד’

כדי להכליל את השיטה שלנו לתחום , נחלק אותו ל- קטעים ועל כל אחד מהם נפעיל את השיטה שלנו. נקבל:

השגיאה של שיטה זו תהיה סכימה של כל השגיאות של השיטה הלא מוכללת:

כאשר .

סעיף ה’

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

נסמן . לכן:

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

נשים לב ש- .
מהגדרת השגיאה:

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

נסיק כי:

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

תרגיל 3

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

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

סעיף א’

נרשום את המערכת משוואות שלנו:

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

נוכל כעת להציב בהגדרת פונקציית המחיר:

סעיף ב’

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

• נמצא את וקטור הכיוון ע”י פתירת מערכת המשוואות:
• נקדם את האיטרציה שלנו ע”י .

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

לכן נבחר את בצורה הבאה:

ההסיין הוא היעקוביאן של :

הפתרון לא בהכרח יתכנס למינימום. הוא יכול להתכנס גם לנקודת אוכף או נקודת מקסימום - והוא תלוי לגמרי בניחוש ההתחלתי.

סעיף ג’

בשיטת הגרדיאנט בוחרים את גודל הצעד שלנו בצורה הבאה:

במקרה שלנו:

כדי לעדכן את האיטרציה שלנו, נוסיף את ל-:

כאשר את נבחר בשיטת החזרה לאחור, עבור כלשהו:

נעצור כאשר נקבל:

תרגיל 4

נתונה בעיית תנאי השפה:

את הבעיה הזו נפתור בעזרת הפרשים סופיים.

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

סעיף א’

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

נציב בשגיאה של הקירוב הראשון, שנתונה ע”י:

באותו אופן עבור השגיאה של הקירוב השני:

לסיכום:

סעיף ב’

משיטת ההפרשים המרכזיים:

נציב במשוואה, כאשר נשים לב שכעת :

נוכל כעת לבנות את מערכת המשוואות, כאשר נשים לב ש-, ואנו עובדים בקטע .

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

כדי לחשב את בעזרת הנוסחה, ניאלץ להוסיף עוד נקודה לחישוב שלנו, :

נציב בחזרה במערכת משוואות, כאשר רק המשוואה הראשונה והאחרונה משתנה:

נסדר טיפה את המשוואה עבור :

בכתיב מטריצי, כאשר אנו מציבים :

סעיף ג’

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

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

נדרוש שהפתרון יקיים את תנאי השפה השני של הבעיה:

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

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