روش ژاکوبی یک روش تکراری در حل دستگاه معادلات خطی است که در جبر خطی مورد بحث قرار میگیرد.
در یک دستگاه مربعی با n معادلۀ خطی:
![{\displaystyle A\mathbf {x} =\mathbf {b} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/45d894430af69e29d6dda5aacbf4bb19336226a0)
که:
اگر ماتریس A را به دو ماتریس به شکل زیر تفکیک کنیم:
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05e23004e83e02ab6dd00953fe2f5bc5508b09c3)
از روش تکرار جواب را میتوان به شکل زیر یافت:
![{\displaystyle \mathbf {x} ^{(k+1)}=D^{-1}(\mathbf {b} -R\mathbf {x} ^{(k)}).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4adf9615704a640c2b6c1b5d5cd15d1014c6df02)
اگر این فرمول را بر اساس المانهایش مرتبط کنیم به این صورت در خواهد آمد:
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14729abaaebeb851f7eac41e41f04a6666463849)
- حدس اولیه:
![{\displaystyle x^{(0)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ad6bd852c94bbaf7de8ed7a188634cb3848167e)
![{\displaystyle k=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6307c8a99dad7d0bcb712352ae0a748bd99a038b)
- تا وقتی که همگرا نشده:
- for i := 1 step until n do
![{\displaystyle \sigma =0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1eb4831f1e0ca1ba7d007dc6b973e54787e1a4b4)
- for j := 1 step until n do
- if j ≠ i then
![{\displaystyle \sigma =\sigma +a_{ij}x_{j}^{(k)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ee0c47c2b53e85c5de51c3c7040fb0fa970bc6e7)
- end if
- پایان حلقه j
![{\displaystyle x_{i}^{(k+1)}={{\left({b_{i}-\sigma }\right)} \over {a_{ii}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ba69c5bc9a149649afc573ff02bf62e80ceb4fe)
- end (i-loop)
- بررسی همگرایی
![{\displaystyle k=k+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daac515060e17c7b2b5ef6ea21ebe7fba066a93)
![{\displaystyle \rho (D^{-1}R)<1.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ef74f108ef54a72b47f384b402daae83a931e26)
![{\displaystyle \left|a_{ii}\right|>\sum _{j\neq i}{\left|a_{ij}\right|}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5543526e4e4c4ce0e00f6e6ca94a0dfd8ce91e7a)
در روش ژاکوبی گاهی علیرغم اینکه شرایط همگرایی برقرار نباشد، جواب همگرا میشود.
در
با داشتن مقدار اولیه (حدس اولیه)، جواب را بدست می آوریم.
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d99d9203a7aa825aeff53f7e0cbe0328ac9d56d2)
با استفاده از رابطۀ
، که در بالا توضیح داده شد، به تخمین
می پردازیم تا جواب بدست آید.
با بازنویسی رابطۀ اخیر به فرم سادهتر
،که در آن
و
.
توجه کنید که
که
و
به ترتیب قسمت پایینی و بالایی
هستند.
با استفاده از مقادیر داده شده:
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e7928f38e2d1c02dba11044b6f1158943986218)
we determine
as
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e6493240180d28c37f205cf4071d5c04959c9902)
Further, C is found as
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c303d556021fc11153b9e981e7568bd0d988f8a)
With T and C calculated, we estimate
as
:
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a09ee6f5a9c7e642cdbc83f9ea211cf8f6ab79fa)
با تکرار بعدی داریم:
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/774f486ce8fdadd7c9e7f735e43798df0cc96c00)
این فرایند تا جایی که همگرایی مشهود باشد تکرار میشود. (به عبارت دقیق تر
کوچک باشد).
جواب پس از ۲۵ بار تکرار خواهد بود:
![{\displaystyle x={\begin{bmatrix}7.111\\-3.222\end{bmatrix}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5458d3839311975d33a349c54b41fbd82e3f7e98)
فرض کنید معادلات زیر را بخواهیم حل کنیم:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11f2a2bb16c285c9e6adcb1581bfdb1dd3b84551)
با انتخاب (0, 0, 0, 0) به عنوان تقریب اولیه:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f438251d712182685bc5fe406dda4e6509ab982b)
پاسخها پس از ۵ بار تکرار در جدول زیر آورده شده است:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
جواب دقیق (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]
جستارهای وابسته[ویرایش]
|
---|
اصول بنیادی | |
---|
مسالهها | |
---|
سختافزارها | |
---|
نرمافزارها | |
---|