شرطیسازی و پایداری عددی
شرطیسازی میزان حساسیت راهحل یک مسئله به اغتشاشات در دادههای آن را اندازهگیری میکند، در حالی که پایداری میزان خطایی را که یک الگوریتم خاص در محاسبات با دقت محدود اضافه میکند، میسنجد؛ این دو با هم دقت یک نتیجه محاسبهشده را تعیین میکنند.
Definition
شرطیسازی یک ویژگی ذاتی مسئله است که چگونگی پاسخ راهحل دقیق آن به اغتشاشات ورودی را توصیف میکند، در حالی که پایداری عددی یک ویژگی الگوریتم است که نشان میدهد چگونه با وجود خطاهای گرد کردن، مسئله را به درستی حل میکند.
Scope
این موضوع شامل محاسبات ممیز شناور و خطای گرد کردن واحد، عدد شرطی مسائل مانند حل سیستمهای خطی و ارزیابی توابع، خطای پیشرو و پسرو، قاعده سرانگشتی که خطای پیشرو توسط عدد شرطی ضربدر خطای پسرو محدود میشود، و تعاریف پایداری پسرو و پیشرو است.
Core questions
- محاسبات ممیز شناور چگونه مدلسازی میشود و نقش خطای گرد کردن واحد چیست؟
- عدد شرطی یک مسئله چه چیزی را کمیسازی میکند و چگونه برای سیستمهای خطی و برای ارزیابی تابع تعریف میشود؟
- خطای پیشرو، خطای پسرو و شرطیسازی چگونه با هم مرتبط هستند؟
- چه چیزی یک الگوریتم پایدار پسرو را از یک الگوریتم پایدار پیشرو متمایز میکند و چرا پایداری پسرو هدف معمول است؟
Key theories
- عدد شرطی
- عدد شرطی عاملی است که توسط آن اغتشاشات نسبی در دادهها میتوانند در راهحل تقویت شوند؛ برای یک سیستم خطی برابر است با نرم ماتریس ضربدر نرم معکوس، و محدودیتی را برای دقت قابل دستیابی مستقل از الگوریتم تعیین میکند.
- تحلیل خطای پسرو
- به جای محدود کردن مستقیم خطا در پاسخ، نشان داده میشود که نتیجه محاسبهشده پاسخ دقیق به یک مسئله نزدیک است؛ یک الگوریتم پایدار پسرو است زمانی که این مسئله نزدیک با مسئله اصلی به میزان مرتبه خطای گرد کردن واحد تفاوت داشته باشد.
- خطای پیشرو برابر است با عدد شرطی ضربدر خطای پسرو
- قاعده سرانگشتی اصلی تحلیل عددی بیان میکند که خطای پیشرو (راهحل) تقریباً توسط عدد شرطی مسئله ضربدر خطای پسرو محدود میشود، که سهم مسئله و الگوریتم را به وضوح از هم جدا میکند.
Mechanisms
اعداد ممیز شناور اعداد حقیقی را با دقت محدود نمایش میدهند، بنابراین هر عملیات ابتدایی یک خطای نسبی را به همراه دارد که توسط خطای گرد کردن واحد محدود میشود. تحلیل خطای پسرو این خطاها را با نسبت دادن آنها به اغتشاشات دادهها به جای نتیجه، ردیابی میکند و کرانهایی به شکل: پاسخ محاسبهشده برابر با پاسخ دقیق یک ورودی اغتشاشیافته، تولید میکند. ترکیب یک کران خطای پسرو با عدد شرطی مسئله، تخمینی از خطای پیشرو را به دست میدهد، که توضیح میدهد چرا یک الگوریتم پایدار ممکن است در یک مسئله بدشرط دقت خود را از دست بدهد.
Clinical relevance
درک شرطیسازی و پایداری هر زمان که نتایج محاسبهشده باید قابل اعتماد باشند، ضروری است: این موضوع توضیح میدهد که چرا برخی فرمولبندیهای حداقل مربعات دقت خود را از دست میدهند، انتخاب الگوریتمهای پایدار و فرمولبندیهای خوشوضع را در شبیهسازی و تحلیل دادهها هدایت میکند، و هشدار میدهد که یک مدل بدشرط نمیتواند پاسخی قابل اعتماد ارائه دهد، صرف نظر از روش مورد استفاده.
History
چارچوب مفهومی توسط ویلکینسون پایهگذاری شد، که تحلیل خطای پسرو او در دهه 1960 قابلیت اطمینان عملی حذف گاوسی را توضیح داد، و بعدها توسط هایام در کل این زمینه نظاممند و گسترش یافت؛ استاندارد ممیز شناور IEEE 754 متعاقباً رفتار گرد کردن را بر پایه محکمی و قابل حمل قرار داد.
Key figures
- James H. Wilkinson
- Nicholas J. Higham
- Lloyd N. Trefethen
- William Kahan
Related topics
Seminal works
- trefethen1997
- higham2002
Frequently asked questions
- اگر یک الگوریتم پایدار باشد، آیا همیشه پاسخ دقیقی خواهد داد؟
- خیر. یک الگوریتم پایدار پسرو تنها تضمین میکند که پاسخ آن برای یک مسئله نزدیک دقیق است؛ اگر خود مسئله بدشرط باشد، آن مسئله نزدیک میتواند راهحل بسیار متفاوتی داشته باشد، بنابراین خطای پیشرو ممکن است همچنان زیاد باشد.
- خطای گرد کردن واحد چیست؟
- خطای گرد کردن واحد حداکثر خطای نسبی است که هنگام گرد کردن یک عدد حقیقی به نزدیکترین عدد ممیز شناور رخ میدهد؛ این خطا گرانولاریته محاسبات ممیز شناور را تعیین میکند و تقریباً در هر کران پایداری ظاهر میشود.