در آموزش‌های قبلی مجله فرادرس، با روش ژاکوبی برای حل دستگاه معادلات خطی به فرم $$ Ax = b $$ ($$ A $$ یک ماتریس $$ n \times n $$ است) آشنا شدیم. در این آموزش، روش دیگری را معرفی خواهیم کرد که روش گوس سایدل نام دارد و می‌توان آن را نسخه‌ای بهبود یافته از روش ژاکوبی در نظر گرفت.

روش گوس سایدل

ابتدا روش گوس سایدل را با جزئیات برای معادله‌ها بیان می‌کنیم، سپس فرم ماتریسی آن را ارائه خواهیم کرد.

فرض کنید $$ x ^ { ( 0 ) } =\begin {bmatrix} x _ 1 ^ { ( 0 ) } \\ x _ 2 ^ { ( 0 ) } \\ \vdots\\ x _ n ^ { ( 0 ) } \end {bmatrix} $$ یک تقریب اولیه برای جواب $$ x $$ از دستگاه $$n$$ معادله و $$ n $$ مجهولی زیر باشد:

$$ \large \begin {align} \quad \begin {matrix} E ( 1 ) : & a _ { 1 1 } x _ 1 & + & a _ { 1 2 } x _ 2 & + & \cdots & + & a _ { 1 n } x _ n & = & b _ 1 \\ E ( 2 ) : & a _ { 2 1 } x _ 1 & + & a _ { 2 2 } x _ 2 & + & \cdots & + & a _ { 2 n } x _ n & = & b _ 2 \\ \vdots & \vdots & & \vdots & & \ddots & & \vdots & & \vdots \\ E ( n ) : & a _ { n 1 } x _ 1 & + & a _ { n 2 } x _ 2 & + & \cdots & + & a _ { n n } x _ n & = & b _ n & \end {matrix} \end {align} $$

ابتدا متغیر $$ x _ i $$ را را برای $$ i = 1, 2, …, n$$ از معادلات $$ E ( i ) $$ به دست می‌آوریم:

$$ \large \begin {align} \quad x _ 1 = \frac { b _ 1 – \left [ a _ { 1 2 } x _ 2 + a _ { 1 3 } x _ 3 + … + a _ { 1 n } x _ n \right ] } { a _ { 1 1 } } \\ x _ 2 = \frac { b _ 2 – \left [ a _ { 2 1 } x _ 1 + a _ { 2 3 } x _ 3 + … + a _ { 2 n } x _ n \right ] } { a _ { 2 2 } } \\ \quad \quad \quad \quad \quad \quad \vdots \quad \quad \quad \quad \quad \quad \\ x _ n = \frac { b _ n – \left [ a _ { n 1 } x _ 1 + a _ { n 2 } x _ 2 + … + a _ { n , n – 1 } x _ { n – 1 } \right ] } { a _ { n n } } \end {align} $$

اکنون تقریب نخست $$ x^{(1)} $$ برای جواب دقیق $$ x $$ را با استفاده از روش تکرار گوس سایدل به دست می‌آوریم. بنابراین، $$ x_1^{(1)}$$ را با قرار دادن مقادیر جواب اولیه تقریب $$ x^{(0)} $$ در معادله اول محاسبه می‌کنیم. سپس تقریب $$ x_2^{(1)} $$ را با کمک مقادیر اولیه و $$ x_1^{(1)} $$ محاسبه شده به دست می‌آوریم. به همین صورت، مقادیر جدید را در معادلات جایگذاری کرده و تکرار را ادامه می‌دهیم:

$$ \large \begin {align} \quad x _ 1 ^ { ( 1 ) } = \frac { b _ 1 – \left [ a _ { 1 2 } x _ 2 ^ { ( 0 ) } + a _ { 1 3 } x _ 3 ^ { ( 0 ) } + a _ { 1 4 } x _ 4 ^ { ( 0 ) } + . . . + a _ { 1 n } x _ n ^ { ( 0 ) } \right ] } { a _ { 1 1 } } \\ x _ 2 ^ { ( 1 ) } = \frac { b _ 2 – \left [ a _ { 2 1 } x _ 1 ^ { ( 1 ) } + a _ { 2 3 } x _ 3 ^ { ( 0 ) } + a _ { 2 4 } x _ 4 ^ { ( 0 ) } + . . . + a _ { 2 n } x _ n ^ { ( 0 ) } \right ] } { a _ { 2 2 } } \\ x _ 3 ^ { ( 1 ) } = \frac { b _ 3 – \left [ a _ { 3 1 } x _ 1 ^ { ( 1 ) } + a _ { 3 2 } x _ 2 ^ { ( 1 ) } + a _ { 3 4 } x _ 4 ^ { ( 0 ) } + . . . + a _ { 3 n } x _ n ^ { ( 0 ) } \right ] } { a _ { 3 3 } } \\ \quad \quad \quad \quad\quad \quad \vdots \quad \quad \quad \quad \quad \quad \\ x _ n ^ { ( 1 ) } = \frac { b _ n – \left [ a _ { n 1 } x _ 1 ^ { ( 1 ) } + a _ { n 2 } x _ 2 ^ { ( 1 ) } + a _ { n 3 } x _ 3 ^ { ( 1 ) } + . . . + a _ { n , n – 1 } x _ { n – 1 } ^ { ( 1 ) } \right ] } { a _ { n n } } \end {align} $$

با استفاده از نماد مجموع، برای $$ i = 1, 2, …, n $$ خواهیم داشت:

$$ \large \begin {align} \quad x _ i ^ { ( 1 ) } = \frac { b _ i – \left [ \sum _ { j = 1 } ^ { i – 1 } a _ { i j } x _ j ^ { (1 ) } + \sum _ { j = i + 1 } ^ { n } a _ { i j } x _ j ^ { ( 0 ) } \right ] } { a _ { i i } } \end {align} $$

به همین ترتیب، برای به دست آوردن تقریب دوم $$ x^{(2)} $$ از $$ x $$ با استفاده از روش گوس سایدل داریم:

$$ \large \begin {align} \quad x _ 1 ^ { ( 2 ) } = \frac { b _ 1 – \left [ a _ { 1 2 } x _ 2 ^ { ( 1 ) } + a _ { 1 3 } x _ 3 ^ { ( 1 ) } + a _ { 1 4 } x _ 4^ { ( 1) } + … + a _ { 1 n } x _ n ^ { ( 1 ) } \right ] } { a_ { 1 1 } } \\ x _ 2 ^ { ( 2 ) } = \frac { b _ 2 – \left [ a _ { 2 1 } x _ 1 ^ { (2 ) } + a _ { 2 3 } x _ 3 ^ { ( 1 ) } + a _ { 2 4 } x _ 4 ^ { ( 1 ) } + . . . + a _ { 2 n } x _ n ^ { ( 1 ) } \right ] } { a _ { 2 2 } } \\ x _ 3 ^ { ( 2 ) } = \frac { b _ 3 – \left [ a _ { 3 1 } x _ 1 ^ { ( 2 ) } + a _ { 3 2 } x _ 2 ^ { ( 2 ) } + a _ { 3 4 } x _ 4 ^ { ( 1 ) } + … + a _ { 3 n } x _ n ^ { ( 1 ) } \right ] } { a _ { 3 3 } } \\ \quad \quad \quad \quad\quad \quad \vdots \quad \quad \quad \quad \quad \quad \\ x _ n ^ { ( 2 ) } = \frac { b _ n – \left [ a _ { n 1 } x _ 1 ^ { ( 2 ) } + a _ { n 2 } x _ 2^ { ( 2 ) } + a _ { n 3 } x _ 3 ^ { ( 2 ) } + … + a _ { n , n – 1 } x _ { n – 1 } ^ { ( 2 ) } \right ] } { a _ { n n } } \end {align} $$

با استفاده از نماد مجموع، برای $$ i = 1, 2, …, n $$ خواهیم داشت:

$$ \large \begin {align} \quad x _ i ^ { ( 2 ) } = \frac { b _ i – \left [ \sum _ { j = 1 } ^ { i – 1 } a _ { i j } x _ j ^ { ( 2 ) } + \sum _ { j = i + 1 } ^ { n } a _ {i j } x _ j ^ { ( 1 ) } \right ] } { a _ { i i } } \end {align} $$

تقریب $$ x $$ را با این جواب‌ها ادامه می‌دهیم تا جایی که جواب به یک مقدار درست همگرا شود. بنابراین، برای $$ k \ge 1$$ و $$ i = 1, 2, …, n $$، نتیجه تکرار $$k$$اُم روش گوس سایدل به صورت زیر خواهد بود:

$$ \large \begin {align} \quad x _ 1 ^ { ( k ) } = \frac { b _ 1 – \left [ a _ { 1 2 } x _ 2 ^ { ( k -1 ) } + a _ { 1 3 } x _ 3 ^ { ( k – 1 ) } + a _ { 1 4 } x _ 4 ^ { ( k – 1 ) } + . . . + a _ { 1 n } x _ n ^ { ( k – 1 ) } \right ] } { a _ { 1 1 } } \\ x _ 2 ^ { ( k ) } = \frac { b _ 2 – \left [ a _ { 2 1 } x _ 1 ^ { ( k ) } + a _ { 2 3 } x _ 3 ^ { ( k – 1 ) } + a _ { 2 4} x _ 4 ^ { ( k – 1 ) } + . . . + a _ { 2 n } x _ n ^ { ( k – 1 ) } \right ] } { a _ { 2 2 } } \\ x _ 3 ^ { ( k ) } = \frac { b _ 3 – \left [ a _ { 3 1 } x _ 1 ^ { ( k ) } + a _ { 3 2 } x _ 2 ^ { ( k ) } + a _ { 3 4 }x _ 4 ^ { ( k – 1 ) } + . . . + a _ { 3 n } x _ n ^ { ( k – 1 ) } \right ] } { a _ { 3 3 } } \\ \quad \quad \quad \quad\quad \quad \vdots \quad \quad \quad \quad \quad \quad \\ x _ n ^ { ( k ) } = \frac { b _ n – \left [ a _ { n 1 } x _ 1 ^ { ( k ) } + a _ { n 2 } x _ 2 ^ { ( k ) } + a _ { n 3 } x _ 3 ^ { ( k ) } + . . . + a _ { n , n – 1 } x _ { n – 1 } ^ { ( k ) } \right ] } { a _ { n n } } \end {align} $$

در نهایت، با استفاده از نماد مجموع، برای $$ i = 1, 2, …, n $$ خواهیم داشت:

$$ \large \begin {align} \quad x _ i ^ { ( k ) } = \frac { b _ i – \left [ \sum _ { j = 1 } ^ { i – 1 } a _ { i j } x _ j ^ { ( k ) } + \sum _ { j = i + 1 } ^ { n } a _ { i j } x _ j ^ { ( k -1 ) } \right ] } { a _ { i i } } \end {align} $$

فرم ماتریسی روش گوس سایدل

در این بخش، فرم ماتریسی روش گوس سایدل را ارائه خواهیم کرد. روش گوس سایدل یک روش تکراری برای حل یک دستگاه مربعی از $$n$$ معادله با مجهول $$ \mathbf { x } $$ است:

$$ \large A \mathbf x = \mathbf b $$

روش گوس سایدل در حقیقت با تکرار زیر تعریف می‌شود:

$$ \large L _ * \mathbf { x } ^ { ( k + 1 ) } = \mathbf { b } – U \mathbf { x } ^ { ( k ) } $$

که در آن، $$ \mathbf{x}^{(k)} $$ برابر با $$k$$اُمین تقریب یا تکرار $$ \mathbf {x}$$، $$\mathbf {x} ^ {(k+1)}$$ تکرار بعدی یا $$k + 1 $$ برای $$ \mathbf {x}$$ است و ماتریس $$ A $$ به ماتریس پایین‌مثلثی $$ L _ * $$ و ماتریس اکیداً بالامثلثی $$U$$ تجزیه شده است: $$ A = L _ * + U $$.

برای بررسی جزئیات، $$ A$$، $$ \mathbf {x}$$ و $$ \mathbf { b } $$ را با مؤلفه‌هایشان نشان می‌دهیم:

$$ \large A = \begin {bmatrix} a _ { 1 1 } & a _ { 1 2 } & \cdots & a _ { 1 n } \\ a _ { 2 1 } & a _ { 2 2 } & \cdots & a _ { 2 n } \\ \vdots & \vdots & \ddots & \vdots \\a _ { n 1 } & a _ { n 2 } & \cdots & a _ { n n } \end {bmatrix} , \qquad \mathbf { x } = \begin {bmatrix} x _ { 1 } \\ x _ 2 \\ \vdots \\ x _ n \end {bmatrix} , \qquad \mathbf { b } = \begin {bmatrix} b _ { 1 } \\ b _ 2 \\ \vdots \\ b _ n \end {bmatrix} . $$

در ادامه، ماتریس $$A$$ را به دو ماتریس پایین‌مثلثی و اکیداً بالامثلثی به صورت زیر تجزیه می‌کنیم:

$$ \large A = L _ * + U \; , \qquad \text {} \qquad L _ * = \begin {bmatrix} a _ { 1 1 } & 0 & \cdots & 0 \\ a _ { 2 1 } & a _ { 2 2 } & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\a _ { n 1 } & a _ { n 2 } & \cdots & a _ { n n } \end {bmatrix} , \quad U = \begin {bmatrix} 0 & a _ { 1 2 } & \cdots & a _ { 1 n } \\ 0 & 0 & \cdots & a _ { 2 n } \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 0 \end {bmatrix} . $$

دستگاه معادلات خطی را می‌توان به صورت زیر بازنویسی کرد:

$$ \large L _ * \mathbf { x } = \mathbf { b } – U \mathbf { x } $$

در اینجا، با استفاده از روش گوس سایدل، $$ \mathbf { x } $$ سمت چپ تساوی بالا را با استفاده از مقدار قبلی $$ \mathbf{x}$$ سمت راست، حل می‌کنیم. این گفته به صورت تحلیلی زیر نوشته می‌شود:‌

$$ \large \mathbf { x } ^ { ( k + 1) } = L _ * ^ { – 1 } ( \mathbf { b } – U \mathbf { x } ^ { ( k ) } ) . $$

اما با بهره‌گیری از فرم مثلثی $$ L  _ * $$، می‌توان $$ \mathbf { x } ^ {(k+1)}$$ را با استفاده از جانشانی پیشرو (Forward Substitution) محاسبه کرد:‌

$$ \large x ^ { ( k + 1 ) } _ i = \frac { 1 } { a _ { i i } } \left ( b _ i – \sum _ { j = 1} ^ { i – 1 } a _ { i j } x ^ { ( k + 1 ) } _ j – \sum _ { j = i + 1 } ^ { n } a _ { i j } x ^ { ( k ) }_ j \right ) , \quad i = 1 , 2 , \dots , n . $$

این روند تا جایی ادامه پیدا می‌کند که تغییرات حاصل از تکرار به مقداری کمتر از یک مقدار مشخص برسد. می‌بینیم که فرمول روش گوس سایدل بسیار شبیه به روش ژاکوبی است.

در محاسبه $$ { \mathbf{x}} ^ { ( k + 1 )}$$ از عناصری از $$ \mathbf {x } ^ { ( k + 1 )} $$ که قبلاً محاسبه شده‌اند و عناصر $$ \mathbf { x } ^ { (k)}$$ استفاده می‌شود که در تکرار $$k +1$$ هنوز محاسبه نشده‌اند. این بدین معنی است که برخلاف روش ژاکوبی، تنها یک بردار ذخیره‌سازی لازم است، زیرا وقتی عناصر محاسبه شدند، می‌توان آن‌ها را جایگزین کرد. این موضوع، یکی از مزایای مهم روش گوس سایدل برای مسائلی با ابعاد بزرگ است.

البته، برخلاف روش ژاکوبی، محاسبات مربوط به هر مؤلفه را نمی‌توان به صورت موازی انجام داد. علاوه بر این، مقادیر هر تکرار به مرتبه معادلات اصلی بستگی دارند.

همگرایی روش گوس سایدل

ویژگی‌های همگرایی روش گوس سایدل به ماتریس $$ A$$ وابسته‌اند. به عبارت دیگر، روش گوس سایدل همگرا است، اگر:

حتی اگر شرایط مذکور بالا برقرار نباشند، گاهی روش گوس سایدل همگرا می‌شود.

مثال‌های روش گوس سایدل

در این بخش، چند مثال را از روش گوس سایدل بررسی می‌کنیم.

مثال ۱

دستگاه خطی $$ A\mathbf { x } = \mathbf { b } $$ را در نظر بگیرید که به صورت زیر داده شده است:

$$ \large A =
\begin {bmatrix}
16 & 3 \\
7 & – 1 1 \\
\end {bmatrix} \; , \; \; \; \; b =
\begin {bmatrix}
1 1 \\
1 3
\end {bmatrix} . $$

می‌خواهیم از معادله $$ \mathbf { x } ^ { ( k + 1 ) } = L _ * ^ { – 1 } ( \mathbf { b } – U \mathbf { x } ^ { ( k ) } ) $$ به فرم زیر استفاده کنیم:

$$ \large \mathbf { x } ^ { ( k + 1 ) } = T \mathbf { x } ^ { ( k ) } + C $$

که در آن، $$ T = – L _ * ^ { – 1} U $$ و $$ C = L _ * ^ { – 1 } \mathbf { b } $$.

باید ماتریس $$ A$$ را به صورت مجموع ماتریس پایین‌مثلثی $$ L _ * $$ و ماتریس اکیداً بالامثلثی $$ U $$ بنویسم:

$$ \large L _ * =
\begin {bmatrix}
1 6 & 0 \\
7 & – 1 1 \\
\end {bmatrix}
\;\; , \; \; \; \; U =
\begin {bmatrix}
0 & 3 \\
0 & 0
\end {bmatrix} . $$

معکوس ماتریس $$ L _ * $$ برابر است با:

$$ \large L _ * ^ { – 1 } =
\begin {bmatrix}
1 6 & 0 \\
7 & – 1 1
\end {bmatrix} ^ { – 1 }
=
\begin {bmatrix}
0 . 0 6 2 5 & 0 . 0 0 0 0 \\
0 . 0 3 9 8 & – 0 . 0 9 0 9 \\
\end {bmatrix} $$

بنابراین، خواهیم داشت:

$$ \large T = –
\begin {bmatrix}
0 . 0 6 2 5 & 0 . 0 0 0 0 \\
0.0398 & -0.0909
\end {bmatrix}
\times
\begin {bmatrix}
0 & 3 \\
0 & 0
\end {bmatrix}
=
\begin {bmatrix}
0 . 0 0 0 & – 0 .1 8 7 5 \\
0 . 0 0 0 & – 0 . 1 1 9 4
\end {bmatrix} , $$

$$ \large C =
\begin {bmatrix}
0 . 0 6 2 5 & 0 . 0 0 0 0 \\
0 . 0 3 9 8 & – 0 . 0 9 0 9
\end {bmatrix}
\times
\begin {bmatrix}
1 1 \\
1 3
\end {bmatrix}
=
\begin {bmatrix}
0 . 6 8 7 5 \\
– 0 . 7 4 3 9
\end {bmatrix} . $$

اکنون $$ T $$ و $$ C $$ را داریم و می‌توانیم از آن‌ها برای به دست آوردن بردارهای تکرار $$ \mathbf { x } $$ استفاده کنیم. ابتدا، $$ \mathbf{x}^{(0)}$$ را انتخاب می‌کنیم. هرچه این حدس اولیه بهتر باشد، الگوریتم سریع‌تر همگرا خواهد شد.

بنابراین، حدس اولیه را به صورت زیر انتخاب می‌کنیم:

$$ \large x ^ { ( 0 ) } =
\begin {bmatrix}
1 . 0 \\
1 . 0
\end {bmatrix} . $$

در نتیجه، خواهیم داشت:

$$ \large \begin {align*}
x ^ { ( 1 ) } & =
\begin {bmatrix}
0 . 0 0 0 & – 0 . 1 8 7 5 \\
0 . 0 0 0 & – 0 . 1 1 9 3
\end {bmatrix}
\times
\begin {bmatrix}
1 . 0 \\
1 . 0
\end {bmatrix}
+
\begin {bmatrix}
0 . 6 8 7 5 \\
– 0 . 7 4 4 3
\end {bmatrix}
=
\begin {bmatrix}
0 . 5 0 0 0 \\
– 0 . 8 6 3 6
\end {bmatrix} . \\
x ^ { ( 2 ) } & =
\begin {bmatrix}
0 . 0 0 0 & – 0 . 1 8 7 5 \\
0 . 0 0 0 & – 0 . 1 1 9 3
\end {bmatrix}
\times
\begin {bmatrix}
0 . 5 0 0 0 \\
– 0 . 8 6 3 6
\end {bmatrix}
+
\begin {bmatrix}
0 . 6 8 7 5 \\
– 0 . 7 4 4 3
\end {bmatrix}
=
\begin {bmatrix}
0 . 8 4 9 4 \\
– 0 . 6 4 1 3
\end {bmatrix} . \\
x ^ { ( 3 ) } & =
\begin {bmatrix}
0 . 0 0 0 & – 0 . 1 8 7 5 \\
0 . 0 0 0 & – 0 . 1 1 9 3
\end {bmatrix}
\times
\begin {bmatrix}
0 . 8 4 9 4 \\
– 0 . 6 4 1 3 \\
\end {bmatrix}
+
\begin {bmatrix}
0 . 6 8 7 5 \\
– 0 . 7 4 4 3
\end {bmatrix}
=
\begin {bmatrix}
0 . 8 0 7 7 \\
– 0 . 6 6 7 8
\end {bmatrix} . \\
x ^ { ( 4 ) } & =
\begin {bmatrix}
0 . 0 0 0 & – 0 . 1 8 7 5 \\
0 . 0 0 0 & – 0 . 1 1 9 3
\end {bmatrix}
\times
\begin {bmatrix}
0 . 8 0 7 7 \\
– 0 . 6 6 7 8
\end {bmatrix}
+
\begin {bmatrix}
0 . 6 8 7 5 \\
– 0 . 7 4 4 3
\end {bmatrix}
=
\begin {bmatrix}
0 . 8 1 2 7 \\
– 0 . 6 6 4 6
\end {bmatrix} . \\
x ^ { ( 5 ) } & =
\begin {bmatrix}
0 . 0 0 0 & – 0 . 1 87 5 \\
0 . 0 0 0 & – 0 . 1 1 9 3
\end {bmatrix}
\times
\begin {bmatrix}
0 . 8 1 2 7 \\
– 0 . 6 6 4 6
\end {bmatrix}
+
\begin {bmatrix}
0 . 6 8 7 5 \\
– 0 . 7 4 4 3
\end {bmatrix}
=
\begin {bmatrix}
0 . 8 1 2 1 \\
– 0 . 6 6 5 0
\end {bmatrix} . \\
x ^ { ( 6 ) } & =
\begin {bmatrix}
0 .0 0 0 & – 0 . 1 8 7 5 \\
0 . 0 0 0 & – 0 . 1 1 9 3
\end {bmatrix}
\times
\begin {bmatrix}
0 . 8 1 2 1 \\
– 0 .6 6 5 0
\end {bmatrix}
+
\begin {bmatrix}
0 . 6 8 7 5 \\
– 0 . 7 4 4 3
\end {bmatrix}
=
\begin {bmatrix}
0 . 8 1 2 2 \\
– 0 . 6 6 5 0
\end {bmatrix} . \\
x ^ { ( 7 ) } & =
\begin {bmatrix}
0 . 0 0 0 & – 0 . 1 8 7 5 \\
0 . 0 0 0 & – 0 . 1 1 9 3
\end {bmatrix}
\times
\begin {bmatrix}
0 . 8 1 2 2 \\
– 0 . 6 6 5 0
\end {bmatrix}
+
\begin {bmatrix}
0 . 6 8 7 5 \\
– 0 . 7 4 4 3
\end {bmatrix}
=
\begin {bmatrix}
0 . 8 1 2 2 \\
– 0 . 6 6 5 0
\end {bmatrix} .
\end {align*} $$

همان‌طور که انتظار می‌رود، الگوریتم به جواب دقیق همگرا می‌شود:

$$ \large \mathbf { x } = A ^ { – 1 } \mathbf { b } \approx \begin {bmatrix} 0 . 8 1 2 2 \\ – 0 . 6 6 5 0 \end {bmatrix} . $$

در حقیقت، ماتریس $$ A$$ اکیداً قطری غالب است (اما معین مثبت نیست).

مثال ۲

دستگاه خطی $$ A \mathbf { x } = \mathbf { b } $$ را در نظر بگیرید:

$$ \large A = \begin {bmatrix}
2 & 3 \\
5 & 7 \\
\end {bmatrix} \; , \; \; \; b =
\begin {bmatrix}
1 1 \\
1 3 \\
\end {bmatrix} . $$

می‌خواهیم از معادله $$ \mathbf { x } ^ { ( k + 1 ) } = L _ * ^ { – 1 } ( \mathbf { b } – U \mathbf { x } ^ { ( k ) } ) $$ به فرم زیر استفاده کنیم:

$$ \large \mathbf { x } ^ { ( k + 1 ) } = T \mathbf { x } ^ { ( k ) } + C $$

که در آن، $$ T = – L _ * ^ { – 1} U $$ و $$ C = L _ * ^ { – 1 } \mathbf { b } $$.

باید ماتریس $$ A$$ را به صورت مجموع ماتریس پایین‌مثلثی $$ L _ * $$ و ماتریس اکیداً بالامثلثی $$ U $$ بنویسم:

$$ \large L _ * =
\begin {bmatrix}
2 & 0 \\
5 & 7 \\
\end {bmatrix} \; , \; \; \;\; U =
\begin {bmatrix}
0 & 3 \\
0 & 0 \\
\end {bmatrix} . $$

معکوس ماتریس $$ L _ * $$ برابر است با:

$$ \large L _ * ^ { – 1 } =
\begin {bmatrix}
2 & 0 \\
5 & 7 \\
\end {bmatrix} ^ { – 1 }
=
\begin {bmatrix}
0 . 5 0 0 & 0 . 0 0 0 \\
– 0 . 3 5 7 & 0 . 1 4 3 \\
\end {bmatrix} . $$

بنابراین، خواهیم داشت:

$$ \large \begin {align*} T & = –
\begin {bmatrix}
0 . 5 0 0 & 0 . 0 0 0 \\
– 0 . 3 5 7 & 0 . 1 4 3 \\
\end {bmatrix}
\times
\begin {bmatrix}
0 & 3 \\
0 & 0 \\
\end {bmatrix}
=
\begin {bmatrix}
0 . 0 0 0 & – 1 . 5 0 0 \\
0 . 0 0 0 & 1 . 0 7 1 \\
\end {bmatrix} , \\ C & =
\begin {bmatrix}
0 . 5 0 0 & 0 . 0 0 0 \\
– 0 . 3 5 7 & 0 . 1 4 3 \\
\end {bmatrix}
\times
\begin {bmatrix}
1 1 \\
1 3 \\
\end {bmatrix}
=
\begin {bmatrix}
5 . 5 0 0 \\
– 2 . 0 7 1 \\
\end {bmatrix} . \end {align*} $$

اکنون $$ T $$ و $$ C $$ را داریم و می‌توانیم از آن‌ها برای به دست آوردن بردارهای تکرار $$ \mathbf { x } $$ استفاده کنیم. ابتدا، $$ \mathbf{x}^{(0)}$$ را انتخاب می‌کنیم. هرچه این حدس اولیه بهتر باشد، الگوریتم سریع‌تر همگرا خواهد شد.

بنابراین، حدس اولیه را به صورت زیر انتخاب می‌کنیم:

$$ \large x ^ { ( 0 ) } =
\begin {bmatrix}
1 . 1 \\
2 . 3 \\
\end {bmatrix} . $$

در نتیجه، خواهیم داشت:

$$ \large \begin {align*}
x ^ { ( 1 ) } & =
\begin{bmatrix}
0 & – 1 . 5 0 0 \\
0 & 1 . 0 7 1 \\
\end {bmatrix}
\times
\begin {bmatrix}
1 . 1 \\
2 . 3 \\
\end {bmatrix}
+
\begin {bmatrix}
5 .5 0 0 \\
– 2 . 0 7 1 \\
\end {bmatrix}
=
\begin {bmatrix}
2 . 0 5 0 \\
0 . 3 9 3 \\
\end {bmatrix} . \\
x ^ { ( 2 ) } & =
\begin {bmatrix}
0 & – 1 . 5 0 0 \\
0 & 1 . 0 7 1 \\
\end {bmatrix}
\times
\begin {bmatrix}
2 . 0 5 0 \\
0 . 3 9 3 \\
\end {bmatrix}
+
\begin {bmatrix}
5 .5 0 0 \\
– 2 . 0 7 1 \\
\end {bmatrix}
=
\begin {bmatrix}
4 . 9 1 1 \\
– 1 . 6 5 1 \\
\end {bmatrix} . \\ x ^ { ( 3 ) } & = \cdots . \,
\end {align*} $$

اگر همگرایی را آزمایش کنیم، خواهیم دید که الگوریتم واگرا می‌شود. در واقع، ماتریس $$ A$$ نه قطری غالب است و نه مثبت معین. در نتیجه، همگرایی به جواب دقیق زیر تضمین نشده است و در این حالت رخ نمی‌دهد:

$$ \large \mathbf { x } = A ^ { – 1 } \mathbf { b } = \begin {bmatrix} – 3 8 \\ 2 9 \end {bmatrix} $$

مثال ۳

فرض کنید $$k$$ معادله داریم که $$ \mathbf {x} _ n $$ بردارهایی از این معادلات هستند و $$ \mathbf { x } _ 0 $$ نقطه شروع است. از معادله اول $$ \mathbf { x } _ 1 $$ را برحسب $$ c _ { n + 1 } $$، $$ c _{n + 2 } $$، … و $$ x _ n $$ حل می‌کنیم. برای معادلات بعدی مقادیر قبلی $$ \mathbf { x } $$ را جایگذاری می‌کنیم.

برای روشن شدن موضوع، مثال زیر را در نظر بگیرید.

$$ \begin {array} {rrrrl}
1 0 x _ 1 & – x _ 2 & + 2 x _ 3 & & = 6 , \\
– x _ 1 & + 1 1 x _ 2 & – x _ 3 & + 3 x _ 4 & = 2 5 , \\
2 x _ 1 & – x _ 2 & + 1 0 x _ 3 & – x _ 4 & = – 1 1 , \\
& 3 x _ 2 & – x _ 3 & + 8 x _ 4 & = 1 5 .
\end {array} $$

مجهولات $$ x _ 1 $$، $$ x _ 2$$، $$ x _ 3 $$ و $$ x _ 4 $$ به صورت زیر نوشته می‌شوند:

$$ \large \begin {align}
x _ 1 & = x _ 2 / 1 0 – x _ 3 / 5 + 3 / 5 , \\
x _ 2 & = x _ 1 / 1 1 + x _ 3 / 11 – 3 x _ 4 / 11 + 25 / 11 , \\
x _ 3 & = – x _ 1 / 5 + x _ 2 / 10 + x _ 4 /10 – 11 / 10 , \\
x _ 4 & = – 3 x _ 2 /8 + x _ 3 / 8 + 1 5 / 8 .
\end {align} $$

تقریب اولیه را $$ ( 0, 0 , 0 , 0 ) $$ در نظر می‌گیریم و بر این اساس، جواب تقریبی نخست را به صورت زیر محاسبه می‌کنیم:

$$ \large \begin {align}
x _ 1 & = 3 / 5 = 0 . 6 , \\
x _ 2 & = ( 3 / 5 ) / 1 1 + 2 5 / 1 1 = 3 / 55 + 25 / 11 = 2.3272, \\
x _ 3 & = – ( 3 / 5 ) / 5 + ( 2 . 3 2 7 2 ) / 10 – 11/ 10 = – 3 / 25 + 0 . 2 3272 – 1.1 = – 0. 9 8 7 3 , \\
x _ 4 & = – 3 ( 2.3272 ) / 8 + ( – 0.9873 ) / 8 + 1 5 / 8 = 0.8789 .
\end {align} $$

با استفاده از تقریب‌های به دست آمده، روند تکراری تا زمانی ادامه پیدا می‌کند که دقت مطلوب حاصل شود. جواب‌های تقریبی زیر بعد از چهار تکرار به دست آمده‌اند.

$$ \large \begin {array} {llll}
x _ 1 & x _ 2 & x _ 3 & x _ 4 \\
\hline 0 . 6 & 2 . 3 2 7 2 7 & – 0 . 9 8 7 2 7 3 & 0 . 8 7 8 8 6 4 \\ 1 . 0 3 0 1 8 & 2 . 0 36 9 4 & – 1 . 0 1 4 4 6 & 0 .9 8 43 4 1 \\ 1. 0 06 5 9 & 2 . 0 03 5 6 & – 1 . 0 0 2 5 3 & 0 . 9 9 8 3 5 1 \\ 1 . 0 0 0 8 6 & 2 . 0 0 0 3 & – 1 . 0 0 0 3 1 & 0 . 9 9 9 8 5 \end {array} $$

جواب دقیق دستگاه $$ ( 1 , 2 , – 1 , 1 ) $$ است.

الگوریتم پیاده‌سازی روش گوس سایدل

از آنجایی که عناصری را که قبلاً محاسبه شده‌اند می‌توان بازنویسی و جایگزین کرد، فقط به یک بردار ذخیره‌سازی نیاز است و نمایه‌سازی بردار حذف می‌شود. الگوریتم روش گوس سایدل به شرح زیر است:

الگوریتم روش گوس سایدل

پیاده‌سازی روش گوس سایدل در پایتون

برنامه زیر، کد پایتون روش گوس سایدل را نشان می‌دهد.

خروجی حاصل از اجرای این برنامه به صورت زیر است:

پیاده‌سازی روش گوس سایدل در متلب

کد کوتاه زیر، برنامه حل دستگاه با تعداد معادلات دلخواه و با استفاده از روش گوس سایدل در متلب است که در آن، از فرمول زیر استفاده شده است:

$$ \large x ^ { ( k + 1 ) } _ i = \frac { 1 } { a _ { i i } } \left ( b _ i – \sum _ { j < i } a _ { i j } x ^ { ( k + 1 ) } _ j – \sum _ { j > i } a _ { i j } x ^ { ( k) } _ j \right ) , \quad i, j = 1 , 2 , \ldots , n $$

برنامه مربوط به فرمول بالا در متلب، به سادگی به صورت زیر نوشته می‌شود:

برنامه متلب زیر نیز یک نسخه دیگر از روش گوس سایدل است که در آن، از فرم ماتریسی استفاده شده است:

پیاده‌سازی روش گوس سایدل در C

کد زیر، پیاده‌سازی روش گوس سایدل در زبان برنامه‌نویسی C را نشان می‌دهد.

خروجی حاصل از اجرای این برنامه به صورت زیر خواهد بود:

خروجی برنامه گاوس سایدل در C

اگر این مطلب برایتان مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

سید سراج حمیدی (+)

سید سراج حمیدی دانش‌آموخته مهندسی برق است و به ریاضیات و زبان و ادبیات فارسی علاقه دارد. او آموزش‌های مهندسی برق، ریاضیات و ادبیات مجله فرادرس را می‌نویسد.

بر اساس رای 7 نفر

آیا این مطلب برای شما مفید بود؟

یک نظر ثبت شده در “روش گوس سایدل — از صفر تا صد

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *