Wikipedia

Metode Jacobi: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
Kembangraps (bicara | kontrib)
Pengurus
31.546 suntingan
kTidak ada ringkasan suntingan
Mas Has12 (bicara | kontrib)
1 suntingan
Fitur saranan suntingan: 3 pranala ditambahkan.
Tag: VisualEditor Suntingan perangkat seluler Suntingan peramban seluler Tugas pengguna baru Disarankan: tambahkan pranala
 
(27 revisi perantara oleh 17 pengguna tidak ditampilkan)
Baris 1:
'''Metode [[iterasiIterasi]] 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 namun 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 Jakob Jacobi]]. Penemuan ini diperkirakan pada tahun 1800-an.
 
Kalau kita merubahmengubah dalam Sistem Persamaan Linear, maka dapat ditulis sebagai berikut
 
:<math> A x = b.\, </math>
Kemudian, diketahui bahwa <math> A = D+\left({L + U} \right)</math>,
di mana <math>D</math> merupakan [[matriks diagonal]], <math>L</math> merupakan matriks segitiga bawah, dan <math>U</math> merupakan matriks segitiga atas.
 
Kemudian, persamaan di atas dapat diubah menjadi :
 
:<math> D x+\left({L + U} \right)x = b. </math><{{br>}}
Kemudian,
:<math> x = D^{ - 1} \left[b -\left({L + U} \right)x \right],
</math><{{br>}}
 
Jika ditulis dalam aturan iteratif, maka metode Jacobi dapat ditulis sebagai :
:<math>
x^{(k+1)} = D^{ - 1} \left[b-\left({L + U} \right)x^{(k)}\right],
</math><{{br>}}
di mana <math>k</math> merupakan banyaknya iterasi.
Jika <math>x^{(k)}</math> menyatakan hampiran ke- <mathkmath>k</math> penyelesaian SPL, maka <math>x^{(0)}</math> adalah hampiran awal.
:<math>
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.
</math>
 
== Deskripsi ==
==Algoritma Metode Iterasi Jacobi==
Jadi
 
:<math>A\mathbf x = \mathbf b</math>
INPUT :
: <math>n</math>, A, b, dan hampiran awal '''Y'''=(y<sub>1</sub> y<sub>2</sub> y<sub>3</sub>...y<sub>n</sub>)<sup>T</sup> , batas toleransi T, dan maksimum iterasi N<br>
 
menjadi sistem kuadrat dari nilai {{math|''n''}} dalam [[persamaan linier]] yaitu:
OUTPUT :
 
:'''X'''=(x<sub>1</sub> x<sub>2</sub> x<sub>3</sub>...x<sub>n</sub>)<sup>T</sup>, vektor galat hampiran <math>g</math>, dan <math>H</math> yang merupakan matriks dengan baris vektor-vektor hampiran selama iterasi.<br>
<math>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}.</math>
 
Setelah itu nilai {{math|''A''}} dapat diuraikan menjadi komponen diagonal {{math|''D''}}, bagian segitiga bawah {{math|''L''}} dan bagian segitiga atas {{math|''U''}}:
 
:<math>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}. </math>
 
== Algoritme Metode Iterasi Jacobi ==
 
INPUT:
: <math>n</math>, A, b, dan hampiran awal '''Y'''=(y<sub>1</sub> y<sub>2</sub> y<sub>3</sub>...y<sub>n</sub>)<sup>T</sup>, batas toleransi T, dan maksimum iterasi N{{br}}
 
OUTPUT:
:'''X'''=(x<sub>1</sub> x<sub>2</sub> x<sub>3</sub>...x<sub>n</sub>)<sup>T</sup>, vektor galat hampiran <math>g</math>, dan <math>H</math> yang merupakan matriks dengan baris vektor-vektor hampiran selama iterasi.{{br}}
 
# Set penghitung iterasi k=1
# WHILE <math>k<=N</math> DO
## FOR <math>i i = 1,2,3,...,n</math>, Hitung <math>x_i = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}y_j\right)</math>
## SET <math>X=(x_1 x_2 x_3...x_n)^T</math>
## IF ||X_Y||<T THEN STOP
## Tambah penghitung iterasi, <math>k=k+1</math>
## FOR <math>i=1,2,3,...,n</math>, Set ''y<sub>i</sub>=x<sub>i</sub>''
## SET Y=(y<sub>1</sub> y<sub>2</sub> y<sub>3</sub>...y<sub>n</sub>)<sup>T</sup>
# Tulis pesan "Metode gagal setelah N iterasi"
# STOP
 
'''Input:''' {{nowrap|initial guess <math>x^{(0)}</math> to the solution}}, (diagonal dominant) matrix <math>A</math>, right-hand side vector <math>b</math>, convergence criterion
'''Output:''' {{nowrap|solution when convergence is reached}}
'''Comments:''' {{nowrap|pseudocode based on the element-based formula above}}
{{nowrap|<math> k = 0 </math>}}
'''while''' convergence not reached '''do'''
'''for''' i := 1 '''step until''' n '''do'''
{{nowrap|<math> \sigma = 0 </math>}}
'''for''' j := 1 '''step until''' n '''do'''
'''if''' j &ne; i '''then'''
{{nowrap|<math> \sigma = \sigma + a_{ij} x_j^{(k)} </math>}}
'''end'''
'''end'''
{{nowrap|<math> x_i^{(k+1)} = {{\frac{1}{a_{ii}} \left( {b_i - \sigma } \right)}} </math>}}
'''end'''
{{nowrap|<math>k = k + 1</math>}}
'''end'''
 
==Algoritma Algoritme Metode Iterasi Jacobi dalam bentuk ''software'' Matlab ==
 
Penggunaan algoritma[[Algoritma|algoritme]] Metode Iterasi Jacobi dalam bentuk matlab. Matlab merupakan program pengolahan data numerik.
 
INPUT :
: <math>n</math>, A, b, dan hampiran awal '''Y'''=(y<sub>1</sub> y<sub>2</sub> y<sub>3</sub>...y<sub>n</sub>)<sup>T</sup> , batas toleransi T, dan maksimum iterasi N<{{br>}}
 
OUTPUT :
:'''X'''=(x<sub>1</sub> x<sub>2</sub> x<sub>3</sub>...x<sub>n</sub>)<sup>T</sup>, vektor galat hampiran <math>g</math>, dan <math>H</math> yang merupakan matriks dengan baris vektor-vektor hampiran selama iterasi.<{{br>}}
 
: H=X0'<{{br>}}
: n=length (b)<{{br>}}
: X=X0<{{br>}}
: for k:=1 until N<{{br>}}
:: for i:=i until n,<{{br>}}
::: S = b (i) - A (i,[1:i-1,i+1:n]) * X0 ([1:i-1,i+1:n](<){{br> }}
::: X(i) = S / A (i,i)<{{br>}}
:: end<{{br>}}
:: g = abs (X-X0)<{{br>}}
:: err = norm (g)<{{br>}}
:: relerr = err / (norm (X)+eps)<{{br>}}
:: X0 = X<{{br>}}
:: H = [H;X0']<{{br>}}
:: if (err<T)|(relerr<T), break, end<{{br>}}
: end
 
== Kekonvergenan ==
 
==Kekonvergenan==
MEtode ini akan bernilai konvergen jika matriksnya merupakan '''matriks dominan secara diagonal''', yaitu apabila unsur diagonal pada kolom tersebut lebih besar dari penjumlahan unsur-unsur lainnya pada kolom tersebut.
 
:<math>\left | a_{ii} \right | > \sum_{i \ne j} {\left | a_{ij} \right |}. </math>
 
== Contoh ==
Sistem linear dari bentuk <math>Ax=b</math> dengan perkiraan awal <math>x^{(0)}</math> diberikan oleh
 
:<math> 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} .</math>
Kami menggunakan persamaan <math> x^{(k+1)}=D^{-1}(b - (L+U)x^{(k)})</math>, dijelaskan di atas, untuk memperkirakan <math>x</math>. Pertama, kami menulis ulang persamaan dalam bentuk yang lebih mudah <math>D^{-1}(b - (L+U)x^{(k)}) = Tx^{(k)} + C</math>, dimana <math>T=-D^{-1}(L+U)</math> dan <math>C = D^{-1}b</math>. Dari nilai-nilai yang diketahui
 
:<math> 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} .</math>
we determine <math> T=-D^{-1}(L+U) </math> as
:<math> 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} .</math>
Further, <math>C</math> is found as
 
:<math> 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}. </math>
Dengan <math>T</math> dan <math>C</math> dihitung, kami perkirakan <math>x</math> sebagai <math> x^{(1)}= Tx^{(0)}+C </math>:
:<math> 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} .</math>
Hasil iterasi berikutnya
:<math> 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} .</math>
Proses ini diulangi sampai konvergensi (yaitu, sampai <math>\|Ax^{(n)} - b\|</math> kecil). Solusi setelah 25 iterasi adalah
:<math> x=\begin{bmatrix}
7.111\\
-3.222
\end{bmatrix}
.</math>
 
=== Contoh lain ===
 
Contohnya kita diberi sistem linier berikut:
 
:<math>
\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}
</math>
 
Bila kita memilih {{math|(0,&nbsp;0,&nbsp;0,&nbsp;0)}} sebagai pendekatan awal, maka solusi perkiraan pertama diberikan oleh
 
:<math>
\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}
</math>
 
Dengan menggunakan perkiraan yang diperoleh, prosedur iteratif diulangi sampai akurasi yang diinginkan tercapai. Berikut ini adalah solusi yang diperkirakan setelah lima iterasi.
 
{| class="wikitable" border="1"
|-
! <math>x_1</math>
! <math>x_2</math>
! <math>x_3</math>
! <math>x_4</math>
|-
| 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
|}
Solusi yang tepat dari sistem ini adalah {{math|(1,&nbsp;2,&nbsp;&minus;1,&nbsp;1)}}.
 
=== Contoh menggunakan Python dan NumPy ===
Prosedur numerik berikut hanya melakukan iterasi untuk menghasilkan vektor solusi.
 
<syntaxhighlight lang="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)
</syntaxhighlight>
 
Menghasilkan keluaran:
 
<pre>
x: [3.99275362 2.95410628 2.16183575 0.96618357]
computed b: [29. 31. 26. 19.]
real b: [29 31 26 19]
</pre>
 
== Lihat pula ==
 
*[[Metode Gauss–Seidel]]
*[[Relaksasi berlebihan berturut-turut]]
*[[Metode berulang#Sistem linear|Metode berulang§Sistem linier]]
*[[Propagasi Keyakinan#Propagasi keyakinan Gaussian .28GaBP.29|Propagasi Keyakinan Gaussian]]
* [[Pemisahan matriks]]
 
==DAFTAR PUSTAKAReferensi ==
{{Reflist}}
: Sahid. 2005. ''Pengantar Komputasi Numerik dengan MATLAB''. ANDI, Yogyakarta
 
== Pranala luar ==
<!--* {{CFDWiki|name=Jacobi_method}}-->
*[http://en.wiki-indonesia.club/wiki/jacobi_method]
* {{MathWorld|urlname=JacobiMethod|title=Metode Jacobi|author=Black, Noel; Moore, Shirley; and Weisstein, Eric W.}}
* [http://www.math-linux.com/spip.php?article49 Jacobi Method from www.math-linux.com]
 
<!--{{Aljabar linear numerik}}-->
[[Kategori:Matematika]]
 
[[Kategori:Aljabar linear numerik]]
[[en:Jacobi method]]
[[Kategori:Artikel dengan contoh kodesemu]]
[[Kategori:Relaksasi (metode berulang)]]
[[Kategori:Artikel dengan contoh kode Python]]
[[Kategori:Analisis numerik]]
Diperoleh dari "https://wiki-indonesia.club/wiki/Metode_Jacobi"