Algoritma Metode Tabel

1. Tentukan interval pencarian \([a, b]\) dan jumlah titik \(n\) yang diinginkan.
2. Buat tabel berisi nilai \(x\) yang dibagi merata dalam interval tersebut.
3. Hitung \(f(x)\) untuk setiap \(x\).
4. Identifikasi nilai \(x\) yang menghasilkan \(f(x)\) terkecil (untuk mencari minimum) atau \(f(x)\) terbesar (untuk mencari maksimum).

Keunggulan dan Kekurangan

• Keunggulan:
  • Sederhana dan mudah diimplementasikan.
  • Tidak memerlukan syarat khusus pada fungsi.
• Kekurangan:
  • Tidak efisien untuk interval yang besar.
  • Akurasi tergantung pada jumlah titik \(n\) yang digunakan.

Fungsi R untuk Metode Tabel

table_method <- function(f, a, b, n = 100, method = "min") {
  x <- seq(a, b, length.out = n)
  y <- sapply(x, f)
  if (method == "min") {
    return(list(data=data.frame(x,y),x.opt=x[which.min(y)],y.opt=f(x[which.min(y)])))
  } else if (method == "max") {
    return(list(data=data.frame(x,y),x.opt=x[which.max(y)],y.opt=f(x[which.max(y)])))
  }
}

Contoh Implementasi

Misalkan fungsi \(f(x) = 3x^3 + 2x^{-1/2}\), kita ingin mencari nilai \(x\) yang menghasilkan \(f(x)\) minimum dalam interval \([-1, 1]\).

\[ f(x) = 3x^3 + 2x^{-1/2} \]

Kode R:

f <- function(x) 3*x^3+2*x^-1/2
table_method(f, -1, 1,n=10,method="min")

## $data
##             x         y
## 1  -1.0000000 -4.000000
## 2  -0.7777778 -2.697237
## 3  -0.5555556 -2.314403
## 4  -0.3333333 -3.111111
## 5  -0.1111111 -9.004115
## 6   0.1111111  9.004115
## 7   0.3333333  3.111111
## 8   0.5555556  2.314403
## 9   0.7777778  2.697237
## 10  1.0000000  4.000000
## 
## $x.opt
## [1] -0.1111111
## 
## $y.opt
## [1] -9.004115

Outputnya berupa data tabel dan nilai minimum \(f(x)\).

table_method(f, 0, 1,n=10,method="min")

## $data
##            x        y
## 1  0.0000000      Inf
## 2  0.1111111 9.004115
## 3  0.2222222 4.532922
## 4  0.3333333 3.111111
## 5  0.4444444 2.513374
## 6  0.5555556 2.314403
## 7  0.6666667 2.388889
## 8  0.7777778 2.697237
## 9  0.8888889 3.231996
## 10 1.0000000 4.000000
## 
## $x.opt
## [1] 0.5555556
## 
## $y.opt
## [1] 2.314403

Algoritma Metode Bisection

1. Tentukan interval \([a, b]\) di mana \(f(a) \cdot f(b) < 0\).
2. Hitung nilai tengah: \[ c = \frac{a+b}{2} \]
3. Periksa nilai \(f(c)\):
   • Jika \(f(c) = 0\), maka \(c\) adalah akar.
   • Jika \(f(a) \cdot f(c) < 0\), maka interval baru adalah \([a, c]\).
   • Jika \(f(c) \cdot f(b) < 0\), maka interval baru adalah \([c, b]\).
4. Ulangi langkah 2-3 hingga \(|b-a| < \text{toleransi}\).

Keunggulan dan Kekurangan

• Keunggulan:
  • Sederhana dan selalu konvergen jika syarat \(f(a) \cdot f(b) < 0\) terpenuhi.
• Kekurangan:
  • Lambat dibanding metode lain.
  • Membutuhkan fungsi kontinu pada interval tertentu.

Fungsi R untuk Metode Bisection

bisection_method <- function(f, a, b, tol = 1e-6, max_iter = 100) {
  if (f(a) * f(b) > 0) {
    stop("f(a) dan f(b) harus beda tanda.")
  }
  iter <- 0

  while (b - a > tol && iter < max_iter) {
    c <- (a + b) / 2
    if (f(c) == 0) {
      return(list(x.opt=c,y.opt=f(c)))
    }
    if (f(a) * f(c) < 0) {
      b <- c
    } else {
      a <- c
    }
    iter <- iter + 1
  }
  return(list(`function`=f,iter=iter,x.opt=mean(c(a, b)),y.opt=f(mean(c(a, b)))))
}

Contoh Implementasi

Misalkan fungsi \(f(x) = 3x^3 + 2x^{-1/2}\), kita ingin mencari akar dalam interval \([-1, 0]\).

Kode R:

 bisection_method(f, -1, 0)

## $`function`
## function(x) 3*x^3+2*x^-1/2
## <bytecode: 0x0000022d77f47390>
## 
## $iter
## [1] 20
## 
## $x.opt
## [1] -4.768372e-07
## 
## $y.opt
## [1] -2097152

Bila dibandingkan dengan metode tabel, bisection method menghasilkan nilai x yang jauh lebih meminimumkan y

#Atur max iter dan toleransi bisa mengubah hasil
bisection_method(f, -1, 0,max_iter = 1000,tol=1e-07)

## $`function`
## function(x) 3*x^3+2*x^-1/2
## <bytecode: 0x0000022d77f47390>
## 
## $iter
## [1] 24
## 
## $x.opt
## [1] -2.980232e-08
## 
## $y.opt
## [1] -33554432

Memperbesar max_iter dan memperkecil batas toleransi menghasilkan nilai yang lebih minimum

Keunggulan dan Kekurangan

• Keunggulan:
  • Cepat dan efisien untuk fungsi tertentu.
• Kekurangan:
  • Membutuhkan turunan \(f'(x)\).
  • Tidak selalu konvergen jika titik awal buruk atau fungsi memiliki lebih dari satu akar.

Fungsi R untuk Metode Newton-Raphson

newton_method <- function(f, df, x0, tol=1e-7, max_iter=100){
  iter <- 0
  xold<-x0
  xnew <- xold + 10*tol

  while(abs(xnew-xold)>tol){
    iter <- iter+1
    xold<-xnew
    xnew <- xold - f(xold)/df(xold)
  }
    root<-xnew
  if(iter>max_iter){
      cat("Error: Solusi tidak ditemukan karena iterasi > N mulai pada iterasi ke ",iter,"dengan x = ",round(xnew),"dan y = ",round(f(xnew)))
  }
  else{
      return(list(`function`=f, x.opt=root,y.opt=f(root), iter=iter))
}
  }  

Contoh Implementasi

Fungsi \(f(x) = 3x^3 + 2x^{-1/2}\) dan turunannya: \[ f'(x) = 9x^2 - x^{-3/2} \]

Kode R:

df<-Deriv::Deriv(f,"x")
newton_method(f,df,x0=0,max_iter=1000,tol=1e-4)

## Error: Solusi tidak ditemukan karena iterasi > N mulai pada iterasi ke  24872 dengan x =  0 dan y =  22797

Dalam kasus ini, algoritma mungkin tidak berhenti karena perbedaan antara x saat ini dan x sebelumnya selalu lebih besar dari toleransi. Ini mungkin terjadi karena fungsi dan turunannya tidak terdefinisi di sekitar akar yang diinginkan atau karena akar yang diinginkan tidak ada. Maka, bisa menggunakan metode bisection ataupun secant.

Keunggulan dan Kekurangan

• Keunggulan:
  • Tidak memerlukan turunan.
• Kekurangan:
  • Tidak secepat Newton-Raphson.

Fungsi R untuk Metode Secant

secant_method <- function(f, x, tol=1e-7, max_iter=100){
  iter <- 0
  xold <- x
  fxold <- f(x)
  x <- xold+10*tol

  while(abs(x-xold)>tol){
iter <- iter+1
fx <- f(x)
xnew <- x - fx*((x-xold)/(fx-fxold))
xold <- x
fxold <- fx
x <- xnew
  }
 if(iter>max_iter){
  cat("Error: Solusi tidak ditemukan karena iterasi > N mulai pada iterasi ke ",iter,"dengan x = ",round(xnew),"dan y = ",round(f(xnew)))
  }

else{
  root<-xnew
  return(list(`function`=f, x.opt=root,y.opt=f(root), iter=iter))
}
}

Contoh Implementasi

Fungsi \(f(x) = 3x^3 + 2x^{-1/2}\), nilai awal \(x_0 = -1, x_1 = 0\).

Kode R:

secant_method(f,x=8,max_iter=100)

## Error: Solusi tidak ditemukan karena iterasi > N mulai pada iterasi ke  17315 dengan x =  -1 dan y =  -2

Dalam kasus ini, algoritma secant juga tidak berhenti sehingga akar yang diinginkan tidak ada. Hal ini dapat diamati dari bentuk kurva yang terbagi dalam selang tertentu serta tiap selang secara sekilas cenderung susah menemukan titik optimum (baik minimum maupun maksimum).