إلغاء كارثي

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

في التحليل العددي ، فإن الإلغاء الكارثي [ 1 ] [ 2 ] هو الظاهرة التي قد يؤدي فيها طرح تقريبات جيدة لرقمين متجاورين إلى تقريب سيئ للغاية لفرق الأرقام الأصلية.

على سبيل المثال، إذا كان هناك مسماران ، واحدل1=253.51سم{\displaystyle L_{1}=253.51\,{\text{cm}}}طويل والآخرل2=252.49سم{\displaystyle L_{2}=252.49\,{\text{cm}}}إذا كانت الأطوال كبيرة، وتم قياسها بمسطرة لا تتجاوز دقتها السنتيمتر، فإن التقديرات ستكون على النحو التالي:ل~1=254سم{\displaystyle {\tilde {L}}_{1}=254\,{\text{cm}}}ول~2=252سم{\displaystyle {\tilde {L}}_{2}=252\,{\text{cm}}}قد تكون هذه تقريبات جيدة، من حيث الخطأ النسبي ، للأطوال الحقيقية: فالتقريبات بها خطأ أقل من 0.2% من الأطوال الحقيقية.|ل1-ل~1|/|ل1|<0.2%{\displaystyle |L_{1}-{\tilde {L}}_{1}|/|L_{1}|<0.2\%}.

لكن إذا طُرحت الأطوال التقريبية ، فسيكون الفرق هول~1-ل~2=254سم-252سم=2سم{\displaystyle {\tilde {L}}_{1}-{\tilde {L}}_{2}=254\,{\text{cm}}-252\,{\text{cm}}=2\,{\text{cm}}}، على الرغم من أن الفرق الحقيقي بين الأطوال هول1-ل2=253.51سم-252.49سم=1.02سم{\displaystyle L_{1}-L_{2}=253.51\,{\text{cm}}-252.49\,{\text{cm}}=1.02\,{\text{cm}}}الفرق بين التقريبات،2سم{\displaystyle 2\,{\text{cm}}}، وهو خاطئ بنسبة تقارب 100% من حجم الفرق بين القيم الحقيقية،1.02سم{\displaystyle 1.02\,{\text{cm}}}.

لا يتأثر الإلغاء الكارثي بحجم المدخلات ، فهو ينطبق على المدخلات الكبيرة والصغيرة على حد سواء. يعتمد فقط على حجم الفرق ، وعلى خطأ المدخلات. سينتج نفس الخطأ تمامًا عند طرح52سم{\displaystyle 52\,{\text{cm}}}من54سم{\displaystyle 54\,{\text{cm}}}كتقريبات لـ52.49سم{\displaystyle 52.49\,{\text{cm}}}و53.51سم{\displaystyle 53.51\,{\text{cm}}}أو عن طريق الطرح2.00052كم{\displaystyle 2.00052\,{\text{كم}}}من2.00054كم{\displaystyle 2.00054\,{\text{كم}}}كتقريبات لـ2.0005249كم{\displaystyle 2.0005249\,{\text{كم}}}و2.0005351كم{\displaystyle 2.0005351\,{\text{كم}}}.

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

التحليل الرسمي

بصورة رسمية، يحدث الإلغاء الكارثي لأن عملية الطرح غير مستقرة عند المدخلات القريبة: حتى لو كانت التقريباتx~=x(1+دلتاx){\displaystyle {\tilde {x}}=x(1+\delta _{x})}وy~=y(1+دلتاy){\displaystyle {\tilde {y}}=y(1+\delta _{y})}تتميز بأخطاء نسبية صغيرة|دلتاx|=|x-x~|/|x|{\displaystyle |\delta _{x}|=|x-{\tilde {x}}|/|x|}و|دلتاy|=|y-y~|/|y|{\displaystyle |\delta _{y}|=|y-{\tilde {y}}|/|y|}من القيم الحقيقيةx{\displaystyle x}وy{\displaystyle y}، على التوالي، الخطأ النسبي للفرقx~-y~{\displaystyle {\tilde {x}} - {\tilde {y}}}من التقريبات الناتجة عن الفرقx-y{\displaystyle xy}نسبة القيم الحقيقية تتناسب عكسياً مع الفرق بين القيم الحقيقية:

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}}}

وبالتالي، فإن الخطأ النسبي للفرق الدقيقx~-y~{\displaystyle {\tilde {x}}-{\tilde {y}}}من التقريبات الناتجة عن الفرقx-y{\displaystyle x-y}من القيم الحقيقية

|xدلتاx-yدلتاyx-y|.{\displaystyle \left|{\frac {x\delta _{x}-y\delta _{y}}{x-y}}\right|.}

والتي يمكن أن تكون كبيرة بشكل تعسفي إذا كانت القيم الحقيقيةx{\displaystyle x}وy{\displaystyle y}قريبون.

في الخوارزميات العددية

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

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

الأرقام المعطاة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 .