تحليل QR وغرام-شميت

بناء أساس متعامد معياري

الأعمدة المتعامدة المعيارية هي أحسن الأعمدة سلوكًا في المصفوفة: $Q^{T}Q=I$ فتحفظ $Q$ الأطوال والزوايا ولا تضخّم الأخطاء أبدًا. ويحوّل غرام-شميت أي أعمدة مستقلة $\mathbf{a}_1,\dots,\mathbf{a}_n$ إلى أعمدة متعامدة معيارية: خذ $\mathbf{q}_1=\mathbf{a}_1/\|\mathbf{a}_1\|$ ثم لكل عمود تالٍ اطرح إسقاطاته على المتجهات $\mathbf{q}$ التي وجدتها وطبّع الباقي.

A=QR,\qquad R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j\ (i\le j),\qquad \mathbf{q}_j=\frac{\mathbf{a}_j-\sum_{i<j}R_{ij}\mathbf{q}_i}{R_{jj}}

(1)

تسجيل الأعداد المستعملة يعطي تحليل QR: تضم $Q$ الأعمدة المتعامدة المعيارية و $R$ مثلثية عليا بعناصر $R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j$ والأطوال $R_{jj}$ على القطر. وفي المربعات الصغرى يُصغَّر $\|A\mathbf{x}-\mathbf{b}\|=\|QR\mathbf{x}-\mathbf{b}\|$ بالمعادلة $R\hat{\mathbf{x}}=Q^{T}\mathbf{b}$ ، وهي نظام مثلثي يُحَل بالتعويض الخلفي دون تكوين $A^{T}A$ أبدًا. ولذلك يكون $\kappa(R)=\kappa(A)$ بدلًا من $\kappa(A)^2$ .

غرام-شميت على عمودينلتكن

A=\begin{pmatrix}3&1\\4&2\end{pmatrix}

بعمودين

\mathbf{a}_1=(3,4)

\mathbf{a}_2=(1,2)

. إذن

R_{11}=\|\mathbf{a}_1\|=5

\mathbf{q}_1=(0.6,\,0.8)

. ثم

R_{12}=\mathbf{q}_1\cdot\mathbf{a}_2=2.2

ويكون طول

\mathbf{a}_2-2.2\,\mathbf{q}_1=(-0.32,\,0.24)

هو

R_{22}=0.4

فيكون

\mathbf{q}_2=(-0.8,\,0.6)

. وهكذا

Q=\begin{pmatrix}0.6&-0.8\\0.8&0.6\end{pmatrix}

R=\begin{pmatrix}5&2.2\\0&0.4\end{pmatrix}

. تحقّق:

\det A=2=\det R

Q: أعمدة متعامدة معيارية، $Q^{T}Q=I$ ، بلا تضخيم للأخطاء.
R: مثلثية عليا؛ يضم قطرها الأطوال الباقية بعد إزالة الاتجاهات السابقة.
غرام-شميت المعدَّل (أو انعكاسات هاوسهولدر في المكتبات) يُبقي $Q$ متعامدة في الفاصلة العائمة؛ أما النسخة الكلاسيكية فتفقد التعامد مع الأعمدة شبه المرتبطة.

لماذا تستخدم المكتبات QR للانحداركثيرًا ما تكون المتغيرات المستقلة في المالية شبه متوازية (عوامل مترابطة كثيرة وحدود متعددة الحدود). وستربّع المعادلات الطبيعية رقم الاشتراط هذا وتعيد هراءً بصمت، بينما يتعامل QR (أو SVD) مع الأمر. وهذه هي الخوارزمية وراء إجراءات المربعات الصغرى في NumPy وstatsmodels، وهي ما ستبنيه في المشروع الختامي.

المختبر: ما الذي يُقيَّم

العنصر القطري الأول10 نقطة
المصفوفة Q20 نقطة
المصفوفة R20 نقطة
محدّد من R15 نقطة
المربعات الصغرى بـ QR15 نقطة
لماذا QR أدق20 نقطة

بناء أساس متعامد معياري

A=QR,\qquad R_{ij}=\mathbf{q}_i\cdot\mathbf{a}_j\ (i\le j),\qquad \mathbf{q}_j=\frac{\mathbf{a}_j-\sum_{i<j}R_{ij}\mathbf{q}_i}{R_{jj}}

(1)

غرام-شميت على عمودينلتكن

A=\begin{pmatrix}3&1\\4&2\end{pmatrix}

بعمودين

\mathbf{a}_1=(3,4)

\mathbf{a}_2=(1,2)

. إذن

R_{11}=\|\mathbf{a}_1\|=5

\mathbf{q}_1=(0.6,\,0.8)

. ثم

R_{12}=\mathbf{q}_1\cdot\mathbf{a}_2=2.2

ويكون طول

\mathbf{a}_2-2.2\,\mathbf{q}_1=(-0.32,\,0.24)

هو

R_{22}=0.4

فيكون

\mathbf{q}_2=(-0.8,\,0.6)

. وهكذا

Q=\begin{pmatrix}0.6&-0.8\\0.8&0.6\end{pmatrix}

R=\begin{pmatrix}5&2.2\\0&0.4\end{pmatrix}

. تحقّق:

\det A=2=\det R

Q: أعمدة متعامدة معيارية، $Q^{T}Q=I$ ، بلا تضخيم للأخطاء.
R: مثلثية عليا؛ يضم قطرها الأطوال الباقية بعد إزالة الاتجاهات السابقة.
غرام-شميت المعدَّل (أو انعكاسات هاوسهولدر في المكتبات) يُبقي $Q$ متعامدة في الفاصلة العائمة؛ أما النسخة الكلاسيكية فتفقد التعامد مع الأعمدة شبه المرتبطة.

المختبر: ما الذي يُقيَّم

العنصر القطري الأول10 نقطة
المصفوفة Q20 نقطة
المصفوفة R20 نقطة
محدّد من R15 نقطة
المربعات الصغرى بـ QR15 نقطة
لماذا QR أدق20 نقطة

تحليل QR وغرام-شميت

بناء أساس متعامد معياري

المختبر: ما الذي يُقيَّم

سجّل الدخول لتشغيل الكود الخاص بك.

تحليل QR وغرام-شميت

بناء أساس متعامد معياري

المختبر: ما الذي يُقيَّم

سجّل الدخول لتشغيل الكود الخاص بك.