روش SOR یا آرامش متوالی

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

روش SOR (Successive Over-Relaxation) روشی مشابه روش گاوس-سایدل برای حل دستگاه معادلات خطی است، با این تفاوت که در این روش از ضریب بزرگنمایی (Scaling factor) برای افزاییش سرعت همگرایی پاسخ استفاده می گردد. این روش در مقایسه با روش های کلاسیک گاوس-سایدل و ژاکوبی یک روش نوین محسوب می گردد.

در این روش مقدار تقریبی بردار پاسخ {x}^{(k)} با استفاده از فرمول زیر محاسبه می گردد:

{x_i}^{(k)} = (1-omega){x_i}^{(k-1)} + omega/a_{ii} delim{[}{b_i - sum{j=1}{i-1}{a_{ij} {x_j}^{(k)}} - sum{j=i+1}{n}{a_{ij} {x_j}^{(k-1)}}}{]}

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

برای بازنویسی فرمول روش SOR به صورت ماتریسی، با در نظر گرفتن ماتریس ضرایب 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 در روش SOR را به صورت ماتریسی زیر بازنویسی کنیم:

(D-omega L)x^{(k)} = delim{[}{(1-omega)D + omega U}{]}x^{(k-1)} + omega b

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

x^{(k)} = {T_omega}x^{(k-1)} + c_omega

که در آن

{T_omega} = {(D-omega L)^{-1}}delim{[}{(1-omega)D + omega U}{]}

{c_omega} = omega {(D-omega L)^{-1}}b

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

همچنین ذکر این نکته لازم است که در صورتی که ماتریس ضرایب delim{[}{A}{]} یک ماتریس مثبت معین/قطعی (positive definite) باشد، روش SOR ذر صورتی که مقدار omega بین 0 و 2 باشد به ازای هر حدس اولیه ی x^{(0)} همگرا می شود. بنابراین در کد ارائه شده در اینجا ابتدا مثبت معین بودن ماتریس بررسی می شود و سپس مقدار omega از کاربر دریافت می گردد.

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

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

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

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

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

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

    ورودی:

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

    خروجی:

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

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

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

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

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

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