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

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

کلیک کنید

1import numpy as np
2
3ITERATION_LIMIT = 1000
4
5# initialize the matrix
6A = np.array([[10., -1., 2., 0.],
7              [-1., 11., -1., 3.],
8              [2., -1., 10., -1.],
9              [0., 3., -1., 8.]])
10# initialize the RHS vector
11b = np.array([6., 25., -11., 15.])
12
13print("System of equations:")
14for i in range(A.shape[0]):
15    row = ["{0:3g}*x{1}".format(A[i, j], j + 1) for j in range(A.shape[1])]
16    print("[{0}] = [{1:3g}]".format(" + ".join(row), b[i]))
17
18x = np.zeros_like(b)
19for it_count in range(1, ITERATION_LIMIT):
20    x_new = np.zeros_like(x)
21    print("Iteration {0}: {1}".format(it_count, x))
22    for i in range(A.shape[0]):
23        s1 = np.dot(A[i, :i], x_new[:i])
24        s2 = np.dot(A[i, i + 1:], x[i + 1:])
25        x_new[i] = (b[i] - s1 - s2) / A[i, i]
26    if np.allclose(x, x_new, rtol=1e-8):
27        break
28    x = x_new
29
30print("Solution: {0}".format(x))
31error = np.dot(A, x) - b
32print("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 $$

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

1function x = gauss_seidel(A, b, x, iters)
2    for i = 1:iters
3        for j = 1:size(A,1)
4            x(j) = (1/A(j,j)) * (b(j) - A(j,:)*x + A(j,j)*x(j));
5        end
6    end
7end

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

1% Gauss-Seidel Method in MATLAB
2function x = gauss_siedel( A ,B )
3disp ( 'Enter the system of linear equations in the form of AX=B')
4
5%Inputting matrix A
6A = input ( 'Enter matrix A :   \n')
7% check if the entered matrix is a square matrix
8[na , ma ] = size (A);
9if na ~= ma
10    disp('ERROR: Matrix A must be a square matrix')
11    return
12end
13
14% Inputting matrix B
15B = input ( 'Enter matrix B :   ')
16% check if B is a column matrix
17[nb , mb ] = size (B);
18if nb ~= na || mb~=1
19   disp( 'ERROR: Matrix B must be a column matrix')
20   return
21end
22
23% Separation of matrix A into lower triangular and upper triangular matrices
24% A = D + L + U
25D = diag(diag(A));
26L = tril(A)- D;
27U = triu(A)- D
28
29% check for convergence condition for Gauss-Seidel method
30e= max(eig(-inv(D+L)*(U)));
31if abs(e) >= 1
32    disp ('Since the modulus of the largest Eigen value of iterative matrix is not less than 1') 
33    disp ('this process is not convergent.')
34    return
35end
36
37% initial guess for X..?
38% default guess is [ 1 1 .... 1]
39r = input ( 'Any initial guess for X? (y/n):   ','s');
40switch r 
41    case 'y'
42        % asking for initial guess
43    X0 = input('Enter initial guess for X :\n')
44        % check for initial guess
45    [nx, mx] = size(X0);
46        if nx ~= na || mx ~= 1
47        disp( 'ERROR: Check input')
48        return
49    end
50    otherwise
51    X0 = ones(na,1);
52end
53
54% allowable error in final answer
55t = input ( 'Enter the error allowed in final answer:  ');
56tol = t*ones(na,1);
57k= 1;
58
59X( : , 1 ) = X0;
60err= 1000000000*rand(na,1);% initial error assumption for looping
61while sum(abs(err) >= tol) ~= zeros(na,1)
62    X ( : ,k+ 1 ) = -inv(D+L)*(U)*X( : ,k) + inv(D+L)*B;% Gauss-Seidel formula
63    err = X( :,k+1) - X( :, k);% finding error
64    k = k + 1;
65    
66end
67
68fprintf ('The final answer obtained after %g iterations is  \n', k)
69X( : ,k)

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

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

1#include<stdio.h>
2#include<math.h>
3#define X 2
4main()
5{
6    float x[X][X+1],a[X], ae, max,t,s,e;
7    int i,j,r,mxit;
8    for(i=0;i<X;i++) a[i]=0;
9    puts(" Eneter the elemrnts of augmented matrix rowwise\n");
10    for(i=0;i<X;i++)
11    {
12    for(j=0;j<X+1;j++)
13    {
14    scanf("%f",&x[i][j]);
15    }
16    }
17    printf(" Eneter the allowed error and maximum number of iteration: ");
18    scanf("%f%d",&ae,&mxit);
19    printf("Iteration\tx[1]\tx[2]\n");
20    for(r=1;r<=mxit;r++)
21    {
22        max=0;
23        for(i=0;i<X;i++)
24        {
25            s=0;
26            for(j=0;j<X;j++)
27            if(j!=i) s+=x[i][j]*a[j];
28            t=(x[i][X]-s)/x[i][i];
29            e=fabs(a[i]-t);
30            a[i]=t;
31        }
32        printf(" %5d\t",r);
33        for(i=0;i<X;i++)
34        printf(" %9.4f\t",a[i]);
35        printf("\n");
36        if(max<ae)
37        {
38            printf(" Converses in %3d iteration\n", r);
39            for(i=0;i<X;i++)
40            printf("a[%3d]=%7.4f\n", i+1,a[i]);
41            return 0;
42        }
43
44        }
45    }

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

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

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

^^