سوال ۱۱۳ کنکور ارشد ریاضی ۱۴۰۰

قضیهٔ حاکم: تحلیل خطای پسرو ویلکینسون

حذف گاوسی با محورگیری جزئی (GEPP) تضمین نمی‌کند که جوابی با خطای پیشرو کوچک تولید کند. آنچه تضمین می‌کند — و تمام محتوای تحلیل ویلکینسون همین است — جوابی با خطای پسرو کوچک است.

قضیه (ویلکینسون، ۱۹۶۱). فرض کنید $\bar{x}$ برداری باشد که GEPP در حساب ممیز شناور با واحد گِرد کردن $u$ محاسبه می‌کند. آنگاه اختلالی مانند $\Delta A$ وجود دارد که $(A+\Delta A)\,\bar{x} = b, \qquad \frac{\|\Delta A\|_\infty}{\|A\|_\infty} \;\le\; c(n)\,\rho_n\,u ,$ که در آن $c(n)$ چندجمله‌ای از درجهٔ پایین بر حسب $n$ است و $\rho_n$ عامل رشد حذف گاوسی است (از نظر نظری با $2^{n-1}$ کران‌دار است، اما در عمل مرتبهٔ $O(n^{2/3})$ مشاهده می‌شود).

به بیان دیگر: $\bar{x}$ محاسبه‌شده جواب دقیقِ یک دستگاه مجاور $\bar{A}x=\bar{b}$ با $\bar{A}\approx A$ و $\bar{b}\approx b$ است. این دقیقاً گزینهٔ ۴ است.

چرا باقیمانده خودبه‌خود کوچک است

این را می‌توان بدون هیچ تحلیل ممیز شناوری و کاملاً جبری دید. با داشتن $r=b-A\bar{x}$ و $\bar{x}\neq 0$، قرار دهید $\Delta A \;=\; \frac{r\,\bar{x}^{T}}{\bar{x}^{T}\bar{x}} \quad\Longrightarrow\quad (A+\Delta A)\bar{x} = A\bar{x} + r = b ,$ و $\|\Delta A\|_2 = \dfrac{\|r\|_2}{\|\bar{x}\|_2}$. قضیهٔ ریگال–گاش می‌گوید این انتخاب بهینه است: کوچک‌ترین خطای پسروی نسبی $\bar{x}$ دقیقاً برابر است با $\eta(\bar{x}) \;=\; \min\Big\{\varepsilon : (A+\Delta A)\bar{x}=b,\ \|\Delta A\|\le \varepsilon\|A\|\Big\} \;=\; \frac{\|r\|}{\|A\|\,\|\bar{x}\|}.$ پس پایداری پسرو و کوچک‌بودن باقیماندهٔ نسبی یک حکم واحدند. چون GEPP پسرو-پایدار است، $\|r\|/(\|A\|\|\bar{x}\|)$ از مرتبهٔ $u$ است — باقیمانده همواره به‌طور نسبی کوچک است، چه ماتریس بدوضع باشد چه نباشد.

خطای پیشرو داستان دیگری است

از $A(x-\bar{x}) = r$ نتیجه می‌گیریم $x-\bar{x}=A^{-1}r$، و از این‌رو کران کلاسیک $\frac{\|x-\bar{x}\|}{\|x\|} \;\le\; \kappa(A)\,\frac{\|r\|}{\|A\|\,\|x\|}, \qquad \kappa(A)=\|A\|\,\|A^{-1}\| .$

$\boxed{\text{forward error} \;\lesssim\; \kappa(A)\times\text{backward error}}$

اگر $A$ بدوضع باشد (یعنی $\kappa(A)$ بسیار بزرگ باشد)، باقیماندهٔ ناچیز تقویت می‌شود و ممکن است $\bar{x}$ به‌شدت نادرست باشد.

حذف گزینه‌های انحرافی

پاسخ: گزینهٔ ۴.

نکتهٔ کنکوری: «باقیماندهٔ کوچک» $\neq$ «جواب دقیق». یک حل‌کنندهٔ پسرو-پایدار فقط قول می‌دهد که شما مسئله‌ای مجاور را دقیق حل کرده‌اید؛ تبدیل این به دقتِ پیشرو ضریبی برابر $\kappa(A)$ هزینه دارد. هر گزینهٔ کنکوری که ادعای دقت حتی برای ماتریس بدوضع را داشته باشد، یک تله است.