Norm، شرطی‌بودن و پایداری عددی

از اندازه خطا تا condition number؛ ببینیم یک محاسبه چقدر نسبت به خطا و تغییرات ورودی حساس است.

برنامه‌نویسی و محاسبات علمیمتوسط

مشاهده آموزش‌های دیگر مشاهده پروژه مرتبط

هدف یادگیری

بتوانید norm را برای سنجش خطا تفسیر کنید، condition number را توضیح دهید و تفاوت residual، error و sensitivity را ببینید.

پیش‌نیازها

جبر خطی مقدماتی
بردار و ماتریس
آشنایی با residual

Norm چه چیزی را اندازه می‌گیرد؟

برای اینکه دو خطا را با هم مقایسه کنیم، به معیاری برای اندازه نیاز داریم. norm دو، طول اقلیدسی بردار را اندازه می‌گیرد.

Norm دو

\|x\|_2=\sqrt{\sum_i x_i^2}

خطای مطلق و نسبی

خطای مطلق برداری

e=x-\hat{x}

خطای نسبی

\text{relative error}=\frac{\|x-\hat{x}\|}{\|x\|}

خطای نسبی کمک می‌کند مقدار خطا را در مقیاس خود مسئله تفسیر کنیم.

Condition number

یک مسئله well-conditioned تغییرات کوچک ورودی را به تغییرات بسیار بزرگ خروجی تبدیل نمی‌کند. برای بسیاری از مسائل خطی، condition number معیار این حساسیت است.

Condition number

\kappa(A)=\|A\|\,\|A^{-1}\|

κ بزرگ‌تر یعنی مسئله نسبت به perturbation حساس‌تر است. این sensitivity با خطایی که خود الگوریتم تولید می‌کند یکسان نیست.

Residual با error یکی نیست

Residual

r=b-A\hat{x}

Residual کوچک یعنی جواب تقریبی با معادله سازگار است؛ اما برای نتیجه‌گیری درباره error باید conditioning را نیز در نظر گرفت.

ارتباط با solver عددی

در Convex QP Solver، diagnostics فقط به مقدار objective محدود نیستند. stationarity، primal feasibility، complementarity و duality gap کمک می‌کنند کیفیت پاسخ را چندبعدی بررسی کنیم.

تمرین

Norm دو بردار (3,4) و (1,1) را محاسبه کنید.
تفاوت absolute error و relative error را با یک مثال توضیح دهید.
چرا residual کوچک همیشه به معنی error کوچک نیست؟

پروژه مرتبط

Convex Quadratic Programming Solver

Residual diagnostics و validation عددی در این پروژه برای بررسی خروجی solver استفاده می‌شوند.

باز کردن منبع

راهکارهای مرتبط

مدل‌سازی، الگوریتم و بهینه‌سازی توسعه و مهندسی نرم‌افزار

خروجی محاسباتی چقدر قابل اعتماد است؟

می‌توان معیارهای خطا، حساسیت و validation را برای یک مسئله مشخص تعریف کرد.

گفت‌وگو درباره مسئله