روش گاوس-سایدل

Gauss-Seidel Method
روش گوس سایدل - Gauss-Seidel Method
معرفی

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

روش گوس-سایدل رایج ترین روش تکراری مورد استفاده برای حل دستگاه معادلات خطی است. فرض کنید یک دستگاه معادلات خطی شامل n معادله به شکل زیر داریم:

delim{[}{A}{]}delim{lbrace}{X}{rbrace}=delim{lbrace}{B}{rbrace}

در اینجا به عنوان مثال یک دستگاه معادلات 3*3 را در نظر می گیریم. اگر تمامی اعضای قطری ماتریس delim{[}{A}{]} غیرصفر باشند، معادله ی اول را می توان برای بدست آوردن x_1، معادله ی دوم را برای x_2 و معادله ی سوم را برای x_3 حل نمود:

x_1={b_1 - a_{12}x_{2} - a_{13}x_{3}}/a_{11}

x_2={b_2 - a_{21}x_{1} - a_{23}x_{3}}/a_{22}

x_3={b_3 - a_{31}x_{1} - a_{32}x_{2}}/a_{33}

اکنون فرایند حل را با حدس یک پاسخ برای xها شروع می کنیم. یک راه ساده برای بدست آوردن حدس اولیه فرض این است که همه ی مولفه های پاسخ صفر می باشند. این صفرها را می توان در معادله ی اول (رابطه ی x_1) جایگذاری نمود که می توان از آن برای محاسبه ی مقدار جدید x_1=b_1/a_11 استفاده نمود. سپس این مقدار جدید x_1 را با فرض قبلی x_3=0 در معادله ی دوم (رابطه ی x_2) قرار می دهیم تا مقدار جدیدی برای x_2 بدست آوریم. این فرایند را برای رابطه ی سوم نیز تکرار می کنیم تا مقدار جدیدی برای x_3 بدست بیاوریم. سپس به معادله ی اول باز می گردیم و این روند را تکرار می کنیم تا پاسخ ها همگرا شوند. به طور کلی برای یک دستگاه n*n می توانیم مقدار مولفه های {x_i} ^{(k)} را برای i = 1,2,...,n  و در تکرار kام با استفاده از رابطه ی زیر بدست آوریم:

{x_i} ^{(k)} = {b_i -sum{j=1}{i-1}{a_ij {x_j} ^{(k)}} - sum{j=i+1}{n}{a_ij {x_j} ^{(k-1)}}}/{a_ii}

به منظور نوشتن روش گوس-سایدل به شکل ماتریسی، دوطرف رابطه ی بالا را در a_ii ضرب می کنیم و سپس تمامی جملات تکرار kام را باهم جمع می کنیم:

a_i1 {x_1} ^{(k)} + a_i2 {x_2} ^{(k)} + ... + a_ii {x_i} ^{(k)} =  - a_{i,i+1} {x_{i+1}} ^{(k-1)}- ... - a_{in} {x_{n}} ^{(k-1)}

که اگر این کار را برای i = 1,2,...,n انجام دهیم خواهیم داشت:

a_11 {x_1} ^{(k)} = -a_12 {x_2} ^{(k-1)}-a_13 {x_3} ^{(k-1)}-...-a_1n {x_n} ^{(k-1)} + b_1

a_21 {x_1} ^{(k)} + a_22 {x_2} ^{(k)} = -a_23 {x_3} ^{(k-1)}-...-a_2n {x_n} ^{(k-1)} + b_2

vdots

a_n1 {x_1} ^{(k)} + a_n2 {x_2} ^{(k)} + ... + a_nn {x_n} ^{(k)} = b_n

اکنون با در نظر گرفتن ماتریس ضرایب delim{[}{A}{]} به صورت:

delim{[}{matrix{4}{4}{a_{11} a_{12} cdots a_{1n} a_{21} a_{22} cdots a_{2n} vdots vdots ~ vdots a_{n1} a_{n2} cdots a_{nn}}}{]}

این ماتریس را به ماتریس های قطری و غیر قطری D, L, U می شکنیم:

A = delim{[}{matrix{4}{4}{a_{11} 0 0 0 0 a_{22} 0 0 ~ ~ ddots ~ 0 0 0 a_{nn}}}{]} - delim{[}{matrix{4}{4}{0 0 0 0 {-a_{21}} 0 0 0 {~} {~} ddots {~} {-a_{n1}} cdots {-a_{n,n-1}} 0}}{]} - delim{[}{matrix{4}{4}{0 {-a_{12}} ~ {-a_{1n}} ~ ~ ddots ~ ~ ~ ~ {-a_{n-1,n}} 0 ~ ~ 0}}{]}

~~ = D - L - U

که در آن D بخش قطری ماتریس delim{[}{A}{]} و ماتریس های -L و -U به ترتیب بخش های پایین مثلثی و بالا مثلثی ماتریس delim{[}{A}{]} می باشند. با توجه به تعریف D,L,U اکنون می توانیم دستگاه معادلات n*n را به صورت ماتریسی زیر بازنویسی کنیم:

(D-L)x^{(k)} = Ux^{(k)} + b

یا به عبارتی اگر (D-L)^{-1} وجود داشته باشد داریم:

x^{(k)} = {T_g}x^{(k-1)} + c_g

که در آن

{T_g} = {(D-L)^{-1}}U

{c_g} = {(D-L)^{-1}}b

اکنون با استفاده از این رابطه و یک حدس اولیه x^{(0)} می توانیم x^{(1)} را محاسبه نماییم. سپس با قرار دادن x^{(1)} به جای x^{(k-1)} مقدار پاسخ در تکرارهای بعدی را محاسبه نماییم تا پاسخ ها با دقت مورد نظر ما همگرا گردند.

    برنامه نویسی با MATLAB

    در اینجا با استفاده از نرم افزار متلب (MATLAB) برنامه ای جهت حل دستگاه معادلات خطی n در n به روش گاوس سایدل که یک روش تقریبی عددی است ارائه گردیده است. دو کد برای این منظور در یک فایل فشرده ارائه گردیده است:

    1. کد صریح (explicit) که در خروجی روند حل کامل مسئله را نمایش می دهد

    2. کد غیرصریح (معمولی) که تنها پاسخ نهایی را نمایش می دهد

    لازم به ذکر است که برنامه ی ارائه شده قادر به حل تمامی مثال های قابل حل با روش گاوس سایدل بوده و به صورت کاملا عمومی (general) کدنویسی شده است.

    ورودی ها و خروجی ها

    ورودی:

    1. ماتریس ضرایب A در دستگاه Ax=b
    2. بردار ثابت b در دستگاه Ax=b به شکل [b1 ;b2 ;…;bn]
    3. بردار حدس اولیه برای پاسخ به شکل [p1 ;p2 ;…;pn]
    4. تعداد تکرار

    خروجی:

    1. محاسبه ماتریس های D، L و U
    2. محاسبه ماتریس های Tg و Cg
    3. محاسبه ی بردار پاسخ x در تکرار های مختلف

    تصاویر اجرای برنامه

    مشاهده ی ورودی و خروجی برنامه در یک مثال نمونه - صفحه 1

    مشاهده ی ورودی و خروجی برنامه در یک مثال نمونه - صفحه 2

    مشاهده ی ورودی و خروجی برنامه ی غیر صریح در یک مثال

    این برنامه با نسخه های متلب/MATLAB سال های 2010-2013 تست شده است. در صورت استفاده از نسخه ی سال های دیگر لایبریکا تضمین کننده ی اجرای صحیح برنامه نمی باشد.