Metode Jacobi

**Metode [[Iterasi]] Jacobi** merupakan salah satu bidang analisis numerik yang digunakan untuk menyelesaikan permasalahan persamaan linear dan sering dijumpai dalam berbagai disiplin ilmu. Metode Iterasi Jacobi merupakan salah satu metode tak langsung, yaitu bermula dari suatu hampiran penyelesaian awal dan kemudian berusaha memperbaiki hampiran dalam tak berhingga tetapi langkah konvergen. Metode Iterasi Jacobi ini digunakan untuk menyelesaikan persamaan linear berukuran besar dan proporsi koefisien nolnya besar.

Metode ini ditemukan oleh matematikawan yang berasal dari Jerman, Carl Gustav Jacob Jacobi. Penemuan ini diperkirakan pada tahun 1800-an.

Kalau kita mengubah dalam Sistem Persamaan Linear, maka dapat ditulis sebagai berikut

: A x = b.\, 
Kemudian, diketahui bahwa  A = D+\left({L + U} \right),
di mana D merupakan matriks diagonal, L merupakan matriks segitiga bawah, dan U merupakan matriks segitiga atas.

Kemudian, persamaan di atas dapat diubah menjadi:

: D x+\left({L + U} \right)x = b.
Kemudian,
: x = D^{ - 1} \left[b -\left({L + U} \right)x \right],


Jika ditulis dalam aturan iteratif, maka metode Jacobi dapat ditulis sebagai:
:
x^{(k+1)}  = D^{ - 1} \left[b-\left({L + U} \right)x^{(k)}\right],

di mana k merupakan banyaknya iterasi.
Jika x^{(k)} menyatakan hampiran ke- k penyelesaian SPL, maka x^{(0)} adalah hampiran awal.
:
x^{(k)}_i  = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}x^{(k-1)}_j\right),\, i=1,2,\ldots,n.


## Deskripsi
Jadi

:A\mathbf x = \mathbf b

menjadi sistem kuadrat dari nilai  dalam persamaan linier yaitu:

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

Setelah itu nilai  dapat diuraikan menjadi komponen diagonal , bagian segitiga bawah  dan bagian segitiga atas :

:A=D+L+U \qquad \text{darimana} \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 } L+U = \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}. 

## Algoritma Metode Iterasi Jacobi

INPUT:
: n, A, b, dan hampiran awal **Y**=(y1 y2 y3...yn)T, batas toleransi T, dan maksimum iterasi N

OUTPUT:
:**X**=(x1 x2 x3...xn)T, vektor galat hampiran g, dan H yang merupakan matriks dengan baris vektor-vektor hampiran selama iterasi.

# Set penghitung iterasi k=1
# WHILE k DO
## FOR i = 1,2,3,...,n, Hitung x_i = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}y_j\right)
## SET X=(x_1 x_2 x_3...x_n)^T
## IF ||X_Y||k=k+1
## FOR i=1,2,3,...,n, Set *y<sub>i</sub>=x<sub>i</sub>*
## SET Y=(y1 y2 y3...yn)T
# Tulis pesan "Metode gagal setelah N iterasi"
# STOP

 **Input:** , (diagonal dominant) matrix A, right-hand side vector b, convergence criterion
 **Output:** 
 **Comments:** 

 
 **while** convergence not reached **do**
     **for** i := 1 **step until** n **do**
         
         **for** j := 1 **step until** n **do**
             **if** j &ne; i **then**
                 
             **end**
         **end**
          }}
     **end**
     
 **end**

## Algoritma Metode Iterasi Jacobi dalam bentuk ''software'' Matlab

Penggunaan algoritme Metode Iterasi Jacobi dalam bentuk matlab. Matlab merupakan program pengolahan data numerik.

INPUT:
: n, A, b, dan hampiran awal **Y**=(y1 y2 y3...yn)T, batas toleransi T, dan maksimum iterasi N

OUTPUT:
:**X**=(x1 x2 x3...xn)T, vektor galat hampiran g, dan H yang merupakan matriks dengan baris vektor-vektor hampiran selama iterasi.

: H=X0'
: n=length (b)
: X=X0
: for k:=1 until N
:: for i:=i until n,
::: S = b (i) - A (i,[1:i-1,i+1:n]) * X0 ([1:i-1,i+1:n])
::: X(i) = S / A (i,i)
:: end
:: g = abs (X-X0)
:: err = norm (g)
:: relerr = err / (norm (X)+eps)
:: X0 = X
:: H = [H;X0']
:: if (err\left | a_{ii} \right | > \sum_{i \ne j} {\left | a_{ij} \right |}.

## Contoh
Sistem linear dari bentuk Ax=b dengan perkiraan awal x^{(0)} diberikan oleh

: A=
      \begin{bmatrix}
           2 & 1 \\
           5 & 7 \\
           \end{bmatrix},
 \ b=
      \begin{bmatrix}
           11 \\
           13 \\
           \end{bmatrix}
\quad \text{dan} \quad x^{(0)} =
        \begin{bmatrix}
           1 \\
           1 \\
        \end{bmatrix} .
Kami menggunakan persamaan  x^{(k+1)}=D^{-1}(b - (L+U)x^{(k)}), dijelaskan di atas, untuk memperkirakan x. Pertama, kami menulis ulang persamaan dalam bentuk yang lebih mudah D^{-1}(b - (L+U)x^{(k)}) = Tx^{(k)} + C, dimana T=-D^{-1}(L+U) dan C = D^{-1}b. Dari nilai-nilai yang diketahui

: D^{-1}=
      \begin{bmatrix}
           1/2 & 0 \\
           0 & 1/7 \\
           \end{bmatrix},
 \ L=
      \begin{bmatrix}
           0 & 0 \\
           5 & 0 \\
           \end{bmatrix}
\quad \text{dan}  \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}. 
Dengan T dan C dihitung, kami perkirakan x sebagai  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} .
Hasil iterasi berikutnya
: 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} .
Proses ini diulangi sampai konvergensi (yaitu, sampai \|Ax^{(n)} - b\| kecil). Solusi setelah 25 iterasi adalah
: x=\begin{bmatrix}
7.111\\
-3.222
\end{bmatrix}
.

### Contoh lain

Contohnya kita diberi sistem linier berikut:

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


Bila kita memilih  sebagai pendekatan awal, maka solusi perkiraan pertama diberikan oleh

:
\begin{align}
x_1 & = (6 + 0 - (2 * 0)) / 10 = 0.6, \\
x_2 & = (25 + 0 + 0 - (3 * 0)) / 11 = 25/11 = 2.2727, \\
x_3 & = (-11 - (2 * 0) + 0 + 0) / 10 = -1.1,\\
x_4 & = (15 - (3 * 0) + 0) / 8 = 1.875.
\end{align}


Dengan menggunakan perkiraan yang diperoleh, prosedur iteratif diulangi sampai akurasi yang diinginkan tercapai. Berikut ini adalah solusi yang diperkirakan setelah lima iterasi.

Solusi yang tepat dari sistem ini adalah .

### Contoh menggunakan Python dan NumPy
Prosedur numerik berikut hanya melakukan iterasi untuk menghasilkan vektor solusi.


```python
def jacobi(A, b, x_init, epsilon=1e-10, max_iterations=500):
    D = np.diag(np.diag(A))
    LU = A - D
    x = x_init
    for i in range(max_iterations):
        D_inv = np.diag(1 / np.diag(D))
        x_new = np.dot(D_inv, b - np.dot(LU, x))
        if np.linalg.norm(x_new - x) < epsilon:
            return x_new
        x = x_new
    return x

# problem data
A = np.array([
    [5, 2, 1, 1],
    [2, 6, 2, 1],
    [1, 2, 7, 1],
    [1, 1, 2, 8]
])
b = np.array([29, 31, 26, 19])

# you can choose any starting vector
x_init = np.zeros(len(b))
x = jacobi(A, b, x_init)

print("x:", x)
print("computed b:", np.dot(A, x))
print("real b:", b)
```


Menghasilkan keluaran:


```
x: [3.99275362 2.95410628 2.16183575 0.96618357]
computed b: [29. 31. 26. 19.]
real b: [29 31 26 19]
```


## Lihat pula

*Metode Gauss–Seidel
*Relaksasi berlebihan berturut-turut
*Metode berulang§Sistem linier
*Propagasi Keyakinan Gaussian
* Pemisahan matriks

## Referensi

: Sahid. 2005. *Pengantar Komputasi Numerik dengan MATLAB*. ANDI, Yogyakarta

## Pranala luar

* 
* Jacobi Method from www.math-linux.com