تجزیهٔ QR و بازتاب‌های هاوس‌هولدر

هدف. تجزیهٔ یک ماتریس به‌صورت $A=QR$، که در آن $Q$ دارای ستون‌های متعامد یکه است ($Q^{\top}Q=I$) و $R$ بالامثلثی است. این نسخهٔ متعامدِ تجزیهٔ $LU$ است (کارت LU را ببینید): به‌جای صفر کردن ستون‌ها با ضریب‌های حذفی نامتعامد، آن‌ها را با تبدیل‌های متعامد صفر می‌کنیم. چون نگاشت‌های متعامد نُرم اقلیدسی را حفظ می‌کنند، تجزیهٔ $QR$ وضعیت‌مندی (conditioning) ماتریس $A$ را به ارث می‌برد ($\kappa_2(R)=\kappa_2(A)$) و گزینهٔ پایدار از نظر عددی برای کمترین مربعات و الگوریتم مقدار ویژهٔ QR است — دقیقاً همان‌جا که $LU$ و دستگاه معادلات نرمال دقت خود را از دست می‌دهند.

برای $A\in\mathbb{R}^{m\times n}$ با $m\ge n$: در تجزیهٔ کامل $QR$ داریم $Q\in\mathbb{R}^{m\times m}$ متعامد و $R\in\mathbb{R}^{m\times n}$؛ در تجزیهٔ تحویل‌یافته (نازک) $QR$، ماتریس $Q\in\mathbb{R}^{m\times n}$ (با ستون‌های متعامد یکه) و $R\in\mathbb{R}^{n\times n}$ بالامثلثی است. اگر $A$ رتبهٔ ستونی کامل داشته باشد و شرط مثبت بودن قطر $r_{ii}>0$ را بخواهیم، تجزیه یکتا است.

وجود، یکتایی، و آنچه در حالت تباهیده باقی می‌ماند.

• وجود: هر $A\in\mathbb{R}^{m\times n}$ (با هر رتبه و هر شکلی) تجزیهٔ کامل $QR$ دارد — ساخت هاوس‌هولدرِ زیر هرگز شکست نمی‌خورد، برخلاف $LU$ بدون محورگیری.
• یکتایی: تنها با رتبهٔ ستونی کامل + نرمال‌سازی علامت $r_{ii}>0$. در غیر این صورت زوج $Q\Lambda,\ \Lambda R$ با $\Lambda=\operatorname{diag}(\pm1)$ نیز معتبر است، و به همین دلیل گزینه‌های کنکور در علامت با هم تفاوت دارند.
• ماتریس $A$ با نقص رتبه: در $R$ یک صفر روی قطر ظاهر می‌شود؛ آنگاه یک کد پایدار از QR با محورگیری ستونی استفاده می‌کند، $AP=QR$ با $\lvert r_{11}\rvert\ge\lvert r_{22}\rvert\ge\cdots$، که رتبهٔ عددی را آشکار می‌سازد.
• حالت مختلط: ترانهاده را با ترانهادهٔ مزدوج جایگزین کنید — $Q$ به ماتریسی یکانی تبدیل می‌شود ($Q^{*}Q=I$) و بازتابنده به‌صورت $H=I-2uu^{*}/(u^{*}u)$ درمی‌آید که همچنان هرمیتی و یکانی است.
• ارتباط با تجزیهٔ چولسکی: $A^{\top}A=R^{\top}Q^{\top}QR=R^{\top}R$، پس (با شرط $r_{ii}>0$) ماتریس $R$ در تجزیهٔ $QR$ همان عامل چولسکیِ ماتریس نرمال است — که بدون تشکیل $A^{\top}A$ و بدون مربع شدن عدد وضعیت به دست می‌آید.

بازتاب‌های هاوس‌هولدر — ابزار اصلی کار

برای یک بردار ناصفر $v$، بازتابندهٔ هاوس‌هولدر

$H=I-2\,\frac{vv^{\top}}{v^{\top}v}$

بازتاب نسبت به ابرصفحهٔ $v^{\perp}$ است. هرگاه $\lVert u\rVert_2=1$ باشد، این رابطه به‌سادگی به $H=I-2uu^{\top}$ تبدیل می‌شود. ویژگی‌های تعریف‌کنندهٔ آن (که هر کدام هدف محبوب طراحان کنکور است):

• متقارن: $H^{\top}=H$.
• متعامد / درگیرشونده (involutory): $H^{\top}H=H^{2}=I$، پس $H^{-1}=H=H^{\top}$.
• نُرم‌نگهدار (تساوی‌سنج): $\lVert Hx\rVert_2=\lVert x\rVert_2$ برای هر $x$.
• طیف $\{-1,+1,\dots,+1\}$: $Hv=-v$ (مقدار ویژهٔ $-1$، یک بار)، و هر $w\perp v$ ثابت می‌ماند، $Hw=w$ (مقدار ویژهٔ $+1$ با بزرگی $n-1$).
• دترمینان $\det H=-1$ (یک مقدار ویژهٔ $-1$). بنابراین یک بازتاب هرگز معین مثبت نیست (مگر آنکه به $I$ تباهیده شود): یک ماتریس متقارنِ متعامد با مقدار ویژهٔ $-1$ در رابطهٔ $v^{\top}Hv=-\lVert v\rVert^{2}<0$ صدق می‌کند.
• رد (اثر) $\operatorname{tr}H=n-2$ (جمع مقادیر ویژه) — راهی یک‌خطی برای تشخیص یک بازتابنده.

کدام نرمال‌سازی‌ها یک بازتابنده می‌دهند؟

طراحان سؤال $H$ را به شکل $I-\dfrac{uu^{\top}}{\beta}$ یا $I-\gamma uu^{\top}$ پنهان می‌کنند. مقیاس آن اجباری است: برای $u\ne0$،

$H^{\top}H=I-2\gamma uu^{\top}+\gamma^{2}(u^{\top}u)\,uu^{\top}=I\iff \gamma^{2}\lVert u\rVert_2^{2}=2\gamma\iff \gamma=\frac{2}{\lVert u\rVert_2^{2}}.$

پس $I-\gamma uu^{\top}$ متعامد است اگر و تنها اگر $\gamma=2/\lVert u\rVert_2^{2}$، یعنی اگر و تنها اگر مخرج برابر $\beta=\tfrac12\lVert u\rVert_2^{2}$ باشد:

$H=I-\frac{uu^{\top}}{\beta},\qquad \beta=\tfrac12\lVert u\rVert_2^{2}\ \Longleftrightarrow\ H=I-\frac{2uu^{\top}}{u^{\top}u}.$

این همان بازتابنده است، فقط به شکلی نوشته شده که LAPACK آن را ذخیره می‌کند. (برای $\gamma$ کلی، ماتریس $I-\gamma uu^{\top}$ همچنان متقارن است با مقادیر ویژهٔ $1-\gamma\lVert u\rVert_2^{2}$ یک بار و $1$ با بزرگی $n-1$؛ این ماتریس هنگامی تصویرگر است که $\gamma=1/\lVert u\rVert_2^{2}$ و هنگامی بازتابنده است که $\gamma=2/\lVert u\rVert_2^{2}$.)

بازتاب یک ستون روی یک محور. برای نگاشتن $x$ به مضربی از $e_1$، چنین انتخاب می‌کنیم:

$v=x-\alpha e_1,\qquad \alpha=-\operatorname{sign}(x_1)\,\lVert x\rVert_2\ \Longrightarrow\ Hx=\alpha e_1 .$

انتخاب علامت $\alpha=-\operatorname{sign}(x_1)\lVert x\rVert$ باعث می‌شود $v$ تا حد ممکن بلند شود و از حذف فاجعه‌بار (cancellation) در $x_1-\alpha$ جلوگیری شود.

هرگز ماتریس را تشکیل ندهید: اعمال ضمنی (رتبه‌یک)

یک بازتابنده تنها با یک بردار $u$ به‌همراه اسکالر $\beta$ ذخیره می‌شود — $n+1$ عدد، نه $n^{2}$ عدد. آنگاه همهٔ حاصل‌ضرب‌ها با بازگروه‌بندی جملهٔ رتبه‌یک و با استفاده از شرکت‌پذیری $(uu^{\top})x=u\,(u^{\top}x)$ محاسبه می‌شوند:

$Hx=x-\frac{u^{\top}x}{\beta}\,u .$

دستور کار چنین است: (۱) $\gamma\leftarrow u^{\top}x$ (یک ضرب داخلی، $2n-1$ عمل ممیز شناور)؛ (۲) $\alpha\leftarrow\gamma/\beta$ (یک تقسیم)؛ (۳) $x-\alpha u$ (یک عمل axpy، $2n$ عمل ممیز شناور). در مجموع $\approx 4n$ عمل، یعنی $\Theta(n)$ — در برابر $\Theta(n^{2})$ اگر $uu^{\top}$ را صریحاً بسازید و ضرب چگال انجام دهید.

همین ترفند برای فرم‌های درجه‌دوم و دوخطی نیز کار می‌کند، که اصلاً به هیچ ضرب ماتریس در بردار نیاز ندارند:

$x^{\top}Hx=\lVert x\rVert_2^{2}-\frac{(u^{\top}x)^{2}}{\beta},\qquad x^{\top}Hy=x^{\top}y-\frac{(u^{\top}x)(u^{\top}y)}{\beta},$

که هر یک $\Theta(n)$ است. حتی دترمینان هم رایگان به دست می‌آید: بنا بر لم دترمینان ماتریسی $\det(I+uv^{\top})=1+v^{\top}u$، پس $\det H=1-\dfrac{u^{\top}u}{\beta}=1-2=-1$، که علامت بازتاب را در $O(n)$ تأیید می‌کند.

اعمال یک بازتابنده بر یک بلوک کامل $B\in\mathbb{R}^{n\times p}$ نیز بر همین ایده استوار است، $HB=B-\dfrac{u\,(u^{\top}B)}{\beta}$:

دقیقاً به همین دلیل است که تجزیهٔ $QR$ هاوس‌هولدر برای یک ماتریس $m\times n$ هزینهٔ $O(mn^{2})$ دارد و نه $O(mn^{3})$: هر یک از $n$ بازتابنده به‌صورت یک به‌روزرسانی رتبه‌یک بر زیرماتریس باقی‌مانده اعمال می‌شود، نه به‌صورت ضرب ماتریس در ماتریس.

تلهٔ رایج: همین بازگروه‌بندی بر هر ماتریس ساختاریافته به شکل $I\pm\sigma uv^{\top}$ حاکم است — بازتابنده‌های هاوس‌هولدر، به‌روزرسانی‌های رتبه‌یک، فرمول شرمن–موریسون $\left(A+uv^{\top}\right)^{-1}=A^{-1}-\dfrac{A^{-1}uv^{\top}A^{-1}}{1+v^{\top}A^{-1}u}$، و تبدیل‌های گاوس. ضرب یک ماتریس رتبه‌یک در یک بردار همیشه $O(n)$ است؛ تنها کسی که $uv^{\top}$ را می‌سازد هزینهٔ $O(n^{2})$ می‌پردازد.

الگوریتم (QR هاوس‌هولدر)

برای $k=1,\dots,n$: فرض کنید $x$ زیرستون $A[k{:}m,\,k]$ از ماتریس جاری باشد. بازتابندهٔ $H_k$ را بسازید (که به شکل $\operatorname{diag}(I_{k-1},\hat H_k)$ نشانده می‌شود) که $x$ را به $\alpha e_1$ می‌برد، و آن را اعمال کنید: $A\leftarrow H_kA$. این کار همهٔ درایه‌های زیر محور $(k,k)$ را صفر می‌کند. پس از $n$ گام،

$H_n\cdots H_2H_1\,A=R\quad\Longrightarrow\quad Q=H_1H_2\cdots H_n,\qquad A=QR,$

زیرا هر $H_k$ وارون خودش است. هزینه در حدود $\sim 2n^{2}(m-n/3)$ عمل ممیز شناور است — همان تجزیهٔ $QR$ چگال استاندارد — و تشکیل صریح $Q$ تقریباً به همین اندازه هزینه دارد، و به همین دلیل حل‌کننده‌ها $Q$ را در فرم تجزیه‌شده نگه می‌دارند (بردارهای $u_k$ در بخش زیرقطری صفرشدهٔ $A$ ذخیره می‌شوند) و آن را به‌طور ضمنی اعمال می‌کنند. چون $\det H_k=-1$ است، ماتریس مونتاژشدهٔ $Q$ در حالت مربعی $\det Q=(-1)^{n}$ دارد (نکته‌ای دربارهٔ زوجیت بازتاب که کنکور دوست دارد آن را بسنجد).

دوران‌های گیونس — صفر کردن جراحی‌وار

یک دوران گیونس در صفحهٔ $(i,j)$،

$G=\begin{pmatrix} c & s \\ -s & c \end{pmatrix},\qquad c=\frac{a}{\sqrt{a^{2}+b^{2}}},\quad s=\frac{b}{\sqrt{a^{2}+b^{2}}},$

تنها یک درایهٔ انتخاب‌شده را صفر می‌کند (زیرا $(a,b)^{\top}\mapsto(\sqrt{a^{2}+b^{2}},0)^{\top}$ را می‌نگارد). هر $G$ متعامد است با $\det G=+1$ (یک دوران سره، برخلاف بازتاب). تجزیهٔ $QR$ گیونس زمانی ترجیح داده می‌شود که $A$ خلوت یا از پیش تقریباً مثلثی باشد (مثلاً ماتریس‌های هسنبرگ در تکرار مقدار ویژه)، چون هر دوران تنها دو سطر را لمس می‌کند — و باز هم با هرگز نساختن عامل کامل $n\times n$، هزینهٔ هر یک $O(n)$ است.

مثال کوچک حل‌شده (گیونس، $2\times 2$)

ماتریس $A=\begin{pmatrix}a & b\\ c & d\end{pmatrix}$ را با دوران دادن ستون اولش $(a,c)^{\top}$ روی محور تجزیه می‌کنیم. با $r=\sqrt{a^{2}+c^{2}}$، قرار می‌دهیم $\cos=a/r,\ \sin=c/r$ و $J=\begin{pmatrix}\cos & \sin\\ -\sin & \cos\end{pmatrix}$. آنگاه $R=JA$ چنین است:

$r_{11}=\lVert(a,c)\rVert=r,\quad r_{21}=0,\quad r_{12}=\frac{q_1\!\cdot\!(b,d)}{1},\quad r_{22}=\frac{\pm\lvert\det A\rvert}{r},$

و $Q=J^{\top}$. اندازهٔ درایه‌های $R$ مستقل از قرارداد است: $r_{11}=\lVert a_1\rVert$ (نُرم ستون اول)، $\lvert r_{22}\rvert=\lvert\det A\rvert/r_{11}$، و $r_{12}=q_1\!\cdot a_2$ (ضرب داخلی نخستین ستون متعامد یکه در ستون دوم). تنها علامت آن‌ها به انتخاب $Q$ بستگی دارد.

نمونهٔ عددی. برای ماتریس متقارن $A=\begin{pmatrix}2&1\\1&1\end{pmatrix}$: $r_{11}=\sqrt5$، $q_1=\tfrac1{\sqrt5}(2,1)^{\top}$، $r_{12}=q_1\!\cdot(1,1)^{\top}=3/\sqrt5$، $\lvert r_{22}\rvert=\lvert\det A\rvert/r_{11}=1/\sqrt5$، که نتیجه می‌دهد

$Q=\frac{1}{\sqrt5}\begin{pmatrix}2&-1\\1&2\end{pmatrix},\qquad R=\begin{pmatrix}\sqrt5 & 3/\sqrt5\\ 0 & 1/\sqrt5\end{pmatrix}.$

توجه کنید که $Q\ne Q^{\top}$، هرچند $A=A^{\top}$ است: تقارن $A$ باعث متقارن شدن $Q$ نمی‌شود و $R$ را هم قطری نمی‌کند. همین یک زوج $2\times2$ به‌تنهایی هر اتحادِ «$Q^{\top}$ را با $Q$ عوض کن» را رد می‌کند.

سه راه محاسبهٔ QR

روش گرام–اشمیت همان تجزیهٔ تحویل‌یافتهٔ $QR$ را تولید می‌کند (با $r_{ii}>0$): $q_k=(a_k-\sum_{j<k}\langle a_k,q_j\rangle q_j)/r_{kk}$، $r_{jk}=\langle a_k,q_j\rangle$ — از نظر مفهومی شفاف است اما در حساب ممیز شناور تعامد را از دست می‌دهد، و به همین دلیل کتابخانه‌ها برای $QR$ از هاوس‌هولدر/گیونس استفاده می‌کنند.

جبر با $A=QR$: جابه‌جا کردن $Q$ و $R$

خانوادهٔ کاملی از سؤالات کنکور صرفاً دست‌کاری نمادین روی این تجزیه است. تنها حرکت‌های مجاز اینهاست:

$Q^{-1}=Q^{\top},\qquad (Q^{\top})^{-1}=Q,\qquad (XY)^{\top}=Y^{\top}X^{\top},\qquad (XY)^{-1}=Y^{-1}X^{-1},$

به‌علاوهٔ $R^{-\top}:=(R^{\top})^{-1}=(R^{-1})^{\top}$، که به‌محض ناتکین بودن $A$ وجود دارد (آنگاه $\det R=\det(Q^{\top}A)\ne0$). نتایج مفید، معتبر برای هر $A=QR$:

$A^{\top}=R^{\top}Q^{\top},\qquad A^{-1}=R^{-1}Q^{\top},\qquad A^{\top}A=R^{\top}R,\qquad AA^{\top}=QRR^{\top}Q^{\top}.$

هرگاه $A$ افزون بر آن متقارن باشد ($A=A^{\top}$)، ترانهاده گرفتن از $A=QR$ اتحاد اصلی زیر را می‌دهد:

$QR=R^{\top}Q^{\top}\ \Longrightarrow\ R=Q^{\top}R^{\top}Q^{\top}\ \Longrightarrow\ R^{-1}=Q\,R^{-\top}\,Q,$

که گام آخر از وارون‌گیری و معکوس کردن ترتیب به دست می‌آید. هم‌ارز با آن، $QRQ=AQ=R^{\top}Q^{\top}Q=R^{\top}$: حاصل‌ضرب $QRQ$ برابر $R^{\top}$ است، نه $R$. جدول استاندارد گزینه‌های انحرافی:

دو نکتهٔ ساختاری که ارزش به‌خاطر سپردن دارند: بالامثلثی بودن $R$ $\Rightarrow$ $R^{-1}$ بالامثلثی و $R^{\top},R^{-\top}$ پایین‌مثلثی هستند؛ و $R=R^{\top}$ ایجاب می‌کند که $R$ قطری باشد، که برای یک $A=QR$ متقارن تنها در حالت‌های خاص رخ می‌دهد (مثلاً وقتی $A$ به‌طور متعامد شبه‌قطری باشد) و هرگز به‌طور عام رخ نمی‌دهد.

چرا QR (به‌جای LU) برای کمترین مربعات

برای یک دستگاه فراتعیین، مقدار $\lVert Ax-b\rVert_2$ را کمینه می‌کنیم. چون $Q$ یک تساوی‌سنج است، با تجزیهٔ کامل $A=QR$ داریم

$\lVert Ax-b\rVert_2=\lVert Q^{\top}Ax-Q^{\top}b\rVert_2=\big\lVert R_1x-(Q^{\top}b)_{1{:}n}\big\rVert_2^{2}+\text{const},$

پس جواب از یک دستگاه مثلثی $R_1x=(Q^{\top}b)_{1{:}n}$ به دست می‌آید و نُرم باقی‌مانده همان دنبالهٔ انتهایی $\lVert(Q^{\top}b)_{n+1{:}m}\rVert$ است. این کار از مربع شدن عدد وضعیت — که دستگاه معادلات نرمال $A^{\top}Ax=A^{\top}b$ (مسیر $LU$/چولسکی) به بار می‌آورد — جلوگیری می‌کند؛ و همین دلیل آن است که $QR$ ابزار پیش‌فرض کمترین مربعات است.

تکرار مقدار ویژهٔ QR (جایی که تجزیه دوباره بازمی‌گردد)

قرار دهید $A_0=A$ و تکرار کنید $A_k=Q_kR_k$، $A_{k+1}=R_kQ_k$. آنگاه

$A_{k+1}=R_kQ_k=Q_k^{\top}A_kQ_k,$

یعنی یک تشابه متعامد، پس مقادیر ویژه حفظ می‌شوند و (با شیفت) دنبالهٔ $A_k$ به فرم شور (شبه‌)مثلثی همگرا می‌شود. دو نتیجه بی‌درنگ به دست می‌آید: اگر $A$ متقارن باشد، هر $A_{k}$ نیز متقارن است ($Q^{\top}AQ$ متقارن می‌ماند)، و اگر $A$ هسنبرگ بالا باشد، هر $A_k$ نیز هسنبرگ بالا است — و به همین دلیل ابتدا $A$ را (با $n-2$ بازتاب هاوس‌هولدر) به فرم هسنبرگ تحویل می‌دهند و سپس گام‌های $QR$ مبتنی بر گیونس را با هزینهٔ $O(n^{2})$ برای هر گام اجرا می‌کنند.

نکتهٔ کنکوری: این یک‌خطیِ بازتابنده را حفظ کنید — بازتابندهٔ هاوس‌هولدر $H=I-2uu^{\top}$ (با $\lVert u\rVert=1$)، هم‌ارز با $I-uu^{\top}/\beta$ که در آن $\beta=\tfrac12\lVert u\rVert_2^{2}$، هم متقارن و هم متعامد است، یک درگیرشونده ($H^2=I$) با مقادیر ویژهٔ $-1,+1,\dots,+1$، $\operatorname{tr}H=n-2$ و $\det H=-1$، پس نُرم‌نگهدار است اما هرگز معین مثبت نیست. هر پرسشی دربارهٔ هزینهٔ آن با بازگروه‌بندی $u(u^{\top}x)$ پاسخ داده می‌شود: ضرب ماتریس در بردار و فرم درجه‌دوم $O(n)$ هستند و تنها تلهٔ ساختن $uu^{\top}$ هزینهٔ $O(n^{2})$ می‌دهد. برای $QR$ یک ماتریس $2\times2$، ماتریس $R$ را با اندازه‌های مستقل از قرارداد مشخص کنید ($r_{11}=\lVert a_1\rVert$، $\lvert r_{22}\rvert=\lvert\det A\rvert/r_{11}$، $r_{12}=q_1\!\cdot a_2$) و بگذارید قرارداد علامت $Q$ (دوران سره با $\det Q=+1$ در برابر بازتاب با $-1$) علامت‌های باقی‌مانده را تعیین کند. و در هر اتحادی که بر $A=QR$ بنا شده است، تنها راه جابه‌جا کردن $Q$ رابطهٔ $Q^{-1}=Q^{\top}$ است — گزینه‌ای که $Q$ را به‌جای $Q^{\top}$ می‌نشاند، همان گزینهٔ انحرافی کلاسیک است.