تحليل LU: كيف تنقل معاملات الحذف عند تبديل صفين؟

صفر في البداية لا يعني انعدام المعكوس

في اتفاق LU المستخدم هنا، قطر L كله1، وأصفارها فوق القطر؛ أما U فأصفارها تحت القطر. التحليل دون تبديل لا يوجد لكل مصفوفة، حتى لو كانت قابلة للعكس. [2]

نختار A=[[0,2,1],[2,2,0],[1,5,4]]. الفواصل بين المجموعات تفصل الصفوف. بالتوسع على الصف الأول نجد det(A)=−2(8−0)+(10−2)=−8، وهو غير صفري.

مع ذلك يستحيل A=LU دون تبديل، بهذه الشروط: من الخانة الأولى u₁₁=a₁₁=0، بينما a₂₁=l₂₁u₁₁ سيكون صفرًا؛ لكنه في A يساوي2. هذا تناقض، وليس مجرد تعثر حسابي.

تبديلان وسجل لمعاملات الحذف

المحور الجزئي يختار أكبر قيمة مطلقة في العمود الحالي، من صف المحور إلى أسفل. تتحرك معاملات الحذف السابقة مع صفوفها. [1]

في العمود الأول نقارن0،2،1؛ فنبدل الصفين1 و2. تصير الصفوف[2,2,0] و[0,2,1] و[1,5,4]. معامل الصف الثاني0/2=0، ومعامل الثالث1/2.

نطرح نصف الأول من الثالث: [1,5,4]−(1/2)[2,2,0]=[0,4,4]. يبقى الصف الثاني[0,2,1]. نخزن المعاملين0 و1/2 في سجل العمود الأول من L.

نبدل الصفين2 و3 لأن4 أكبر من2. تنتقل خانتا العمود الأول في L من(0،1/2) إلى(1/2،0)؛ ونترك قطرها وأعمدتها المستقبلية.

بعد التبديل، نطرح نصف الصف الثاني[0,4,4] من الثالث[0,2,1] فنحصل على[0,0,−1]. المعامل الجديد l₃₂=1/2؛ فتظهر U=[[2,2,0],[0,4,4],[0,0,−1]].

افحص الترتيب وحاصل الضرب

الصفوف الأصلية أصبحت بالترتيب2،3،1، لذلك P=[[0,1,0],[0,0,1],[1,0,0]]. وهي تعطي PA=[[2,2,0],[1,5,4],[0,2,1]].

سجل المعاملات الصحيح يعطي L=[[1,0,0],[1/2,1,0],[0,1/2,1]]. حاصل LU صفه الأول[2,2,0]؛ والثاني(1/2)[2,2,0]+[0,4,4]=[1,5,4]؛ والثالث(1/2)[0,4,4]+[0,0,−1]=[0,2,1].

لو أبقينا معاملي العمود الأول في موضعيهما القديمين، لحصلنا على Lخطأ=[[1,0,0],[0,1,0],[1/2,1/2,1]]. حاصل LخطأU=[[2,2,0],[0,4,4],[1,3,1]] لا يساوي PA.

PᵀP=I₃، ولذلك من PA=LU نجد A=PᵀLU. في مثالنا P≠Pᵀ: الأولى ترسل الصفوف إلى2،3،1، ومنقولها يعيدها إلى ترتيبها الأصلي. نثبت هذا الاتفاق قبل مقارنة صيغة مكتوبة في مرجع آخر.

التبديلان يعطيان det(P)=1، وقطر L كله1. حاصل قطر U هو2×4×(−1)=−8، فيتفق مع محدد A الذي حسبناه مباشرة.

بدّل الثوابت ثم حل مثلثين

من Ax=b وPA=LU نحصل على LUx=Pb. نحل النظام السفلي Ly=Pb بالتعويض الأمامي، ثم العلوي Ux=y بالتعويض الخلفي. [3]

اختر b=(3,6,7). الترتيب نفسه2،3،1 يعطي Pb=(6,7,3)، بينما Pᵀb=(7,3,6) مختلف؛ المطلوب هنا Pb. تبديل المعادلات لا يغير ترتيب المجهولات في x.

من Ly=Pb نجد y₁=6؛ ثم(1/2)y₁+y₂=7، فيكون y₂=4؛ وأخيرًا(1/2)y₂+y₃=3، فيكون y₃=1.

من Ux=y نجد−x₃=1، ثم4x₂+4x₃=4، ثم2x₁+2x₂=6. إذن x₃=−1 وx₂=2 وx₁=1.

نراجع Ax: الصف الأول2×2−1=3؛ والثاني2×1+2×2=6؛ والثالث1+5×2+4×(−1)=7. أما استعمال b دون تبديله في Ly، فيحل نظامًا مختلفًا، لأن LU=PA.

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