تحليل LU

في التحليل العددي والجبر الخطي ، يُحلل تحليل LU ( التحليل السفلي-العلوي ) المصفوفة إلى حاصل ضرب مصفوفة مثلثية سفلية ومصفوفة مثلثية علوية (انظر ضرب المصفوفات وتحليل المصفوفات ). قد يتضمن حاصل الضرب أحيانًا مصفوفة تبديل . يُمكن اعتبار تحليل LU بمثابة الصيغة المصفوفية لحذف غاوس . عادةً ما تستخدم الحواسيب تحليل LU لحل أنظمة المعادلات الخطية المربعة ، كما أنه خطوة أساسية عند حساب معكوس المصفوفة أو محددها . يُشار إليه أحيانًا بتحليل LR (التحليل إلى مصفوفات مثلثية يسارية ويمينية). قدّم عالم الفلك البولندي تاديوش باناتشيفيتش خوارزمية تحليل LU للمصفوفات العامة عام 1938. ^[¹^]

التعريفات

لتكن $A$ مصفوفة مربعة. يشير تحليل LU إلى تحليل $A$ إلى حاصل ضرب عاملين: مصفوفة مثلثية سفلية $L$ ومصفوفة مثلثية علوية $U$ ، بحيث يكون $A = LU$ . أحيانًا يكون التحليل مستحيلاً دون إعادة ترتيب $A$ مسبقًا لتجنب القسمة على صفر أو الزيادة غير المنضبطة في أخطاء التقريب. لذا، يصبح التعبير البديل $PAQ = LU$ ، حيث يشير عاملا مصفوفة التبديل $P$ و $Q$ في الترميز الرسمي إلى تبديل صفوف (أو أعمدة) $A.$ نظريًا، يُحصل على $P$ (أو $Q ) من خلال تبديل صفوف (أو أعمدة)$ مصفوفة الوحدة ؛ عمليًا ، تُطبق التبديلات المقابلة مباشرةً على صفوف (أو أعمدة) $A.$

المصفوفة $A$ ذات الجانب $n$ تحتوي على $n^{2}$ تحتوي معاملات المصفوفتين المثلثيتين المدمجتين على $n (n +1)$ معاملًا، وبالتالي فإن معاملات المصفوفة $LU$ غير مستقلة. جرت العادة على جعل $L مصفوفة مثلثية أحادية$ $،$ أي أن جميع عناصر قطرها الرئيسي $n$ تساوي واحدًا. مع ذلك، فإن جعل المصفوفة $U$ مصفوفة مثلثية أحادية يختزل إلى نفس الإجراء بعد نقل حاصل ضرب المصفوفات (انظر خصائص نقل المصفوفات). $B=A^{\textsf {T}}=(LU)^{\textsf {T}}=U^{\textsf {T}}L^{\textsf {T}}.$ بعد عملية النقل، يصبح $U T$ مثلثًا سفليًا، بينما يصبح $L T$ عاملًا مثلثيًا علويًا للمصفوفة $B.$ وهذا يُظهر أيضًا أن العمليات على الصفوف (مثل التمحور) تُكافئ تلك التي تُجرى على أعمدة المصفوفة المنقولة، وبشكل عام، لا يُقدم اختيار خوارزمية الصفوف أو الأعمدة أي ميزة.

في المصفوفة المثلثية السفلية، تكون جميع العناصر فوق القطر الرئيسي أصفارًا، وفي المصفوفة المثلثية العلوية، تكون جميع العناصر أسفل القطر أصفارًا. على سبيل المثال، بالنسبة لمصفوفة $A من الرتبة$ 3 × 3 ، يكون تحليلها باستخدام طريقة LU كما يلي: ${\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{bmatrix}}={\begin{bmatrix}\ell _{11}&0&0\\\ell _{21}&\ell _{22}&0\\\ell _{31}&\ell _{32}&\ell _{33}\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\end{bmatrix}}.$

بدون ترتيب أو تباديل مناسبة في المصفوفة، قد لا تتحقق عملية التحليل. على سبيل المثال، من السهل التحقق (عن طريق توسيع ضرب المصفوفات ) من أن ${\textstyle a_{11}=\ell _{11}u_{11}}$ . لو ${\textstyle a_{11}=0}$ ثم واحد على الأقل من ${\textstyle \ell _{11}}$ و ${\textstyle u_{11}}$ يجب أن يكون الناتج صفرًا، مما يعني أن إما $L$ أو $U$ منفردة . وهذا مستحيل إذا كانت $A غير$ منفردة (قابلة للعكس). من حيث العمليات، فإن تصفير/حذف العناصر المتبقية من العمود الأول من $A$ يتضمن قسمة ${\textstyle a_{21},a_{31}}$ مع ${\textstyle a_{11}}$ مستحيل إذا كانت القيمة صفرًا. هذه مشكلة إجرائية. يمكن حلها ببساطة عن طريق إعادة ترتيب صفوف المصفوفة $A$ بحيث يكون العنصر الأول في المصفوفة المُبدَّلة غير صفري. يمكن حل المشكلة نفسها في خطوات التحليل اللاحقة بنفس الطريقة. من أجل الاستقرار العددي ضد أخطاء التقريب/القسمة على أعداد صغيرة، من المهم اختيار ${\textstyle a_{11}}$ ذات قيمة مطلقة كبيرة (انظر إلى التمحور).

LU من خلال التكرار

يوضح المثال أعلاه لمصفوفات 3 × 3 أن ضرب الصف العلوي والعمود الأيسر للمصفوفات المعنية يلعب دورًا خاصًا لنجاح خوارزمية $LU$ . لنرمز إلى النسخ المتتالية من المصفوفات بـ $(0),\;(1),\dots$ ثم لنكتب حاصل ضرب المصفوفات $A\equiv A^{(0)}=L^{(0)}U^{(0)}$ بحيث تكون هذه الصفوف والأعمدة منفصلة عن باقي الصفوف والأعمدة. ولتحقيق ذلك، سنستخدم ترميز المصفوفة الكتلية ، على سبيل المثال: $a\equiv a_{11}$ هو عدد عادي، ${\bf {w}}^{\textsf {T}}\equiv (a_{12},a_{13})^{\textsf {T}}$ هو متجه صف و ${\bf {v}}=(a_{21},a_{31})$ هو متجه عمودي و $A'$ هي مصفوفة فرعية من المصفوفة $A^{(0)}$ بدون الصف العلوي والعمود الأيسر. ثم يمكننا استبدالها. $A^{(0)}=L^{(0)}U^{(0)}$ باستخدام ضرب المصفوفات الكتلية . أي أنه يمكن ضرب كتل المصفوفات كما لو كانت أعدادًا عادية، أي صف في عمود، باستثناء أن مكوناتها الآن هي مصفوفات فرعية، تُختزل أحيانًا إلى كميات قياسية أو متجهات. $u{\bf {l}}$ يشير إلى متجه تم الحصول عليه من ${\bf {l}}$ بعد ضرب كل مكون في عدد $u$ ، ${\bf {lu}}^{\textsf {T}}$ هو ناتج خارجي للمتجهات ${\bf {l,u}}$ أي مصفوفة يكون عمودها الأول هو $u_{12}{\bf {l}}$ ثم يأتي التالي $u_{13}{\bf {l}}$ وهكذا بالنسبة لجميع مكونات ${\bf {u}}$ و $L^{(1)}U^{(1)}$ هو ناتج مصفوفات فرعية من $L^{(0)},\;U^{(0)}$ $\begin{aligned}\left(\begin{array}{c|c}a&\bf{w}}^{\textsf{T}}\\\hline \\[-0.5em]\bf{v}}&\quad A'\quad \\[-0.5em]\\\end{array}}\right)&=\left(\begin{array}{c|c}{\rm{1}}&\bf{0}}^{\textsf{T}}\\\hline \\[-0.5em]\bf{l}}&\quad L^{(1)}\quad \\[-0.5em]\\\end{array}}\right)\;\left(\begin{array}{c|c}u&\bf{u}}^{\textsf{T}}\\\hline \\[-0.5em]{\bf {0}}&\quad U^{(1)}\\[-0.5em]\\\end{array}}\right)\\&=\left({\begin{array}{c|c}u&{\bf {u}}^{\textsf {T}}\\\hline \\[-0.5em]u{\bf {l}}&\quad {\bf {lu}}^{\textsf {T}}+L^{(1)}U^{(1)}\\[-0.5em]\\\end{array}}\right)\end{aligned}}}$

ينتج عن تساوي المصفوفتين الأولى والأخيرة المصفوفة النهائية $u=a$ ، ${\bf {u=w}}$ ، ${\bf {l}}={(1/a)}{\bf {v}}$ بينما المصفوفة $A'$ يتم تحديثه/استبداله بـ $A^{(1)}\equiv L^{(1)}U^{(1)}=$ $A'-{\bf {lu}}^{\textsf {T}}$ والآن تأتي الملاحظة الحاسمة: لا شيء يمنعنا من العلاج $A^{(1)}$ بنفس الطريقة التي اتبعناها مع $A^{(0)}$ ، بشكل متكرر. إذا كان بُعد $A$ هي $n$ × $n$ ، وبعد $n - 1$ من هذه الخطوات، جميع الأعمدة ${\bf {v}}$ تشكل الجزء القطري الفرعي لمصفوفة المثلث $L$ وجميع المحاور $a$ بالإضافة إلى الصفوف ${\bf {w}}^{\textsf {T}}$ شكل مصفوفة مثلثية علوية $U$ كما هو مطلوب. في المثال أعلاه ، $ن = 3$ ، لذا تكفي خطوتان فقط.

يوضح الإجراء المذكور أعلاه أنه في أي خطوة من خطوات عنصر المحور القطري العلوي $a$ يمكن أن تكون قيم المصفوفات الفرعية المتتالية صفرًا. لتجنب ذلك، يمكن تبديل الأعمدة أو الصفوف بحيث $a$ تصبح غير صفرية. يُطلق على هذا الإجراء الذي يتضمن التبديل اسم LUP ، وهو التفكيك مع التمحور.

تبديل الأعمدة يتوافق مع ضرب المصفوفات $AQ^{(0)}$ أين $Q^{(0)}$ هي مصفوفة تبديل، أي مصفوفة الوحدة $I$ بعد نفس تبديل الأعمدة. بعد كل هذه الخطوات، ينطبق تحليل LUP على $AQ^{(0)}\cdots Q^{(n-1)}\equiv AQ=LU$ تُعدّ طريقة الحساب الحالية وما شابهها في دراسة كورمن وآخرون ^{[ 2 ]} أمثلة على خوارزميات التكرار . وهي تُظهر خاصيتين عامتين لتحليل LU:

الحاجة إلى تغيير المسار في كل خطوة؛ و
يتم الحصول على القيم النهائية لمصفوفات $L$ و $U$ تدريجياً، صف واحد أو عمود واحد في كل خطوة.

لا تُعدّ خوارزميات التكرار مكلفةً للغاية من حيث العمليات الجبرية، إلا أنها تعاني من عيب عملي يتمثل في الحاجة إلى تحديث وتخزين معظم عناصر المصفوفة $A$ في كل خطوة. وسنرى أنه من خلال إعادة ترتيب العمليات الحسابية، يُمكن الاستغناء عن تخزين القيم الوسيطة.

تحليل LU مع التمحور الجزئي

اتضح أن التبديل المناسب للصفوف (أو الأعمدة) لاختيار العمود (أو الصف) المحوري الأقصى المطلق $a 11$ كافٍ لتحليل LU المستقر عدديًا، باستثناء الحالات الشاذة المعروفة. ويُطلق عليه اسم " تحليل LU مع التمحور الجزئي " (LUP). $PA=LU,\quad (AQ=LU),$ حيث $L$ و $U$ مصفوفتان مثلثيتان سفليتان وعلويتان، و $P$ و $Q$ مصفوفتا تبديل متناظرتان ، وعند ضربهما من اليسار واليمين في $A$ ، يُعاد ترتيب صفوف وأعمدة $A.$ وقد تبيّن أن جميع المصفوفات المربعة قابلة للتحليل إلى عواملها الأولية بهذه الطريقة، ^{[ 3 ]} وأن هذا التحليل مستقر عدديًا عمليًا. ^{[ 4 ]} وهذا ما يجعل تحليل LUP تقنية مفيدة في التطبيق العملي.

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

تحليل LU مع التمحور الكامل

تتضمن عملية " تحليل LU مع التمحور الكامل " تبديل الصفوف والأعمدة لإيجاد العنصر الأقصى المطلق في المصفوفة الفرعية بأكملها: $PAQ=LU,$ حيث يتم تعريف $L$ و $U$ و $P كما سبق$ ^، $و Q$ هي مصفوفة تبديل تعيد ترتيب أعمدة $A.$ [ ^{5 ]}

تحليل القطر السفلي العلوي (LDU)

يُعدّ " التحليل القطري السفلي العلوي " (LDU) تحليلًا على شكل $A=LDU,$ حيث $D$ هي مصفوفة قطرية ، و $L$ و $U$ مصفوفات مثلثية أحادية ، مما يعني أن جميع المدخلات على أقطار $L$ و $U$ تساوي واحدًا.

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

اشترطنا سابقًا أن تكون المصفوفة $A$ مربعة، ولكن يمكن تعميم هذه التحليلات لتشمل المصفوفات المستطيلة أيضًا. ^{[ 6 ]} في هذه الحالة، تكون المصفوفتان $L$ و $D$ مربعتين، ولكل منهما نفس عدد صفوف المصفوفة $A$ ، وللمصفوفة $U$ نفس أبعاد المصفوفة $A$ تمامًا . يُقصد بمصطلح "المصفوفة المثلثية العلوية" أنها تحتوي على عناصر صفرية فقط أسفل القطر الرئيسي، الذي يبدأ من الزاوية العلوية اليسرى. وبالمثل، فإن المصطلح الأكثر دقة للمصفوفة $U$ هو أنها تمثل شكل الصفوف المتدرجة للمصفوفة $A.$

مثال

نقوم بتحليل المصفوفة التالية ذات الأبعاد 2 × 2 إلى عواملها الأولية : ${\begin{bmatrix}4&3\\6&3\end{bmatrix}}={\begin{bmatrix}\ell _{11}&0\\\ell _{21}&\ell _{22}\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}}.$

إحدى طرق إيجاد تحليل LU لهذه المصفوفة البسيطة هي حل المعادلات الخطية بالمعاينة. بتوسيع عملية ضرب المصفوفات نحصل على $\left\{{\begin{alignedat}{4}\ell _{11}\cdot u_{11}&&\;+\;&&0\cdot 0&&\;=\;&&4\\\ell _{11}\cdot u_{12}&&\;+\;&&0\cdot u_{22}&&\;=\;&&3\\\ell _{21}\cdot u_{11}&&\;+\;&&\ell _{22}\cdot 0&&\;=\;&&6\\\ell _{21}\cdot u_{12}&&\;+\;&&\ell _{22}\cdot u_{22}&&\;=\;&&3\end{alignedat}}\right.$

هذا النظام من المعادلات غير محدد . في هذه الحالة، يُعتبر أي عنصرين غير صفريين في المصفوفتين $L$ و $U$ معلمات للحل، ويمكن تعيينهما بشكل عشوائي لأي قيمة غير صفرية. لذلك، لإيجاد تحليل LU الفريد، من الضروري وضع بعض القيود على المصفوفتين $L$ و $U.$ على سبيل المثال، يمكننا اشتراط أن تكون المصفوفة المثلثية السفلية $L$ مصفوفة مثلثية وحدوية، بحيث تكون جميع عناصر قطرها الرئيسي تساوي واحدًا. عندئذٍ يكون لنظام المعادلات الحل التالي: ${\begin{aligned}\ell _{11}&=\ell _{22}=1\\\ell _{21}&=1.5\\u_{11}&=4\\u_{12}&=3\\u_{22}&=-1.5\end{aligned}}$

بتعويض هذه القيم في تحليل LU أعلاه نحصل على ${\begin{bmatrix}4&3\\6&3\end{bmatrix}}={\begin{bmatrix}1&0\\1.5&1\end{bmatrix}}{\begin{bmatrix}4&3\\0&-1.5\end{bmatrix}}.$

الوجود والتفرد

المصفوفات المربعة

أي مصفوفة مربعة $A$ تقبل تحليل LUP وPLU. ^{[ 3 ]} إذا كانت $A$ قابلة للعكس ، فإنها تقبل تحليل LU (أو LDU) إذا وفقط إذا كانت جميع محدداتها الرئيسية الرئيسية غير صفرية ^{[ 7 ]}^{[ 8 ]} (على سبيل المثال $\left[{\begin{smallmatrix}0&1\\1&0\end{smallmatrix}}\right]$ (لا تقبل تحليل LU أو LDU). إذا كانت $A$ مصفوفة منفردة من الرتبة $k$ ، فإنها تقبل تحليل LU إذا كانت المحددات الرئيسية $k$ الأولى غير صفرية، على الرغم من أن العكس غير صحيح. ^{[ 9 ]}

إذا كانت المصفوفة المربعة القابلة للعكس تمتلك تحليلًا من نوع LDU (حيث تكون جميع عناصر القطر الرئيسي للمصفوفتين $L$ و $U$ مساوية $للواحد$ )، فإن هذا التحليل يكون فريدًا. ^{[ 8 ]} في هذه الحالة، يكون تحليل LU فريدًا أيضًا إذا اشترطنا أن يتكون قطر إحدى المصفوفتين $L$ أو $U$ من الواحدات.

بشكل عام، يمكن أن تحتوي أي مصفوفة مربعة $A n \times n$ على أحد الخيارات التالية:

تحليل فريد لـ LU (كما ذكر أعلاه)؛
عدد لا نهائي من تحليلات LU إذا كانت أي من الأعمدة الأولى $(n - 1)$ مرتبطة خطيًا؛
لا يوجد تحليل LU إذا كانت الأعمدة الأولى $(n - 1)$ مستقلة خطيًا وكان أحد المحددات الرئيسية الرئيسية على الأقل يساوي صفرًا.

في الحالة 3، يمكن تقريب تحليل LU عن طريق تغيير عنصر قطري $a ij$ إلى $a ij \pm ε$ لتجنب وجود فاصل رئيسي رئيسي صفري. ^{[ 10 ]}

المصفوفات المتناظرة الموجبة المحددة

إذا كانت $A$ مصفوفة متناظرة (أو هيرميتية ، إذا كانت $A$ مركبة) موجبة التحديد ، فيمكننا ترتيب الأمور بحيث تكون $U$ هي منقولة المرافق لـ $L.$ أي، يمكننا كتابة $A$ على النحو التالي: $A=LL^{*}\,.$

يُطلق على هذا التحليل اسم تحليل تشوليسكي . إذا كانت المصفوفة $A$ موجبة التحديد، فإن تحليل تشوليسكي موجود وفريد. علاوة على ذلك، فإن حساب تحليل تشوليسكي أكثر كفاءة وأكثر استقرارًا عدديًا من حساب بعض تحليلات LU الأخرى.

المصفوفات العامة

بالنسبة لأي مصفوفة (ليست بالضرورة قابلة للعكس) على أي حقل، فإن الشروط اللازمة والكافية التي بموجبها يكون لها تحليل LU معروفة. تُعبَّر هذه الشروط بدلالة رتب بعض المصفوفات الفرعية. وقد تم توسيع خوارزمية الحذف الغاوسي للحصول على تحليل LU لتشمل هذه الحالة العامة. ^{[ 11 ]}

الخوارزميات

الصيغة المغلقة

عندما يكون تحليل LDU موجودًا وفريدًا، توجد صيغة مغلقة (صريحة) لعناصر $L$ و $D$ و $U$ بدلالة نسب محددات مصفوفات فرعية معينة من المصفوفة الأصلية $A.$ ^{[ 12 ]} على وجه الخصوص، $D1 = A1,1 ،$ وبالنسبة لـ $i = 2، ...، n$ ، $فإن$ $Di$ هي نسبة المصفوفة الفرعية الرئيسية $رقم i$ إلى المصفوفة الفرعية الرئيسية رقم $(i - 1)$ . حساب المحددات مكلف حسابيًا $،$ لذا لا تُستخدم هذه الصيغة الصريحة عمليًا.

باستخدام طريقة الحذف الغاوسي

الخوارزمية التالية هي في الأساس شكل مُعدَّل من $خوارزمية$ الحذف الغاوسي . يتطلب حساب تحليل LU باستخدام هذه الخوارزمية $2/3 n³ عملية حسابية للأعداد العشرية، مع تجاهل الحدود$ ^ذات الرتبة الأدنى. يُضيف التمحور الجزئي حدًا تربيعيًا $فقط$ $؛ وهذا ليس هو$ الحال بالنسبة للتمحور الكامل. $[$ ^{13 ]}

شرح عام

الترميز

بالنظر إلى مصفوفة $N$ × $N$ $A=(a_{i,j})_{1\leq i,j\leq N}$ ، يُعرِّف $A^{(0)}$ باعتبارها النسخة الأصلية غير المعدلة للمصفوفة $A.$ يشير الرمز العلوي بين قوسين (مثلاً، $(0)$ ) للمصفوفة $A$ إلى نسخة المصفوفة. المصفوفة $A (n)$ هي المصفوفة $A$ التي تم فيها حذف العناصر الموجودة أسفل القطر الرئيسي إلى الصفر باستخدام طريقة الحذف الغاوسي لأول $n$ عمود.

فيما يلي مصفوفة يمكن ملاحظتها لمساعدتنا على تذكر الرموز (حيث يمثل كل $* أي$ عدد حقيقي في المصفوفة):

$A^{(n-1)}={\begin{pmatrix}*&&&\cdots &&&*\\0&\ddots &&&&\\&\ddots &*&&&\\\vdots &&0&a_{n,n}^{(n-1)}&&&\vdots \\&&\vdots &a_{i,n}^{(n-1)}&*\\&&&\vdots &\vdots &\ddots \\0&\cdots &0&a_{i,n}^{(n-1)}&*&\cdots &*\end{pmatrix}}$

إجراء

خلال هذه العملية، نُعدِّل المصفوفة $A$ تدريجيًا باستخدام عمليات الصفوف حتى تصبح المصفوفة $U$ التي تكون فيها جميع العناصر أسفل القطر الرئيسي مساوية للصفر. وخلال ذلك، سنُنشئ في الوقت نفسه مصفوفتين منفصلتين $P$ و $L$ ، بحيث يكون $PA = LU$ .

نُعرّف مصفوفة التبديل النهائية $P$ بأنها مصفوفة الوحدة التي تحتوي على جميع الصفوف المتشابهة مُبدّلة بنفس الترتيب كما في المصفوفة $A$ ، وذلك عند تحويلها إلى المصفوفة $U.$ بالنسبة لمصفوفتنا $A (n -1)$ ، يُمكننا البدء بتبديل الصفوف لتوفير الشروط المطلوبة للعمود رقم $n$ . على سبيل المثال، يُمكننا تبديل الصفوف لإجراء تمحور جزئي، أو يُمكننا القيام بذلك لتعيين عنصر المحور $a n,n$ على القطر الرئيسي إلى عدد غير صفري حتى نتمكن من إكمال عملية الحذف الغاوسي.

بالنسبة لمصفوفتنا $A (n -1 )$ ، نريد أن نضع كل عنصر أسفل $a_{n,n}^{(n-1)}$ إلى الصفر (حيث $a_{n,n}^{(n-1)}$ (هو العنصر الموجود في العمود رقم $n$ من القطر الرئيسي). سنرمز لكل عنصر أدناه $a_{n,n}^{(n-1)}$ مثل $a_{i,n}^{(n-1)}$ (حيث $i = n + 1، ...، N$ ). لتعيين $a_{i,n}^{(n-1)}$ لتعيين الصفر، نضع $الصف i = الصف i - (ℓ i,n)\cdot الصف n$ لكل صف $i$ . لهذه العملية، ${\textstyle \ell _{i,n}:={a_{i,n}^{(n-1)}}/{a_{n,n}^{(n-1)}}}$ . بمجرد أن نقوم بإجراء عمليات الصف لأول $N - 1$ عمودًا، نحصل على مصفوفة مثلثية علوية $A (N -1)$ والتي يرمز لها بـ $U.$

يمكننا أيضًا إنشاء المصفوفة المثلثية السفلية المشار إليها بـ $L$ ، عن طريق إدخال القيم المحسوبة مسبقًا لـ $ℓ i,n$ مباشرةً عبر الصيغة أدناه.

$L={\begin{pmatrix}1&0&\cdots &0\\\ell _{2,1}&\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &0\\\ell _{N,1}&\cdots &\ell _{N,N-1}&1\end{pmatrix}}$

مثال

إذا أعطيت لنا المصفوفة $A={\begin{pmatrix}0&5&{\frac {22}{3}}\\4&2&1\\2&7&9\\\end{pmatrix}},$ سنختار تطبيق التمحور الجزئي، وبالتالي تبديل الصفين الأول والثاني بحيث تصبح مصفوفة $A$ والتكرار الأول لمصفوفة $P على التوالي$ $A^{(0)}={\begin{pmatrix}4&2&1\\0&5&{\frac {22}{3}}\\2&7&9\\\end{pmatrix}},\quad P^{(0)}={\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\\\end{pmatrix}}.$ بعد تبديل الصفوف، يمكننا حذف العناصر الموجودة أسفل القطر الرئيسي في العمود الأول عن طريق تنفيذ ${\begin{alignedat}{0}row_{2}=row_{2}-(\ell _{2,1})\cdot row_{1}\\row_{3}=row_{3}-(\ell _{3,1})\cdot row_{1}\end{alignedat}}$ بحيث، ${\begin{alignedat}{0}\ell _{2,1}={\frac {0}{4}}=0\\\ell _{3,1}={\frac {2}{4}}=0.5\end{alignedat}}$ بعد طرح هذه الصفوف، نكون قد استنتجنا من $A (1)$ المصفوفة $A^{(1)}={\begin{pmatrix}4&2&1\\0&5&{\frac {22}{3}}\\0&6&8.5\\\end{pmatrix}}.$

لأننا نقوم بتطبيق التمحور الجزئي، فإننا نبدل الصفين الثاني والثالث من المصفوفة المشتقة والنسخة الحالية من مصفوفة $P$ على التوالي للحصول على $A^{(1)}={\begin{pmatrix}4&2&1\\0&6&8.5\\0&5&{\frac {22}{3}}\\\end{pmatrix}},\quad P^{(1)}={\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\\\end{pmatrix}}.$ الآن، نحذف العناصر الموجودة أسفل القطر الرئيسي في العمود الثاني بإجراء العملية التالية: $الصف$ $3 = الصف 3 - (ℓ3,2) \cdot الصف 2، بحيث يكون ℓ3,2 = 5/6$ $.$ $ولأنه لا توجد عناصر غير صفرية أسفل القطر الرئيسي في$ $تكرارنا$ الحالي $للمصفوفة A بعد طرح$ هذا $الصف ،$ $فإن$ $طرح هذا الصف يُنتج مصفوفة A$ النهائية (المشار إليها بـ $U$ ) ومصفوفة $P$ النهائية . $A^{(2)}=A^{(N-1)}=U={\begin{pmatrix}4&2&1\\0&6&8.5\\0&0&0.25\\\end{pmatrix}},\quad P={\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\\\end{pmatrix}}.$ وبعد تبديل الصفوف المقابلة أيضاً، نحصل على مصفوفة $L$ النهائية : $L={\begin{pmatrix}1&0&0\\\ell _{3,1}&1&0\\\ell _{2,1}&\ell _{3,2}&1\\\end{pmatrix}}={\begin{pmatrix}1&0&0\\0.5&1&0\\0&{\frac {5}{6}}&1\\\end{pmatrix}}$

الآن، توجد علاقة بين هذه المصفوفات بحيث يكون $PA = LU$ .

العلاقات عندما لا يتم تبديل الصفوف

إذا لم نقم بتبديل الصفوف على الإطلاق خلال هذه العملية، فيمكننا إجراء عمليات الصفوف في وقت واحد لكل عمود $n$ عن طريق التعيين $A^{(n)}:=L_{n}^{-1}A^{(n-1)},$ أين $L_{n}^{-1}$ هي مصفوفة الوحدة $N$ × $N$ مع استبدال عمودها $n$ بالمتجه المنقول $(0 \dots 01 - ℓ n +1, n \dots - ℓ N, n) T$ .

بمعنى آخر، المصفوفة المثلثية السفلية $L_{n}^{-1}={\begin{pmatrix}1&&&&&\\&\ddots &&&&\\&&1&&&\\&&-\ell _{n+1,n}&&&\\&&\vdots &&\ddots &\\&&-\ell _{N,n}&&&1\end{pmatrix}}.$

إجراء جميع عمليات الصفوف لأول $N - 1$ عمودًا باستخدام $A^{(n)}:=L_{n}^{-1}A^{(n-1)}$ الصيغة تعادل إيجاد التفكيك $A=L_{1}L_{1}^{-1}A^{(0)}=L_{1}A^{(1)}=L_{1}L_{2}L_{2}^{-1}A^{(1)}=L_{1}L_{2}A^{(2)}=\dotsm =L_{1}\dotsm L_{N-1}A^{(N-1)}.$ تشير إلى $L = L 1 \dots L N -1$ بحيث $A = LA (N -1) = LU$ .

لنحسب الآن متتالية $L 1 \dots L N -1$ . نعلم أن $L i$ لها الصيغة التالية: $L_{n}={\begin{pmatrix}1&&&&&\\&\ddots &&&&\\&&1&&&\\&&\ell _{n+1,n}&&&\\&&\vdots &&\ddots &\\&&\ell _{N,n}&&&1\end{pmatrix}}$

إذا كانت لدينا مصفوفتان مثلثيتان سفليتان تحتويان على 1 في القطر الرئيسي، ولم تحتوي أي منهما على عنصر غير صفري أسفل القطر الرئيسي في نفس العمود، فيمكننا تضمين جميع العناصر غير الصفرية في نفس الموقع في حاصل ضرب المصفوفتين. على سبيل المثال:

$\left({\begin{array}{ccccc}1&0&0&0&0\\77&1&0&0&0\\12&0&1&0&0\\63&0&0&1&0\\7&0&0&0&1\end{array}}\right)\left({\begin{array}{ccccc}1&0&0&0&0\\0&1&0&0&0\\0&22&1&0&0\\0&33&0&1&0\\0&44&0&0&1\end{array}}\right)=\left({\begin{array}{ccccc}1&0&0&0&0\\77&1&0&0&0\\12&22&1&0&0\\63&33&0&1&0\\7&44&0&0&1\end{array}}\right)$

وأخيرًا، اضرب $L 1$ معًا لتكوين المصفوفة المدمجة $L$ (كما ذُكر سابقًا). باستخدام المصفوفة $L$ ، نحصل على $A = LU$ .

من الواضح أنه لكي تعمل هذه الخوارزمية، يجب أن يكون لدى المرء $a_{n,n}^{(n-1)}\neq 0$ في كل خطوة (انظر تعريف $ℓ i,n)$ . إذا لم يتحقق هذا الافتراض في مرحلة ما، يجب تبديل الصف رقم $n$ مع صف آخر أسفله قبل المتابعة. لهذا السبب، يبدو تحليل LU بشكل عام على النحو التالي: $P -1 A = LU$ .

تحلل لو باناتشيفيتش

على الرغم من أن خوارزمية تحليل LU لباناشيفيتش (1938) سبقت ظهور الحواسيب الإلكترونية المبرمجة، إلا أنها كانت جاهزة للتطبيق المباشر في الشيفرة البرمجية، حيث أن تبديل الفهارس، ونقل المصفوفة، والضرب العمودي، لا تزال من القدرات الأساسية لمعظم لغات البرمجة، ويتولى المترجمون تنفيذها دون تأخير يُذكر في التنفيذ الفعلي. وقد مكّنه ترميز المصفوفات الخاص الذي استخدمه باناشيفيتش من ضرب المصفوفات عمودًا بعمود، وهي ميزة ملائمة للحسابات الآلية، إذ كان بإمكانه تحديد العوامل المتتالية بتحريك مسطرة إلى الصفوف التالية من المصفوفات. أما بالنسبة للقراء، فمن الأفضل تحويل معادلاته إلى ترميز المصفوفات القياسي. وللحصول على حسابات المصفوفتين المثلثيتين $U$ و $L من مصفوفة$ $A$ كاملة ، ابدأ بنسخ الصف العلوي والعمود الأيسر من $A$ على التوالي إلى المواضع المقابلة في المصفوفتين $U$ و $L.$ لا يتم تخزين عناصر القطر الرئيسي المعروفة للمصفوفة $L$ ولا استخدامها طوال العملية. وتستمر الحسابات للصفوف والأعمدة اللاحقة حتى الزاوية السفلية اليمنى من $A.$

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

لاحظ أنه بعد إتمام المرحلة الثالثة ، لا تُستخدم عناصر المصفوفة $A المعنية، ولا عناصر المراحل السابقة. يُمكّن هذا من استبدال هذه العناصر بقيم$ $U$ و $L$ الناتجة ، أي تنفيذ تحليل LU في مكانه ، بحيث تُستبدل المصفوفة $A$ بالكامل بـ $U$ و $L$ باستثناء القطر الرئيسي لـ $L.$ تُعد خوارزمية Banachiewicz LU مناسبةً تمامًا للمحورية الجزئية، وذلك باختيار المحور الأقصى المطلق من الصف المحسوب حديثًا في $U$ ، ثم تبديل أعمدته بحيث يقع على القطر الرئيسي. يمكن الاطلاع على مزيد من التفاصيل في كود Fortran90 المرفق.

تتساوى تقريبًا تكلفة جميع خوارزميات LU ذات المحور الجزئي، من رتبة ${\textstyle O\left({2 \over 3}n^{3}\right)}$ العمليات، حيث $n$ هو عدد الصفوف أو الأعمدة في $A.$

تحلل فطر الكراوت في جامعة لويزيانا

لاحظ أن التفكيك الناتج عن هذه العملية هو تفكيك دوليتل : يتكون القطر الرئيسي للمصفوفة $L من الآحاد فقط. إذا قمنا بإزالة العناصر الموجودة$ أعلى القطر الرئيسي بإضافة مضاعفات الأعمدة ( بدلاً من إزالة العناصر الموجودة أسفل القطر بإضافة مضاعفات الصفوف ) ، فسنحصل على تفكيك كراوت ، حيث يكون القطر الرئيسي للمصفوفة $U$ مكونًا من الآحاد فقط.

$هناك$ طريقة أخرى (مكافئة) لإنتاج تحليل كراوت لمصفوفة معينة $A$ وهي الحصول على تحليل دوليتل لمنقولة $A.$ في الواقع، إذا كان $A$ $=$ $T$ $=$ $L₀U₀$ $هو$ $تحليل LU الذي$ تم الحصول عليه من خلال الخوارزمية المعروضة في هذا القسم، فعندئذٍ بأخذ $L$ $= U₀T₀$ $و$ $U$ $=$ L₀T₀ $،$ $نحصل$ على أن $A$ $= LU هو$ تحليل كراوت.

خوارزمية عشوائية

من الممكن إيجاد تقريب منخفض الرتبة لتحليل LU باستخدام خوارزمية عشوائية . بفرض وجود مصفوفة إدخال $A$ ورتبة منخفضة مطلوبة $k$ ، تُعيد خوارزمية LU العشوائية مصفوفات التبديل $P$ و $Q$ ، ومصفوفات شبه منحرفة سفلية/علوية $L$ و $U$ بحجم $m$ × $k$ و $k$ × $n$ على التوالي، بحيث يكون احتمال ‖PAQ − LU‖ 2 ≤ Cσ k +1 مرتفعًا $، حيث C ثابت يعتمد على معلمات الخوارزمية$ ^، و $σ$ $k$ +1 $هي$ $القيمة المفردة ($ k $+ 1)$ للمصفوفة $A.$ [ ^{14 ]}

التعقيد النظري

إذا أمكن ضرب مصفوفتين من الرتبة $n في زمن$ $M (n)$ ، حيث $M (n) \geq n a$ لبعض $a > 2$ ، فإنه يمكن حساب تحليل LU في زمن $O(M (n))$ . ^{[ 15 ]} هذا يعني، على سبيل المثال، وجود خوارزمية $O(n²³⁷⁶)$ مبنية على خوارزمية كوبرسميث-وينوغراد . انظر أيضًا مقالة خوارزميات ضرب المصفوفات السريعة $لمزيد$ من التفاصيل.

تحليل المصفوفة المتفرقة

طُوِّرت خوارزميات خاصة لتحليل المصفوفات المتفرقة الكبيرة . تحاول هذه الخوارزميات إيجاد عوامل متفرقة $L$ و $U.$ من الناحية المثالية، تُحدَّد تكلفة الحساب بعدد العناصر غير الصفرية، وليس بحجم المصفوفة.

تستخدم هذه الخوارزميات حرية تبديل الصفوف والأعمدة لتقليل التعبئة (الإدخالات التي تتغير من الصفر الأولي إلى قيمة غير صفرية أثناء تنفيذ الخوارزمية).

يمكن معالجة الترتيبات التي تقلل من التعبئة باستخدام نظرية الرسم البياني .

التطبيقات

حل المعادلات الخطية

بفرض نظام من المعادلات الخطية في شكل مصفوفة $A\mathbf {x} =\mathbf {b} ,$

نريد حل المعادلة لإيجاد قيمة $x$ ، بمعلومية $A$ و $b$ . لنفترض أننا حصلنا بالفعل على تحليل LUP لـ $A$ بحيث يكون $PA = LU$ ، وبالتالي $LU x = P b$ .

في هذه الحالة، يتم الحل في خطوتين منطقيتين:

أولاً، نقوم بحل المعادلة $L y = P b$ لإيجاد $قيمة y$ .
ثانيًا، نقوم بحل المعادلة $U x = y$ لإيجاد قيمة $x$ .

في كلتا الحالتين نتعامل مع المصفوفات المثلثية ( $L$ و $U$ )، والتي يمكن حلها مباشرة عن طريق التعويض الأمامي والخلفي دون استخدام عملية الحذف الغاوسي (ومع ذلك، نحتاج إلى هذه العملية أو ما يعادلها لحساب تحليل LU نفسه).

يمكن تطبيق الإجراء المذكور أعلاه بشكل متكرر لحل المعادلة عدة مرات لقيم مختلفة لـ $b$ . في هذه الحالة، يكون إجراء تحليل LU للمصفوفة $A$ مرة واحدة ثم حل المصفوفات المثلثية لقيم $b$ المختلفة أسرع (وأكثر ملاءمة) ، بدلاً من استخدام طريقة الحذف الغاوسي في كل مرة. يمكن اعتبار المصفوفتين $L$ و $U$ بمثابة "تشفير" لعملية الحذف الغاوسي.

تبلغ تكلفة حل نظام المعادلات الخطية حوالي $2/3$ $من$ $n³$ عملية حسابية للفاصلة العائمة إذا كان حجم المصفوفة $A$ $هو$ n $.$ $وهذا$ يجعلها أسرع بمرتين من الخوارزميات القائمة على تحليل QR $،$ والتي تتطلب حوالي $4/3$ $من$ $n³$ $عملية$ ^حسابية للفاصلة العائمة عند $استخدام$ انعكاسات هاوسهولدر . لهذا السبب $،$ يُفضل عادةً استخدام تحليل LU $.$ ^[ $16$ ^]

قلب المصفوفة

عند حل أنظمة المعادلات، يُعامل $b$ $عادةً كمتجه طوله يساوي ارتفاع المصفوفة A.$ أما في عملية عكس المصفوفة، فبدلاً من المتجه $b$ ، لدينا المصفوفة $B$ ، حيث $B$ مصفوفة من الرتبة $n$ × $p$ ، وبالتالي نحاول إيجاد المصفوفة $X$ (وهي أيضاً مصفوفة من الرتبة $n$ × $p$ ): $AX=LUX=B.$

يمكننا استخدام نفس الخوارزمية المعروضة سابقًا لحل كل عمود من أعمدة المصفوفة $X.$ لنفترض الآن أن $B$ هي مصفوفة الوحدة ذات الحجم $n$ ، $أي I$ = $n$ . يترتب على ذلك أن النتيجة $X$ يجب أن تكون معكوس $A.$ ^{[ 17 ]}

حساب المحدد

بمعرفة تحليل LUP للمصفوفة المربعة $A = P -1 LU$ $،$ يمكن حساب محدد $A مباشرةً كما يلي:$ ${\begin{aligned}\det(A)&=\det \left(P^{-1}\right)\det(L)\det(U)\\&=(-1)^{S}\left(\prod _{i=1}^{n}l_{ii}\right)\left(\prod _{i=1}^{n}u_{ii}\right).\end{aligned}}$

المعادلة الثانية تتبع من حقيقة أن محدد المصفوفة المثلثية هو ببساطة حاصل ضرب عناصرها القطرية، وأن محدد مصفوفة التبديل يساوي $(-1) S$ حيث $S$ هو عدد عمليات تبديل الصفوف في التفكيك.

في حالة تحليل LU مع التمحور الكامل، $فإن det(A)$ يساوي أيضًا الجانب الأيمن من المعادلة أعلاه، إذا افترضنا أن $S$ هو العدد الإجمالي لعمليات تبادل الصفوف والأعمدة.

يمكن تطبيق نفس الطريقة بسهولة على تحليل LU عن طريق جعل $P$ مساوية لمصفوفة الوحدة.

تاريخ

يرتبط تحليل LU بحذف أنظمة المعادلات الخطية، كما وصفه رالستون على سبيل المثال. ^{[ 18 ]} كان حل $N$ معادلة خطية في $N$ مجهولًا عن طريق الحذف معروفًا لدى الصينيين القدماء. ^{[ 19 ]} قبل غاوس، كان العديد من علماء الرياضيات في أوراسيا يطبقون هذه الطريقة ويطورونها، ولكن نظرًا لأن هذه الطريقة اقتصرت على المرحلة المدرسية، لم يترك سوى القليل منهم وصفًا تفصيليًا لها. لذا، فإن اسم "الحذف الغاوسي" ليس إلا اختصارًا مناسبًا لتاريخ معقد.

قدم عالم الفلك البولندي تاديوش باناتشيفيتش تحليل LU في عام 1938. ^{[ 20 ]} قال بول دوير عن باناتشيفيتش: ^{[ 21 ]}

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

— بول دوير، الحسابات الخطية (1951)

كان باناتشيفيتش ^{[ 20 ]} أول من نظر في عملية الحذف باستخدام المصفوفات، وبهذه الطريقة صاغ تحليل LU، كما هو موضح في رسمه التوضيحي. تتبع حساباته حسابات المصفوفات العادية، إلا أن الترميز يختلف حيث فضل كتابة أحد العوامل منقولًا، ليتمكن من ضربها آليًا عمودًا تلو الآخر، عن طريق تحريك المسطرة على الصفوف المتتالية من كليهما (باستخدام آلة الحساب ). مع تبديل ترتيب المؤشرات، تصبح صيغه بالترميز الحديث كما يلي: ${\begin{aligned}{\mathbf {x} }\cdot IA'={\mathbf {0} }&\rightarrow A'{\mathbf {x} =0}\equiv (A|{\mathbf {l} }){\mathbf {x} },\\A=G\cdot H&\rightarrow A^{T}=G^{T}H,\end{aligned}}$

حيث $IA \to A T$ ; $x \equiv [x 1, ... , x n, -1]$ ; $A'$ تشير إلى $A$ الموسعة بالعمود الأخير؛ والمكون الأخير من $x$ هو $-1$ . ترد صيغ المصفوفات لحساب صفوف وأعمدة عوامل LU بالاستدعاء الذاتي في الجزء المتبقي من ورقة باناتشيفيتش في المعادلتين (2.3) و(2.4). تتضمن هذه الورقة، التي كتبها باناتشيفيتش، اشتقاق عوامل $LU$ و $R T R$ للمصفوفات غير المتناظرة والمتناظرة على التوالي. يحدث خلط بينهما أحيانًا، حيث تميل المنشورات اللاحقة إلى ربط اسمه فقط بإعادة اكتشاف تحليل تشوليسكي. يمكن تبرير عدم تحرك باناتشيفيتش نفسه لأنه عانى بالفعل في العام التالي من اضطهاد المحتلين، حيث أمضى ثلاثة أشهر في معسكر اعتقال ساكسنهاوزن ، وعند إطلاق سراحه حمل بنفسه من القطار زميله المتعاون معه ورفيقه في السجن أنطوني ويلك، الذي توفي من الإرهاق بعد أسبوع.

أمثلة على التعليمات البرمجية

مثال على كود Fortran90

وحدة mlu ضمنية لا شيء عدد صحيح ، معامل :: SP = نوع ( 1 d0 ) ! ضبط دقة الإدخال/الإخراج حقيقي خاص  عام luban ، lusolve يحتوي على  روتين فرعي luban ( a ، tol ، g ، h ، ip ، condinv ، detnth ) ! بواسطة Banachiewicz (1938، المشار إليه فيما يلي بـ B38) طريقة تحليل LU تحسب ! المثلثات L=G^T، وU=H بحيث يكون المربع B=A^T=G^TH=LU. التمحور الجزئي ! عن طريق تبديل الأعمدة IP(:) هو إضافة حديثة. ! داخل الكود، يتوافق a وg مع B38 A^T وG^T، بحيث يتحقق a=gh. ! ! الاستخدام العادي هو للمربع A، ولكن بالنسبة للطرف الأيمن l المعروف بالفعل ! المدخل (A|l)^T ينتج (L|y^T)^T حيث x في L^Tx=y هو حل Ax=l. حقيقي ( SP )، غرض ( In ) :: a (:, :) ! مصفوفة الإدخال A(m,n)، حيث n ≤ m، عدد حقيقي ( SP )، غرض ( الإدخال ) : tol ! التسامح مع المحور القريب من الصفر، عدد حقيقي ( SP )، غرض ( الإخراج ) : g ( size ( a , dim = 1 ), size ( a , dim = 2 )) ! L(m,n) ، عدد حقيقي ( SP )، غرض ( الإخراج ) : h ( size ( a , dim = 2 ), size ( a , dim = 2 )) ! U(n,n) ! ملاحظة: يتم تبديل أعمدة U، عدد حقيقي ( SP )، غرض ( الإخراج ) : condinv ! 1/cond(A)، 0 للمصفوفة A المفردة، عدد حقيقي ( SP )، غرض ( الإخراج ) : detnth ! sign*Abs(det(A))**(1/n)، عدد صحيح ، غرض ( الإخراج ) : ip( size ( a , dim = 2 )) ! تبديل الأعمدة ! عدد صحيح :: k , n , j , l , isig عدد حقيقي ( SP ) :: tol0 , pivmax , pivmin , piv ! n = size ( a , dim = 2 ) tol0 = Max ( tol , 3._SP * epsilon ( tol0 )) ! استخدم القيمة الافتراضية لـ tol=0 ! ! يُسمح بالمصفوفات المستطيلة A و G في حالة الشرط: إذا كان ( n > size ( a , dim = 1 ) . أو . n < 1 ) توقف 91 لكل ( k = 1 : n ) ip ( k ) = k h = 0._SP g = 0._SP isig = 1 detnth = 0._SP pivmax = Maxval ( Abs ( a ( 1 , :))) pivmin = pivmax ! كرر k = 1 , n ! معادلة باناتشيفيتش (1938). (2.3) h ( k , ip ( k :)) = a ( k , ip ( k :)) - Matmul ( g ( k , : k - 1 ), h (: k - 1 , ip ( k :)) ! ! إيجاد عنصر الارتكاز للصف j = ( Maxloc ( Abs ( h ( k , ip ( k :)), dim = 1 ) + k - 1إذا كان ( j ≠ k ) فإن: ! تبديل العمودين j و k isig = -isig ! تغيير إشارة Det(A) بسبب التبديل l = ip ( k ) ip ( k ) = ip ( j ) ip ( j ) = l نهاية الشرط piv = Abs ( h ( k , ip ( k ))) pivmax = Max ( piv , pivmax ) ! ضبط condinv pivmin = Min ( piv , pivmin ) إذا كان ( piv < tol0 ) فإن: ! مصفوفة منفردة isig = 0 pivmax = 1._SP خروج  وإلا: ! مراعاة مساهمة المحور في إشارة وقيمة Det(A) إذا كان ( h ( k , ip ( k )) < 0._SP ) isig = -isig detnth = detnth + Log ( piv ) نهاية الشرط ! ! منقول معادلة باناشيفيتز (1938) . (2.4) g ( k + 1 :, k ) = ( a ( k + 1 :, ip ( k )) - & Matmul ( g ( k + 1 :, : k - 1 ), h (: k - 1 , ip ( k )))) / h ( k , ip ( k )) g ( k , k ) = 1._SP End Do ! detnth = isig * Exp ( detnth / n ) condinv = Abs (isig ) * pivmin / pivmax ! اختبر المربع A(n,n) عن طريق إزالة التعليق أدناه ! اطبع *, '|AQ-LU| ',Maxval (Abs(a(:,ip(:))-Matmul(g, h(:,ip(:))))) نهاية الروتين الفرعي luban الروتين الفرعي lusolve ( l , u , ip , x ) ! يحل نظام Ax=b باستخدام عوامل المثلث LU=A Real ( SP ), Intent ( In ) :: l (:, :) ! مصفوفة المثلث السفلي L(n,n) Real ( SP ), Intent ( In ) :: u (:, :) ! مصفوفة المثلث العلوي U(n,n) Integer , Intent ( In ) :: ip (:) ! تبديل الأعمدة IP(n) Real ( SP ), Intent ( InOut ) :: x (:, :) ! المدخلات: m مجموعة من الأطراف اليمنى B(n,m), ! الناتج: مجموعات المجاهيل المقابلة X(n,m) عدد صحيح :: n ، m ، i ، j n = حجم ( ip ) m = حجم ( x ، البعد = 2 ) إذا ( n < 1. أو m < 1. أو أي ( [ n ، n ] /= شكل ( l )). أو أي ( شكل ( l ) / = شكل ( u ) ) . أو & n / = حجم ( x ، البعد = 1 )) توقف 91 كرر i = 1 ، m كرر j = 1 ، n x ( j ، i ) = x ( j ، i ) - حاصل الضرب النقطي ( x(: j - 1 , i ), l ( j ,: j - 1 )) End Do  Do j = n , 1 , - 1 x ( j , i ) = ( x ( j , i ) - dot_product ( x ( j + 1 :, i ), u ( j , ip ( j + 1 :)))) / & u ( j , ip ( j )) End Do  End Do  End Subroutine lusolve End Module mlu

مثال على كود C

/* المدخلات: A - مصفوفة من المؤشرات إلى صفوف مصفوفة مربعة ذات بُعد N * Tol - رقم سماحية صغير لاكتشاف الفشل عندما تكون المصفوفة قريبة من الانحلال * المخرجات: يتم تغيير المصفوفة A، وتحتوي على نسخة من كلتا المصفوفتين LE و U حيث A=(LE)+U بحيث P*A=L*U. * لا يتم تخزين مصفوفة التبديل كمصفوفة، ولكن في متجه عدد صحيح P بحجم N+1 * يحتوي على مؤشرات الأعمدة حيث تحتوي مصفوفة التبديل على "1". العنصر الأخير P[N]=S+N، * حيث S هو عدد عمليات تبديل الصفوف اللازمة لحساب المحدد، det(P)=(-1)^S */ int LUPDecompose ( double ** A , int N , double Tol , int * P ) {int i , j , k , imax ; double maxA , * ptr , absA ;for ( i = 0 ; i <= N ; i ++ ) P [ i ] = i ; // مصفوفة التبديل الوحدوية، P[N] مهيأة بالقيمة Nfor ( i = 0 ; i < N ; i ++ ) { maxA = 0.0 ; imax = i ;for ( k = i ; k < N ; k ++ ) if (( absA = fabs ( A [ k ][ i ])) > maxA ) { maxA = absA ; imax = k ; }إذا كانت قيمة maxA أقل من Tol ، فأرجع 0 ؛ // فشل، المصفوفة متدهورةإذا كان ( imax != i ) { // تحويل P j = P [ i ]; P [ i ] = P [ imax ]; P [ imax ] = j ;// تحويل صفوف المصفوفة A ptr = A [ i ]; A [ i ] = A [ imax ]; A [ imax ] = ptr ;// عدّ المحاور بدءًا من N (للحصول على المحدد) P [ N ] ++ ; }for ( j = i + 1 ; j < N ; j ++ ) { A [ j ][ i ] /= A [ i ][ i ];for ( k = i + 1 ; k < N ; k ++ ) A [ j ][ k ] -= A [ j ][ i ] * A [ i ][ k ]; } }return 1 ; // تم الانتهاء من عملية التفكيك }/* المدخلات: A وP مُعبأتان في LUPDecompose؛ b - متجه الطرف الأيمن؛ N - البُعد * المخرجات: x - متجه حل المعادلة A*x=b */ void LUPSolve ( double ** A , int * P , double * b , int N , double * x ) {for ( int i = 0 ; i < N ; i ++ ) { x [ i ] = b [ P [ i ]];for ( int k = 0 ; k < i ; k ++ ) x [ i ] -= A [ i ][ k ] * x [ k ]; }for ( int i = N - 1 ; i >= 0 ; i-- ) { for ( int k = i + 1 ; k < N ; k ++ ) x [ i ] -= A [ i ] [ k ] * x [ k ];x [ i ] /= A [ i ][ i ]; } }/* المدخلات: A وP مُعبأتان في LUPDecompose؛ N - بُعد * المخرجات: IA هي معكوس المصفوفة الأصلية */ void LUPInvert ( double ** A , int * P , int N , double ** IA ) { for ( int j = 0 ; j < N ; j ++ ) { for ( int i = 0 ; i < N ; i ++ ) { IA [ i ][ j ] = P [ i ] == j ? 1.0 : 0.0 ;for ( int k = 0 ; k < i ; k ++ ) IA [ i ][ j ] -= A [ i ][ k ] * IA [ k ][ j ]; }for ( int i = N - 1 ; i >= 0 ; i-- ) { for ( int k = i + 1 ; k < N ; k ++ ) IA [ i ][ j ] -= A [ i ] [ k ] * IA [ k ][ j ];IA [ i ][ j ] /= A [ i ][ i ]; } } }/* المدخلات: A وP مُعبأتان في LUPDecompose؛ N - بُعد. * المخرجات: تُعيد الدالة مُحدِّد المصفوفة الأصلية */ double LUPDeterminant ( double ** A , int * P , int N ) {double det = A [ 0 ][ 0 ];for ( int i = 1 ; i < N ; i ++ ) det *= A [ i ][ i ];العودة ( P [ N ] - N ) % 2 == 0 ؟ ديت : - ديت ; }

مثال على كود C#

public class SystemOfLinearEquations { public double [] SolveUsingLU ( double [,] matrix , double [] rightPart , int n ) { // تحليل المصفوفة double [,] lu = new double [ n , n ]; double sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i ; j < n ; j ++ ) { sum = 0 ; for ( int k = 0 ; k < i ; k ++ ) sum += lu [ i , k ] * lu [ k , j ]; lu [ i , j ] = matrix [ i , j ] - sum ; } for ( int j = i + 1 ; j < n ; j ++ ) { sum = 0 ; for ( int k = 0 ; k < i ; k ++ ) sum += lu [ j , k ] * lu [ k , i ]; lu [ j , i ] = ( 1 / lu [ i , i ]) * ( matrix [ j , i ] - sum ); } }// lu = L+UI // إيجاد حل للمعادلة Ly = b double [] y = new double [ n ]; for ( int i = 0 ; i < n ; i ++ ) { sum = 0 ; for ( int k = 0 ; k < i ; k ++ ) sum += lu [ i , k ] * y [ k ]; y [ i ] = rightPart [ i ] - sum ; } // إيجاد حل للمعادلة Ux = y double [ ] x = new double [ n ]; for ( int i = n - 1 ; i >= 0 ; i-- ) { sum = 0 ; for ( int k = i + 1 ; k < n ; k ++ ) sum += lu [ i , k ] * x [ k ]; x [ i ] = ( 1 / lu [ i , i ]) * ( y [ i ] - sum ); } return x ; } }

مثال على كود MATLAB

الدالة LU = LUDecompDoolittle ( A ) n = الطول ( A ); لو = أ ؛ for k = 2 : n for i = 1 : k - 1 lamda = LU ( k , i ) / LU ( i , i ) ; لو ( ك , ط ) = لامدا ; LU ( ك , i + 1 : n ) = LU ( ك , i + 1 : n ) - LU ( i , i + 1 : n ) * لامدا ; نهاية نهاية نهايةدالة x = SolveLinearSystem ( LU, B ) n = length ( LU ); y = zeros ( size ( B )); % إيجاد حل Ly = B for i = 1 : n y ( i ,:) = B ( i ,:) - LU ( i , 1 : i ) * y ( 1 : i ,:); end % إيجاد حل Ux = y x = zeros ( size ( B )); for i = n :( - 1 ): 1 x ( i ,:) = ( y ( i ,:) - LU ( i ,( i + 1 ): n ) * x (( i + 1 ): n ,:)) / LU ( i , i ); end endA = [ 4 3 3 ; 6 3 3 ; 3 4 3 ] LU = LUDecompDoolittle ( A ) B = [ 1 2 3 ; 4 5 6 ; 7 8 9 ; 10 11 12 ] ' x = SolveLinearSystem ( LU , B ) A * x

انظر أيضاً

ملحوظات

↑ شوارزنبرغ-تشيرني، أ. (1995). "حول تحليل المصفوفات وحل المربعات الصغرى الفعال" . سلسلة ملاحق علم الفلك والفيزياء الفلكية . 110 : 405. Bibcode : 1995A & AS..110..405S .
↑ كورمن وآخرون (2009) ، ص. 819 ، 28.1: حل أنظمة المعادلات الخطية.
1 2 أوكونيف وجونسون (1997) ، النتيجة 3 .
^ تريفثين وباو (1997) ، ص. 166.
^ تريفثين وباو (1997) ، ص. 161.
↑ Banachiewicz (1938) ؛ Lay, Lay & McDonald (2021) ، ص. 133 ، 2.5: تحليل المصفوفات.
^ ريجوتي (2001) ، قائد رئيسي ثانوي.
1 2 هورن وجونسون (1985) ، النتيجة 3.5.5
↑ هورن وجونسون (1985) ، النظرية 3.5.2.
↑ نياي، لي؛ فان-يامادا، تويتدونغ (2021). "دراسة إمكانية تحليل LU". مجلة أمريكا الشمالية لجيوجبرا . 9 (1).
↑ أوكونيف وجونسون (1997) .
↑ هاوسهولدر (1975) .
^ جولوب وفان لون (1996) ، ص 112، 119.
↑ شبات، جيل؛ شموئيلي، يانيف؛ أيزنبود، ياريف؛ أفيربوش، أمير (2016). “التحلل العشوائي LU”. التحليل التوافقي التطبيقي والحاسوبي . 44 (2): 246– 272. أرخايف : 1310.7202 . دوى : 10.1016/j.acha.2016.04.006 . S2CID 1900701 .
↑ بانش وهوبكروفت (1974) .
^ تريفثين وباو (1997) ، ص. 152.
^ جولوب وفان لون (1996) ، ص. 121.
↑ رالستون (1965) .
↑ هارت (2011) .
1 2 باناتشيفيتش (1938) .
↑ دوير (1951) .

مراجع

Banachiewicz، T. (1938)، “Méthode de résolution numérique des équations linéaires…” (PDF) ، Bull. المتدرب. دي لاكاد. بولونيز، سيري أ. الرياضيات. : 393 – 404.
بانش، جيمس ر.؛ هوبكروفت، جون (1974)، "تحليل المصفوفات المثلثية وعكسها عن طريق ضرب المصفوفات السريع"، رياضيات الحساب ، 28 (125): 231-236 ، doi : 10.2307/2005828 ، hdl : 1813/6003 ، ISSN 0025-5718 ، JSTOR 2005828 .
كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين ، كليفورد (2009)، مقدمة للخوارزميات ( الطبعة الثالثة)، مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل، ISBN 978-0-262-03293-3.
دوير، بول س. (1951)، الحسابات الخطية ، نيويورك: وايلي.
جولوب، جين هـ .؛ فان لون، تشارلز ف. (1996)، حسابات المصفوفات ( الطبعة الثالثة)، بالتيمور: جونز هوبكنز، ISBN 978-0-8018-5414-9.
هارت، روجر (2011)، الجذور الصينية للجبر الخطي ، بالتيمور: جونز هوبكنز، ISBN 978-0801897559.
هورن، روجر أ.؛ جونسون، تشارلز ر. (1985)، تحليل المصفوفات ، مطبعة جامعة كامبريدج، ISBN 978-0-521-38632-6انظر القسم 3.5. N − 1
هاوسهولدر، ألستون س. (1975)، نظرية المصفوفات في التحليل العددي ، نيويورك: منشورات دوفر ، MR 0378371 .
لاي، ديفيد سي؛ لاي، ستيفن آر؛ ماكدونالد، جودي جيه (2021)، الجبر الخطي وتطبيقاته ( الطبعة السادسة)، بيرسون، ISBN 978-0-13-585125-8.
أوكونيف، بافيل؛ جونسون، تشارلز ر. (1997)، الشروط الضرورية والكافية لوجود تحليل LU لمصفوفة عشوائية ، arXiv : math.NA/0506382.
بول، ديفيد (2006)، الجبر الخطي: مقدمة حديثة ( الطبعة الثانية)، كندا: تومسون بروكس/كول، رقم ISBN 978-0-534-99845-5.
رالستون، أنتوني (1965)، مدخل إلى التحليل العددي ، نيويورك: ماكجرو هيل، رقم ISBN 978-0-070-51157-6.
بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007)، "القسم 2.3" ، وصفات عددية: فن الحوسبة العلمية ( الطبعة الثالثة)، نيويورك: مطبعة جامعة كامبريدج، رقم ISBN 978-0-521-88068-8.
تريفثين، لويد ن .؛ باو، ديفيد (1997)، الجبر الخطي العددي ، فيلادلفيا: جمعية الرياضيات الصناعية والتطبيقية، ISBN 978-0-89871-361-9.
ريغوتي، لوكا (2001)، ECON 2001 - مقدمة في الأساليب الرياضية، المحاضرة 8

روابط خارجية

مراجع

تحليل LU على موقع MathWorld .
تحليل LU على نظام Math-Linux .
تحليل LU في معهد الأساليب العددية الشاملة
تحليل المصفوفات باستخدام طريقة LU . مرجع MATLAB.

شفرة الحاسوب

LAPACK عبارة عن مجموعة من الإجراءات الفرعية المكتوبة بلغة FORTRAN لحل مسائل الجبر الخطي الكثيف
يتضمن ALGLIB منفذًا جزئيًا لـ LAPACK إلى C++ و C# و Delphi وما إلى ذلك.
كود C++ ، الأستاذ ج. لوميس، جامعة دايتون
كود C ، مكتبة مصادر الرياضيات
كود Rust
LU في X10

الموارد الإلكترونية

تطبيق ويب يقوم بحل أنظمة المعادلات الخطية وصفياً باستخدام تحليل LU
حاسبة المصفوفات مع خطوات، بما في ذلك تحليل LU ،
أداة تحليل LU ، uni-bonn.de
تحليل LU بواسطة إد بيج الابن ، مشروع عروض وولفرام ، 2007.

[Schwarzenberg-1] شوارزنبرغ-تشيرني، أ. (1995). "حول تحليل المصفوفات وحل المربعات الصغرى الفعال" . سلسلة ملاحق علم الفلك والفيزياء الفلكية . 110 : 405. Bibcode : 1995A & AS..110..405S .

[FOOTNOTECormenLeisersonRivestStein2009[httpsarchiveorgdetailsintroduction-to-algorithms-third-edition-2009page819_819]28.1:_Solving_systems_of_linear_equations-2] كورمن وآخرون (2009) ، ص. 819 ، 28.1: حل أنظمة المعادلات الخطية.

[okunev-cor3-3] 1 2 أوكونيف وجونسون (1997) ، النتيجة 3 .

[FOOTNOTETrefethenBau1997166-4] تريفثين وباو (1997) ، ص. 166.

[FOOTNOTETrefethenBau1997161-5] تريفثين وباو (1997) ، ص. 161.

[FOOTNOTEBanachiewicz1938LayLayMcDonald2021[httpsarchiveorgdetailslinear-algebra-its-applications-6thpage133_133]2.5:_Matrix_Factorizations-6] Banachiewicz (1938) ؛ Lay, Lay & McDonald (2021) ، ص. 133 ، 2.5: تحليل المصفوفات.

[FOOTNOTERigotti2001Leading_Principal_Minor-7] ريجوتي (2001) ، قائد رئيسي ثانوي.

[horn-cor355-8] 1 2 هورن وجونسون (1985) ، النتيجة 3.5.5

[FOOTNOTEHornJohnson1985Theorem_3.5.2-9] هورن وجونسون (1985) ، النظرية 3.5.2.

[10] نياي، لي؛ فان-يامادا، تويتدونغ (2021). "دراسة إمكانية تحليل LU". مجلة أمريكا الشمالية لجيوجبرا . 9 (1).

[FOOTNOTEOkunevJohnson1997-11] أوكونيف وجونسون (1997) .

[FOOTNOTEHouseholder1975-12] هاوسهولدر (1975) .

[FOOTNOTEGolubVan_Loan1996112,_119-13] جولوب وفان لون (1996) ، ص 112، 119.

[14] شبات، جيل؛ شموئيلي، يانيف؛ أيزنبود، ياريف؛ أفيربوش، أمير (2016). “التحلل العشوائي LU”. التحليل التوافقي التطبيقي والحاسوبي . 44 (2): 246– 272. أرخايف : 1310.7202 . دوى : 10.1016/j.acha.2016.04.006 . S2CID 1900701 .

[FOOTNOTEBunchHopcroft1974-15] بانش وهوبكروفت (1974) .

[FOOTNOTETrefethenBau1997152-16] تريفثين وباو (1997) ، ص. 152.

[FOOTNOTEGolubVan_Loan1996121-17] جولوب وفان لون (1996) ، ص. 121.

[FOOTNOTERalston1965-18] رالستون (1965) .

[FOOTNOTEHart2011-19] هارت (2011) .

[FOOTNOTEBanachiewicz1938-20] 1 2 باناتشيفيتش (1938) .

[FOOTNOTEDwyer1951-21] دوير (1951) .

[

[ 3 ]

[ 4 ]

،

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

ذات

،

[ 15 ]

حسابية

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗