عملية غرام-شميت

المشكلة: بناء أساس متعامد

في الدرس السابق رأينا مدى قوة المتجهات المتعامدة — تبسّط الإسقاطات، وتستقر الحسابات، وتصبح الصيغ أنيقة. لكن في الواقع العملي، المتجهات التي تبدأ بها نادراً ما تكون متعامدة. قد يكون لديك ثلاثة اتجاهات تمتد فضاءً جزئياً لكنها تشير بزوايا مائلة بالنسبة لبعضها.

تحلّ عملية غرام-شميت هذه المشكلة: بإعطاء أي أساس {v₁, v₂, …, vₙ} لفضاء جزئي، تنتج أساساً متعامداً موحّداً {q₁, q₂, …, qₙ} لنفس الفضاء الجزئي. الفكرة الجوهرية هي الإسقاط التسلسلي — كل متجه أساس جديد يُحصل عليه بأخذ المتجه التالي من المدخلات وطرح جميع مكوناته في الاتجاهات التي تم تحديدها مسبقاً.

لماذا متعامد موحّد؟

الأساس المتعامد يحتوي متجهات متعامدة متبادلاً (حواصل الضرب النقطي صفر). أما الأساس المتعامد الموحّد فيذهب أبعد — طول كل متجه وحدة أيضاً. التعامد الموحّد هو المعيار الذهبي: حين تكون أعمدة المصفوفة Q متعامدة موحّدة، يكون QᵀQ = I، مما يجعل كل صيغة تتضمن Q سريعة ومستقرة عدديًا.

الخوارزمية خطوة بخطوة

ابدأ بمتجهات مستقلة خطياً v₁, v₂, …, vₙ. تنتج غرام-شميت متجهات متعامدة موحّدة q₁, q₂, …, qₙ في ثلاث خطوات مفاهيمية لكل تكرار:

ابدأ من جديد — خذ المتجه التالي من المدخلات vₖ.
اطرح الإسقاطات — أزل مكونات vₖ في كل اتجاه تم إنشاؤه (q₁ إلى qₖ₋₁).
وحّد — اقسم النتيجة على طولها للحصول على متجه وحدة.

صيغة غرام-شميت

\mathbf{u}_k = \mathbf{v}_k - \sum_{j=1}^{k-1} (\mathbf{q}_j^T \mathbf{v}_k)\,\mathbf{q}_j, \qquad \mathbf{q}_k = \frac{\mathbf{u}_k}{\|\mathbf{u}_k\|}

المتجه غير الموحّد uₖ يُحصل عليه بطرح إسقاطات vₖ على جميع المتجهات المتعامدة الموحّدة المحسوبة مسبقاً q₁, …, qₖ₋₁. ثم يُوحَّد: qₖ = uₖ / ‖uₖ‖.

إسقاط vₖ على qⱼ هو ببساطة (qⱼᵀvₖ)qⱼ، لأن qⱼ متجه وحدة. العدد القياسي qⱼᵀvₖ هو الضرب الداخلي (أو الارتباط) بين vₖ والاتجاه qⱼ — يقيس مقدار vₖ الكامن في qⱼ. بطرح جميع هذه المكونات، يكون المتبقي uₖ مضمون التعامد مع جميع متجهات q السابقة.

الخطوتان الأوليان بالتفصيل

الخطوة 1 (k = 1): المتجه الأول تافه — وحّد v₁ فقط. اضبط u₁ = v₁ وq₁ = u₁ / ‖u₁‖. لا شيء لطرحه بعد.

الخطوة 2 (k = 2): خذ v₂ واطرح إسقاطه على q₁. المكوّن من v₂ في اتجاه q₁ هو (q₁ᵀv₂)q₁، إذن:

خطوة غرام-شميت الثانية

\mathbf{u}_2 = \mathbf{v}_2 - (\mathbf{q}_1^T\mathbf{v}_2)\,\mathbf{q}_1, \qquad \mathbf{q}_2 = \frac{\mathbf{u}_2}{\|\mathbf{u}_2\|}

u₂ هو المكوّن من v₂ المتعامد مع q₁. يشير "بعيداً" عن الاتجاه الأول الذي تم التقاطه. ثم q₂ = u₂ / ‖u₂‖.

تحقق: q₁ᵀu₂ = q₁ᵀv₂ − (q₁ᵀv₂)(q₁ᵀq₁) = q₁ᵀv₂ − q₁ᵀv₂ = 0. الطرح يُلغي تماماً مكوّن q₁ — u₂ متعامد مع q₁ بالبناء.

مثال محسوب

لتكن v₁ = [1, 1, 0]ᵀ وv₂ = [1, 0, 1]ᵀ وv₃ = [0, 1, 1]ᵀ في ℝ³. هذه مستقلة خطياً (تحقق: محددها غير صفري). طبّق غرام-شميت:

الخطوة 1: u₁ = v₁ = [1, 1, 0]ᵀ. الطول: ‖u₁‖ = √2. إذن q₁ = [1/√2, 1/√2, 0]ᵀ.

الخطوة 2: q₁ᵀv₂ = (1/√2)(1) + (1/√2)(0) + 0 = 1/√2. اطرح: u₂ = v₂ − (1/√2)q₁ = [1, 0, 1]ᵀ − (1/√2)[1/√2, 1/√2, 0]ᵀ = [1/2, −1/2, 1]ᵀ. الطول: ‖u₂‖ = √(1/4 + 1/4 + 1) = √6/2. إذن q₂ = [1/√6, −1/√6, 2/√6]ᵀ.

الخطوة 3: q₁ᵀv₃ = 1/√2. q₂ᵀv₃ = 1/√6. اطرح: u₃ = v₃ − (1/√2)q₁ − (1/√6)q₂ = [−2/3, 2/3, 2/3]ᵀ. بعد التوحيد: q₃ = [−1/√3, 1/√3, 1/√3]ᵀ.

التحقق من الصحة

تحقق: q₁·q₂ = (1/√2)(1/√6) + (1/√2)(−1/√6) + 0 = 0 ✓. وq₁·q₃ = (1/√2)(−1/√3) + (1/√2)(1/√3) + 0 = 0 ✓. كل qⱼ محسوب له طول الوحدة وكل زوج متعامد — هذا بالضبط ما تضمنه غرام-شميت.

تحليل QR

تحقق غرام-شميت أكثر من إنتاج أساس متعامد موحّد — إنها تُحلّل المصفوفة الأصلية سراً. رتّب المتجهات المدخلة كأعمدة A = [v₁ v₂ … vₙ]. تنتج عملية غرام-شميت Q = [q₁ q₂ … qₙ] بأعمدة متعامدة موحّدة. ماذا حدث لـA؟

بما أن كل vₖ هو تركيب خطي لـq₁, …, qₖ (بالبناء)، فإن A = QR حيث R مثلثية علوية بعناصر قطرية موجبة rₖₖ = ‖uₖ‖. هذا هو تحليل QR:

تحليل QR

A = QR, \quad Q^TQ = I, \quad R_{ij} = \mathbf{q}_i^T\mathbf{v}_j \text{ for } i \le j

A = QR حيث Q لها أعمدة متعامدة موحّدة (QᵀQ = I) وR مثلثية علوية بـrᵢⱼ = qᵢᵀvⱼ لـi ≤ j. العناصر القطرية rₖₖ = ‖uₖ‖ > 0 عندما تكون أعمدة A مستقلة خطياً.

العنصر rᵢⱼ = qᵢᵀvⱼ هو الضرب الداخلي المحسوب أثناء غرام-شميت — مقدار vⱼ الذي يُسقط على qᵢ. لأن غرام-شميت تطرح الإسقاطات على متجهات أسبق فقط (q₁, …, qₖ₋₁)، فإن كل vₖ يتضمن فقط q₁ حتى qₖ — مما يجعل R مثلثية علوية وليست كاملة. هذا ليس مصادفة؛ إنه البصمة الجبرية لعملية الطرح التسلسلي.

لماذا QR أساسي

تحليل QR هو أحد أهم تحليلات المصفوفات في الجبر الخطي العددي. يُستخدم في:

حل مسائل المربعات الصغرى باستقرار (عبر الإحلال العكسي على R)
حساب القيم الذاتية (خوارزمية QR تكرر تحليلات QR)
تعامد المتجهات في طرق الفضاء الكريلوفي (GMRES، Lanczos)
تحقيق تحويل فورييه بكفاءة

الاستقرار العددي: غرام-شميت الكلاسيكية مقابل المعدّلة

خوارزمية غرام-شميت الكلاسيكية الموصوفة أعلاه صحيحة رياضياً، لكن في الحساب بالفاصلة العائمة يمكن أن تتراكم الأخطاء. المشكلة: حين تحسب u₂ = v₂ − (q₁ᵀv₂)q₁ ثم u₃ = v₃ − (q₁ᵀv₃)q₁ − (q₂ᵀv₃)q₂ باستخدام q₂ محسوب مسبقاً، تنتقل أخطاء التقريب في q₂ إلى u₃.

غرام-شميت المعدّلة (MGS) تُعيد ترتيب الحساب ذاته للحد من نمو الخطأ. بدلاً من طرح جميع الإسقاطات دفعة واحدة باستخدام vₖ الأصلي، تُحدّث MGS المتجه الجاري بعد كل طرح إسقاط:

غرام-شميت المعدّلة

\mathbf{v}_k^{(j)} = \mathbf{v}_k^{(j-1)} - (\mathbf{q}_j^T \mathbf{v}_k^{(j-1)})\,\mathbf{q}_j, \quad j = 1, \ldots, k{-}1

في MGS، بعد كل طرح إسقاط يُحدَّث المتجه الوسيط v⁽ʲ⁾ قبل الطرح التالي. مكافئ رياضياً لـGS الكلاسيكية، لكنه أكثر استقراراً عددياً بكثير في حساب الدقة المحدودة.

تنتج كلتا الخوارزميتين النتيجة ذاتها في الحساب الدقيق. الفارق يتعلق فقط بسلوك الفاصلة العائمة. تُبقي MGS المتجهات الوسيطة أقرب إلى التعامد لأنها تُعيد التعامد مع الاتجاهات المنقّاة مسبقاً بدلاً من المتجهات الأصلية (المرتبطة محتملاً). بالنسبة للمتجهات شبه المعتمدة خطياً، يمكن أن يكون الفارق جذرياً.

الأعمدة المتعامدة الموحّدة وصيغة الإسقاط

أحد الفوائد الكبرى لغرام-شميت هو تبسيط صيغة الإسقاط. تذكر من الدرس 5.1: الإسقاط على col(A) يستخدم P = A(AᵀA)⁻¹Aᵀ، مما يستلزم حساب AᵀA وعكسها. عندما تكون A = Q بأعمدة متعامدة موحّدة، يكون QᵀQ = I (المتحدة)، فتنهار الصيغة:

الإسقاط بأساس متعامد موحّد

P = QQ^T, \qquad P\mathbf{b} = \sum_{j=1}^{n}(\mathbf{q}_j^T\mathbf{b})\,\mathbf{q}_j

حين تملك Q أعمدة متعامدة موحّدة، الإسقاط على col(Q) هو ببساطة QQᵀb — لا حاجة لعكس المصفوفة. كل حد (qⱼᵀb)qⱼ هو الإسقاط على اتجاه أساس واحد. الإسقاط الكلي هو مجموع n إسقاطات أحادية البُعد مستقلة.

هذه هي القوة الحسابية لغرام-شميت: بالاستثمار المسبق في تعامد الأساس وتوحيده، يصبح كل إسقاط لاحق، أو حل بمربعات صغرى، أو استخراج إحداثيات، مجرد حاصل ضرب نقطي — لا حاجة لحل أنظمة، ولا لعكس مصفوفات.

الصلة بمتسلسلة فورييه

متسلسلة فورييه هي بالضبط هذه الصيغة مطبّقة على أساس متعامد موحّد لا نهائي من دوال الجيب وجيب التمام. معامل فورييه aₙ = ⟨f, cos(nθ)⟩ هو الضرب الداخلي لـf مع دالة الأساس n — نظير qⱼᵀb. تعيد متسلسلة فورييه تركيب f كمجموع هذه الإسقاطات. غرام-شميت، في أكثر صورها تجريداً، هي النسخة ذات الأبعاد المحدودة من تحليل فورييه.

أبرز النقاط

تحوّل غرام-شميت أي مجموعة مستقلة خطياً {v₁, …, vₙ} إلى مجموعة متعامدة موحّدة {q₁, …, qₙ} تمتد نفس الفضاء الجزئي. كل متجه جديد يطرح الإسقاطات على الاتجاهات السابقة: uₖ = vₖ − Σⱼ (qⱼᵀvₖ)qⱼ، ثم qₖ = uₖ/‖uₖ‖. مطبّقة على أعمدة A، تنتج غرام-شميت تحليل QR: A = QR بـQᵀQ = I وR مثلثية علوية. غرام-شميت المعدّلة مفضّلة عددياً. بعد التعامد الموحّد، تختزل الإسقاطات إلى QQᵀb — لا حاجة لعكس المصفوفة، فقط حواصل ضرب نقطية.