تجزیهٔ LU، حذف گاوسی، محورگزینی و چولسکی

هدف. نوشتن یک ماتریس مربعی به صورت $A=LU$، که در آن $L$ پایین‌مثلثی یکه است (قطر برابر یک، ضریب‌های حذف در زیر آن) و $U$ بالامثلثی است. این چیزی جز حذف گاوسی نیست که به شکل یک حاصل‌ضرب ثبت شده باشد: $U$ همان فرم پلکانی سطری‌ای است که به آن می‌رسید، و $L$ ضریب‌هایی را که برای رسیدن به آن به کار برده‌اید نگه می‌دارد. پس از به دست آوردن آن، دستگاه $Ax=b$ به دو دستگاه مثلثی تجزیه می‌شود — $Ly=b$ با جای‌گذاری پیشرو و سپس $Ux=y$ با جای‌گذاری پسرو — که هر یک $O(n^{2})$ هستند؛ بنابراین پس از یک تجزیهٔ $O(n^{3}/3)$، حل برای بردارهای سمت راست متعدد ارزان تمام می‌شود.

دو نوع بهنجارسازی رایج است و به هر دو «تجزیهٔ $LU$» گفته می‌شود: دولیتل ($\ell_{ii}=1$، که در همهٔ این متن به کار می‌رود) و کروت ($u_{ii}=1$). وجود نوعی بهنجارسازی برای یکتایی الزامی است، زیرا برای هر ماتریس قطری وارون‌پذیر $D$ داریم $LU=(LD)(D^{-1}U)$.

۱. الگوریتم (شکل دولیتل)

برای $k=1,\dots,n-1$، با استفاده از محور $u_{kk}$، درایه‌های ستون $k$ را در زیر قطر حذف کنید. برای هر سطر $i>k$:

$\ell_{ik}=\frac{a_{ik}^{(k)}}{u_{kk}},\qquad R_i\;\leftarrow\;R_i-\ell_{ik}\,R_k.$

ضریب‌های $\ell_{ik}$ مثلث پایینی اکید $L$ را پر می‌کنند؛ ماتریس تبدیل‌شده‌ای که باقی می‌ماند همان $U$ است. به طور مشخص:

$L=\begin{bmatrix} 1 & & & \\ \ell_{21} & 1 & & \\ \vdots & & \ddots & \\ \ell_{n1} & \cdots & \ell_{n,n-1} & 1 \end{bmatrix},\qquad U=\begin{bmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ & u_{22} & & \vdots \\ & & \ddots & \\ & & & u_{nn} \end{bmatrix}.$

شکل فشرده (درایه‌به‌درایه). به جای اجرای کامل حذف، می‌توانید مستقیماً درایه‌های دو طرف $A=LU$ را برابر قرار دهید؛ این کار وقتی تنها یک درایه، یک سطر یا یک ستون از یکی از عامل‌ها خواسته شده باشد بسیار سریع‌تر است:

$u_{kj}=a_{kj}-\sum_{m<k}\ell_{km}u_{mj}\quad(j\ge k),\qquad \ell_{ik}=\frac{1}{u_{kk}}\Big(a_{ik}-\sum_{m<k}\ell_{im}u_{mk}\Big)\quad(i>k).$

خواندن $U$. پس از حذف، $U$ بالامثلثی است: هر درایهٔ زیر قطر برابر $0$ است، قطر محورها را نگه می‌دارد و درایه‌های بالای قطر هر چیزی هستند که باقی مانده است. بنابراین ستون $j$-ام ماتریس $U$ برابر $(u_{1j},\dots,u_{jj},0,\dots,0)^{\mathsf T}$ است — یعنی زیر سطر $j$ به طور خودکار صفر است. وقتی سؤالی «ستون دوم $U$» را برای یک ماتریس $3\times3$ می‌خواهد، چند گزینه فقط به دلیل شکلشان حذف می‌شوند: پاسخ باید به صورت $(*,\ *,\ 0)^{\mathsf T}$ باشد، پس تنها محور و درایهٔ بالای آن نیاز به محاسبه دارند.

تجزیه چه چیزی به دست می‌دهد.

$Ax=b\iff\begin{cases} Ly=b: & y_i=b_i-\sum_{j<i}\ell_{ij}y_j,\\[2pt] Ux=y: & x_i=\dfrac{1}{u_{ii}}\Big(y_i-\sum_{j>i}u_{ij}x_j\Big).\end{cases}$

همچنین $\det A=\prod_{i=1}^{n}u_{ii}$، یا $\det A=(-1)^{s}\prod_i u_{ii}$ هرگاه $s$ بار تعویض سطر انجام شده باشد؛ و محاسبهٔ $A^{-1}$ علاوه بر یک تجزیه، $n$ جفت حل مثلثی هزینه دارد.

حسابداری هزینه. تجزیه به $\tfrac13n^{3}+O(n^{2})$ ضرب/تقسیم نیاز دارد ($\tfrac23n^{3}$ عمل ممیز شناور اگر جمع‌ها جداگانه شمرده شوند)؛ هر حل مثلثی تنها $\tfrac12n^{2}$ ضرب لازم دارد. پس $m$ دستگاه با ماتریس ضرایب مشترک $A$ در مجموع $\tfrac13n^{3}+m\,n^{2}$ هزینه دارند، نه $m\cdot\tfrac13n^{3}$ — و این دقیقاً دلیل ذخیرهٔ $L$ و $U$ به جای تکرار حذف است (و بسیار ارزان‌تر از تشکیل $A^{-1}$). اگر $A$ نواری با پهنای نوار $p$ باشد، $L$ و $U$ همان ساختار نواری را به ارث می‌برند و هزینه به $O(np^{2})$ کاهش می‌یابد؛ حالت سه‌قطری $p=1$ همان الگوریتم توماس با هزینهٔ $O(n)$ است.

۲. حذف گاوسی به عنوان بازگشت مکمل شور

هر چیزی که دربارهٔ شکست الگوریتم، محورگزینی و پایداری گفته می‌شود از یک اتحاد واحد نتیجه می‌گیرد. سطر و ستون اول $A$ را جدا کنید:

$A=\begin{pmatrix} a_{11} & w^{\mathsf T}\\ v & B\end{pmatrix}=\begin{pmatrix} 1 & 0^{\mathsf T}\\ v/a_{11} & I\end{pmatrix}\begin{pmatrix} a_{11} & w^{\mathsf T}\\ 0 & S\end{pmatrix},\qquad S=B-\frac{v\,w^{\mathsf T}}{a_{11}}.$

در اینجا $S$ همان مکمل شور $A/a_{11}$ است: یک گام حذف دقیقاً یک به‌روزرسانی رتبه‌یک روی بلوک باقی‌مانده است، و عامل اول دقیقاً ستون اول $L$ است. اِعمال بازگشتی این اتحاد روی $S$ همان حذف گاوسی است. سه نتیجه:

• محورها. محور $k$-ام یعنی $a_{kk}^{(k)}$ درایهٔ $(1,1)$ مکمل شورِ $(k-1)$ مرتبه تکرارشده است. با گرفتن دترمینان به $\det A=a_{11}\det S$ می‌رسیم و از آن به طور استقرایی $a_{kk}^{(k)}=\Delta_k/\Delta_{k-1}$ — همان فرمول بخش ۳.
• تجزیهٔ $LU$ بلوکی. با یک بلوک پیشروی مربعی وارون‌پذیر $A_{11}$، همان اتحاد چنین خوانده می‌شود

$\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}=\begin{pmatrix}I&0\\A_{21}A_{11}^{-1}&I\end{pmatrix}\begin{pmatrix}A_{11}&A_{12}\\0&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{pmatrix},$

پس $\det A=\det A_{11}\cdot\det\!\big(A/A_{11}\big)$. همین شکل بلوکی است که کتابخانه‌های واقعی اجرا می‌کنند (چون کار را به ضرب ماتریس در ماتریس تبدیل می‌کند).

• کدام رده‌های ماتریسی هرگز به محورگزینی نیاز ندارند. یک رده دقیقاً وقتی از حذف بدون محورگزینی سالم بیرون می‌آید که نسبت به مکمل شور بسته باشد و درایهٔ پیشرو ناصفر (یا مثبت) داشته باشد. ماتریس‌های متقارن معین مثبت، اکیداً قطرغالب، $M$-ماتریس‌ها و ماتریس‌های تماماً نامنفی همگی بسته‌اند؛ یک ماتریس عمومی چنین نیست. همین واقعیت ساختاری دلیل جدول بخش ۴ است.

۳. وجود و یکتایی

فرض کنید $\Delta_k=\det\big(A[1{:}k,\,1{:}k]\big)$ کهادهای اصلی پیشرو باشند، با $\Delta_0=1$.

قضیه. ۱. اگر $\Delta_k\neq0$ برای $k=1,\dots,n-1$، آنگاه حذف گاوسی بدون حتی یک تعویض سطر تا انتها اجرا می‌شود، و تجزیهٔ $A=LU$ با $L$ پایین‌مثلثی یکه وجود دارد و یکتا است. ۲. محورها از روی کهادها به دست می‌آیند: $u_{11}=\Delta_1=a_{11}$ و $u_{kk}=\Delta_k/\Delta_{k-1}$. ۳. برعکس، اگر $A$ نامنفرد باشد و $A=LU$ با $L$ پایین‌مثلثی یکه، آنگاه $\Delta_k\neq0$ برای هر $k$.

پس برای $A$ی وارون‌پذیر، این معیار یک هم‌ارزی دقیق است: تجزیهٔ $A=LU$ وجود دارد $\iff\Delta_1,\dots,\Delta_{n-1}\neq0$. اگر برای یک $k<n$ داشته باشیم $\Delta_k=0$، محور $k$-ام صفر می‌شود در حالی که درایه‌ای ناصفر زیر آن قرار دارد: حذف متوقف می‌شود و تعویض سطر اجتناب‌ناپذیر است. آنگاه تجزیهٔ $LU$ ساده وجود ندارد، اما تجزیهٔ جایگشت‌یافته همیشه وجود دارد.

یکتایی در یک خط. اگر $L_1U_1=L_2U_2$ با هر دو $L_i$ پایین‌مثلثی یکه و $A$ وارون‌پذیر باشد، آنگاه $L_2^{-1}L_1=U_2U_1^{-1}$ هم‌زمان پایین‌مثلثی یکه و بالامثلثی است، پس برابر $I$ است.

حالت مرزی. بند ۳ واقعاً به نامنفرد بودن نیاز دارد — یک ماتریس منفرد ممکن است حتی با کهادهای صفر تجزیه شود (مثلاً ماتریس صفر، $O=I\cdot O$). به همین دلیل پرسش‌های مربوط به وجود همواره برای $A$ی وارون‌پذیر مطرح می‌شوند.

۴. محورگزینی: وقتی حذف متوقف می‌شود

اگر محوری صفر باشد (یا در حساب ممیز شناور، خطرناک‌قدر کوچک باشد) سطرها را جابه‌جا می‌کنید. ثبت این جابه‌جایی‌ها در یک ماتریس جایگشت $P$ تجزیه‌ای می‌دهد که برای هر ماتریس مربعی $A$ همیشه وجود دارد:

$PA=LU.$

• محورگزینی جزئی (سطری) — در گام $k$، آن $r\ge k$ را انتخاب کنید که $|a_{rk}^{(k)}|$ را بیشینه کند و سطرهای $k\leftrightarrow r$ را جابه‌جا کنید. نتیجه: $|\ell_{ik}|\le1$ برای همهٔ $i,k$، پس ضریب‌ها هرگز نمی‌توانند خطا را تقویت کنند. هزینه: $O(n^{2})$ مقایسه، که ناچیز است. این انتخاب پیش‌فرض است.
• محورگزینی جزئی مقیاس‌شده — مقادیر $|a_{rk}^{(k)}|/s_r$ را با $s_r=\max_j|a_{rj}|$ مقایسه کنید؛ این کار در برابر سطرهای بدمقیاس مصون می‌سازد.
• محورگزینی کامل — جست‌وجو در سراسر زیرماتریس باقی‌مانده، که به $PAQ=LU$ می‌انجامد (تعویض سطر و ستون). ایمن‌ترین کران بر رشد را می‌دهد، اما جست‌وجوی $O(n^{3})$ آن به‌ندرت به زحمتش می‌ارزد.

چرا اصلاً محورگزینی وجود دارد: ضریب رشد

پایداری هر روش از نوع حذف را ضریب رشد تعیین می‌کند

$\rho=\frac{\max_{i,j,k}\big|a_{ij}^{(k)}\big|}{\max_{i,j}|a_{ij}|},$

یعنی اینکه درایه‌های میانی تولیدشده در حین حذف نسبت به داده‌ها چقدر بزرگ می‌شوند. تحلیل خطای پسروِ ویلکینسون برای عامل‌های محاسبه‌شده می‌دهد

$\hat L\hat U=A+\Delta A,\qquad \|\Delta A\|_{\infty}\le c\,n\,\rho\,\|A\|_{\infty}\,u,$

که در آن $u$ گِرد کردن واحد است. محورگزینی دقیقاً یک هدف دارد: کوچک نگه داشتن $\rho$. نتیجهٔ آن قاعده‌ای است که نیمی از پرسش‌های مفهومی این مبحث را هدایت می‌کند: روشی که کمیت‌های میانی‌اش پیشاپیش به وسیلهٔ داده‌ها کراندار باشند، هیچ نیازی به محورگزینی ندارد.

۵. چولسکی: حالت متقارن معین مثبت

قضیه (چولسکی). ماتریس متقارن $A\in\mathbb{R}^{n\times n}$ معین مثبت است اگر و تنها اگر تجزیهٔ زیر را بپذیرد

$A=LL^{\mathsf T},\qquad L\ \text{lower triangular},\ \ \ell_{kk}>0,$

و در آن صورت این $L$ یکتا است. محاسبهٔ آن چنین است:

$\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$ گزاره‌های زیر هم‌ارزند:

$A\ \text{positive definite}\iff \Delta_k>0\ (k=1,\dots,n)\iff \lambda_i(A)>0\ \forall i\iff A=LL^{\mathsf T}\ \text{with}\ \ell_{kk}>0.$

در نتیجه، حذف گاوسی بدون محورگزینی روی یک ماتریس متقارن معین مثبت، در هر تکرار محور زیر را تولید می‌کند

$a_{kk}^{(k)}=\frac{\Delta_k}{\Delta_{k-1}}=\ell_{kk}^{2}>0,$

یعنی نسبت دو دترمینان مثبت. پس محور در هر گام اکیداً مثبت است — نه هرگز صفر و نه هرگز منفی — بنابراین بازگشت نمی‌تواند شکست بخورد، هر جذر از عددی مثبت گرفته می‌شود، و هیچ تعویضی هرگز تحمیل نمی‌شود. (برای ماتریس عمومی، محورها می‌توانند مثبت، منفی یا صفر باشند؛ مثبت بودن در اینجا نتیجهٔ واقعی فرض معین مثبت بودن است، نه یک تصادف.)

اصطلاح‌شناسی. در صورت‌های فارسی، «محور» همان pivot است (درایهٔ $a_{kk}^{(k)}$ که در گام $k$ به کار می‌رود) و «محورگزینی» همان pivoting است (عمل انتخاب یا جابه‌جا کردن آن). یک جمله اغلب هر دو را می‌پرسد — مقدار محور و نیاز به محورگزینی — پس به هر دو پاسخ دهید.

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

(الف) هیچ محوری نمی‌تواند صفر شود. هر زیرماتریس اصلی پیشروِ $A_k$ از یک ماتریس متقارن معین مثبت، خود متقارن معین مثبت است (فرم درجه دوم را به بردارهایی که تنها روی $k$ مؤلفهٔ نخست تکیه دارند محدود کنید)، پس $\det A_k>0$. از آنجا که $\det A_k=\prod_{j\le k}\ell_{jj}^{2}$، داریم

$\ell_{kk}^{2}=\frac{\det A_k}{\det A_{k-1}}>0:$

زیر رادیکال هرگز $0$ نمی‌شود و تقسیم بر صفر رخ نمی‌دهد. (به‌ویژه همهٔ $\Delta_k>0$ هستند، پس یک ماتریس متقارن معین مثبت به طور خودکار معیار وجود $LU$ در بخش ۳ را برآورده می‌کند.)

اثبات دوم (مکمل شور)، همانی که تعمیم می‌یابد. با $A=\begin{pmatrix}a_{11}&w^{\mathsf T}\\ w&B\end{pmatrix}$ی متقارن، محور اول برابر $a_{11}=e_1^{\mathsf T}Ae_1>0$ است. برای $x\neq0$ در $\mathbb{R}^{n-1}$ قرار دهید $y=\big(-\tfrac{w^{\mathsf T}x}{a_{11}},\,x\big)^{\mathsf T}$؛ با بسط دادن فرم درجه دوم،

$0<y^{\mathsf T}Ay=x^{\mathsf T}\Big(B-\frac{w\,w^{\mathsf T}}{a_{11}}\Big)x=x^{\mathsf T}Sx.$

پس مکمل شور $S$ نیز متقارن معین مثبت است؛ بنا بر بازگشت بخش ۲، هر محور بعدی درایهٔ قطری پیشرو یک ماتریس متقارن معین مثبت است و در نتیجه مثبت است. این دقیقاً همان گزارهٔ «ردهٔ متقارن معین مثبت نسبت به مکمل شور بسته است» می‌باشد.

(ب) نبودِ رشد درایه‌ها، و در نتیجه پایداری پسروِ نامشروط بدون محورگزینی. با مقایسهٔ درایه‌های $(i,i)$ در $A=LL^{\mathsf T}$ به $a_{ii}=\sum_{j\le i}\ell_{ij}^{2}$ می‌رسیم و از آن کران پیشینی

$|\ell_{ij}|\le\sqrt{a_{ii}}\le\sqrt{\max_k a_{kk}}\qquad(1\le j\le i),\qquad\text{indeed}\quad\|L\|_F^{2}=\operatorname{tr}(A).$

دو نامساوی دیگر استدلال را کامل می‌کنند. نخست، برای $A$ی متقارن معین مثبت، کران کوشی–شوارتس $|a_{ij}|\le\sqrt{a_{ii}a_{jj}}\le\max_k a_{kk}$ می‌گوید بزرگ‌ترین درایه از نظر قدرمطلق روی قطر قرار دارد. دوم، قطر مکمل شور فقط کوچک‌تر می‌شود: $s_{ii}=b_{ii}-w_i^{2}/a_{11}\le b_{ii}$. بنابراین هیچ ماتریس میانی هرگز از $\max_k a_{kk}=\max_{i,j}|a_{ij}|$ فراتر نمی‌رود، یعنی

$\rho=1\quad(\text{in particular }\rho\le1).$

آنگاه نتیجهٔ ویلکینسون می‌دهد $\hat L\hat L^{\mathsf T}=A+\Delta A$ با $\|\Delta A\|_2\le c(n)\,u\,\|A\|_2$ و $c(n)=O(n)$: پس چولسکی به طور نامشروط از نظر پسرو پایدار است. محورگزینی سطری نه‌تنها غیرضروری است، بلکه تقارنی را نابود می‌کند که کل روش بر آن بنا شده است؛ تنها محورگزینی متقارن $P^{\mathsf T}AP$ گاهی به کار می‌رود، آن هم فقط برای ماتریس‌های با رتبهٔ ناقص یا نیمه‌معین.

(ج) نصف کار $LU$. تقارن یعنی تنها یک عامل مثلثی محاسبه و تنها نیمی از ماتریس ذخیره می‌شود، و جست‌وجوی محور هم وجود ندارد:

$\text{Cholesky}\sim\tfrac16 n^{3}\ \text{mult/div},\qquad LU\sim\tfrac13 n^{3}\ \text{mult/div},$

یا هم‌ارز با آن $\tfrac13n^{3}$ در برابر $\tfrac23n^{3}$ عمل ممیز شناور وقتی جمع‌ها جداگانه شمرده شوند — در هر دو حالت همان نسبت $1:2$، به‌علاوهٔ $n$ جذر برای چولسکی. هر دو قرارداد در گزینه‌های کنکور ظاهر می‌شوند؛ تنها چیزی که ابهام ندارد نسبت است.

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

(ه) چولسکی در برابر حذف گاوسی با محورگزینی — مقایسهٔ منصفانه. مقایسهٔ درست، چولسکی روی $A$ی متقارن معین مثبت در برابر حذف گاوسی با محورگزینی جزئی روی $A$ی عمومی است، و باید هم‌زمان روی هر دو محور انجام شود:

حکم نهایی: روی ماتریس متقارن معین مثبت، چولسکی هم پایدار است و هم تقریباً دو برابر سریع‌تر. دو تلهٔ استاندارد یکی از این دو محور را می‌پذیرند و دیگری را انکار می‌کنند — «پایدار اما کندتر» (نسبت عملیات را وارونه می‌گیرد) و «سریع‌تر اما احتمالاً ناپایدار» (این توصیف حذف گاوسی بدون محورگزینی روی ماتریس عمومی است، نه چولسکی روی ماتریس متقارن معین مثبت). معمولاً روش ارزان‌تر پرخطرتر است؛ معین مثبت بودن دقیقاً همان فرض به‌قدر کافی قوی است که روش ارزان‌تر را هم‌زمان ایمن‌تر می‌کند.

گونهٔ بدون جذر. تجزیهٔ $A=LDL^{\mathsf T}$ با $L$ پایین‌مثلثی یکه و $D=\operatorname{diag}(d_1,\dots,d_n)$ از $n$ جذر پرهیز می‌کند؛ این تجزیه برای هر ماتریس متقارن $A$ با $\Delta_k\neq0$ وجود دارد، و $A$ متقارن معین مثبت است $\iff$ همهٔ $d_k>0$. این همان محاسبهٔ $LU$ است: $U=DL^{\mathsf T}$، $d_k=u_{kk}=\Delta_k/\Delta_{k-1}$، و در حالت معین مثبت، عامل چولسکی برابر $\tilde L=LD^{1/2}$ است. برای ماتریس‌های متقارن نامعین از $LDL^{\mathsf T}$ با محورگزینی متقارن (بانچ–کافمن) و بلوک‌های قطری $1\times1$/$2\times2$ استفاده می‌شود.

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

(الف) یک $LU$ ساده. برای

$A=\begin{bmatrix}2&1&1\\4&-6&0\\-2&7&2\end{bmatrix},\qquad \ell_{21}=\tfrac{4}{2}=2,\ \ \ell_{31}=\tfrac{-2}{2}=-1\ \Longrightarrow\ \begin{bmatrix}2&1&1\\0&-8&-2\\0&8&3\end{bmatrix},\qquad \ell_{32}=\tfrac{8}{-8}=-1,$

$L=\begin{bmatrix}1&0&0\\2&1&0\\-1&-1&1\end{bmatrix},\qquad U=\begin{bmatrix}2&1&1\\0&-8&-2\\0&0&1\end{bmatrix}.$

بررسی متقابل با فرمول کهادها: $\Delta_1=2$، $\Delta_2=-16$، پس $u_{22}=\Delta_2/\Delta_1=-8$ — و $\det A=\prod_i u_{ii}=-16$ که رایگان به دست آمد.

(ب) وارون‌پذیر، اما بدون $LU$. ماتریس $A=\begin{bmatrix}0&1\\1&0\end{bmatrix}$ دارای $\det A=-1\neq0$ است اما $\Delta_1=0$: حذف حتی نمی‌تواند شروع شود، پس هیچ $LU$ وجود ندارد. یک تعویض مشکل را حل می‌کند، $PA=I=I\cdot I$. همین ماتریس دو‌در‌دو تمام محتوای هر سؤالِ «وارون‌پذیر اما بدون تجزیهٔ $LU$» است؛ کنکور فقط آن را با یک $\Delta_2=0$ پنهان به اندازهٔ $3\times3$ بزرگ می‌کند.

(ج) چولسکی. برای $A=\begin{bmatrix}4&2&-2\\2&5&-1\\-2&-1&5\end{bmatrix}$ (متقارن، با $\Delta_1=4,\ \Delta_2=16,\ \Delta_3=64$ که همه $>0$ هستند، پس متقارن معین مثبت):

$\ell_{11}=2,\quad \ell_{21}=1,\quad \ell_{31}=-1,\quad \ell_{22}=\sqrt{5-1}=2,\quad \ell_{32}=\frac{-1-(-1)(1)}{2}=0,\quad \ell_{33}=\sqrt{5-1-0}=2,$

$L=\begin{bmatrix}2&0&0\\1&2&0\\-1&0&2\end{bmatrix},\qquad \det A=\Big(\prod_i\ell_{ii}\Big)^{2}=64.$

توجه کنید که برای هر درایه $|\ell_{ij}|\le\sqrt{\max_k a_{kk}}=\sqrt5$، دقیقاً همان‌طور که کران رشد پیش‌بینی می‌کند.

(د) همان ماتریس، در قالب بازگشت مکمل شور. با $a_{11}=4>0$ و $w=(2,-2)^{\mathsf T}$،

$S=\begin{bmatrix}5&-1\\-1&5\end{bmatrix}-\frac{1}{4}\begin{bmatrix}2\\-2\end{bmatrix}\begin{bmatrix}2&-2\end{bmatrix}=\begin{bmatrix}5&-1\\-1&5\end{bmatrix}-\begin{bmatrix}1&-1\\-1&1\end{bmatrix}=\begin{bmatrix}4&0\\0&4\end{bmatrix},$

که باز هم متقارن معین مثبت است و درایه‌های قطری‌اش از قبل بزرگ‌تر نشده‌اند ($5\to4$). دنبالهٔ محورها $4,4,4$ است: همه اکیداً مثبت (چنان‌که $\Delta_1/\Delta_0=4$، $\Delta_2/\Delta_1=4$، $\Delta_3/\Delta_2=4$ پیش‌بینی می‌کنند)، همه $\le\max_k a_{kk}=5$، پس $\rho=1$ و $\ell_{kk}=\sqrt{4}=2$ که با بند (ج) هم‌خوان است. اگر یکی از محورها $\le0$ درمی‌آمد، $A$ اساساً معین مثبت نبود — و هیچ تعویضی نمی‌توانست نجاتش دهد.

۷. وجود تجزیه در برابر وارون‌پذیری — این دو را اشتباه نگیرید

ماتریس همیشگی کنکور وارون‌پذیر است ($\det A\neq0$، اغلب عددی منفی و کوچک) ولی $\Delta_2=0$ دارد، پس تجزیهٔ $LU$ سادهٔ آن وجود ندارد: این دو مفهوم واقعاً از هم مستقل‌اند.

۸. کدام تجزیه را انتخاب کنیم

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

مجموعهٔ الگوها کوچک و در طول سال‌ها ثابت است:

۱. محاسبهٔ یک عامل. «$L$ را بیابید»، «ستون دوم $U$»، «درایهٔ $\ell_{32}$». از شکل فشرده و قیدهای شکلی استفاده کنید؛ معمولاً یک درایه گزینه‌ها را از هم جدا می‌کند. ۲. وجود. «برای کدام ماتریس تجزیهٔ $LU$ (بدون تعویض سطر) وجود ندارد؟» — مقادیر $\Delta_1,\dots,\Delta_{n-1}$ را حساب کنید؛ همهٔ گزینه‌های انحرافی وارون‌پذیرند، پس $\det A$ هرگز تعیین‌کننده نیست. ۳. پایداری مفهومی. «چرا چولسکی بدون محورگزینی پایدار است؟» یا «کدام گزاره دربارهٔ چولسکی نادرست است؟» — چهار گزینه یکتایی، نامنفرد بودن، شمارش عملیات و رشد درایه‌ها را با هم می‌آمیزند و سه‌تای آن‌ها گزاره‌های درستی هستند. تنها کراندار بودن کمیت‌های میانی است که علت پایداری است. ۴. هزینه. چولسکی نصف $LU$ است؛ یک حل مثلثی $O(n^{2})$ است، پس وقتی $A=LU$ ذخیره شده باشد بردارهای سمت راست اضافی تقریباً رایگان‌اند؛ تشکیل صریح $A^{-1}$ گزینهٔ اسراف‌کارانه است. ۵. کمیت‌های مشتق‌شده. $\det A$ از روی محورها (با علامت جایگشت)، فرمول محور $u_{kk}=\Delta_k/\Delta_{k-1}$، یا شمارش عملیات برای حل $m$ دستگاه با ماتریس ضرایب مشترک $A$. ۶. «محور در هر تکرار چیست؟» — که برای ماتریس متقارن معین مثبتِ تجزیه‌شده به صورت $A=LL^{\mathsf T}$ با حذف گاوسی پرسیده می‌شود. چهار گزینه حالت‌های علامت را افراز می‌کنند: مثبت است اما شاید همچنان به محورگزینی نیاز باشد / ممکن است صفر، منفی یا مثبت باشد / ممکن است صفر باشد، پس محورگزینی لازم است / مثبت است و محورگزینی لازم نیست. گزینهٔ آخر درست است و توجیه آن دولایه است: مثبت بودن از $\Delta_k/\Delta_{k-1}>0$ (نبود شکست) به‌علاوهٔ $\rho=1$ (نبود دلیل دقتی برای تعویض). «ممکن است صفر/منفی باشد» توصیف یک ماتریس عمومی است؛ فرض معین مثبت بودن دقیقاً همان چیزی است که این حالت را ممنوع می‌کند. ۷. مقایسهٔ رودررو با حذف گاوسی + محورگزینی. «برای مثلثی‌سازی یک ماتریس متقارن معین مثبت، چولسکی در مقایسه با حذف گاوسی با محورگزینی … است» با گزینه‌هایی از ضرب دکارتی {پایدار، ناپایدار} × {سریع‌تر، کندتر}. پاسخ: پایدار و سریع‌تر. هر دو نیمه را جداگانه بررسی کنید — پایداری از نبود رشد درایه‌ها، و سرعت از $\tfrac16n^{3}$ در برابر $\tfrac13n^{3}$ ضرب به‌علاوهٔ حذف جست‌وجوی محور و نصف شدن حافظه.

تلهٔ رایج: وجود تجزیهٔ $LU$ را کهادهای اصلی پیشرو از مرتبهٔ $1,\dots,n-1$ تعیین می‌کنند، نه $\det A$. یک ماتریس کاملاً وارون‌پذیر می‌تواند فاقد $LU$ باشد (یک محور میانی صفر می‌شود)، و برای بررسی وجود هرگز لازم نیست $\Delta_n=\det A$ را حساب کنید. دترمینان‌های بالا-چپِ $k\times k$ را بیازمایید، در مرتبهٔ $n-1$ متوقف شوید، و اگر یکی صفر بود سراغ تعویض سطر بروید ($PA=LU$).

نکتهٔ کنکوری: وقتی سؤالی می‌پرسد چرا یک روش بدون محورگزینی پایدار است، پاسخ همیشه گزاره‌ای دربارهٔ ضریب رشد است — اینکه اعداد میانی نمی‌توانند بزرگ شوند — نه هرگز یکتایی، نه وارون‌پذیری، نه شمارش عملیات. این سه معمولاً واقعیت‌های درستی دربارهٔ روش‌اند و دقیقاً به همین دلیل گزینه‌های انحرافی خوبی می‌سازند. دو ردهٔ کلاسیکی که به محورگزینی نیاز ندارند عبارت‌اند از متقارن معین مثبت ($\rho=1$، از $|\ell_{ij}|\le\sqrt{a_{ii}}$) و اکیداً قطرغالب ($\rho\le2$).

نکتهٔ کنکوری: عبارت «متقارن معین مثبت» هم‌زمان به دو پرسش متفاوت پاسخ می‌دهد. محور چیست؟ — اکیداً مثبت، $a_{kk}^{(k)}=\Delta_k/\Delta_{k-1}=\ell_{kk}^{2}$، نه هرگز صفر و نه هرگز منفی. آیا محورگزینی لازم است؟ — خیر، چون $\rho=1$؛ و تعویض سطرها حتی تقارنی را که $A=LL^{\mathsf T}$ بر آن تکیه دارد نابود می‌کند. این دو را کنار هم بگذارید و می‌بینید چولسکی روی هر دو محور از حذف گاوسی با محورگزینی بهتر است: هم به طور نامشروط پایدار است و هم نصف محاسبات را دارد.