خواندن ۴ دقیقه·۶ سال پیش

محاسبات ناپایدار: یک خطای مهندسی مهلک

در تاریخ ۲۵ فوریه سال ۱۹۹۱ میلادی سیستم موشکی پاتریوت (patriot missile system) در عربستان دچار خطا شده و یک موشک بالستیک باعث کشته شدن ۲۸ سرباز آمریکایی شد. بررسی بعد از حادثه نکته ی شگفت انگیزی را آشکار کرد. ساعت داخلی پاتریوت بر اساس قدم های زمانی ۰.۱ ثانیه با یک عدد صحیح به عنوان آفست کار می کرد. این عدد سپس به یک عدد شناور (float) با ۲۴ بیت تبدیل می شد که برای محاسبه سرعت موشک و مکان حمله مورد استفاده قرار میگرفت. بیست ساعت آنلاین بودن سیستم باعث تجمیع خطا در یک «محاسبه ناپایدار» که ناشی از تبدیل عدد int به float بود به جایی رسید که سیستم پاتریوت عملا غیر قابل استفاده میشد چون تمام محاسبات عددی آن غلط بودند و همین باعث فاجعه شد!

اما «محاسبه ناپایدار» یعنی چه؟ ما هنگام محاسبات فرمولهای فیزیک و ریاضی فرض میگیرم که عددهایی که در داخل فرمول ها هستند حقیقی هستند و به همین خاطر ویژگی های خوبی مانند پیوستگی از آن ها انتظار داریم اما در عمل یعنی در کامپیوتر عدد حقیقی ای وجود ندارد بلکه با اعداد اعشاری floating point مواجه هستیم که دقت بی نهایت ندارند! برای اینکه مشکل را متوجه بشید به فرمول زیر دقت کنید:

این فرمول را اگر ساده کنید به نتیجه زیر میرسید:

و وقتی h خیلی کوچک باشد میتوان نوشت:

اگر تمام اعداد اینجا اعداد حقیقی باشند حرف درست است اما در کامپیوتر با اعداد floating point روبرو هستیم. اگر بیاییم و به جای آخرین فرمول اولی را پیاده سازی کنیم. و مقایسه کنیم چیزی شبیه زیر خواهد بود:

که جواب درست همان محاسبه پایدار است. دلیل اینکه چنین اتفاقی می افتد این است که وقتی با اعداد بسیار کوچک یا بزرگ کار می کنیم همیشه این احتمال وجود دارد که گرد کردن اتفاق بیفتد یا عدد ورودی به الگوریتم دارای قدری خطای اندازه گیری باشد و این در محاسبات floating point فاجعه آفرین است.

چنین مساله ای آنقدر اهمیت دارد که یک نظریه کامل برای آن وجود دارد! خواننده کنجکاو می تواند به درون آن کند و کاو کند اینجا فقط چند مثال دیگر می آوریم.

در محاسبات ماتریسی هنگام وارون کردن یک ماتریس (که بسیار معمول هستند) مثلا برای حل معادلات باید بسیار دقت کرد. زیرا بعضی از ماتریس ها بسیار به ماتریس singular نزدیک هستند و معکوس کردن آن ها با قدری تغییر نتایج کاملا متفاوتی را ایجاد می کند. به طور مثال ماتریس زیر را در نظر بگیرید:

اگر معکوس این ماتریس را محاسبه کنیم داریم:

حالا کافی است قدری مقادیر ماتریس را تغییر دهیم. مثلا به صورت زیر:

اگرچه ماتریس خیلی تغییر نکرده اما معکوس آن به صورت زیر می شود:

برای آنکه متوجه بشویم اشکال کار کجاست ابزاری ساخته شده است به نام «عدد شرطی» (condition number) که اندازه آن مشخص می کند چقدر یک ماتریس (یا به طور کلی فرمول) در محاسبات ناپایدار است. برای ماتریس این مقدار برابر است با: