Root Finding - Pemrograman Statistika Pertemuan 9

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 digunakan untuk menyimpan akar-akar persamaan dari iterasi sebelumnya
    xold <- xnew
    # xnew digunakan untuk menghitung akar-akar persamaan pada iterasi yang sedang berjalan
    xnew <- ftn(xold) #ingat ftn bentuknya fungsi
    # iter digunakan untuk menyimpan banyaknya iterasi
    iter <- iter + 1
    cat("At iteration", iter, "value of x is:", xnew, "\n")
  }
  # output bergantung pada kesuksesan algoritma
  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, 3, tol=1e-3)

At iteration 1 value of x is: 1.051047 
At iteration 2 value of x is: 1.41846 
At iteration 3 value of x is: 1.273905 
At iteration 4 value of x is: 1.322782 
At iteration 5 value of x is: 1.305248 
At iteration 6 value of x is: 1.311413 
At iteration 7 value of x is: 1.30923 
At iteration 8 value of x is: 1.310001 
Algorithm converged
[1] 1.310001

ftn3 <- function(x) return(x+log(x)-exp(-x))
fixedpoint(ftn3, 2, tol = 1e-6, max.iter = 20)

At iteration 1 value of x is: 2.557812 
At iteration 2 value of x is: 3.41949 
At iteration 3 value of x is: 4.616252 
At iteration 4 value of x is: 6.135946 
At iteration 5 value of x is: 7.947946 
At iteration 6 value of x is: 10.02051 
At iteration 7 value of x is: 12.3251 
At iteration 8 value of x is: 14.83673 
At iteration 9 value of x is: 17.53383 
At iteration 10 value of x is: 20.39797 
At iteration 11 value of x is: 23.4134 
At iteration 12 value of x is: 26.56671 
At iteration 13 value of x is: 29.84637 
At iteration 14 value of x is: 33.24243 
At iteration 15 value of x is: 36.74626 
At iteration 16 value of x is: 40.3503 
At iteration 17 value of x is: 44.04789 
At iteration 18 value of x is: 47.83317 
At iteration 19 value of x is: 51.70089 
At iteration 20 value of x is: 55.64637 
Algorithm failed to converge
NULL

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 Newton Raphson

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

At iteration 1 value of x is: 1.295082 
At iteration 2 value of x is: 1.30971 
At iteration 3 value of x is: 1.3098 
Algorithm converged
[1] 1.3098

ftn1 <- function(x) {
# returns function value and its derivative at x
fx <- 4*x^2 - 3*x - 7 # fungsi f(x)
dfx <- 4*2*x - 3 # turunan pertama f(x)
return(c(fx, dfx))
}

newtonraphson(ftn1,3)

At iteration 1 value of x is: 2.047619 
At iteration 2 value of x is: 1.776479 
At iteration 3 value of x is: 1.75025 
At iteration 4 value of x is: 1.75 
Algorithm converged
[1] 1.75

Fungsi Lain yang bisa kita coba

library(Deriv)
newtonr <- function (fx , x0 =1){
  fx1 <- Deriv (fx ,"x") # turunan pertama
  err <- 1000
  while (err >10^(-5)){
    x <- x0
    f0<- eval(fx)
    f1 <- eval(fx1)
    x1 <- x0 - f0/f1
    err <- abs(x1-x0)
    x0 <- x1
  }
  return (x1)
}

fx <-expression(log(x) - exp(-x))
newtonr(fx,3.2)

[1] 1.3098

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)
}
if (abs(xb-xa) > tol) {
cat("Algorithm failed to converge\n")
return(NULL)
} else {
cat("Algorithm converged\n")
return(xb)
}
}
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

Metode Bisection

bisection <- function(f, xl, xr, tol = 1e-7,max.iter = 100) {
  # Jika tanda dari hasil evaluasi fungsi pada titik xl dan xr berbeda maka program dihentikan
  if (!(f(xl) > 0) && (f(xr) < 0)) {
    stop('signs of f(xl) and f(xr) differ')
  }
  
  for (iter in 1:max.iter) {
    xm <- (xl + xr) / 2 # menghitung nilai tengah
    
    cat("At iteration", iter, "value of x is:", xm, "\n")       
    #Jika fungsinya sama dengan 0 di titik tengah atau titik tengah di bawah toleransi yang diinginkan, hentikan dan keluarkan nilai tengah sebagai akar
    if ((f(xm) == 0) || abs(xr - xl) < tol) {
      return(xm)
    }
    # Jika diperlukan iterasi lain,
    # periksa tanda-tanda fungsi pada titik xm dan xl dan tetapkan kembali
    # xl atau xr sebagai titik tengah yang akan digunakan pada iterasi berikutnya.    
    ifelse(sign(f(xm)) == sign(f(xl)), 
           xl <- xm,xr <- xm)
  }
}
fbisec <- function(x) return(x^3-2*x-5)
bisection(fbisec, xl=-3, xr=3)

At iteration 1 value of x is: 0 
At iteration 2 value of x is: 1.5 
At iteration 3 value of x is: 2.25 
At iteration 4 value of x is: 1.875 
At iteration 5 value of x is: 2.0625 
At iteration 6 value of x is: 2.15625 
At iteration 7 value of x is: 2.109375 
At iteration 8 value of x is: 2.085938 
At iteration 9 value of x is: 2.097656 
At iteration 10 value of x is: 2.091797 
At iteration 11 value of x is: 2.094727 
At iteration 12 value of x is: 2.093262 
At iteration 13 value of x is: 2.093994 
At iteration 14 value of x is: 2.09436 
At iteration 15 value of x is: 2.094543 
At iteration 16 value of x is: 2.094635 
At iteration 17 value of x is: 2.094589 
At iteration 18 value of x is: 2.094566 
At iteration 19 value of x is: 2.094555 
At iteration 20 value of x is: 2.094549 
At iteration 21 value of x is: 2.094552 
At iteration 22 value of x is: 2.094551 
At iteration 23 value of x is: 2.094551 
At iteration 24 value of x is: 2.094552 
At iteration 25 value of x is: 2.094552 
At iteration 26 value of x is: 2.094551 
At iteration 27 value of x is: 2.094551 
[1] 2.094551

---

1. Statistika dan Sains Data, IPB University↩︎