تحلل كيو آر

الحلول الحسابية QR لحساب القيم لمعامل التحول الخطي، والتي تعتبر واحدة من 10 خوارزميات الأكثر أهمية في القرن 20. وقد اكتشف بشكل مستقل من قبل عالم الكمبيوتر البريطاني جون GF فرانسيس في 1959 ، وعالم الرياضيات السوفياتي فيرا في عام 1961.

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

${\displaystyle A=QR,\,}$

حيث أن Q عبارة عن مصفوفة متعامدة( أعمدتها هي متجهات متعامدة بمعني ان Q^TQ = I)) و أيضا Rعبارة عن مصفوفة ثلاثية ( وتسمى أيضا المصفوفة الثلاثية اليمنى ).

هذا شامل المصفوفة المربعة A وايضا مصفوفة الوحدة Q من خلال(Q*Q = I). في حالة أن A ليس لها معكوس بالتالي التحليل له حالة خاصة بحيث نحتاج بأن تكون عناصر القطر موجبة .

بشكل عام يمكننا ان نحلل المصفوفة المعقدة 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₂ تمتلك الأعمدة المتعامدة

Golub & Van Loan (1996, §5.2) call Q₁R₁ the thin QR factorization of A; Trefethen and Bau يدعى this the تخفيض عملية تحليل الQR.[1]

في حالة ان المصفوفة A هوعبارة عن رتبة كاملة لقيمة ال n بالتالي بنحتاج إلى ان عناصر القطر تكون موجبة من ال R₁ و R₁وQ₁ مختلفه، لكن بصورة عامةQ₂ ليست كذلك . و R₁ يساوي العناصر الثلاثية من تحليل كوليسكي

A (= ATA
في حالة ان قيمة A حقيقية

بالقياس، يمكن أن نحدد قيم QL، RQ، وLQ التحليل، مع L كونها المصفوفة الثلاثية السفلى .

هناك عدة طرق لحساب تحليل QR ، مثل Gram–Schmidt process, Householder transformations, or Givens rotations. لكل طريقة عدد من المزايا والعيوب.

اباعتبار Gram–Schmidt وتطبيقها على أعمدة المصفوفه كاملة الرتبة ${\displaystyle A=[\mathbf {a} _{1},\cdots ,\mathbf {a} _{n}]}$, في الداخل ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{\top }\mathbf {w} }$ أو ${\displaystyle \langle \mathbf {v} ,\mathbf {w} \rangle =\mathbf {v} ^{*}\mathbf {w} }$ في الحالات المعقدة

يعرف الإسقاط :

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

then:

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

بإعادة ترتيب المعادلات أعلاه حيث ${\displaystyle \mathbf {a} _{i}}$s على اليسار، وذلك باستخدام ${\displaystyle \mathbf {e} _{i}}$ كون هي متجهات الوحدة:

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

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

${\displaystyle A=QR}$

حيث :

${\displaystyle Q=\left[\mathbf {e} _{1},\cdots ,\mathbf {e} _{n}\right]\qquad {\text{and}}\qquad R={\begin{pmatrix}\langle \mathbf {e} _{1},\mathbf {a} _{1}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{1},\mathbf {a} _{3}\rangle &\ldots \\0&\langle \mathbf {e} _{2},\mathbf {a} _{2}\rangle &\langle \mathbf {e} _{2},\mathbf {a} _{3}\rangle &\ldots \\0&0&\langle \mathbf {e} _{3},\mathbf {a} _{3}\rangle &\ldots \\\vdots &\vdots &\vdots &\ddots \end{pmatrix}}.}$

التحليل RQ يحول المصفوفة A إلى مصفوفة ثلاثية عليا R (المعروف أيضا باسم المصفوفة الثلاثية اليمنى) والمصفوفة المتعامدةQ.

والفرق الوحيد بالنسبة التحليل QR هو ترتيب هذه المصفوفات.

تحليل ال QR هو the Gram–Schmidt متعامدة من الأعمدة ل A, والتي تبدأ من العمود الأول.

تحليل ال QR هو the Gram–Schmidt متعامدة من الصفوف ل A, والتي تبدأ من الصف الاخير.

Householder معكوس ل QR-تحليل: الهدف إيجاد علاقة خطيت تغير المتجه ${\displaystyle x}$ إلى متجه بنفس الطول بعلاقة خطية ${\displaystyle e_{1}}$. سنستخدم الإسقاط المتعامد (Gram-Schmidt) لكن هذا غير مستقر عدديا إذا كان المتجه ${\displaystyle x}$ و ${\displaystyle e_{1}}$ قريبين للتعامد. بدلا من, the Householder معكوس خلال الخط المنقط (اختيار الزاوية بين ${\displaystyle x}$ and ${\displaystyle e_{1}}$). الزاوية القصوى تقريبا 45 درجة.

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

Q يمكن استخدامها لتعكس المتجهات أحيانا بجميع الإحداثيات ولكن احداثي واحد ممكن يختفي.

باعتبار ان ${\displaystyle \mathbf {x} }$ ثابت الابعاد للاعمدة المتجهات ل ${\displaystyle A}$ مثل ${\displaystyle \|\mathbf {x} \|=|\alpha |}$ للمقياس α. لو الطريقة نفذت باستخدام عدد فاصل عائم, وايضا α لابد ان تحصل على إشارة معاكسه كما k-th وتنسيق من ${\displaystyle \mathbf {x} }$ ,بينما ${\displaystyle x_{k}}$ أن تكون محور التنسيق والتي بعدها كل الإدخالات 0 في مصفوفة ذات الشكل الثلاثي العلويA's، لتجنب فقدان أهمية المصفوفة . في الحالات المعقدة وضع :

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

(Stoer & Bulirsch 2002, p. 225) واستبدال التحويل بتحويل مترافق ل Q أدناه .

حيث ${\displaystyle \mathbf {e} _{1}}$ هي متجهة (1,0,...,0)T, ||·|| هو القاعدة الإقليدية و${\displaystyle I}$ عبارة عن مصفوفة متطابقة m-by-m, باعتبار

${\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1},}$

${\displaystyle \mathbf {v} ={\mathbf {u} \over \|\mathbf {u} \|},}$

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

أو باعتبار ان ${\displaystyle A}$ مركب أو معقد:

${\displaystyle Q=I-(1+w)\mathbf {v} \mathbf {v} ^{H}}$, where ${\displaystyle w=\mathbf {x} ^{H}\mathbf {v} \mathbf {/} \mathbf {v} ^{H}\mathbf {x} }$

باعتبار ان حيث ${\displaystyle \mathbf {x} ^{H}}$ هو تحويل مترافق (tranjugate) من ${\displaystyle \mathbf {x} }$

${\displaystyle Q}$ مصفوفة m-by-m و : ${\displaystyle Q\mathbf {x} =(\alpha ,0,\cdots ,0)^{T}.\,}$

وبهذا يمكن أن تستخدم تدريجيا لتحويل m-by-n مصفوفة A إلى النموذج الثلاثي العلوي. أولا، ضربنا A مع المصفوفة Q₁ لنحصل عندما نختار أول عمود من المصفوفة x. هذه النتائج في المصفوفة Q₁A مع الأصفار في العمود الأيسر (باستثناء الصف الأول).

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

هذا يمكن أن يتكرر ل A′(تم الحصول عليها من Q₁A بحذف الصف الأول والعمود الأول)، مما أدى إلى مصفوفة Q′₂. لاحظ أن Q′₂ أصغر من Q₁. لأن نريد حقا أن تعمل على Q₁A بدلا من A′ نحن بحاجة إلى توسيعه ليشمل الجانب الأيسر العلوي، واستكمال في 1، أو بشكل عام:

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

بعد بمقدار ${\displaystyle t}$ من التكرارات

${\displaystyle t=\min(m-1,n)}$,

في المصفوفة العلوية الثلاثية مثل

${\displaystyle Q=Q_{1}^{T}Q_{2}^{T}\cdots Q_{t}^{T},}$

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

هذا الأسلوب لديه قدر أكبر من الاستقرار العددي من طريقة Gram–Schmidt أعلاه. ويبين الجدول التالي عدد العمليات في خطوة k-th ال من QR-التحليل، على افتراض مصفوفة مربعة مع حجم n.

Operation	Number of operations in the k-th step
multiplications	${\displaystyle 2(n-k+1)^{2}}$
additions	${\displaystyle (n-k+1)^{2}+(n-k+1)(n-k)+2}$
division	${\displaystyle 1}$
square root	${\displaystyle 1}$

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

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

عن طريق التحليل QR يمكن أن نحسب سلسلة التدوير للمعطيات. كل دورة تصفر عنصر في المصفوفة العمودية ، وتشكل مصفوفة ثلاثية علويةR. في سلسلة من كل تدوير المعطيات تشكل Q مصفوفة متعامدة. عمليا، لا يتم إجراء Givens rotations فعليا من خلال بناء مصفوفة كاملة والقيام بعملية ضرب المصفوفة. ويستخدم خطوات تدوير المعطيات بشكل مكافئ لمصفوفة الضرب، دون التعامل مع العناصر المتفرقة. تدوير المعطيات مفيد في الحالات التي تحتاج سوى عدد قليل نسبيا من العناصر القطرية لاجل ان تصبح اصفارا ، وبشكل متوازي مكافئة لتحويل ال Householder.

يمكن استخدام التحليل QR للعثور على القيمة المطلقة من المحددات لمصفوفة مربعة. افترض أن تحلل المصفوفة كما يلي ${\displaystyle A=QR}$ . لدينا

:${\displaystyle \det(A)=\det(Q)\cdot \det(R).}$

باعتبار أن Q احادية و ${\displaystyle |\det(Q)|=1}$

:${\displaystyle |\det(A)|=|\det(R)|={\Big |}\prod _{i}r_{ii}{\Big |},}$

حيث ${\displaystyle r_{ii}}$ هي العناصر القطرية ل R.

ولهذا، المحدد يساوي حاصل ضرب القيم الذاتية، لدينا

:${\displaystyle {\Big |}\prod _{i}r_{ii}{\Big |}={\Big |}\prod _{i}\lambda _{i}{\Big |},}$

حيث ${\displaystyle \lambda _{i}}$ القيمة الذاتية ل ${\displaystyle A}$.

يمكن تعميم الخصائص المذكورة أعلاه إلى غير المصفوفة المربعة المعقدة ${\displaystyle A}$ عن طريق إدخال تعريف QR-التحليل المصفوفة المربعة المعقدة واستبدال القيم الذاتية مع قيم احادية.

لنفترض أن التحليل QR لمصفوفة غير المربعة A:

:${\displaystyle A=Q{\begin{pmatrix}R\\O\end{pmatrix}},\qquad Q^{*}Q=I,}$

باعتبار أن ${\displaystyle O}$ مصفوفة صفرية , و ${\displaystyle Q}$ مصفوفة وحدة

من خصائص SVD ومحددا للمصفوفة، لدينا

:${\displaystyle {\Big |}\prod _{i}r_{ii}{\Big |}=\prod _{i}\sigma _{i},}$

حيث ${\displaystyle \sigma _{i}}$ القيمة الاحادية ل ${\displaystyle A}$.

لاحظ أن القيم الاحادية ل ${\displaystyle A}$و${\displaystyle R}$ متطابقة، على الرغم من القيم المعقدة الذاتية قد تكون مختلفة. ومع ذلك، إذاAمربعة، وفيما يلي صحيحا:

${\displaystyle {\prod _{i}\sigma _{i}}={\Big |}{\prod _{i}\lambda _{i}}{\Big |}.}$

في النهاية، التحليل QR يمكن استخدامها بكفاءة لحساب حاصل ضرب القيم الذاتية أو القيم الاحادية من مصفوفة.

QR التحليل مع تحوير الأعمدة ينتج مصفوفة التباديل P

${\displaystyle AP=QR\quad \iff A=QRP^{T}}$

تمحور العمود مفيد عندما المصفوفة A تكون رتبتها ناقصة. فإنه يمكن أيضا تحسين الدقة الرقمية .Pعادة ما يتم اختيارها بحيث عناصرالقطر من R لا تزيد: ${\displaystyle |r_{11}|\geq |r_{22}|\geq \ldots \geq |r_{nn}|}$. يمكن استخدامها للحصول على الرتبة الرقميه ل A بااقل الحسابات من تحليل القيمة الاحادية، تشكل أساس ما يسمى الكشف عن رتبة لوغاريتمات QR.

مقارنة بالمصفوفة المعكوسة، الحلول العكسية باستخدام التحليل QR هي أكثر استقرارا من الناحية العددية كما يتضح من انخفاض العددالشرطي. Parker Geophysical Inverse)) لحل الغير محددات (${\displaystyle m<n}$) المسالة الخطية ${\displaystyle Ax=b}$ حيث المصفوفة A لها أبعاد ${\displaystyle m\times n}$ ورتبة${\displaystyle m}$, أولا تحليل QR للمعكوس A: ${\displaystyle A^{T}=QR}$, حيث Q المصفوفة العمودية مثال${\displaystyle Q^{T}=Q^{-1}}$ , و R يمتلك شكل خاص : ${\displaystyle R={\begin{bmatrix}R_{1}\\0\end{bmatrix}}}$.

حيث ${\displaystyle R_{1}}$هو ${\displaystyle m\times m}$ مربع المصفوفة الثلاثية اليمنى ,والمصفوفة الصفرية تمتلك ابعاد ${\displaystyle (n-m)\times m}$.${\displaystyle (n-m)\times m}$. بعد بعض العمليات الحسابية حل المسألة الخطية ممكن ان تظهر كالاتي ${\displaystyle x=Q{\begin{bmatrix}(R_{1}^{T})^{-1}b\\0\end{bmatrix}}}$ حيث ممكن ان نجد ${\displaystyle R_{1}^{-1}}$ بواسطة Gaussian elimination ${\displaystyle (R_{1}^{T})^{-1}b}$ بطريقة مباشرة مصفوفة مثلثية . والطريقة الأخيرة يتمتع بقدر أكبر من الدقة وحساباته أقل.

لإيجاد الحل ل ${\displaystyle {\hat {x}}}$ للحساب (${\displaystyle m\geq n}$) بمسالة ${\displaystyle Ax=b}$ بحيث نقلل المعيار norm ${\displaystyle \|A{\hat {x}}-b\|}$, أولا تحليل QR ل A: ${\displaystyle A=QR}$. الحل يمكن أن يشرح كالاتي ${\displaystyle {\hat {x}}=R_{1}^{-1}(Q_{1}^{T}b)}$, , حيث ${\displaystyle Q_{1}}$ عبارة عن مصفوفة ${\displaystyle m\times n}$ تحتوي على أول عمود ${\displaystyle n}$ يمثل أساسيات full ${\displaystyle Q}$ القاعده المتعامده وحيث أن ${\displaystyle R_{1}}$ كما سبق. ما يعادل حالة غير المحدد، يمكن أن نستخدم تبديل عكسي للسرعة وبدقة الحصول على ${\displaystyle {\hat {x}}}$ من دون معكوس ${\displaystyle R_{1}}$. (${\displaystyle Q_{1}}$ و${\displaystyle R_{1}}$ غالبا ما تقدمها المكتبات الرقمية باعتبارها "الاقتصادي" التحليل QR).

• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (الطبعة 3rd), Johns Hopkins, ISBN 978-0-8018-5414-9 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).
• Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 0-521-38632-2 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link). Section 2.8.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.10. QR Decomposition", Numerical Recipes: The Art of Scientific Computing (الطبعة 3rd), New York: Cambridge University Press, ISBN 978-0-521-88068-8 الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link)
• Stoer, Josef; Bulirsch, Roland (2002), Introduction to Numerical Analysis (الطبعة 3rd), Springer, ISBN 0-387-95452-X الوسيط |CitationClass= تم تجاهله (مساعدة); الوسيط |separator= تم تجاهله (مساعدة)CS1 maint: ref=harv (link).

• بوابة جبر