הצגת המקור של הדף "הלמה של סטרבנץ"

{{סימון מתמטי}}
בחישובי [[נקודה צפה]], '''ה[[למה (מתמטיקה)|לֶמה]] של סטרבנץ''' (ב[[אנגלית]]: '''Sterbenz' lemma'''){{כ}}{{הערה|{{cite book |last1=Muller |first1=Jean-Michel |last2=Brunie |first2=Nicolas |last3=de Dinechin |first3=Florent |last4=Jeannerod |first4=Claude-Pierre |last5=Joldes |first5=Mioara |last6=Lefèvre |first6=Vincent |last7=Melquiond |first7=Guillaume |last8=Revol |first8=Nathalie |last9=Torres |first9=Serge |title=Handbook of Floating-Point Arithmetic |date=2018 |publisher=Birkhäuser |location=Gewerbestrasse 11, 6330 Cham, Switzerland |isbn=978-3-319-76525-9 |page=101 |doi=10.1007/978-3-319-76526-6 |edition=2nd |url=https://doi.org/10.1007/978-3-319-76526-6}}}} היא משפט שנותן את התנאים בהם חישוב הפרש של [[נקודה צפה]] מחושב באופן מדויק. היא נקראת על שם פט ה. סטרבנץ, שפרסם אותה כמשפט 4.3.1 בספרו ''Floating Point Computation'' בשנת 1974.{{הערה|{{cite book |last1=Sterbenz |first1=Pat H. |title=Floating-Point Computation |date=1974 |publisher=Prentice-Hall |location=Englewood Cliffs, NJ, United States |isbn=0-13-322495-3 |page=138 |url=https://archive.org/details/SterbenzFloatingPointComputation/page/n153/mode/2up}}}}

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

<math display="block">\frac{y}{2} \leq x \leq 2 y</math>

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

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

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

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

== שימוש באנליזה נומרית ==
הלמה של סטרבנץ היא חשובה להוכחת תיאוריות על גבול עליון [[אלגוריתם|באלגוריתמים]] של נקודה צפה.
בתור דוגמה, [[נוסחת הרון]] לחישוב שטח של משולש עם צלעות <math>a</math>, <math>b</math>, <math>c</math> היא:
<math display="block">A = \sqrt{s (s - a) (s - b) (s - c)}</math>
כאשר <math>s = (a + b + c)/2</math> היא מחצית ההיקף.
אם נשתמש בנוסחה הזאת בחישובי נקודה צפה, היא עשויה לתת תוצאות בעלות שגיאה גדולה עבור משולשים צרים.
לעומת זאת, עבור הנוסחה החלופית:
<math display="block">A = \frac{1}{4} \sqrt{\bigl(a + (b + c)\bigr) \bigl(c - (a - b)\bigr) \bigl(c + (a - b)\bigr) \bigl(a + (b - c)\bigr)}</math>
נוכל להוכיח, בעזרת הלמה של סטרבנץ, שהיא בעלת שגיאה קדמית נמוכה לכל קלט אפשרי.{{הערה|{{cite web |last=Kahan |first=W. |author-link=William Kahan |title=Miscalculating Area and Angles of a Needle-like Triangle |date=2014-09-04 |access-date=2020-09-17 |url=https://people.eecs.berkeley.edu/~wkahan/Triangle.pdf |work=Lecture Notes for Introductory Numerical Analysis Classes }}}}{{הערה|{{cite journal |last1=Goldberg |first1=David |title=What every computer scientist should know about floating-point arithmetic |journal=ACM Computing Surveys |date=March 1991 |volume=23 |issue=1 |pages=5–48 |doi=10.1145/103162.103163 |url=https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html |accessdate=2020-09-17 |publisher=Association for Computing Machinery |location=New York, NY, United States |issn=0360-0300}}}}{{הערה|{{cite conference |last1=Boldo |first1=Sylvie |title=How to Compute the Area of a Triangle: a Formal Revisit |journal=Computer Arithmetic, 2009. Arith 2009. 19Th IEEE Symposium on |date=April 2013 |conference=21st IEEE Symposium on Computer Arithmetic |conference-url=http://arith21.arithsymposium.org |doi=10.1109/ARITH.2013.29 |url=https://hal.inria.fr/hal-00790071/document |publisher=IEEE Computer Society |editor1-last=Nannarelli |editor1-first=Alberto |editor2-last=Seidel |editor2-first=Peter-Michael |editor3-last=Tang |editor3-first=Ping Tak Peter |isbn=978-0-7695-4957-6 |issn=1063-6889 |pages=91–98 }}}}

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

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