ביטול הרסני

באנליזה נומרית, ביטול הרסני<ref name="handbook"></ref><ref name="goldberg"></ref> היא תופעה בה הדיוק של חיסור של שני מספרים עם שגיאה קטנה גוררת שגיאה גדולה. דבר זה עלול לקרות גם אם החיסור הוא מדויק.

לדוגמה, נניח שיש לנו שני עמודי עץ, אחד באורך <math>L_1 = 254.5\,\text{cm}</math> והשני <math>L_2 = 253.5\,\text{cm}</math>. אם נמדוד אותם בסרגל בעל דיוק של סנטימטר, אנחנו עלולים לקבל ערכים: <math>\tilde L_1 = 255\,\text{cm}</math>, <math>\tilde L_2 = 253\,\text{cm}</math>, שמתאימים להרבה שימושים: שגיאה יחסית של פחות מ-2% מהאורך האמיתי: <math>|L_1 - \tilde L_1|/|L_1| < 2%</math>.

אבל אם נחשב את ההפרש בין הערכים המשוערים, נקבל: <math>\tilde L_1 - \tilde L_2 = 255\,\text{cm} - 253\,\text{cm} = 2\,\text{cm}</math>, לעומת הפרש אמיתי של <math>L_1 - L_2 = 254.5\,\text{cm} - 253.5\,\text{cm} = 1\,\text{cm}</math>. השגיאה היחסית היא כעת 100%.

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

== ניתוח פורמלי ==
פורמלית, ביטול הרסני קורה בגלל שחיסור היא פעולה בעלת מספר התניה גרוע עבור ערכים קרובים: גם אם המספרים המשוערכים <math>\tilde x = x (1 + \delta_x)</math>, <math>\tilde y = y (1 + \delta_y)</math> הם בעלי שגיאה יחסית נמוכה <math>|\delta_x| = |x - \tilde x|/|x|</math> <math>|\delta_y| = |y - \tilde y|/|y|</math> בהתאמה, השגיאה היחסית של פעולת החיסור היא בעלת פרופורציה הפוכה להפרש האמיתי בין הערכים:

<math display="block">
\begin{align}
 \tilde x - \tilde y
 &= x (1 + \delta_x) - y (1 + \delta_y)
 = x - y + x \delta_x - y \delta_y \\
 &= x - y + (x - y) \frac{x \delta_x - y \delta_y}{x - y} \\
 &= (x - y) \biggr(1 + \frac{x \delta_x - y \delta_y}{x - y}\biggr).
\end{align}
</math>

וכך אנו נוכחים שהשגיאה היחסית של החיסור המדויק <math>\tilde x - \tilde y</math> של המספרים המשוערכים היא:

<math display="block">
\biggl|\frac{x \delta_x - y \delta_y}{x - y}\biggr|.
</math>

והיא עלולה להיות גדולה מאוד אם הערכים האמיתיים <math>x</math> ,<math>y</math> קרובים.

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

<math display="block">
\arcsin(z) = i \log \bigl(\sqrt{1 - z^2} - i z\bigr).
</math>

כדוגמה בעייתית של שלב החיסור באלגוריתם, נניח למשל: <math>z = i y</math> וכן <math>y \ll 0</math>.
וכך מתקבל:
<math>\sqrt{1 - z^2} \approx -y</math>
<math>i z = -y</math>
ההפרש בין המספרים הוא כמעט אפסי, נבטא את ההפרש: <math>\varepsilon</math>—a

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

<math display="block">
\operatorname{fl}\Bigl(\sqrt{\operatorname{fl}(1 - \operatorname{fl}(z^2))}\Bigr)
= \sqrt{1 - z^2}(1 + \delta)
</math>

ונבצע את החישוב ללא תוספת שגיאה <math>\delta \ne 0</math> עקב חישוב של נקודה צפה <math>\operatorname{fl}(\cdots)</math>
וכעת, ההפרש בין המספרים:

<math display="block">
\sqrt{1 - z^2}(1 + \delta) - i z
</math>

של שני המספרים הקרובים, ששניהם קרובים לערך <math>-y</math>, עשוי להגביר את השגיאה באחד ערכי הקלט בפקטור של <math>1/\varepsilon</math>—a שהוא מאוד גדול, בגלל שההפרש ביניהם הוא מאוד קטן.

דוגמה מספרית:
אם <math>z = -1234567 i</math> אז הערך המדויק של <math>\arcsin(z)</math> הוא בסביבות <math>-14.71937803983977i</math>, אבל בשימוש בנוסחה הלוגריתמית בנקודה צפה של בעלת 64 ביטים תתקבל תוצאה של <math>-14.719\underline{644263563968}i</math>, עם רק 5 מתוך 16 ספרות נכונות, וכל שאר הספרות (עם קו תחתון) הן שגויות.

במקרה של <math>z = i y</math> אבל <math>y < 0</math>, אם נשתמש בזהות <math>\arcsin(z) = -\arcsin(-z)</math> נצליח להימנע מביטול הרסני, וזה בגלל שמתקיים: <math>\sqrt{1 - (-z)^2} = \sqrt{1 - z^2} \approx -y</math> אבל <math>i (-z) = -i z = y</math>, ולכן החיסור הוא חיבור עם אותו הסימן שלא סובל מתופעת הביטול ההרסני.

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

==ראו גם==
* אנליזה נומרית

== הערות שוליים ==

קטגוריה:אנליזה נומרית