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

في التحليل العددي ، يُعدّ تحليل تشوليسكي غير الكامل لمصفوفة متناظرة موجبة التحديد تقريبًا متفرقًا لتحليل تشوليسكي . ويُستخدم تحليل تشوليسكي غير الكامل غالبًا كمعالجة مسبقة لخوارزميات مثل طريقة التدرج المترافق .

يُعطى تحليل تشوليسكي لمصفوفة موجبة محددة A من الرتبة N بالعلاقة A = LL *، حيث L مصفوفة مثلثية سفلية . أما تحليل تشوليسكي غير الكامل فيُعطى بمصفوفة مثلثية سفلية K أقل كثافة من L ، ولكنها تُشابهها في بعض النواحي . ويُسمى المُهيئ المُقابل KK *.

توجد طرق عديدة لإنشاء تحليلات تشوليسكي غير الكاملة. تستعرض هذه المقالة اثنتين منها.

لنأخذ المصفوفة التالية كمثال:

${\displaystyle \mathbf {A} ={\begin{bmatrix}5&-2&0&-2&-2\\-2&5&-2&0&0\\0&-2&5&-2&0\\-2&0&-2&5&-2\\-2&0&0&-2&5\\\end{bmatrix}}}$

إذا طبقنا تحليل تشوليسكي المنتظم الكامل ، فإنه ينتج عنه:

${\displaystyle \mathbf {L} ={\begin{bmatrix}2.24&0&0&0&0\\-0.89&2.05&0&0&0\\0&-0.98&2.02&0&0\\-0.89&-0.39&-1.18&1.63&0\\-0.89&-0.39&-0.19&-1.95&0.45\\\end{bmatrix}}}$

وبحسب التعريف:

${\displaystyle \mathbf {A} =\mathbf {L} \mathbf {L'} }$

مع ذلك، بتطبيق تحليل تشوليسكي، نلاحظ أن بعض العناصر الصفرية في المصفوفة الأصلية تصبح عناصر غير صفرية في المصفوفة المُحللة، مثل العناصر (4،2) و(5،2) و(5،3) في هذا المثال. تُعرف هذه العناصر باسم "العناصر المُضافة".

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

لذا، ونظرًا لأهمية تحليل تشوليسكي في حسابات المصفوفات، فمن الضروري للغاية إعادة استخدام الطريقة التقليدية للتخلص من توليد القيم المفقودة. وتقوم تحليلات تشوليسكي غير الكاملة بذلك تحديدًا، إذ تُنتج مصفوفة ما.${\displaystyle \mathbf {K} }$هذا أقل كثافة من${\displaystyle \mathbf {L} }$ويعطي تقريبًا${\displaystyle \mathbf {A} \approx \mathbf {K} \mathbf {K'} }$.

تُشغّل خوارزمية تشوليسكي غير المكتملة من المستوى صفر أو IC(0) خوارزمية تشوليسكي الدقيقة، ولكنها تتخطى تحديثات K لضمان أن يكون لها نفس درجة التباعد مثل A. لوصف الخوارزمية رياضيًا، قم بتهيئة K إلى مصفوفة صفرية من الرتبة N × N.${\displaystyle i}$من${\displaystyle 1}$ل${\displaystyle N}$، نحن نحدد

${\displaystyle K_{ii}=\left({a_{ii}-\sum \limits _{k=1}^{i-1}{K_{ik}^{2}}}\right)^{1 \over 2}}$،

ولـ${\displaystyle j}$من${\displaystyle i+1}$ل${\displaystyle N}$، نقوم بتطبيق التحديث التالي فقط إذا${\displaystyle a_{ji}}$غير صفري

${\displaystyle K_{ji}={1 \over {K_{ii}}}\left({a_{ji}-\sum \limits _{k=1}^{i-1}{K_{ik}K_{jk}}}\right)}$.

ينتج عن ذلك عامل K يكون بنفس قلة عناصر المثلث السفلي للمصفوفة A، وبالتالي فإن تخزين كل من A و K يتطلب ضعف مساحة التخزين المطلوبة لتخزين A وحدها على الأكثر. قد تتوقف خوارزمية IC(0) مع وجود خطأ في بعض المصفوفات الموجبة المحددة. وهي مضمونة النجاح إذا كانت A مهيمنة قطريًا ، على الرغم من وجود العديد من المصفوفات الموجبة المحددة التي تنجح فيها IC(0) حتى بدون هيمنة قطرية.

دالة a = ichol ( a ) n = size ( a , 1 );لـ k = 1 : n a ( k , k ) = sqrt ( a ( k , k )); لـ i = ( k + 1 ): n إذا كان ( a ( i , k ) != 0 ) a ( i , k ) = a ( i , k ) / a ( k , k ); endif endfor لـ j = ( k + 1 ): n لـ i = j : n إذا كان ( a ( i , j ) != 0 ) a ( i , j ) = a ( i , j ) - a ( i , k ) * a ( j , k ); endif endfor endfor endforfor i = 1 : n for j = i + 1 : n a ( i , j ) = 0 ; endfor endfor endfunction

القيمة 5 -2 -2 -2 5 -2 5 -2 5 -2 5 الصف 1 2 4 5 2 3 3 4 4 5 5 العمود 1 1 1 1 2 2 3 3 4 4 5 

القيمة 2.24 -0.89 -0.89 -0.89 | 5 -2 5 -2 5 -2 5 الصف 1 2 4 5 | 2 3 3 4 4 5 5 العمود 1 1 1 1 | 2 2 3 3 4 4 5 

القيمة 2.24 -0.89 -0.89 -0.89 | 4.2 -2 5 -2 4.2 -2.8 4.2 الصف 1 2 4 5 | 2 3 3 4 4 5 5 العمود 1 1 1 1 | 2 2 3 3 4 4 5 ↑ ↑ ↑ ↑ 

القيمة 2.24 -0.89 -0.89 -0.89 | 2.05 -0.98 | 5 -2 4.2 -2.8 4.2 الصف 1 2 4 5 | 2 3 | 3 4 4 5 5 العمود 1 1 1 1 | 2 2 | 3 3 4 4 5 

القيمة 2.24 -0.89 -0.89 -0.89 | 2.05 -0.98 | 4.05 -2 4.2 -2.8 4.2 الصف 1 2 4 5 | 2 3 | 3 4 4 5 5 العمود 1 1 1 1 | 2 2 | 3 3 4 4 5 ↑ 

القيمة 2.24 -0.89 -0.89 -0.89 2.05 -0.98 | 2.01 -0.99 | 4.2 -2.8 4.2 الصف 1 2 4 5 2 3 | 3 4 | 4 5 5 العمود 1 1 1 1 2 2 | 3 3 | 4 4 5 

القيمة 2.24 -0.89 -0.89 -0.89 2.05 -0.98 | 2.01 -0.99 | 3.21 -2.8 4.2 الصف 1 2 4 5 2 3 | 3 4 | 4 5 5 العمود 1 1 1 1 2 2 | 3 3 | 4 4 5 ↑ 

القيمة 2.24 -0.89 -0.89 -0.89 2.05 -0.98 2.01 -0.99 | 1.79 -1.56 | 4.2 الصف 1 2 4 5 2 3 3 4 | 4 5 | 5 العمود 1 1 1 1 2 2 3 3 | 4 4 | 5 

القيمة 2.24 -0.89 -0.89 -0.89 2.05 -0.98 2.01 -0.99 | 1.79 -1.56 | 1.76 الصف 1 2 4 5 2 3 3 4 | 4 5 | 5 العمود 1 1 1 1 2 2 3 3 | 4 4 | 5 ↑ 

القيمة 2.24 -0.89 -0.89 -0.89 2.05 -0.98 2.01 -0.99 1.79 -1.56 | 1.33 الصف 1 2 4 5 2 3 3 4 4 5 | 5 العمود 1 1 1 1 2 2 3 3 4 4 | 5 

دالة A = Sp_ichol ( A ) n = size ( A , 1 ); ncols = A ( n ). col ; c_end = 0 ; for col = 1 : ncols is_next_col = 0 ; c_start = c_end + 1 ; for i = c_start : n if A ( i ). col == col % في العمود الحالي (col): if A ( i ). col == A ( i ) . row A ( i ). val = sqrt ( A ( i ). val ); % خذ الجذر التربيعي لعنصر القطر الرئيسي للعمود الحالي div = A ( i ). val ; else A ( i ). val = A ( i ). val / div ; % اقسم عناصر العمود الحالي الأخرى على الجذر التربيعي لعنصر القطر الرئيسي end end if A ( i ). col > col % في الأعمدة التالية (col+1 ... ncols): إذا كان is_next_col == 0 c_end = i - 1 ; is_next_col = 1 ; end v1 = 0 ; v2 = 0 ; for j = c_start : c_end if A ( j ). col == col if A ( j ). row == A ( i ). row % ابحث عن عناصر العمود الحالي (col) A(j) التي يكون فهرس صفها هو نفسه فهرس صف العنصر الحالي A(i) v1 = A ( j ). val ;إذا كان A ( j ) .row == A ( i ) .col % ابحث عن عناصر العمود الحالي (col) A(j) التي يكون فهرس صفها هو نفسه فهرس عمود العنصر الحالي A(i) v2 = A ( j ) .val ; نهاية إذا كان v1 ~ = 0 && v2 ~= 0 % إذا كانت هذه العناصر موجودة في العمود الحالي (col)، فأعد حساب العنصر الحالي A(i): A ( i ) .val = A ( i ) .val - v1 * v2 ; break ; نهاية نهاية نهاية نهاية نهاية نهاية نهاية

تُنشئ خوارزمية تشوليسكي غير المكتملة القائمة على القطر (DIC) عاملاً K يمكن تخزينه باستخدام المساحة المتاحة فقط لعددين إضافيين A و N. ^{[ 1 ]} ومثل IC(0)، تنجح خوارزمية DIC عندما يكون العنصر مهيمناً قطرياً. ويمكن لبعض متغيرات خوارزمية DIC أن تعمل حتى الاكتمال لفئات أعم قليلاً من المصفوفات.

باستخدام DIC، نحدد${\displaystyle \mathbf {K} =(\mathbf {S} +\mathbf {D} )\mathbf {D} ^{-1/2}}$، أين${\displaystyle \mathbf {S} }$هو المثلث السفلي الصارم لـ${\displaystyle \mathbf {A} }$و${\displaystyle \mathbf {D} }$هي المصفوفة القطرية الناتجة عن الإجراء التالي:

نهيئ متجهًا d على قطر المصفوفة A. ثم نكرر العملية على${\displaystyle i}$من 2 إلى N. عند تكرار معين i، نكرر على j من i+1 إلى N، ونخفض التاريخ${\displaystyle d_{j}=d_{j}-a_{ji}^{2}/d_{i}}$لاحظ أنه يمكن تخطي هذا التحديث عند${\displaystyle a_{ji}}$يساوي صفرًا.

من scipy.sparse استورد csc_matrix، واستورد numpy كـ npdef dic_diagonal ( A : csc_matrix ) -> np . ndarray : # يوضح الشكل 3.3 من www.netlib.org/templates/templates.pdf كيفية # حساب قطر "inv(D)" للمُهيئ LU غير الكامل القائم على القطر. # تُكيّف هذه الدالة تلك الطريقة للمصفوفات المتناظرة # ذات القطر المهيمن، وتُنشئ قطر D # (بدلاً من قطر inv(D)). d = A . diagonal () inds = A . indices ptrs = A . indptr vals = A . البيانات لـ i في نطاق ( حجم d ) : إذا كان d [ i ] < 0 : ارفع ValueError ( 'فشل تحليل DIC!' ) j = inds [ ptrs [ i ]: ptrs [ i + 1 ]] v = vals [ ptrs [ i ]: ptrs [ i + 1 ]] selector = j > i j = j [ selector ] v = v [ selector ] d [ j ] -= v ** 2 / d [ i ] إرجاع d

• تحليل تشوليسكي غير الكامل في ويكي CFD Online
• جولوب، جين هـ .؛ فان لون، تشارلز ف. (1996)، حسابات المصفوفات (  الطبعة الثالثة)، جونز هوبكنز، ISBN 978-0-8018-5414-9انظر القسم 10.3.2.