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 \(x^n\) 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 matrik \(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

dan vektor 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.

Contoh 6.9 Selesaikan sistem persamaan berikut menggunakan iterasi Jacobi!

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.0000 0.000
## [2,]  0.0 0.1429 0.000
## [3,]  0.0 0.0000 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.000
## [2,] 5.571
## [3,] 6.875

iterasi 2

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

##         [,1]
## [1,]  1.6464
## [2,] -0.6429
## [3,]  3.7857

iterasi 3

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

##       [,1]
## [1,] 5.986
## [2,] 2.938
## [3,] 6.910

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

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 xx akhir sebagai berikut:

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

Contoh 6.10 Selesaikan sistem persamaan berikut menggunakan fungsi jacobi()

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] 2.425 3.573 1.926

Berdasarkan hasil perhitungan, vektor xx 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,]   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

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

(Linv <- solve(L))

##            [,1]      [,2]    [,3]
## [1,]  0.0370370  0.000000 0.00000
## [2,] -0.0148148  0.066667 0.00000
## [3,] -0.0004115 -0.001235 0.01852

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

## [1] 0 0 0

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:

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#iteratif

Metode Iterasi Jacobi dan Gauss-Seidel pada Aljabar Linier

Imamatul Khoiriyah/Prof. Dr. Suhartono, M.Kom

10 November 2021

Metode Iterasi

Iterasi Jacobi

Iterasi Gauss-Seidel