NUM1_E2021WA 2021 חורף מועד א

2021 חורף מועד א’

תרגיל 1

נתונה הפונקציה . נרצה למצוא את הנקודות שהפונקציה מתאפסת (נניח שהפתרון לא ידוע).

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

סעיף א’

נרצה למצוא מתי מתקיים

בעזרת שיטת ניוטון.
נמצא את הנגזרת של הפונקציה (באופן אנליטי):

הנוסחה לשיטה האיטרטיבית:

נתחיל עם :

סעיף ב’

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

סעיף ג’

נרצה למצוא את :

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

ליד הפתרון, כלומר ליד , נוכל לבצע את ההנחות הבאות:

נציב ונקבל:

נסיק כי קצב ההתכנסות של השיטה ליד הפתרון הוא לינארי.

תרגיל 2

נתונה מערכת משוואות , כאשר:

נרצה לפתור את הבעיה בעזרת שיטת יעקובי.

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

סעיף א’

תהי מטריצה ריבועית כללית . נסמן:

כאשר היא מטריצה המכילה רק את האלכסון של .

נמצא את הנורמה של :

מעצם הגדרת מתקיים:

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

נפרק את פעולת הסכימה למקרים בהם ולמקרים בהם :

נציב את התכונה הנתונה:

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

סעיף ב’

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

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

סעיף ג’

הנוסחה לשיטת יעקובי:

נציב את הנתונים שלנו, עם תנאי ההתחלה :

קיבלנו ש:

סעיף ד’

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

הנורמה- שלה יהיה:

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

נרצה לדעת מתי הביטוי הימני שווה ל-. נשווה ונציב את הערך שמצאנו עבור הנורמה- של :

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

תרגיל 3

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

עם התנאי שפה:

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

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

סעיף א’

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

עבור נגזרת שנייה:

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

נציב ונקבל את הבעיה:

נחלק את הקטע ל- קטעים באורך . לכן:

נציב במשוואה:

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

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

סעיף ב’

באופן מטריצי:

סעיף ג’

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

תרגיל 4

בשאלה זו סעיפים ג’, ד’ לא תלויים בסעיפים א’,ב’.

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

אינטגרלי עזר:

סעיף א’

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

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

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

נציב במשוואה הראשונה ונקבל:

לסיכום:

סעיף ב’

השגיאה נתונה ע”י:

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

כאשר . נמשיך עם האינטגרציה, כאשר ניעזר באינטגרלי עזר:

את כבר מצאנו בסעיף קודם:

את הערך גם נפתח בטור מקלורן:

כאשר . נפשט טיפה את הביטוי:

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

ממשפט ערך הביניים, נוכל לשלב את ו-:

כאשר . נמשיך לפתח את הביטוי:

נשים לב כי:

נציב בחזרה בביטוי עבור :

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

נודר בחיים לא הייתי מצליח את הסעיף הזה במבחן.

סעיף ג’

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

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

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

סעיף ד’

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