Root Finding

Pendahuluan

Suatu nilai x yang memenuhi persamaan f(x) = 0 disebut sebagai akar persamaan. Root Finding atau penentuan akar persamaan dapat dikerjakan dengan beberapa metode. Beberapa metode yang dapat digunakan antara lain metode fixed point, metode newton raphson, metode secant, dan metode bisection.

Metode Fixed Point

Metode fixed point adalah metode iteratif untuk menyelesaikan persamaan dengan bentuk f(x) = x. Metode ini membangkitkan sekuen titik-titik \(x_0\), \(x_1\), \(x_2\), … \(x_n\) yang diharapkan konvergen terhadap suatu titik sehingga f(a)=a. Suatu perkiraan nilai awal \(x_0\), untuk menentukan dugaan berikutnya, yaitu \(x_1\)=\(f(x_0)\), dan terus berulang. Proses iteratif relatif lambat.

Argumen dalam fungsi adalah:

  • ftn berupa function di R
  • tol merupakan nilai toleransi dengan default 1e-9
  • max.iter iterasi maksimum dengan nilai maksimum 100
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 digunaka untuk mengitung akar-akar persamaan ada iterasi yang sedang berjalan
      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)
           }
}

Menentukan akar persamaan dari
\[\mathrm{f(x)} = e^{e^{-x}}\]

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

Menentukan akar persamaan dari
\[\mathrm{f(x)} = x+log(x)-e^{-x}\]

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

Untuk menyelesaikan persamaan dengan bentuk f(x) = 0, yaitu menentukan akar dari persamaan itu. Suatu perkiraan nilai awal \(x_0\) untuk menentukan akar persamaan. Sekuen nilai-nilai \(x_0, x_1, x_2, x_3\), … diperoleh secara iteratif yang konvergen terhadap nilai akar yang sebenarnya. Proses konvergen lebih cepat karena nilai awal iterasi dapat diduga untuk memperoleh nilai pendekatan terhadap nilai sebenarnya.

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

Menentukan akar persamaan dari
\[\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

Menentukan akar persamaan dari
\[\mathrm{f(x)} = 4x^2 - 3x-7\]

ftn <- 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(ftn, 3, 1e-4)
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

Menggunakan package 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)
}

Menentukan akar persamaan dari
\[\mathrm{f(x)} = log(x)-e^{-x}\]

fx <- expression (log(x) - exp(-x))
newtonr(fx,3)
[1] 1.3098

Menentukan akar persamaan dari
\[\mathrm{f(x)} = 4x^2 - 3x-7\]

fx <- expression (4*x^2 - 3*x - 7)
newtonr(fx,3)
[1] 1.75

Metode Secant

Tahapan dalam metode secant dapat dituliskan sebagai berikut:

  • Tentukan nilai \(x_1\) dan \(x_2\)
  • Memulai perulangan
  • Hitung nilai x selanjutnya menggunakan formula iterasi

\[\mathrm{x_{i+2}} = x_{i+1}-f(x_{i+1}) \frac{x_{i+1}-x_i}{f(x_{i+1})-f(x_i)}\]

  • Buang titik \(x_i\)
  • Ulangi terus sampai tingkat presisi yang diinginkan
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)
  }
}

Menentukan akar persamaan dari
\[\mathrm{f(x)} = log(x)-e^{-x}\]

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

Tahapan metode bisection:

Tetapkan dua nilai \(x_i\) dan \(x_r\), sehingga \(f(x_i)f(x_r)<0\)

  • Jika \(|x_r-x_i| < e\) maka stop
  • Tetapkan \(x_m = (x_i+x_r)/2\) jika \(f(x_m)=0\) maka stop
  • Jika \(f(x_i)f(x_m)<0\) maka tetapkan \(x_r=x_m\), selainnya tetapkan \(x_i=x_m\)
  • Lanjutkan ke langkah 1

Contoh fungsi yang digunakan untuk metode ini adalah \[\mathrm{f(x)} = 4x^2-3x-7\]

Plot

func <- function(x) {
  4*x^2 - 3 * x - 7
}

curve(func, xlim=c(-5,5), col='blue', lwd=1.5, lty=2)
abline(h=0)
abline(v=0)

library(NLRoot)
BFfzero(func, 0, 3)
[1] 1
[1] 1.749998
[1] -1.678466e-05
[1] "finding root is successful"

Fungsi Bisection dengan Iterasi

bisection <- function(ftn, xl, xr, tol=1e-5, max.iter=100){
  fxl <- ftn(xl)
  fxr <- ftn(xr)
  iter <- 0
  
  if (fxl*fxr<0){
    while((abs(xr-xl) > tol) && (iter < max.iter)){
      xm <- (xl+xr)/2
      fxm <- ftn(xm)
      
      if(fxm == 0) {
        return(xm)
        } else {
          iter <- iter + 1
          cat("At iteration", iter, "value of x is:", xm, "\n")
          
          if (fxl*fxm<0) {
            xr = xm
            } else {
              xl=xm
            }
        }
      }
    } else {
      cat("Change initiation that fulfills \n")
      }
  
  if (abs(xr-xl) > tol) {
    cat("Algorithm failed to converge\n")
    return(NULL)
    } else {
      cat("Algorithm converged\n")
      return(xm)
      }
}

Mencari akar persamaan dari \[\mathrm{f(x)} = 4x^2-3x-7\]

ftnbisection <- function(x) return(( 4*x^2 - 3 * x - 7))
bisection(ftnbisection,0,3)
At iteration 1 value of x is: 1.5 
At iteration 2 value of x is: 2.25 
At iteration 3 value of x is: 1.875 
At iteration 4 value of x is: 1.6875 
At iteration 5 value of x is: 1.78125 
At iteration 6 value of x is: 1.734375 
At iteration 7 value of x is: 1.757812 
At iteration 8 value of x is: 1.746094 
At iteration 9 value of x is: 1.751953 
At iteration 10 value of x is: 1.749023 
At iteration 11 value of x is: 1.750488 
At iteration 12 value of x is: 1.749756 
At iteration 13 value of x is: 1.750122 
At iteration 14 value of x is: 1.749939 
At iteration 15 value of x is: 1.750031 
At iteration 16 value of x is: 1.749985 
At iteration 17 value of x is: 1.750008 
At iteration 18 value of x is: 1.749996 
At iteration 19 value of x is: 1.750002 
Algorithm converged
[1] 1.750002

Mencari akar persamaan dari \[\mathrm{f(x)} = x^3-2x-5\]

func <- function(x) {
  x^3 - 2 * x - 5
}
bisection(func,2,3)
At iteration 1 value of x is: 2.5 
At iteration 2 value of x is: 2.25 
At iteration 3 value of x is: 2.125 
At iteration 4 value of x is: 2.0625 
At iteration 5 value of x is: 2.09375 
At iteration 6 value of x is: 2.109375 
At iteration 7 value of x is: 2.101562 
At iteration 8 value of x is: 2.097656 
At iteration 9 value of x is: 2.095703 
At iteration 10 value of x is: 2.094727 
At iteration 11 value of x is: 2.094238 
At iteration 12 value of x is: 2.094482 
At iteration 13 value of x is: 2.094604 
At iteration 14 value of x is: 2.094543 
At iteration 15 value of x is: 2.094574 
At iteration 16 value of x is: 2.094559 
At iteration 17 value of x is: 2.094551 
Algorithm converged
[1] 2.094551

Latihan

Latihan 3

Modifikasi fungsi newton raphson dengan output berupa list

newtonraphson.modif <- function(ftn, x0, tol = 1e-5, max.iter = 100) {
    x <- x0
    fx <- ftn(x)
    iter <- 0
    vector <- c()
   while ((abs(fx[1]) > tol) && (iter < max.iter)) {
         x <- x - fx[1]/fx[2]
         fx <- ftn(x)
         iter <- iter + 1
         vector <- c(vector, x)
         }
   # output depends on success of algorithm
   if (abs(fx[1]) > tol) {
       cat("Algorithm failed to converge\n")
       return(NULL)
       } else {
            cat("Algorithm converged\n")
            list.NR <- list("Root" = x, "X_values" = vector, "error" = abs(fx[1])) # output berupa list
            return(list.NR)
            }
     }

Menentukan akar ciri dari persamaan
\[\mathrm{f(x)} = x^3 - 2x-5\]

ftn <- function(x) {
# returns function value and its derivative at x
     fx <- x^3 - 2*x - 5  # fungsi f(x)
     dfx <- 3*x^2 - 2    # turunan pertama f(x)
     return(c(fx, dfx))
}
newtonraphson.modif(fx, 0)
Algorithm converged
$Root
[1] 2.094551

$X_values
 [1] -2.5000000 -1.5671642 -0.5025924 -3.8207065 -2.5493934 -1.6081115
 [7] -0.5761004 -4.5977096 -3.0835431 -2.0221943 -1.1237641  1.2086516
[13]  3.5807900  2.6552332  2.2161063  2.1021250  2.0945836  2.0945515

$error
[1] 6.472653e-09

Latihan 4

Selidiki penggunaan fungsi browser() di R. Gunakan fungsi newtonraphson untuk ilustrasi penggunaan. Laporkan hasil penyelidikanmu beserta ilustrasi coding!

Fungsi browser() di R adalah sebuah fungsi yang digunakan untuk melakukan debugging. Sebagai ilustrasi akan digunakan fungsi browser() untuk melihat jalannya program pada fungsi newtonraphson. Persamaan yang digunakan untuk melakukan debugging fungsi tersebut adalah \[\mathrm{f(x)} = log(x)-e^{-x}\] dengan \(x_0\) yang dimasukkan adalah 3 dan nilai tol diisikan dengan 1e-04.
aa Dengan menambahkan fungsi browser() dalam syntax yang dibuat maka dapat dilihat jalannya program tersebut baris per baris. Ketika program dijalankan dengan argumen x0 = 3 terlihat bahwa nilai x sudah terisi dengan nilai x0 yaitu 3, nilai f(x) juga sudah terisi sesuai dengan nilai f(X) pada saat x=3.
aa Selanjutnya akan dijalankan syntax pada baris ke-7 yang akan mengganti nilai x sebelumnya.
aa Terlihat bahwa nilai x yang sebelumnya berisi 3 sekarang sudah berganti menjadi 0.26… sesuai dengan syntax yang dijalankan pada baris ke-7. aa Kemudian akan dilanjutkan pada syntax pada baris ke-8 yang output dari syntax tersebut dapat kita lihat juga pada tab values. aa Proses ini dapat terus dijalankan sampai debugging selesai dilakukan, sehingga kita dapat melakukan pemeriksaan apakah syntax yang kita buat pada setiap baris sudah sesuai hasilnya.

Latihan 5

Buatlah gambar fungsi pada Latihan 2 dengan menggunakan package ggplot dengan menggunakan fungsi geom_curve!
Persamaan
\[x^3-x-1=0\]
Plot

df.x <- c()
df.y <- c()
for (i in -3:3) {
  x = i
  y = x^3 - x - 1
  df.x <- c(df.x, x)
  df.y <- c(df.y, y)
}
df.5 <- data.frame(df.x, df.y)
library(ggplot2)
ggplot (df.5)+
  geom_curve(aes(x=df.5[1,1], y=df.5[1,2], xend = df.5[4,1], yend = df.5[4,2]), curvature = -0.33, color="red")+
  geom_curve(aes(x=df.5[4,1], y=df.5[4,2], xend = df.5[7,1], yend = df.5[7,2]), curvature = 0.33, color="red")+
  xlab("x") + ylab("y") +
  geom_vline(xintercept = 0, col="grey50")+
  geom_hline(yintercept = 0, col="grey50")

Referensi

Dito, Gerry Alfa dan Raharjo, Mulianto. (21 April 2021). Algoritma Iteratif. Retrieved from https://newlms.ipb.ac.id/

Wigena, Aji Hamim. (21 April 2021). STA561 Pemrograman Statistika: Penentuan Akar Persamaan (Root Finding). Retrieved from https://newlms.ipb.ac.id/