ניוטון רפסון

[student47]

ניוטון רפסון

עליי למצוא את השורש של המשוואה f(x)=x^3 + 13.8x^2 + 42.2x -9
שנמצא בקטע [0,1] עם (tol = 10^(-6.
יש להתייחס לשגיאה כ- e_n = zz x_(n+1) - x_n zz.

בשלב ראשון, אני צריך לעשות את זה בשיטת ניוטון רפסון.
אני גוזר ומקבל: f'(x)= 3x^2 -27.6x+42.2
מתקיים: (x_(n+1) = x_n - f(x_n) / f'(x_n

ולאחר הצבה אני מקבל:
zz x_(n+1) = x_n - ((x_n)^3 +13.8(x_n)^2 + 42.2x_n - 9) / (3(x_n)^2 - 27.6x_n + 42.2) zz (*)

כאמור בשאלה, יש להתייחס לשגיאה כאל: |e_n = |x_(n+1) - x_n
לכן אם נעביר אגפים במשוואה (*), ונשים ערך מוחלט, מקבל:
zz |x_(n+1) - x_n| = |x_n - ((x_n)^3 +13.8(x_n)^2 + 42.2x_n - 9) / (3(x_n)^2 - 27.6x_n + 42.2)| zz

1) מאיזה x אני צריך להתחיל את הפעלת ניוטון רפסון? האם x=2 זה בסדר?
2) x_n, עבור n = 0, זו הנקודה הראשונה שאיתה אני מתחיל. (x_(n+1 זה החיתוך עם ציר ה-x של הישר ששיפועו (f'(x0 המשיק לגרף בנקודה ((x0,f(x0).
3) השגיאה היא zz |x_(n+1) - x_n| zz , שזה בדיוק הביטוי המודגש.
אם אציב בביטוי במקום x_n בביטוי המודגש, את ערך ה-x שאיתו אני מתחיל את ניוטון רפסון (למשל את x=2), אז יוצא שאני מתייחס לשגיאה
כך: |(en = |f(x_(n+1)) - f(x_n ולא כך: |(en = |f(x_(n+1)) - f(x_n (כפי שדורשים בשאלה). או שאני מתבלבל?

אודה על עזרתכם!

 

[student47]

באותו עניין: שאלה חשובה ובסיסית

4) שאלה ספציפית לגבי שיטת ניוטון רפסון באופן כללי (לאו דווקא בנוגע לשאלה ששאלה מקודם, למרות שהיא כמובן רלוונטית גם אליה)..
נניח שיש פונקציה f שהשורש שלה הוא x = p. כלומר f(p)=0.
בעצם בשיטת ניוטון רפסון אני מקבל כל פעם נקודת חיתוך של המשיק הנוכחי עם ציר ה-x.
כלומר אני מקבל סדרת נקודות {x_n} שמתכנסת ל-x = p.
נניח למשל, כמו בדוגמה הקודמת, ש (tol = 10^(-6.

נסמן את ה x_n הראשון בסדרה {x_n} שמתכנסת ל-p, אשר מרחקו מ p קטן מ (tol = 10^(-6, ב 'x. למה מציאת 'x שקולה לכך
שהגעתי לאיטרציה של האלגוריתם עבורה ההפרש zz |x_(n+1) - x_n| zz קטן מ-tol?

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

שוב, תודה על העזרה.

 

[student47]

(לגבי שאלה 4) יש מצב שזה קשור לקריטריון קושי להתכנסות סדרות?

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

 

[1ca1]

אין שום קשר

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

 

[1ca1]

השאלה אולי חשובה אבל לא בהכרח נכונה

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

 

[student47]

בקשר למה שענית

1)
כשאתה אומר " אתה מקבל הרי סדרת נקודות שתמיד יהיו מימין ומשמאל לשורש המקורי, ככה זה עובד"
אתה מתכוון שמדובר בסדרת נקודות שכל 2 נקודות עוקבות בה (עוקבות באינדקסים כמובן), (x_n , x_(n+1, נמצאות בשניי צדדים שונים של השורש?

אם ההתכנסות היא ע"י סדרת נקודות כך שכל 2 נקודות עוקבות (x_n, x(n+1, נמצאות בצדדים שונים של השורש, אז אחלה..זה עונה לי על השאלה
כי מצאתי 2 נקודות משניי צידי השורש שהמרחק ביניהן קטן מ-tol, אז זה שקול להגיד שמצאתי נקודה p בסדרה, שנמצאת מספיק קרוב לשורש.

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

 

[1ca1]

תשובה

זה לא תמיד נכון, אבל בחיים זה בד"כ מה שקורה.
זה קורה במקרה של חישוב שורש ריבועי למשל אם אני זוכר נכון.
&nbsp
אבל יש מקרים של התכנסות מצד אחד, נניח f תמיד חיובית וקמורה, אז תמיד הנגזרת תתקרב רק מצד אחד.
&nbsp
באופן כללי, התנאי שכתבת לעצירה הוא לא נכון.
אפשר לדמיין כזאת פרבולה (כנראה צריך כאן משהו בחזקה זוגית מאוד גדולה, x^8 או משהו) עם קצת גלים באורך גל של השגיאה הזאת שתיארת ותבחר נקודות ספציפיות שקצב ההתכנסות בהן יהיה מתאים ופשוט תפגע בגלים הללו, והמשיקים יחתכו קרוב אחד לשני ויימשכו לבסוף לשורש האמיתי אבל בדרך יהיה מקרה ש- x_n+1 - xn יהיה קטן, אבל לא קרוב בכלל לשורש.
או פונקציה קמורה עם שיפועים מתאימים ועוד דוגמאות שונות.