Universitas : Universitas Islam Negeri Maulana Malik Ibrahim Malang

Jurusan : Teknik Informatika

Metode Iterasi

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.

dimana xn merupakan iterasi ke-n dari algoritma dan t0 merupakan nilai toleransi maksimum yang diterima

Iterasi Jacobi

Untuk menyelesaikan matriks menggunakan metode iterasi, kita dapat mulai dengan premis terdapat matriks A dan vektor x dan b, sehingga Ax = 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 :

Persamaan (6.37) merupakan persamaan yang dapat kita gunakan untuk memperoleh nilai x. Jika kita menulis kembali persamaan tersebut, maka kita akan memperoleh persamaan yang digunakan sebagai acuan iterasi Jacobi.

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.

Jawab

Berdasarkan matriks A (matriks koefisien), kita dapat memastikan bahwa matriks tersebut memiliki nilai dominan pada elemen diagonal utama. Sebagai contoh:

Untuk mempermudah proses iterasi, kita akan menggunakan bantuan R untuk melakukan komputasi. Langkah pertama yang perlu dilakukan adalah menyiapkan matriks A, vektor b, dan vektor x (nilai taksiran awal).

(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).

Iterasi 1

(x1 <- Dinv %*% (b-R%*%x))
##          [,1]
## [1,] 8.000000
## [2,] 5.571429
## [3,] 6.875000

Iterasi 2

(x2 <- Dinv %*% (b-R%*%x1))
##            [,1]
## [1,]  1.6464286
## [2,] -0.6428571
## [3,]  3.7857143

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

Selama proses iterasi nilai tersebut terus mengecil. Iterasi dihantikan jika nilai akar jumlah kuadrat tersebut lebih kecil dari nilai toleransi. Pada contoh ini digunakan nilai toleransi 10−7.

Proses iterasi berlangsung sampai dengan iterasi ke-62 dengan nilai x akhir sebagai berikut:

Algoritma Iterasi Jacobi

  1. Masukkan matriks AA, dan vektor BB beserta ukurannya nn.

  2. Hitung invers matriks DD, dimana nilai invernya merupakan matriks diagonal dari satu per diagonal utama matriks AA.

  3. Hitung matriks RR, dimana RR merupakan selisih matriks AA dikurangi dengan matriks diagonal dengan entri dari diagonal utama matriks AA.

  4. Tetapkan vektor xx estimasi.

  5. Tetapkan nilai toleransi maksimum yang dapat diterima.

  6. Lakukan iterasi menggunakan Persamaan (6.38).

  7. Hitung akar jumlah kuadrat dari vektor xn+1xn+1 dan vektor xnxn.

  8. Jadikan nilai xn+1xn+1 sebagai nilai taksiran xx untuk iterasi berikutnya.

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

Berikut adalah penerpan fungsi jacobi() tersebut:

jacobi(A,b)

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

Jawab Matriks A (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.425
## [2,] 3.573
## [3,] 1.926
## 
## $iter
## [1] 17

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

solve(A,b)
## [1] 4 1 6

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 A lebih besar dari nilai elemen lainnya pada satu kolom. Selain itu, nilai diagonal matriks D tidak boleh sama dengan nol agar inver matriks D 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 A menjadi matriks segitiga atas U dan matriks segitiga bawah L. Dekomposisi ini tidak sama dengan dekomposisi LU pada Chapter 6.4.1. Matriks U pada metode Gauss-Seidel merupakan elemen (entri) matriks A pada bagian atas diagonal utama, sedangkan matriks L merupakan elemen diagonal utama dan bagian bawah diagonal utama matriks A. 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 L dan U.

# membentuk matriks U dan L dari matriks A
(L <- U <- A)
##      [,1] [,2] [,3]
## [1,]    5    2    3
## [2,]    2    7    4
## [3,]    1    3    8
# membentuk matriks L dari entri bagian bawah diagonal utama matriks A
L[upper.tri(A, diag=FALSE)]<-0
L
##      [,1] [,2] [,3]
## [1,]    5    0    0
## [2,]    2    7    0
## [3,]    1    3    8
# membentuk matriks U dari entri bagian atas diagonal utama matriks A
U[lower.tri(A, diag=TRUE)]<-0
U
##      [,1] [,2] [,3]
## [1,]    0    2    3
## [2,]    0    0    4
## [3,]    0    0    0

Selanjutya lakukan invers terhadap matriks L menggunakan fungsi solve().

(Linv <- solve(L))
##              [,1]        [,2]  [,3]
## [1,]  0.200000000  0.00000000 0.000
## [2,] -0.057142857  0.14285714 0.000
## [3,] -0.003571429 -0.05357143 0.125

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

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

Lakukan iterasi menggunakan Persamaan (6.39).

Iterasi 1

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

##       [,1]
## [1,] 3.148
## [2,] 3.541
## [3,] 1.913

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

## [1] 8.602

Iterasi 2

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

##       [,1]
## [1,] 2.432
## [2,] 3.572
## [3,] 1.926

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

## [1] 0.672

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

Algoritma Iterasi Gauss-Seidel

  1. Masukkan matriks A, dan vektor B beserta ukurannya n

  2. Lakukan dekomposisi LU, dimana matriks L merupakan matriks segitiga bawah dengan nilai entri diagonal utama matriks A dan bagian bawah diagonalnya dan matriks U merupakan matriks segitiga atas dengan entri berasal dari elemen atas diagonal utama matriks
    A. Isi elemen lain yang tidak disebut pada kedua matriks tersebut dengan nol.

  3. Tetapkan vektor x estimasi.

  4. Tetapkan nilai toleransi maksimum yang dapat diterima.

  5. Lakukan iterasi menggunakan Persamaan (6.39).

  6. Hitung akar jumlah kuadrat dari vektor x^n +1 dan vektor x^n

  7. Jadikan nilai x^n +1 sebagai nilai taksiran x untuk iterasi berikutnya.

  8. 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()!

jawab

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

gauss_seidel(A,b)
## $X
##       [,1]
## [1,] 2.425
## [2,] 3.573
## [3,] 1.926
## 
## $iter
## [1] 7

Referensi

https://bookdown.org/moh_rosidi2610/Metode_Numerik/linearaljabar.html#dekomposisimatriks