روش گوس سایدل — از صفر تا صد

در آموزش‌های قبلی مجله فرادرس، با روش ژاکوبی برای حل دستگاه معادلات خطی به فرم $$ 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$$ یک ماتریس مثبت معین متقارن باشد، یا
• $$ A$$ اکیداً غالب قطری باشد.

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

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

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

فیلم آموزش محاسبات عددی در پایتون Python

اینجا کلیک کنید

مثال ۱

دستگاه خطی $$ 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 ) $$ است.

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

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

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

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

فیلم آموزش محاسبات عددی در پایتون Python

اینجا کلیک کنید

import numpy as np

ITERATION_LIMIT = 1000

# initialize the matrix
A = np.array([[10., -1., 2., 0.],
              [-1., 11., -1., 3.],
              [2., -1., 10., -1.],
              [0., 3., -1., 8.]])
# initialize the RHS vector
b = np.array([6., 25., -11., 15.])

print("System of equations:")
for i in range(A.shape[0]):
    row = ["{0:3g}*x{1}".format(A[i, j], j + 1) for j in range(A.shape[1])]
    print("[{0}] = [{1:3g}]".format(" + ".join(row), b[i]))

x = np.zeros_like(b)
for it_count in range(1, ITERATION_LIMIT):
    x_new = np.zeros_like(x)
    print("Iteration {0}: {1}".format(it_count, x))
    for i in range(A.shape[0]):
        s1 = np.dot(A[i, :i], x_new[:i])
        s2 = np.dot(A[i, i + 1:], x[i + 1:])
        x_new[i] = (b[i] - s1 - s2) / A[i, i]
    if np.allclose(x, x_new, rtol=1e-8):
        break
    x = x_new

print("Solution: {0}".format(x))
error = np.dot(A, x) - b
print("Error: {0}".format(error))

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

System of equations:
[ 10*x1 +  -1*x2 +   2*x3 +   0*x4] = [  6]
[ -1*x1 +  11*x2 +  -1*x3 +   3*x4] = [ 25]
[  2*x1 +  -1*x2 +  10*x3 +  -1*x4] = [-11]
[  0*x1 +   3*x2 +  -1*x3 +   8*x4] = [ 15]
Iteration 1: [ 0.  0.  0.  0.]
Iteration 2: [ 0.6         2.32727273 -0.98727273  0.87886364]
Iteration 3: [ 1.03018182  2.03693802 -1.0144562   0.98434122]
Iteration 4: [ 1.00658504  2.00355502 -1.00252738  0.99835095]
Iteration 5: [ 1.00086098  2.00029825 -1.00030728  0.99984975]
Iteration 6: [ 1.00009128  2.00002134 -1.00003115  0.9999881 ]
Iteration 7: [ 1.00000836  2.00000117 -1.00000275  0.99999922]
Iteration 8: [ 1.00000067  2.00000002 -1.00000021  0.99999996]
Iteration 9: [ 1.00000004  1.99999999 -1.00000001  1.        ]
Iteration 10: [ 1.  2. -1.  1.]
Solution: [ 1.  2. -1.  1.]
Error: [  2.06480930e-08  -1.25551054e-08   3.61417563e-11   0.00000000e+00]

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

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

$$ \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 $$

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

function x = gauss_seidel(A, b, x, iters)
    for i = 1:iters
        for j = 1:size(A,1)
            x(j) = (1/A(j,j)) * (b(j) - A(j,:)*x + A(j,j)*x(j));
        end
    end
end

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

% Gauss-Seidel Method in MATLAB
function x = gauss_siedel( A ,B )
disp ( 'Enter the system of linear equations in the form of AX=B')

%Inputting matrix A
A = input ( 'Enter matrix A :   \n')
% check if the entered matrix is a square matrix
[na , ma ] = size (A);
if na ~= ma
    disp('ERROR: Matrix A must be a square matrix')
    return
end

% Inputting matrix B
B = input ( 'Enter matrix B :   ')
% check if B is a column matrix
[nb , mb ] = size (B);
if nb ~= na || mb~=1
   disp( 'ERROR: Matrix B must be a column matrix')
   return
end

% Separation of matrix A into lower triangular and upper triangular matrices
% A = D + L + U
D = diag(diag(A));
L = tril(A)- D;
U = triu(A)- D

% check for convergence condition for Gauss-Seidel method
e= max(eig(-inv(D+L)*(U)));
if abs(e) >= 1
    disp ('Since the modulus of the largest Eigen value of iterative matrix is not less than 1') 
    disp ('this process is not convergent.')
    return
end

% initial guess for X..?
% default guess is [ 1 1 .... 1]
r = input ( 'Any initial guess for X? (y/n):   ','s');
switch r 
    case 'y'
        % asking for initial guess
    X0 = input('Enter initial guess for X :\n')
        % check for initial guess
    [nx, mx] = size(X0);
        if nx ~= na || mx ~= 1
        disp( 'ERROR: Check input')
        return
    end
    otherwise
    X0 = ones(na,1);
end

% allowable error in final answer
t = input ( 'Enter the error allowed in final answer:  ');
tol = t*ones(na,1);
k= 1;

X( : , 1 ) = X0;
err= 1000000000*rand(na,1);% initial error assumption for looping
while sum(abs(err) >= tol) ~= zeros(na,1)
    X ( : ,k+ 1 ) = -inv(D+L)*(U)*X( : ,k) + inv(D+L)*B;% Gauss-Seidel formula
    err = X( :,k+1) - X( :, k);% finding error
    k = k + 1;
    
end

fprintf ('The final answer obtained after %g iterations is  \n', k)
X( : ,k)

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

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

#include<stdio.h>
#include<math.h>
#define X 2
main()
{
    float x[X][X+1],a[X], ae, max,t,s,e;
    int i,j,r,mxit;
    for(i=0;i<X;i++) a[i]=0;
    puts(" Eneter the elemrnts of augmented matrix rowwise\n");
    for(i=0;i<X;i++)
    {
    for(j=0;j<X+1;j++)
    {
    scanf("%f",&x[i][j]);
    }
    }
    printf(" Eneter the allowed error and maximum number of iteration: ");
    scanf("%f%d",&ae,&mxit);
    printf("Iteration\tx[1]\tx[2]\n");
    for(r=1;r<=mxit;r++)
    {
        max=0;
        for(i=0;i<X;i++)
        {
            s=0;
            for(j=0;j<X;j++)
            if(j!=i) s+=x[i][j]*a[j];
            t=(x[i][X]-s)/x[i][i];
            e=fabs(a[i]-t);
            a[i]=t;
        }
        printf(" %5d\t",r);
        for(i=0;i<X;i++)
        printf(" %9.4f\t",a[i]);
        printf("\n");
        if(max<ae)
        {
            printf(" Converses in %3d iteration\n", r);
            for(i=0;i<X;i++)
            printf("a[%3d]=%7.4f\n", i+1,a[i]);
            return 0;
        }

        }
    }

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

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

• مجموعه آموزش‌های محاسبات عددی
• آموزش محاسبات عددی با MATLAB
• مجموعه آموزش‌های دروس ریاضیات
• آموزش ریاضی پایه دانشگاهی
• روش نیوتن — به زبان ساده
• روش وتری — به زبان ساده
• روش کرامر — از صفر تا صد

^^