Definisi Fungsi

newtonraphson <- function(ftn, x0, tol = 1e-9, 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")
  }
  if (abs(fx[1]) > tol) {
    cat("Algorithm failed to converge\n")
    return(NULL)
  } else {
    cat("Algorithm converged\n")
    return(x)
  }
}

secant <- function(ftn, x0, x1, tol = 1e-9, max.iter = 100) {
  f0 <- ftn(x0)
  f1 <- ftn(x1)
  iter <- 0
  while ((abs(f1) > tol) && (iter < max.iter)) {
    if (f1 == f0) {
      cat("error: f(x_i) = f(x_{i-1}), pembagi nol\n")
      return(NULL)
    }
    x2 <- x1 - f1 * (x1 - x0) / (f1 - f0)
    x0 <- x1; f0 <- f1
    x1 <- x2; f1 <- ftn(x1)
    iter <- iter + 1
    cat("At iteration", iter, "value of x is:", x1, "\n")
  }
  if (abs(f1) > tol) {
    cat("Algorithm failed to converge\n")
    return(NULL)
  } else {
    cat("Algorithm converged\n")
    return(x1)
  }
}

newton_aman <- function(ftn, lo, hi, tol = 1e-10, max.iter = 100) {
  flo <- ftn(lo)[1]; fhi <- ftn(hi)[1]
  if (flo * fhi > 0) stop("akar tidak terkurung")
  x <- (lo + hi) / 2
  for (iter in 1:max.iter) {
    fx <- ftn(x)
    if (abs(fx[1]) < tol) return(list(root = x, iter = iter - 1))
    if (flo * fx[1] < 0) hi <- x else lo <- x
    xn <- if (fx[2] != 0) x - fx[1] / fx[2] else NA
    x <- if (!is.na(xn) && xn > lo && xn < hi) xn else (lo + hi) / 2
  }
  stop("batas iterasi tercapai")
}

bisection <- function(ftn, x.l, x.r, tol = 1e-9) {
  if (x.l >= x.r) {
    cat("error: x.l >= x.r \n")
    return(NULL)
  }
  f.l <- ftn(x.l)
  f.r <- ftn(x.r)
  if (f.l == 0) {
    return(x.l)
  } else if (f.r == 0) {
    return(x.r)
  } else if (f.l * f.r > 0) {
    cat("error: ftn(x.l) * ftn(x.r) > 0 \n")
    return(NULL)
  }
  n <- 0
  while ((x.r - x.l) > tol) {
    x.m <- (x.l + x.r) / 2
    f.m <- ftn(x.m)
    if (f.m == 0) {
      return(x.m)
    } else if (f.l * f.m < 0) {
      x.r <- x.m
      f.r <- f.m
    } else {
      x.l <- x.m
      f.l <- f.m
    }
    n <- n + 1
    cat("at iteration", n, "the root lies between", x.l, "and", x.r, "\n")
  }
  return((x.l + x.r) / 2)
}

Nomor 1:

Soal. Tentukan akar \(f(x) = x^3 - x - 2\) dengan \(x_0 = 1{,}5\) dan toleransi \(10^{-10}\). Bandingkan jumlah iterasi dengan Bisection pada \([1, 2]\) dan dengan uniroot.

cnt_f3 <- 0
f3 <- function(x) { cnt_f3 <<- cnt_f3 + 1; c(x^3 - x - 2, 3*x^2 - 1) }
r1 <- newtonraphson(f3, 1.5, tol = 1e-10)
## At iteration 1 value of x is: 1.521739 
## At iteration 2 value of x is: 1.52138 
## At iteration 3 value of x is: 1.52138 
## Algorithm converged
iter_newton <- cnt_f3 - 1          
print(r1, digits = 10)
## [1] 1.521379707
cat("Newton: iterasi =", iter_newton, "\n\n")
## Newton: iterasi = 3
cnt_b <- 0
f0 <- function(x) { cnt_b <<- cnt_b + 1; x^3 - x - 2 }
rb <- bisection(f0, 1, 2, tol = 1e-10)
## at iteration 1 the root lies between 1.5 and 2 
## at iteration 2 the root lies between 1.5 and 1.75 
## at iteration 3 the root lies between 1.5 and 1.625 
## at iteration 4 the root lies between 1.5 and 1.5625 
## at iteration 5 the root lies between 1.5 and 1.53125 
## at iteration 6 the root lies between 1.515625 and 1.53125 
## at iteration 7 the root lies between 1.515625 and 1.523438 
## at iteration 8 the root lies between 1.519531 and 1.523438 
## at iteration 9 the root lies between 1.519531 and 1.521484 
## at iteration 10 the root lies between 1.520508 and 1.521484 
## at iteration 11 the root lies between 1.520996 and 1.521484 
## at iteration 12 the root lies between 1.52124 and 1.521484 
## at iteration 13 the root lies between 1.521362 and 1.521484 
## at iteration 14 the root lies between 1.521362 and 1.521423 
## at iteration 15 the root lies between 1.521362 and 1.521393 
## at iteration 16 the root lies between 1.521378 and 1.521393 
## at iteration 17 the root lies between 1.521378 and 1.521385 
## at iteration 18 the root lies between 1.521378 and 1.521381 
## at iteration 19 the root lies between 1.521379 and 1.521381 
## at iteration 20 the root lies between 1.521379 and 1.52138 
## at iteration 21 the root lies between 1.521379 and 1.52138 
## at iteration 22 the root lies between 1.521379 and 1.52138 
## at iteration 23 the root lies between 1.52138 and 1.52138 
## at iteration 24 the root lies between 1.52138 and 1.52138 
## at iteration 25 the root lies between 1.52138 and 1.52138 
## at iteration 26 the root lies between 1.52138 and 1.52138 
## at iteration 27 the root lies between 1.52138 and 1.52138 
## at iteration 28 the root lies between 1.52138 and 1.52138 
## at iteration 29 the root lies between 1.52138 and 1.52138 
## at iteration 30 the root lies between 1.52138 and 1.52138 
## at iteration 31 the root lies between 1.52138 and 1.52138 
## at iteration 32 the root lies between 1.52138 and 1.52138 
## at iteration 33 the root lies between 1.52138 and 1.52138 
## at iteration 34 the root lies between 1.52138 and 1.52138
iter_bis <- cnt_b - 2              # 2 evaluasi awal di x.l dan x.r
cat("Bisection: akar =", rb, " iterasi =", iter_bis, "\n\n")
## Bisection: akar = 1.52138  iterasi = 34
hasil <- uniroot(f0, interval = c(1, 2), tol = 1e-10)
cat("uniroot: akar =", hasil$root, " iterasi =", hasil$iter, "\n")
## uniroot: akar = 1.52138  iterasi = 8

Interpretasi. Berdasarkan hasil perhitungan, metode Newton-Raphson berhasil memperoleh akar persamaan sekitar 1,521380 dalam r iter_newton iterasi, dimulai dari tebakan awal 1,5 dengan toleransi 0,0000000001. Metode Bisection pada selang [1, 2] dan fungsi uniroot() juga menghasilkan akar yang hampir sama, tetapi jumlah iterasinya berbeda. Bisection membutuhkan r iter_bis iterasi, sedangkan uniroot() menyelesaikannya dalam r hasil$iter iterasi. Newton-Raphson adalah metode yang paling cepat karena setiap langkahnya memakai turunan pertama fungsi, yaitu kemiringan kurva di titik yang sedang ditinjau, sehingga jumlah digit yang benar hampir berlipat dua pada setiap iterasi. Bisection lebih lambat karena hanya membagi selang menjadi dua pada setiap langkah tanpa memperhatikan bentuk fungsi. uniroot() berada di tengah karena menggabungkan pembagian selang untuk menjamin akar tetap terkurung dengan tebakan yang lebih cerdas. Dengan demikian, Newton-Raphson unggul dari sisi kecepatan, uniroot() memberikan keseimbangan antara kecepatan dan keamanan, dan Bisection unggul dari sisi kesederhanaan serta jaminan konvergensi, meskipun paling lambat.

Nomor 2:

Soal. Cari \(t_{0{,}975}\) untuk \(df = 9\) dengan Newton-Raphson, dengan \(f(x) = P(T \le x) - 0{,}975\) dan \(f'(x) = dt(x, 9)\). Bandingkan dengan qt(0.975, 9). Coba \(x_0 = 10\) dan jelaskan hasilnya.

cnt_t <- 0
ft <- function(x) { cnt_t <<- cnt_t + 1; c(pt(x, 9) - 0.975, dt(x, 9)) }

r_a <- newtonraphson(ft, 2, tol = 1e-10)
## At iteration 1 value of x is: 2.215137 
## At iteration 2 value of x is: 2.260436 
## At iteration 3 value of x is: 2.262155 
## At iteration 4 value of x is: 2.262157 
## Algorithm converged
iter_a <- cnt_t - 1
cat("Newton x0 = 2: akar =", r_a, " iterasi =", iter_a, "\n\n")
## Newton x0 = 2: akar = 2.262157  iterasi = 4
cnt_t <- 0
r_b <- tryCatch(
  newtonraphson(ft, 10, tol = 1e-10),
  error = function(e) { cat("Gagal:", conditionMessage(e), "\n"); NULL }
)
## At iteration 1 value of x is: -16776.42 
## At iteration 2 value of x is: 7.514743e+37 
## At iteration 3 value of x is: -Inf 
## At iteration 4 value of x is: NaN 
## Gagal: missing value where TRUE/FALSE needed
r_aman <- newton_aman(ft, 0, 5, tol = 1e-10)
cat("newton_aman [0,5]: akar =", r_aman$root, " iterasi =", r_aman$iter, "\n\n")
## newton_aman [0,5]: akar = 2.262157  iterasi = 4
cat("qt(0.975, 9) =", qt(0.975, 9), "\n")
## qt(0.975, 9) = 2.262157
cat("Selisih Newton x0=2 dengan qt =", abs(r_a - qt(0.975, 9)), "\n")
## Selisih Newton x0=2 dengan qt = 4.503065e-12
cat("dt(10, 9) =", dt(10, 9), "\n")
## dt(10, 9) = 1.489193e-06
cat("pt(10, 9) - 0.975 =", pt(10, 9) - 0.975, "\n")
## pt(10, 9) - 0.975 = 0.02499821

Interpretasi. Berdasarkan output, Newton-Raphson dengan tebakan awal 2 berhasil konvergen dalam r iter_a iterasi ke akar sekitar 2,262157. Nilai ini sama dengan qt(0.975, 9) hingga delapan digit, sehingga dapat dipercaya sebagai nilai kritis t untuk derajat bebas 9. Jumlah iterasi yang sedikit menunjukkan bahwa ketika tebakan awal dekat dengan akar, Newton-Raphson bekerja sangat efisien. Nilai 2,262 juga lebih besar daripada kuantil normal 1,96, dan hal ini wajar karena distribusi t dengan derajat bebas kecil memiliki ekor yang lebih tebal, sehingga untuk mencakup 95 persen probabilitas di tengah dibutuhkan batas yang lebih lebar. Sebaliknya, ketika tebakan awal diambil 10, output memperlihatkan kegagalan yang jelas. Nilai x melonjak dari sekitar minus 16.000 ke angka yang sangat besar, lalu muncul -Inf dan NaN, dan R berhenti dengan pesan error “missing value where TRUE/FALSE needed”. Penyebabnya adalah nilai turunan di x = 10 yang sangat kecil, sekitar 0,0000015, sehingga langkah Newton menjadi terlalu besar. Pengaman newton_aman() pada selang [0, 5] berhasil menemukan akar yang sama dalam r_aman$iter iterasi, sehingga terlihat bahwa Newton-Raphson dapat diandalkan bila tebakan awalnya dekat dengan akar atau dibantu selang pengaman.

Nomor 3:

Soal. Selesaikan \(\cos x = x\) dengan Secant (\(x_0 = 0\), \(x_1 = 1\)) dan Newton (\(x_0 = 1\)). Bandingkan iterasi dan jumlah evaluasi fungsi.

cnt_s <- 0
fs <- function(x) { cnt_s <<- cnt_s + 1; cos(x) - x }
sec <- secant(fs, 0, 1, tol = 1e-9)
## At iteration 1 value of x is: 0.6850734 
## At iteration 2 value of x is: 0.736299 
## At iteration 3 value of x is: 0.7391194 
## At iteration 4 value of x is: 0.7390851 
## At iteration 5 value of x is: 0.7390851 
## Algorithm converged
iter_sec <- cnt_s - 2
cat("Secant: akar =", sec, " iterasi =", iter_sec, " evaluasi f =", cnt_s, "\n\n")
## Secant: akar = 0.7390851  iterasi = 5  evaluasi f = 7
cnt_n <- 0
fn <- function(x) { cnt_n <<- cnt_n + 1; c(cos(x) - x, -sin(x) - 1) }
new <- newtonraphson(fn, 1, tol = 1e-9)
## At iteration 1 value of x is: 0.7503639 
## At iteration 2 value of x is: 0.7391129 
## At iteration 3 value of x is: 0.7390851 
## Algorithm converged
iter_nw <- cnt_n - 1
cat("Newton: akar =", new, " iterasi =", iter_nw, " pemanggilan ftn =", cnt_n, "\n")
## Newton: akar = 0.7390851  iterasi = 3  pemanggilan ftn = 4

Interpretasi. Berdasarkan output, Secant dan Newton-Raphson sama-sama menghasilkan akar sekitar 0,7390851 untuk persamaan cos x = x, sehingga kedua metode saling menguatkan. Secant membutuhkan r iter_sec iterasi dengan total r cnt_s pemanggilan fungsi, sedangkan Newton-Raphson membutuhkan r iter_nw iterasi dengan r cnt_n pemanggilan. Newton-Raphson lebih sedikit iterasinya, sesuai dengan sifat konvergensinya yang cepat. Namun setiap langkah Newton-Raphson juga menghitung turunan, sehingga biaya per langkahnya lebih besar. Secant tidak memerlukan turunan dan hanya mengevaluasi fungsi satu kali per iterasi, sehingga pada fungsi ini keduanya cukup seimbang. Secant menjadi pilihan yang lebih efisien ketika turunan sulit atau mahal dihitung, misalnya pada fungsi hasil simulasi atau integral numerik.

Nomor 4: Proyek mini, MLE shape Gamma pada data tinggi badan

Soal. Data tinggi badan mahasiswa (cm) dimodelkan dengan distribusi Gamma. Taksir parameter bentuk (shape) dengan metode Newton-Raphson, memakai persamaan skor MLE dengan tebakan awal alpha0 = 1/(2s), lalu bandingkan hasilnya dengan fungsi fitdistr() dari paket MASS. Semua nilai data harus positif karena distribusi Gamma hanya didefinisikan untuk x > 0.

ketinggian <- c(160.42, 155.04, 180.16, 178.43, 155)  
x <- ketinggian

# Statistik s = ln(rata-rata x) - rata-rata dari ln(x)
s <- log(mean(x)) - mean(log(x))
fg <- function(a) c(log(a) - digamma(a) - s, 1/a - trigamma(a))
a0 <- 1 / (2 * s)
cat("alpha0 =", a0, "\n")
## alpha0 = 221.8787
cnt_g <- 0
fg_cnt <- function(a) { cnt_g <<- cnt_g + 1; fg(a) }
a_newton <- newtonraphson(fg_cnt, a0, tol = 1e-10)
## At iteration 1 value of x is: 222.0451 
## At iteration 2 value of x is: 222.0452 
## Algorithm converged
iter_gm <- cnt_g - 1
print(a_newton, digits = 10)
## [1] 222.0452131
# Pembanding: MASS::fitdistr
library(MASS)
fit <- fitdistr(x, "gamma")
print(fit$estimate)
##      shape       rate 
## 221.975760   1.338736
cat("Selisih shape (Newton - fitdistr) =", a_newton - fit$estimate["shape"], "\n")
## Selisih shape (Newton - fitdistr) = 0.06945304

Interpretasi. Berdasarkan output, Newton-Raphson dengan tebakan awal sekitar 221,88 mencapai shape sekitar 222,045 hanya dalam dua iterasi, dan algoritma dinyatakan konvergen. Nilai ini dibandingkan dengan shape dari fitdistr, yaitu sekitar 221,976, dengan selisih sekitar 0,069 atau kurang dari 0,03 persen, sehingga kedua metode memberikan taksiran yang praktis sama. Rate dari fitdistr sekitar 1,339, dan rasio shape terhadap rata-rata sampel juga akan bernilai sekitar 1,339, sehingga kedua parameter saling konsisten dengan data.