روش ژاکوبی

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

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

: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** را به دو ماتریس به شکل زیر تفکیک کنیم:

: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}. 

از روش تکرار جواب را می‌توان به شکل زیر یافت:
: \mathbf{x}^{(k+1)} = D^{-1} (\mathbf{b} - R \mathbf{x}^{(k)}). 

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

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

## الگوریتم
:  حدس اولیه: x^{(0)} 
:   k = 0 
:  تا وقتی که همگرا نشده:
::  for i := 1 step until n do
:::   \sigma = 0 
:::  for j := 1 step until n do
::::  if j &ne; i then
:::::   \sigma  = \sigma  + a_{ij} x_j^{(k)} 
::::  end if
:::  پایان حلقه j
:::    x_i^{(k+1)}  = } 
::  end (i-loop)
::  بررسی همگرایی
::  k = k + 1

## همگرایی
:\rho(D^{-1}R) 

:\left | a_{ii} \right |> \sum_{j \ne i} {\left | a_{ij} \right |}. 

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

## چند مثال
### مثال۱
در Ax=b با داشتن مقدار اولیه (حدس اولیه)، جواب را بدست می آوریم.
: 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 - Rx^{(k)})، که در بالا توضیح داده شد، به تخمین x می پردازیم تا جواب بدست آید.

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

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

با استفاده از مقادیر داده شده:
: 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)  as
: 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 =
      \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 as  x^{(1)}= Tx^{(0)}+C :
: 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)}= 
      \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} .
این فرایند تا جایی که همگرایی مشهود باشد تکرار می‌شود. (به عبارت دقیق تر \|Ax^{(n)} - b\| کوچک باشد).  
جواب پس از ۲۵ بار تکرار خواهد بود:
: x=\begin{bmatrix}
7.111\\
-3.222
\end{bmatrix}
.

### مثال۲
فرض کنید معادلات زیر را بخواهیم حل کنیم:
:
\begin{align}
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{align}


با انتخاب (0,&nbsp;0,&nbsp;0,&nbsp;0) به عنوان تقریب اولیه:
:
\begin{align}
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{align}


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

    

جواب دقیق (1,&nbsp;2,&nbsp;&minus;1,&nbsp;1) است.

### حل مثال در پایتون

```python
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)
```


خروجی به این شکل خواهد بود:

```python
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]
```


## جستارهای وابسته
* روش گاوس سیدل

## منابع

* 

رده:جبر خطی عددی
رده:روش‌های تکراری