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

واقعیت حاکم (تجزیهٔ چولسکی = حذف گاوسی بدون محورگیری و پایدار پسرو روی یک ماتریس معین مثبت متقارن). اگر $A\in\mathbb{R}^{n\times n}$ متقارن معین مثبت (SPD) باشد، آنگاه حذف گاوسی بدون هیچ تعویض سطری یا ستونی تا انتها اجرا می‌شود و تجزیهٔ زیر را به دست می‌دهد: $A = LL^{T},\qquad L \text{ lower triangular with } \ell_{ii}>0 .$

۱. چرا هرگز به محورگیری نیاز نیست (گزینهٔ ۲ را رد می‌کند). همهٔ کهادهای اصلی پیشرو یک ماتریس SPD مثبت‌اند، پس هر محور $a_{kk}^{(k)}>0$ است و فرایند حذف هرگز شکست نمی‌خورد. افزون بر این، پس از یک گام حذف $A=\begin{pmatrix} a_{11} & b^{T}\\ b & A_{22}\end{pmatrix}\;\longrightarrow\; S = A_{22}-\frac{bb^{T}}{a_{11}},$ متمم شور $S$ باز هم SPD است (برای $x\neq 0$ قرار دهید $y=(-b^{T}x/a_{11},\,x^{T})^{T}$؛ آنگاه $x^{T}Sx=y^{T}Ay>0$). بنابراین این ساختار خودبازتولید است و الگوریتم بدون هیچ شرطی خوش‌تعریف است.

۲. چرا اعداد میانی نمی‌توانند رشد کنند (این همان گزینهٔ ۳ است). مقایسهٔ درایه‌های ستون $j$ در رابطهٔ $A=LL^{T}$ می‌دهد: $a_{jj}=\sum_{k=1}^{j}\ell_{jk}^{2}\quad\Longrightarrow\quad |\ell_{jk}|\le \sqrt{a_{jj}}\le \sqrt{\max_i a_{ii}} .$ هر درایهٔ عامل محاسبه‌شده با ریشهٔ دوم یک درایهٔ قطری ماتریس اصلی کران‌دار می‌شود — هیچ درایه‌ای نمی‌تواند منفجر شود. هم‌ارز با آن، برای خودِ فرایند حذف، قطر متمم شور فقط کاهش می‌یابد، $s_{ii}=a_{ii}-\frac{b_i^{2}}{a_{11}}\le a_{ii},$ و چون یک ماتریس SPD بزرگ‌ترین قدرمطلق خود را روی قطر اختیار می‌کند ($|a_{ij}|<\sqrt{a_{ii}a_{jj}}$)، عامل رشد در رابطهٔ زیر صدق می‌کند: $\rho_n=\frac{\max_{i,j,k}|a_{ij}^{(k)}|}{\max_{i,j}|a_{ij}|}=1 .$ با $\rho_n=1$، کران خطای پسروی ویلکینسون $\;(A+\Delta A)\hat{x}=b,\ \|\Delta A\|\lesssim c_n\,\rho_n\,u\,\|A\|\;$ نشان می‌دهد که این فرایند بدون هیچ شرطی پایدار پسرو است. پس گزینهٔ ۴ (ناپایداری ممکن / رشد قابل‌توجه) نادرست است و گزینهٔ ۳ دقیقاً درست است.

۳. شمارش عملیات (گزینهٔ ۱ را رد می‌کند). هزینهٔ چولسکی برابر است با $\frac{n^{3}}{6}+O(n^{2})\ \text{multiplications},\qquad \text{i.e. } \ \frac{n^{3}}{3}+O(n^{2})\ \text{flops},$ یعنی نصف $\tfrac{2n^{3}}{3}$ عمل ممیز شناور تجزیهٔ LU عمومی — اما همچنان $\Theta(n^{3})$ است، نه $O(n^{2})$. (فقط دستگاه‌های SPD نواری/تُنُک به $O(n^{2})$ یا کمتر کاهش می‌یابند.)

بنابراین تکمیل درست، گزینهٔ ۳ است.

نکتهٔ کنکوری: حالت SPD تنها حالت کلاسیکی است که در آن حذف گاوسی هیچ نیازی به محورگیری ندارد: متمم شور SPD می‌ماند، قطر هرگز افزایش نمی‌یابد، پس $\rho_n=1$. این دو عدد کلیدی را به خاطر بسپارید — هزینهٔ $\tfrac{1}{3}n^{3}$ عمل ممیز شناور (نصف LU) و عامل رشد دقیقاً $1$ — و گزینه‌های ۱، ۲ و ۴ یک‌جا کنار می‌روند.