تحلل كيو آر

مثال

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

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

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

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

Then

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

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

• :
• حيث R1 عبارة عن n×n المصفوفة الثلاثية العليا
• 0عبارة عن (m − n)×n مصفوفة صفرية

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

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

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

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

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

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

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

باعتبار ان ثابت الابعاد للاعمدة المتجهات ل مثل للمقياس α.

• في الحالات المعقدة وضع :
• :
• واستبدال التحويل بتحويل مترافق ل Q أدناه .

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

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

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

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

• :
• حيث هي العناصر القطرية ل R.
• ولهذا، المحدد يساوي حاصل ضرب القيم الذاتية، لدينا
• :
• حيث القيمة الذاتية ل .

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

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

نحصل على:

مثال

• لنحسب التحليل ل:
• في البداية نوجد معكوس الصف الأول للمصفوفة A, vector , to
• الآن,
• و
• هنا,
• and
• لذلك

مثال

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

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

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

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

.

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

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

:

هي تحليل QR .

من جهة ثانية، Operation Number of operations in the k-th step multiplications additions division square root

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

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

التاريخ

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

Q1 عبارة عن m×n

, Q2 عبارة عن m×(m − n)

Q1 و Q2 تمتلك الأعمدة المتعامدة

وفي هذا الصدد، call Q1R1 the thin QR factorization of A; Trefethen and Bau يدعى this the تخفيض عملية تحليل الQR.

في حالة ان قيمة A حقيقية

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

A (= ATA

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

:

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

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

,

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

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

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

then:

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

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

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

حيث :

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

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

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

:

شرح الطريقة

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

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

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

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

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

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

من جهة ثانية، عن طريق التحليل QR يمكن أن نحسب سلسلة التدوير للمعطيات. كل دورة تصفر عنصر في المصفوفة العمودية ، وتشكل مصفوفة ثلاثية علويةR.

في سلسلة من كل تدوير المعطيات تشكل Q مصفوفة متعامدة.

. ( و

وفي السياق ذاته، غالبا ما تقدمها المكتبات الرقمية باعتبارها «الاقتصادي» التحليل QR).

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

وفي السياق ذاته، ما يعادل حالة غير المحدد، يمكن أن نستعمل تبديل عكسي للسرعة وبدقة الحصول على من دون معكوس

والطريقة الأخيرة يتمتع بقدر أكبر من الدقة وحساباته أقل.

كذلك، حيث هو مربع المصفوفة الثلاثية اليمنى ,والمصفوفة الصفرية تمتلك ابعاد .. بعد بعض العمليات الحسابية حل المسألة الخطية ممكن ان تظهر كالاتي

Parker Geophysical Inverse))

وعلى صعيد آخر، حيث ممكن ان نجد بواسطة Gaussian elimination بطريقة مباشرة مصفوفة مثلثية .

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

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

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

and , and then

• الآن لاحظ:
• حصلنا على وجه التقريب على مصفوف مثلثة. ونحتاج فقط لتصفير مدخل (3, 2) .
• خذ (1, 1) مختصر(جبر خطي), وطبق العملية مرة أخرى
• باستخدام نفس الطريقة اعلاه, نحصل على مصفوفة التحويل ل the Householder

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

الآن اوجدنا

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

لكل طريقة عدد من المزايا والعيوب.

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

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

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

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

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

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

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

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

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

:

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