تحليل QR

يمكن تحليل أي مصفوفة مربعة حقيقية A إلى:

${\displaystyle A=QR,}$

حيث Q هي مصفوفة متعامدة (أعمدتها عبارة عن متجهات وحدة متعامدة بمعنى${\displaystyle Q^{\textsf {T}}=Q^{-1}}$و R مصفوفة مثلثية علوية (تُسمى أيضًا مصفوفة مثلثية يمنى). إذا كانت A قابلة للعكس ، فإن التحليل يكون فريدًا إذا اشترطنا أن تكون عناصر القطر الرئيسي لـ R موجبة .

أما إذا كانت A مصفوفة مربعة مركبة، فإنه يوجد تحليل A = QR حيث Q مصفوفة وحدوية (وبالتالي منقولة المرافق).${\displaystyle Q^{\dagger }=Q^{-1}}$).

إذا كانت المصفوفة A تحتوي على n عمودًا مستقلًا خطيًا ، فإن أول n عمودًا من Q تُشكّل أساسًا متعامدًا لفضاء أعمدة A. وبشكل أعم، تُشكّل أول k عمودًا من Q أساسًا متعامدًا للفضاء الممتد لأول k عمودًا من A لأي عدد صحيح موجب 1 ≤ k ≤ n . ^{[ 1 ]} إن حقيقة أن أي عمود k من A يعتمد فقط على أول k عمودًا من Q تُقابل الشكل المثلثي لـ R. ^{[ 1 ]} 

بشكل عام، يمكننا تحليل مصفوفة معقدة من الرتبة m × n، A ، حيث m ≥ n ، إلى حاصل ضرب مصفوفة وحدوية من الرتبة m × m ، Q، ومصفوفة مثلثية علوية من الرتبة m × n، R. وبما أن الصفوف ( m − n ) السفلية من مصفوفة مثلثية علوية من الرتبة m × n تتكون بالكامل من أصفار، فإنه من المفيد غالبًا تقسيم R ، أو كل من R و Q :

${\displaystyle A=QR=Q{\begin{bmatrix}R_{1}\\0\end{bmatrix}}={\begin{bmatrix}Q_{1}&Q_{2}\end{bmatrix}}{\begin{bmatrix}R_{1}\\0\end{bmatrix}}=Q_{1}R_{1},}$

حيث R ₁ هي مصفوفة مثلثية علوية من الرتبة n × n ، و 0 هي مصفوفة صفرية من الرتبة ( m − n ) × n ، و Q ₁ هي من الرتبة m × n ، و Q ₂ هي من الرتبة m × ( m − n ) ، و Q ₁ و Q ₂ كلاهما لهما أعمدة متعامدة.

يُطلق غولوب وفان لون (1996 ، §5.2) _على Q1R1 اسم تحليل QR الرقيق _{للمصفوفة} A ؛ ويُطلق عليه تريفثن وباو اسم تحليل QR المُختزل . ^{[ 1 ]} إذا كانت A من الرتبة n الكاملة ، واشترطنا أن تكون العناصر القطرية لـ R1 موجبة، فإن R1 وQ1 يكونان وحيدين، ولكن Q2 _ليس كذلك بشكل عام . عندئذٍ ، يكون _R1 مساويًا _{للعامل المثلثي} العلوي لتحليل تشوليسكي للمصفوفة A * A ( أي ATA إذا كانت A _حقيقية ⁾ . 

وبالمثل، يمكننا تعريف تحليلات QL و RQ و LQ، حيث L عبارة عن مصفوفة مثلثية سفلية .

لنفترض تطبيق عملية غرام-شميدت على أعمدة مصفوفة الرتبة العمودية الكاملة${\displaystyle A={\begin{bmatrix}\mathbf {a} _{1}&\cdots &\mathbf {a} _{n}\end{bmatrix}}}$، مع المنتج الداخلي${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\textsf {T}}\mathbf {w} }$(أو${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\dagger }\mathbf {w} }$(للحالات المعقدة).

حدد الإسقاط :

${\displaystyle \operatorname {proj} _{\mathbf {u} }\mathbf {a} ={\frac {\left\langle \mathbf {u} ,\mathbf {a} \right\rangle }{\left\langle \mathbf {u} ,\mathbf {u} \right\rangle }}{\mathbf {u} }}$

ثم:

${\displaystyle {\begin{aligned}\mathbf {u} _{1}&=\mathbf {a} _{1},&\mathbf {e} _{1}&={\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}\\\mathbf {u} _{2}&=\mathbf {a} _{2}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{2},&\mathbf {e} _{2}&={\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}\\\mathbf {u} _{3}&=\mathbf {a} _{3}-\operatorname {proj} _{\mathbf {u} _{1}}\mathbf {a} _{3}-\operatorname {proj} _{\mathbf {u} _{2}}\mathbf {a} _{3},&\mathbf {e} _{3}&={\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\\&\;\;\vdots &&\;\;\vdots \\\mathbf {u} _{k}&=\mathbf {a} _{k}-\sum _{j=1}^{k-1}\operatorname {proj} _{\mathbf {u} _{j}}\mathbf {a} _{k},&\mathbf {e} _{k}&={\frac {\mathbf {u} _{k}}{\|\mathbf {u} _{k}\|}}\end{aligned}}}$

يمكننا الآن التعبير عن${\displaystyle \mathbf {a} _{i}}$s على أساسنا المتعامد المحسوب حديثًا:

${\displaystyle {\begin{aligned}\mathbf {a} _{1}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{1}\right\rangle \mathbf {e} _{1}\\\mathbf {a} _{2}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{2}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{2}\right\rangle \mathbf {e} _{2}\\\mathbf {a} _{3}&=\left\langle \mathbf {e} _{1},\mathbf {a} _{3}\right\rangle \mathbf {e} _{1}+\left\langle \mathbf {e} _{2},\mathbf {a} _{3}\right\rangle \mathbf {e} _{2}+\left\langle \mathbf {e} _{3},\mathbf {a} _{3}\right\rangle \mathbf {e} _{3}\\&\;\;\vdots \\\mathbf {a} _{k}&=\sum _{j=1}^{k}\left\langle \mathbf {e} _{j},\mathbf {a} _{k}\right\rangle \mathbf {e} _{j}\end{aligned}}}$

أين${\displaystyle \left\langle \mathbf {e} _{i},\mathbf {a} _{i}\right\rangle =\left\|\mathbf {u} _{i}\right\|}$يمكن كتابة ذلك في شكل مصفوفة :

${\displaystyle A=QR}$

أين:

${\displaystyle Q={\begin{bmatrix}\mathbf {e} _{1}&\cdots &\mathbf {e} _{n}\end{bmatrix}}}$

و

${\displaystyle R={\begin{bmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{1},\mathbf {a} _{n}\rangle \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{2},\mathbf {a} _{n}\rangle \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\cdots &\langle \mathbf {e} _{3},\mathbf {a} _{n}\rangle \\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\cdots &\langle \mathbf {e} _{n},\mathbf {a} _{n}\rangle \\\end{bmatrix}}.}$

مثال

ضع في اعتبارك تفكيك

${\displaystyle A={\begin{bmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{bmatrix}}.}$

تذكر أن المصفوفة المتعامدة${\displaystyle Q}$يمتلك العقار${\displaystyle Q^{\textsf {T}}Q=I}$.

بعد ذلك، يمكننا حساب${\displaystyle Q}$عن طريق غرام-شميدت على النحو التالي:

${\displaystyle {\begin{aligned}U={\begin{bmatrix}\mathbf {u} _{1}&\mathbf {u} _{2}&\mathbf {u} _{3}\end{bmatrix}}&={\begin{bmatrix}12&-69&-58/5\\6&158&6/5\\-4&30&-33\end{bmatrix}};\\Q={\begin{bmatrix}{\frac {\mathbf {u} _{1}}{\|\mathbf {u} _{1}\|}}&{\frac {\mathbf {u} _{2}}{\|\mathbf {u} _{2}\|}}&{\frac {\mathbf {u} _{3}}{\|\mathbf {u} _{3}\|}}\end{bmatrix}}&={\begin{bmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{bmatrix}}.\end{aligned}}}$

وهكذا، لدينا

${\displaystyle {\begin{aligned}Q^{\textsf {T}}A&=Q^{\textsf {T}}Q\,R=R;\\R&=Q^{\textsf {T}}A={\begin{bmatrix}14&21&-14\\0&175&-70\\0&0&35\end{bmatrix}}.\end{aligned}}}$

انعكاس هاوسهولدر (أو تحويل هاوسهولدر ) هو تحويل يأخذ متجهًا ويعكسه حول مستوى أو مستوى فائق . يمكننا استخدام هذه العملية لحساب تحليل QR لمصفوفة من الرتبة m × n${\displaystyle A}$حيث m ≥ n .

يمكن استخدام Q لعكس متجه بطريقة تجعل جميع الإحداثيات تختفي باستثناء إحداثية واحدة.

يترك${\displaystyle \mathbf {x} }$ليكن متجه عمودي حقيقي عشوائي ذو m بُعد${\displaystyle A}$بحيث${\displaystyle \|\mathbf {x} \|=|\alpha |}$بالنسبة للقيمة العددية α ، يجب أن تأخذ α نفس إشارة${\displaystyle k}$الإحداثي رقم - من${\displaystyle \mathbf {x} }$، أين${\displaystyle x_{k}}$يُفترض أن تكون إحداثية المحور التي بعدها تصبح جميع المدخلات أصفارًا في الشكل المثلثي العلوي النهائي للمصفوفة A. إذا تم تنفيذ الخوارزمية باستخدام حسابات الفاصلة العائمة ، فيجب أن تأخذ α الإشارة المعاكسة لتجنب فقدان الدلالة (على سبيل المثال، عندما${\displaystyle \mathbf {x} }$يكاد يكون على خط مستقيم واحد مع${\displaystyle \mathbf {e} _{1}}$،${\displaystyle \|\mathbf {u} \|}$يصبح "صغيراً" و${\displaystyle \mathbf {u} /\|\mathbf {u} \|}$غير مستقر عدديًا؛ الحالة القصوى هي${\displaystyle \|\mathbf {u} \|=0}$مما يؤدي إلى أن ينتج عن القسمة السابقة قيمة NaN ).

في الحالة المعقدة، المجموعة ^{[ 2 ]}

${\displaystyle \alpha =-e^{i\arg x_{k}}\|\mathbf {x} \|}$

واستبدل التبديل بالتبديل المرافق في بناء Q أدناه.

ثم أين${\displaystyle \mathbf {e} _{1}}$المتجه [1 0 ⋯ 0] ^T ، و || · || هو المعيار الإقليدي و${\displaystyle I}$هي مصفوفة وحدة من الرتبة m × m ، مجموعة

${\displaystyle {\begin{aligned}\mathbf {u} &=\mathbf {x} -\alpha \mathbf {e} _{1},\\\mathbf {v} &={\frac {\mathbf {u} }{\|\mathbf {u} \|}},\\Q&=I-2\mathbf {v} \mathbf {v} ^{\textsf {T}}.\end{aligned}}}$

أو إذا${\displaystyle A}$الأمر معقد

${\displaystyle Q=I-2\mathbf {v} \mathbf {v} ^{\dagger }.}$

${\displaystyle Q}$هي مصفوفة هاوسهولدر من الرتبة m × m ، وهي متناظرة ومتعامدة (هيرميتية ووحدوية في الحالة المركبة)، و

${\displaystyle Q\mathbf {x} ={\begin{bmatrix}\alpha \\0\\\vdots \\0\end{bmatrix}}.}$

يمكن استخدام هذه الطريقة لتحويل مصفوفة A _{ذات الأبعاد} m × n تدريجيًا إلى شكل مثلثي علوي. أولًا ، نضرب A بمصفوفة هاوسهولدر Q₁ التي نحصل عليها باختيار العمود الأول للمصفوفة x . ينتج عن ذلك مصفوفة Q₁A تحتوي على أصفار في العمود الأيسر (باستثناء الصف الأول).

${\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\cdots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}}$

يمكن تكرار هذه العملية للمصفوفة _A ′ (المُستخرجة من Q1A بحذف الصف الأول والعمود الأول)، مما ينتج عنه مصفوفة هاوسهولدر Q′2 . لاحظ أن Q′2 أصغر من Q1 . ولأننا نريد تطبيق العملية على Q1A بدلاً من A _{′ ،} نحتاج إلى توسيعها إلى الزاوية العلوية اليسرى، بإضافة الرقم 1، أو _{بشكل عام} :

${\displaystyle Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}.}$

بعد${\displaystyle t}$تكرارات هذه العملية،${\displaystyle t=\min(m-1,n)}$،

${\displaystyle R=Q_{t}\cdots Q_{2}Q_{1}A}$

هي مصفوفة مثلثية علوية. لذا، مع

${\displaystyle {\begin{aligned}Q^{\textsf {T}}&=Q_{t}\cdots Q_{2}Q_{1},\\Q&=Q_{1}^{\textsf {T}}Q_{2}^{\textsf {T}}\cdots Q_{t}^{\textsf {T}}\end{aligned}}}$

${\displaystyle A=QR}$هو تحليل QR لـ${\displaystyle A}$.

تتمتع هذه الطريقة بثبات عددي أكبر من طريقة غرام-شميدت المذكورة أعلاه.

في الاختبارات العددية، العوامل المحسوبة${\displaystyle Q_{c}}$و${\displaystyle R_{c}}$مُرضٍ ${\displaystyle {\frac {\|QR-Q_{c}R_{c}\|_{\infty }}{\|A\|_{\infty }}}=O(\varepsilon )}$ بدقة الآلة. كما يتم الحفاظ على التعامد:${\displaystyle \|Q_{c}^{\mathsf {T}}Q_{c}-I\|_{\infty }=O(\varepsilon )}$ومع ذلك، فإن دقة${\displaystyle Q_{c}}$و${\displaystyle R_{c}}$يتناقص مع رقم الحالة: ${\displaystyle \|Q-Q_{c}\|_{\infty }=O(\varepsilon \,\kappa _{\infty }(A)),\quad {\frac {\|R-R_{c}\|_{\infty }}{\|R\|_{\infty }}}=O(\varepsilon \,\kappa _{\infty }(A)).}$

لمثال جيد التكييف (${\displaystyle n=4000}$،${\displaystyle \kappa _{\infty }(A)\approx 3\times 10^{3}}$): ${\displaystyle {\frac {\|QR-Q_{c}R_{c}\|_{\infty }}{\|A\|_{\infty }}}\approx 1.6\times 10^{-15},}$${\displaystyle \|Q-Q_{c}\|_{\infty }\approx 1.6\times 10^{-15},}$${\displaystyle {\frac {\|R-R_{c}\|_{\infty }}{\|R\|_{\infty }}}\approx 4.3\times 10^{-14},}$${\displaystyle \|Q_{c}^{\mathsf {T}}Q_{c}-I\|_{\infty }\approx 1.1\times 10^{-13}.}$

في اختبار سيئ التكييف (${\displaystyle n=4000}$،${\displaystyle \kappa _{\infty }(A)\approx 4\times 10^{18}}$): ${\displaystyle {\frac {\|QR-Q_{c}R_{c}\|_{\infty }}{\|A\|_{\infty }}}\approx 1.3\times 10^{-15},}$${\displaystyle \|Q-Q_{c}\|_{\infty }\approx 5.2\times 10^{-4},}$${\displaystyle {\frac {\|R-R_{c}\|_{\infty }}{\|R\|_{\infty }}}\approx 1.2\times 10^{-4},}$${\displaystyle \|Q_{c}^{\mathsf {T}}Q_{c}-I\|_{\infty }\approx 1.1\times 10^{-13}.}$^{[ 3 ]}

يوضح الجدول التالي عدد العمليات في الخطوة k من عملية تحليل QR بواسطة تحويل هاوسهولدر، بافتراض مصفوفة مربعة بحجم n .

عملية	عدد العمليات في الخطوة رقم k
الضرب	${\displaystyle 2(n-k+1)^{2}}$
إضافات	${\displaystyle (n-k+1)^{2}+(n-k+1)(n-k)+2}$
قسم	${\displaystyle 1}$
الجذر التربيعي	${\displaystyle 1}$

بجمع هذه الأرقام على مدى n − 1 خطوة (لمصفوفة مربعة من الحجم n )، فإن تعقيد الخوارزمية (من حيث عمليات ضرب الأعداد العشرية) يُعطى بالصيغة التالية:

${\displaystyle {\frac {2}{3}}n^{3}+n^{2}+{\frac {1}{3}}n-2=O\left(n^{3}\right).}$

يمكن أيضًا حساب تحليلات QR باستخدام سلسلة من دورانات جيفنز . كل دوران يُصفّر عنصرًا في القطر الفرعي للمصفوفة، مُشكِّلًا بذلك مصفوفة R. ويُشكِّل دمج جميع دورانات جيفنز مصفوفة Q المتعامدة .

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

من الممكن حساب تحليل QR بسرعة باستخدام خوارزميات ضرب المصفوفات السريعة في وقت${\displaystyle O({n^{\omega }})}$ل${\displaystyle ~2.37\leq \omega <3}$[ ^{5 ] [ 6 ]​}