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

في الجبر الخطي العددي، طريقة غاوس-زايدل المعروفة أيضًا بطريقة ليبمان، هي طريقة تكرارية تستخدم في حل نظم المعادلات الخطية. وسميت على اسم عالمي الرياضيات الألمانيين كارل فريدريش غاوس وفيليب لودفيش فون زايدل. وذكرت فقط في رساله خاصة من غاوس إلى تلميذه كريستيان غيرلنغ عام 1823.^[1] لكنها لم تنشر إلا من قبل زايدل عام 1874.

الوصف

تعتمد طريقة غاوس زايدل على أسلوب التكرار لحل معادلات خطية عددها n بمجهول x.

A x = b

وتعرّف بالتكرار:

L_{*} x^{(k + 1)} = b - U x^{(k)},

بحيث: $x^{(k)}$ هو التكرار أو التقريب رقم k لـ $x, x^{k + 1}$ هو التكرار رقم k + 1 لـ $x$ .

وبالتفصيل:

A = [\begin{matrix} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}], x = [\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix}], b = [\begin{matrix} b_{1} \\ b_{2} \\ ⋮ \\ b_{n} \end{matrix}] .

A = L_{*} + U where L_{*} = [\begin{matrix} a_{11} & 0 & \dots & 0 \\ a_{21} & a_{22} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ a_{n 1} & a_{n 2} & \dots & a_{n n} \end{matrix}], U = [\begin{matrix} 0 & a_{12} & \dots & a_{1 n} \\ 0 & 0 & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & 0 \end{matrix}] .

ومن ثم يمكن كتابة نظام المعادلات الخطية كما يلي:

L_{*} x = b - U x

x^{(k + 1)} = L_{*}^{- 1} (b - U x^{(k)}) .

x_{i}^{(k + 1)} = \frac{1}{a_{i i}} (b_{i} - \sum_{j < i} a_{i j} x_{j}^{(k + 1)} - \sum_{j > i} a_{i j} x_{j}^{(k)}), i, j = 1, 2, \dots, n .

^[2]

$A x = b$

A = [\begin{matrix} 16 & 3 \\ 7 & - 11 \end{matrix}]

و

b = [\begin{matrix} 11 \\ 13 \end{matrix}]

نحتاج لاستخدام المعادلة

x^{(k + 1)} = L_{*}^{- 1} (b - U x^{(k)})

في صورة

x^{(k + 1)} = T x^{(k)} + C

حيث:

T = - L_{*}^{- 1} U

و

C = L_{*}^{- 1} b .

يجب أن نحلل المصفوفة $A_{}^{}$ إلى مجموع $L_{*}^{}$ و $U_{}^{}$ :

L_{*} = [\begin{matrix} 16 & 0 \\ 7 & - 11 \end{matrix}]

و

U = [\begin{matrix} 0 & 3 \\ 0 & 0 \end{matrix}] .

ومعكوس $L_{*}^{}$ هو:

L_{*}^{- 1} = {[\begin{matrix} 16 & 0 \\ 7 & - 11 \end{matrix}]}^{- 1} = [\begin{matrix} 0.0625 & 0.0000 \\ 0.0398 & - 0.0909 \end{matrix}]

.

نستطيع الآن إيجاد:

T = - [\begin{matrix} 0.0625 & 0.0000 \\ 0.0398 & - 0.0909 \end{matrix}] \times [\begin{matrix} 0 & 3 \\ 0 & 0 \end{matrix}] = [\begin{matrix} 0.000 & - 0.1875 \\ 0.000 & - 0.1193 \end{matrix}],

C = [\begin{matrix} 0.0625 & 0.0000 \\ 0.0398 & - 0.0909 \end{matrix}] \times [\begin{matrix} 11 \\ 13 \end{matrix}] = [\begin{matrix} 0.6875 \\ - 0.7443 \end{matrix}] .

بذلك نكون قد حصلنا على $T_{}^{}$ و $C_{}^{}$

نفرض:

x^{(0)} = [\begin{matrix} 1.0 \\ 1.0 \end{matrix}] .

ثم يمكننا أن نحسب:

x^{(1)} = [\begin{matrix} 0.000 & - 0.1875 \\ 0.000 & - 0.1193 \end{matrix}] \times [\begin{matrix} 1.0 \\ 1.0 \end{matrix}] + [\begin{matrix} 0.6875 \\ - 0.7443 \end{matrix}] = [\begin{matrix} 0.5000 \\ - 0.8636 \end{matrix}] .

x^{(2)} = [\begin{matrix} 0.000 & - 0.1875 \\ 0.000 & - 0.1193 \end{matrix}] \times [\begin{matrix} 0.5000 \\ - 0.8636 \end{matrix}] + [\begin{matrix} 0.6875 \\ - 0.7443 \end{matrix}] = [\begin{matrix} 0.8494 \\ - 0.6413 \end{matrix}] .

x^{(3)} = [\begin{matrix} 0.000 & - 0.1875 \\ 0.000 & - 0.1193 \end{matrix}] \times [\begin{matrix} 0.8494 \\ - 0.6413 \end{matrix}] + [\begin{matrix} 0.6875 \\ - 0.7443 \end{matrix}] = [\begin{matrix} 0.8077 \\ - 0.6678 \end{matrix}] .

x^{(4)} = [\begin{matrix} 0.000 & - 0.1875 \\ 0.000 & - 0.1193 \end{matrix}] \times [\begin{matrix} 0.8077 \\ - 0.6678 \end{matrix}] + [\begin{matrix} 0.6875 \\ - 0.7443 \end{matrix}] = [\begin{matrix} 0.8127 \\ - 0.6646 \end{matrix}] .

x^{(5)} = [\begin{matrix} 0.000 & - 0.1875 \\ 0.000 & - 0.1193 \end{matrix}] \times [\begin{matrix} 0.8127 \\ - 0.6646 \end{matrix}] + [\begin{matrix} 0.6875 \\ - 0.7443 \end{matrix}] = [\begin{matrix} 0.8121 \\ - 0.6650 \end{matrix}] .

x^{(6)} = [\begin{matrix} 0.000 & - 0.1875 \\ 0.000 & - 0.1193 \end{matrix}] \times [\begin{matrix} 0.8121 \\ - 0.6650 \end{matrix}] + [\begin{matrix} 0.6875 \\ - 0.7443 \end{matrix}] = [\begin{matrix} 0.8122 \\ - 0.6650 \end{matrix}] .

x^{(7)} = [\begin{matrix} 0.000 & - 0.1875 \\ 0.000 & - 0.1193 \end{matrix}] \times [\begin{matrix} 0.8122 \\ - 0.6650 \end{matrix}] + [\begin{matrix} 0.6875 \\ - 0.7443 \end{matrix}] = [\begin{matrix} 0.8122 \\ - 0.6650 \end{matrix}] .

وبذلك تكون قيمة x:

x = A^{- 1} b = [\begin{matrix} 0.8122 \\ - 0.6650 \end{matrix}] .