حساب ممیز شناور، شرطی‌بودن و پایداری عددی

1. دستگاه ممیز شناور چیست

یک ماشین تنها مجموعه‌ای متناهی $\mathbb{F}=\mathbb{F}(\beta,t,L,U)\subset\mathbb{R}$ از اعداد ماشینی را ذخیره می‌کند که به شکل نرمال‌شده نوشته می‌شوند:

$x=\pm\,(0.d_1d_2\cdots d_t)_\beta\times\beta^{e}=\pm\left(\frac{d_1}{\beta}+\frac{d_2}{\beta^{2}}+\cdots+\frac{d_t}{\beta^{t}}\right)\beta^{e},\qquad d_1\neq 0,\quad L\le e\le U,$

با پایهٔ $\beta$، طول مانتیس $t$ و بازهٔ نما $[L,U]$. نرمال‌سازی ($d_1\neq0$) نمایش را یکتا می‌کند. دو قرارداد رایج‌اند — شکل کسری بالا و شکل IEEE یعنی $(d_0.d_1\cdots d_{t-1})_\beta\times\beta^{E}$ با $e=E+1$ — و این دو تنها در یک انتقال نما با هم فرق دارند، هرگز در پاسخ.

تصویر شبکه — تنها تصویری که باید به خاطر بسپارید. نما $e$ را ثابت کنید. وقتی مانتیس روی $(\beta-1)\beta^{t-1}$ مقدار مجاز خود می‌گردد، اعداد ماشینی واقع در $[\beta^{e-1},\beta^{e})$ یک تصاعد حسابی می‌سازند که گام آن یک واحد در آخرین رقم مانتیس است:

$\operatorname{ulp}(x)=\beta^{-t}\cdot\beta^{e}=\beta^{\,e-t}.$

پس $\mathbb{F}$ به‌طور یکنواخت فاصله‌گذاری نشده است: هر بار که از یک توان $\beta$ عبور می‌کنید، گام در $\beta$ ضرب می‌شود. آنچه (تقریباً) ثابت می‌ماند فاصلهٔ نسبی است، $\operatorname{ulp}(x)/\lvert x\rvert\in(\beta^{-t},\,\beta^{1-t}]$. بیرون از $[\beta^{L-1},(1-\beta^{-t})\beta^{U}]$ با زیرریزی / سرریز روبه‌رو می‌شوید (استاندارد IEEE انتهای پایین را با اعداد زیرنرمال $\pm(0.d_1\cdots d_t)_\beta\beta^{L}$ ملایم می‌کند: با فاصله‌گذاری یکنواخت و دقتی که پیوسته کمتر می‌شود).

1a. فرمولی مستقل از قرارداد برای فاصله

چون دو قرارداد، $e$ و $t$ را هم‌زمان یک واحد جابه‌جا می‌کنند، بهتر است فاصله را به شکلی به یاد بسپاریم که به هیچ‌یک اشاره نکند. فرض کنید $t$ تعداد ارقام بامعنای واقعاً ذخیره‌شده باشد و $x$ در باینِد $[\beta^{k},\beta^{k+1})$ قرار گیرد، یعنی $k=\lfloor\log_\beta\lvert x\rvert\rfloor$. آنگاه

$\boxed{\ \operatorname{ulp}(x)=\beta^{\,1-t}\cdot\beta^{\,\lfloor\log_\beta\lvert x\rvert\rfloor}=\varepsilon_{\text{mach}}\,\beta^{k}\ }$

وارسی درستی: در $x=1$ به $\beta^{1-t}=\varepsilon_{\text{mach}}$ می‌رسیم، یعنی فاصلهٔ $1$ تا عدد ماشینی بعد از آن — که دقیقاً تعریف اپسیلون ماشین است. هر چیز دیگری همین فرمول است که در $\beta^{k}$ مقیاس شده باشد.

1b. شبکه در هر توان پایه نامتقارن است

در مرز دو باینِد فاصله جهش می‌کند، پس شکاف رو به بالا و شکاف رو به پایین یکسان نیستند:

به‌طور مشخص با $\beta=2$ و $t=3$ بیت بامعنا، اعداد ماشینی پیرامون $8=2^{3}$ چنین‌اند:

$\dots,\ 4,\ 5,\ 6,\ 7,\ \mathbf{8},\ 10,\ 12,\ 14,\ 16,\ 20,\dots$

با فاصلهٔ $1$ روی $[4,8)$ و فاصلهٔ $2$ روی $[8,16)$. پرسشی که همسایهٔ بزرگ‌تر از یک توان پایه را می‌خواهد و پرسشی که همسایهٔ کوچک‌تر را می‌خواهد، پاسخ‌هایی دارند که دقیقاً به ضریب $\beta$ تفاوت می‌کنند — و هر دو عدد همیشه در میان چهار گزینه حاضرند.

1c. دستگاه چند عدد دارد

اندازهٔ $\mathbb{F}$ یک قاعدهٔ ضرب خالص است: انتخاب‌های مستقل را بشمارید، سپس تنها مقداری را که نرمال‌سازی نمی‌تواند بیان کند وصله بزنید.

$\boxed{\ \lvert\mathbb{F}\rvert=2(\beta-1)\beta^{\,t-1}(U-L+1)+1\ }$

خواندن ساختاری این تجزیه ارزش دارد: $(\beta-1)\beta^{t-1}$ تعداد مانتیس‌های مجاز است (هم‌ارز با تعداد اعداد ماشینی درون یک باینِد)، $U-L+1$ تعداد باینِدها است، و ضریب پیشروی $2$ همه‌چیز را نسبت به مبدأ آینه می‌کند. متمایز بودن خودبه‌خود برقرار است، زیرا نمایش‌های نرمال‌شده یکتایند.

عبارت‌بندی پرسش تعیین می‌کند کدام تکه‌ها را نگه دارید:

(شمارِ زیرنرمال‌ها یعنی $\beta^{\,t-1}-1$، تعداد مانتیس‌های $0.0d_2\cdots d_t$ است که همگی صفر نیستند و همه با همان تک‌نمای $L$ حمل می‌شوند.)

شمارش نما لغزش حسابی کلاسیک است: $-4\le e\le 4$ شامل $9$ عدد صحیح است، نه $8$، و $L\le e\le U$ شامل $U-L+1$ است، نه $U-L$. فراموش کردن $+1$ مربوط به صفر، یا ضریب $2$ مربوط به علامت، دو گزینهٔ انحرافی دیگر را می‌سازد.

2. گرد کردن، قطع کردن و واحد گردکردن

نگاشت $\operatorname{fl}:\mathbb{R}\to\mathbb{F}$ یک عدد حقیقی را به یک عدد ماشینی می‌برد، یا با گرد کردن به نزدیک‌ترین نقطهٔ شبکه یا با قطع کردن (دور ریختن همهٔ ارقام پس از $d_t$). در هر دو حالت

$\operatorname{fl}(x)=x(1+\delta),\qquad \lvert\delta\rvert\le u=\begin{cases}\tfrac{1}{2}\beta^{1-t}, & \text{round to nearest},\\ \beta^{1-t}, & \text{chopping (truncation)}.\end{cases}$

عدد $u$ واحد گردکردن است؛ و $\varepsilon_{\text{mach}}=\beta^{1-t}$ اپسیلون ماشین است، یعنی فاصلهٔ $1$ تا عدد ماشینی بعدی (در واقع $1=(0.10\cdots0)_\beta\times\beta^{1}$ در نمای $e=1$ می‌نشیند، پس ulp آن $\beta^{\,1-t}$ است). به‌طور مطلق $\lvert\operatorname{fl}(x)-x\rvert\le\tfrac12\beta^{\,e-t}$ (گرد کردن) و $<\beta^{\,e-t}$ (قطع کردن)؛ قطع کردن به سمت صفر اریب است و گرد کردن متقارن است. دقت مضاعف IEEE: $\beta=2$، $t=53$، $\varepsilon_{\text{mach}}=2^{-52}\approx2.2\times10^{-16}$.

شیوهٔ گرد کردن خطا را تغییر می‌دهد، نه شبکه را. قطع کردن، گرد کردن به نزدیک‌ترین، و گرد کردن به نزدیک‌ترینِ زوج همگی به همان مجموعهٔ $\mathbb{F}$ می‌نگارند، مجموعه‌ای که تنها با $(\beta,t,L,U)$ تعیین می‌شود. پس هر پرسشی دربارهٔ جای اعداد قابل نمایش — فاصله، عدد بعدی، عدد قبلی، تعدادشان — کاملاً نسبت به واژه‌های «گرد کردن / قطع کردن» بی‌اثر است؛ این واژه‌ها فقط بر اندازهٔ $\lvert\operatorname{fl}(x)-x\rvert$ اثر دارند.

2a. سه کمیت که همه «اپسیلون» نامیده می‌شوند — آن‌ها را جدا نگه دارید

چرا سطر آخر به ضریب $2$ فرق می‌کند: در قطع کردن، هر عدد حقیقی در $[1,\,1+\beta^{1-t})$ به $1$ بریده می‌شود، پس چیزی کمتر از یک ulp کامل نمی‌تواند مقدار ذخیره‌شده را تکان دهد — از این رو $\beta^{1-t}$. در گرد کردن به نزدیک‌ترین، نقطهٔ میانی $1+\tfrac12\beta^{1-t}$ همین حالا به بالا گرد می‌شود، پس نصف یک ulp کافی است (با قاعدهٔ تساوی‌به‌زوج، کمی بیش از نصف لازم است). بنابراین عبارت فارسی «روند عدد یک» در دستگاهی با قطع کردن، $\beta^{1-t}$ را می‌خواهد و مقدار گرد کردن یعنی $\tfrac12\beta^{1-t}$ دقیقاً همان گزینهٔ انحرافیِ ضریب $2$ است که کنارش گذاشته‌اند.

مدل استاندارد حساب. برای $\ast\in\{+,-,\times,\div\}$ داریم $\operatorname{fl}(x\ast y)=(x\ast y)(1+\delta)$ با $\lvert\delta\rvert\le u$: هر عمل مقدماتی روی داده‌ای اندکی آشفته دقیق است. همین یک سطر بذر تمام تحلیل خطای پسرو است.

لم اشترنبنز. اگر $\tfrac12 y\le x\le 2y$ آنگاه $x-y$ در حساب ممیز شناور دقیقاً محاسبه می‌شود. درست بخوانیدش: حذف تفاضلی خطای گردکردن نمی‌سازد — بلکه خطایی را که $x$ و $y$ از پیش با خود داشتند آشکار می‌کند، چون نتیجه را کوچک می‌کند در حالی که خطای مطلق ثابت می‌ماند.

3. خطاها و «ارقام درست»

برای تقریب $\bar x$ از $x\neq0$: خطای مطلق $\lvert\bar x-x\rvert$، خطای نسبی $\varepsilon=\lvert\bar x-x\rvert/\lvert x\rvert$. به‌طور دقیق، $\bar x$ دارای $k$ رقم بامعنای درست در مبنای ده است هرگاه $\varepsilon\le\tfrac12\times10^{1-k}$؛ فرهنگ واژگانِ به‌درد‌بخور در کنکور این است:

$k\ \text{reliable decimal digits}\iff\varepsilon\approx10^{-k}\iff k\approx-\log_{10}\varepsilon .$

چون ارقام همان $-\log_{10}$ خطای نسبی‌اند، هر ضریب تقویت ضربی به یک تفریق از ارقام تبدیل می‌شود. تمام ترفند §5 همین است.

4. خطا چگونه در یک محاسبه منتشر می‌شود

انتشار مرتبهٔ اول (دیفرانسیلی) برای $y=f(x_1,\dots,x_n)$:

$\Delta y\approx\sum_{i}\frac{\partial f}{\partial x_i}\,\Delta x_i,\qquad \frac{\Delta y}{y}\approx\sum_i\underbrace{\frac{x_i}{f}\frac{\partial f}{\partial x_i}}_{\text{condition numbers}}\frac{\Delta x_i}{x_i},$

و برای یک متغیر، عدد شرطی مسئلهٔ $x\mapsto f(x)$ برابر است با $\kappa_f(x)=\left\lvert\dfrac{x\,f'(x)}{f(x)}\right\rvert$.

حذف تفاضلی تنها راهی است که یک فرمول به‌ظاهر بی‌آزار ارقام را نابود می‌کند، و درمانش بازنویسی عبارت است، نه بالا بردن دقت محاسبه:

$\sqrt{x+1}-\sqrt{x}=\frac{1}{\sqrt{x+1}+\sqrt{x}},\qquad 1-\cos x=2\sin^{2}\!\frac{x}{2},$

و برای $ax^{2}+bx+c$ ریشهٔ با قدرمطلق بزرگ‌تر را از فرمول معمول بگیرید و دیگری را از $x_1x_2=c/a$ به دست آورید.

انباشت در طول عمل‌های بسیار. جمع کردن $n$ عدد ماشینی به ترتیب، کران $\lvert\hat s-s\rvert\lesssim (n-1)u\sum_i\lvert x_i\rvert$ را می‌دهد: خطای گردکردن (در بدترین حالت) به‌طور خطی با تعداد عمل‌ها رشد می‌کند، پس یک الگوریتم $O(n^{3})$ بدترین حالت $O(n^{3}u)$ دارد — که در عمل معمولاً $O(\sqrt{n}\,u)$ است، زیرا $\delta_i$ ها مانند علامت‌های تصادفی مستقل رفتار می‌کنند. جمع کردن از کوچک‌ترین به بزرگ‌ترین، یا جمع جبرانی (کاهان)، بیشتر آن را از میان برمی‌دارد.

خطای برشی در برابر خطای گردکردن — بده‌بستان دوسویه. روش‌های گسسته‌سازی یک خطای روش دارند که با گام $h$ کوچک می‌شود و یک خطای گردکردن که با $h\to0$ بزرگ می‌شود. برای تفاضل پیشرو $\dfrac{f(x+h)-f(x)}{h}$،

$E(h)\ \lesssim\ \underbrace{\tfrac{h}{2}\lvert f''\rvert}_{\text{truncation}}+\underbrace{\frac{2u\lvert f\rvert}{h}}_{\text{roundoff}},\qquad h_{\text{opt}}\sim\sqrt{u},\quad E_{\min}\sim\sqrt{u},$

در حالی که تفاضل مرکزی $h_{\text{opt}}\sim u^{1/3}$ و $E_{\min}\sim u^{2/3}$ می‌دهد. کوچک‌تر کردن پیوستهٔ $h$ سرانجام پاسخ را بدتر می‌کند — همان منحنی خطای V-شکل کلاسیک.

5. شرطی‌بودن دستگاه خطی $Ax=b$

برای $A$ ناتکین و یک نُرم ماتریسی القایی، عدد شرطی چنین است:

$\kappa(A)=\lVert A\rVert\,\lVert A^{-1}\rVert\ \ge\ \lVert AA^{-1}\rVert=1,\qquad \kappa(A)=\infty\ \text{for singular }A.$

قضیهٔ اختلال. اگر $A$ ناتکین باشد، $\lVert A^{-1}\rVert\,\lVert\delta A\rVert<1$ و $(A+\delta A)(x+\delta x)=b+\delta b$، آنگاه

$\frac{\lVert\delta x\rVert}{\lVert x\rVert}\ \le\ \frac{\kappa(A)}{1-\kappa(A)\frac{\lVert\delta A\rVert}{\lVert A\rVert}}\left(\frac{\lVert\delta A\rVert}{\lVert A\rVert}+\frac{\lVert\delta b\rVert}{\lVert b\rVert}\right)\ \approx\ \kappa(A)\left(\frac{\lVert\delta A\rVert}{\lVert A\rVert}+\frac{\lVert\delta b\rVert}{\lVert b\rVert}\right).$

این کران برای اختلال‌های مناسب حاصل می‌شود، پس $\kappa(A)$ دقیقاً ضریب تقویت در بدترین حالت، از خطای نسبی داده به خطای نسبی جواب است. (حالت خاص $\delta A=0$ می‌شود $\lVert\delta x\rVert/\lVert x\rVert\le\kappa(A)\lVert\delta b\rVert/\lVert b\rVert$.)

مانده در برابر خطا (تلهٔ صحیح/غلط محبوب). با $r=b-A\hat{x}$،

$\frac{1}{\kappa(A)}\,\frac{\lVert r\rVert}{\lVert b\rVert}\ \le\ \frac{\lVert\hat{x}-x\rVert}{\lVert x\rVert}\ \le\ \kappa(A)\,\frac{\lVert r\rVert}{\lVert b\rVert}.$

مانده‌ای بسیار کوچک وقتی $\kappa$ بزرگ است گواه دقیق بودن جواب نیست — تنها گواه پایداری پسرو است.

قاعدهٔ سرانگشتی از دست رفتن ارقام. دو منبع خطای مستقل به حل‌کننده خوراک می‌دهند — دادهٔ $(A,b)$ که تا دقتی متناهی معلوم است، و حسابِ ماشین که تا $u$ دقیق است — و بدترینشان حاکم است:

$\text{digits}(\bar x)\ \approx\ \min\Big\{\underbrace{-\log_{10}\varepsilon_{\text{data}}}_{\text{digits in the data}},\ \underbrace{-\log_{10}u}_{\text{digits of the machine}}\Big\}\;-\;\log_{10}\kappa(A).$

هم‌ارز، در یک خط حساب: $\varepsilon_{\text{eff}}=\max\{\varepsilon_{\text{data}},u\}$، سپس $\lVert\bar x-x\rVert/\lVert x\rVert\lesssim\kappa(A)\,\varepsilon_{\text{eff}}$، سپس $-\log_{10}$ بگیرید. به بیان ساده: یک دستگاه بدوضع $\log_{10}\kappa(A)$ رقم اعشاری از شما می‌گیرد، و هیچ الگوریتمی نمی‌تواند دقتی را که داده هرگز نداشته بازگرداند. این قاعده یک کران بالا برای دقت دست‌یافتنی است — صورت‌مسئله‌های کنکور دقیقاً به همین دلیل «حداکثر» می‌گویند.

نُرم‌هایی که باید بتوانید دستی حساب کنید.

برای ماتریس‌های $2\times2$، $A^{-1}=\dfrac{1}{\det A}\begin{pmatrix} d & -b\\ -c & a\end{pmatrix}$ — و کنکور هرگز بیش از این وارون‌گیری نمی‌خواهد. همچنین $\kappa_1(A)=\kappa_\infty(A^{\mathsf{T}})$، و هر سه عدد شرطی تا ضرایبی از مرتبهٔ $n$ هم‌ارزند، پس «بزرگ» یعنی بزرگ در هر نُرم.

خواصی که ارزش حفظ کردن دارند.

• $\kappa(\alpha A)=\kappa(A)$: مقیاس کردن کل ماتریس هرگز کمکی نمی‌کند.
• $\kappa(A^{-1})=\kappa(A)$ و $\kappa(AB)\le\kappa(A)\kappa(B)$.
• $\kappa_2(Q)=1$ برای $Q$ متعامد — تبدیل‌های متعامد رایج‌ترین سرمایهٔ الگوریتم‌های پایدارند، و $\kappa_2(QAZ)=\kappa_2(A)$ برای $Q,Z$ متعامد.
• اگر $A$ متقارن (به‌طور کلی‌تر، نرمال) باشد، $\kappa_2(A)=\lvert\lambda\rvert_{\max}/\lvert\lambda\rvert_{\min}$. برای $A$ عمومی باید از مقادیر تکین استفاده کنید، نه مقادیر ویژه.
• $\kappa_2(A^{\mathsf{T}}A)=\kappa_2(A)^{2}$ — معادلات نرمال شرطی‌بودن را به توان دو می‌رسانند؛ کمترین مربعات را به‌جای آن با تجزیهٔ QR حل کنید.
• معنای هندسی: $\min\{\lVert\Delta A\rVert_2/\lVert A\rVert_2:\ A+\Delta A\ \text{singular}\}=1/\kappa_2(A)$، پس «بدوضع» یعنی «نسبتاً نزدیک به تکین».
• کوچک بودن $\lvert\det A\rvert$ به معنای بدوضع بودن نیست ($\tfrac{1}{100}I_2$ $\det=10^{-4}$ و $\kappa=1$ دارد)، و بزرگ بودنش هم به معنای خوش‌وضع بودن نیست. خانواده‌های بدوضع نامدار: ماتریس هیلبرت $h_{ij}=1/(i+j-1)$ که $\kappa_2(H_n)$ آن مانند $e^{3.5n}$ رشد می‌کند، و ماتریس‌های واندرموند روی گره‌های نزدیک به هم.

5a. خواندن $\kappa_2$ مستقیماً از روی یک تجزیه

اگر $A=USV^{\mathsf{T}}$ با $U,V$ متعامد و $S=\operatorname{diag}(s_1,\dots,s_n)$، $s_i>0$، آنگاه این یک SVD است (جابه‌جا کردن ستون‌ها مجموعهٔ قطری را تغییر نمی‌دهد): از $A^{\mathsf{T}}A=VS^{2}V^{\mathsf{T}}$ مقادیر ویژهٔ $A^{\mathsf{T}}A$ برابر $s_i^{2}$ اند، پس $\sigma_i(A)=s_i$ و

$\kappa_2(A)=\frac{\max_i s_i}{\min_i s_i}.$

دلیل بی‌نیازی از هرگونه محاسبه این است که نُرم $2$ نمی‌تواند $U$ یا $V$ را ببیند: ماتریس‌های متعامد طول اقلیدسی را حفظ می‌کنند، پس $\lVert A\rVert_2=\lVert S\rVert_2=\sigma_{\max}$، و چون $A^{-1}=VS^{-1}U^{\mathsf{T}}$ باز هم همان شکل را دارد، $\lVert A^{-1}\rVert_2=\lVert S^{-1}\rVert_2=1/\sigma_{\min}$.

سه کمیت دیگر از همان فهرست خوانده می‌شوند و گزینه‌های انحرافی استانداردند: $\lvert\det A\rvert=\prod_i s_i$، $\lVert A\rVert_F=(\sum_i s_i^{2})^{1/2}$، و $\lambda_{\max}(A^{\mathsf{T}}A)/\lambda_{\min}(A^{\mathsf{T}}A)=\kappa_2(A)^{2}$ — هرگز خودِ $\kappa_2$. و چون همیشه $\kappa_2\ge1$، هر گزینهٔ کوچک‌تر از $1$ را می‌توان در نگاه اول خط زد.

6. شرطی‌بودن (مسئله) در برابر پایداری (الگوریتم)

این‌ها دو چیز متفاوت‌اند و کنکور عاشق مخلوط کردنشان است.

• شرطی‌بودن خاصیت مسئله است — خاصیت نگاشت داده $\mapsto$ جواب. کدنویسی بهتر آن را بهبود نمی‌دهد.
• پایداری خاصیت الگوریتم است. یک الگوریتم پایدارِ پسرو است هرگاه $\hat y$ محاسبه‌شده پاسخ دقیق برای دادهٔ اندکی آشفتهٔ $\tilde x$ باشد، با $\lVert\tilde x-x\rVert/\lVert x\rVert=O(u)$.
• نامساوی اصلی که این دو را به هم گره می‌زند:

$\underbrace{\text{forward relative error}}_{\text{what you observe}}\ \lesssim\ \underbrace{\kappa(\text{problem})}_{\text{conditioning}}\times\underbrace{\text{backward error}}_{\text{stability}}\ \approx\ \kappa\,u.$

نمونه‌های شاخص: حذف گاوسی بدون محورگیری ناپایدار است (محوری بسیار کوچک ضریب رشد $\rho$ را منفجر می‌کند؛ محورگیری جزئی ضریب‌ها را با $1$ کران‌دار می‌کند و در عمل آن را پایدار می‌سازد)؛ تجزیهٔ QR به روش هاوس‌هولدر و گیونز پایدارِ پسرو است؛ گرام–اشمیت کلاسیک تعامد را از دست می‌دهد (نسخهٔ اصلاح‌شده را به کار ببرید)؛ و بازیابی ریشه‌های چندجمله‌ای از روی ضرایب ذاتاً بدوضع است — برای ریشهٔ سادهٔ $r$ از $p$، اختلال ضریبیِ $\delta p$ آن را به اندازهٔ $\delta r\approx-\delta p(r)/p'(r)$ جابه‌جا می‌کند، همان فاجعهٔ چندجمله‌ای ویلکینسون. همتای این مطلب برای مقادیر ویژه قضیهٔ باوئر–فایک است: برای $A=X\Lambda X^{-1}$ قطری‌پذیر، هر مقدار ویژهٔ $A+E$ در فاصلهٔ $\kappa_2(X)\lVert E\rVert_2$ از طیف $A$ قرار می‌گیرد، پس شرطی‌بودن ماتریس بردارهای ویژه حاکم است (ماتریس‌های متقارن $\kappa_2(X)=1$ دارند: مقادیر ویژه‌شان کاملاً خوش‌وضع‌اند).

6a. یک حل‌کنندهٔ خطی واقعاً چه قولی می‌دهد (تحلیل پسروی ویلکینسون)

قضیه (ویلکینسون). فرض کنید $\bar x$ از $Ax=b$ با حذف گاوسی و محورگیری جزئی (سطری)، در حساب ممیز شناور با واحد گردکردن $u$ محاسبه شده باشد. آنگاه اختلالی مانند $\Delta A$ وجود دارد با $(A+\Delta A)\,\bar x=b,\qquad \frac{\lVert\Delta A\rVert_\infty}{\lVert A\rVert_\infty}\ \le\ c(n)\,\rho_n\,u,$ که در آن $c(n)$ چندجمله‌ای با درجهٔ پایین برحسب $n$ است و $\rho_n=\dfrac{\max_{i,j,k}\lvert a^{(k)}_{ij}\rvert}{\max_{i,j}\lvert a_{ij}\rvert}$ ضریب رشد حذف است.

به بیان ساده: بردار محاسبه‌شده جواب دقیق یک دستگاه مجاور است. تمام تضمین همین است — دربارهٔ $\bar x-x$ مطلقاً هیچ ادعایی نمی‌شود.

• محورگیری جزئی هر ضریب را وادار می‌کند در $\lvert m_{ik}\rvert\le1$ صدق کند، از این رو $\rho_n\le2^{\,n-1}$؛ این کران تنها با ماتریس‌های ساختگی (نمونهٔ ویلکینسون) حاصل می‌شود و در عمل $\rho_n$ مانند $O(n^{2/3})$ رفتار می‌کند. پس GEPP برای همهٔ مقاصد عملی پایدارِ پسرو است.
• محورگیری کامل کران رشد به‌مراتب کوچک‌تری دارد اما $O(n^{3})$ مقایسهٔ اضافی هزینه می‌برد؛ بدون هیچ محورگیری اصلاً کرانی وجود ندارد (محوری به اندازهٔ $u$ همه‌چیز را خراب می‌کند). ماتریس‌های متقارن معین مثبت و ماتریس‌های اکیداً قطری‌غالب به محورگیری نیاز ندارند: تجزیهٔ چولسکی به‌طور نامشروط پایدارِ پسرو است.

مانده به‌رایگان کوچک است — و این یک قضیه است، نه شانس. برای هر $\bar x\neq0$ با ماندهٔ $r=b-A\bar x$، قرار دهید

$\Delta A=\frac{r\,\bar x^{\mathsf{T}}}{\bar x^{\mathsf{T}}\bar x}\quad\Longrightarrow\quad (A+\Delta A)\bar x=A\bar x+r=b,\qquad \lVert\Delta A\rVert_2=\frac{\lVert r\rVert_2}{\lVert\bar x\rVert_2}.$

قضیهٔ ریگال–گاش می‌گوید این اختلال رتبه‌یک بهینه است: کوچک‌ترین خطای پسروی نسبی $\bar x$ دقیقاً برابر است با

$\eta(\bar x)=\min\big\{\varepsilon:\ (A+\Delta A)\bar x=b,\ \lVert\Delta A\rVert\le\varepsilon\lVert A\rVert\big\}=\frac{\lVert r\rVert}{\lVert A\rVert\,\lVert\bar x\rVert}.$

پس «پایدارِ پسرو» و «ماندهٔ نسبی کوچک» عیناً یک گزاره‌اند، و خطای پیشرو از $x-\bar x=A^{-1}r$ نتیجه می‌شود:

$\frac{\lVert x-\bar x\rVert}{\lVert x\rVert}\ \le\ \kappa(A)\,\frac{\lVert r\rVert}{\lVert A\rVert\,\lVert x\rVert}\ \approx\ \kappa(A)\,\eta(\bar x)\ \approx\ \kappa(A)\,c(n)\rho_n u .$

پرسش چهارگزینه‌ایِ مفهومی همیشه زیرمجموعه‌ای از این پنج ادعاست:

وقتی خطای پیشرو اهمیت دارد، درمان‌ها این‌هاست: پالایش تکراری (مانده $r=b-A\bar x$ را با دقت بالاتر بسازید، $Ad=r$ را با همان عوامل $LU$ که دارید حل کنید و $\bar x\leftarrow\bar x+d$ بگذارید — تا وقتی $\kappa(A)u<1$ باشد دقت کامل را بازمی‌گرداند)، متعادل‌سازی/مقیاس‌بندی سطرها و ستون‌ها، و بازفرمول‌بندی مسئله به‌گونه‌ای که خودِ $\kappa$ کاهش یابد (QR به‌جای معادلات نرمال).

7. مثال‌های کوچک حل‌شده

(الف) فاصله تا عدد قابل نمایش بعدی. بگیرید $\beta=8$، $t=3$، $x=7$. نخست نرمال کنید: $7=(0.700)_8\times8^{1}$، پس $7\in\mathbb{F}$ با $e=1$. آخرین رقم مانتیس را یک واحد بالا ببرید:

$x^{+}=(0.701)_8\times8^{1}=7+\frac{8}{8^{3}}=7+\frac{1}{64},\qquad x^{+}-x=\beta^{\,e-t}=8^{\,1-3}=\frac{1}{64}.$

دستور کار هرگز تغییر نمی‌کند: نرمال کن، $e$ را بخوان، پاسخ $\beta^{\,e-t}$ است. توجه کنید که $\beta^{-t}=8^{-3}$ به‌تنهایی نادرست است — باید در $\beta^{e}$ مقیاس شود — و اینکه گرد کردن یا قطع کردن هیچ نقشی ندارد.

(ب) $\kappa$ و ارقامی که نابود می‌کند. برای $A=\begin{pmatrix}1 & 1\\ 1 & 1{.}0001\end{pmatrix}$ داریم $\det A=10^{-4}$ و $A^{-1}=\begin{pmatrix}10001 & -10000\\ -10000 & 10000\end{pmatrix}$، از این رو $\lVert A\rVert_\infty=2{.}0001$، $\lVert A^{-1}\rVert_\infty=20001$ و $\kappa_\infty(A)\approx4\times10^{4}$. با داده‌ای که تا $8$ رقم درست است روی ماشینی با $10$ رقم،

$\text{digits}(\bar x)\approx\min\{8,10\}-\log_{10}(4\times10^{4})\approx8-4{.}6\approx3,$

هرقدر هم که حل‌کننده خوب باشد. با اعداد گردی که کنکور می‌پسندد ($\kappa=10^{3}$، دادهٔ $8$ رقمی، ماشین $10$ رقمی) همین دستور کار $\min\{8-3,\;10-3\}=5$ رقم قابل اعتماد می‌دهد — شاخهٔ داده برنده می‌شود، که دقیقاً همان نکتهٔ مورد آزمون است.

(ج) خواندن $\kappa_2$ از روی یک تجزیه. اگر $A=USV^{\mathsf{T}}$ با $U,V$ متعامد و $S=\operatorname{diag}(s_1,\dots,s_n)$، آنگاه $s_i$ ها همان مقادیر تکین‌اند (عوامل متعامد در نُرم $2$ تساوی‌سنج‌اند: $\lVert A\rVert_2=\lVert S\rVert_2$ و $\lVert A^{-1}\rVert_2=\lVert S^{-1}\rVert_2$)، پس

$\kappa_2(A)=\frac{\max_i\lvert s_i\rvert}{\min_i\lvert s_i\rvert}.$

وقتی $s_i$ ها با قاعده‌ای وابسته به اندیس داده می‌شوند (مثلاً $s_i=i$ برای $i$ زوج و $s_i=1/i$ برای $i$ فرد)، تمام تمرین یافتن عضو حدی هر خانواده است — مراقب قیدهای زوجیت و بازهٔ $n$ باشید، چون گزینه‌های انحرافی دقیقاً از همان‌جا ساخته می‌شوند.

(د) همان مسئله با یک قاعدهٔ یکنوا. فرض کنید $S_{ii}=\sqrt{i}$ برای $i=1,\dots,n$. چون $i\mapsto\sqrt{i}$ صعودی است، $\sigma_{\max}=\sqrt{n}$ و $\sigma_{\min}=\sqrt{1}=1$، پس

$\kappa_2(A)=\frac{\sqrt{n}}{1}=\sqrt{n}.$

همسایه‌هایی را که گزینه‌ها پیشنهاد می‌کنند مقایسه کنید: $\prod_i\sqrt{i}=\sqrt{n!}=\lvert\det A\rvert$، $\big(\sum_i i\big)^{1/2}=\sqrt{n(n+1)/2}=\lVert A\rVert_F$، و $n=\kappa_2^{2}=\lambda_{\max}(A^{\mathsf{T}}A)/\lambda_{\min}(A^{\mathsf{T}}A)$. تنها نسبت مقادیر تکین برابر $\kappa_2$ است. (قاعدهٔ یکنوا مسئله را یک‌خطی می‌کند؛ قاعدهٔ نایکنوا آن را به جست‌وجوی دوخطی برای یافتن حدها تبدیل می‌کند — تنها تفاوت نسخهٔ آسان و متوسط این الگو همین است.)

تمام خانوادهٔ قاعده‌های توانی یک‌جا فرومی‌ریزد: اگر $s_{ii}=i^{\,p}$ با $p>0$ باشد آنگاه $\sigma_{\max}=n^{p}$، $\sigma_{\min}=1$ و

$\kappa_2(A)=n^{\,p}\qquad\big(s_{ii}=\sqrt{i}\Rightarrow\sqrt{n},\quad s_{ii}=i\Rightarrow n,\quad s_{ii}=i^{2}\Rightarrow n^{2}\big),$

و اگر $p<0$ باشد فهرست صرفاً نزولی می‌شود و باز هم $\kappa_2=n^{\lvert p\rvert}$ می‌دهد — هرگز مقداری کمتر از $1$. دو گزینه از چهار گزینه همیشه توان‌های همسایه‌اند ($n$ در برابر $n^{2}$)، یکی وارونِ $n^{-p}$ است که $\kappa_2\ge1$ فوراً آن را حذف می‌کند، و یکی همان $1$ خشک‌وخالی است (واکنش غریزی «عوامل متعامدند، پس کاملاً خوش‌وضع است»، که تنها وقتی همهٔ $s_i$ ها برابر باشند درست است).

(ه) شکافی در یک توان پایه. پایهٔ $\beta=2$ با $t=3$ بیت بامعنا، در $x=8$. اینجا $8=2^{3}=(1.00)_2\times2^{3}$، پس $k=\lfloor\log_2 8\rfloor=3$ و

$\operatorname{ulp}(8)=2^{1-3}\cdot2^{3}=2^{1}=2,$

و عدد بعدی $(1.01)_2\times2^{3}=(1+\tfrac14)\cdot8=10$ است. در قرارداد کسری همین محاسبه چنین خوانده می‌شود: $8=(0.100)_2\times2^{4}$، $e=4$، $\beta^{\,e-t}=2^{4-3}=2$ — یکسان، همان‌طور که قول داده شد. عدد قبلی یک باینِد پایین‌تر زندگی می‌کند، جایی که فاصله $2^{1-3}\cdot2^{2}=1$ است، پس برابر $7$ می‌شود: شکاف بالا دو برابر شکاف پایین است.

(و) ارقامی که از یک $\kappa$ بزرگ جان به در می‌برند. دادهٔ دقیق تا $8$ رقم اعشاری، ماشینی که $16$ رقم اعشاری حمل می‌کند، $\kappa(A)=10^{5}$. آنگاه $\varepsilon_{\text{eff}}=\max\{10^{-8},10^{-16}\}=10^{-8}$، خطای جواب $\lesssim10^{5}\cdot10^{-8}=10^{-3}$ است، یعنی حدود $3$ رقم قابل اعتماد $=8-5$. سه پاسخ نادرست خودشان را می‌نویسند: $16$ (طول کلمهٔ ماشین، با نادیده گرفتن شرطی‌بودن)، $8$ (دقت داده، با نادیده گرفتن شرطی‌بودن)، و $16-5=11$ (اعمال قاعده روی دقت ماشین به‌جای دادهٔ درشت‌تر). همیشه بدترینِ این دو دقت را کاهش دهید.

همین الگو با دادهٔ $10$ رقمی، ماشین $15$ رقمی و $\kappa(A)=10^{4}$ به $\min\{10,15\}-4=6$ می‌رسد، در حالی که $15$، $11=15-4$ و یک $7$ با خطای یک‌واحدی کنارش در فهرست گزینه‌ها نشسته‌اند. همان سه تله، با اعداد دیگر — شکل را بشناسید، نه ارقام را.

(ز) اندازه و تفکیک‌پذیری یک دستگاه کامل. فرض کنید $\mathbb{F}$ از اعداد $\pm(0.d_1d_2d_3)_5\times5^{e}$ با $-4\le e\le4$ و با قطع کردن تشکیل شده باشد. آنگاه $\beta=5$، $t=3$، $L=-4$، $U=4$، و

$\lvert\mathbb{F}\rvert=\underbrace{2}_{\text{sign}}\cdot\underbrace{4}_{d_1\neq0}\cdot\underbrace{5^{2}}_{d_2,d_3}\cdot\underbrace{9}_{-4\le e\le 4}+\underbrace{1}_{\text{zero}}=1800+1=1801 .$

و برای تفکیک‌پذیری در $1$: در مبنای $5$ داریم $1=(0.100)_5\times5^{1}$، و عدد بعدی $(0.101)_5\times5^{1}=1+\tfrac{5}{125}=1{.}04$ است، پس $\varepsilon_{\text{mach}}=\operatorname{ulp}(1)=5^{\,1-3}=\tfrac1{25}=0{.}04$. با قطع کردن، هر عددی در $[1,\,1{.}04)$ به $1$ بریده می‌شود، پس واحد گردکردنِ عدد یک همان $0{.}04$ کامل است؛ با گرد کردن نصف آن، یعنی $0{.}02$، می‌شد. پاسخ‌های نادرست ساخته‌شده دقیقاً $1601$ (هشت نما به‌جای نُه) و $0{.}02$ (واحد گرد کردن که در دستگاهی با قطع کردن نقل شده) هستند.

(ح) خواندن یک پرسش مفهومی دربارهٔ پایداری. با داشتن تنها «$Ax=b$ که با حذف گاوسی و محورگیری جزئی حل شده، ماندهٔ $r=b-A\bar x$»، تنها گزارهٔ درست بدون فرض‌های اضافی این است که $\bar x$ دقیقاً دستگاه آشفتهٔ $\bar A x=\bar b$ را با $\bar A$ نزدیک $A$ و $\bar b$ نزدیک $b$ حل می‌کند — یا هم‌ارز، اینکه $\lVert r\rVert$ به‌طور نسبی کوچک است. هر گزینه‌ای که چیزی دربارهٔ خطای پیشرو ادعا کند (اینکه $\bar x$ دقیق است، اینکه $\bar x$ به‌شدت غلط است، اینکه مانده بزرگ است) یا نادرست است یا صرفاً ممکن، زیرا تصمیم‌گیری دربارهٔ آن به $\kappa(A)$ نیاز دارد که صورت‌مسئله هرگز نمی‌دهد. وقتی صورت‌مسئله $\kappa$ را نمی‌دهد، پاسخ نمی‌تواند به آن وابسته باشد.

8. کنکور این مبحث را چگونه می‌آزماید

چهار گزینه تقریباً همیشه همان کمیت‌اند با یک گام خراب‌شده: حذف مقیاس نما ($\beta^{-t}$ به‌جای $\beta^{\,e-t}$)، گرفتن شکاف از سمت اشتباه یک توان $\beta$، اشتباه گرفتن شیوهٔ گرد کردن، شمارش بازهٔ نما با خطای یک واحد، کمینه نگرفتن دو شمارِ ارقام، یا جابه‌جا کردن $\sigma_{\min}$ و $\sigma_{\max}$ (یا ضرب کردن به‌جای تقسیم).

نکتهٔ کنکوری: هر پرسشی از این خانواده دقیقاً یکی از دو محاسبه است. پرسش شبکه‌ای می‌پرسد اعداد ماشینی کجایند و چند تا هستند — فاصله $\beta^{\,e-t}$ است (تفکیک‌پذیری مانتیس یعنی $\beta^{-t}$ را بگیرید و آن را با نمای $\beta^{e}$ عددی که روی آن ایستاده‌اید مقیاس کنید) و شمارش، حاصل‌ضرب انتخاب‌های مستقل به‌علاوهٔ یکی برای صفر است. پرسش تقویتی می‌پرسد چقدر دقت باقی می‌ماند — پاسخ (خطای نسبی ورودی) $\times\,\kappa$ است، که در زبان ارقام یک تفریق است: $\log_{10}\kappa$ رقم از دست می‌رود. پیش از دست زدن به یک عدد، تصمیم بگیرید در کدام‌یک از این دو هستید.