7.3.1 تحليل QR (QR decomposition) 

كما نوقش في القسم السابق، يمكن الحصول على كسر أولي فيما بينه بالبحث عن الأعمدة المستقلة خطياً في محصّل سيلفستر بترتيب من اليسار إلى اليمين. ويتبين أن تحليل QR المتاح على نطاق واسع يمكن استخدامه لتحقيق هذا البحث.

اعتبر مصفوفة $ \mathbf{M} $ ذات أبعاد $ n \times m $. عندئذ توجد مصفوفة متعامدة (orthogonal) $ \mathbf{Q} $ ذات أبعاد $ n \times n $ ومصفوفة مثلثية علوية (upper triangular) $ \mathbf{R} $ ذات أبعاد $ n \times m $ بحيث

$$ \mathbf {M} = \mathbf {Q R} $$

يسمى ذلك تحليل QR. توجد عدة طرق لإجراء التحليل. راجع ويكيبيديا (Wikipedia). إحدى الطرق هي إجراء شميدت للتعامد (Schmidt orthonormalization) الذي نوقش في القسم 3.2. في الواقع، أظهر المثال 3.2.2 أن $ \mathbf{Q} = \bar{\mathbf{A}}\bar{\mathbf{R}} $ لمصفوفة $ \mathbf{A} $ غير منفردة مع $ \mathbf{Q} $ متعامدة و$ \bar{\mathbf{R}} $ مثلثية علوية. لتكن $ \mathbf{R} := \bar{\mathbf{R}}^{-1} $. عندئذ فإن $ \mathbf{Q} = \bar{\mathbf{A}}\bar{\mathbf{R}} $ تعني $ \mathbf{A} = \bar{\mathbf{Q}}\bar{\mathbf{R}}^{-1} = \mathbf{Q}\mathbf{R} $. وبما أن معكوس المصفوفة المثلثية العلوية هو مصفوفة مثلثية علوية، فقد أظهر المثال تحليل QR. في MATLAB يمكن الحصول على $ \mathbf{Q} $ و$ \mathbf{R} $ بكتابة $ [\mathbf{q}, \mathbf{r}] = \mathbf{qr}(\mathfrak{m}) $.

نناقش الآن استخدام التحليل. بما أن $ \mathbf{Q} $ متعامدة، فإن $ \mathbf{Q}^{-1} = \mathbf{Q}' \eqqcolon \bar{\mathbf{Q}} $. والضرب المسبق بـ $ \mathbf{Q}^{-1} $ على $ \mathbf{M} = \mathbf{QR} $ يعطينا

$$ \bar {\mathbf {Q}} \mathbf {M} = \mathbf {R} $$

حيث إن $ \mathbf{R} $ مصفوفة مثلثية علوية لها الأبعاد نفسها كـ $ \mathbf{M} $. وبما أن $ \bar{\mathbf{Q}} $ تعمل على صفوف $ \mathbf{M} $، فإن استقلال الأعمدة خطياً في $ \mathbf{M} $ يبقى محفوظاً في أعمدة $ \mathbf{R} $. وبعبارة أخرى، إذا كان عمود في $ \mathbf{R} $ معتمداً خطياً على الأعمدة الواقعة على يساره (LHS)، فإن العمود المناظر في $ \mathbf{M} $ كذلك. والآن بما أن $ \mathbf{R} $ على شكل مثلث علوي، فإن عمودها $ m $ مستقل خطياً عن الأعمدة الواقعة على يساره إذا وفقط إذا كان عنصره $ m $ في الموضع القطري غير صفري. وبالتالي باستخدام $ \mathbf{R} $ يمكن تحديد الأعمدة المستقلة خطياً في $ \mathbf{M} $، من اليسار إلى اليمين، بمجرد الفحص.

لنطبق تحليل QR على المحصّل في المثال 7.3.1. نكتب

$$ \begin{array}{l} d = \left[ \begin{array}{l l l l l} 1 0 & 1 6 & 1 5 & 7 & 2 \end{array} \right]; n = \left[ \begin{array}{l l l l l} - 2 0 & 3 & 1 & 6 & 0 \end{array} \right]; \\ s = [ d 0 0 0; n 0 0 0; 0 d 0 0; 0 n 0 0; \dots \\ 0 0 d 0; 0 0 n 0; 0 0 0 d; 0 0 0 n ] ^ {\prime}; \\ \end{array} $$

$$ [ q, r ] = q r (s) $$

وبما أننا لا نحتاج إلى $ \mathbf{Q} $، نعرض فقط $ \mathbf{R} $:

$$ r = \left[ \begin{array}{c c c c c c c c} - 2 5. 1 & 3. 7 & - 2 0. 6 & 1 0. 1 & - 1 1. 6 & 1 1. 0 & - 4. 1 & 5. 3 \\ 0 & - 2 0. 7 & - 1 0. 3 & 4. 3 & - 7. 2 & 2. 1 & - 3. 6 & 6. 7 \\ 0 & 0 & - 1 0. 2 & - 1 5. 6 & - 2 0. 3 & 0. 8 & - 1 6. 8 & 9. 6 \\ 0 & 0 & 0 & 8. 9 & - 3. 5 & - 1 7. 9 & - 1 1. 2 & 7. 3 \\ 0 & 0 & 0 & 0 & - 5. 0 & 0 & - 1 2. 0 & - 1 5. 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & - 2. 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & - 4. 6 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right] $$

نرى أن المصفوفة مثلثية علوية. وبما أن العمود السادس له 0 في عنصره السادس (موضع قطري)، فهو معتمد خطياً على الأعمدة الواقعة على يساره. وكذلك العمود الأخير. ولتحديد ما إذا كان عمود ما معتمداً خطياً نحتاج فقط إلى معرفة ما إذا كان العنصر القطري صفراً أم لا. ومن ثم يمكن تبسيط المصفوفة إلى

$$ r = \left[ \begin{array}{c c c c c c c c} d & x & x & x & x & x & x & x \\ 0 & n & x & x & x & x & x & x \\ 0 & 0 & d & x & x & x & x & x \\ 0 & 0 & 0 & n & x & x & x & x \\ 0 & 0 & 0 & 0 & d & 0 & x & x \\ 0 & 0 & 0 & 0 & 0 & 0 & x & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & d & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right] $$

حيث إن $ d, n $ و$ x $ تمثل عناصر غير صفرية، كما أن $ d $ تشير إلى عمود $ D $ و$ n $ تشير إلى عمود $ N $. نرى أن كل عمود $ D $ مستقل خطياً عن الأعمدة الواقعة على يساره، ولا يوجد سوى عمودين مستقلين خطياً من أعمدة $ N $. وبالتالي باستخدام تحليل QR نحصل مباشرةً على $ \mu $ وعمود $ N $ المعتمد الرئيس. في دوال التحويل القياسية يمكننا استخدام rank أو qr لإيجاد $ \mu $. أما في الحالة المصفوفية فإن استخدام rank غير ملائم؛ وسنستخدم تحليل QR.