Catastrophic cancellation

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 81 صور
الموسوعة الحرة

In numerical analysis, catastrophic cancellation[1][2] is the phenomenon that subtracting good approximations to two nearby numbers may yield a very bad approximation to the difference of the original numbers.

For example, if there are two studs, one L1=253.51cm{\displaystyle L_{1}=253.51\,{\text{cm}}} long and the other L2=252.49cm{\displaystyle L_{2}=252.49\,{\text{cm}}} long, and they are measured with a ruler that is good only to the centimeter, then the approximations could come out to be L~1=254cm{\displaystyle {\tilde {L}}_{1}=254\,{\text{cm}}} and L~2=252cm{\displaystyle {\tilde {L}}_{2}=252\,{\text{cm}}}. These may be good approximations, in relative error, to the true lengths: the approximations are in error by less than 0.2% of the true lengths, |L1−L~1|/|L1|<0.2%{\displaystyle |L_{1}-{\tilde {L}}_{1}|/|L_{1}|<0.2\%}.

However, if the approximate lengths are subtracted, the difference will be L~1−L~2=254cm−252cm=2cm{\displaystyle {\tilde {L}}_{1}-{\tilde {L}}_{2}=254\,{\text{cm}}-252\,{\text{cm}}=2\,{\text{cm}}}, even though the true difference between the lengths is L1−L2=253.51cm−252.49cm=1.02cm{\displaystyle L_{1}-L_{2}=253.51\,{\text{cm}}-252.49\,{\text{cm}}=1.02\,{\text{cm}}}. The difference of the approximations, 2cm{\displaystyle 2\,{\text{cm}}}, is in error by almost 100% of the magnitude of the difference of the true values, 1.02cm{\displaystyle 1.02\,{\text{cm}}}.

Catastrophic cancellation is not affected by how large the inputs are—it applies just as much to large and small inputs. It depends only on how large the difference is, and on the error of the inputs. Exactly the same error would arise by subtracting 52cm{\displaystyle 52\,{\text{cm}}} from 54cm{\displaystyle 54\,{\text{cm}}} as approximations to 52.49cm{\displaystyle 52.49\,{\text{cm}}} and 53.51cm{\displaystyle 53.51\,{\text{cm}}}, or by subtracting 2.00052km{\displaystyle 2.00052\,{\text{كم}}} from 2.00054km{\displaystyle 2.00054\,{\text{كم}}} as approximations to 2.0005249km{\displaystyle 2.0005249\,{\text{كم}}} and 2.0005351km{\displaystyle 2.0005351\,{\text{كم}}}.

Catastrophic cancellation may happen even if the difference is computed exactly, as in the example above—it is not a property of any particular kind of arithmetic like floating-point arithmetic; rather, it is inherent to subtraction, when the inputs are approximations themselves. Indeed, in floating-point arithmetic, when the inputs are close enough, the floating-point difference is computed exactly, by the Sterbenz lemma—there is no rounding error introduced by the floating-point subtraction operation.

Formal analysis

Formally, catastrophic cancellation happens because subtraction is ill-conditioned at nearby inputs: even if approximations x~=x(1+δx){\displaystyle {\tilde {x}}=x(1+\delta _{x})} and y~=y(1+δy){\displaystyle {\tilde {y}}=y(1+\delta _{y})} have small relative errors|δx|=|x−x~|/|x|{\displaystyle |\delta _{x}|=|x-{\tilde {x}}|/|x|} and |δy|=|y−y~|/|y|{\displaystyle |\delta _{y}|=|y-{\tilde {y}}|/|y|} from true values x{\displaystyle x} and y{\displaystyle y}, respectively, the relative error of the difference x~−y~{\displaystyle {\tilde {x}} - {\tilde {y}}} of the approximations from the difference x−y{\displaystyle xy} of the true values is inversely proportional to the difference of the true values:

x~−y~=x(1+δx)−y(1+δy)=x−y+xδx−yδy=x−y+(x−y)xδx−yδyx−y=(x−y)(1+xδx−yδyx−y).{\displaystyle {\begin{aligned}{\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{aligned}}}

Thus, the relative error of the exact difference x~−y~{\displaystyle {\tilde {x}}-{\tilde {y}}} of the approximations from the difference x−y{\displaystyle x-y} of the true values is

|xδx−yδyx−y|.{\displaystyle \left|{\frac {x\delta _{x}-y\delta _{y}}{x-y}}\right|.}

which can be arbitrarily large if the true values x{\displaystyle x} and y{\displaystyle y} are close.

In numerical algorithms

لا يؤدي طرح الأعداد المتقاربة في العمليات الحسابية ذات الفاصلة العائمة دائمًا إلى إلغاء كارثي، أو حتى أي خطأ - فبحسب نظرية ستيربنز ، إذا كانت الأعداد متقاربة بدرجة كافية، يكون الفرق في الفاصلة العائمة دقيقًا. لكن الإلغاء قد يُضخّم الأخطاء في المدخلات الناتجة عن التقريب في عمليات حسابية أخرى ذات فاصلة عائمة.

مثال: الفرق بين مربعين

الأرقام المعطاةx{\displaystyle x}وy{\displaystyle y}، المحاولة الساذجة لحساب الدالة الرياضية x2-y2{\displaystyle x^{2}-y^{2}} باستخدام الحساب ذي الفاصلة العائمة فل⁡(فل⁡(x2)-فل⁡(y2)){\displaystyle \operatorname {fl} (\operatorname {fl} (x^{2})-\operatorname {fl} (y^{2}))} يخضع للإلغاء الكارثي عندماx{\displaystyle x}وy{\displaystyle y}تكون القيم متقاربة في المقدار، لأن عملية الطرح قد تكشف أخطاء التقريب في عملية التربيع. التحليل البديل (x+y)(x-y){\displaystyle (x+y)(x-y)}، يتم تقييمها بواسطة الحساب ذي الفاصلة العائمة فل⁡(فل⁡(x+y)⋅فل⁡(x-y)){\displaystyle \operatorname {fl} (\operatorname {fl} (x+y)\cdot \operatorname {fl} (x-y))}[ 2 ] يتجنب الإلغاء الكارثي لأنه يتجنب إدخال خطأ التقريب الذي يؤدي إلى عملية الطرح.

على سبيل المثال، إذا x=1+2-29≈1.0000000018626451{\displaystyle x=1+2^{-29}\approx 1.0000000018626451} و y=1+2-30≈1.0000000009313226{\displaystyle y=1+2^{-30}\approx 1.0000000009313226}ثم القيمة الحقيقية للفرق x2-y2{\displaystyle x^{2}-y^{2}} يكون 2-29⋅(1+2-30+2-31)≈1.8626451518330422×10-9{\displaystyle 2^{-29}\cdot (1+2^{-30}+2^{-31})\approx 1.8626451518330422\times 10^{-9}}في حساب IEEE 754 الثنائي 64 ، يتم تقييم التحليل البديل (x+y)(x-y){\displaystyle (x+y)(x-y)} يعطي النتيجة الصحيحة تمامًا (بدون تقريب)، ولكن تقييم التعبير البسيط x2-y2{\displaystyle x^{2}-y^{2}} يعطي العدد العشري 2-29=1.86264514923095703125_×10-9{\displaystyle 2^{-29}=1.8626451{\underline {4923095703125}}\times 10^{-9}}، منها أقل من نصف الأرقام صحيحة، والأرقام الأخرى (المسطرة) تعكس الحدود المفقودة2-59+2-60{\displaystyle 2^{-59}+2^{-60}}، مفقودة بسبب التقريب عند حساب القيم التربيعية الوسيطة.

مثال: دالة الجيب العكسي المركبة

عند حساب دالة الجيب العكسي المركبة ، قد يميل المرء إلى استخدام الصيغة اللوغاريتمية مباشرة:

دالة الجيب العكسية⁡(z)=أناسجل⁡(1-z2-أناz).{\displaystyle \arcsin(z)=i\log {\bigl (}{\sqrt {1-z^{2}}}-iz{\bigr )}.}

لكن، لنفترضz=أناy{\displaystyle z=iy}لy≪-1{\displaystyle y\ll -1}. ثم1-z2≈-y{\displaystyle {\sqrt {1-z^{2}}}\approx -y}وأناz=-y{\displaystyle iz=-y}؛ أطلق على الفرق بينهما اسمε{\displaystyle \varepsilon }— فرق ضئيل للغاية، يكاد يكون معدوماً. إذا1-z2{\displaystyle {\sqrt {1-z^{2}}}}يتم تقييمها باستخدام الحساب ذي الفاصلة العائمة مما يعطي

فل⁡(فل⁡(1-فل⁡(z2)))=1-z2(1+دلتا){\displaystyle \operatorname {fl} {\Bigl (}{\sqrt {\operatorname {fl} (1-\operatorname {fl} (z^{2}))}}{\Bigr )}={\sqrt {1-z^{2}}}(1+\delta )}

مع أي خطأدلتا≠0{\displaystyle \delta \neq 0}، أينفل⁡(⋯){\displaystyle \operatorname {fl} (\cdots )}يشير إلى تقريب الأرقام العشرية، ثم حساب الفرق

1-z2(1+دلتا)-أناz{\displaystyle {\sqrt {1-z^{2}}}(1+\delta )-iz}

من رقمين متجاورين، كلاهما قريب جدًا من-y{\displaystyle -y}قد يؤدي ذلك إلى تضخيم الخطأدلتا{\displaystyle \delta }في مدخل واحد بمعامل1/ε{\displaystyle 1/\varepsilon }— عامل كبير جداً لأنε{\displaystyle \varepsilon }كانت قريبة من الصفر. قد يؤدي هذا إلى جعل الخطأ النهائي كبيرًا جدًا حتى لو كان الخطأدلتا{\displaystyle \delta }في مجال الحوسبة1-z2{\displaystyle {\sqrt {1-z^{2}}}}صغير جداً.

على سبيل المثال، لنفترضz=-1234567أنا{\displaystyle z=-1234567i}القيمة الحقيقية لـدالة الجيب العكسية⁡(z){\displaystyle \arcsin(z)}يبلغ تقريبًا-14.71937803983977أنا{\displaystyle -14.71937803983977i}لكن باستخدام الصيغة اللوغاريتمية البسيطة في حساب IEEE 754 الثنائي 64 - والتي تحسب1-z2{\displaystyle 1-z^{2}}بالضبط، ولا ينتج عنه سوى خطأ تقريب واحد من|دلتا|<2-53{\displaystyle |\delta |<2^{-53}}في1-z2{\displaystyle {\sqrt {1-z^{2}}}}قد يعطي العدد العشري الأقرب إلى-14.719644263563968_أنا{\displaystyle -14.719{\underline {644263563968}}i}، حيث كانت خمسة أرقام فقط من أصل ستة عشر رقماً صحيحة، أما الباقي (المسطر تحته) فكانت جميعها خاطئة.

في الحالة المذكورة أعلاه لـz=أناy{\displaystyle z=iy}لy≪-1{\displaystyle y\ll -1}باستخدام الهويةدالة الجيب العكسية⁡(z)=-دالة الجيب العكسية⁡(-z){\displaystyle \arcsin(z)=-\arcsin(-z)}يتجنب الإلغاء لأنه1-(-z)2=1-z2≈-y{\textstyle {\sqrt {1-(-z)^{2}}}={\sqrt {1-z^{2}}}\approx -y}لكنأنا(-z)=-أناz=y{\displaystyle i(-z)=-iz=y}لذا فإن عملية الطرح هي في الواقع عملية جمع بنفس الإشارة التي لا تلغي بعضها بعضاً.

مثال: التحويل الجذري

غالبًا ما تُكتب الثوابت العددية في برامج الحاسوب بالنظام العشري، كما هو الحال في جزء لغة C لتعريف وتهيئة متغير ثنائي IEEE 754 باسم . ومع ذلك،doublex=1.000000000000001;x1.000000000000001{\displaystyle 1.000000000000001}ليس عددًا ثنائيًا من نوع الفاصلة العائمة 64 بت؛ أقرب عدد من هذا النوع، والذي xسيتم تهيئته في هذا الجزء، هو1.0000000000000011102230246251565404236316680908203125=1+5⋅2-52{\displaystyle 1.0000000000000011102230246251565404236316680908203125=1+5\cdot 2^{-52}}على الرغم من أن تحويل الأساس من نظام الفاصلة العائمة العشري إلى نظام الفاصلة العائمة الثنائي لا يتسبب إلا في خطأ نسبي صغير، إلا أن الإلغاء الكارثي قد يضخمه إلى خطأ أكبر بكثير:

double x = 1.000000000000001 ; // تُقرّب إلى 1 + 5*2^{-52} double y = 1.000000000000002 ; // تُقرّب إلى 1 + 9*2^{-52} double z = y - x ; // الفرق يساوي بالضبط 4*2^{-52}

الفرق1.000000000000002-1.000000000000001{\displaystyle 1.000000000000002-1.000000000000001}يكون0.000000000000001=1.0×10-15{\displaystyle 0.000000000000001=1.0\times 10^{-15}}. الأخطاء النسبية xمن1.000000000000001{\displaystyle 1.000000000000001}ومنy​1.000000000000002{\displaystyle 1.000000000000002}كلاهما أدناه10-15=0.0000000000001%{\displaystyle 10^{-15}=0.0000000000001\%}ويتم حساب عملية الطرح ذات الفاصلة العائمة y - xبدقة بواسطة مبرهنة ستيربنز.

لكن على الرغم من أن المدخلات تمثل تقريبات جيدة، وعلى الرغم من أن عملية الطرح تُحسب بدقة، فإن الفرق بين التقريباتy~-x~=(1+9⋅2-52)-(1+5⋅2-52)=4⋅2-52≈8.88×10-16{\displaystyle {\tilde {y}}-{\tilde {x}}=(1+9\cdot 2^{-52})-(1+5\cdot 2^{-52})=4\cdot 2^{-52}\approx 8.88\times 10^{-16}}يبلغ الخطأ النسبي أكثر من11%{\displaystyle 11\%}من الفرق1.0×10-15{\displaystyle 1.0\times 10^{-15}}بالنسبة للقيم الأصلية كما هي مكتوبة بالنظام العشري: أدى الإلغاء الكارثي إلى تضخيم خطأ صغير في تحويل الأساس إلى خطأ كبير في الناتج.

إلغاء غير مقصود

يُعدّ الإلغاء مفيدًا ومرغوبًا فيه أحيانًا في الخوارزميات العددية. على سبيل المثال، تعتمد خوارزميتا 2Sum و Fast2Sum على هذا الإلغاء بعد حدوث خطأ في التقريب لحساب الخطأ بدقة في عملية جمع الأعداد العشرية كعدد عشري بحد ذاته.

الوظيفة سجل⁡(1+x){\displaystyle \log(1+x)}، إذا تم تقييمها بشكل ساذج عند النقاط 0<x⋘1{\displaystyle 0<x\lll 1}، سيفقد معظم أرقامx{\displaystyle x}في التقريب فل⁡(1+x){\displaystyle \operatorname {fl} (1+x)}ومع ذلك، فإن الوظيفة سجل⁡(1+x){\displaystyle \log(1+x)} نفسه مهيأ بشكل جيد عند المدخلات القريبة0{\displaystyle 0}إعادة كتابتها على النحو التالي: سجل⁡(1+x)=xسجل⁡(1+x)(1+x)-1{\displaystyle \log(1+x)=x{\frac {\log(1+x)}{(1+x)-1}}} استغلال الإلغاء في x^:=فل⁡(1+x)-1{\displaystyle {\hat {x}}:=\operatorname {fl} (1+x)-1} لتجنب الخطأ من سجل⁡(1+x){\displaystyle \log(1+x)} يتم تقييمها مباشرة. [ 2 ] ينجح هذا بسبب الاختزال في البسط سجل⁡(فل⁡(1+x))=x^+يا(x^2){\displaystyle \log(\operatorname {fl} (1+x))={\hat {x}}+O({\hat {x}}^{2})} والإلغاء في المقام x^=فل⁡(1+x)-1{\displaystyle {\hat {x}}=\operatorname {fl} (1+x)-1} يتعارضان مع بعضهما البعض؛ الوظيفة μ(ξ)=سجل⁡(1+ξ)/ξ{\displaystyle \mu (\xi )=\log(1+\xi )/\xi } مشروطة بشكل جيد بالقرب من الصفر بحيث μ(x^){\displaystyle \mu ({\hat {x}})} يعطي تقريبًا جيدًا لـ μ(x){\displaystyle \mu (x)}وبالتالي x⋅μ(x^){\displaystyle x\cdot \mu ({\hat {x}})} يعطي تقريبًا جيدًا لـ x⋅μ(x)=سجل⁡(1+x){\displaystyle x\cdot \mu (x)=\log(1+x)}.

مراجع

  1. ^ مولر، جان ميشيل. بروني، نيكولاس؛ دي دينشين، فلوران؛ جانرود، كلود بيير؛ جولديس، ميوارا؛ لوفيفر، فنسنت؛ ملكيوند، غيوم؛ ريفول, ناتالي ; توريس، سيرج (2018). دليل حساب النقطة العائمة (  الطبعة الثانية). Gewerbestrasse 11، 6330 شام، سويسرا: بيركهاوسر. ص.  102. دوى : 10.1007/978-3-319-76526-6 . رقم ISBN 978-3-319-76525-9.{{cite book}}: CS1 maint: location ( link )
  2. 1 2 3 غولدبيرغ، ديفيد (مارس 1991). "ما يجب أن يعرفه كل عالم حاسوب عن حسابات الفاصلة العائمة" . مجلة ACM Computing Surveys . 23 (1). نيويورك، نيويورك، الولايات المتحدة: جمعية آلات الحوسبة: 5-48 . doi : 10.1145/103162.103163 . ISSN 0360-0300 . S2CID 222008826. تاريخ الاسترجاع: 17 سبتمبر 2020 .