روش ژاکوبی یک روش تکراری در حل دستگاه معادلات خطی است که در جبر خطی مورد بحث قرار میگیرد.
در یک دستگاه مربعی با n معادلۀ خطی:
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 را به دو ماتریس به شکل زیر تفکیک کنیم:
A
=
D
+
R
where
D
=
[
a
11
0
⋯
0
0
a
22
⋯
0
⋮
⋮
⋱
⋮
0
0
⋯
a
n
n
]
and
R
=
[
0
a
12
⋯
a
1
n
a
21
0
⋯
a
2
n
⋮
⋮
⋱
⋮
a
n
1
a
n
2
⋯
0
]
.
{\displaystyle A=D+R\qquad {\text{where}}\qquad D={\begin{bmatrix}a_{11}&0&\cdots &0\\0&a_{22}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &a_{nn}\end{bmatrix}}{\text{ and }}R={\begin{bmatrix}0&a_{12}&\cdots &a_{1n}\\a_{21}&0&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\cdots &0\end{bmatrix}}.}
از روش تکرار جواب را میتوان به شکل زیر یافت:
x
(
k
+
1
)
=
D
−
1
(
b
−
R
x
(
k
)
)
.
{\displaystyle \mathbf {x} ^{(k+1)}=D^{-1}(\mathbf {b} -R\mathbf {x} ^{(k)}).}
اگر این فرمول را بر اساس المانهایش مرتبط کنیم به این صورت در خواهد آمد:
x
i
(
k
+
1
)
=
1
a
i
i
(
b
i
−
∑
j
≠
i
a
i
j
x
j
(
k
)
)
,
i
=
1
,
2
,
…
,
n
.
{\displaystyle x_{i}^{(k+1)}={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j\neq i}a_{ij}x_{j}^{(k)}\right),\quad i=1,2,\ldots ,n.}
حدس اولیه:
x
(
0
)
{\displaystyle x^{(0)}}
k
=
0
{\displaystyle k=0}
تا وقتی که همگرا نشده:
for i := 1 step until n do
σ
=
0
{\displaystyle \sigma =0}
for j := 1 step until n do
if j ≠ i then
σ
=
σ
+
a
i
j
x
j
(
k
)
{\displaystyle \sigma =\sigma +a_{ij}x_{j}^{(k)}}
end if
پایان حلقه j
x
i
(
k
+
1
)
=
(
b
i
−
σ
)
a
i
i
{\displaystyle x_{i}^{(k+1)}={{\left({b_{i}-\sigma }\right)} \over {a_{ii}}}}
end (i-loop)
بررسی همگرایی
k
=
k
+
1
{\displaystyle k=k+1}
ρ
(
D
−
1
R
)
<
1.
{\displaystyle \rho (D^{-1}R)<1.}
|
a
i
i
|
>
∑
j
≠
i
|
a
i
j
|
.
{\displaystyle \left|a_{ii}\right|>\sum _{j\neq i}{\left|a_{ij}\right|}.}
در روش ژاکوبی گاهی علیرغم اینکه شرایط همگرایی برقرار نباشد، جواب همگرا میشود.
در
A
x
=
b
{\displaystyle Ax=b}
با داشتن مقدار اولیه (حدس اولیه)، جواب را بدست می آوریم.
A
=
[
2
1
5
7
]
,
b
=
[
11
13
]
and
x
(
0
)
=
[
1
1
]
.
{\displaystyle A={\begin{bmatrix}2&1\\5&7\\\end{bmatrix}},\ b={\begin{bmatrix}11\\13\\\end{bmatrix}}\quad {\text{and}}\quad x^{(0)}={\begin{bmatrix}1\\1\\\end{bmatrix}}.}
با استفاده از رابطۀ
x
(
k
+
1
)
=
D
−
1
(
b
−
R
x
(
k
)
)
{\displaystyle x^{(k+1)}=D^{-1}(b-Rx^{(k)})}
، که در بالا توضیح داده شد، به تخمین
x
{\displaystyle x}
می پردازیم تا جواب بدست آید.
با بازنویسی رابطۀ اخیر به فرم سادهتر
D
−
1
(
b
−
R
x
(
k
)
)
=
T
x
(
k
)
+
C
{\displaystyle D^{-1}(b-Rx^{(k)})=Tx^{(k)}+C}
،که در آن
T
=
−
D
−
1
R
{\displaystyle T=-D^{-1}R}
و
C
=
D
−
1
b
{\displaystyle C=D^{-1}b}
.
توجه کنید که
R
=
L
+
U
{\displaystyle R=L+U}
که
L
{\displaystyle L}
و
U
{\displaystyle U}
به ترتیب قسمت پایینی و بالایی
A
{\displaystyle A}
هستند.
با استفاده از مقادیر داده شده:
D
−
1
=
[
1
/
2
0
0
1
/
7
]
,
L
=
[
0
0
5
0
]
and
U
=
[
0
1
0
0
]
.
{\displaystyle D^{-1}={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}},\ L={\begin{bmatrix}0&0\\5&0\\\end{bmatrix}}\quad {\text{and}}\quad U={\begin{bmatrix}0&1\\0&0\\\end{bmatrix}}.}
we determine
T
=
−
D
−
1
(
L
+
U
)
{\displaystyle T=-D^{-1}(L+U)}
as
T
=
[
1
/
2
0
0
1
/
7
]
{
[
0
0
−
5
0
]
+
[
0
−
1
0
0
]
}
=
[
0
−
1
/
2
−
5
/
7
0
]
.
{\displaystyle T={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}\left\{{\begin{bmatrix}0&0\\-5&0\\\end{bmatrix}}+{\begin{bmatrix}0&-1\\0&0\\\end{bmatrix}}\right\}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}.}
Further, C is found as
C
=
[
1
/
2
0
0
1
/
7
]
[
11
13
]
=
[
11
/
2
13
/
7
]
.
{\displaystyle C={\begin{bmatrix}1/2&0\\0&1/7\\\end{bmatrix}}{\begin{bmatrix}11\\13\\\end{bmatrix}}={\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}.}
With T and C calculated, we estimate
x
{\displaystyle x}
as
x
(
1
)
=
T
x
(
0
)
+
C
{\displaystyle x^{(1)}=Tx^{(0)}+C}
:
x
(
1
)
=
[
0
−
1
/
2
−
5
/
7
0
]
[
1
1
]
+
[
11
/
2
13
/
7
]
=
[
5.0
8
/
7
]
≈
[
5
1.143
]
.
{\displaystyle x^{(1)}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}{\begin{bmatrix}1\\1\\\end{bmatrix}}+{\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}={\begin{bmatrix}5.0\\8/7\\\end{bmatrix}}\approx {\begin{bmatrix}5\\1.143\\\end{bmatrix}}.}
با تکرار بعدی داریم:
x
(
2
)
=
[
0
−
1
/
2
−
5
/
7
0
]
[
5.0
8
/
7
]
+
[
11
/
2
13
/
7
]
=
[
69
/
14
−
12
/
7
]
≈
[
4.929
−
1.714
]
.
{\displaystyle x^{(2)}={\begin{bmatrix}0&-1/2\\-5/7&0\\\end{bmatrix}}{\begin{bmatrix}5.0\\8/7\\\end{bmatrix}}+{\begin{bmatrix}11/2\\13/7\\\end{bmatrix}}={\begin{bmatrix}69/14\\-12/7\\\end{bmatrix}}\approx {\begin{bmatrix}4.929\\-1.714\\\end{bmatrix}}.}
این فرایند تا جایی که همگرایی مشهود باشد تکرار میشود. (به عبارت دقیق تر
‖
A
x
(
n
)
−
b
‖
{\displaystyle \|Ax^{(n)}-b\|}
کوچک باشد).
جواب پس از ۲۵ بار تکرار خواهد بود:
x
=
[
7.111
−
3.222
]
.
{\displaystyle x={\begin{bmatrix}7.111\\-3.222\end{bmatrix}}.}
فرض کنید معادلات زیر را بخواهیم حل کنیم:
10
x
1
−
x
2
+
2
x
3
=
6
,
−
x
1
+
11
x
2
−
x
3
+
3
x
4
=
25
,
2
x
1
−
x
2
+
10
x
3
−
x
4
=
−
11
,
3
x
2
−
x
3
+
8
x
4
=
15.
{\displaystyle {\begin{aligned}10x_{1}-x_{2}+2x_{3}&=6,\\-x_{1}+11x_{2}-x_{3}+3x_{4}&=25,\\2x_{1}-x_{2}+10x_{3}-x_{4}&=-11,\\3x_{2}-x_{3}+8x_{4}&=15.\end{aligned}}}
با انتخاب (0, 0, 0, 0) به عنوان تقریب اولیه:
x
1
=
(
6
−
0
−
0
)
/
10
=
0.6
,
x
2
=
(
25
−
0
−
0
)
/
11
=
25
/
11
=
2.2727
x
3
=
(
−
11
−
0
−
0
)
/
10
=
−
1.1
,
x
4
=
(
15
−
0
−
0
)
/
8
=
1.875.
{\displaystyle {\begin{aligned}x_{1}&=(6-0-0)/10=0.6,\\x_{2}&=(25-0-0)/11=25/11=2.2727\\x_{3}&=(-11-0-0)/10=-1.1,\\x_{4}&=(15-0-0)/8=1.875.\end{aligned}}}
پاسخها پس از ۵ بار تکرار در جدول زیر آورده شده است:
x
1
{\displaystyle x_{1}}
x
2
{\displaystyle x_{2}}
x
3
{\displaystyle x_{3}}
x
4
{\displaystyle x_{4}}
0.6
{\displaystyle 0.6}
2.27272
{\displaystyle 2.27272}
−
1.1
{\displaystyle -1.1}
1.875
{\displaystyle 1.875}
1.04727
{\displaystyle 1.04727}
1.7159
{\displaystyle 1.7159}
−
0.80522
{\displaystyle -0.80522}
0.88522
{\displaystyle 0.88522}
0.93263
{\displaystyle 0.93263}
2.05330
{\displaystyle 2.05330}
−
1.0493
{\displaystyle -1.0493}
1.13088
{\displaystyle 1.13088}
1.01519
{\displaystyle 1.01519}
1.95369
{\displaystyle 1.95369}
−
0.9681
{\displaystyle -0.9681}
0.97384
{\displaystyle 0.97384}
0.98899
{\displaystyle 0.98899}
2.0114
{\displaystyle 2.0114}
−
1.0102
{\displaystyle -1.0102}
1.02135
{\displaystyle 1.02135}
جواب دقیق (1, 2, −1, 1) است.
import numpy as np
ITERATION_LIMIT = 1000
# initialize the matrix
A = np . array ([[ 10. , - 1. , 2. , 0. ],
[ - 1. , 11. , - 1. , 3. ],
[ 2. , - 1. , 10. , - 1. ],
[ 0.0 , 3. , - 1. , 8. ]])
# initialize the RHS vector
b = np . array ([ 6. , 25. , - 11. , 15. ])
# prints the system
print ( "System:" )
for i in range ( A . shape [ 0 ]):
row = [ " {} *x {} " . format ( A [ i , j ], j + 1 ) for j in range ( A . shape [ 1 ])]
print ( " + " . join ( row ), "=" , b [ i ])
print ()
x = np . zeros_like ( b )
for it_count in range ( ITERATION_LIMIT ):
print ( "Current solution:" , x )
x_new = np . zeros_like ( x )
for i in range ( A . shape [ 0 ]):
s1 = np . dot ( A [ i , : i ], x [: i ])
s2 = np . dot ( A [ i , i + 1 :], x [ i + 1 :])
x_new [ i ] = ( b [ i ] - s1 - s2 ) / A [ i , i ]
if np . allclose ( x , x_new , rtol = 1e-10 ):
break
x = x_new
print ( "Solution:" )
print ( x )
error = np . dot ( A , x ) - b
print ( "Error:" )
print ( error )
خروجی به این شکل خواهد بود:
System :
10.0 * x1 + - 1.0 * x2 + 2.0 * x3 + 0.0 * x4 = 6.0
- 1.0 * x1 + 11.0 * x2 + - 1.0 * x3 + 3.0 * x4 = 25.0
2.0 * x1 + - 1.0 * x2 + 10.0 * x3 + - 1.0 * x4 = - 11.0
0.0 * x1 + 3.0 * x2 + - 1.0 * x3 + 8.0 * x4 = 15.0
Current solution : [ 0. 0. 0. 0. ]
Current solution : [ 0.6 2.27272727 - 1.1 1.875 ]
Current solution : [ 1.04727273 1.71590909 - 0.80522727 0.88522727 ]
Current solution : [ 0.93263636 2.05330579 - 1.04934091 1.13088068 ]
Current solution : [ 1.01519876 1.95369576 - 0.96810863 0.97384272 ]
Current solution : [ 0.9889913 2.01141473 - 1.0102859 1.02135051 ]
Current solution : [ 1.00319865 1.99224126 - 0.99452174 0.99443374 ]
Current solution : [ 0.99812847 2.00230688 - 1.00197223 1.00359431 ]
Current solution : [ 1.00062513 1.9986703 - 0.99903558 0.99888839 ]
Current solution : [ 0.99967415 2.00044767 - 1.00036916 1.00061919 ]
Current solution : [ 1.0001186 1.99976795 - 0.99982814 0.99978598 ]
Current solution : [ 0.99994242 2.00008477 - 1.00006833 1.0001085 ]
Current solution : [ 1.00002214 1.99995896 - 0.99996916 0.99995967 ]
Current solution : [ 0.99998973 2.00001582 - 1.00001257 1.00001924 ]
Current solution : [ 1.00000409 1.99999268 - 0.99999444 0.9999925 ]
Current solution : [ 0.99999816 2.00000292 - 1.0000023 1.00000344 ]
Current solution : [ 1.00000075 1.99999868 - 0.99999899 0.99999862 ]
Current solution : [ 0.99999967 2.00000054 - 1.00000042 1.00000062 ]
Current solution : [ 1.00000014 1.99999976 - 0.99999982 0.99999975 ]
Current solution : [ 0.99999994 2.0000001 - 1.00000008 1.00000011 ]
Current solution : [ 1.00000003 1.99999996 - 0.99999997 0.99999995 ]
Current solution : [ 0.99999999 2.00000002 - 1.00000001 1.00000002 ]
Current solution : [ 1. 1.99999999 - 0.99999999 0.99999999 ]
Current solution : [ 1. 2. - 1. 1. ]
Solution :
[ 1. 2. - 1. 1. ]
Error :
[ - 2.81440107e-08 5.15706873e-08 - 3.63466359e-08 4.17092547e-08 ]
اصول بنیادی مسالهها سختافزارها نرمافزارها