الطرائق التكرارية لحل أنظمة المعادلات الخطية

الطرائق التكرارية لحل أنظمة المعادلات الخطية Iterative Methods for Solving Linear Systems

الأنظمة الخطية التي تنشأ في الكثير من التطبيقات الهندسية والعلمية تكون مصفوفة معاملاتها عبارة عن مصفوفة هشة، أي المصفوفة التي تكون معظم عناصرها أصفاراً وذات سعة كبيرة.وإذا تم استخدام الطرائق المباشرة لحل هذة الأنظمة فسوف يتطلب ذلك جهد حسابي كبير (وناتج معظمة أصفاراً), وتحتاج إلى سعة كبيرة (غير ضرورية) في ذاكرة الحاسوب والتي قد لايمكن توفرها. لهذا السبب فإن الكثير من الباحثين الذين تواجههم مثل هذه الأنظمة. تعد الطرائق التكرارية طرائق تقريبية أي أنها لا تحسب الحل مباشرة وإنما تبدأ من حل تقريبي وليكن x^0، وتحسب متتالية من المتجهات ∞^{X^(k)] _(k=0] والتي يُتأمل أن تتقارب إلى الحل المضبوط x. ويمكن توضيح ذلك بالشكل التالي:

X^(0) →X^(1)→X^(2)→⋯X^(k)→⋯→X

الفكرة الرئيسية لهذه الطرائق هي كتابة النظام الخطي Ax=b , حيث أن A مصفوفة مربعة من النوع n×n بالشكل المساوي: x=Tx+C

حيث أن T مصفوفة مربعة من النوع n×n و c متجه عمود ذو البعد n . بعد اختيار التقريب الابتدائي X^0 ,

نحسب متتالية المتجهات ∞^{X^(k) ]_(k=0] باستخدام الصيغة التكرارية: x^(k)=Tx^(k-1)+c

من أجل k≥1 . تعتمد المصفوفة Tفي تكوينها على المصفوفة A أما المتجه فإن عناصره تستنتج من المصفوفة A والمتجه b. هناك عدة أساليب لكتابة المصفوفة T والمتجه c سوف ندرس أسلوبين وهما: جاكوبي، جاوس – سيدل

بداية نكتب النظام الخطي AX=b بالشكل التالي:

a_11 x_1+a_12 x_2+⋯.+a_1n x_n=b_1
a_21 x_1+a_22 x_2+⋯.+a_2n x_n=b_2
a_n1 x_1+a_n2 x_2+⋯.+a_nn x_n=b_n

ونفرض أن i=1,2,…….,n ; a_ii≠0 (وإذا كان a_ii=0 لقيمة معينة من قيم i فيمكن تبديل المعادلات بصورة مناسبة). من مجموعة المعادلات السابقة يمكننا أن نكتب العلاقات التالية التي تعطي قيم المتغيرات x_1 ,x_2,….,x_n بدلالة هذه القيم نفسها

[ x_1=-1/a_11 [a_12 x_2+⋯+a_1n x_n-b_1
[x_2=-1/a_22 [a_21 x_1+a_23 x_3+⋯+a_2n x_n-b_2
[x_n=-1/a_nn [a_n1 x_1+a_n2 x_2+⋯+a_(n,n-1) x_(n-1)-b_n

وللاختصار يمكن صياغة النظام السابق بالصورة التالية: [x_i=1/a_ii [b_i-∑_(k=1)^n a_ik x^k

a_ii≠0 , k≠i لكل i=1,2,….,n و k≥1 . عادة فإننا نعيد ترتيب المعادلات والمتغيرات (المجاهيل) بحيث نحقق قدر الاستطاعة شرط السيطرة القطرية (diagonal dominance) والذي يعني أن القيمة المطلقة لأي عنصر قطري a_ii تكون أكبر من – أو تساوي – مجموع القيم المطلقة للعناصر الأخرى في صفه (الصف رقم i) ونعبر عن ذلك بالمتباينة:

 |a_ii |≥∑_■(j=1@j≠i)^n[|a_ij |] ; i=1,2,…..n|

طريقة جاكوبي التكرارية: في هذه الطريقة نبدأ بقيمة تقريبية أولية للمجاهيل ولتكن

(x^(0)=x_1^(0),x_2^(0),…..x_n^(0

ثم نعوض بهذه القيم في الطرف الأيمن في نظام المعادلات السابق بالصورة الأتية [(x_i^(k)=1/a_ii [b_i-∑_■(j=1@j≠i)^n[a_ij x_j^(k-1 لكل i=1,2,….,n و k≥1. لنحصل على التقريب الأول للمجاهيل وهو

(x^(1)=x_1^(1),x_2^(1),…..x_n^(1

ثم نكرر العملية للحصول على التقريب الثاني (x^(2)=x_1^(2),x_2^(2),…..x_n^(2

ولنصل إلى الدقة المطلوبة والتي تحقق المتباينات التالية x_i^(k)-x_i^(k-1) ‖<∈_i i=1,2,……,n ‖

كذلك يمكن كتابتها بالشكل المصفوفي كالتالي: x^((k))=T_J X^((K-1))+c

حيث أن k≥1 والمصفوفة T_J والمتجه C كما هي معرفة سابقاً. يمكن استنتاج الشكل المصفوفي لطريقة جاكوبي التكرارية كما يلي:

أولاً نوزع المصفوفة A إلى حاصل جمع المصفوفات: A=D-L-U بحيث D تمثل المصفوفة القطرية وL تمثل المثلث السفلي من المصفوفة وU تمثل المثلث العلوي من المصفوفة وبذلك يمكن تحويل النظام الخطي Ax=b إلى الشكل D-L-U)x=b) والذي منه نحصل على (Dx)-(L+U)x=b→Dx=(L+U)x+b)→x=D^(-1) (L+U)x+D^(-1) b)

وبالتالي يكون لدينا الصيغة التكرارية لطريقة جاكوبي حيث أن: c=D^(-1) b و (T_J=D^(-1) (L+U

خوارزمية: طريقة جاكوبي التكرارية: تتضمن الخوارزمية كيفية استخدام طريقة جاكوبي التكرارية. نشير هنا إلى أن البرنامج الذي ينتج من استخدام هذه الخوارزمية لايُخزن جميع متجهات المتتالية وإما يخزن متجهين متتاليين فقط، وبالتالي يستطيع طباعة نتيجة تكرارين متتاليين فقط وهما، حسب رموز الخوارزمية x_i وy_i لكل i=1,2,3……..,n

إذا أعطينا عدد المجاهيل n, عناصر المصفوفة A , المتجهb , المتجه الابتدائي y=x^0 , التفاوت المسموح به Tol والعدد الأقصى للتكرارات M فإن الخوارزمية توجد حل تقريبي y للنظام الخطي Ax=b

الخطوة 1: ضع k=1
الخطوة 2: بينما k≤M أعمل الخطوات 3-6
الخطوة 3: من أجل i=1,2,……….n احسب

[x_i=1/a_ii [b_i-∑_■(j=1@j≠i)^n a_ij y_j

الخطوة 4: إذا كان ‖ Tol ≤ ‖x-y فاكتب الحل التقريبي المطلوب هو " i=1,2,….,n ,x_i ", قف.
الخطوة 5: ضع k=k+1
الخطوة 6: من أجل i=1,2,….,n ضع y_i=x_i
الخطوة 7: اكتب «لم نحصل على الحل التقريبي المطلوب بعد M تكرار», قف.
ملاحظات:

يتضح من الخطوة 3 في خوارزمية جاكوبي التكرارية أنه يجب أن يكون a_ii≠0 من أجل i=1,2,….,n , لذلك إذا كانت المصفوفة A غير شاذة وأحد عناصر قطرها يكون مساوياً للصفر فإنه يجب إعادة ترتيب المعادلات بحيث يكون عناصر القطر لا تساوي الصفر

الخطوة الرابعة هي خطوة الوقوف وتتضمن شرط الوقوف: ‖(X^(K)-X^(K-1)) ‖≤∈

من أجل k≥1 حيث أن (X^(K و (X^(K-1 الحلين التقريبيين عند التكراريين k-1 و k على الترتيب. هنا ∈= 5×[t^[10 حيث tأكبر من أو يساوي 1 , عدد صحيح هو الدقة المطلوبة للحل التقريبي أو مايسمى بالتفاوت المسموح به حول الحل. في الواقع يوجد شروط أخرى لإيقاف الحسابات نذكر منها الشرط: ‖(X^(K)-X^(K-1)) ‖/‖X^(K) ‖ ≤∈

مثال 1: لنظام الخطي التالي:
E_1: 10x_1-x_2+2x_3 = 6
E_2:-x_1+11x_2-x_3+3x_4= 25
E_3:2x_1-x_2+10x_3-x_4= -11
E_4: 3x_2-x_3+8 x_4= 15

حل وحيد x=[1,2,-1,1]^T . استخدم طريقة جاكوبي التكرارية لإيجاد حل تقريبي إلى x بحيث x^(0)=[0,0,0,0]^t باستخدام معيار التوقف (X^(K)-X^(K-1) ‖/‖X^(K) ‖ ≤10^(-3)‖ الحل: من مجموعة المعادلات السابقة يمكننا أن نكتب العلاقات التالية التي تعطي قيم المتغيرات x_1 ,x_2,….,x_n بدلالة هذه القيم نفسها:

x_1=1/10 x_2-1/5 x_3+3/5
x_2=1/11 x_1+1/11 x_3-3/11 x_4+25/11
x_3=-1/5 x_1+1/10 x_2+1/10 x_4-11/10
x_4= -3/8 x_2+1/8 x_3+3/5

ثم نعوض بقيم x^(0)=[0,0,0,0]^t في الطرف الأيمن في نظام المعادلات السابق بالصورة الأتية

x_1^(1)=1/10 x_2^(0)-1/5 x_3^(0)+3/5 =0.6000
x_2^(1)=1/11 x_1^(0)+1/11 x_3^(0)-3/11 x_4^(0)+25/11 =2.2727
x_3^(1)=-1/5 x_1^(0)+1/10 x_2^(0)+1/10 x_4^(0)-11/10=-1.1000
x_4^(1)= -3/8 x_2^(0)+1/8 x_3^(0)+3/5 =1.8750

نكرر نفس الطريقة لنحصل على عدد من التكرارات كم هو موضح بالجدول: رقم 1

إلى أن نقف عند التكرار العاشر وذلك لكون: X^(10)-X^(9)) ‖/‖X^(10) ‖ =(8.0 ×[10]^-4)/(1.9998)≤[10[^-3)‖ في الواقع 0.0002= ‖x^(10)-x‖ .......................................................

طريقة جاوس – سايدل التكرارية:

كما هو واضح من الصيغة التكرارية لجاكوبي فإننا نحسب العنصر x_i^(k), i=1,2,….,n , باستخدام العناصر (x_j^(k-1 من أجل 1≤j≤nحيث أن j≠i . ولكن لو استخدمنا العناصر (x_j^(k من أجل 1≤j≤i-1 وال (x_j^(kعناصر (x_j^(k-1 من أجل 1+i≤j≤n لحصلنا على تقريب أفضل وذلك لأن العناصر x_j^(k), 1≤j≤i-1 هي تقريب أفضل للعناصر التي توافقها في الحل المضبوط من العناصر x_j^(k-1), 1≤j≤i-1 . هذا هو مبدأ طريقة جاوس – سايدل التكرارية والتي يمكن صيغتها التكرارية بالشكل: ](x_i^(k)=1/a_ii [b_i-∑_(j=1)^(i-1)[a_ij x_j^(k) ]-∑_(j=i+1)^n[a_ij x_j^(k-1 من أجل i=1,2,…,n و k≥1 .

خوارزمية جاوس –سيدل التكرارية:

إذا أعطينا عدد المجاهيل n, عناصر المصفوفة A , المتجهb , المتجه الابتدائي (y=x^(0 , التفاوت المسموح به Tol والعدد الأقصى للتكرارات M فإن الخوارزمية توجد حل تقريبي y للنظام الخطي Ax=b

الخطوة 1: ضع k=1
الخطوة 2: بينما k≤M أعمل الخطوات 3-6
الخطوة 3: من أجل i=1,2,……….n احسب

[x_i=1/a_ii [b_i-∑_(j=1)^(i-1)[a_ij x_j] -∑_(j=i+1)^n[a_ij y_j

الخطوة 4: إذا كان ‖Tol ≤ ‖x-y أطبع الحل التقريبي المطلوب هو " i=1,2,….,n ,x_i ", قف.
الخطوة 5: ضع k=k+1
الخطوة 6: من أجل i=1,2,….,n ضع y_i=x_i
الخطوة 7: أطبع «لم نحصل على الحل التقريبي المطلوب بعد M تكرار», قف.

لها نفس ملاحظات خوارزمية طريقة جاكوبي الآن لكتابة الصيغة التكرارية لهذه الطريقة بالشكل المصفوفي، فإنه من العلاقة [(x_i^(k) =1/a_ii [b_i-∑_(j=1)^(i-1)[a_ij x_j^((k) ] -∑_(j=i+1)^n [a_ij x_j^(k-1 يصبح لدينا D-L)x-(U)x=b→ (D-L)x=(U)x+b→x=(D-L)^(-1) (U)x+(D-L)^(-1) b) ومنه يكون لدينا الصيغة التكرارية لطريقة جاوس –سايدل x^(k)=T_GS x^(k-1)+c من أجل k≥1 , حيث أن c=(D-L)^(-1) b وT_GS=(D-L)^(-1) U .

مثال 2: استخدم طريقة جاوس سايدل التكرارية لإيجاد تكرارين للأنظمة الخطية التالية:

4x_1+ 2x_2 + x_3= 11
2x_1+ x_2+ 4x_3= 16
x_1+2x_2 = 3 -

الحل : قمنا بتبديل المعادلتين الثانية والثالثة لأن a_33=0 وبذلك تصبح المعادلات بالترتيب التالي:

4x_1+2x_2+ x_3= 11
x_1+2x_2 = 3 -
2x_1+x_2+ 4x_3= 16

ومن هذه المعادلات نحصل على العلاقات التالية:

x_1=11/4-1/2 x_2-1/4 x_3
x_2=3/2+1/2 x_1
x_3=4-1/2 x_1-1/4 x_2

نختار – اختيارياً – المتجه الابتدائي التالي للتقريبات الأولية: x^((0))=(1,1,1)^T وبذلك نحصل على القيم التالية في التكرار الأول:

x_1^((1))=11/4-1/2-1/4=2
x_2^((1))=3/2+1/2 (2)=5/2
x_3^((1))=4-1/2 (2)-1/4 (5/2)=19/8

والتكرار الثاني يعطينا:

x_1^(2)=11/4-1/2(5/2)-1/4(19/8)=29/32
x_2^(2)=3/2+1/2 (29/32)=125/64
x_3^(2)=4-1/2 (29/32)-1/4 (125/64)=783/256
مثال3: أوجدي حل النظام الخطي بطريقتين؟
4x_1-x_2+x_3=1
x_1+〖3x〗_2+x_3=4
x_1+2x_2+5x_3=2

بدقة ∈=5×[10]^(-4)وذلك ابتداء من المتجه الابتدائي x^(0)=[1,0,0]^T . الحل:

باستخدام طريقة جاكوبي التكرارية لإيجاد حلاً تقريبياً للنظام الخطي

بداية لنكتب صيغة جاكوبي التكرارية لهذا النظام والتي يمكن كتابتها بالشكل:

x_1^(k)=1/4 x_2^(k-1)-1/4 x_3^(k-1)+1/4
x_2^(k)=-1/3 x_1^(k-1)-1/3 x_3^((k-1)+4/3
x_3^(k) =-1/5 x_1^(k-1)-2/5 x_2^(k-1) +2/5

من أجل k≥1 وبوضع k=1 تأخذ الصيغة الشكل التالي:

x_1^(1)=1/4 x_2^(0)-1/4 x_3^(0)+1/4
x_2^(1)=-1/3 x_1^(0)-1/3 x_3^(0)+4/3
x_3^(1) =-1/5 x_1^(0)-2/5 x_2^(0)+2/5

وبالتعويض عن x_1^((0))=1 و x_2^((0))=0 وx_3^((0))=0 نحصل على:

x_1^(1)=1/4 (0)-1/4 (0)+1/4=1/4
x_2^(1)=-1/3 (1)-1/3 (0)+4/3=1
x_3^(1) =-1/5 (1)-2/5 (0)+2/5=1/5

إذا التكرار (التقريب) الأول هو x^(1)=[1/4,1,1/5]^T بعد ذلك نضع k=2 ونعوض عن قيم عناصر المتجه (x^(1 لنحصل على:

x_1^(2)=1/4 x_2^(1)-1/4 x_3^(1)+1/4=1/4 (1)-1/4 (1/5)+1/4=0.45
x_2^(2)=-1/3 x_1^(1)-1/3 x_3^(1)+4/3=-1/3 (1/4)-1/3 (1/5)+4/3=1.18333
x_3^(2) =-1/5 x_1^(1) -2/5 x_2^(1)+2/5=-1/5 (1/4)-2/5 (1)+2/5=-0.05

وبالتالي فإن التكرار الثاني هو x^(2)=[0.45,1.18333,-0.5]^T وهكذا نستمر حتى نحصل على الحل التقريبي المطلوب. النتائج العددية لحل هذه المسألة موجودة في الجدول التالي: رقم 2

k	1	2	3	4	5	6	7	8	9	10
x_1^k	0.6000	1.0473	0.9326	1.0152	0.9890	1.0032	0.9981	1.0006	0.9997	1.0001
x_2^k	2.2727	1.7159	2.053	1.9537	2.0114	1.9922	2.0023	1.9987	2.0004	1.9998
x_3^k	-1.1000	-0.8052	-1.0493	-0.9681	-1.0103	-0.9945	-1.0020	-0.9990	-1.0004	-0.9998
x_4^k	1.8750	0.8852	1.1309	0.9739	1.0214	0.9944	1.0036	0.9989	1.0006	0.9998

حيث يتضح أن (x^(7هو الحل التقريبي المطلوب. نشير هنا إلى أننا أوقفنا العمليات الحسابية عندما حصلنا على الحل التقريبي الذي يحقق الشرط ‖(X^(K)-X^K-1) ‖≤∈ حيث حصلنا على: X^(7)-X^(6) =[0.00021,-0.00017,0.00024]^T وبالتالي يكون لدينا X^(7)-X^(6) ‖=2.4×[10]^(-4)<5×[10]^-4)‖ وهذا يحقق الدقة المطلوبة.

باستخدام طريقة جاوس –سيدل التكرارية لإيجاد حلاً تقريبياً للنظام الخطي:

صيغة جاوس – سيدل التكرارية لهذا النظام تكتب بالشكل التالي:

x_1^(k)=1/4 x_2^(k-1)-1/4 x_3^(k-1)+1/4
x_2^(k)=-1/3 x_1^(k)-1/3 x_3^(k-1)+4/3
x_3^(k)=-1/5 x_1^(k)-2/5 x_2^(k)+2/5

من أجل k≥1 وبوضع k=1 تأخذ الصيغة الشكل التالي:

x_1^(1)=1/4 x_2^(0)-1/4 x_3^(0)+1/4
x_2^(1)=-1/3 x_1^(1)-1/3 x_3^(0)+4/3
x_3^(1)=-1/5 x_1^(1) -2/5 x_2^(1)+2/5

وبالتعويض عن x_2^(0)=0 وx_3^(0)=0 في المعادلة الأولى من هذه الصيغة نحصل على: x_1^(1)=1/4 (0)-1/4 (0)+1/4 = 1/4 وبالتعويض عن x_1^(1) = 1/4 و x_3^(0)=0 في العادلة الثانية يكون لدينا: x_2^(1) =-1/3 (1/4)-1/3 (0)+4/3=1.25 وبالتعويض عن x_1^(1) =0.25 و x_2^(1) =1.25 في المعادلة الثالثة نجد أن: x_3^(1)=-1/5 (0.25)-2/5 (1.25)+2/5=-0.1 إذا التكرار (التقريب) الأول هو x^(1)=[0.25,1.25,-0.1]^T وهكذا نستمر حتى نحصل على الحل التقريبي المطلوب. النتائج العددية لحل هذه المسألة موجودة في الجدول التالي: رقم 3

k	1	2	3	4	5	6
x_1^k	0.25000	0.45000	0.55833	0.59083	0.59833	0.59978
x_2^k	1.00000	1.18333	1.20000	1.20167	1.20028	1.20017
x_3^k	0.20000	-0.05000	-0.16333	-0.19167	-0.19883	-0.19978

حيث يتضح أن ((x^((5 هو الحل التقريبي المطلوب. نشير هنا إلى أننا أننا أوقفنا العمليات الحسابية عندما حصلنا على الحل التقريبي الذي يحقق الشرط حيث حصلنا على: x^(5) -x^(4)=[0.00027,0.00002,0.00017]^T وبالتالي يكون لدينا (x^(5) - x^(4) ‖=2.7×[10]^(-4) < 5×[10]^(-4 ‖ وهذا يحقق الدقة المطلوبة. بمقارنة النتائج العددية الموجودة بطريقة جاكوبي وطريقة جاوس –سايدل نلاحظ أننا حصلنا على الحل التقريبي المطلوب عند التكرار السابع عندما استخدمنا طريقة جاكوبي بينما حصلنا علية عند التكرار الخامس باستخدام طريقة جاوس – سايدل مما يعني أن طريقة جاوس أسرع في التقارب إلى الحل التام من طريقة جاكوبي.

المراجع

كتاب التحليل العددي - للمؤلفين: محمود أبو العز، محمد صلاح الدين السيد متولي، فتحي عبد السلام، 1427هـ / 2006م – مكتبة الرشد فرع الرياض.
كتاب التحليل العددي - للمؤلف الدكتور أبو بكر أحمد السيد – الطبعة الأولى 1409هـ /1988م- دار القلم للنشر والتوزيع.
كتاب الطرق العددية والتحليل العددي- للمؤلف أ.د أبو بكر أحمد السيد - الطبعة الأولى 1433هـ/ 2012م – دار حنين للنشر والتوزيع.
كتاب التحليل العددي، عيسى بن عبد الله السعيد، قسم الرياضيات/ كلية العلوم / جامعة الملك سعود – 1432هـ /2011م
Numerical Analysis - Richard L.Burden/J.Douglas Faires- Ninth Edition

k	1	2	3	4	5
((x_1^k	0.25000	0.60000	0.59417	0.59961	0.59988
((x_2^k	1.25000	1.18333	1.19972	1.19970	1.19998
((x_3^k	-0.10000	-0.19333	-0.19872	-0.19980	-0.19997