הלמה של סטרבנץ

תבנית:סימון מתמטי בחישובי נקודה צפה, הלֶמה של סטרבנץ (באנגלית: Sterbenz' lemma)תבנית:כתבנית:הערה היא משפט שנותן את התנאים בהם חישוב הפרש של נקודה צפה מחושב באופן מדויק. היא נקראת על שם פט ה. סטרבנץ, שפרסם אותה כמשפט 4.3.1 בספרו Floating Point Computation בשנת 1974.תבנית:הערה

הלמה של סטרבנץ טוענת שעבור מערכת מספרים של נקודה צפה עם מספרים תת-נורמליים, כגון IEEE 754 binary64, אם $y$, $x$ הם מספרי נקודה צפה כך שמתקיים:

$$\frac{y}{2}\le x\le 2y$$

אז המספר $x-y$ גם הוא מספר נקודה צפה. ולכן, חישוב ההפרש $x\ominus y=\mathrm{fl}(x-y)=x-y$ מתבצע באופן מדויק.

קשר לביטול הרסני

ניתן להשוות בין הלמה של סטרבנץ לבין ביטול הרסני: הלמה של סטרבנץ טוענת כי אם $y$, $x$ הן מספרי נקודה צפה מספיק קרובים, אז ההפרש ביניהם מחושב באופן מדויק, ללא צורך בעיגול: $x\ominus y=\mathrm{fl}(x-y)$.

התופעה של ביטול הרסני היא שאם $\tilde{x}$, $\tilde{y}$ הם ערכים משוערכים למספרים האמיתיים $x$, $y$ בהתאמה. בין אם השגיאה בחישובם מופיע מעיגול קודם או מקיטום, השגיאה המתקבלת בחישוב ההפרש בין המספרים המשוערכים $\tilde{x}-\tilde{y}$ היא הפוכה בפרופורציה להפרש המדויק $x-y$. ולכן, אם הערכים קרובים מאוד, השגיאה של החישוב המשוערך גדולה מאוד.

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

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

הלמה של סטרבנץ היא חשובה להוכחת תיאוריות על גבול עליון באלגוריתמים של נקודה צפה. בתור דוגמה, נוסחת הרון לחישוב שטח של משולש עם צלעות $a$, $b$, $c$ היא: $$A=\sqrt{s(s-a)(s-b)(s-c)}$$ כאשר $s=(a+b+c)/2$ היא מחצית ההיקף. אם נשתמש בנוסחה הזאת בחישובי נקודה צפה, היא עשויה לתת תוצאות בעלות שגיאה גדולה עבור משולשים צרים. לעומת זאת, עבור הנוסחה החלופית: $$A=\frac{1}{4}\sqrt{(a+(b+c))(c-(a-b))(c+(a-b))(a+(b-c))}$$ נוכל להוכיח, בעזרת הלמה של סטרבנץ, שהיא בעלת שגיאה קדמית נמוכה לכל קלט אפשרי.תבנית:הערהתבנית:הערהתבנית:הערה