Metode Iterasi; Uraian Iterasi Jacobi dan Iterasi Gauss-Seidel

Metode Iterasi

Iterasi Jacobi

0.1 Algoritma Iterasi Jacobi

0.1.1 Berikut adalah penerpan fungsi jacobi() tersebut:

0.1.2 Selanjutya lakukan invers terhadap matriks L menggunakn fungsi solve().
0.1.3 ◾iterasi 1◾
0.1.4 ◾iterasi 2◾

Iterasi Gauss-Seidel

0.2 Algoritma Iterasi Gauss-Seidel

0.2.0.1 Jawab:

0.3 $Referensi$

Dosen Pengampu : Prof. Dr. Suhartono, M.Kom

Lembaga : Universitas Islam Negeri Maulana Malik Ibrahim Malang

Jurusan : Teknik Informatika

Fakultas : Sains dan Teknologi

Metode Iterasi

Pada Chapter ini kita akan membahas penyelesaian persamaan linier dengan menggunakan metode iterasi. Terdapat dua metode iterasi yang akan dibahas yaitu iterasi Jacobi dan Gauss-Seidel.

Metode iterasi dimulai dengan estimasi nilai akhir. Setelah menerapkan beberapa perlakuan pada nilai estimasi, hasil perlakuan selanjutnya menjadi nilai estimasi untuk iterasi berikutnya. Proses tersebut akan berlangsung secara terus-menerus hingga ambang batas dipenuhi. Nilai ambang batas dapat berupa jumlah iterasi maksimum atau selisih antara nilai estimasi baru dan estimasi semula lebih kecil dari suatu nilai toleransi yang ditetapkan.

Jumlah kuadrat merupakan metode yang sering digunakan untuk mengecek apakah selisih nilai estimasi baru terhadap estimasi lama lebih kecil dari nilai toleransi yang ditetapkan. Persamaan (6.33) menampilkan hubungan antara jumlah kuadrat dan nilai toleransi pada proses iterasi.

Iterasi Jacobi

Untuk menyelesaikan matriks menggunakan metode iterasi, kita dapat mulai dengan premis terdapat matriks A dan vektor x dan b, sehingga x=b.Dengan menggunakan metode Jacobi, pertama-tama kita dapat amati bahwa terdapat matriks R dan D yang memiliki hubungan A=R+D . Berdasarkan kedua hubungan tersebut, dapat diturunkan operasi matriks melalui persamaan berikut:

dimana D merupakan matriks diagonal dengan nilai elemen diagonal berupa diagonal utama matriks A . Invers dari matriks D secara sederhana sebagai matriks diagonal sama dengan satu dibagi dengan elemen diagonal utama matriks A. Matriks R identik dengan matriks A . Namun, diagonal utamanya bernilai nol. Suatu iterasi dikatakan konvergen jika jumlah kuadrat dari vektor x(n+1) dan vektor x(n) semakin mengecil.

Suatu persamaan linier yang hendak diselesaikan dengan menggunakan metode iterasi Jacobi harus memenuhi syarat nilai elemen diagonal utama matriks harus lebih dominan. Maksudnya adalah nilai absolut diagonal utama matriks harus lebih besar dari jumlah nilai absolut elemen matriks lainnya pada satu kolom.

(A <- matrix(c(5,2,1,2,7,3,3,4,8), 3))

##      [,1] [,2] [,3]
## [1,]    5    2    3
## [2,]    2    7    4
## [3,]    1    3    8

(b <- c(40,39,55))

## [1] 40 39 55

(x <- rep(0,3))

## [1] 0 0 0

Langkah selanjutnya adalah memperoleh invers matriks D .

(Dinv <- diag(1/diag(A)))

##      [,1]      [,2]  [,3]
## [1,]  0.2 0.0000000 0.000
## [2,]  0.0 0.1428571 0.000
## [3,]  0.0 0.0000000 0.125

Persiapan terakhir sebelum iterasi dilakukan adalah menyiapkan matriks R .

(R<-A-diag(diag(A)))

##      [,1] [,2] [,3]
## [1,]    0    2    3
## [2,]    2    0    4
## [3,]    1    3    0

Iterasi selanjutnya dilakukan menggunakan Persamaan (6.38).

0.0.1 ◾iterasi 1◾

(x1 <- Dinv %*% (b-R%*%x))

##          [,1]
## [1,] 8.000000
## [2,] 5.571429
## [3,] 6.875000

0.0.2 ◾iterasi 2◾

(x2 <- Dinv %*% (b-R%*%x1))

##            [,1]
## [1,]  1.6464286
## [2,] -0.6428571
## [3,]  3.7857143

0.0.3 ◾iterasi 3◾

(x3 <- Dinv %*% (b-R%*%x2))

##          [,1]
## [1,] 5.985714
## [2,] 2.937755
## [3,] 6.910268

Selama proses iterasi,jumlah akar jumlah kuadrat dihitung. Sebagai contoh berikut disajikan akar jumlah kuadrat pada iterasi ke-3:

sqrt(sum(x3-x2)^2)

## [1] 11.04445

0.1 Algoritma Iterasi Jacobi

Masukkan matriks AA, dan vektor BB beserta ukurannya nn.
Hitung invers matriks DD, dimana nilai invernya merupakan matriks diagonal dari satu per diagonal utama matriks AA.
Hitung matriks RR, dimana RR merupakan selisih matriks AA dikurangi dengan matriks diagonal dengan entri dari diagonal utama matriks AA.
Tetapkan vektor xx estimasi.
Tetapkan nilai toleransi maksimum yang dapat diterima.
Lakukan iterasi menggunakan Persamaan (6.38).
Hitung akar jumlah kuadrat dari vektor xn+1xn+1 dan vektor xnxn.
Jadikan nilai xn+1xn+1 sebagai nilai taksiran xx untuk iterasi berikutnya.
Hentikan proses iterasi jika telah memenuhi syarat yang ditampilkan pada Persamaan (6.33).

Berdasarkan algoritma tersebut, kita dapat menyusun fungsi sebuah fungsi untuk melakukan iterasi Jacobi. Berikut sintaks yang digunakan:

jacobi <- function(a, b, tol=1e-7, maxiter=100){
  n <- length(b)
  iter <- 0
  
  Dinv <- diag(1/diag(a))
  R <- a-diag(diag(a))
  x <- rep(0,n)
  x_new <- rep(tol, n)
  
  while(sqrt(sum(x_new-x)^2)>tol){
            if(iter>maxiter){
              warning("iterasi maksimum tercapai")
              break
            }
            x <- x_new
            x_new <- Dinv %*% (b - R %*% x)
            iter <- iter+1
  }
  return(list(X = x_new, iter=iter))
  
}

0.1.1 Berikut adalah penerpan fungsi `jacobi()` tersebut:

jacobi(A,b)

## $X
##      [,1]
## [1,]    4
## [2,]    1
## [3,]    6
## 
## $iter
## [1] 62

Contoh 6.10 Selesaikan sistem persamaan berikut menggunakan fungsi jacobi()

Jawab:

Matriks AA (matriks koefisien) berdasarkan sistem persamaan linier tersebut telah memenuhi syarat dari algoritma Jacobi (nilai diagonal utama dominan dibanding nilai lainnya pada satu kolom). Penyelesaian sistem persamaan tersebut, sebagai berikut:

A <- matrix(c(27,6,1,6,15,1,-1,2,54), 3)
b <- c(85,72,110)

jacobi(A,b)

## $X
##          [,1]
## [1,] 2.425476
## [2,] 3.573016
## [3,] 1.925954
## 
## $iter
## [1] 17

Nilai vektor x sesungguhnya dapat diperoleh menggunakan fungsi solve().

solve(A,b)

## [1] 2.425476 3.573016 1.925954

Berdasarkan hasil perhitungan, vektor x hasil iterasi memiliki nilai identik dengan nilai penyelesaian yang sebenarnya.

Perlu diperhatikan dalam penggunaan fungsi jacobi() syarat utama matriks haruslah terpenuhi, seperti: nilai diagonal matriks AA lebih besar dari nilai elemen lainnya pada satu kolom. Selain itu, nilai diagonal matriks DD tidak boleh sama dengan nol agar inver matriks DD dapat diperoleh. Jika syarat-syarat tersebut terpenuhi, maka metode Jacobi dapat diterapkan. Jika tidak terpenuhi, maka penyelesaian yang konvergen mungkin masih dapat diperoleh meskipun penulis tidak dapat menjamin hal tersebut dapat terjadi.

Iterasi Gauss-Seidel

Metode iterasi Gauss-Seidel melakukan dekomposisi pada matriks AA menjadi matriks segitiga atas UU dan matriks segitiga bawah LL. Dekomposisi ini tidak sama dengan dekomposisi LU pada Chapter 6.4.1. Matriks UU pada metode Gauss-Seidel merupakan elemen (entri) matriks AA pada bagian atas diagonal utama, sedangkan matriks LL merupakan elemen diagonal utama dan bagian bawah diagonal utama matriks AA. Elemen selain yang penulis sebutkan pada kedua matriks tersebut akan bernilai nol. Persamaan iterasi Gauss-Seidel ditampilkan pada Persamaan (6.39).

Syarat agar suatu sistem persamaan linier dapat diselesaikan menggunakan metode Gauss-Seidel adalah matriks harus memiliki nilai diagonal utama yang dominan. Maksudnya, nilai absolut diagonal utama lebih besar dari jumlah nilai absolut elemen lainnya dalam satu kolom. Jika syarat ini tidak terpenuhi maka metode ini tidak akan memperoleh penyelesaian yang konvergen.

Contoh 6.11 Selesaikan sistem persamaan pada Contoh 6.10 menggunakan iterasi Gauss-Seidel!

Jawab:

Kita akan kembali menggunakan bantuan R untuk melakukan kalkulasi pada proses iterasi Gauss-Seidel. Kita telah melakukan pengecekan pada sistem persamaan linier pada contoh tersebut dan menghasilkan kesimpulan bahwa persamaan linier tersebut dapat diselesaikan dengan metode Gauss-Seidel. Langkah selanjutnya adalah membentuk matriks LL dan UU.

# membentuk matriks U dan L dari matriks A
(L <- U <- A)

##      [,1] [,2] [,3]
## [1,]   27    6   -1
## [2,]    6   15    2
## [3,]    1    1   54

# membentuk matriks L dari entri bagian bawah diagonal utama matriks A
L[upper.tri(A, diag=FALSE)]<-0
L

##      [,1] [,2] [,3]
## [1,]   27    0    0
## [2,]    6   15    0
## [3,]    1    1   54

# membentuk matriks U dari entri bagian atas diagonal utama matriks A
U[lower.tri(A, diag=TRUE)]<-0
U

##      [,1] [,2] [,3]
## [1,]    0    6   -1
## [2,]    0    0    2
## [3,]    0    0    0

0.1.2 Selanjutya lakukan invers terhadap matriks L menggunakn fungsi `solve()`.

(Linv <- solve(L))

##               [,1]         [,2]       [,3]
## [1,]  0.0370370370  0.000000000 0.00000000
## [2,] -0.0148148148  0.066666667 0.00000000
## [3,] -0.0004115226 -0.001234568 0.01851852

Tetapkan nilai estimasi awal dan nilai toleransi yang dikehendaki. Nilai toleransi pada proses ini ditetapkan sebesar 10−710−7.

# tebakan awal nilai x
(x <- rep(0, length(b)))

## [1] 0 0 0

Lakukan iterasi menggunakan Persamaan (6.39).

0.1.3 ◾iterasi 1◾

(x1 <- Linv %*% (b - U %*% x))

##          [,1]
## [1,] 3.148148
## [2,] 3.540741
## [3,] 1.913169

# akar jumlah kuadrat
sqrt(sum(x1-x)^2)

## [1] 8.602058

0.1.4 ◾iterasi 2◾

(x2 <- Linv %*% (b - U %*% x1))

##          [,1]
## [1,] 2.432175
## [2,] 3.572041
## [3,] 1.925848

# akar jumlah kuadrat
sqrt(sum(x2-x1)^2)

## [1] 0.6719939

Iterasi terus dilakukan sampai dengan nilai akar jumlah kuadrat lebih kecil dari nilai toleransi. Setelah iterasi ke-7 diperoleh nilai vektor x sebesar:

0.2 Algoritma Iterasi Gauss-Seidel

Masukkan matriks AA, dan vektor BB beserta ukurannya nn.
Lakukan dekomposisi LU, dimana matriks LL merupakan matriks segitiga bawah dengan nilai entri diagonal utama matriks AA dan bagian bawah diagonalnya dan matriks UU merupakan matriks segitiga atas dengan entri berasal dari elemen atas diagonal utama matriks AA. Isi elemen lain yang tidak disebut pada kedua matriks tersebut dengan nol.
Tetapkan vektor xx estimasi.
Tetapkan nilai toleransi maksimum yang dapat diterima.
Lakukan iterasi menggunakan Persamaan (6.39).
Hitung akar jumlah kuadrat dari vektor xn+1xn+1 dan vektor xnxn.
Jadikan nilai xn+1xn+1 sebagai nilai taksiran xx untuk iterasi berikutnya.
Hentikan proses iterasi jika telah memenuhi syarat yang ditampilkan pada Persamaan (6.33).

Berdasarkan algoritma tersebut, kita dapat menyusun fungsi sebuah fungsi untuk melakukan iterasi Gauss-Seidel. Berikut sintaks yang digunakan:

gauss_seidel <- function(a, b, tol=1e-7, maxiter=100){
  n <- length(b)
  iter <- 0
  
  
  L <- U <- a
  L[upper.tri(a, diag=FALSE)] <- 0
  U[lower.tri(a, diag=TRUE)] <- 0
  Linv <- solve(L)
  
  x <- rep(0,n)
  x_new <- rep(tol, n)
  
  while(sqrt(sum(x_new-x)^2)>tol){
            if(iter>maxiter){
              warning("iterasi maksimum tercapai")
              break
            }
            x <- x_new
            x_new <- Linv %*% (b - U %*% x)
            iter <- iter+1
  }
      return(list(X = x_new, iter=iter))
}

Contoh 6.12 Selesaikan sistem persamaan pada Contoh 6.10 menggunakan fungsi gauss_seidel()!

0.2.0.1 Jawab:

Penyelesaiansistem persamaan linier tersebut menggunakan fungsi gauss_seidel() disajikan pada sintaks berikut:

gauss_seidel(A,b)

## $X
##          [,1]
## [1,] 2.425476
## [2,] 3.573016
## [3,] 1.925954
## 
## $iter
## [1] 7

Metode Iterasi; Uraian Iterasi Jacobi dan Iterasi Gauss-Seidel

Shafira Halmahera

14/11/2021

Metode Iterasi

Iterasi Jacobi

0.0.1 ◾iterasi 1◾

0.0.2 ◾iterasi 2◾

0.0.3 ◾iterasi 3◾

0.1 Algoritma Iterasi Jacobi

0.1.1 Berikut adalah penerpan fungsi `jacobi()` tersebut:

Iterasi Gauss-Seidel

0.1.2 Selanjutya lakukan invers terhadap matriks L menggunakn fungsi `solve()`.

0.1.3 ◾iterasi 1◾

0.1.4 ◾iterasi 2◾

0.2 Algoritma Iterasi Gauss-Seidel

0.2.0.1 Jawab:

0.3 $Referensi$

Metode Iterasi; Uraian Iterasi Jacobi dan Iterasi Gauss-Seidel

Shafira Halmahera

14/11/2021

Metode Iterasi

Iterasi Jacobi

0.0.1 ◾iterasi 1◾

0.0.2 ◾iterasi 2◾

0.0.3 ◾iterasi 3◾

0.1 Algoritma Iterasi Jacobi

0.1.1 Berikut adalah penerpan fungsi jacobi() tersebut:

Iterasi Gauss-Seidel

0.1.2 Selanjutya lakukan invers terhadap matriks L menggunakn fungsi solve().

0.1.3 ◾iterasi 1◾

0.1.4 ◾iterasi 2◾

0.2 Algoritma Iterasi Gauss-Seidel

0.2.0.1 Jawab:

0.3 ReferensiReferensi

0.1.1 Berikut adalah penerpan fungsi `jacobi()` tersebut:

0.1.2 Selanjutya lakukan invers terhadap matriks L menggunakn fungsi `solve()`.

0.3 $Referensi$