اكتب مصفوفة مربعة، وافتح تبويب التحليلات، ثم اضغط LU(A). ولأن الجواب زوج من المصفوفات لا مصفوفة واحدة، فهو يسكن عرض الخطوات بأكمله، وينفتح من تلقائه ويعرض L و U جنبًا إلى جنب في النهاية. وCholesky(A) في التبويب نفسه، للحالة المتماثلة المشروحة أدناه.
ما العاملان
يكتب تحليل LU المصفوفة على صورة A = L·U، حيث L مثلثية سفلى و U مثلثية عليا. ولا غموض في أي منهما: فـ U هي بعينها الصورة الدرجية التي ينتجها حذف غاوس، و L تحفظ المضاعفات التي استعملتها في الطريق. وحذف واحد يعطيك العاملين معًا.
مثال محلول
| 4 | 3 |
| 6 | 3 |
| 1 | 0 |
| 3/2 | 1 |
| 4 | 3 |
| 0 | −3/2 |
والعدد 3/2 في L هو المضاعف الذي صفّر العدد 6 تحت المحور. ولاحظ أن المحدد صار مجانًا: اضرب عناصر قطر U فتحصل على 4 · (−3/2) = −6، مضروبًا في −1 عن كل تبديل صفوف أُجري.
لماذا يستحق العناء
لأن التحليل قابل لإعادة الاستعمال. فحلّ Ax = b من الصفر يكلف نحو n³/3 عملية. وبعد الحصول على L و U لا يكلف كل طرف أيمن جديد إلا n²: حلّ Ly = b بالتعويض الأمامي ثم Ux = y بالتعويض الخلفي. وإن كنت تحل النظام نفسه مع متجهات b كثيرة مختلفة — وهي الحال المعتادة في الهندسة والمحاكاة — فالتوفير هائل. ففي مصفوفة 100×100 وخمسين طرفًا أيمن يكون ذلك تحليلًا واحدًا وخمسين مرورًا رخيصًا، بدل خمسين حذفًا كاملًا.
التعويض الأمامي والخلفي بالأرقام
خذ المصفوفة 3×3 المحمَّلة أعلاه. حذف واحد يعطي العاملين:
| 2 | 1 | 1 |
| 4 | −6 | 0 |
| −2 | 7 | 2 |
| 1 | 0 | 0 |
| 2 | 1 | 0 |
| −1 | −1 | 1 |
| 2 | 1 | 1 |
| 0 | −8 | −2 |
| 0 | 0 | 1 |
وعناصر L هي بعينها المضاعفات المستعملة في الحذف: فالعدد 2 صفّر الـ 4، و−1 صفّر الـ −2، و−1 صفّر ما بقي في العمود الثاني. فلنحل الآن Ax = b عند b = (4, −2, 7). أولًا Ly = b من الأعلى إلى الأسفل، وكل صف يعطي قيمة جديدة فورًا لأن ما على يمينه أصفار:
y₁ = 4؛ ثم 2·4 + y₂ = −2 فيكون y₂ = −10؛ ثم −4 + 10 + y₃ = 7 فيكون y₃ = 1.
ثم Ux = y من الأسفل إلى الأعلى: x₃ = 1؛ ثم −8x₂ − 2 = −10 فيكون x₂ = 1؛ ثم 2x₁ + 1 + 1 = 4 فيكون x₁ = 1. والحل (1, 1, 1)، بلغناه بلا قسمة واحدة على شيء غير عنصر قطري. والمحدد يأتي مجانًا من العاملين نفسيهما: 2 · (−8) · 1 = −16.
اختيار العنصر المحوري
ليست كل مصفوفة تقبل A = L·U مجردًا: فصفر في موضع المحور يكسره. والعلاج مصفوفة تبديل، فيصير P·A = L·U. ويُستعمل الاختيار المحوري عمليًا على كل حال، لأن أخذ أكبر محور متاح يُبقي أخطاء التقريب تحت السيطرة. والتحليل وحيد بعد تثبيت اصطلاح؛ وهذه الحاسبة تستعمل اصطلاح دوليتل، الذي يضع آحادًا على قطر L.
تشوليسكي: الحالة المتماثلة
إذا كانت A متماثلة ومعرَّفة موجبة فإنها تتحلل إلى A = L·Lᵀ — جذر تربيعي للمصفوفات، بعامل مثلثي واحد فحسب. والتماثل يعني A = Aᵀ، والتعريف الموجب يعني أن كل قيمة ذاتية أكبر من صفر. ويبدو ذلك مقيّدًا، غير أن المصفوفات التي يصفها في كل مكان: فمصفوفات التغاير، ومصفوفات غرام، والمعادلات السوية للمربعات الصغرى، ومصفوفات الجساءة في طريقة العناصر المنتهية كلها متماثلة معرَّفة موجبة بحكم بنائها.
| 4 | 2 |
| 2 | 5 |
| 2 | 0 |
| 1 | 2 |
| 2 | 1 |
| 0 | 2 |
وكل عنصر قطري في L جذر تربيعي — هنا √4 = 2 و√(5 − 1²) = 2 — ولهذا تشترط الطريقة بقاء ما تحت كل جذر موجبًا. وهذا الشرط هو بعينه التعريف الموجب، وهو يحوّل الخوارزمية إلى اختبار: فإن اكتمل التحليل كانت المصفوفة معرَّفة موجبة، وإن اصطدم بقيمة غير موجبة تحت جذر فليست كذلك. وتشوليسكي أسرع بنحو الضعف من LU، ويستهلك نصف الذاكرة، وثابت بلا اختيار محوري — ولهذا تختبر الحلّالات التماثل أولًا وتلجأ إليه كلما أمكن.
أخطاء شائعة
- افتراض أن كل مصفوفة تتحلل. صفر في موضع المحور يكسر LU المجرد. والعلاج مصفوفة تبديل:
P·A = L·U. - تطبيق تشوليسكي على مصفوفة غير متماثلة. إن A = L·Lᵀ متماثلة بحكم البناء، فلا تحليل كهذا لمدخل غير متماثل. استعمل LU.
- ظن أن التماثل يكفي. المصفوفة المتماثلة ذات قيمة ذاتية سالبة غير معرَّفة الإشارة وستخفق في منتصف الخوارزمية.
- توقّع عوامل صحيحة. قطر تشوليسكي فيه جذور تربيعية، فتكون L عادةً غير جذرية حتى لو كانت A صحيحة.
- نسيان تبديلات الصفوف في المحدد. كل تبديل يعكس إشارته.