از ویکیپدیا، دانشنامهٔ آزاد
روش گاوس سایدل (به انگلیسی : Gauss–Seidel method جبر خطی عددی روش تکراری است که برای حل دستگاه معادلات خطی استفاده میشود. نام این روش از روی ریاضیدانان آلمانی کارل فریدریش گاوس و فیلیپ لودویگ ون سایدل نهاده شدهاست. اگرچه از این روش میتوان در هر ماتریسی که دارای درایه قطری صفر نباشد استفاده کرد، اما فقط در صورتی همگرایی تضمین میشود که ماتریس مثبت معین یا قطریغالب باشد.
برای یک سیستم مربعی با n معادلهٔ خطی و دارای مجهول x داریم:
A
x
=
b
{\displaystyle A\mathbf {x} =\mathbf {b} }
که در آن:
A
=
[
a
11
a
12
⋯
a
1
n
a
21
a
22
⋯
a
2
n
⋮
⋮
⋱
⋮
a
n
1
a
n
2
⋯
a
n
n
]
,
x
=
[
x
1
x
2
⋮
x
n
]
,
b
=
[
b
1
b
2
⋮
b
n
]
.
{\displaystyle 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
where
L
∗
=
[
a
11
0
⋯
0
a
21
a
22
⋯
0
⋮
⋮
⋱
⋮
a
n
1
a
n
2
⋯
a
n
n
]
,
U
=
[
0
a
12
⋯
a
1
n
0
0
⋯
a
2
n
⋮
⋮
⋱
⋮
0
0
⋯
0
]
{\displaystyle 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
∗
x
=
b
−
U
x
{\displaystyle L_{*}\mathbf {x} =\mathbf {b} -U\mathbf {x} }
روش گاوس سایدل از روش تکراری برای حل قسمت چپ عبارت جهت به دست آوردن x بهره میبرد، و بدین منظور از مقدار قبلی x در سمت راست عبارت استفاده میکند. میتوان آن را به صورت زیر نوشت:
x
(
k
+
1
)
=
L
∗
−
1
(
b
−
U
x
(
k
)
)
.
{\displaystyle \mathbf {x} ^{(k+1)}=L_{*}^{-1}(\mathbf {b} -U\mathbf {x} ^{(k)}).}
و با استفاده از خواص ماتریس مثلثی L * میتوان x (k +1) را به صورت زیر به دست آورد:
x
i
(
k
+
1
)
=
1
a
i
i
(
b
i
−
∑
j
>
i
a
i
j
x
j
(
k
)
−
∑
j
<
i
a
i
j
x
j
(
k
+
1
)
)
,
i
=
1
,
2
,
…
,
n
.
{\displaystyle x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j>i}a_{ij}x_{j}^{(k)}-\sum _{j<i}a_{ij}x_{j}^{(k+1)}\right),\quad i=1,2,\ldots ,n.}
در واقع برای محاسبه x i (k +1) به همه عناصر x (k ) به جز خود x i (k ) نیاز خواهد شد.
محاسبات تا زمانی ادامه داده میشود تا در تکراری خاص به خطایی کمتر از مقدار مورد نظر برسیم.
برای سیستمی که به شکل
A
x
=
b
{\displaystyle A\mathbf {x} =\mathbf {b} }
A
=
[
16
3
7
−
11
]
{\displaystyle A={\begin{bmatrix}16&3\\7&-11\\\end{bmatrix}}}
b
=
[
11
13
]
.
{\displaystyle b={\begin{bmatrix}11\\13\end{bmatrix}}.}
میخواهیم از معادله زیر
x
(
k
+
1
)
=
L
∗
−
1
(
b
−
U
x
(
k
)
)
{\displaystyle \mathbf {x} ^{(k+1)}=L_{*}^{-1}(\mathbf {b} -U\mathbf {x} ^{(k)})}
به شکل
x
(
k
+
1
)
=
T
x
(
k
)
+
C
{\displaystyle \mathbf {x} ^{(k+1)}=T\mathbf {x} ^{(k)}+C}
استفاده کنیم، که در آن:
T
=
−
L
∗
−
1
U
{\displaystyle T=-L_{*}^{-1}U}
C
=
L
∗
−
1
b
.
{\displaystyle C=L_{*}^{-1}\mathbf {b} .}
باید
A
{\displaystyle A_{}^{}}
ماتریس پایین مثلثی و بالا مثلثی
L
∗
{\displaystyle L_{*}^{}}
U
{\displaystyle U_{}^{}}
L
∗
=
[
16
0
7
−
11
]
{\displaystyle L_{*}={\begin{bmatrix}16&0\\7&-11\\\end{bmatrix}}}
U
=
[
0
3
0
0
]
.
{\displaystyle U={\begin{bmatrix}0&3\\0&0\end{bmatrix}}.}
معکوس
L
∗
{\displaystyle L_{*}^{}}
L
∗
−
1
=
[
16
0
7
−
11
]
−
1
=
[
0.0625
0.0000
0.0398
−
0.0909
]
{\displaystyle L_{*}^{-1}={\begin{bmatrix}16&0\\7&-11\end{bmatrix}}^{-1}={\begin{bmatrix}0.0625&0.0000\\0.0398&-0.0909\\\end{bmatrix}}}
و حالا میتوانیم مقدار زیر را پیدا کنیم:
T
=
−
[
0.0625
0.0000
0.0398
−
0.0909
]
×
[
0
3
0
0
]
=
[
0.000
−
0.1875
0.000
−
0.1193
]
,
{\displaystyle 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
=
[
0.0625
0.0000
0.0398
−
0.0909
]
×
[
11
13
]
=
[
0.6875
−
0.7443
]
.
{\displaystyle 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
{\displaystyle T_{}^{}}
C
{\displaystyle C_{}^{}}
x
{\displaystyle \mathbf {x} }
باید مقدار اولیه را به صورت حدس انتخاب کنیم، برای همین فرض میکنیم:
x
(
0
)
=
[
1.0
1.0
]
.
{\displaystyle x^{(0)}={\begin{bmatrix}1.0\\1.0\end{bmatrix}}.}
حال میتوانیم محاسبه کنیم:
x
(
1
)
=
[
0.000
−
0.1875
0.000
−
0.1193
]
×
[
1.0
1.0
]
+
[
0.6875
−
0.7443
]
=
[
0.5000
−
0.8636
]
.
{\displaystyle 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
)
=
[
0.000
−
0.1875
0.000
−
0.1193
]
×
[
0.5000
−
0.8636
]
+
[
0.6875
−
0.7443
]
=
[
0.8494
−
0.6413
]
.
{\displaystyle 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
)
=
[
0.000
−
0.1875
0.000
−
0.1193
]
×
[
0.8494
−
0.6413
]
+
[
0.6875
−
0.7443
]
=
[
0.8077
−
0.6678
]
.
{\displaystyle 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
)
=
[
0.000
−
0.1875
0.000
−
0.1193
]
×
[
0.8077
−
0.6678
]
+
[
0.6875
−
0.7443
]
=
[
0.8127
−
0.6646
]
.
{\displaystyle 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
)
=
[
0.000
−
0.1875
0.000
−
0.1193
]
×
[
0.8127
−
0.6646
]
+
[
0.6875
−
0.7443
]
=
[
0.8121
−
0.6650
]
.
{\displaystyle 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
)
=
[
0.000
−
0.1875
0.000
−
0.1193
]
×
[
0.8121
−
0.6650
]
+
[
0.6875
−
0.7443
]
=
[
0.8122
−
0.6650
]
.
{\displaystyle 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
)
=
[
0.000
−
0.1875
0.000
−
0.1193
]
×
[
0.8122
−
0.6650
]
+
[
0.6875
−
0.7443
]
=
[
0.8122
−
0.6650
]
.
{\displaystyle 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}}.}
و همانگونه که انتظار داشتیم به مقدار دقیق همگرا شد:
x
=
A
−
1
b
=
[
0.8122
−
0.6650
]
.
{\displaystyle \mathbf {x} =A^{-1}\mathbf {b} ={\begin{bmatrix}0.8122\\-0.6650\end{bmatrix}}.}
