تحليل LU خطوة بخطوة
تحليل المصفوفة إلى جزأين مثلثيين سفلي وعلوي، ولماذا هو أسرع من إعادة الحذف، وكيف يخصّصه تحليل تشوليسكي.
يكتب تحليل LU المصفوفة المربعة جداءً لمصفوفة مثلثية سفلية في مصفوفة مثلثية علوية: A = L·U. والعاملان يخرجان مباشرة من حذف غاوس — فـU هي الشكل الدرجي، وL تسجّل المضاعفات التي استعملتها للوصول إليه.
| 4 | 3 |
| 6 | 3 |
| 1 | 0 |
| 3/2 | 1 |
| 4 | 3 |
| 0 | −3/2 |
ما فائدته
لأن التحليل قابل لإعادة الاستعمال. فحل Ax = b من الصفر يكلّف نحو n³/3 عملية. وبمجرد أن تصبح L وU جاهزتين، يكلّف كل طرف أيمن جديد n² فقط: حلّ Ly = b بالتعويض الأمامي، ثم Ux = y بالتعويض الخلفي. ومع عشرات الأطراف اليمنى يكون المكسب كبيرًا.
والمحدد يأتي مجانًا أيضًا — فهو جداء قطر U مضروبًا في −1 عن كل تبديل صفوف جرى.
اختيار المحور
ليست كل مصفوفة تقبل A = L·U بصورته البسيطة: فوجود صفر في موضع المحور يكسر الطريقة. والعلاج مصفوفة تبديل، فيصير P·A = L·U. وعمليًا يُستعمل اختيار المحور على أي حال، لأن انتقاء أكبر محور متاح يبقي أخطاء التقريب تحت السيطرة.
تشوليسكي: الحالة المتماثلة
إذا كانت A متماثلة ومعرّفة موجبة، فإنها تتحلل إلى A = L·Lᵀ — ويكفيك عامل مثلثي واحد. وتحليل تشوليسكي أسرع من LU بنحو الضعف ومستقر عدديًا جدًا، ولهذا يسود في الاستمثال والمربعات الصغرى والإحصاء (فمصفوفات التغاير متماثلة ومعرّفة موجبة بحكم بنائها).
وإن طلبت الخوارزمية في أي لحظة الجذر التربيعي لعدد سالب، فالمصفوفة لم تكن معرّفة موجبة — وبذلك يصلح تشوليسكي اختبارًا لهذه الخاصية أيضًا.