تحليل LU غير الكامل

في الجبر الخطي العددي ، يعتبر تحليل LU غير الكامل (المختصر بـ ILU ) للمصفوفة تقريبًا متفرقًا لتحليل LU الذي يستخدم غالبًا كمعالج مسبق .

لنفترض نظامًا خطيًا متفرقًا${\displaystyle Ax=b}$غالباً ما يتم حل هذه المسائل عن طريق حساب التحليل إلى عوامل.${\displaystyle A=LU}$، حيث L مثلثية سفلية أحادية و U مثلثية علوية . ثم يتم حلها${\displaystyle Ly=b}$،${\displaystyle Ux=y}$، وهو ما يمكن القيام به بكفاءة لأن المصفوفات مثلثية.

بالنسبة للمصفوفات المتفرقة النموذجية، قد تكون عوامل LU أقل تفرقًا بكثير من المصفوفة الأصلية ، وهي ظاهرة تُعرف باسم "التعبئة" . وبالتالي، قد تُصبح متطلبات الذاكرة اللازمة لاستخدام خوارزمية حل مباشرة عائقًا أمام حل الأنظمة الخطية. ويمكن التغلب على هذه المشكلة باستخدام إعادة ترتيب مجاهيل المصفوفة لتقليل التعبئة، مثل خوارزمية الحد الأدنى للدرجة .

أما التحليل غير الكامل فيبحث عن المصفوفات المثلثية L و U بحيث${\displaystyle A\approx LU}$بدلاً من${\displaystyle A=LU}$حل المعادلة لـ${\displaystyle Lux=b}$يمكن القيام بذلك بسرعة، لكنه لا يؤدي إلى الحل الدقيق لـ${\displaystyle Ax=b}$لذلك، نستخدم المصفوفة بدلاً من ذلك.${\displaystyle M=LU}$كعامل تهيئة مسبقة في خوارزمية حل تكرارية أخرى مثل طريقة التدرج المترافق أو GMRES .

بالنسبة لمصفوفة معينة${\displaystyle A\in \mathbb {R} ^{n\times n}}$يُعرّف المرء الرسم البياني${\displaystyle G(A)}$مثل

${\displaystyle G(A):=\left\lbrace (i,j)\in \mathbb {N} ^{2}:A_{ij}\neq 0\right\rbrace \,,}$

والتي تُستخدم لتحديد شروط نمط التباعد${\displaystyle S}$الاحتياجات التي يجب تلبيتها

${\displaystyle S\subset \left\lbrace 1,\dots ,n\right\rbrace ^{2}\,,\quad \left\lbrace (i,i):1\leq i\leq n\right\rbrace \subset S\,,\quad G(A)\subset S\,.}$

تفكيك الشكل${\displaystyle A=LU-R}$حيثما ينطبق ما يلي

• ${\displaystyle L\in \mathbb {R} ^{n\times n}}$هي مصفوفة مثلثية سفلية أحادية
• ${\displaystyle U\in \mathbb {R} ^{n\times n}}$هي مصفوفة مثلثية علوية
• ${\displaystyle L,U}$تكون القيم صفرًا خارج نمط التباعد:${\displaystyle L_{ij}=U_{ij}=0\quad \forall \;(i,j)\notin S}$
• ${\displaystyle R\in \mathbb {R} ^{n\times n}}$يساوي صفرًا ضمن نمط التباعد:${\displaystyle R_{ij}=0\quad \forall \;(i,j)\in S}$

يُطلق عليه اسم تحليل LU غير الكامل (فيما يتعلق بنمط التباعد)${\displaystyle S}$).

غالبًا ما يُختار نمط التباعد للمصفوفتين L و U ليكون مطابقًا لنمط التباعد للمصفوفة الأصلية A. إذا أمكن الإشارة إلى بنية المصفوفة الأساسية باستخدام المؤشرات بدلًا من نسخها، فإن الذاكرة الإضافية المطلوبة تقتصر على عناصر L و U. يُطلق على هذه المُهيئ اسم ILU(0).

فيما يتعلق باستقرار ILU، تم إثبات النظرية التالية بواسطة مايرنك وفان دير فورست. ^{[ 1 ]}

يترك${\displaystyle A}$لتكن مصفوفة M ، فإن تحليل LU (الكامل) يُعطى بواسطة${\displaystyle A={\hat {L}}{\hat {U}}}$، و ILU بواسطة${\displaystyle A=LU-R}$. ثم

${\displaystyle |L_{ij}|\leq |{\hat {L}}_{ij}|\quad \forall \;i,j}$

يثبت ذلك. وبالتالي، فإن وحدة ILU مستقرة على الأقل مثل تفكيك LU (الكامل).

يمكن الحصول على مُهيئ أكثر دقةً بالسماح بمستوى معين من التعبئة الإضافية في عملية التحليل. ومن الخيارات الشائعة استخدام نمط التباعد للمصفوفة A² بدلاً من ^A ؛ فهذه المصفوفة أكثر كثافةً بشكل ملحوظ من A ، ولكنها لا تزال متفرقةً في مجملها. يُسمى هذا المُهيئ ILU(1). ويمكن تعميم هذه العملية؛ فالمُهيئ ILU(k) للمصفوفة A هو تحليل LU غير الكامل باستخدام نمط التباعد للمصفوفة Aⁿ⁺¹ ^.

تتطلب مُهيئات ILU الأكثر دقة ذاكرة أكبر، لدرجة أن وقت تشغيل الخوارزمية يزداد في النهاية على الرغم من انخفاض إجمالي عدد التكرارات. ونتيجة لذلك، توجد مفاضلة بين التكلفة والدقة يجب على المستخدمين تقييمها، عادةً على أساس كل حالة على حدة اعتمادًا على عائلة الأنظمة الخطية المراد حلها.

يمكن إجراء تقريب لتحليل ILU كعملية تكرار بنقطة ثابتة بطريقة متوازية للغاية. ^{[ 2 ]}

• تحليل تشوليسكي غير الكامل

• سعد، يوسف (1996)، الطرق التكرارية للأنظمة الخطية المتفرقة (الطبعة الأولى  )، بوسطن: PWS، ISBN 978-0-534-94776-7انظر القسم 10.3 وما يليه.

• تحليل LU غير المكتمل على موقع CFD Wiki