Fungsi dari Materi

Fungsi newtonraphson(), secant(), dan bisection() mengikuti pola kode pada materi Pertemuan 11 (dan Pertemuan 10 untuk Bisection). Untuk Newton, ftn(x) mengembalikan c(f(x), f'(x)); untuk Secant dan Bisection, ftn(x) hanya mengembalikan f(x). Kriteria berhenti adalah \(|f(x)| \le tol\).

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]                 # langkah Newton
    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) {                        # garis sekan mendatar
      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                     # geser: x_i menjadi x_{i-1}
    x1 <- x2; f1 <- ftn(x1)                # hanya SATU evaluasi f baru
    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 <- function(ftn, x.l, x.r, tol = 1e-9, max.iter = 100) {
  f.l <- ftn(x.l)
  f.r <- ftn(x.r)
  if (f.l * f.r > 0) {
    cat("Error: f(x.l) dan f(x.r) bertanda sama\n")
    return(NULL)
  }
  iter <- 0
  x.m <- (x.l + x.r) / 2
  f.m <- ftn(x.m)
  while ((abs(f.m) > tol) && (iter < max.iter)) {
    if (f.l * f.m < 0) {
      x.r <- x.m; f.r <- f.m
    } else {
      x.l <- x.m; f.l <- f.m
    }
    x.m <- (x.l + x.r) / 2
    f.m <- ftn(x.m)
    iter <- iter + 1
    cat("At iteration", iter, "value of x is:", x.m, "\n")
  }
  if (abs(f.m) > tol) {
    cat("Algorithm failed to converge\n")
    return(NULL)
  } else {
    cat("Algorithm converged\n")
    return(x.m)
  }
}

# Pembantu: hitung jumlah iterasi dari keluaran cat()
hitung.iter <- function(expr) {
  out <- capture.output(r <- expr)
  list(root = r, iter = length(grep("At iteration", out)))
}

Soal 1. Newton-Raphson pada \(f(x) = x^3 - x - 2\)

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.

Turunannya \(f'(x) = 3x^2 - 1\). Selang \([1, 2]\) mengurung akar karena \(f(1) = -2 < 0\) dan \(f(2) = 4 > 0\).

f1 <- function(x) c(x^3 - x - 2,      # f(x)
                    3*x^2 - 1)        # f'(x)

D(expression(x^3 - x - 2), "x")       # periksa turunan
## 3 * x^2 - 1
r1 <- newtonraphson(f1, 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
print(r1, digits = 12)
## [1] 1.5213797068
g1 <- function(x) x^3 - x - 2

r1.bis <- bisection(g1, 1, 2, tol = 1e-10)
## At iteration 1 value of x is: 1.75 
## At iteration 2 value of x is: 1.625 
## At iteration 3 value of x is: 1.5625 
## At iteration 4 value of x is: 1.53125 
## At iteration 5 value of x is: 1.515625 
## At iteration 6 value of x is: 1.523438 
## At iteration 7 value of x is: 1.519531 
## At iteration 8 value of x is: 1.521484 
## At iteration 9 value of x is: 1.520508 
## At iteration 10 value of x is: 1.520996 
## At iteration 11 value of x is: 1.52124 
## At iteration 12 value of x is: 1.521362 
## At iteration 13 value of x is: 1.521423 
## At iteration 14 value of x is: 1.521393 
## At iteration 15 value of x is: 1.521378 
## At iteration 16 value of x is: 1.521385 
## At iteration 17 value of x is: 1.521381 
## At iteration 18 value of x is: 1.521379 
## At iteration 19 value of x is: 1.52138 
## At iteration 20 value of x is: 1.52138 
## At iteration 21 value of x is: 1.52138 
## At iteration 22 value of x is: 1.52138 
## At iteration 23 value of x is: 1.52138 
## At iteration 24 value of x is: 1.52138 
## At iteration 25 value of x is: 1.52138 
## At iteration 26 value of x is: 1.52138 
## At iteration 27 value of x is: 1.52138 
## At iteration 28 value of x is: 1.52138 
## At iteration 29 value of x is: 1.52138 
## At iteration 30 value of x is: 1.52138 
## At iteration 31 value of x is: 1.52138 
## At iteration 32 value of x is: 1.52138 
## Algorithm converged
print(r1.bis, digits = 12)
## [1] 1.5213797068
r1.uni <- uniroot(g1, c(1, 2), tol = 1e-10)
print(r1.uni$root, digits = 12)
## [1] 1.5213797068
r1.uni$iter
## [1] 8
n1.newton <- hitung.iter(newtonraphson(f1, 1.5, tol = 1e-10))$iter
n1.bis    <- hitung.iter(bisection(g1, 1, 2, tol = 1e-10))$iter
n1.uni    <- r1.uni$iter

data.frame(Metode  = c("Newton-Raphson", "Bisection", "uniroot"),
           Iterasi = c(n1.newton, n1.bis, n1.uni))
##           Metode Iterasi
## 1 Newton-Raphson       3
## 2      Bisection      32
## 3        uniroot       8
par(mfrow = c(1, 2))
curve(x^3 - x - 2, 0.8, 2.1, ylab = "f(x)", main = "f(x) = x^3 - x - 2")
abline(h = 0, col = "grey50")
points(r1, 0, pch = 19, col = "red")
barplot(c(n1.newton, n1.bis, n1.uni), names.arg = c("Newton", "Bisection", "uniroot"),
        col = c("firebrick", "steelblue", "darkgreen"), ylab = "Iterasi",
        main = "Jumlah iterasi")

Interpretasi. Ketiga metode menghasilkan akar yang sama, yaitu \(x \approx 1{,}5213797\). Newton-Raphson paling cepat, hanya 3 iterasi, karena konvergensinya kuadratik (digit benar kira-kira berlipat dua tiap iterasi) dan tebakan awal 1,5 sudah dekat dengan akar. Bisection membutuhkan 32 iterasi karena galatnya hanya dibagi dua tiap iterasi (konvergensi linear). uniroot memakai metode Brent yang menggabungkan kepastian Bisection dengan kecepatan interpolasi, sehingga cukup 8 iterasi. Kekurangan Newton: memerlukan \(f'(x)\) dan tebakan awal yang masuk akal.


Soal 2. Kuantil \(t_{0{,}975}\) dengan df = 9

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

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

newtonraphson(ft, 1, tol = 1e-10)
## At iteration 1 value of x is: 1.640325 
## At iteration 2 value of x is: 2.047073 
## At iteration 3 value of x is: 2.229612 
## At iteration 4 value of x is: 2.261325 
## At iteration 5 value of x is: 2.262157 
## At iteration 6 value of x is: 2.262157 
## Algorithm converged
## [1] 2.262157
qt(0.975, 9)                              # pembanding bawaan R
## [1] 2.262157

Beberapa tebakan awal lain:

newtonraphson(ft, 0, tol = 1e-10)
## At iteration 1 value of x is: 1.224117 
## At iteration 2 value of x is: 1.786244 
## At iteration 3 value of x is: 2.125294 
## At iteration 4 value of x is: 2.248348 
## At iteration 5 value of x is: 2.262006 
## At iteration 6 value of x is: 2.262157 
## At iteration 7 value of x is: 2.262157 
## Algorithm converged
## [1] 2.262157
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
## [1] 2.262157

Tebakan awal \(x_0 = 10\) (jauh di ekor kurva):

dt(10, 9)                                 # kepadatan di x = 10: sangat kecil
## [1] 1.489193e-06
pt(10, 9) - 0.975
## [1] 0.02499821
# gagal: x menjadi Inf lalu NaN, sehingga while() error -> ditangkap tryCatch
tryCatch(newtonraphson(ft, 10, tol = 1e-10),
         error = function(e) cat("Berhenti karena NaN:", conditionMessage(e), "\n"))
## 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 
## Berhenti karena NaN: missing value where TRUE/FALSE needed
# langkah pertama dihitung manual
x1 <- 10 - (pt(10, 9) - 0.975) / dt(10, 9)
x1
## [1] -16776.42
par(mfrow = c(1, 2))
curve(pt(x, 9) - 0.975, -3, 12, ylab = "f(x)", main = "f(x) = pt(x, 9) - 0.975")
abline(h = 0, col = "grey50")
points(10, ft(10)[1], pch = 19, col = "red")
text(10, ft(10)[1] - 0.15, "x0 = 10", col = "red")
curve(dt(x, 9), -12, 12, ylab = "f'(x)", main = "f'(x) = dt(x, 9)")
abline(v = 10, col = "red", lty = 3)

Interpretasi. Dari \(x_0 = 0, 1, 2\) Newton konvergen ke \(t_{0{,}975} = 2{,}262157\), sama persis dengan qt(0.975, 9).

Mengapa \(x_0 = 10\) gagal? Di \(x = 10\), kepadatan dt(10, 9) hanya sekitar \(1{,}49 \times 10^{-6}\), artinya kurva \(f\) hampir datar (ekor distribusi), sedangkan \(f(10) = 0{,}025\). Garis singgung yang hampir mendatar baru memotong sumbu-x sangat jauh: \(x_1 \approx -16776\). Di titik itu $f’ $ praktis nol lagi, sehingga loncatan berikutnya meledak (\(\approx 7{,}5 \times 10^{37}\)), lalu dt() bernilai 0, pembagian menghasilkan -Inf dan akhirnya NaN, sehingga while error. Ini jebakan “turunan hampir nol” yang sama dengan SK3 pada materi. Solusinya: pilih tebakan awal dekat akar (misalnya 1 sampai 3), atau pakai versi aman newton_aman() (SK5).


Soal 3. Secant dan Newton pada \(\cos x = x\)

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

Persamaan diubah menjadi \(f(x) = \cos x - x = 0\) dengan \(f'(x) = -\sin x - 1\).

f3  <- function(x) cos(x) - x                       # untuk Secant
f3n <- function(x) c(cos(x) - x, -sin(x) - 1)       # untuk Newton

r3.sec <- secant(f3, 0, 1, tol = 1e-10)
## 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
print(r3.sec, digits = 12)
## [1] 0.739085133215
r3.new <- newtonraphson(f3n, 1, tol = 1e-10)
## 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 
## At iteration 4 value of x is: 0.7390851 
## Algorithm converged
print(r3.new, digits = 12)
## [1] 0.739085133215
n3.sec <- hitung.iter(secant(f3, 0, 1, tol = 1e-10))$iter
n3.new <- hitung.iter(newtonraphson(f3n, 1, tol = 1e-10))$iter

# Secant : 2 evaluasi awal (x0, x1) + 1 evaluasi f per iterasi
eval.sec <- 2 + n3.sec
# Newton : f dan f' pada tiap titik (x0 sampai x_n)
eval.new <- 2 * (1 + n3.new)

data.frame(Metode   = c("Secant", "Newton-Raphson"),
           Iterasi  = c(n3.sec, n3.new),
           Evaluasi = c(eval.sec, eval.new))
##           Metode Iterasi Evaluasi
## 1         Secant       5        7
## 2 Newton-Raphson       4       10
uniroot(f3, c(0, 1), tol = 1e-12)$root              # pembanding
## [1] 0.7390851
par(mfrow = c(1, 2))
curve(cos(x), -0.2, 1.3, ylab = "y", main = "cos(x) = x")
curve(x * 1, add = TRUE, col = "orange")
points(r3.new, r3.new, pch = 19, col = "red")
legend("topright", c("cos x", "y = x"), col = c("black", "orange"), lty = 1, bty = "n")
barplot(rbind(c(n3.sec, n3.new), c(eval.sec, eval.new)), beside = TRUE,
        names.arg = c("Secant", "Newton"), col = c("steelblue", "firebrick"),
        legend.text = c("Iterasi", "Evaluasi f"), main = "Iterasi vs evaluasi fungsi")

Interpretasi. Kedua metode menemukan akar yang sama, \(x \approx 0{,}7390851\). Dari sisi iterasi, Newton lebih sedikit (4 vs 5) karena orde konvergensinya 2, sedangkan Secant \(\approx 1{,}618\). Namun dari sisi jumlah evaluasi fungsi, Secant lebih hemat (7 vs 10), sebab tiap iterasi Secant hanya menghitung satu \(f\) baru, sedangkan Newton harus menghitung \(f\) dan \(f'\). Ini sesuai indeks efisiensi pada materi: \(E_{Newton} = \sqrt{2} \approx 1{,}414\) dan \(E_{Secant} \approx 1{,}618\). Bila turunan sulit atau mahal dihitung, Secant lebih tepat.


Soal 4. Proyek Mini: MLE Parameter Bentuk Gamma

Soal. Taksir MLE parameter bentuk Gamma (\(\alpha\)) dari data dengan Newton, dengan

\[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)\), dan \(\alpha_0 = 1/(2s)\). Bandingkan dengan MASS::fitdistr.

Karena data tidak diberikan, data dibangkitkan dari Gamma(shape = 3, rate = 0,5) dengan \(n = 100\). Bila Anda punya data sendiri, ganti baris x <- rgamma(...).

set.seed(123)
x <- rgamma(100, shape = 3, rate = 0.5)             # data simulasi (alpha = 3)
s <- log(mean(x)) - mean(log(x))
s
## [1] 0.1434942
fg <- function(a) c(log(a) - digamma(a) - s,        # f(alpha)
                    1/a - trigamma(a))              # f'(alpha)

a0 <- 1 / (2 * s)
a0
## [1] 3.484461
alpha.hat <- newtonraphson(fg, a0, tol = 1e-10)
## At iteration 1 value of x is: 3.635574 
## At iteration 2 value of x is: 3.64271 
## At iteration 3 value of x is: 3.642725 
## Algorithm converged
print(alpha.hat, digits = 10)
## [1] 3.642724731
beta.hat <- alpha.hat / mean(x)                     # taksiran rate
beta.hat
## [1] 0.6662807
library(MASS)
fit <- fitdistr(x, "gamma")
fit
##      shape         rate   
##   3.64273362   0.66628249 
##  (0.49338629) (0.09676053)
alpha.hat - fit$estimate["shape"]                   # selisih Newton vs fitdistr
##         shape 
## -8.888479e-06

Kepekaan terhadap tebakan awal:

newtonraphson(fg, 1, tol = 1e-10)
## At iteration 1 value of x is: 1.672505 
## At iteration 2 value of x is: 2.540802 
## At iteration 3 value of x is: 3.296763 
## At iteration 4 value of x is: 3.608565 
## At iteration 5 value of x is: 3.642392 
## At iteration 6 value of x is: 3.642725 
## At iteration 7 value of x is: 3.642725 
## Algorithm converged
## [1] 3.642725
newtonraphson(fg, 0.5, tol = 1e-10)
## At iteration 1 value of x is: 0.8839675 
## At iteration 2 value of x is: 1.499378 
## At iteration 3 value of x is: 2.340172 
## At iteration 4 value of x is: 3.159617 
## At iteration 5 value of x is: 3.576129 
## At iteration 6 value of x is: 3.641458 
## At iteration 7 value of x is: 3.642724 
## At iteration 8 value of x is: 3.642725 
## Algorithm converged
## [1] 3.642725
par(mfrow = c(1, 2))
curve(log(x) - digamma(x) - s, 0.3, 6, xlab = "alpha", ylab = "f(alpha)",
      main = "Persamaan MLE Gamma")
abline(h = 0, col = "grey50")
points(alpha.hat, 0, pch = 19, col = "red")
hist(x, breaks = 15, freq = FALSE, col = "lightblue", main = "Data dan kurva Gamma hasil Newton")
curve(dgamma(x, shape = alpha.hat, rate = beta.hat), add = TRUE, col = "red", lwd = 2)

Interpretasi. Tebakan awal \(\alpha_0 = 1/(2s) = 3{,}4845\) sudah sangat dekat dengan akar, sehingga Newton hanya perlu 3 iterasi dan menghasilkan \(\hat\alpha = 3{,}642725\). Hasil ini hampir identik dengan MASS::fitdistr (\(3{,}642734\)); selisih sekitar \(9 \times 10^{-6}\) muncul karena fitdistr memakai optimasi numerik dengan toleransi lebih longgar, sedangkan Newton dipaksa sampai \(|f| < 10^{-10}\). Taksiran laju \(\hat\beta = \hat\alpha/\bar{x} = 0{,}6663\) juga sama. Nilai \(\hat\alpha = 3{,}64\) berbeda dari nilai sebenarnya 3 karena variasi sampel (\(n = 100\)); galat baku sekitar 0,49 sehingga nilai 3 masih wajar. Newton juga cukup kokoh: dari \(\alpha_0 = 1\) diperlukan 7 iterasi dan dari \(\alpha_0 = 0{,}5\) diperlukan 8 iterasi, karena \(f(\alpha)\) mulus dan monoton tanpa titik stasioner.


Kesimpulan Umum

Newton-Raphson sangat cepat bila turunan mudah dan tebakan awal dekat akar (Soal 1, 2, 4), tetapi rapuh bila garis singgung hampir mendatar (Soal 2 dengan \(x_0 = 10\)). Secant tidak memerlukan turunan dan unggul dalam jumlah evaluasi fungsi (Soal 3). Bisection lambat namun pasti, dan uniroot menjadi kompromi yang aman dan cepat. Praktik terbaik seperti pada materi: kurung akar dengan Bisection, lalu selesaikan dengan Newton atau Secant.