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

ما هو تحليل تشولسكي؟

تحليل تشولسكي هو تحليل خاص متاح للمصفوفات المتماثلة الموجبة التعريف (SPD) — أهم فئة من المصفوفات في الجبر الخطي العددي. لأي مصفوفة SPD يُسمى A، يضمن تشولسكي وجود مصفوفة مثلثية سفلية L فريدة ذات عناصر قطرية موجبة تحقق A = LLᵀ. هذا التحليل هو جذر "المصفوفة التربيعي": تمامًا كما يمتلك أي عدد حقيقي موجب x جذره التربيعي √x، يمتلك أي مصفوفة SPD "جذرًا مثلثيًا" L.

تكمن أناقة تحليل تشولسكي في كفاءته. مقارنةً بتحليل LU (الذي يُحلل A = LU للمصفوفات المربعة العامة)، يتطلب تشولسكي نصف عمليات الحساب فحسب — ما يقارب n³/6 عملية ضرب مقابل n³/3 لتحليل LU. كما يحتاج إلى نصف مساحة التخزين لأن تماثل A يُستغل بالكامل. وهو مستقر عدديًا دون ترتيب المحاور: لا يواجه الخوارزمية قيمًا قطرية صفرية أو قريبة من الصفر طالما كانت A موجبة التعريف فعلًا.

يعد تحليل تشولسكي الطريقة المثلى كلما احتجت إلى حل Ax = b بشكل متكرر مع نفس المصفوفة SPD، أو حساب محدد A، أو أخذ عينات من توزيع غاوسي متعدد الأبعاد، أو اختبار ما إذا كانت المصفوفة موجبة التعريف. ويظهر في فلاتر كالمان وانحدار العمليات الغاوسية وطرق العناصر المنتهية وخوارزميات التحسين.

المصفوفات المتماثلة الموجبة التعريف

المصفوفة متماثلة موجبة التعريف إذا كانت مربعة، ومساوية لمنقولها (Aᵀ = A)، وتحقق xᵀAx > 0 لكل متجه غير صفري x. حدسيًا، المصفوفة الموجبة التعريف تدفع دائمًا المتجهات بعيدًا عن الأصل — فليس فيها اتجاه واحد تقلبه أو تسحقه إلى الصفر أو تعكسه عبر الأصل.

المصدر الأكثر طبيعية للمصفوفات SPD في التطبيق العملي هو مصفوفة المعادلات الطبيعية AᵀA (أو AAᵀ)، التي تنشأ في مسائل المربعات الصغرى وتحليل المركبات الرئيسية والانحدار الخطي. إذا كانت A ذات رتبة عمود كاملة، فإن AᵀA تكون دائمًا SPD. وتشمل مصفوفات SPD الشائعة الأخرى مصفوفات التباين في الإحصاء — وهي تقيس التباين، فالمقدار xᵀΣx هو تباين التركيبة الخطية xᵀy ولا يمكن أن يكون سالبًا — ومصفوفات الصلابة في تحليل العناصر المنتهية، ومصفوفة غرام لمجموعة من المتجهات.

وهناك شروط مكافئة تخبرك أن مصفوفة متماثلة موجبة التعريف: أن تكون كل قيمها الذاتية موجبة تمامًا، وأن يكون محدد كل مصفوفة رئيسية طرفية موجبًا (معيار سيلفستر)، والأنفع عمليًا — أن تكتمل خوارزمية تشولسكي دون أن تصادف عنصرًا قطريًا غير موجب.

الإيجابية التعريفية

A \text{ is SPD} \iff x^T A x > 0 \; \forall x \neq 0 \iff \lambda_i(A) > 0 \; \forall i \iff A = LL^T \text{ exists}

المصفوفة المتماثلة A موجبة التعريف إذا وفقط إذا كان xᵀAx > 0 لكل x ≠ 0. يعادل ذلك: جميع القيم الذاتية λᵢ(A) > 0؛ وجميع المحددات الرئيسية الطرفية det(Aₖ) > 0 (معيار سيلفستر)؛ ووجود A = LLᵀ مع قطر موجب L (وجود تشولسكي).

تحليل تشولسكي: A = LLᵀ

يكتب تحليل تشولسكي مصفوفة SPD ذات n × n كحاصل ضرب مصفوفة مثلثية سفلية L ومنقولها Lᵀ (وهي مثلثية علوية). جميع العناصر القطرية لـ L موجبة بشكل صارم. التحليل فريد: توجد L واحدة فحسب لأي مصفوفة SPD.

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

A = LL^T, \quad L = \begin{pmatrix} \ell_{11} & & \\ \ell_{21} & \ell_{22} & \\ \ell_{31} & \ell_{32} & \ell_{33} \end{pmatrix}, \quad \ell_{ii} > 0

A = LLᵀ حيث L مثلثية سفلية ذات عناصر قطرية موجبة. في مثال 3 × 3: L لها عناصر ℓᵢⱼ (i ≥ j) محسوبة عمودًا بعمود. كل عنصر قطري ℓⱼⱼ = √(aⱼⱼ − Σₖ<ⱼ ℓⱼₖ²)، وكل عنصر تحت القطر ℓᵢⱼ = (aᵢⱼ − Σₖ<ⱼ ℓᵢₖℓⱼₖ) / ℓⱼⱼ.

وهناك صيغة بديلة تُسمى تحليل LDLᵀ، تكتب A = LDLᵀ حيث L مثلثية سفلية واحدية (كل عناصرها القطرية تساوي 1) وD قطرية بعناصر موجبة. صيغة LDLᵀ تتخلص من الجذور التربيعية تمامًا، وهذا مفيد حين تكون الجذور التربيعية في الفاصلة العائمة مكلفة، أو حين تريد العمل على مصفوفات متماثلة غير محددة الإشارة — فتظهر في D عناصر سالبة. وترتبط الصيغتان معًا: اكتب D = diag(d₁, …, dₙ) وادمج √dᵢ في كل عمود من L فتحصل على تشولسكي القياسي A = LLᵀ.

خوارزمية تشولسكي

تتقدم خوارزمية تشولسكي عمودًا بعمود، محسوبةً كل عمود من L بدوره. للعمود j (j = 1, …, n):

العنصر القطري: ℓⱼⱼ = √(aⱼⱼ − Σₖ₌₁ʲ⁻¹ ℓⱼₖ²). وهو الجذر التربيعي للكتلة القطرية "المتبقية" بعد طرح مساهمات الأعمدة المحسوبة سابقًا. إذا كانت هذه القيمة ≤ 0، فإن A ليست موجبة التعريف.
العناصر تحت القطر: لـ i = j+1, …, n، احسب ℓᵢⱼ = (aᵢⱼ − Σₖ₌₁ʲ⁻¹ ℓᵢₖℓⱼₖ) / ℓⱼⱼ. هذه هي العناصر المتبقية في العمود j، مقسومةً على القطر.

خوارزمية تشولسكي (العمود j)

\ell_{jj} = \sqrt{a_{jj} - \sum_{k=1}^{j-1} \ell_{jk}^2}, \qquad \ell_{ij} = \frac{a_{ij} - \sum_{k=1}^{j-1} \ell_{ik}\ell_{jk}}{\ell_{jj}} \quad (i > j)

خوارزمية تشولسكي: العنصر القطري ℓⱼⱼ هو الجذر التربيعي للقطر المخفَّض؛ والعناصر تحت القطر تُحسب بقسمة بسيطة. إذا كانت الحجة داخل الجذر التربيعي غير موجبة، تُبلِّغ الخوارزمية بأن A ليست موجبة التعريف. التكلفة الإجمالية: n³/6 ضربة وn عملية جذر تربيعي — تقريبًا نصف تكلفة تحليل LU.

تكلفة الخوارزمية O(n³/6) عملية ضرب وn عملية جذر تربيعي. وللمقارنة، يكلف تحليل LU نحو O(n³/3) عملية ضرب. أي أن تشولسكي أسرع بمقدار الضعف تقريبًا، ولا يحتاج في الذاكرة إلا إلى المثلث السفلي من A. ولا حاجة إلى ترتيب المحاور هنا: العناصر القطرية ℓⱼⱼ موجبة بالضمان طالما كانت A موجبة التعريف، فلا يظهر قاسم صفري أبدًا.

مثال محلول: تشولسكي 3 × 3

خُذ هذه المصفوفة الموجبة التعريف:

مثال 3 × 3

A = \begin{pmatrix} 4 & 6 & -4 \\ 6 & 13 & -11 \\ -4 & -11 & 21 \end{pmatrix} = LL^T, \quad L = \begin{pmatrix} 2 & 0 & 0 \\ 3 & 2 & 0 \\ -2 & -5/2 & \sqrt{17}/2 \end{pmatrix}

خطوة بخطوة: ℓ₁₁ = √4 = 2؛ ℓ₂₁ = 6/2 = 3، ℓ₂₂ = √(13 − 9) = 2؛ ℓ₃₁ = −4/2 = −2، ℓ₃₂ = (−11 − 3·(−2))/2 = −5/2، ℓ₃₃ = √(21 − 4 − 25/4) = √17/2.

حل الأنظمة الخطية باستخدام تشولسكي

بعد حساب A = LLᵀ، يصبح حل Ax = b عملية من خطوتين للأنظمة المثلثية — نفس البنية كتحليل LU لكن مع مثلث واحد فقط للتخزين:

التعويض الأمامي: حل Ly = b من أجل y. بما أن L مثلثية سفلية، تكلفته O(n²) وتتقدم من المركبة الأولى إلى الأخيرة.
التعويض الخلفي: حل Lᵀx = y من أجل x. بما أن Lᵀ مثلثية علوية، تكلفته O(n²) ويتقدم من المركبة الأخيرة للأولى.

وإذا احتجت إلى حل Ax = bᵢ لأطراف يمنى كثيرة b₁, b₂, …, bₘ بالمصفوفة A نفسها، فحلّل A = LLᵀ مرة واحدة بتكلفة O(n³/6)، ثم نفّذ m زوجًا من الحلول المثلثية بتكلفة O(n²) لكل زوج. لهذا وزن كبير في خوارزميات التحسين التي تحل النظام نفسه بمصفوفة هسيان واحدة مرة بعد مرة، وفي الاستدلال البايزي حين تسحب عينات لاحقة متعددة بمصفوفة التباين نفسها.

الحل على مرحلتين

Ax = b \Rightarrow LL^T x = b \Rightarrow \underbrace{Ly = b}_{\text{forward}} \Rightarrow \underbrace{L^T x = y}_{\text{back}}, \quad \det(A) = \left(\prod_{i=1}^n \ell_{ii}\right)^2

حل Ax = b عبر A = LLᵀ: أولًا التعويض الأمامي Ly = b يعطي y، ثم التعويض الخلفي Lᵀx = y يعطي x. كل حل مثلثي يكلف O(n²). محدد A مباشرةً: det(A) = (ℓ₁₁ · ℓ₂₂ · ⋯ · ℓₙₙ)².

المحدد عبر تشولسكي

محدد A سهل الحساب بعد معرفة L: det(A) = det(L) · det(Lᵀ) = det(L)² = (ℓ₁₁ · ℓ₂₂ · ⋯ · ℓₙₙ)². في كثير من تطبيقات الإحصاء (مثل حساب لوغاريتم الاحتمالية لتوزيع غاوسي متعدد الأبعاد)، تحتاج إلى log det(A) = 2 Σᵢ log ℓᵢᵢ، وهي قيمة مستقرة عدديًا عند حسابها من عامل تشولسكي.

اختبار الإيجابية التعريفية

توفر خوارزمية تشولسكي الاختبار الأكثر عملية للإيجابية التعريفية: حاول إجراء التحليل. إذا اكتمل دون أن يصادف حجة قطرية غير موجبة — أي إذا بقي aⱼⱼ − Σₖ<ⱼ ℓⱼₖ² > 0 في كل خطوة — فإن A موجبة التعريف. وإذا صارت الحجة صفرًا أو سالبة في أي خطوة، فليست A موجبة التعريف. هذا أوثق من التحقق من القيم الذاتية، الذي يستلزم التحليل الطيفي الكامل، وأوثق من معيار سيلفستر الذي يستلزم حساب n محددًا.

وفي التطبيق العملي، قد يجعل التشويش العددي مصفوفة شبه موجبة التعريف تفشل في اختبار تشولسكي رغم أن قيمها الذاتية النظرية كلها موجبة. والعلاج الشائع أن تضيف تنظيمًا صغيرًا ε إلى القطر: احسب تشولسكي للمصفوفة A + εI. فإن نجح، فإن A موجبة التعريف عدديًا. وأصغر قيمة ε ينجح عندها تشولسكي تعطيك تقديرًا لمدى قرب A من حدود الإيجابية التعريفية.

تطبيقات تحليل تشولسكي

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

في المربعات الصغرى الخطية، تتضمن المعادلات الطبيعية AᵀAx = Aᵀb المصفوفة SPD (وهي AᵀA عندما تكون A ذات رتبة عمود كاملة). تشولسكي هي الطريقة المباشرة القياسية لحل هذه المعادلات. غير أن المحللين العدديين يفضلون في أحيان كثيرة تحليل QR المطبق مباشرةً على A، إذ إن تكوين AᵀA يُربّع رقم التكييف: κ(AᵀA) = κ(A)²، فتتضخم أخطاء التقريب حين تكون A سيئة التكييف. أما في المسائل جيدة التكييف فتشولسكي على المعادلات الطبيعية سريع ودقيق.

توليد متغيرات عشوائية مترابطة

لتوليد عينات من التوزيع الغاوسي متعدد الأبعاد 𝒩(μ, Σ)، تحسب عامل تشولسكي L لمصفوفة التباين Σ = LLᵀ، وتولد متجه z من عينات غاوسية مستقلة قياسية، ثم تحسب x = μ + Lz. النتيجة لها متوسط μ وتباين E[(Lz)(Lz)ᵀ] = L·E[zzᵀ]·Lᵀ = LILᵀ = Σ. هذه هي الخوارزمية القياسية في المحاكاة بمونتي كارلو، وفي أخذ العينات البايزي، وفي النماذج التوليدية للبيانات المترابطة.

أخذ العينات من 𝒩(μ, Σ)

\Sigma = LL^T, \quad z \sim \mathcal{N}(0, I), \quad x = \mu + Lz \implies x \sim \mathcal{N}(\mu, \Sigma)

توليد x ~ 𝒩(μ, Σ): احسب Σ = LLᵀ، ارسم z ~ 𝒩(0, I)، ثم x = μ + Lz. عامل تشولسكي L هو "الجذر التربيعي" لمصفوفة التباين الذي يُدخل الترابطات المطلوبة. يُستخدم في انحدار العمليات الغاوسية وفلتر كالمان والشبكات العصبية البايزية.

فلتر كالمان

يحتفظ فلتر كالمان بتقدير للحالة x̂ ومصفوفة تباين للخطأ P. وفي كل خطوة يجب تحديث P وعكسها لحساب كسب كالمان K. وبما أن P مصفوفة تباين، فهي دائمًا SPD، وتشولسكي هو الأداة الطبيعية لهذا الحساب. وتعمل متغيرات "فلتر الجذر التربيعي" على عامل تشولسكي لـ P مباشرةً دون أن تحسب P نفسها صراحةً. هذه الفلاتر أكثر استقرارًا عدديًا، لأنها تضمن بقاء P موجبة التعريف ومتماثلة رغم أخطاء الفاصلة العائمة التي كانت ستفسد أحد الشرطين أو كليهما.

انحدار العمليات الغاوسية

يتطلب انحدار العملية الغاوسية حل نظام خطي مع مصفوفة النواة K (التي هي SPD بالتعريف) وحساب log det(K). كلتا العمليتين تتمان عبر تحليل تشولسكي K = LLᵀ: النظام K⁻¹y يُحل كحلين مثلثيين، وlog det(K) = 2 Σᵢ log Lᵢᵢ. التكلفة التكعيبية O(n³) لتشولسكي هي الاختناق الحسابي الرئيسي للاستدلال الدقيق بالعمليات الغاوسية، ومن هنا جاءت التقريبات المتفرقة ومنخفضة الرتبة والتكرارية للبيانات الكبيرة.

طرق العناصر المنتهية

تنتج محاكاة التحليل الإنشائي وانتقال الحرارة والمجالات الكهرومغناطيسية بطرق العناصر المنتهية (FEM) أنظمة SPD كبيرة ومتفرقة على الصورة Ku = f، حيث K مصفوفة الصلابة. وتشولسكي — أو نسخته المتفرقة — هو الحل المباشر المفضّل هنا. وعندما تكون K متفرقة، يعتمد نمط الامتلاء في تشولسكي، أي العناصر غير الصفرية الجديدة التي يستحدثها التحليل، على ترتيب المجاهيل؛ ولهذا تُستخدم خوارزميات إعادة الترتيب مثل الدرجة الدنيا والتقسيم المتداخل لتقليل الامتلاء وتوفير الذاكرة ووقت الحساب معًا.

الخصائص العددية والاستقرار

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

يحقق الخطأ الخلفي لخوارزمية تشولسكي العلاقة (A + ΔA) = LLᵀ حيث ‖ΔA‖ ≤ ε_mach · ‖A‖ بإهمال ثوابت صغيرة. بعبارة أخرى: العامل L المحسوب هو عامل تشولسكي الدقيق لمصفوفة A + ΔA قريبة نسبيًا من A. وبضم ذلك إلى رقم التكييف κ(A) = σ_max/σ_min — أو λ_max/λ_min للمصفوفات SPD — يصبح الخطأ الأمامي في الحل x للنظام Ax = b محكومًا بالتقريب ‖Δx‖/‖x‖ ≈ κ(A) · ε_mach.

رقم تكييف مصفوفة SPD

\kappa_2(A) = \frac{\lambda_{\max}(A)}{\lambda_{\min}(A)} = \frac{\sigma_1}{\sigma_n}, \qquad \frac{\|\Delta x\|}{\|x\|} \lesssim \kappa_2(A) \cdot \varepsilon_{\mathrm{mach}}

للمصفوفة SPD، رقم التكييف κ₂(A) = λ_max / λ_min، أي نسبة أكبر قيمة ذاتية إلى أصغرها. وبما أن λᵢ = σᵢ للمصفوفات SPD، فإن κ₂(A) = σ₁/σₙ، وهو رقم التكييف نفسه المحسوب من SVD. الأنظمة SPD جيدة التكييف (κ ≈ 1) تُحل بدقة حتى في الفاصلة العائمة؛ أما سيئة التكييف (κ ≫ 1) فقد تحتاج إلى تهيئة مسبقة أو تنظيم.

المقارنة مع التحليلات الأخرى

كيف يقارن تشولسكي بالتحليلات الأخرى في الوحدة 7؟

مقابل تحليل LU: تشولسكي أسرع بمقدار الضعف ولا يحتاج ترتيب محاور، لكنه يشترط أن تكون A موجبة التعريف ومتماثلة. تحليل LU يعمل على أي مصفوفة مربعة قابلة للعكس، لكنه يكلف ضعف الحساب ويحتاج الترتيب الجزئي للمحاور ليبقى مستقرًا عدديًا.
مقابل تحليل QR: تحليل QR المطبق على A مباشرةً يتجنب تربيع رقم التكييف، فهو أكثر استقرارًا في المسائل سيئة التكييف. تكلفته O(2n³/3)، أي أكثر من تشولسكي، لكنه يعمل على المصفوفات غير المربعة وناقصة الرتبة كذلك.
مقابل SVD: SVD هو الأعمّ والأغنى بالمعلومات، فهو يكشف الرتبة ورقم التكييف وكل الفضاءات الفرعية، لكن تكلفته O(n³) بثابت كبير — نحو ستة أمثال تشولسكي. اختر SVD حين تريد أقصى بصيرة عددية، واختر تشولسكي حين تكون A موجبة التعريف والسرعة مهمة.
مقابل التحليل الطيفي: للمصفوفات SPD يتوفر التحليلان: A = QΛQᵀ (طيفي) وA = LLᵀ (تشولسكي). التحليل الطيفي يعطيك معلومة طيفية — القيم الذاتية منفردة — لكنه أغلى من تشولسكي. لحل Ax = b يُفضل تشولسكي؛ ولتحليل المركبات الرئيسية أو التقطير القطري تحتاج التحليل الطيفي.

الأثر الهندسي

في التطبيق الهندسي، scipy.linalg.cholesky وnumpy.linalg.cholesky وLAPACK's dpotrf هي روتينات تشولسكي القياسية. للأنظمة SPD الكبيرة المتفرقة (FEM، لابلاسيان الرسم البياني)، يوفر scipy.sparse.linalg تشولسكي المتفرق عبر CHOLMOD. في تعلم الآلة، يُكشف torch.linalg.cholesky وjnp.linalg.cholesky مع تطبيقات مسرَّعة بالمعالج الرسومي. نمط "حاول تشولسكي، إذا فشل فالمصفوفة ليست SPD" هو معيار اختبار الإيجابية التعريفية في الكود الإنتاجي. وحساب لوغاريتم المحدد عبر تشولسكي — ضعف مجموع لوغاريتمات العناصر القطرية — هو الطريقة المستقرة عدديًا لتقييم لوغاريتم الاحتمالية الغاوسية متعددة الأبعاد في الاستدلال البايزي.

أبرز النقاط

تحليل تشولسكي A = LLᵀ هو أسرع وأكثر استقرارًا طريقة مباشرة للمصفوفات المتماثلة الموجبة التعريف. يكلف n³/6 عملية ضرب (نصف تحليل LU)، لا يحتاج ترتيب المحاور، ومضمون الاستقرار. يحل الأنظمة الخطية عبر تعويضين مثلثيين، يحسب المحددات كـ (حاصل ضرب العناصر القطرية)²، يختبر الإيجابية التعريفية بمحاولة التحليل، ويولد متجهات عشوائية مترابطة بالتحويل x = μ + Lz. تشمل التطبيقات الإحصاء (محاكاة التباين المشترك)، والتحسين (طريقة نيوتن بمصفوفات هسيان موجبة التعريف)، ومعالجة الإشارات (فلترة كالمان)، وتعلم الآلة (انحدار العمليات الغاوسية).