تحلل كيو آر

في الجبر الخطي، **تحليل QR**  لمصفوفة هو طريقة التحليل أو الإحلال *QR* وتعرف أيضا بطريقة عوامل، *QR* عبارة عن تحليل أو احلال المصفوفة *A* وادخالها في المعادلة:  A = QR, \, 

من مصفوفة متعامدة *Q* ومصفوفة ثلاثية *R*. كثيرا ماتستخدم طريقة التحليل *QR* لحل مسائل المربعات الخطية وايضا تعتبر من الأساسيات الخاصة لخوارزميات معامل التحول الخطي.

في حالة أن المصفوفة *A* تحتوي على عدد*N* من الأعمدة الخطية، والعمود الأول *N* من *Q* يشكل أساسا التعامد لمدى المصفوفة A, بالتحديد أول عمود K من *Q* أساس التعامد لإحصاء أو مدى أول عمود *K* من المصفوفة *A* ما بين *1 ≤ k ≤ n*.
في الحقيقة أن أي عمود*k* في المصفوفة *A* يعتمد فقط على الأعمدة *k* الأولى من المصفوفة *Q* وهو المسؤول عن التشكيل الثلاثي من .

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

## شرح الطريقة
أي تربيع للمصفوفة *A* يمكن أن يحلل كالاتي:

:  A = QR, \, 
حيث أن *Q* عبارة عن مصفوفة متعامدة (أعمدتها هي متجهات متعامدة بمعني ان *Q*T*Q* = *I*)
و أيضا Rعبارة عن مصفوفة ثلاثية (وتسمى أيضا المصفوفة الثلاثية اليمنى).

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

## المصفوفة المستطيلة
بشكل عام يمكننا ان نحلل المصفوفة المعقدة *m*×*n* *A* مع *m*&nbsp;≥&nbsp;*n* وايضا العملية *m*×*m* بمصفوفة الوحدة *Q* وايضا*m*×*n* بالمصفوفة الثلاثية العليا *R*.

 الصفوف السفلية (*m*−*n*) من *m*×*n* للمصفوفة الثلاثية تحتوي على الاصفار وهذا يساعد في إيجاد قيمة*R* أو *R* و *Q* بالكامل .
 :
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*1 عبارة عن *n*×*n* المصفوفة الثلاثية العليا
*0*عبارة عن (*m*&nbsp;−&nbsp;*n*)×*n* مصفوفة صفرية
*Q*1 عبارة عن *m*×*n*
, *Q*2 عبارة عن *m*×(*m*&nbsp;−&nbsp;*n*)
*Q*1 و *Q*2 تمتلك الأعمدة المتعامدة

 call *Q*1*R*1 the *thin QR factorization* of *A*; Trefethen and Bau يدعى this the *تخفيض عملية تحليل الQR*.

في حالة ان المصفوفة *A* هوعبارة عن رتبة كاملة لقيمة ال *n* بالتالي بنحتاج إلى ان عناصر القطر تكون موجبة من ال *R*1 و *R*1و*Q*1 مختلفه، لكن بصورة عامة*Q*2 ليست كذلك . و *R*1 يساوي العناصر الثلاثية من تحليل كوليسكي
 *A* (=&nbsp;*A*T*A*
 في حالة ان قيمة *A* حقيقية

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

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

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

يعرف الإسقاط :
:\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:
:
\begin{align}
 \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{align}


بإعادة ترتيب المعادلات أعلاه حيث \mathbf{a}_is على اليسار، وذلك باستخدام \mathbf{e}_i كون هي متجهات الوحدة:
:
\begin{align}
 \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{align}

حيث أن \langle\mathbf{e}_i,\mathbf{a}_i \rangle = \|\mathbf{u}_i\|. يمكن أن تكتب بشكل مصفوفة:
: A = Q R 
حيث :
: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}.

### مثال
نعتبر التحليل ل:
: A = 
\begin{pmatrix}
12 & -51 & 4 \\
6 & 167 & -68 \\
-4 & 24 & -41
\end{pmatrix}
.

باستدعاء المصفوفة المتعامدة Q has the property
: 
\begin{matrix}
 Q^T \,Q = I.
\end{matrix}


نقوم بحساب Q by means of Gram–Schmidt كالتالي:
: 
U = 
\begin{pmatrix}
\mathbf u_1 & \mathbf u_2 & \mathbf u_3
\end{pmatrix}
=
\begin{pmatrix}
12 & -69 & -58/5 \\
6  & 158 & 6/5 \\
-4 &  30 & -33
\end{pmatrix};

: 
Q = 
\begin{pmatrix}
\frac{\mathbf u_1}{\|\mathbf u_1\|} &
\frac{\mathbf u_2}{\|\mathbf u_2\|} &
\frac{\mathbf u_3}{\|\mathbf u_3\|}
\end{pmatrix}
=
\begin{pmatrix}
     6/7    &    -69/175   &   -58/175   \\
     3/7    &    158/175   &     6/175   \\
    -2/7    &      6/35    &   -33/35
\end{pmatrix}.


نحصل على:
: 
\begin{matrix}
 Q^{T} A = Q^{T}Q\,R = R;
\end{matrix}

: 
\begin{matrix}
 R = Q^{T}A =
\end{matrix}
\begin{pmatrix}
    14  &  21          &            -14 \\
     0  & 175          &           -70 \\
     0  &   0          &          35
\end{pmatrix}.


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

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

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

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

## استخدام معكوس Householder
تصغير|Householder معكوس ل QR-تحليل: الهدف إيجاد علاقة خطيت تغير المتجه <math>x</math> إلى متجه بنفس الطول بعلاقة خطية <math>e_1</math>. سنستخدم الإسقاط المتعامد (Gram-Schmidt) لكن هذا غير مستقر عدديا إذا كان المتجه <math>x</math> و <math>e_1</math> قريبين للتعامد. بدلا من, the Householder معكوس خلال الخط المنقط (اختيار الزاوية بين <math>x</math> and <math>e_1</math>). الزاوية القصوى تقريبا 45 درجة.
Householder انعكاس ويسمى أيضا( التحويل الخطي) هو التحويل الذي يأخذ المتجهات ويعكسها حول المستوى أو المستوى الفائق. يمكننا استخدام هذه العملية لحساب تحليل*QR* من مصفوفة *m*-by-*n* مصفوفة A مع *m*&nbsp;≥&nbsp;*n*.

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

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

 واستبدال التحويل بتحويل مترافق ل *Q* أدناه .
 حيث \mathbf{e}_1 هي متجهة (1,0,...,0)T, ||·|| هو القاعدة الإقليدية وI عبارة عن مصفوفة متطابقة *m*-by-*m*, باعتبار
: \mathbf{u} = \mathbf{x} - \alpha\mathbf{e}_1,
: \mathbf{v} = {\mathbf{u}\over\|\mathbf{u}\|},
: Q = I - 2 \mathbf{v}\mathbf{v}^T.

أو باعتبار ان A مركب أو معقد:
: Q = I - (1+w)\mathbf{v}\mathbf{v}^H, where w = \mathbf{x}^H\mathbf{v}\mathbf{/}\mathbf{v}^H\mathbf{x} 
باعتبار ان
حيث \mathbf{x}^H هو تحويل مترافق (tranjugate) من \mathbf{x}

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

وبهذا يمكن أن تستخدم تدريجيا لتحويل *m*-by-*n* مصفوفة *A* إلى النموذج الثلاثي العلوي. أولا، ضربنا *A* مع المصفوفة *Q*1 لنحصل عندما نختار أول عمود من المصفوفة **x**. هذه النتائج في المصفوفة *Q*1*A* مع الأصفار في العمود الأيسر (باستثناء الصف الأول).
 :Q_1A = \begin{bmatrix}
                   \alpha_1&\star&\dots&\star\\
                      0    &     &    &    \\
                   \vdots  &     &  A' &    \\
                      0    &     &     & \end{bmatrix}

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

:Q_k = \begin{pmatrix}
                  I_{k-1} & 0\\
                   0  & Q_k'\end{pmatrix}.

بعد بمقدار t من التكرارات
 t = \min(m-1, n),

في المصفوفة العلوية الثلاثية مثل
: Q = Q_1^T Q_2^T \cdots Q_t^T, 
A = QR هي تحليل QR A.

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

تلخيص هذه الأرقام على مدى *n*&nbsp;−&nbsp;1 الخطوات (لمصفوفة المربعة لحجم *n*)، وصعوبة الخوارزميات (من حيث ضرب النقطة ) بواسطة :
 :\frac{2}{3}n^3+n^2+\frac{1}{3}n-2=O(n^3).

### مثال
لنحسب التحليل ل:
: A = \begin{pmatrix}
12 & -51 & 4 \\
6 & 167 & -68 \\
-4 & 24 & -41 \end{pmatrix}.

في البداية نوجد معكوس الصف الأول للمصفوفة *A*, vector \mathbf{a}_1 = (12, 6, -4)^T, to \|\mathbf{a}_1\| \;\mathrm{e}_1 = (14, 0, 0)^T.

الآن,
: \mathbf{u} = \mathbf{x} + \alpha\mathbf{e}_1,
و
: \mathbf{v} = {\mathbf{u}\over\|\mathbf{u}\|}.
هنا,
: \alpha = -14 and \mathbf{x} = \mathbf{a}_1 = (12, 6, -4)^T

لذلك
: \mathbf{u} = (-2, 6, -4)^T=({2})(-1, 3, -2)^T and \mathbf{v} = {1 \over \sqrt{14}}(-1, 3, -2)^T, and then
:Q_1 = I - {2 \over \sqrt{14} \sqrt{14}} \begin{pmatrix} -1 \\ 3 \\ -2 \end{pmatrix}\begin{pmatrix} -1 & 3 & -2 \end{pmatrix}
: = I - {1 \over 7}\begin{pmatrix}
1 & -3  & 2 \\
-3 & 9 & -6 \\
2  & -6  & 4
\end{pmatrix}
: = \begin{pmatrix}
6/7 & 3/7   &  -2/7 \\
3/7  &-2/7  &  6/7 \\
-2/7 & 6/7  &   3/7 \\
\end{pmatrix}.

الآن لاحظ:
:Q_1A = \begin{pmatrix}
14 & 21 & -14 \\
0 & -49 & -14 \\
0 & 168 & -77 \end{pmatrix},
حصلنا تقريبا على مصفوف مثلثة. ونحتاج فقط لتصفير مدخل (3, 2) .

خذ (1, 1) [\det(Q)|=1</math>
 :<math>|\det(A)|=|\det(R)|=\Big|\prod_{i} r_{ii}\Big|,</math>

حيث <math>r_{ii}</math> هي العناصر القطرية ل ''R''.

ولهذا، المحدد يساوي حاصل ضرب القيم الذاتية، لدينا
 :<math>\Big|\prod_{i} r_{ii}\Big|=\Big|\prod_{i} \lambda_{i}\Big|,</math>

حيث <math>\lambda_{i}</math> القيمة الذاتية ل <math>A</math>.
 
يمكن تعميم الخصائص المذكورة أعلاه إلى غير المصفوفة المربعة المعقدة <math>A</math> عن طريق إدخال تعريف QR-التحليل المصفوفة المربعة المعقدة واستبدال القيم الذاتية مع قيم احادية.

لنفترض أن التحليل QR لمصفوفة غير المربعة ''A'':
 :<math>A = Q \begin{pmatrix}R\\O\end{pmatrix}, \qquad Q^*Q = I,</math>
باعتبار أن <math>O</math> مصفوفة صفرية , و <math>Q</math> مصفوفة وحدة

من خصائص SVD ومحددا للمصفوفة، لدينا
 :<math>\Big|\prod_{i} r_{ii}\Big| = \prod_{i} \sigma_{i},</math>
حيث <math>\sigma_{i}</math> القيمة الاحادية ل <math>A</math>.

لاحظ أن القيم الاحادية ل <math>A</math>و<math>R</math> متطابقة، على الرغم من القيم المعقدة الذاتية قد تكون مختلفة. ومع ذلك، إذا''A''مربعة، وفيما يلي صحيحا:
:<math>
{\prod_{i} \sigma_{i}} = \Big|{\prod_{i} \lambda_{i}}\Big|.
</math>
 
في النهاية، التحليل QR يمكن استخدامها بكفاءة لحساب حاصل ضرب القيم الذاتية أو القيم الاحادية من مصفوفة.

== تحوير الاعمدة ==
QR التحليل مع تحوير الأعمدة ينتج مصفوفة التباديل P
:<math>A P = Q R \quad \iff A = Q R P^T </math>
تمحور العمود مفيد عندما المصفوفة ''A'' تكون رتبتها ناقصة. فإنه يمكن أيضا تحسين الدقة الرقمية .''P''عادة ما يتم اختيارها بحيث عناصرالقطر من ''R'' لا تزيد:
<math>|r_{11}| \ge |r_{22}| \ge \ldots \ge |r_{nn}|</math>.
يمكن استخدامها للحصول على الرتبة الرقميه ل ''A'' بااقل الحسابات من تحليل القيمة الاحادية، تشكل أساس ما يسمى الكشف عن رتبة لوغاريتمات QR.

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

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

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

## مراجع

* .
* . Section 2.8.
* 
* .

## وصلات خارجية

تصنيف:تفكيك المصفوفات
تصنيف:جبر خطي عددي