الطرق التكرارية

لماذا الطرق التكرارية؟

الطرق المباشرة — التخلص الغاوسي، تحليل LU، تحليل تشولسكي — تحل Ax = b بدقة تامة (باستثناء أخطاء التقريب) في O(n³) عملية. عند n = 10,000، هذا 10¹² عملية حسابية: مكلف لكن ممكن. أما عند n = 10⁶ (مقياس نماذج العناصر المنتهية أو المعادلات التفاضلية الجزئية المنفصلة)، يتطلب O(n³) إجراء 10¹⁸ عملية — خارج نطاق الإمكان تمامًا. والأسوأ أن تخزين مصفوفة كثيفة 10⁶ × 10⁶ يحتاج 8 بيتابايت من الذاكرة.

الحل هو أن المسائل الكبيرة الحجم دائمًا تقريبًا متفرقة: كل صف من A لا يحوي سوى حفنة من الإدخالات غير الصفرية (عادةً O(1) أو O(√n) في مسائل المعادلات التفاضلية الجزئية). الطرق التكرارية لا تُشكّل المصفوفة الكاملة قط؛ تحتاج فحسب لضرب المصفوفة في متجه Av، الذي يكلّف O(nnz) حيث nnz عدد العناصر غير الصفرية — غالبًا O(n) للمصفوفات المتفرقة. الثمن هو أن الطرق التكرارية تعيد حلًا تقريبيًا بعد عدد محدود من التكرارات، وليس التقارب مضمونًا دائمًا.

طريقة ياكوبي

أبسط الطرق التكرارية تُحلّل A = D + L + U، حيث D هي القطر الرئيسي، وL المثلث الأسفل الصرف، وU المثلث الأعلى الصرف. تُعيد طريقة ياكوبي صياغة كل معادلة i بحيث يُعبَّر عن xᵢ بدلالة جميع المتغيرات الأخرى، ثم تُحدَّث جميع المركّبات في آنٍ واحد باستخدام التقريب السابق:

طريقة ياكوبي

x_i^{(k+1)} = \frac{1}{a_{ii}}\!\left(b_i - \sum_{j \neq i} a_{ij}\, x_j^{(k)}\right)

تُحدَّث كل مركّبة باستخدام التقريب السابق x⁽ᵏ⁾ فحسب. مصفوفة التكرار هي T_J = −D⁻¹(L + U). تتقارب الطريقة إذا وفقط إذا كان نصف قطر الطيف ρ(T_J) < 1. السيادة القطرية — |aᵢᵢ| > Σⱼ≠ᵢ |aᵢⱼ| لكل i — تضمن ρ(T_J) < 1 وبالتالي التقارب.

في صيغة المصفوفة، تحديث ياكوبي هو x⁽ᵏ⁺¹⁾ = D⁻¹b − D⁻¹(L + U)x⁽ᵏ⁾. لا تحتاج الطريقة إلى تحليل: كل تكرار يكلّف ضرب مصفوفة متفرقة في متجه وn قسمة على عناصر القطر. تتمتع بالتوازي التام لأن جميع المركّبات تُحدَّث بصورة مستقلة — ميزة كبيرة على أجهزة الحوسبة المتعددة النوى والمعالجات الرسومية. عيبها البطء في التقارب: الخطأ عند الخطوة k يتناسب مع ρ(T_J)^k، وقد يقترب ρ(T_J) من 1 في المسائل العملية، مما يستلزم آلاف التكرارات.

تحليل التقارب

عرّف الخطأ عند الخطوة k بـ e⁽ᵏ⁾ = x⁽ᵏ⁾ − x*، حيث x* الحل الحقيقي. بطرح معادلة النقطة الثابتة x* = T_J x* + c من التكرار، نحصل على e⁽ᵏ⁺¹⁾ = T_J e⁽ᵏ⁾. وبالتالي ‖e⁽ᵏ⁾‖ ≤ ‖T_J‖^k ‖e⁽⁰⁾‖. معدل التقارب المقارب يحكمه نصف قطر الطيف ρ(T_J). عدد التكرارات اللازمة لتخفيض الخطأ بمعامل ε هو تقريبًا log(ε) / log(ρ(T_J)). حين ρ(T_J) = 0.99، تقليل الخطأ بمقدار 10⁶ يستلزم نحو 1,380 تكرارًا؛ أما حين ρ(T_J) = 0.5، يكفي نحو 20 تكرارًا.

طريقة غاوس-زيدل

تحسين بسيط على ياكوبي: عند تحديث المركّبة i، استخدم فورًا القيم المُحدَّثة حديثًا x₁⁽ᵏ⁺¹⁾، …، xᵢ₋₁⁽ᵏ⁺¹⁾ بدلًا من القيم القديمة. هذه هي طريقة غاوس-زيدل:

طريقة غاوس-زيدل

x_i^{(k+1)} = \frac{1}{a_{ii}}\!\left(b_i - \sum_{j < i} a_{ij}\, x_j^{(k+1)} - \sum_{j > i} a_{ij}\, x_j^{(k)}\right)

مصفوفة تكرار غاوس-زيدل هي T_GS = −(D + L)⁻¹U. للمصفوفات المتماثلة الموجبة التحديد تتقارب دائمًا؛ وللمصفوفات المهيمنة قطريًا بصرامة تتقارب بسرعة مضاعفة تقريبًا مقارنةً بياكوبي. على عكس ياكوبي، تُحدَّث غاوس-زيدل بشكل تسلسلي مما يحدّ من قابليتها للتوازي.

في صيغة المصفوفة، تُحل منظومة المثلث الأسفل (D + L)x⁽ᵏ⁺¹⁾ = b − Ux⁽ᵏ⁾ بالإحلال الأمامي في O(nnz) عملية. لمعادلة بواسون على شبكة n×n (معيار معادلات تفاضلية جزئية قياسي)، نصف قطر الطيف لغاوس-زيدل هو ρ(T_GS) ≈ 1 − π²/n²، فيحتاج عدد التكرارات اللازمة للتقارب إلى O(n²) — بطيء جدًا للحجم الكبير، مما يحفز على استخدام الشبكات المتعددة والتدرج المترافق المُكيَّف مسبقًا.

الاسترخاء المتتالي المتصاعد (SOR)

يُسرّع SOR طريقةَ غاوس-زيدل بإدخال معامل استرخاء ω. بعد حساب تحديث غاوس-زيدل x̃ᵢ، يأخذ تحديث SOR مزيجًا موزونًا بين القيمة القديمة ونتيجة غاوس-زيدل:

تحديث SOR

x_i^{(k+1)} = (1-\omega)\,x_i^{(k)} + \frac{\omega}{a_{ii}}\!\left(b_i - \sum_{j < i} a_{ij}\,x_j^{(k+1)} - \sum_{j > i} a_{ij}\,x_j^{(k)}\right)

عند ω = 1 يُختزل SOR إلى غاوس-زيدل. عند ω ∈ (1, 2) تحدث الإفراط في الاسترخاء (التخمين ما وراء تحديث غاوس-زيدل)، وهو ما يمكن أن يُسرّع التقارب بشكل كبير. القيمة المثلى لـ ω لمعادلة بواسون على شبكة n×n هي ω* = 2/(1 + sin(π/n))، مما يعطي ρ(T_SOR) ≈ 1 − 2π/n — تحسين O(n) في عدد التكرارات مقارنةً بـ O(n²) لغاوس-زيدل.

إيجاد القيمة المثلى لـ ω تحليليًا يتطلب معرفة نصف قطر الطيف لمصفوفة تكرار غاوس-زيدل، وهو نادرًا ما يتوفر للحالات العامة. عمليًا، يُضبط ω تجريبيًا أو يُقدَّر عبر إجراء تكيّفي. SOR مع القيمة المثلى لـ ω يُقلّص عدد التكرارات من O(n²) إلى O(n) لمسائل بواسون — فارق يحول الساعات إلى دقائق.

شروط التقارب

إطار موحّد لتحليل الطرق التكرارية الثابتة (ياكوبي، غاوس-زيدل، SOR) يعتبر التحليل A = M − N، حيث x⁽ᵏ⁺¹⁾ = M⁻¹(b + Nx⁽ᵏ⁾). النتائج الرئيسية في التقارب:

شرط ضروري وكافٍ: ρ(T) < 1 (نصف قطر طيف مصفوفة التكرار أقل من 1 بصرامة).
كافٍ — السيادة القطرية: إذا كان |aᵢᵢ| > Σⱼ≠ᵢ |aᵢⱼ| لكل i، تتقارب كل من ياكوبي وغاوس-زيدل.
كافٍ — متماثلة موجبة التحديد: إذا كانت A متماثلة موجبة التحديد و0 < ω < 2، يتقارب SOR. غاوس-زيدل (ω = 1) يتقارب دائمًا للمصفوفات المتماثلة الموجبة التحديد.
التباعد مضمون: لـ SOR، ρ(T_SOR) ≥ |ω − 1| لأي مصفوفة، لذا يجب أن يكون ω في (0, 2) لأي أمل في التقارب.
مبرهنة المقارنة: للمصفوفات M (فئة تشمل المصفوفات المهيمنة قطريًا ذات الإدخالات غير القطرية غير الموجبة)، ρ(T_GS) = ρ(T_J)² — نصف قطر طيف غاوس-زيدل هو مربّع نصف قطر طيف ياكوبي.

طريقة التدرج المترافق

للمصفوفات المتماثلة الموجبة التحديد — التي تنشأ في معادلات بواسون، ومعادلات الانحدار العادية، ومصفوفات التباين، وكثير من الأنظمة الفيزيائية — طريقة التدرج المترافق (CG) تفوق بكثير الطرق الثابتة المذكورة أعلاه. CG هي طريقة فضاء كريلوف: تبني تقريبًا أمثليًا من الفضاء المولود بـ {b, Ab, A²b, …, Aᵏb}، الذي يلتقط الاتجاهات الأهم للحل.

خوارزمية التدرج المترافق

\alpha_k = \frac{r_k^T r_k}{p_k^T A p_k},\quad x_{k+1} = x_k + \alpha_k p_k,\quad r_{k+1} = r_k - \alpha_k A p_k,\quad \beta_k = \frac{r_{k+1}^T r_{k+1}}{r_k^T r_k},\quad p_{k+1} = r_{k+1} + \beta_k p_k

يحتفظ CG بثلاثة متجهات: x (الحل)، r = b − Ax (البقية)، و p (اتجاه البحث). في كل خطوة، يُختار α لتصغير الخطأ على طول p؛ ثم يُحدَّث β ليجعل p مترافقًا-A (متعامدًا-A) مع الاتجاه السابق. تتوقف الطريقة في أكثر من n خطوة في الحساب الدقيق.

تتميز طريقة CG بخاصيتي أمثلية بارزتين. أولًا، xᵏ يُصغّر معيار-A للخطأ ‖e‖_A = (eᵀAe)^{1/2} على فضاء كريلوف 𝒦ₖ(A, b). ثانيًا، البقايا rₖ متعامدة تبادليًا واتجاهات البحث pₖ مترافقة-A: pᵢᵀApⱼ = 0 عند i ≠ j. معدل التقارب يعتمد على رقم التكييف:

حد تقارب التدرج المترافق

\frac{\|e_k\|_A}{\|e_0\|_A} \leq 2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k

κ = κ₂(A) هو رقم التكييف. الخطأ يتراجع هندسيًا بمعدل (√κ − 1)/(√κ + 1). عند κ = 100، المعدل 9/11 ≈ 0.82 — 18% تحسن لكل تكرار. عند κ = 10,000، المعدل 99/101 ≈ 0.98 — يستلزم ~300 تكرار لدقة 6 خانات. التكييف المسبق يستبدل A بـ M⁻¹A لتقليص رقم التكييف الفعلي.

التكييف المسبق

التكييف المسبق هو أقوى أداة لتسريع طرق كريلوف. بدلًا من حل Ax = b مباشرةً، نحل المنظومة المُكيَّفة مسبقًا M⁻¹Ax = M⁻¹b، حيث يُختار M بحيث يكون لـ M⁻¹A رقم تكييف أصغر بكثير من A، وتطبيق M⁻¹ رخيص الثمن. من أكثر المُكيِّفات شيوعًا:

التكييف القطري (ياكوبي): M = D. يُقيّس الصفوف. رخيص لكن غالبًا غير كافٍ للمسائل سيئة التكييف.
LU ناقص / IC ناقص: تحليل تقريبي يحافظ على أنماط التفرق. O(nnz) لكل تطبيق. فعّال جدًا لمنظومات المعادلات التفاضلية الجزئية.
SSOR: يُقلّص κ من O(n²) إلى O(n) لمسائل لابلاس.
الشبكة المتعددة الجبرية (AMG): المعيار الذهبي للمعادلات التفاضلية الجزئية الإهليجية. يحقق تقارب شبه O(n) بغض النظر عن حجم الشبكة.
الهدف: تجميع القيم الذاتية لـ M⁻¹A قرب 1.

متى تتفوق الطرق التكرارية على المباشرة؟

الاختيار بين المحللات المباشرة والتكرارية يعتمد على الحجم والبنية وعدد الأطراف اليمنى:

منظومات متفرقة كبيرة (n > 10⁴–10⁵): الطرق المباشرة تملأ البنية المتفرقة أثناء التحليل، منتجةً عوامل مثلثية كثيفة. الطرق التكرارية تحافظ على التفرق طوال الحساب.
أطراف يمنى كثيرة بنفس A: الطرق المباشرة تفوز — حلّل A مرةً واحدة، ثم حلّ كل b جديد في O(n).
مسائل بلا مصفوفة صريحة: إذا كانت A محددة ضمنيًا (كمؤثر تفاضلي أو تقييم دالة)، فالطرق التكرارية هي الوحيدة الممكنة.
مسائل ثلاثية الأبعاد: التحليل المباشر يملأ بشكل أكبر في 3D (O(n²) ملء)، مما يجعل الطرق التكرارية مع التكييف المسبق الخيار الوحيد العملي.

كقاعدة عملية: للمسائل أحادية وثنائية الأبعاد الصغيرة (n ≲ 10⁴)، استخدم الطرق المباشرة للمتانة. للمسائل الكبيرة ثنائية الأبعاد (n ~ 10⁵–10⁶)، يُعدّ CG المُكيَّف مسبقًا أو GMRES معيارًا. للمسائل ثلاثية الأبعاد وأي مسألة n > 10⁶، الشبكة المتعددة أو تحليل النطاق مع تسريع كريلوف هما المقاربة الوحيدة القابلة للتطبيق.

التطبيق الهندسي

في scipy: scipy.sparse.linalg.cg(A, b) تُشغّل CG المُكيَّفة مسبقًا؛ مرّر M=preconditioner لتسريع كبير. scipy.sparse.linalg.spsolve تستخدم محللًا مباشرًا متفرقًا (UMFPACK). لمسائل المعادلات التفاضلية الجزئية في Python، مكتبة pyamg توفر مُكيِّفات الشبكة المتعددة الجبرية. في MATLAB، عامل القسمة الخلفي يختار تلقائيًا محللًا مباشرًا متفرقًا؛ pcg() للتدرج المترافق. عند حل منظومة بواسون متفرقة 10⁶ × 10⁶، يتقارب CG مع مُكيِّف تشولسكي ناقص في ~100 تكرار — كل منها بتكلفة O(n) — مقارنةً بتحليل تشولسكي المتفرق المباشر الذي يكلّف O(n^{3/2}) زمنًا وتخزينًا في ثنائي الأبعاد.

الأفكار الرئيسية

الطرق التكرارية تتجنب التحليل O(n³) بتحسين تقريب عبر حاصل ضرب مصفوفة في متجه. ياكوبي تُحدّث جميع المركّبات في آنٍ واحد باستخدام القيم القديمة؛ غاوس-زيدل تستخدم فورًا المركّبات المُحدَّثة لتقارب أسرع. SOR تضيف معامل استرخاء ω ∈ (0,2) يُقلّص عدد التكرارات من O(n²) إلى O(n) عند القيمة المثلى لمسائل بواسون. التقارب يشترط أن يكون نصف قطر الطيف لمصفوفة التكرار أصغر من 1؛ السيادة القطرية والموجبية التحديد شرطان كافيان رئيسيان. طريقة التدرج المترافق مثلى للمصفوفات المتماثلة الموجبة التحديد: تُصغّر خطأ معيار-A على فضاء كريلوف في k ≤ n خطوة، بمعدل تقارب ((√κ−1)/(√κ+1))^k. التكييف المسبق — تحويل A إلى M⁻¹A بـ κ أصغر — الأداة الرئيسية لتسريع CG. الطرق التكرارية تتفوق على المباشرة في المنظومات المتفرقة الكبيرة ومسائل المعادلات التفاضلية الجزئية ثلاثية الأبعاد والمسائل بلا مصفوفة صريحة.