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

الأنظمة الخطية التي تنشأ في الكثير من التطبيقات الهندسية والعلمية تكون مصفوفة معاملاتها عبارة عن مصفوفة هشة، أي المصفوفة التي تكون معظم عناصرها أصفاراً وذات سعة كبيرة.وإذا تم استخدام الطرائق المباشرة لحل هذة الأنظمة فسوف يتطلب ذلك جهد حسابي كبير (وناتج معظمة أصفاراً), وتحتاج إلى سعة كبيرة (غير ضرورية) في ذاكرة الحاسوب والتي قد لايمكن توفرها. لهذا السبب فإن الكثير من الباحثين الذين تواجههم مثل هذه الأنظمة. تعد الطرائق التكرارية طرائق تقريبية أي أنها لا تحسب الحل مباشرة وإنما تبدأ من حل تقريبي وليكن 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) ونعبر عن ذلك بالمتباينة:
(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
إذا أعطينا عدد المجاهيل n, عناصر المصفوفة A , المتجهb , المتجه الابتدائي y=x^0 , التفاوت المسموح به Tol والعدد الأقصى للتكرارات M فإن الخوارزمية توجد حل تقريبي y للنظام الخطي Ax=b
* الخطوة 1: ضع k=1
* الخطوة 2: بينما k≤M أعمل الخطوات 3-6
* الخطوة 3: من أجل i=1,2,……….n احسب
* الخطوة 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 من أجل
](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 احسب
* الخطوة 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 يصبح لدينا
ومنه يكون لدينا الصيغة التكرارية لطريقة جاوس –سايدل x^(k)=T_GS x^(k-1)+c من أجل k≥1 , حيث أن c=(D-L)^(-1) b وT_GS=(D-L)^(-1) U .
* 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 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| x_1^k | 0.0000 | 0.6000 | 1.0473 | 0.9326 | 1.0152 | 0.9890 | 1.0032 | 0.9981 | 1.0006 | 0.9997 | 1.0001 |
| x_2^k | 0.0000 | 2.2727 | 1.7159 | 2.053 | 1.9537 | 2.0114 | 1.9922 | 2.0023 | 1.9987 | 2.0004 | 1.9998 |
| x_3^k | 0.0000 | -1.1000 | -0.8052 | -1.0493 | -0.9681 | -1.0103 | -0.9945 | -1.0020 | -0.9990 | -1.0004 | -0.9998 |
| x_4^k | 0.0000 | 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_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 ‖ وهذا يحقق الدقة المطلوبة.
بمقارنة النتائج العددية الموجودة بطريقة جاكوبي وطريقة جاوس –سايدل نلاحظ أننا حصلنا على الحل التقريبي المطلوب عند التكرار السابع عندما استخدمنا طريقة جاكوبي بينما حصلنا علية عند التكرار الخامس باستخدام طريقة جاوس – سايدل مما يعني أن طريقة جاوس أسرع في التقارب إلى الحل التام من طريقة جاكوبي.