روش ژاکوبی

روش ژاکوبی یک روش تکراری در حل دستگاه معادلات خطی است که در جبر خطی مورد بحث قرار می‌گیرد.

معرفی کلی

در یک دستگاه مربعی با n معادلۀ خطی:

$A𝐱=𝐛$

که:

$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right],𝐱=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right],𝐛=\left[\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_n\end{array}\right].$

اگر ماتریس A را به دو ماتریس به شکل زیر تفکیک کنیم:

$A=D+R\text{where}D=\left[\begin{array}{cccc}{a}_{11}& 0& \cdots & 0\\ 0& a_{22}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_{nn}\end{array}\right]\text{ and }R=\left[\begin{array}{cccc}0& a_{12}& \cdots & a_{1n}\\ a_{21}& 0& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & 0\end{array}\right].$

از روش تکرار جواب را می‌توان به شکل زیر یافت:

${𝐱}^{(k+1)}=D^{-1}(𝐛-R{𝐱}^{(k)}).$

اگر این فرمول را بر اساس المانهایش مرتبط کنیم به این صورت در خواهد آمد:

$x_i^{(k+1)}=\frac{1}{a_{ii}}(b_i-\sum _{j\ne i}{a}_{ij}{x}_j^{(k)}),i=1,2,\dots ,n.$

الگوریتم

حدس اولیه: $x^{(0)}$

$k=0$

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

for i := 1 step until n do

$\sigma =0$

for j := 1 step until n do

if j ≠ i then

$\sigma =\sigma +a_{ij}{x}_j^{(k)}$

end if

پایان حلقه j

$x_i^{(k+1)}=\frac{\left(b_i-\sigma \right)}{a_{ii}}$

end (i-loop)

بررسی همگرایی

$k=k+1$

همگرایی

$\rho (D^{-1}R)<1.$

$\left|a_{ii}\right|>\sum _{j\ne i}\left|a_{ij}\right|.$

در روش ژاکوبی گاهی علی‌رغم اینکه شرایط همگرایی برقرار نباشد، جواب همگرا می‌شود.

چند مثال

مثال۱

در $Ax=b$ با داشتن مقدار اولیه (حدس اولیه)، جواب را بدست می آوریم.

$A=\left[\begin{array}{cc}2& 1\\ 5& 7\end{array}\right],b=\left[\begin{array}{c}11\\ 13\end{array}\right]\text{and}{x}^{(0)}=\left[\begin{array}{c}1\\ 1\end{array}\right].$

با استفاده از رابطۀ $x^{(k+1)}=D^{-1}(b-R{x}^{(k)})$، که در بالا توضیح داده شد، به تخمین $x$ می پردازیم تا جواب بدست آید.

با بازنویسی رابطۀ اخیر به فرم ساده‌تر $D^{-1}(b-R{x}^{(k)})=T{x}^{(k)}+C$،که در آن $T=-D^{-1}R$ و $C=D^{-1}b$.

توجه کنید که $R=L+U$ که $L$ و $U$ به ترتیب قسمت پایینی و بالایی $A$ هستند.

با استفاده از مقادیر داده شده:

$D^{-1}=\left[\begin{array}{cc}1/2& 0\\ 0& 1/7\end{array}\right],L=\left[\begin{array}{cc}0& 0\\ 5& 0\end{array}\right]\text{and}U=\left[\begin{array}{cc}0& 1\\ 0& 0\end{array}\right].$

we determine $T=-D^{-1}(L+U)$ as

$T=\left[\begin{array}{cc}1/2& 0\\ 0& 1/7\end{array}\right]\{\left[\begin{array}{cc}0& 0\\ -5& 0\end{array}\right]+\left[\begin{array}{cc}0& -1\\ 0& 0\end{array}\right]\}=\left[\begin{array}{cc}0& -1/2\\ -5/7& 0\end{array}\right].$

Further, C is found as

$C=\left[\begin{array}{cc}1/2& 0\\ 0& 1/7\end{array}\right]\left[\begin{array}{c}11\\ 13\end{array}\right]=\left[\begin{array}{c}11/2\\ 13/7\end{array}\right].$

With T and C calculated, we estimate $x$ as $x^{(1)}=T{x}^{(0)}+C$:

$x^{(1)}=\left[\begin{array}{cc}0& -1/2\\ -5/7& 0\end{array}\right]\left[\begin{array}{c}1\\ 1\end{array}\right]+\left[\begin{array}{c}11/2\\ 13/7\end{array}\right]=\left[\begin{array}{c}5.0\\ 8/7\end{array}\right]\approx \left[\begin{array}{c}5\\ 1.143\end{array}\right].$

با تکرار بعدی داریم:

$x^{(2)}=\left[\begin{array}{cc}0& -1/2\\ -5/7& 0\end{array}\right]\left[\begin{array}{c}5.0\\ 8/7\end{array}\right]+\left[\begin{array}{c}11/2\\ 13/7\end{array}\right]=\left[\begin{array}{c}69/14\\ -12/7\end{array}\right]\approx \left[\begin{array}{c}4.929\\ -1.714\end{array}\right].$

این فرایند تا جایی که همگرایی مشهود باشد تکرار می‌شود. (به عبارت دقیق تر $\Vert A{x}^{(n)}-b\Vert$ کوچک باشد). جواب پس از ۲۵ بار تکرار خواهد بود:

$x=\left[\begin{array}{c}7.111\\ -3.222\end{array}\right].$

مثال۲

فرض کنید معادلات زیر را بخواهیم حل کنیم:

$\begin{array}{cc}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{array}$

با انتخاب (0, 0, 0, 0) به عنوان تقریب اولیه:

$\begin{array}{cc}{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{array}$

پاسخ‌ها پس از ۵ بار تکرار در جدول زیر آورده شده است:

$x_1$	$x_2$	$x_3$	$x_4$
$0.6$	$2.27272$	$-1.1$	$1.875$
$1.04727$	$1.7159$	$-0.80522$	$0.88522$
$0.93263$	$2.05330$	$-1.0493$	$1.13088$
$1.01519$	$1.95369$	$-0.9681$	$0.97384$
$0.98899$	$2.0114$	$-1.0102$	$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]

جستارهای وابسته

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

منابع

• الگو:یادکرد ویکی