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

ایدهٔ اصلی: هرگز ماتریسِ به‌روزشده با به‌روزرسانی رتبه‌یک را نسازید

$E = I - \alpha uv^{T}$ یک ماتریس مقدماتی است (یک به‌روزرسانی رتبه‌یک از همانی — تبدیل‌های گاوس، بازتابنده‌های هاوس‌هولدر $I-2ww^{T}/w^{T}w$ و به‌روزرسانی‌های نوع گیونس همگی همین شکل را دارند). کل نکتهٔ جبر خطی عددی دربارهٔ چنین ماتریس‌هایی این است که هرگز نباید $E$ را تشکیل داد: تنها ضرب خارجی $uv^{T}$ به‌خودی‌خود $n^{2}$ ضرب هزینه دارد و سپس یک ضرب ماتریس-بردارِ چگال $2n^{2}$ عمل ممیز شناور دیگر می‌برد. به‌جای آن از شرکت‌پذیری استفاده کنید.

بازآرایی حاصل‌ضرب

برای هر $x \in \mathbb{R}^{n\times 1}$،

زیرا $\left(uv^{T}\right)x = u\left(v^{T}x\right)$ — اسکالر $\tau = v^{T}x$ نخست استخراج می‌شود. شمارش عملیات:

پس $y = Ex$ $\approx 4n$ عمل ممیز شناور هزینه دارد، یعنی $\Theta(n)$. سرانجام

نیز $n$ ضرب، $n-1$ جمع و یک جذر می‌افزاید — باز هم $\Theta(n)$. در مجموع:

چرا «دست‌کم از مرتبهٔ $n$» دقیقاً $n$ است

این شمارش نمی‌تواند کمتر از $\Theta(n)$ باشد: هر یک از $n$ مؤلفهٔ $x$ بر $\|Ex\|_{2}$ اثر می‌گذارد، پس هر الگوریتم درستی دست‌کم باید همهٔ آن‌ها را بخواند — یک کران پایینِ $\Omega(n)$. چون $\Theta(n)$ با روش بالا نیز به‌دست می‌آید، کمترین مرتبهٔ دست‌یافتنی دقیقاً $n$ است؛ بنابراین جای خالی با گزینهٔ ۱ پر می‌شود.

بررسی گزینه‌های انحرافی

• $n^{2}$ — هزینهٔ مسیر ساده‌لوحانه: ساختن $uv^{T}$ ($n^{2}$ عمل) و ضرب ماتریس چگال در $x$ ($2n^{2}$ عمل). این همان تلهٔ موردنظر طراح است.
• $n\sqrt{n}$ و $\sqrt{n}$ — نماد $\sqrt{\cdot}$ در نُرم اقلیدسی فقط یک جذر اسکالر در پایان کار است و در مرتبهٔ شمارش عملیات وارد نمی‌شود.

نکتهٔ کنکوری: هرگاه ماتریسی به شکل همانی + (رتبه‌پایین) داده شد، بی‌درنگ حاصل‌ضرب را چنان گروه‌بندی کنید که عامل رتبه‌پایین نخست همچون یک ضرب داخلی عمل کند. همین یک واکنش، $O(n^{2})$ را به $O(n)$ تبدیل می‌کند و دقیقاً دلیل آن است که اعمال $k$ بازتابندهٔ هاوس‌هولدر بر یک بردار $O(kn)$ هزینه دارد، نه $O(kn^{2})$.