روش حذفی گاوس

Naive Gaussian Elimination
حل دستگاه معادلات خطی به روش مستقیم
معرفی

اگر در زمینه ی جبر خطی و یا تئوری ماتریس ها مطالعه کرده باشید احتمالا قبلا با روش حذفی گاوس (Gaussian Elimination یا Naive Gaussian Elimination) آشنا شده اید. روش حذفی گوس مهم ترین و مقدماتی ترین روش برای تعیین سیستماتیک پاسخ یک دستگاه معادلات خطی است. در این روش متغیرهای معادلات حذف می شوند تا به یک معادله با تنها یک متغیر مجهول برسیم. معادله ی دوم شامل آن متغیر و متغیری دیگر خواهد بود و معادله ی سوم شامل دو متغیر قبل بعلاوه ی متغیری دیگر خواهد بود و به این ترتیب ادامه می یابد. حل دستگاه با یافتن پاسخ اولین معادله با یک متغیر مجهول آغاز می شود و سپس سایر مقادیر مجهول به ترتیب با استفاده از پاسخ معادله ی قبل محاسبه می گردند.

اگر E_i معادله ی i ام از دستگاه معادلات n*n باشد، برای انجام فرآیند روش حذفی گاوس از سه عملیات استفاده می گردد:

1. می توان یک معادله را در یک عدد ثابت غیر صفر m ضرب نمود (mE_i)right(E_i)

2. می توان یک معادله را در یک عدد ثابت غیر صفر m ضرب و با معادله ای دیگر جمع نمود (E_i + mE_j)right(E_i)

3. می توان دو معادله را با یکدیگر جابجا کرد (E_j)leftright(E_i)

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

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

E_1:~ a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n = b_1

E_2:~ a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n = b_2

vdots

E_n:~ a_{n1}x_1 + a_{n2}x_2 + ... + a_{nn}x_n = b_n

ابتدا ماتریس افزوده ی A را با اضافه کردن بردار ثوابت (طرف راست تساوی دستگاه معادلات) به ستون انتهایی ماتریس ضرایب دستگاه معادلات به شکل زیر تشکیل می دهیم:

delim{[}{A}{]} = delim{[}{matrix{4}{5}{a_{11} a_{12} cdots a_{1n} b_1 a_{21} a_{22} cdots a_{2n} b_2 vdots vdots ~ vdots vdots a_{n1} a_{n2} cdots a_{nn} b_n}}{]}

فرض کنیم a_{11} غیر صفر باشد. برای صفر نمودن درایه های ماتریس در ستون اول که در زیر a_{11} قرار دارند، عملیاتی به صورت (E_k - m_{k1}E_1)right(E_k) برای هر k = 2,3,...,n با محاسبه ی ضریب مناسب m_{k1} انجام می دهیم. به این ترتیب متغیر مجهول x_1 بغیر از معادله ی اول در سایر معادلات حذف می گردد. به درایه ی قطری ماتریس A که برای حذف سایر درایه های پایین تر از آن در همان ستون استفاده گردید، a_{11}، درایه یا المان لولا می گویند. همچنین ضریب m_{k1} در سطر k ام به صورت m_{k1}=a_{k1}/a_{11} محاسبه می گردد.

با انجام عملیات (E_k - m_{k1}E_1)right(E_k) برای هر k = 2,3,...,n ضرایب x_1 در تمامی معادلات بغیر از معادله ی اول حذف (یا به صفر تبدیل) می گردد:

delim{[}{A}{]} = delim{[}{matrix{4}{5}{a_{11} a_{12} cdots a_{1n} b_1 0 a_{22} cdots a_{2n} b_2 vdots vdots ~ vdots vdots 0 a_{n2} cdots a_{nn} b_n}}{]}

در گام بعد با در نظر گرفتن معادله ی دوم و قرار دادن درایه ی غیر صفر a_{22}  به عنوان المان لولا، به حذف متغیر x_2 در معادلات سوم، چهارم و … می پردازیم. برای این منظور عملیات (E_k - m_{k2}E_2)right(E_k) را برای هر k = 3,...,n انجام می دهیم و ضرایب m_{k2} را به صورت m_{k2}=a_{k2}/a_{22} محاسبه می نماییم:

delim{[}{A}{]} = delim{[}{matrix{4}{5}{a_{11} a_{12} cdots a_{1n} b_1 0 a_{22} cdots a_{2n} b_2 vdots vdots ~ vdots vdots 0 0 cdots a_{nn} b_n}}{]}

همین فرآیند را تا معادله ی n-1 ادامه می دهیم تا در معادله ی n ام تنها یک متغیر باقی بماند و با محاسبه ی مقدار آن و جایگزینی مقدار آن در معادله ی قبلی و تکرار این فرآیند مقدار سایر متغیرهای مجهول را به ترتیب محاسبه می نماییم. به این فرآیند یافتن متغیرهای مجهول جایگذاری بازگشتی (backward substitution) می گویند که فرمولاسیون آن را برای سطر i ام می توان به صورت زیر بیان نمود:

x_i={a_{i,n+1} - (a_{i,i+1}x_{i+1} + a_{i,i+2}x_{i+2} + ... + a_{i,n}x_{n})}/{a_{ii}}

که در آن i = n-1, n-2, ..., 2,1.

ذکر این نکته لازم است که در صورتی که المان لولا a_{ii} در یکی از سطرها صفر باشد می توانیم سطر را با اولین سطری که المان لولای غیر صفر دارد جابجا نماییم یعنی:

(E_i)leftright(E_p)

که در آن p شماره ی اولین سطر بعد از سطر i است که درایه ی a_{pi} در آن غیر صفر است.

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

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

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

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

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

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

    ورودی:

    1. ماتریس ضرایب دستگاه معادلات خطی Ax=b
    2. بردار ثابت b در دستگاه Ax=b به شکل [b1 ;b2 ;…;bn] (ماتریس افزوده ی A که از به هم پیوستن بردار b و ماتریس A ایجاد می گردد در خود برنامه ساخته می شود و نیازی به دادن آن در ورودی نیست)

    خروجی:

    1. نمایش کامل عملیات ها و محاسبات لازم در روند حل روش حذفی گوس
    2. محاسبه و نمایش پاسخ نهایی

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

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

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

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

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