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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

روش گاوس سایدل (به انگلیسی: Gauss–Seidel method) در جبر خطی عددی روش تکراری است که برای حل دستگاه معادلات خطی استفاده می‌شود. نام این روش از روی ریاضی‌دانان آلمانی کارل فریدریش گاوس و فیلیپ لودویگ ون سایدل نهاده شده‌است. اگرچه از این روش می‌توان در هر ماتریسی که دارای درایه قطری صفر نباشد استفاده کرد، اما فقط در صورتی همگرایی تضمین می‌شود که ماتریس مثبت معین و یا غالب قطری باشد.

توضیح[ویرایش]

برای یک سیستم مربعی با n معادله ی خطی و دارای مجهول x داریم:

A\mathbf x = \mathbf b

که در آن:

A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \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 را به ماتریس پایین مثلثی و بالا مثلثی L* و U تجزیه کنیم:

A=L_*+U \qquad \text{where} \qquad L_* = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ a_{21} & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \quad U = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ 0 & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & 0 \end{bmatrix}

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

L_* \mathbf{x} = \mathbf{b} - U \mathbf{x}

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

 \mathbf{x}^{(k+1)} = L_*^{-1} (\mathbf{b} - U \mathbf{x}^{(k)}).

و با استفاده از خواص ماتریس مثلثی L* می‌توان x(k+1) را به صورت زیر به دست آورد:

 x^{(k+1)}_i  = \frac{1}{a_{ii}} \left(b_i - \sum_{j>i}a_{ij}x^{(k)}_j - \sum_{j<i}a_{ij}x^{(k+1)}_j \right),\quad i=1,2,\ldots,n.

در واقع برای محاسبه xi(k+1) به همه عناصر x(k) به جز خود xi(k) نیاز خواهد شد.

محاسبات تا زمانی ادامه داده می‌شود تا در تکراری خاص به خطایی کمتر از مقدار مورد نظر برسیم.

مثال[ویرایش]

برای سیستمی که به شکل A \mathbf{x} = \mathbf{b} نمایش می‌دهیم داریم:

 A=
      \begin{bmatrix}
           16  &   3 \\
            7  & -11 \\
           \end{bmatrix}
و  b=
      \begin{bmatrix}
           11 \\
           13
           \end{bmatrix}.

می‌خواهیم از معادله زیر

 \mathbf{x}^{(k+1)} = L_*^{-1} (\mathbf{b} - U \mathbf{x}^{(k)})

به شکل

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

استفاده کنیم، که در آن:

T = - L_*^{-1} U و C = L_*^{-1} \mathbf{b}.

باید A_{}^{} به جمع دو ماتریس پایین مثلثی و بالا مثلثی L_*^{} و U_{}^{} تجزیه شود:

 L_*=
      \begin{bmatrix}
           16 &   0 \\
           7  & -11 \\
           \end{bmatrix}
و  U =
        \begin{bmatrix}
           0 & 3 \\
           0 & 0
        \end{bmatrix}.

معکوس L_*^{} برابر است با:

 L_*^{-1} =
      \begin{bmatrix}
           16 &   0 \\
           7  & -11
           \end{bmatrix}^{-1}
      =
      \begin{bmatrix}
           0.0625 &  0.0000 \\
           0.0398 & -0.0909 \\
           \end{bmatrix}
.

و حالا می‌توانیم مقدار زیر را پیدا کنیم:

 T = - 
      \begin{bmatrix}
           0.0625 &  0.0000 \\
           0.0398 & -0.0909
      \end{bmatrix}
      \times
      \begin{bmatrix}
           0 & 3 \\
           0 & 0
      \end{bmatrix}  
      =
      \begin{bmatrix}
           0.000 & -0.1875 \\
           0.000 & -0.1193
      \end{bmatrix},
 C = 
      \begin{bmatrix}
           0.0625 &  0.0000 \\
           0.0398 & -0.0909
      \end{bmatrix}
      \times
      \begin{bmatrix}
           11 \\
           13
      \end{bmatrix}  
      =
      \begin{bmatrix}
           0.6875 \\
          -0.7443
      \end{bmatrix}.

و با استفاده از T_{}^{} و C_{}^{} مقدار \mathbf{x} را به صورت تکرار به دست می‌آوریم.

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

 x^{(0)} =
        \begin{bmatrix}
           1.0 \\
           1.0
        \end{bmatrix}.

حال می‌توانیم محاسبه کنیم:

 x^{(1)} = 
      \begin{bmatrix}
           0.000 & -0.1875 \\
           0.000 & -0.1193
      \end{bmatrix}
      \times
      \begin{bmatrix}
           1.0 \\
           1.0
      \end{bmatrix}
      +
      \begin{bmatrix}
           0.6875 \\
          -0.7443
      \end{bmatrix}  
      =
      \begin{bmatrix}
           0.5000 \\
          -0.8636
      \end{bmatrix}.
 x^{(2)} =
      \begin{bmatrix}
           0.000 & -0.1875 \\
           0.000 & -0.1193
      \end{bmatrix}
      \times
      \begin{bmatrix}
           0.5000 \\
          -0.8636
      \end{bmatrix}
      +
      \begin{bmatrix}
           0.6875 \\
          -0.7443
      \end{bmatrix}  
      =
      \begin{bmatrix}
           0.8494 \\
          -0.6413
      \end{bmatrix}.
 x^{(3)} =
      \begin{bmatrix}
           0.000 & -0.1875 \\
           0.000 & -0.1193
      \end{bmatrix}
      \times
      \begin{bmatrix}
           0.8494 \\
          -0.6413 \\
      \end{bmatrix}
      +
      \begin{bmatrix}
           0.6875 \\
          -0.7443
      \end{bmatrix}  
      =
      \begin{bmatrix}
           0.8077 \\
          -0.6678
      \end{bmatrix}.
 x^{(4)} =
      \begin{bmatrix}
           0.000 & -0.1875 \\
           0.000 & -0.1193
      \end{bmatrix}
      \times
      \begin{bmatrix}
           0.8077 \\
          -0.6678
      \end{bmatrix}
      +
      \begin{bmatrix}
           0.6875 \\
          -0.7443
      \end{bmatrix}  
      =
      \begin{bmatrix}
           0.8127 \\
          -0.6646
      \end{bmatrix}.
 x^{(5)} =
      \begin{bmatrix}
           0.000 & -0.1875 \\
           0.000 & -0.1193
      \end{bmatrix}
      \times
      \begin{bmatrix}
           0.8127 \\
          -0.6646
      \end{bmatrix}
      +
      \begin{bmatrix}
           0.6875 \\
          -0.7443
      \end{bmatrix}  
      =
      \begin{bmatrix}
           0.8121 \\
          -0.6650
      \end{bmatrix}.
 x^{(6)} =
      \begin{bmatrix}
           0.000 & -0.1875 \\
           0.000 & -0.1193
      \end{bmatrix}
      \times
      \begin{bmatrix}
           0.8121 \\
          -0.6650
      \end{bmatrix}
      +
      \begin{bmatrix}
           0.6875 \\
          -0.7443
      \end{bmatrix}  
      =
      \begin{bmatrix}
           0.8122 \\
          -0.6650
      \end{bmatrix}.
 x^{(7)} =
      \begin{bmatrix}
           0.000 & -0.1875 \\
           0.000 & -0.1193
      \end{bmatrix}
      \times
      \begin{bmatrix}
           0.8122 \\
          -0.6650
      \end{bmatrix}
      +
      \begin{bmatrix}
           0.6875 \\
          -0.7443
      \end{bmatrix}  
      =
      \begin{bmatrix}
           0.8122 \\
          -0.6650
      \end{bmatrix}.

و همانگونه که انتظار داشتیم به مقدار دقیق همگرا شد:

 \mathbf{x} = A^{-1} \mathbf{b} = \begin{bmatrix} 0.8122\\ -0.6650 \end{bmatrix}.

منابع[ویرایش]

پیوند به بیرون[ویرایش]