The double splitting iteration method for solving the large indefinite least squares problem

ملخص تقني: طريقة التكرار بالتقسيم المزدوج لمسائل المربعات الصغرى غير المحددة الكبيرة

بيان المشكلة
تتناول الورقة التحديات الحسابية المرتبطة بحل مسائل المربعات الصغرى غير المحددة (ILS) واسعة النطاق، والتي تُصاغ كتقليل للصيغة التربيعية غير المحددة $(b - Ax)^T J (b - Ax)$، حيث $A \in \mathbb{R}^{m \times n}$ مصفوفة كبيرة متفرقة، و $b \in \mathbb{R}^m$، و $J = \text{diag}(I_p, -I_q)$ هي مصفوفة توقيع حيث $p+q=m$. عندما يكون $pq > 0$، تؤدي هذه المسألة إلى معادلة طبيعية$A^T J A x = A^T J b$ تتضمن مصفوفة هسيان (Hessian) ليست موجبة التعريف. وبينما توجد طرق مباشرة للمسائل الصغيرة الكثيفة، تُفضل المخططات التكرارية للأنظمة واسعة النطاق. تعتمد الحلول التكرارية الرائدة الحالية لهذه المسألة بشكل أساسي على استراتيجيات "التقسيم الفردي" لمصفوفة المعاملات $A^T J A = M - N$، مثل طرق التقسيم (SP)، والتقسيم العام (GSP)، وطريقة الاتجاه الضمني المتناوب (ADI).

المنهجية
يقترح المؤلفون طريقة تكرار جديدة تعتمد على التقسيم المزدوج (DS). وخلافاً للمقاربات التقليدية التي تفكك مصفوفة المعاملات إلى جزأين ($M - N$)، تستخدم هذه الطة تفكيكاً ثلاثي الأجزاء:
$$A^T J A = P - R - S$$
حيث $P$ مصفوفة غير منفردة. وبإلهام من بنية طريقة GSP، حدد المؤلفون مصفوفات محددة بناءً على التقسيم $A = [A_1; A_2]$:

• $P = \alpha I + A_1^T A_1$ (مصفوفة متماثلة وموجبة التعريف، SPD)
• $R = A_2^T A_2$ (متماثلة)
• $S = \alpha I$ (متماثلة)
  حيث $\alpha > 0$ هو معامل معطى.

يؤدي هذا التفكيك إلى مخطط تكرار ثابت ذي خطوتين:
$$x_{k+1} = P^{-1} R x_k + P^{-1} S x_{k-1} + P^{-1} A^T J b$$
يتضمن هذا الصياغة معلومات من الخطوتين السابقتين ($x_k$ و $x_{k-1}$)، مما يميزها عن الطبيعة ذات الخطوة الواحدة لطرق SP و GSP. تم تحليل تقارب هذا المخطط من خلال فحص نصف قطر الطيف $\rho(W)$ لمصفوفة التكرار الكتلية المرتبطة $W$. اشتق المؤلفون معادلة تربيعية قياسية للقيم الذاتية $\lambda$ للمصفوفة $W$ وطبقوا تمهيدية تتعلق بجذور المعادلات التربيعية لإثبات أن $|\lambda| < 1$ لجميع قيم $\alpha > 0$.

المساهمات الرئيسية

1. إطار عمل تكراري مبتكر: تقدم الورقة استراتيجية تقسيم مزدوج ملموسة مصممة خصيصاً للمعادلات الطبيعية الناشئة عن مسائل ILS، مما يوفر بديلاً متميزاً لنماذج التقسيم الفردي المهيمنة.
2. إثبات التقارب غير المشروط: قدم المؤلفون تحليلاً طيفياً دقيقاً يثبت أن طريقة تكرار DS المقترحة تتقارب بشكل غير مشروط لأي معامل $\alpha$ موجب. وقد تم وضع هذه النتيجة في سياقها من خلال ربطها بمعايير التقارب لمصفوفات هيرميت الموجبة التعريف الموجودة في الأدبيات السابقة.
3. التنفيذ الخوارزمي: تم تقديم خوارزمية مفصلة (الخوارزمية 2.1)، توضح الخطوات الحسابية، بما في ذلك استخدام تفكيك تشوليسكي لعكس المصفوفة $P$ الموجبة التعريف والمتماثلة.

النتائج العددية
أُجريت تجربتان عدديتان لتقييم أداء طريقة DS مقابل طرق SP و GSP و ADI:

• المثال 3.1 (المصفوفات الكثيفة): باستخدام مصفوفات كثيفة عشوائية واسعة النطاق، تم اختبار طريقة DS مع أبعاد متغيرة ($m$ تصل إلى 54,000). مع المعامل الأمثل $\alpha=1$، تقاربت طريقة DS في تكرارين بالضبط. وبينما تقاربت طرق SP و GSP أيضاً في تكرار واحد، حققت طريقة DS أوقات معالجة مركزية (CPU times) أقل بكثير (على سبيل المثال، ~4.8 ثانية مقابل ~75 ثانية لطريقة GSP عند $m=51,000$).
• المثال 3.2 (المصفوفات المتفرقة): باستخدام مصفوفات مشتقة من مسائل المربعات الصغرى الكلية، تم اختبار طريقة DS مع هياكل متفرقة. مع المعامل الأمثل $\alpha=10^{-4}$، تقاربت طريقة DS مرة أخرى في تكرارين. وقد تفوقت باستمرار على طرق التقسيم الفردي من حيث وقت الحوسبة عبر جميع الأحجام المختبرة (حتى $m=8,192$)، مما أظهر كفاءة فائقة حتى مع زيادة حجم المسألة.

الأهمية والادعاءات
تدعي الورقة أن نموذج تكرار التقسيم المزدوج المقترح يقدم تحسيناً بنائياً على مقاربات التقسيم الفردي التقليدية. تكمن الأهمية الأساسية في قدرة الطريقة على تحقيق سرعة تقارب أكبر (من حيث وقت المعالجة المركزية) والمتانة لمسائل ILS واسعة النطاق. ويؤكد المؤلفون أنه بينما تتطلب الطة خطوتين سابقتين، فإن دمج هذه المعلومات التاريخية يسمح بخفض كبير في التكلفة الحسابية مقارلة بطرق الخطوة الواحدة مثل SP و GSP و ADI. يوفر هذا العمل مراجع منهجية للبحوث المستقبلية في طرق التكرار القائمة على التقسيم المزدوج ويقترح توسعات محتملة في اختيار المعاملات التكيفية وأنواع أخرى من الأنظمة الخطية غير المحددة.