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

این ماتریس یک بازتابندهٔ هاوس‌هولدر است — هرگز آن را تشکیل ندهید

با $\beta = \tfrac{1}{2}\|u\|_{2}^{2}$ داریم

$H = I - \frac{uu^{T}}{\beta} = I - \frac{2\,uu^{T}}{\|u\|_{2}^{2}},$

که همان بازتاب هاوس‌هولدر نسبت به اَبَرصفحهٔ $u^{\perp}$ است. این ماتریس متقارن و متعامد است ($H^{T}=H$، $H^{2}=I$).

تمام هدف از ذخیرهٔ ضمنی $H$ به کمک تنها بردار $u$ (به‌همراه اسکالر $\beta$) این است که ضرب‌های شامل $H$ هرگز به ماتریس رتبه‌یکِ $n\times n$ یعنی $uu^{T}$ نیاز نداشته باشند. تشکیل $uu^{T}$ هزینهٔ $n^{2}$ ضرب دارد و ضرب چگال $Hx$ نیز $2n^{2}$ عمل ممیز شناور دیگر — و دام گزینه‌های انحرافی دقیقاً بر همین استوار است.

هزینهٔ $Hx$

از شرکت‌پذیری جملهٔ رتبه‌یک استفاده کنید: $(uu^{T})x = u\,(u^{T}x)$، یعنی

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

الگوریتم چنین است:

1. $\gamma \leftarrow u^{T}x$ — یک ضرب داخلی: $n$ ضرب و $n-1$ جمع.
2. $\alpha \leftarrow \gamma/\beta$ — یک تقسیم (خودِ $\beta$ برابر $\tfrac12 u^{T}u$ است و یک‌بار محاسبه می‌شود).
3. $Hx \leftarrow x - \alpha u$ — یک عمل axpy: $n$ ضرب و $n$ تفریق.

مجموعاً $\approx 4n$ عمل ممیز شناور، و بنابراین $O(n)$.

هزینهٔ $x^{T}Hx$

$Hx$ را محاسبه نکنید و سپس کورکورانه با $x$ ضرب داخلی نگیرید (هرچند این هم $O(n)$ است، اما راه تمیزتر حتی ارزان‌تر است). فرم درجه‌دوم را بسط دهید:

$x^{T}Hx = x^{T}x - \frac{x^{T}uu^{T}x}{\beta} = \|x\|_{2}^{2} - \frac{(u^{T}x)^{2}}{\beta}.$

در اینجا $u^{T}x = \gamma$ از پیش در دسترس است و $\|x\|_{2}^{2}$ تنها یک ضرب داخلی دیگر است: $2n$ عمل اضافی. پس $x^{T}Hx$ نیز $\approx 4n$ عمل هزینه دارد، و باز هم $O(n)$ است.

نتیجه

هر دو کمیت با $O(n)$ عمل پایه قابل محاسبه‌اند، که همان گزینهٔ ۴ است.

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

نکتهٔ کنکوری: هرگاه ماتریسی به شکل $I \pm \sigma\, uv^{T}$ باشد (هاوس‌هولدر، به‌روزرسانی رتبه‌یک، شرمن–موریسون)، آن را به‌صورت $u\,(v^{T}x)$ دسته‌بندی مجدد کنید. ضرب یک ماتریس رتبه‌یک در یک بردار همواره $O(n)$ است؛ تنها کسی که $uv^{T}$ را صریحاً می‌سازد هزینهٔ $O(n^{2})$ می‌پردازد.