Algoritma - Metode Bisection

Metode bisection dimulai dengan menghitung titik tengah, \(\mathrm{m=\frac {a+b}{2}}\) dari interval. Selanjutnya, fungsi dievaluasi pada titik f(m). Sesuai teorema Bolzano, jika f(a) dan f(m) memiliki tanda yang berlawanan, metode bisection menggantikan nilai b dengan titik tengah yang dihitung (m). Begitu juga jika f (b) dan f(m) memiliki tanda yang berlawanan, a akan diganti dengan titik tengah (m). Langkah ini memastikan masih ada root yang terkandung dalam interval. Prosedur kemudian berlanjut ke iterasi berikutnya. Solusinya dikatakan ditemukan setelah fungsinya sama dengan 0 pada f(m).

Sehingga jika dirangkum cara kerja dari metode bisection tersebut adalah :

Tetapkan dua nilai a dan b sehingga f(a)f(b) < 0.

1. Jika |b – al| ≤ ε maka stop.
2. Tetapkan \(\mathrm{m=\frac {a+b}{2}}\) ; jika f(m) = 0 maka stop.
3. Jika f(a)f(m) < 0 maka tetapkan b = m; selainnya, tetapkan a = m.
4. Lanjutkan ke langkah 1.

Flowchart

Program R - Metode Bisection

Misal akan dicari akar persamaan dari fungsi \(\mathrm{log(x)-e^{-x}}\).

func <- function(x) {
  log(x) - exp(-x)
}

curve(func, xlim=c(0,7), col='red', lwd=1.5, lty=2)
abline(h=0)
abline(v=0)

metodebisection <- function(func, a, b, tol = 1e-5, max.iter = 100) {
    fa <- func(a)
    fb <- func(b)
    iter <- 0
    
    if(fa*fb<0) {
      while ((abs(b-a) > tol) && (iter < max.iter)) {
         m <- (a+b)/2   #menghitung nilai tengah m
         fm <- func(m)
         
         if(fm==0){  #jika fm=0 maka stop dan kembalikan nilai
           return(m)
         }
         
         else{  #jika fm tidak sama dengan 0, iterasi
           iter <- iter+1
           cat("At iteration", iter, "value of x is:", m, "\n")
         
            if(fa*fm<0){ #fa dan fm berbeda tanda
              b <- m 
            }
            else{
              a <- m
            }
         }
      }
    }
    else { 
      cat("Change initiation that fulfills \n")
    }
# output depends on success of algorithm
   if (abs(b-a) > tol) {
       cat("Algorithm failed to converge\n")
       return(NULL)
       } else {
            cat("Algorithm converged\n")
            return(m)
            }
     }

Perhitungan akar persamaan dengan Fungsi metodebisection

Selanjutnya akan dicari akar persamaan dari fungsi \(\mathrm{log(x)-e^{-x}}\) pada interval [1,2] dengan fungsi metodebisection yang telah dibuat

metodebisection(func, 1, 2)

## At iteration 1 value of x is: 1.5 
## At iteration 2 value of x is: 1.25 
## At iteration 3 value of x is: 1.375 
## At iteration 4 value of x is: 1.3125 
## At iteration 5 value of x is: 1.28125 
## At iteration 6 value of x is: 1.296875 
## At iteration 7 value of x is: 1.304688 
## At iteration 8 value of x is: 1.308594 
## At iteration 9 value of x is: 1.310547 
## At iteration 10 value of x is: 1.30957 
## At iteration 11 value of x is: 1.310059 
## At iteration 12 value of x is: 1.309814 
## At iteration 13 value of x is: 1.309692 
## At iteration 14 value of x is: 1.309753 
## At iteration 15 value of x is: 1.309784 
## At iteration 16 value of x is: 1.309799 
## At iteration 17 value of x is: 1.309807 
## Algorithm converged

## [1] 1.309807

Output dari fungsi metodebisection menunjukkan bahwa akar dari fungsi \(\mathrm{log(x)-e^{-x}}\) terletak di x=1.309807.

R juga telah menyediakan perhitungan bagi metode bisection dalam package NLRoot dan fungsi BFfzero(). Untuk mencocokan hasil dari fungsi metodebisection, akan digunakan fungsi BFfzero() dari package NLRoot

library(NLRoot)

BFfzero(func, 1, 2)

## [1] 1
## [1] 1.309799
## [1] -4.045236e-07
## [1] "finding root is successful"

Output dari fungsi BFfzero menunjukkan nilai yang sama dengan fungsi metodebisection yang telah dibuat yaitu akar persamaan terletak pada x=1.309799

Program R - Metode Newton-Raphson

newtonraphson <- function(ftn, x0, tol = 1e-5, max.iter = 100) {
    x <- x0
    fx <- ftn(x)
    iter <- 0
   while ((abs(fx[1]) > tol) && (iter < max.iter)) {
         x <- x - fx[1]/fx[2]
         fx <- ftn(x)
         iter <- iter + 1
         cat("At iteration", iter, "value of x is:", x, "\n")
         }
   # output depends on success of algorithm
   if (abs(fx[1]) > tol) {
       cat("Algorithm failed to converge\n")
       return(NULL)
       } else {
            cat("Algorithm converged\n")
            return(x)
            }
     }

Perhitungan akar persamaan dengan Fungsi newtonraphson

Akan dilakukan perhitungan akar persamaan dengan soal yang sama dengan metode bisection yaitu \[\mathrm{f(x)=log(x)-e^{-x}}\]

ftn <- function(x) {
# returns function value and its derivative at x
     fx <- log(x) - exp(-x)  # fungsi f(x)
     dfx <- 1/x + exp(-x)   # turunan pertama f(x)
     return(c(fx, dfx))
}

newtonraphson(ftn, 3, 1e-4)

## At iteration 1 value of x is: 0.2624136 
## At iteration 2 value of x is: 0.7224658 
## At iteration 3 value of x is: 1.156032 
## At iteration 4 value of x is: 1.299908 
## At iteration 5 value of x is: 1.309759 
## Algorithm converged

## [1] 1.309759

Kesimpulan : Dari perhitungan dengan metode Newton-Raphson, didapatkan nilai akar persamaan yang sama dengan metode bisection yaitu x=1.309759

Program R - Metode Secant

secant <- function(ftn, x0, x1, tol = 1e-9, max.iter = 100) {
  xa <- x0
  fxa <- ftn(xa)
  xb <- x1
  fxb <- ftn(xb)
  iter <- 0
  while ((abs(xb-xa) > tol) && (iter < max.iter)) {
    xt <- fxb*((xb-xa)/(fxb-fxa))
    xc <- xb-xt
    # fxc <- ftn(xc)
    iter <- iter + 1
    cat("At iteration", iter, "value of x2 is:", xc, "\n")
    xa <- xb
    xb <- xc
    fxa <- ftn(xa)
    fxb <- ftn(xb)
  }
  
   # output depends on success of algorithm
 if (abs(xb-xa) > tol) {
     cat("Algorithm failed to converge\n")
     return(NULL)
  } else {
    cat("Algorithm converged\n")
    return(xb)
    }
}

Perhitungan akar persamaan dengan Fungsi secant

ftnsec <- function(x) return(log(x) - exp(-x))
secant(ftnsec, 1, 2, tol = 1e-6)

## At iteration 1 value of x2 is: 1.39741 
## At iteration 2 value of x2 is: 1.285476 
## At iteration 3 value of x2 is: 1.310677 
## At iteration 4 value of x2 is: 1.309808 
## At iteration 5 value of x2 is: 1.3098 
## At iteration 6 value of x2 is: 1.3098 
## Algorithm converged

## [1] 1.3098

Kesimpulan : Dari perhitungan dengan metode Secant, didapatkan nilai akar persamaan yang sama dengan metode Bisection dan Newton-Raphson yaitu x=1.3098

Program R - Metode Fixed Point

fixedpoint <- function(ftn, x0, tol = 1e-9, max.iter = 100) {
  xold <- x0
  xnew <- ftn(xold)
  iter <- 1
  cat("At iteration 1 value of x is:", xnew, "\n")
  
  while ((abs(xnew-xold) > tol) && (iter < max.iter)) {
      xold <- xnew;
      xnew <- ftn(xold);
      iter <- iter + 1
      cat("At iteration", iter, "value of x is:", xnew, "\n")
      }
  
  if (abs(xnew-xold) > tol) {
      cat("Algorithm failed to converge\n")
      return(NULL)
      } else {
           cat("Algorithm converged\n")
           return(xnew)
           }
 }

ftn1 <- function(x) return(exp(exp(-x)))
fixedpoint(ftn1, 2, tol = 1e-6)

## At iteration 1 value of x is: 1.144921 
## At iteration 2 value of x is: 1.374719 
## At iteration 3 value of x is: 1.287768 
## At iteration 4 value of x is: 1.317697 
## At iteration 5 value of x is: 1.307022 
## At iteration 6 value of x is: 1.310783 
## At iteration 7 value of x is: 1.309452 
## At iteration 8 value of x is: 1.309922 
## At iteration 9 value of x is: 1.309756 
## At iteration 10 value of x is: 1.309815 
## At iteration 11 value of x is: 1.309794 
## At iteration 12 value of x is: 1.309802 
## At iteration 13 value of x is: 1.309799 
## At iteration 14 value of x is: 1.3098 
## Algorithm converged

## [1] 1.3098