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

زمینهٔ مسئله. برای یک ماتریس متقارن معین مثبت (SPD) به‌صورت $A\in\mathbb{R}^{n\times n}$، قضیهٔ چولسکی وجود یک تجزیهٔ یکتا را تضمین می‌کند: $A = LL^{\mathsf T},\qquad L \text{ lower triangular},\ \ \ell_{kk}>0 ,$ با بازگشتی زیر: $\ell_{kk}=\sqrt{a_{kk}-\sum_{j<k}\ell_{kj}^{2}},\qquad \ell_{ik}=\frac{1}{\ell_{kk}}\Big(a_{ik}-\sum_{j<k}\ell_{ij}\ell_{kj}\Big),\quad i>k .$ حال هر چهار گزینه را بررسی می‌کنیم.

(۱) نبودِ درایهٔ محوری صفر — درست است. هر زیرماتریس اصلی پیشروِ $A_k$ از یک ماتریس SPD، خود SPD است (کافی است فرم درجهٔ دوم را به بردارهایی محدود کنیم که تنها روی $k$ مؤلفهٔ نخست پشتیبان دارند)، پس $\det A_k>0$ برای هر $k$ برقرار است. چون $\det A_k=\prod_{j\le k}\ell_{jj}^{2}$، نتیجه می‌گیریم $\ell_{kk}^{2}=\frac{\det A_k}{\det A_{k-1}}>0 ,$ بنابراین هر درایهٔ محوری اکیداً مثبت است؛ عبارت زیر رادیکال هرگز $0$ نمی‌شود و هیچ تقسیم بر صفری رخ نمی‌دهد.

(۲) کم‌هزینه‌تر از $LU$ — درست است. روش چولسکی از تقارن بهره می‌برد و تنها یک عامل مثلثی را محاسبه می‌کند: $\text{Cholesky}\ \sim\ \tfrac{1}{3}n^{3}\ \text{flops},\qquad \text{Gaussian elimination / }LU\ \sim\ \tfrac{2}{3}n^{3}\ \text{flops},$ یعنی نصفِ کارِ محاسباتی (به‌علاوهٔ نصف حافظه و بدون نیاز به جست‌وجوی درایهٔ محوری).

(۳) ناپایداری در نبود محورگیری — نادرست است (همین گزینهٔ پاسخ است). چولسکی نمونهٔ کلاسیک الگوریتمی است که بدون هیچ محورگیری‌ای پایدارِ پسرو است. دلیلش کرانی پیشینی بر درایه‌های $L$ است: از $A=LL^{\mathsf T}$، درایهٔ قطری $i$‌ام می‌دهد $\sum_{j=1}^{i}\ell_{ij}^{2}=a_{ii}\quad\Longrightarrow\quad |\ell_{ij}|\le \sqrt{a_{ii}}\le \max_k\sqrt{a_{kk}} .$ پس هیچ رشد درایه‌ای ممکن نیست (عامل رشد به $1$ کران‌دار است) و عامل محاسبه‌شدهٔ $\widehat L$ در رابطهٔ $\widehat L\widehat L^{\mathsf T}=A+\Delta A$ با $\|\Delta A\|\le c(n)\,u\,\|A\|$ صدق می‌کند، که در آن $u$ واحد گِردکردن است. بنابراین محورگیری لازم نیست — و در واقع محورگیری سطری تقارنی را که روش بر پایهٔ آن ساخته شده از بین می‌برد (تنها محورگیری متقارن $P^{\mathsf T}AP$ به کار می‌رود، آن هم فقط برای ماتریس‌های با رتبهٔ ناقص یا نیمه‌معین).

(۴) آزمون معین مثبت بودن — درست است. بازگشتی را روی یک ماتریس متقارن $A$ اجرا کنید: اگر در گامی $a_{kk}-\sum_{j<k}\ell_{kj}^{2}\le 0$ شود، آنگاه $\det A_k\le 0$ و $A$ معین مثبت نیست؛ و اگر الگوریتم تا پایان با همهٔ عبارات زیر رادیکالِ مثبت اجرا شود، آنگاه $A=LL^{\mathsf T}$ با $L$ نامنفرد است و برای هر $x\ne 0$ داریم $x^{\mathsf T}Ax=\|L^{\mathsf T}x\|_2^{2}>0$. تلاش برای اجرای چولسکی دقیقاً ارزان‌ترین آزمون عملی برای معین مثبت بودن است.

پس گزارهٔ نادرست گزینهٔ ۳ است.

نکتهٔ کنکوری: «SPD $\Rightarrow$ بی‌نیازی از محورگیری» تنها واقعیتی است که این سؤال می‌سنجد. برای $LU$ عمومی محورگیری لازم است (برای مهار عامل رشد)، اما برای ماتریس‌های SPD — و نیز ماتریس‌های اکیداً قطری‌غالب — حذف گاوسی/چولسکی بدون هیچ تعویض سطری پایدار است.