الرئيسية / LA 101 / الوحدة 7 / الدرس 2
وضع القصص

تحليل QR

تحليل أي مصفوفة A إلى متعامد Q ومثلثية علوية R. تحليل QR هو العمود الفقري لحلول المربعات الصغرى وخوارزميات القيم الذاتية — وهو أكثر استقراراً عددياً من نهج المعادلات الاعتيادية.

~١٨ دقيقة قراءة و٧ · د٢ متوسط

ما هو تحليل QR؟

يمكن تحليل أي مصفوفة A ذات أعمدة مستقلة خطياً إلى حاصل ضرب A = QR، حيث تملك Q أعمدة متعامدة وحدوية، وR مثلثية علوية بمدخلات قطرية موجبة. يوجد هذا التحليل لأي مصفوفة m × n حيث m ≥ n وrتبتها n — أي لأي مصفوفة أعمدتها مستقلة خطياً. خلافاً لتحليل LU الذي يتطلب مصفوفة مربعة، يعمل تحليل QR مع المصفوفات المستطيلة الطويلة أيضاً، مما يجعله الأداة الطبيعية لمسائل المربعات الصغرى الزائدة التحديد.

يلتقط العامل المتعامد Q هندسة فضاء العمود في A: أعمدته تشكّل أساساً متعامداً وحدوياً لذلك الفضاء. أما العامل المثلثي العلوي R فيلتقط "التحجيم والقص" اللازمين للانتقال من الأساس المتعامد الوحدوي القياسي إلى أعمدة A الفعلية. معاً يرمّزان كل شيء عن A في شكل متميز باستقراره العددي.

يظهر تحليل QR في ثلاثة تطبيقات رئيسية: حل مسائل المربعات الصغرى، وحساب القيم الذاتية عبر خوارزمية QR، وجعل مجموعة من المتجهات متعامدة. في الثلاثة جميعها، تعامد Q هو المفتاح — إذ يعني أن Q⁻¹ = Qᵀ، فضرب المتجهات بـ Q أو Qᵀ مشروط تماماً ولا يضخّم الأخطاء قط.

العاملان Q وR

لمصفوفة m × n تحقق m ≥ n وأعمدتها مستقلة خطياً، يكتب تحليل QR A = QR حيث:

تحليل QR
A = QR, \quad Q^T Q = I_n, \quad R = \begin{pmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{pmatrix}, \quad r_{kk} > 0
A هي m × n، وQ هي m × n بأعمدة متعامدة وحدوية (QᵀQ = Iₙ)، وR هي n × n مثلثية علوية بقطر موجب. أعمدة Q تشكّل أساساً متعامداً وحدوياً لفضاء عمود A. عندما m = n، تكون Q مصفوفة متعامدة مربعة (QQᵀ = QᵀQ = I).

يوجد أيضاً تحليل QR "الكامل" حيث تُوسَّع Q إلى مصفوفة متعامدة m × m بإضافة m − n أعمدة متعامدة وحدوية إضافية، وتُوسَّع R إلى مصفوفة m × n بحشو صفوف من الأصفار. كلا الشكلين مفيد، لكن تحليل QR "الرفيع" (مع Q بحجم m × n) هو الأكثر استخداماً عملياً.

حساب QR: عملية غرام-شميدت

أبسط طريقة مفاهيمياً لحساب QR هي عملية غرام-شميدت، التي تبني الأعمدة المتعامدة الوحدوية لـ Q عموداً تلو الآخر. تذكر من الوحدة 5 أن غرام-شميدت تأخذ مجموعة من المتجهات المستقلة خطياً وتُنتج أساساً متعامداً وحدوياً لمجالها. عند تطبيقها على الأعمدة a₁، a₂، …، aₙ من A، تُنتج الأعمدة q₁، q₂، …، qₙ من Q.

العملية تكرارية. في الخطوة k، نأخذ aₖ، نطرح منها إسقاطاتها على جميع المتجهات الأساسية المبنية سابقاً q₁، …، q_{k−1}، ثم نُعيار البقية:

خطوة غرام-شميدت
\tilde{e}_k = a_k - \sum_{i=1}^{k-1}(q_i^T a_k)\,q_i, \quad q_k = \frac{\tilde{e}_k}{\|\tilde{e}_k\|}, \quad r_{ik} = q_i^T a_k,\; r_{kk} = \|\tilde{e}_k\|
في كل خطوة k، نشكّل البقية ẽₖ بطرح إسقاطات aₖ على جميع q₁، …، q_{k−1} السابقة. ثم نُعيار: qₖ = ẽₖ / ‖ẽₖ‖. المدخلات rᵢₖ = qᵢᵀaₖ تملأ العمود k من R فوق القطر، ورₖₖ = ‖ẽₖ‖ يملأ القطر. والنتيجة A = QR.

قراءة مدخلات R من خطوات غرام-شميدت: المدخل القطري rₖₖ = ‖ẽₖ‖ هو معيار البقية في الخطوة k، والمدخلات خارج القطر rᵢₖ = qᵢᵀaₖ هي معاملات الإسقاط. يمكن استعادة الأعمدة a₁، a₂، …، aₙ من q₁، q₂، …، qₙ عبر المصفوفة المثلثية العلوية R، مما يؤكد أن A = QR.

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

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

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

حساب QR: انعكاسات هاوس-هولدر

نهج انعكاسات هاوس-هولدر هو الطريقة المستخدمة في المكتبات العددية الإنتاجية (LAPACK وNumPy وMATLAB). بدلاً من بناء Q عموداً بعمود كما في غرام-شميدت، تبني Q كحاصل ضرب مصفوفات متعامدة ابتدائية مضروبة من اليسار في A.

انعكاس هاوس-هولدر H هو مصفوفة متعامدة متماثلة من الشكل H = I − 2vvᵀ / (vᵀv)، حيث v يسمى متجه هاوس-هولدر. هندسياً، H تعكس أي متجه عبر الفضاء المتعامد مع v. باختيار v مناسب في كل خطوة، يمكننا تصفير جميع المدخلات تحت القطر في عمود معين من A.

انعكاس هاوس-هولدر
H = I - \frac{2vv^T}{v^T v}, \quad H^T H = I, \quad H^2 = I, \quad Hx = \|x\|\,e_1
المصفوفة H = I − 2vvᵀ/(vᵀv) متعامدة (HᵀH = I) ومتماثلة (H = Hᵀ)، لذا H² = I. يُختار v بحيث يكون Hx = ‖x‖e₁ لمتجه هدف x معطى — أي H تعكس x على المحور الإحداثي الأول وتُصفّر جميع المكوّنات الأخرى. تطبيق n انعكاسات من اليسار على A ينتج في النهاية R = Hₙ⋯H₁A، ثم Q = H₁⋯Hₙ.

يتميز نهج هاوس-هولدر بميزتين رئيسيتين. أولاً الاستقرار العددي: كل انعكاس هو تحويل متعامد دقيق لا يُفقد التعامد بسبب التقريب. ثانياً الكفاءة: العمل مع vvᵀ بشكل ضمني (دون تشكيل المصفوفة الكاملة n×n) يجعل كل خطوة تكلف O(mn) بدلاً من O(mn²). عملياً، تخزّن LAPACK متجهات هاوس-هولدر وتطبّقها بكسل، مما يجعل تكلفة التحليل الكلية حوالي 2mn² − 2n³/3 عملية.

حساب QR: دورانات غيفنز

يبني نهج ثالث Q كحاصل ضرب دورانات غيفنز — مصفوفات متعامدة ابتدائية تدور إحداثيين في كل مرة. دوران غيفنز G(i, j, θ) يؤثر فقط على الصفين i وj، يدورهما بزاوية θ بحيث يصبح مدخل هدف صفراً. هذا هو "المشرط الجراحي": بينما تُصفّر انعكاسات هاوس-هولدر عموداً كاملاً تحت القطر في خطوة واحدة، تُصفّر دورانات غيفنز مدخلاً واحداً في كل مرة.

تتألق دورانات غيفنز عندما تكون A متفرقة: إن كانت معظم مدخلات A أصفاراً، فمن المضيّع تطبيق انعكاس هاوس-هولدر كامل. دورانات غيفنز تلمس فقط الصفين المعنيين في كل تصفير، مما يحفظ التفرق أفضل بكثير. وهي الطريقة المفضلة للمصفوفات الشريطية ولتحديث تحليل QR القائم عند تغيّر صف واحد من A.

التطبيق: المربعات الصغرى عبر QR

الدافع الأساسي لتحليل QR في التطبيقات هو حل مسائل المربعات الصغرى الزائدة التحديد: بمعطى مصفوفة A بحجم m × n حيث m > n ومتجه b ∈ ℝᵐ، أوجد x ∈ ℝⁿ يُصغّر ‖Ax − b‖².

النهج القياسي — المعادلات الاعتيادية AᵀAx = Aᵀb — يحسب AᵀA مما يضاعف رقم التكييف: κ(AᵀA) = κ(A)²، وهو ما يمكن أن يكون كارثياً عندما تكون A سيئة التكييف. نهج QR يتجنب تشكيل AᵀA كلياً.

المربعات الصغرى عبر QR
\min_x \|Ax - b\|^2 = \min_x \|QRx - b\|^2 \;\Rightarrow\; Rx = Q^T b \text{ (back substitution)}
نعوّض A = QR في ‖Ax − b‖² = ‖QRx − b‖². لأن أعمدة Q متعامدة وحدوية، يحفظ الضرب بـ Qᵀ من اليسار المعايير: ‖QRx − b‖² = ‖Rx − Qᵀb‖² + ‖(I − QQᵀ)b‖². الحد الثاني ثابت، فتصغير x يتطلب حل المنظومة المثلثية العلوية Rx = Qᵀb بالتعويض الخلفي — O(n²) بعد التحليل.

يكلّف نهج QR 2mn² − 2n³/3 عملية للتحليل، لكن خفض رقم التكييف من κ(A)² إلى κ(A) يستحق التكلفة الإضافية عادةً. عندما تكون A قريبة من الرتبة المنقوصة أو البيانات صاخبة، يمكن لنهج QR أن يُعطي إجابات صحيحة حيث تُنتج المعادلات الاعتيادية نتائج عشوائية.

التطبيق: خوارزمية QR للقيم الذاتية

تحليل QR هو أيضاً محرّك أكثر الخوارزميات استخداماً لحساب جميع القيم الذاتية لمصفوفة: خوارزمية QR (لا تُخلط مع تحليل QR نفسه). التكرار الأساسي بسيط بشكل لافت:

  1. ابدأ بـ A₀ = A.
  2. في كل خطوة k: احسب تحليل QR للمصفوفة Aₖ = QₖRₖ.
  3. شكّل Aₖ₊₁ = RₖQₖ (اعكس ترتيب الحاصل).
  4. كرر حتى تتقارب Aₖ إلى مصفوفة مثلثية علوية (أو شبه مثلثية).
تكرار QR
A_k = Q_k R_k \;\Rightarrow\; A_{k+1} = R_k Q_k = Q_k^T A_k Q_k \quad (\text{similar to } A)
المتتالية A₀، A₁، A₂، … تتقارب نحو الشكل المثلثي العلوي (شكل شور) الذي مدخلاته القطرية هي القيم الذاتية لـ A. جميع مصفوفات المتتالية متشابهة لـ A₀ = A (لأن Aₖ₊₁ = QₖᵀAₖQₖ)، فهي تتشارك القيم الذاتية ذاتها. عملياً تُسرَّع الخوارزمية بالانزياحات والانهيار للتقارب في O(n) خطوة.

خوارزمية QR مع الانزياحات هي الطريقة المفضلة لمسائل القيم الذاتية الكثيفة وهي منفَّذة في دالة dgeev في LAPACK (مصفوفات عامة) وdsyev (مصفوفات متماثلة). للمصفوفات المتماثلة، تتقارب المتتالية نحو مصفوفة قطرية تكشف جميع القيم الذاتية مباشرةً.

الاستقرار العددي: لماذا QR يتفوق على المعادلات الاعتيادية

رقم التكييف لنظام خطي يقيس مقدار تغيّر الحل نسبةً إلى اضطرابات البيانات. لمسألة المربعات الصغرى min ‖Ax − b‖²، رقم التكييف ذو الصلة هو κ(A). الحل عبر المعادلات الاعتيادية يُدخل AᵀA، الذي عدد شرطه κ(A)². هذا التربيع يمكن أن يكون كارثياً: إن كان κ(A) = 10⁶ (درجة خفيفة من سوء التكييف للبيانات الحقيقية)، فإن κ(AᵀA) = 10¹² وتُفقد ١٢ خانة دقة قبل البدء بالحل.

تحليل QR يتفادى هذا التربيع. لأن Q متعامدة، فالنظام Rx = Qᵀb له عدد شرط κ(R) = κ(A) وليس κ(A)². التحويل Qᵀb لا يُسوّئ الأمور قط — التحويلات المتعامدة تحفظ جميع المعايير والزوايا بدقة. هذا هو السبب الجوهري لكون تحليل QR هو الطريقة المفضلة لحساب المربعات الصغرى في أي تطبيق حساس عددياً.

مقارنة أعداد الشرط
\kappa(A^T A) = \kappa(A)^2 \gg \kappa(R) = \kappa(A)
عدد شرط المعادلات الاعتيادية AᵀA هو κ(AᵀA) = κ(A)²، بينما عدد شرط نظام QR هو κ(R) = κ(A). للبيانات سيئة التكييف، يفقد نهج QR نصف عدد خانات الدقة التي يفقدها نهج المعادلات الاعتيادية.
الأثر الهندسي

تحليل QR هو الخوارزمية وراء numpy.linalg.lstsq، ومشغّل الشرطة المائلة العكسية في MATLAB للأنظمة الزائدة التحديد، وsccipy.linalg.qr. كلما ضبطت نموذجاً على بيانات — انحدار خطي، ملاءمة متعددة الحدود، ملاءمة أسية — فأنت تحل مسألة مربعات صغرى، وأي محلّل محكم الصياغة يستخدم تحليل QR. خوارزمية QR للقيم الذاتية هي محرّك numpy.linalg.eig وsccipy.linalg.eigh وكل كود تحليل الاهتزازات الإنشائية والكيمياء الكمية الذي يحتاج قيماً ذاتية للمصفوفات الكثيفة. في معالجة الإشارات، تظهر خوارزميات QR في الترشيح التكيفي (RLS) وتقدير اتجاه الوصول (خوارزمية MUSIC) وتشكيل الحزم — حيثما يجب تحديث مصفوفة التباين المشترك بشكل تدريجي وكفوء.

أبرز ما تعلمناه

يحلّل تحليل QR المصفوفة A = QR إلى متعامدة Q ومثلثية علوية R. يمكن حسابه عبر غرام-شميدت (واضحة مفاهيمياً، النسخة المعدَّلة مقبولة عددياً)، أو انعكاسات هاوس-هولدر (مستقرة عددياً، مستخدمة في LAPACK)، أو دورانات غيفنز (الأفضل للمصفوفات المتفرقة أو الشريطية). لمسائل المربعات الصغرى، يتفادى QR تربيع رقم التكييف: حل Rx = Qᵀb يكلف κ(A) فحسب مقابل κ(A)² للمعادلات الاعتيادية. خوارزمية QR — حساب تحليلات QR بشكل متكرر وعكس الحاصل — تتقارب نحو القيم الذاتية لأي مصفوفة، مما يجعل تحليل QR العمود الفقري لحساب القيم الذاتية الكثيفة في العالم.