1 Fungsi yang Dipakai

newtonraphson() dan secant() mengikuti materi Pertemuan 11 (berhenti bila \(|f(x)| \le\) tol). bisection_n() dan hitung_panggil() (pencacah pemanggilan fungsi) ditambahkan untuk keperluan perbandingan.

newtonraphson <- function(ftn, x0, tol = 1e-9, max.iter = 100) {
  # ftn(x) mengembalikan c(f(x), f'(x)); berhenti bila |f(x)| <= tol
  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)
  }
}

# Bisection sederhana (pembanding), berhenti bila |f(titik tengah)| <= tol
bisection_n <- function(f, a, b, tol = 1e-10, max.iter = 200) {
  if (f(a) * f(b) > 0) stop("akar tidak terkurung pada [a, b]")
  for (iter in 1:max.iter) {
    m <- (a + b) / 2
    fm <- f(m)
    if (abs(fm) <= tol) return(list(root = m, iter = iter))
    if (f(a) * fm < 0) b <- m else a <- m
  }
  stop("batas iterasi tercapai")
}

# Pencacah pemanggilan fungsi: membungkus f dan menghitung berapa kali dipanggil
hitung_panggil <- function(f) {
  n <- 0
  list(f = function(x) { n <<- n + 1; f(x) },
       n = function() n)
}

2 Newton-Raphson

2.1 Soal

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

2.2 Rcode dan Hasil

D(expression(x^3 - x - 2), "x")
## 3 * x^2 - 1
f_1  <- function(x) x^3 - x - 2
ftn1 <- function(x) c(x^3 - x - 2, 3*x^2 - 1)   # f(x) dan f'(x)

akar_newton1 <- newtonraphson(ftn1, 1.5, tol = 1e-10)
## At iteration 1 value of x is: 1.52173913 
## At iteration 2 value of x is: 1.521379806 
## At iteration 3 value of x is: 1.521379707 
## Algorithm converged
print(akar_newton1, digits = 12)
## [1] 1.5213797068
# jumlah iterasi Newton dihitung dengan pencacah (panggilan pertama = titik awal)
cnt1  <- hitung_panggil(ftn1)
invisible(capture.output(newtonraphson(cnt1$f, 1.5, tol = 1e-10)))
iter_newton1 <- cnt1$n() - 1

bis1  <- bisection_n(f_1, 1, 2, tol = 1e-10)
uni1  <- uniroot(f_1, c(1, 2), tol = 1e-10)

hasil1 <- data.frame(
  Metode  = c("Newton-Raphson (x0 = 1,5)", "Bisection [1, 2]", "uniroot (Brent) [1, 2]"),
  Akar    = c(akar_newton1, bis1$root, uni1$root),
  Iterasi = c(iter_newton1, bis1$iter, uni1$iter)
)
hasil1

2.3 Interpretasi

Ketiga metode menghasilkan akar yang sama, yaitu \(x \approx\) 1.52137971. Newton-Raphson paling cepat dengan 3 iterasi, disusul uniroot dengan 8 iterasi, lalu Bisection dengan 33 iterasi. Bisection hanya membagi dua galat tiap iterasi (konvergensi linear), sedangkan Newton-Raphson berorde kuadratik sehingga jumlah digit benar kira-kira berlipat dua tiap iterasi, asalkan \(x_0\) dekat akar dan \(f'(x) \ne 0\). Kelemahannya, Newton membutuhkan turunan dan tidak menjamin konvergen bila \(x_0\) jauh dari akar.

3 Kuantil Distribusi \(t\)

3.1 Soal

Cari \(t_{0{,}975}\) untuk \(df = 9\) dengan Newton-Raphson ($f(x) = $ pt(x, 9) - 0.975, $f’(x) = $ dt(x, 9)), bandingkan dengan qt(0.975, 9). Coba \(x_0 = 10\) dan jelaskan hasilnya.

3.2 Rcode dan Hasil

ft <- function(x) c(pt(x, 9) - 0.975, dt(x, 9))

akar_t <- newtonraphson(ft, 2, tol = 1e-10)
## At iteration 1 value of x is: 2.215136517 
## At iteration 2 value of x is: 2.260436076 
## At iteration 3 value of x is: 2.262154792 
## At iteration 4 value of x is: 2.262157163 
## Algorithm converged
print(akar_t, digits = 12)
## [1] 2.26215716279
print(qt(0.975, 9), digits = 12)      # pembanding bawaan R
## [1] 2.2621571628
abs(akar_t - qt(0.975, 9))
## [1] 4.503064588e-12
x0_uji <- c(-1, 0, 1, 2, 3)
tabel_t <- do.call(rbind, lapply(x0_uji, function(x0) {
  cnt <- hitung_panggil(ft)
  hasil <- NULL
  invisible(capture.output(hasil <- newtonraphson(cnt$f, x0, tol = 1e-10)))
  data.frame(x0 = x0,
             hasil = if (is.null(hasil)) NA else hasil,
             iterasi = cnt$n() - 1)
}))
tabel_t
res10 <- try(newtonraphson(ft, 10, tol = 1e-10, max.iter = 20), silent = TRUE)
## At iteration 1 value of x is: -16776.4195 
## At iteration 2 value of x is: 7.514742638e+37 
## At iteration 3 value of x is: -Inf 
## At iteration 4 value of x is: NaN
res10
## [1] "Error in while ((abs(fx[1]) > tol) && (iter < max.iter)) { : \n  missing value where TRUE/FALSE needed\n"
## attr(,"class")
## [1] "try-error"
## attr(,"condition")
## <simpleError in 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")}: missing value where TRUE/FALSE needed>
x_awal <- 10
f_awal <- ft(x_awal)
x1_t   <- x_awal - f_awal[1] / f_awal[2]
f_x1   <- ft(x1_t)
x2_t   <- x1_t - f_x1[1] / f_x1[2]

data.frame(
  langkah = c("x0", "x1", "x2"),
  x       = c(x_awal, x1_t, x2_t),
  f       = c(f_awal[1], f_x1[1], NA),
  fprime  = c(f_awal[2], f_x1[2], NA)
)

3.3 Interpretasi

Dari tebakan awal yang wajar (\(-1\) sampai \(3\)), Newton-Raphson konvergen cepat ke \(t_{0{,}975} \approx\) 2.262157, sama dengan qt(0.975, 9) (selisih 4.5e-12). Pada \(x_0 = 10\) algoritma gagal: titik itu berada di ekor kanan sehingga \(f'(10) = f_t(10) \approx\) 1.49e-06 hampir nol, garis singgung nyaris mendatar, dan langkah \(-f/f'\) melempar \(x_1\) jauh ke -16776.4. Di sana kepadatan juga hampir nol, sehingga \(x_2\) meledak menjadi Inf/NaN. Solusinya adalah memakai tebakan awal dekat akar, misalnya dari pendekatan normal (\(z_{0{,}975} = 1{,}96\)).

4 Secant vs Newton-Raphson

4.1 Soal

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

4.2 Rcode dan Hasil

f3   <- function(x) cos(x) - x
ftn3 <- function(x) c(cos(x) - x, -sin(x) - 1)
cnt_s <- hitung_panggil(f3)
akar_s <- secant(cnt_s$f, 0, 1, tol = 1e-10)
## At iteration 1 value of x is: 0.6850733573 
## At iteration 2 value of x is: 0.7362989976 
## At iteration 3 value of x is: 0.7391193619 
## At iteration 4 value of x is: 0.7390851121 
## At iteration 5 value of x is: 0.7390851332 
## Algorithm converged
print(akar_s, digits = 12)
## [1] 0.739085133215
cnt_n <- hitung_panggil(ftn3)
akar_n <- newtonraphson(cnt_n$f, 1, tol = 1e-10)
## At iteration 1 value of x is: 0.7503638678 
## At iteration 2 value of x is: 0.7391128909 
## At iteration 3 value of x is: 0.7390851334 
## At iteration 4 value of x is: 0.7390851332 
## Algorithm converged
print(akar_n, digits = 12)
## [1] 0.739085133215
iter_s  <- cnt_s$n() - 2      # dua panggilan awal (x0 dan x1), lalu satu per iterasi
iter_n  <- cnt_n$n() - 1      # satu panggilan awal (x0), lalu satu per iterasi
eval_s  <- cnt_s$n()          # tiap panggilan Secant = 1 evaluasi f
eval_n  <- 2 * cnt_n$n()      # tiap panggilan Newton = 2 evaluasi (f dan f')

perbandingan3 <- data.frame(
  Metode            = c("Secant (x0 = 0, x1 = 1)", "Newton-Raphson (x0 = 1)"),
  Akar              = c(akar_s, akar_n),
  Iterasi           = c(iter_s, iter_n),
  Evaluasi_fungsi   = c(eval_s, eval_n)
)
perbandingan3
uniroot(f3, c(0, 1), tol = 1e-12)$root   # pembanding bawaan R
## [1] 0.7390851332

4.3 Interpretasi

Kedua metode menemukan akar yang sama, \(x \approx\) 0.7390851. Newton-Raphson butuh 4 iterasi dan Secant 5 iterasi, sesuai orde konvergensinya (Newton 2, Secant \(\approx 1{,}618\)). Namun dari sisi biaya, Newton menghitung \(f\) dan \(f'\) di tiap titik sehingga total 10 evaluasi, sedangkan Secant hanya 7 evaluasi karena cukup satu \(f\) baru per iterasi. Jadi Secant lebih hemat evaluasi dan tidak memerlukan turunan, walaupun iterasinya sedikit lebih banyak.

5 Proyek Mini: MLE Parameter Bentuk Gamma

5.1 Soal

Taksir MLE parameter bentuk Gamma (\(\alpha\)) dengan Newton-Raphson, \(f(\alpha) = \ln\alpha - \psi(\alpha) - \left[\ln\bar{x} - \frac{1}{n}\sum \ln x_i\right] = 0\), \(f'(\alpha) = 1/\alpha - \text{trigamma}(\alpha)\), \(\alpha_0 = 1/(2s)\). Bandingkan dengan MASS::fitdistr.

5.2 Rcode dan Hasil

data_gamma <- c(3.14, 1.23, 7.70, 4.38, 4.51, 8.05, 5.13, 5.88, 4.12, 4.92,
                3.92, 4.61, 7.72, 3.33, 2.24, 2.35, 3.83, 8.55, 2.93, 3.81,
                7.16, 6.03, 3.07, 7.52, 16.12, 18.82, 3.21, 8.52, 9.29, 5.26)

n    <- length(data_gamma)
xbar <- mean(data_gamma)
s4   <- log(xbar) - mean(log(data_gamma))   # statistik s
c(n = n, xbar = xbar, s = s4)
##             n          xbar             s 
## 30.0000000000  5.9116666667  0.1636623704
fa <- function(a) c(log(a) - digamma(a) - s4,    # f(alpha)
                    1/a - trigamma(a))           # f'(alpha)

alpha0   <- 1 / (2 * s4)
alpha0
## [1] 3.055070012
alpha_hat <- newtonraphson(fa, alpha0, tol = 1e-10)
## At iteration 1 value of x is: 3.204098232 
## At iteration 2 value of x is: 3.212095465 
## At iteration 3 value of x is: 3.212116373 
## Algorithm converged
print(alpha_hat, digits = 12)
## [1] 3.21211637279
rate_hat <- alpha_hat / xbar                    # MLE laju (rate) = alpha / xbar
c(alpha = alpha_hat, rate = rate_hat, scale = 1 / rate_hat)
##        alpha         rate        scale 
## 3.2121163728 0.5433520788 1.8404273011
cnt_g <- hitung_panggil(fa)
invisible(capture.output(newtonraphson(cnt_g$f, alpha0, tol = 1e-10)))
iter_g <- cnt_g$n() - 1
iter_g
## [1] 3
# tebakan awal alternatif (dibungkus try karena dapat gagal)
for (a0 in c(0.1, 1, 10)) {
  cat("alpha0 =", a0, ": ")
  h <- NULL
  r <- try(suppressWarnings(
    capture.output(h <- newtonraphson(fa, a0, tol = 1e-10, max.iter = 30))),
    silent = TRUE)
  if (inherits(r, "try-error") || is.null(h)) cat("gagal\n") else cat("konvergen ke", h, "\n")
}
## alpha0 = 0.1 : konvergen ke 3.212116373 
## alpha0 = 1 : konvergen ke 3.212116372 
## alpha0 = 10 : gagal
library(MASS)
fit <- fitdistr(data_gamma, "gamma")
fit
##       shape           rate    
##   3.2121361094   0.5433537164 
##  (0.7900902248) (0.1446569261)
perbandingan4 <- data.frame(
  Metode = c("Newton-Raphson", "MASS::fitdistr"),
  alpha  = c(alpha_hat, unname(fit$estimate["shape"])),
  rate   = c(rate_hat,  unname(fit$estimate["rate"]))
)
perbandingan4
abs(alpha_hat - unname(fit$estimate["shape"]))
## [1] 1.973664537e-05

5.3 Interpretasi

Dengan \(\alpha_0 = 1/(2s) =\) 3.0551, Newton-Raphson konvergen dalam 3 iterasi ke \(\hat\alpha =\) 3.212116 dengan laju \(\hat\lambda =\) 0.5434, dekat dengan parameter pembangkit data (\(\alpha = 3\), laju 0,5). MASS::fitdistr memberi \(\hat\alpha =\) 3.212136, selisihnya hanya 1.97e-05 karena fitdistr memaksimumkan log-kemungkinan secara numerik lewat optim, sedangkan Newton langsung menyelesaikan persamaan skor. Tebakan awal \(1/(2s)\) aman karena dekat akar; tebakan yang terlalu jauh dapat membuat langkah keluar dari daerah \(\alpha > 0\) sehingga \(\ln\alpha\) tidak terdefinisi.