في الجبر الخطي، تحليل QR (بالإنجليزية: QR decomposition)‏ لمصفوفة هو طريقة التحليل أو الإحلال QR وتعرف أيضا بطريقة عوامل، QR عبارة عن تحليل أو احلال المصفوفة A وادخالها في المعادلة:

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

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

التاريخ

عدل

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

شرح الطريقة

عدل

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

 

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

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

المصفوفة المستطيلة

عدل

بشكل عام يمكننا ان نحلل المصفوفة المعقدة m×n A مع m ≥ n وايضا العملية m×m بمصفوفة الوحدة Q وايضاm×n بالمصفوفة الثلاثية العليا R.

الصفوف السفلية (mn) من m×n للمصفوفة الثلاثية تحتوي على الاصفار وهذا يساعد في إيجاد قيمةR أو R و Q بالكامل .
: 

حيث R1 عبارة عن n×n المصفوفة الثلاثية العليا 0عبارة عن (m − nn مصفوفة صفرية Q1 عبارة عن m×n , Q2 عبارة عن m×(m − n) Q1 و Q2 تمتلك الأعمدة المتعامدة

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

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

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

التحليل QL, RQ و LQ

عدل

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

حساب التحليل QR

عدل

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

استخدام طريقة the Gram–Schmidt

عدل

اباعتبار Gram–Schmidt وتطبيقها على أعمدة المصفوفه كاملة الرتبة  , في الداخل   أو   في الحالات المعقدة

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

 

then:

 

بإعادة ترتيب المعادلات أعلاه حيث  s على اليسار، وذلك باستخدام   كون هي متجهات الوحدة:

 

حيث أن  . يمكن أن تكتب بشكل مصفوفة:

 

حيث :

 

مثال

عدل

نعتبر التحليل ل:

 

باستدعاء المصفوفة المتعامدة   has the property

 

نقوم بحساب   by means of Gram–Schmidt كالتالي:

 
 

نحصل على:

 
 

بالنسبة لتحليل RQ

عدل

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

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

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

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

استخدام معكوس Householder

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

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

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

باعتبار ان   ثابت الابعاد للاعمدة المتجهات ل   مثل   للمقياس α. لو الطريقة نفذت باستخدام عدد فاصل عائم, وايضا α لابد ان تحصل على إشارة معاكسه كما k-th وتنسيق من   ,بينما   أن تكون محور التنسيق والتي بعدها كل الإدخالات 0 في مصفوفة ذات الشكل الثلاثي العلويA's، لتجنب فقدان أهمية المصفوفة . في الحالات المعقدة وضع :

: 

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

حيث   هي متجهة (1,0,...,0)T, ||·|| هو القاعدة الإقليدية و  عبارة عن مصفوفة متطابقة m-by-m, باعتبار
 
 
 

أو باعتبار ان   مركب أو معقد:

 , where  

باعتبار ان حيث   هو تحويل مترافق (tranjugate) من  

  مصفوفة m-by-m و :  

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

: 

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

 

بعد بمقدار   من التكرارات

 ,

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

 

  هي تحليل QR  .

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

Operation Number of operations in the k-th step
multiplications  
additions  
division  
square root  

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

: 

مثال

عدل

لنحسب التحليل ل:

 

في البداية نوجد معكوس الصف الأول للمصفوفة A, vector  , to  

الآن,

 

و

 

هنا,

  and  

لذلك

  and  , and then
 
 
 

الآن لاحظ:

 

حصلنا تقريبا على مصفوف مثلثة. ونحتاج فقط لتصفير مدخل (3, 2) .

خذ (1, 1) [[مختصر(جبر خطي), وطبق العملية مرة أخرى

 

باستخدام نفس الطريقة اعلاه, نحصل على مصفوفة التحويل ل the Householder

 

بعد القيام بعملية الجمع المباشر ل 1 للتأكد من ان الخطوة التالية تعمل بشكل مناسب.

الآن اوجدنا

 

Then

 
 

المصفوفة Q متعامده و R مصفوفة ثلاثية علويه, A = QR تتطلب تحليل QR.

استخدام تدوير المعطيات

عدل

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

مثال

عدل

لنحسب التحليل ل:

 

أولا, نحتاج لتدوير المصفوفة لتصفير العنصر الشمالي الأسفل,  . نكون المصفوفة باستخدام the Givens rotation نستدعي المصفوفة  . بداية ندور المتجه  , لنقطة على طول محورX . متجه بزاوية  . نكون تعامد Givens rotation مصفوفة,  :

 
 

نتيجة ال   الآن في صفر في   element.

 

بشكل مماثل المصفوفات المعطاة   و  , التي تصفر العناصر حول القطرية   and  , مكونة المصفوفة المثلثة  . المصفوفة المتعامدة   تتكون من تسلسل كل المعطيات matrices  . لذا نحصل على  , و ال QR التحليل هو  .

الارتباط بالمحدد أو جداء القيم الذاتية

عدل

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

: 

باعتبار أن Q احادية و  

: 

حيث   هي العناصر القطرية ل R.

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

: 

حيث   القيمة الذاتية ل  .

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

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

: 

باعتبار أن   مصفوفة صفرية , و   مصفوفة وحدة

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

: 

حيث   القيمة الاحادية ل  .

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

 

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

تحوير الاعمدة

عدل

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

 

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

استخدامها في حل المسائل العكسية الخطية

عدل

مقارنة بالمصفوفة المعكوسة، الحلول العكسية باستخدام التحليل QR هي أكثر استقرارا من الناحية العددية كما يتضح من انخفاض العددالشرطي. Parker Geophysical Inverse)) لحل الغير محددات ( ) المسالة الخطية   حيث المصفوفة A لها أبعاد   ورتبة , أولا تحليل QR للمعكوس A:  , حيث Q المصفوفة العمودية مثال  , و R يمتلك شكل خاص :  .

حيث  هو   مربع المصفوفة الثلاثية اليمنى ,والمصفوفة الصفرية تمتلك ابعاد  . . بعد بعض العمليات الحسابية حل المسألة الخطية ممكن ان تظهر كالاتي   حيث ممكن ان نجد   بواسطة Gaussian elimination   بطريقة مباشرة مصفوفة مثلثية . والطريقة الأخيرة يتمتع بقدر أكبر من الدقة وحساباته أقل.

لإيجاد الحل ل   للحساب ( ) بمسالة   بحيث نقلل المعيار norm  , أولا تحليل QR ل A:  . الحل يمكن أن يشرح كالاتي  , , حيث   عبارة عن مصفوفة   تحتوي على أول عمود   يمثل أساسيات full   القاعده المتعامده وحيث أن   كما سبق. ما يعادل حالة غير المحدد، يمكن أن نستخدم تبديل عكسي للسرعة وبدقة الحصول على   من دون معكوس  . (  و  غالبا ما تقدمها المكتبات الرقمية باعتبارها «الاقتصادي» التحليل QR).

مراجع

عدل
  1. ^ L. N. Trefethen and D. Bau, Numerical Linear Algebra (SIAM, 1997).
  • Golub، Gene H.؛ Van Loan، Charles F. (1996)، Matrix Computations (ط. 3rd)، Johns Hopkins، ISBN:978-0-8018-5414-9.
  • Horn، Roger A.؛ Johnson، Charles R. (1985)، Matrix Analysis، Cambridge University Press، ISBN:0-521-38632-2. 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
  • Stoer، Josef؛ Bulirsch، Roland (2002)، Introduction to Numerical Analysis (ط. 3rd)، Springer، ISBN:0-387-95452-X.

وصلات خارجية

عدل