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

۹۷۷۱ بازدید
آخرین به‌روزرسانی: ۱۳ اردیبهشت ۱۴۰۲
زمان مطالعه: ۲۶ دقیقه
دانلود PDF مقاله
روش گوس سایدل – از صفر تا صدروش گوس سایدل – از صفر تا صد

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

997696

روش گوس سایدل

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

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

E(1):a11x1+a12x2++a1nxn=b1E(2):a21x1+a22x2++a2nxn=b2E(n):an1x1+an2x2++annxn=bn\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}

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

x1=b1[a12x2+a13x3+...+a1nxn]a11x2=b2[a21x1+a23x3+...+a2nxn]a22xn=bn[an1x1+an2x2+...+an,n1xn1]ann\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^{(1)} برای جواب دقیق xx را با استفاده از روش تکرار گوس سایدل به دست می‌آوریم. بنابراین، x1(1)x_1^{(1)} را با قرار دادن مقادیر جواب اولیه تقریب x(0)x^{(0)} در معادله اول محاسبه می‌کنیم. سپس تقریب x2(1)x_2^{(1)} را با کمک مقادیر اولیه و x1(1)x_1^{(1)} محاسبه شده به دست می‌آوریم. به همین صورت، مقادیر جدید را در معادلات جایگذاری کرده و تکرار را ادامه می‌دهیم:

x1(1)=b1[a12x2(0)+a13x3(0)+a14x4(0)+...+a1nxn(0)]a11x2(1)=b2[a21x1(1)+a23x3(0)+a24x4(0)+...+a2nxn(0)]a22x3(1)=b3[a31x1(1)+a32x2(1)+a34x4(0)+...+a3nxn(0)]a33xn(1)=bn[an1x1(1)+an2x2(1)+an3x3(1)+...+an,n1xn1(1)]ann\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,...,ni = 1, 2, ..., n خواهیم داشت:

xi(1)=bi[j=1i1aijxj(1)+j=i+1naijxj(0)]aii\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^{(2)} از xx با استفاده از روش گوس سایدل داریم:

x1(2)=b1[a12x2(1)+a13x3(1)+a14x4(1)+...+a1nxn(1)]a11x2(2)=b2[a21x1(2)+a23x3(1)+a24x4(1)+...+a2nxn(1)]a22x3(2)=b3[a31x1(2)+a32x2(2)+a34x4(1)+...+a3nxn(1)]a33xn(2)=bn[an1x1(2)+an2x2(2)+an3x3(2)+...+an,n1xn1(2)]ann\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,...,ni = 1, 2, ..., n خواهیم داشت:

xi(2)=bi[j=1i1aijxj(2)+j=i+1naijxj(1)]aii\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}

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

x1(k)=b1[a12x2(k1)+a13x3(k1)+a14x4(k1)+...+a1nxn(k1)]a11x2(k)=b2[a21x1(k)+a23x3(k1)+a24x4(k1)+...+a2nxn(k1)]a22x3(k)=b3[a31x1(k)+a32x2(k)+a34x4(k1)+...+a3nxn(k1)]a33xn(k)=bn[an1x1(k)+an2x2(k)+an3x3(k)+...+an,n1xn1(k)]ann\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,...,ni = 1, 2, ..., n خواهیم داشت:

xi(k)=bi[j=1i1aijxj(k)+j=i+1naijxj(k1)]aii\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}

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

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

Ax=b\large A \mathbf x = \mathbf b

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

Lx(k+1)=bUx(k)\large L _ * \mathbf { x } ^ { ( k + 1 ) } = \mathbf { b } - U \mathbf { x } ^ { ( k ) }

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

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

A=[a11a12a1na21a22a2nan1an2ann],x=[x1x2xn],b=[b1b2bn].\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} .

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

A=L+U  ,L=[a1100a21a220an1an2ann],U=[0a12a1n00a2n000].\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} .

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

Lx=bUx\large L _ * \mathbf { x } = \mathbf { b } - U \mathbf { x }

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

x(k+1)=L1(bUx(k)).\large \mathbf { x } ^ { ( k + 1) } = L _ * ^ { - 1 } ( \mathbf { b } - U \mathbf { x } ^ { ( k ) } ) .

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

xi(k+1)=1aii(bij=1i1aijxj(k+1)j=i+1naijxj(k)),i=1,2,,n.\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 .

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

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

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

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

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

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

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

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

مثال ۱

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

A=[163711]  ,        b=[1113].\large A = \begin {bmatrix} 16 & 3 \\ 7 & - 1 1 \\ \end {bmatrix} \; , \; \; \; \; b = \begin {bmatrix} 1 1 \\ 1 3 \end {bmatrix} .

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

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

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

باید ماتریس AA را به صورت مجموع ماتریس پایین‌مثلثی LL _ * و ماتریس اکیداً بالامثلثی UU بنویسم:

L=[160711]    ,        U=[0300].\large L _ * = \begin {bmatrix} 1 6 & 0 \\ 7 & - 1 1 \\ \end {bmatrix} \;\; , \; \; \; \; U = \begin {bmatrix} 0 & 3 \\ 0 & 0 \end {bmatrix} .

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

L1=[160711]1=[0.06250.00000.03980.0909]\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}

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

T=[0.06250.00000.03980.0909]×[0300]=[0.0000.18750.0000.1194],\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} ,

C=[0.06250.00000.03980.0909]×[1113]=[0.68750.7439].\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} .

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

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

x(0)=[1.01.0].\large x ^ { ( 0 ) } = \begin {bmatrix} 1 . 0 \\ 1 . 0 \end {bmatrix} .

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

x(1)=[0.0000.18750.0000.1193]×[1.01.0]+[0.68750.7443]=[0.50000.8636].x(2)=[0.0000.18750.0000.1193]×[0.50000.8636]+[0.68750.7443]=[0.84940.6413].x(3)=[0.0000.18750.0000.1193]×[0.84940.6413]+[0.68750.7443]=[0.80770.6678].x(4)=[0.0000.18750.0000.1193]×[0.80770.6678]+[0.68750.7443]=[0.81270.6646].x(5)=[0.0000.18750.0000.1193]×[0.81270.6646]+[0.68750.7443]=[0.81210.6650].x(6)=[0.0000.18750.0000.1193]×[0.81210.6650]+[0.68750.7443]=[0.81220.6650].x(7)=[0.0000.18750.0000.1193]×[0.81220.6650]+[0.68750.7443]=[0.81220.6650].\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*}

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

x=A1b[0.81220.6650].\large \mathbf { x } = A ^ { - 1 } \mathbf { b } \approx \begin {bmatrix} 0 . 8 1 2 2 \\ - 0 . 6 6 5 0 \end {bmatrix} .

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

مثال ۲

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

A=[2357]  ,      b=[1113].\large A = \begin {bmatrix} 2 & 3 \\ 5 & 7 \\ \end {bmatrix} \; , \; \; \; b = \begin {bmatrix} 1 1 \\ 1 3 \\ \end {bmatrix} .

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

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

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

باید ماتریس AA را به صورت مجموع ماتریس پایین‌مثلثی LL _ * و ماتریس اکیداً بالامثلثی UU بنویسم:

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

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

L1=[2057]1=[0.5000.0000.3570.143].\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} .

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

T=[0.5000.0000.3570.143]×[0300]=[0.0001.5000.0001.071],C=[0.5000.0000.3570.143]×[1113]=[5.5002.071].\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*}

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

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

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

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

x(1)=[01.50001.071]×[1.12.3]+[5.5002.071]=[2.0500.393].x(2)=[01.50001.071]×[2.0500.393]+[5.5002.071]=[4.9111.651].x(3)=.\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*}

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

x=A1b=[3829]\large \mathbf { x } = A ^ { - 1 } \mathbf { b } = \begin {bmatrix} - 3 8 \\ 2 9 \end {bmatrix}

مثال ۳

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

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

10x1x2+2x3=6,x1+11x2x3+3x4=25,2x1x2+10x3x4=11,3x2x3+8x4=15.\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}

مجهولات x1x _ 1، x2x _ 2، x3x _ 3 و x4x _ 4 به صورت زیر نوشته می‌شوند:

x1=x2/10x3/5+3/5,x2=x1/11+x3/113x4/11+25/11,x3=x1/5+x2/10+x4/1011/10,x4=3x2/8+x3/8+15/8.\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)( 0, 0 , 0 , 0 ) در نظر می‌گیریم و بر این اساس، جواب تقریبی نخست را به صورت زیر محاسبه می‌کنیم:

x1=3/5=0.6,x2=(3/5)/11+25/11=3/55+25/11=2.3272,x3=(3/5)/5+(2.3272)/1011/10=3/25+0.232721.1=0.9873,x4=3(2.3272)/8+(0.9873)/8+15/8=0.8789.\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}

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

x1x2x3x40.62.327270.9872730.8788641.030182.036941.014460.9843411.006592.003561.002530.9983511.000862.00031.000310.99985\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)( 1 , 2 , - 1 , 1 ) است.

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

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

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

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

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

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

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]

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

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

xi(k+1)=1aii(bij<iaijxj(k+1)j>iaijxj(k)),i,j=1,2,,n\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

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

^^

بر اساس رای ۱۸ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
WikipediaMathonline
دانلود PDF مقاله
۳ دیدگاه برای «روش گوس سایدل – از صفر تا صد»

سلام آقای حمیدی وقتتون بخیر امیدوارم حالتون خوب باشه و خدا قوت برای تلاشتون
یک سوال این وسط پیش میاد اگر ما یک ماتریس n×n قطری غالب و مثبت معین داشته باشیم برای n بالای 2000 برای همگرا شدن به جواب ممکنه چند تکرار صورت بگیره
میدونم بستگی به ارور مشخص شده داره ولی ممکنه این تو متلب چقدر طول بکشه ؟
بازم ممنون

به اون آقایی که واسه ژاکوبی تو متلب با مثال رو‌فیلم توضیح میداد بگین واسه گوس سایدل تو متلب هم همینطوری توضیح بدن ممنون☹️?

خیلی عالی و مفید. خسته نباشید.

نظر شما چیست؟

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