تحلل تشوليسكي

إذا كانت المصفوفة الهرميتية A شبه موجبة فقط، بدلاً من كونها موجبة تمامًا، فإنها لا تزال قابلة للتحليل على الصورة A = LL * حيث يُسمح بأن تكون عناصر القطر الرئيسي للمصفوفة L أصفارًا. ^{[ 7 ]} ولا يشترط أن يكون هذا التحليل فريدًا، على سبيل المثال: $${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}=\mathbf {L} \mathbf {L} ^{*},\quad \quad \mathbf {L} ={\begin{bmatrix}0&0\\\cos \theta &\sin \theta \end{bmatrix}},}$$ لأي قيمة لـ θ . ومع ذلك، إذا كانت رتبة A هي r ، فإنه يوجد مثلث سفلي وحيد L يحتوي على r عنصر قطري موجب بالضبط و n − r عمود تحتوي جميعها على أصفار. ^{[ 8 ]}

بدلاً من ذلك، يمكن جعل التفكيك فريدًا عند تحديد اختيار محوري. رسميًا، إذا كانت A مصفوفة شبه موجبة من الرتبة r من الرتبة n × n ، فإنه يوجد على الأقل مصفوفة تبديل واحدة P بحيث يكون لـ PAP ^T تفكيك فريد على الصورة PAP ^T = LL ^* مع ${\textstyle \mathbf {L} ={\begin{bmatrix}\mathbf {L} _{1}&0\\\mathbf {L} _{2}&0\end{bmatrix}}}$حيث L1 هي مصفوفة مثلثية سفلية من الرتبة _r × r ذات قطر موجب. ^{[ 9 ]}

يُستخدم تحليل تشوليسكي بشكل أساسي للحل العددي للمعادلات الخطية${\textstyle \mathbf {Ax} =\mathbf {b} }$إذا كانت المصفوفة A متناظرة وموجبة التحديد، فإن ${\textstyle \mathbf {Ax} =\mathbf {b} }$يمكن حلها عن طريق حساب تحليل تشوليسكي أولاً ${\textstyle \mathbf {A} =\mathbf {LL} ^{\mathrm {*} }}$ثم حلها${\textstyle \mathbf {Ly} =\mathbf {b} }$لإيجاد قيمة y عن طريق التعويض الأمامي ، ثم حل المعادلة في النهاية.${\textstyle \mathbf {L^{*}x} =\mathbf {y} }$لإيجاد قيمة x باستخدام التعويض العكسي .

طريقة بديلة لتجنب حساب الجذور التربيعية في${\textstyle \mathbf {LL} ^{\mathrm {*} }}$التحليل هو حساب تفكيك LDL${\textstyle \mathbf {A} =\mathbf {LDL} ^{\mathrm {*} }}$ثم حلها${\textstyle \mathbf {Ly} =\mathbf {b} }$بالنسبة لـ y ، وأخيراً حل${\textstyle \mathbf {DL} ^{\mathrm {*} }\mathbf {x} =\mathbf {y} }$.

بالنسبة للأنظمة الخطية التي يمكن صياغتها في شكل متناظر، يُعد تحليل تشوليسكي (أو أحد متغيراته LDL) الطريقة المُفضلة، لما يتميز به من كفاءة واستقرار عددي فائقين . وبالمقارنة مع تحليل LU ، فهو أكثر كفاءة بمرتين تقريبًا. ^{[ 2 ]}

في مسألة المربعات الصغرى الخطية، يُبحث عن حل x لنظام المعادلات الزائد التحديد Ax = l ، بحيث يكون المعيار التربيعي لمتجه الباقي Ax-l في أدنى قيمة له. ويمكن تحقيق ذلك عن طريق حل المعادلات العادية باستخدام تحليل تشوليسكي.${\displaystyle \mathbf {Nx} =\mathbf {A} ^{\mathsf {T}}\mathbf {l} }$، أين${\displaystyle \mathbf {N} =\mathbf {A} ^{\mathsf {T}}\mathbf {A} }$هي مصفوفة متناظرة موجبة التحديد. قد تنشأ مصفوفة المعادلة المتناظرة أيضًا من دالة طاقة، والتي يجب أن تكون موجبة لأسباب فيزيائية؛ ويحدث هذا بشكل متكرر في الحل العددي للمعادلات التفاضلية الجزئية .

تُعدّ هذه الطريقة اقتصادية وفعّالة في العديد من التطبيقات، إلا أنها تفشل في حالة الأعداد الطبيعية شبه المنفردة . ويتضح ذلك جلياً في الحالة الشاذة للمربعات.${\displaystyle \mathbf {A} }$حيث يكون محدد المصفوفة N هو مربع محدد النظام الأصلي Ax = l . عندئذٍ، يُفضّل تطبيق تحليل القيم المفردة (SVD) أو تحليل QR. يتميز تحليل QR لمعادلات جيفنز بأنه، على غرار المعادلات العادية، لا يتطلب الاحتفاظ بالمصفوفة A كاملةً ، إذ يُمكن تحديث عامل تشوليسكي باستخدام الصفوف المتتالية من A.

تُعدّ طريقة المربعات الصغرى غير الخطية حالة خاصة من التحسين غير الخطي. لنفترض${\textstyle \mathbf {f} (\mathbf {x} )=\mathbf {l} }$أن يكون نظامًا من المعادلات المحددة بشكل زائد مع دالة غير خطية${\displaystyle \mathbf {f} }$إرجاع نتائج متجهة. الهدف هو تقليل المعيار التربيعي للبواقي.${\textstyle \mathbf {v} =\mathbf {f} (\mathbf {x} )-\mathbf {l} }$يتم الحصول على حل تقريبي لطريقة نيوتن عن طريق توسيع${\displaystyle \mathbf {f} }$في سلسلة تايلور المختصرة${\displaystyle {\bf {f(x_{\rm {0}}+\delta x)\approx f(x_{\rm {0}})+(\partial f/\partial x)\delta x}}}$ينتج عنه مسألة المربعات الصغرى الخطية لـ${\displaystyle {\bf {\delta x}}}$

${\displaystyle {\bf {(\partial f/\partial x)\delta x=l-f(x_{\rm {0}})=v,\;\;\min _{\delta x}=\|v\|^{2}}}.}$

بالطبع، بسبب إهمال حدود تايلور العليا، فإن هذا الحل تقريبي فقط، إن وُجد أصلاً. الآن يمكن تحديث نقطة التوسع إلى${\displaystyle {\bf {x_{\rm {n+1}}=x_{\rm {n}}+\delta x}}}$ ثم تُكرر العملية برمتها، على أمل أن (أ) تتقارب التكرارات نحو حل، و(ب) أن يكون هذا الحل هو المطلوب. لسوء الحظ، لا يوجد ضمان لأي منهما، ويجب التحقق منه.

يمكن أيضًا تطبيق طريقة المربعات الصغرى غير الخطية على مسألة المربعات الصغرى الخطية عن طريق تحديد${\displaystyle {\bf {x_{\rm {0}}=0}}}$و${\displaystyle {\bf {f(x_{\rm {0}})=Ax}}}$قد يكون هذا مفيدًا إذا أسفر تحليل تشوليسكي عن معكوس غير دقيق${\displaystyle {\bf {R^{\rm {-1}}}}}$بالنسبة لمصفوفة المثلث حيث ${\displaystyle {\bf {R^{\rm {T}}R=N}}}$بسبب أخطاء التقريب. يُطلق على هذا الإجراء اسم التصحيح التفاضلي للحل. طالما أن التكرارات تتقارب، فإنها، بفضل نظرية باناش للنقطة الثابتة، تُعطي الحل بدقة لا يحدها سوى دقة البواقي المحسوبة.${\displaystyle {\bf {v=Ax-l}}}$الدقة مستقلة عن أخطاء التقريب في${\displaystyle {\bf {R^{\rm {-1}}}}}$. فقير${\displaystyle {\bf {R^{\rm {-1}}}}}$قد يحد من منطقة البداية${\displaystyle {\bf {x_{\rm {0}}}}}$ يؤدي ذلك إلى التقارب أو يمنعه تمامًا. عادةً ما يكون التقارب أبطأ، على سبيل المثال، التقارب الخطي، بحيث${\displaystyle {\bf {\|\delta x_{\rm {n+1}}\|\approx \|=\alpha \delta x_{\rm {n}}\|}}}$حيث ثابت ${\displaystyle \alpha <1}$قد يتم تسريع هذا التقارب البطيء بواسطة أيتكن${\displaystyle \delta ^{2}}$طريقة. إذا كان حساب${\displaystyle {\bf {R^{\rm {-1}}}}}$على الرغم من تكلفتها العالية، إلا أنه من الممكن استخدامها من التكرارات السابقة طالما تم الحفاظ على التقارب. قد تنجح طريقة تشوليسكي هذه حتى مع مصفوفات هيلبرت، المعروفة بصعوبة عكسها. ^{[ 15 ]}

يمكن تقليل قيمة الدوال غير الخطية متعددة المتغيرات بالنسبة لمعاملاتها باستخدام متغيرات من طريقة نيوتن تسمى طرق شبه نيوتن . في التكرار k، تتحرك خطوات البحث في اتجاه${\textstyle p_{k}}$يتم تعريفها عن طريق حل${\textstyle B_{k}p_{k}=-g_{k}}$ل${\textstyle p_{k}}$، أين${\textstyle p_{k}}$هذا هو اتجاه الخطوة،${\textstyle g_{k}}$هو التدرج ، و${\textstyle B_{k}}$هي تقريب لمصفوفة هيسيان المُشكَّلة بتكرار تحديثات الرتبة 1 في كل تكرار. من أشهر صيغ التحديث صيغتا ديفيدون-فليتشر-باول (DFP) وبرودن-فليتشر-غولدفراب-شانو (BFGS). يُمكن تجنب فقدان شرط التحديد الموجب نتيجة خطأ التقريب إذا تم تحديث تحليل تشوليسكي لتقريب مصفوفة هيسيان نفسها بدلاً من تحديث تقريب لمعكوس مصفوفة هيسيان. ^{[ 16 ]}

يُستخدم تحليل تشوليسكي بشكل شائع في طريقة مونت كارلو لمحاكاة الأنظمة ذات المتغيرات المتعددة المترابطة. يتم تحليل مصفوفة التغاير للحصول على المصفوفة المثلثية السفلية L. بتطبيق هذا التحليل على متجه من المشاهدات غير المترابطة في عينة u، ينتج متجه عينة Lu بخصائص التغاير للنظام قيد النمذجة. ^{[ 17 ]}

يوضح المثال المبسط التالي الاقتصاد الذي يمكن الحصول عليه من تحليل تشوليسكي: لنفترض أن الهدف هو توليد متغيرين طبيعيين مترابطين${\textstyle x_{1}}$و${\textstyle x_{2}}$بمعامل ارتباط معين${\textstyle \rho }$ولتحقيق ذلك، من الضروري أولاً توليد متغيرين عشوائيين غاوسيين غير مرتبطين.${\textstyle z_{1}}$و${\textstyle z_{2}}$(على سبيل المثال، عبر تحويل بوكس-مولر ). بالنظر إلى معامل الارتباط المطلوب${\textstyle \rho }$يمكن الحصول على المتغيرات الطبيعية المترابطة من خلال التحويلات${\textstyle x_{1}=z_{1}}$و${\textstyle x_{2}=\rho z_{1}+{\sqrt {1-\rho ^{2}}}z_{2}}$.

تستخدم مرشحات كالمان غير الخطية عادةً تحليل تشوليسكي لاختيار مجموعة من النقاط تُسمى نقاط سيجما. يتتبع مرشح كالمان الحالة المتوسطة للنظام كمتجه x بطول N، ^{والتباين} كمصفوفة P من الرتبة N × N. المصفوفة P موجبة شبه محددة دائمًا، ويمكن تحليلها إلى L²T . يمكن جمع أعمدة L²T وطرحها من المتوسط ​​x لتكوين مجموعة من 2²N متجه تُسمى نقاط سيجما . تُجسد نقاط سيجما هذه بشكل كامل متوسط ​​وتباين حالة النظام.

يمكن حساب المعكوس الصريح لمصفوفة هيرميتية عن طريق تحليل تشوليسكي، بطريقة مشابهة لحل الأنظمة الخطية، باستخدام${\textstyle n^{3}}$العمليات (${\textstyle {\tfrac {1}{2}}n^{3}}$الضرب). ^{[ 11 ]} يمكن حتى إجراء عملية القلب بأكملها بكفاءة في مكانها.

يمكن أيضًا عكس المصفوفة غير الهرميتية B باستخدام المتطابقة التالية، حيث ستكون BB * دائمًا هرميتية:

$${\displaystyle \mathbf {B} ^{-1}=\mathbf {B} ^{*}(\mathbf {BB} ^{*})^{-1}.}$$

يمكن أيضًا استخدام تحليل تشوليسكي لتعويض البيانات المفقودة. وتستفيد العديد من خوارزميات تعويض البيانات، بما في ذلك خوارزمية تعظيم التوقع، من تحليل تشوليسكي. ^{[ 18 ]}

خوارزمية تشوليسكي ، المستخدمة لحساب مصفوفة التفكيك L ، هي نسخة معدلة من الحذف الغاوسي .

تبدأ الخوارزمية التكرارية بـ i  := 1 و

A ⁽¹⁾  := A .

في الخطوة i ، تكون المصفوفة A ^{( i )} بالشكل التالي: $${\displaystyle \mathbf {A} ^{(i)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&a_{i,i}&\mathbf {b} _{i}^{*}\\0&\mathbf {b} _{i}&\mathbf {B} ^{(i)}\end{pmatrix}},}$$ حيث I _{i −1} تشير إلى مصفوفة الوحدة ذات البعد i − 1 .

إذا تم تعريف المصفوفة L _{i بواسطة}$${\displaystyle \mathbf {L} _{i}:={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&{\sqrt {a_{i,i}}}&0\\0&{\frac {1}{\sqrt {a_{i,i}}}}\mathbf {b} _{i}&\mathbf {I} _{n-i}\end{pmatrix}},}$$ (لاحظ أن aᵢ _,ᵢ > 0 لأن A ^{( i )} موجبة التحديد)، إذن يمكن كتابة A ^{( i ) على النحو التالي:}$${\displaystyle \mathbf {A} ^{(i)}=\mathbf {L} _{i}\mathbf {A} ^{(i+1)}\mathbf {L} _{i}^{*}}$$ أين $${\displaystyle \mathbf {A} ^{(i+1)}={\begin{pmatrix}\mathbf {I} _{i-1}&0&0\\0&1&0\\0&0&\mathbf {B} ^{(i)}-{\frac {1}{a_{i,i}}}\mathbf {b} _{i}\mathbf {b} _{i}^{*}\end{pmatrix}}.}$$ لاحظ أن b _i b _i * هو منتج خارجي ، لذلك تسمى هذه الخوارزمية نسخة المنتج الخارجي في (Golub & Van Loan).

تُكرر هذه العملية لـ i من 1 إلى n . بعد n خطوة، نحصل على A ^{( n +1)} = I ، ومن ثم، تُحسب المصفوفة المثلثية السفلية L المطلوبة على النحو التالي:

$${\displaystyle \mathbf {L}$$ :=\mathbf {L} _{1}\mathbf {L} _{2}\dots \mathbf {L} _{n}.}

إذا كانت المعادلة $${\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LL} ^{T}&={\begin{pmatrix}L_{11}&0&0\\L_{21}&L_{22}&0\\L_{31}&L_{32}&L_{33}\\\end{pmatrix}}{\begin{pmatrix}L_{11}&L_{21}&L_{31}\\0&L_{22}&L_{32}\\0&0&L_{33}\end{pmatrix}}\\[8pt]&={\begin{pmatrix}L_{11}^{2}&&({\text{symmetric}})\\L_{21}L_{11}&L_{21}^{2}+L_{22}^{2}&\\L_{31}L_{11}&L_{31}L_{21}+L_{32}L_{22}&L_{31}^{2}+L_{32}^{2}+L_{33}^{2}\end{pmatrix}},\end{aligned}}}$$

عند كتابة المعادلة، نحصل على ما يلي:

$${\displaystyle {\begin{aligned}\mathbf {L} ={\begin{pmatrix}{\sqrt {A_{11}}}&0&0\\A_{21}/L_{11}&{\sqrt {A_{22}-L_{21}^{2}}}&0\\A_{31}/L_{11}&\left(A_{32}-L_{31}L_{21}\right)/L_{22}&{\sqrt {A_{33}-L_{31}^{2}-L_{32}^{2}}}\end{pmatrix}}\end{aligned}}}$$

وبالتالي، فإن الصيغ التالية لعناصر المصفوفة L هي:

$${\displaystyle L_{j,j}=(\pm ){\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}^{2}}},}$$$${\displaystyle L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{i,k}L_{j,k}\right)\quad {\text{for }}i>j.}$$

بالنسبة للمصفوفات المركبة والحقيقية، يُسمح بتغييرات طفيفة في إشارات عناصر القطر الرئيسي والعناصر غير القطرية المرتبطة بها. ويكون المقدار تحت الجذر التربيعي موجبًا دائمًا إذا كانت المصفوفة A حقيقية وموجبة التحديد.

بالنسبة للمصفوفة الهرميتية المعقدة، تنطبق الصيغة التالية:

$${\displaystyle L_{j,j}={\sqrt {A_{j,j}-\sum _{k=1}^{j-1}L_{j,k}^{*}L_{j,k}}},}$$$${\displaystyle L_{i,j}={\frac {1}{L_{j,j}}}\left(A_{i,j}-\sum _{k=1}^{j-1}L_{j,k}^{*}L_{i,k}\right)\quad {\text{for }}i>j.}$$

ويمكن إثبات ذلك${\displaystyle L_{j,j}}$تكون دائمًا حقيقية وموجبة إذا كانت A موجبة تمامًا. ^{[ 22 ] : 49}

لذا، أصبح من الممكن الآن حساب المدخل ( i , j ) إذا كانت المدخلات الموجودة على يساره وأعلاه معروفة. وعادةً ما يتم ترتيب الحساب بأحد الترتيبين التاليين:

• تبدأ خوارزمية Cholesky–Banachiewicz من الزاوية العلوية اليسرى للمصفوفة L وتستمر في حساب المصفوفة صفًا تلو الآخر.

for ( i = 0 ; i < dimensionSize ; i ++ ) { for ( j = 0 ; j <= i ; j ++ ) { float sum = 0 ; for ( k = 0 ; k < j ; k ++ ) sum += L [ i ][ k ] * L [ j ][ k ];إذا كان ( i == j ) فإن L [ i ][ j ] = جذر ( A [ i ][ i ] - المجموع )؛ وإلا فإن L [ i ][ j ] = ( 1.0 / L [ j ][ j ] * ( A [ i ][ j ] - المجموع ))؛ } }

يمكن التعبير عن الخوارزمية المذكورة أعلاه بإيجاز من خلال الجمع بين الضرب النقطي وضرب المصفوفات في لغات البرمجة المتجهة مثل فورتران كما يلي:

كرر من i = 1 ، حجم ( A ، 1 ) L ( i , i ) = جذر ( A ( i , i ) - حاصل الضرب النقطي ( L ( i , 1 : i - 1 ), L ( i , 1 : i - 1 ))) L ( i + 1 :, i ) = ( A ( i + 1 :, i ) - مصفوفة الضرب ( مرافق ( L ( i , 1 : i - 1 )), L ( i + 1 :, 1 : i - 1 ))) / L ( i , i ) نهاية التكرار

حيث conjgيشير إلى المرافق المعقد للعناصر.

• تبدأ خوارزمية Cholesky–Crout من الزاوية العلوية اليسرى للمصفوفة L وتستمر في حساب المصفوفة عمودًا تلو الآخر.

  for ( j = 0 ; j < dimensionSize ; j ++ ) { float sum = 0 ; for ( k = 0 ; k < j ; k ++ ) { sum += L [ j ][ k ] * L [ j ][ k ]; } L [ j ][ j ] = sqrt ( A [ j ][ j ] - sum );for ( i = j + 1 ; i < dimensionSize ; i ++ ) { sum = 0 ; for ( k = 0 ; k < j ; k ++ ) { sum += L [ i ][ k ] * L [ j ][ k ]; } L [ i ][ j ] = ( 1.0 / L [ j ][ j ] * ( A [ i ][ j ] - sum )); } }

يمكن التعبير عن الخوارزمية المذكورة أعلاه بإيجاز من خلال الجمع بين الضرب النقطي وضرب المصفوفات في لغات البرمجة المتجهة مثل فورتران كما يلي:

كرر من i = 1 ، حجم ( A ، 1 ) L ( i , i ) = جذر ( A ( i , i ) - حاصل الضرب النقطي ( L ( 1 : i - 1 , i ), L ( 1 : i - 1 , i ))) L ( i , i + 1 ) = ( A ( i , i + 1 ) - مصفوفة ( مرافق ( L ( 1 : i - 1 , i )), L ( 1 : i - 1 , i + 1 ))) / L ( i , i ) نهاية التكرار

حيث conjgيشير إلى المرافق المعقد للعناصر.

يسمح أي من نمطي الوصول بإجراء الحساب بالكامل في مكانه إذا رغب في ذلك.

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

لنفترض الآن أن تحليل تشوليسكي قابل للتطبيق. كما ذُكر سابقًا، ستكون الخوارزمية أسرع بمرتين. علاوة على ذلك، لن تكون هناك حاجة إلى التمحور ، وسيكون الخطأ صغيرًا دائمًا. تحديدًا، إذا كان Ax = b ، و y يمثل الحل المحسوب، فإن y يحل النظام المضطرب ( A + E ) y = b ، حيث $${\displaystyle \|\mathbf {E} \|_{2}\leq c_{n}\varepsilon \|\mathbf {A} \|_{2}.}$$ هنا ||·|| ₂ هو المعيار 2 للمصفوفة ، و c _n هو ثابت صغير يعتمد على n ، و ε يشير إلى التقريب الوحدوي .

من الأمور التي يجب الانتباه إليها في تحليل تشوليسكي استخدام الجذور التربيعية. فإذا كانت المصفوفة المراد تحليلها موجبة التحديد كما هو مطلوب، فإن الأرقام تحت الجذور التربيعية تكون موجبة دائمًا في العمليات الحسابية الدقيقة . ولكن لسوء الحظ، قد تصبح هذه الأرقام سالبة بسبب أخطاء التقريب ، وفي هذه الحالة لا يمكن للخوارزمية الاستمرار. مع ذلك، لا يحدث هذا إلا إذا كانت المصفوفة سيئة التكييف للغاية. إحدى طرق معالجة هذه المشكلة هي إضافة مصفوفة تصحيح قطرية إلى المصفوفة المراد تحليلها في محاولة لتعزيز خاصية موجبة التحديد. ^{[ 23 ]} ورغم أن هذا قد يقلل من دقة التحليل، إلا أنه قد يكون مفيدًا جدًا لأسباب أخرى؛ فعلى سبيل المثال، عند تطبيق طريقة نيوتن في التحسين ، يمكن أن تُحسّن إضافة مصفوفة قطرية الاستقرار عندما يكون الحل بعيدًا عن الحل الأمثل.

هناك شكل بديل، يُلغي الحاجة إلى أخذ الجذور التربيعية عندما تكون المصفوفة A متناظرة، وهو التحليل غير المحدد المتناظر ^{[ 22 ] : 84}$${\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}1&0&0\\L_{21}&1&0\\L_{31}&L_{32}&1\\\end{pmatrix}}{\begin{pmatrix}D_{1}&0&0\\0&D_{2}&0\\0&0&D_{3}\\\end{pmatrix}}{\begin{pmatrix}1&L_{21}&L_{31}\\0&1&L_{32}\\0&0&1\\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}D_{1}&&(\mathrm {symmetric} )\\L_{21}D_{1}&L_{21}^{2}D_{1}+D_{2}&\\L_{31}D_{1}&L_{31}L_{21}D_{1}+L_{32}D_{2}&L_{31}^{2}D_{1}+L_{32}^{2}D_{2}+D_{3}.\end{pmatrix}}.\end{aligned}}}$$

تنطبق العلاقات التكرارية التالية على مدخلات D و L : $${\displaystyle D_{j}=A_{jj}-\sum _{k=1}^{j-1}L_{jk}^{2}D_{k},}$$$${\displaystyle L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}D_{k}\right)\quad {\text{for }}i>j.}$$

تنجح هذه الطريقة طالما بقيت العناصر القطرية المُولَّدة في المصفوفة D غير صفرية. عندئذٍ يكون التحليل فريدًا. المصفوفتان D و L حقيقيتان إذا كانت المصفوفة A حقيقية.

بالنسبة للمصفوفة الهرميتية المعقدة A ، تنطبق الصيغة التالية:

$${\displaystyle D_{j}=A_{jj}-\sum _{k=1}^{j-1}L_{jk}L_{jk}^{*}D_{k},}$$$${\displaystyle L_{ij}={\frac {1}{D_{j}}}\left(A_{ij}-\sum _{k=1}^{j-1}L_{ik}L_{jk}^{*}D_{k}\right)\quad {\text{for }}i>j.}$$

مرة أخرى، يسمح نمط الوصول بإجراء الحساب بالكامل في مكانه إذا رغب في ذلك.

عند استخدام تحليل LDL * على المصفوفات غير المحددة، يُعرف أنه غير مستقر دون استخدام تقنية التمحور الدقيق؛ ^{[ 24 ]} تحديدًا، يمكن أن تنمو عناصر التحليل بشكل عشوائي. يتمثل أحد التحسينات الممكنة في إجراء التحليل على مصفوفات فرعية كتلية، عادةً ما تكون 2 × 2: ^{[ 25 ]}

$${\displaystyle {\begin{aligned}\mathbf {A} =\mathbf {LDL} ^{\mathrm {T} }&={\begin{pmatrix}\mathbf {I} &0&0\\\mathbf {L} _{21}&\mathbf {I} &0\\\mathbf {L} _{31}&\mathbf {L} _{32}&\mathbf {I} \\\end{pmatrix}}{\begin{pmatrix}\mathbf {D} _{1}&0&0\\0&\mathbf {D} _{2}&0\\0&0&\mathbf {D} _{3}\\\end{pmatrix}}{\begin{pmatrix}\mathbf {I} &\mathbf {L} _{21}^{\mathrm {T} }&\mathbf {L} _{31}^{\mathrm {T} }\\0&\mathbf {I} &\mathbf {L} _{32}^{\mathrm {T} }\\0&0&\mathbf {I} \\\end{pmatrix}}\\[8pt]&={\begin{pmatrix}\mathbf {D} _{1}&&(\mathrm {symmetric} )\\\mathbf {L} _{21}\mathbf {D} _{1}&\mathbf {L} _{21}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {D} _{2}&\\\mathbf {L} _{31}\mathbf {D} _{1}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{21}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}&\mathbf {L} _{31}\mathbf {D} _{1}\mathbf {L} _{31}^{\mathrm {T} }+\mathbf {L} _{32}\mathbf {D} _{2}\mathbf {L} _{32}^{\mathrm {T} }+\mathbf {D} _{3}\end{pmatrix}},\end{aligned}}}$$

حيث أن كل عنصر في المصفوفات أعلاه هو مصفوفة فرعية مربعة. ومن هذا، تترتب العلاقات التكرارية المماثلة التالية:

$${\displaystyle \mathbf {D} _{j}=\mathbf {A} _{jj}-\sum _{k=1}^{j-1}\mathbf {L} _{jk}\mathbf {D} _{k}\mathbf {L} _{jk}^{\mathrm {T} },}$$$${\displaystyle \mathbf {L} _{ij}=\left(\mathbf {A} _{ij}-\sum _{k=1}^{j-1}\mathbf {L} _{ik}\mathbf {D} _{k}\mathbf {L} _{jk}^{\mathrm {T} }\right)\mathbf {D} _{j}^{-1}.}$$

يتضمن ذلك عمليات ضرب المصفوفات والانعكاس الصريح، مما يحد من حجم الكتلة العملي.

من المهام التي تظهر غالبًا في الممارسة العملية الحاجة إلى تحديث تحليل تشوليسكي. بتفصيل أكثر، يكون المرء قد قام بالفعل بحساب تحليل تشوليسكي${\textstyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}}$من مصفوفة ما${\textstyle \mathbf {A} }$ثم يقوم المرء بتغيير المصفوفة${\textstyle \mathbf {A} }$بطريقة ما في مصفوفة أخرى، على سبيل المثال${\textstyle {\tilde {\mathbf {A} }}}$ويريد المرء حساب تحليل تشوليسكي للمصفوفة المحدثة:${\textstyle {\tilde {\mathbf {A} }}={\tilde {\mathbf {L} }}{\tilde {\mathbf {L} }}^{*}}$والسؤال الآن هو ما إذا كان بالإمكان استخدام تحليل تشوليسكي لـ${\textstyle \mathbf {A} }$تم حساب ذلك مسبقًا لحساب تحليل تشوليسكي لـ${\textstyle {\tilde {\mathbf {A} }}}$.

دالة L = updateChol ( L,x,c ) % بمعلومية تحليل تشوليسكي L*L' للمصفوفة، احسب العامل المحدث L بحيث يكون لدينا تحليل تشوليسكي L*L'+c*x*x'؛ n = length ( x ); for k = 1 : n - 1 l = L (:, k ); % القيمة القديمة للعمود k lk = l ( k ); xk = x ( k ); dk = sqrt ( lk ^ 2 + c * xk ^ 2 ); % القيمة القطرية الجديدة L (:, k )=( lk / dk ) * l + ( c * xk / dk ) * x ; % قيمة العمود الجديدة x = x - l * ( xk / lk ); c = c * ( lk / dk ) ^ 2 ; end L ( n , n )= sqrt ( L ( n , n ) ^ 2 + c * x ( n ) ^ 2 ); end

تُظهر الخوارزميات المذكورة أعلاه أن كل مصفوفة موجبة محددة${\textstyle \mathbf {A} }$يحتوي على تحليل تشوليسكي. يمكن تعميم هذه النتيجة على الحالة شبه الموجبة المحددة باستخدام حجة حدية. هذه الحجة ليست بنائية بالكامل، أي أنها لا تقدم خوارزميات عددية صريحة لحساب عوامل تشوليسكي.

لو${\textstyle \mathbf {A} }$هو${\textstyle n\times n}$إذا كانت المصفوفة شبه موجبة ، فإن المتتالية${\textstyle \left(\mathbf {A} _{k}\right)_{k}:=\left(\mathbf {A} +{\frac {1}{k}}\mathbf {I} _{n}\right)_{k}}$تتكون من مصفوفات موجبة محددة . (هذه نتيجة مباشرة، على سبيل المثال، لنظرية التحويل الطيفي لحساب الدوال متعددة الحدود). أيضًا، $${\displaystyle \mathbf {A} _{k}\rightarrow \mathbf {A} \quad {\text{for}}\quad k\rightarrow \infty }$$ في معيار المؤثر . من الحالة الموجبة المحددة، كل${\textstyle \mathbf {A} _{k}}$يحتوي على تحلل تشوليسكي${\textstyle \mathbf {A} _{k}=\mathbf {L} _{k}\mathbf {L} _{k}^{*}}$بحسب خاصية معيار المؤثر،

$${\displaystyle \|\mathbf {L} _{k}\|^{2}\leq \|\mathbf {L} _{k}\mathbf {L} _{k}^{*}\|=\|\mathbf {A} _{k}\|\,.}$$

ال${\textstyle \leq }$لذلك لأن${\textstyle M_{n}(\mathbb {C} )}$الجبر المزود بمعيار المؤثر هو جبر C*.${\textstyle \left(\mathbf {L} _{k}\right)_{k}}$هي مجموعة محدودة في فضاء باناخ للمؤثرات، وبالتالي فهي متراصة نسبيًا (لأن فضاء المتجهات الأساسي محدود الأبعاد). ونتيجة لذلك، لها متتالية جزئية متقاربة، يُرمز لها أيضًا بـ${\textstyle \left(\mathbf {L} _{k}\right)_{k}}$، مع حد${\textstyle \mathbf {L} }$يمكن التحقق بسهولة من ذلك${\textstyle \mathbf {L} }$يمتلك الخصائص المطلوبة، أي${\textstyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}}$، و${\textstyle \mathbf {L} }$هي مصفوفة مثلثية سفلية ذات عناصر قطرية غير سالبة: لكل${\textstyle x}$و${\textstyle y}$،

$${\displaystyle \langle \mathbf {A} x,y\rangle =\left\langle \lim \mathbf {A} _{k}x,y\right\rangle =\langle \lim \mathbf {L} _{k}\mathbf {L} _{k}^{*}x,y\rangle =\langle \mathbf {L} \mathbf {L} ^{*}x,y\rangle \,.}$$

لذلك،${\textstyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{*}}$بما أن فضاء المتجهات الأساسي محدود الأبعاد، فإن جميع التوبولوجيات على فضاء المؤثرات متكافئة.${\textstyle \left(\mathbf {L} _{k}\right)_{k}}$يميل إلى${\textstyle \mathbf {L} }$في المعيار يعني${\textstyle \left(\mathbf {L} _{k}\right)_{k}}$يميل إلى${\textstyle \mathbf {L} }$من المدخل إلى المدخل. وهذا بدوره يعني أنه، بما أن كل${\textstyle \mathbf {L} _{k}}$هي مثلثية سفلية ذات عناصر قطرية غير سالبة،${\textstyle \mathbf {L} }$هو كذلك.

يترك${\textstyle \mathbf {A} }$لتكن مصفوفة هيرميتية شبه موجبة . عندئذٍ يمكن كتابتها كحاصل ضرب مصفوفة الجذر التربيعي الخاصة بها .${\textstyle \mathbf {A} =\mathbf {B} \mathbf {B} ^{*}}$يمكن الآن تطبيق تحليل QR على${\textstyle \mathbf {B} ^{*}}$، مما أدى إلى${\textstyle \mathbf {B} ^{*}=\mathbf {Q} \mathbf {R} }$ ، أين${\textstyle \mathbf {Q} }$هو نظام وحدوي و${\textstyle \mathbf {R} }$هي مثلثية علوية. بإدخال التفكيك في المعادلة الأصلية ينتج${\textstyle A=\mathbf {B} \mathbf {B} ^{*}=(\mathbf {QR} )^{*}\mathbf {QR} =\mathbf {R} ^{*}\mathbf {Q} ^{*}\mathbf {QR} =\mathbf {R} ^{*}\mathbf {R} }$. جلسة${\textstyle \mathbf {L} =\mathbf {R} ^{*}}$وهذا يُكمل البرهان.