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)
}
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.
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
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.
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.
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)
)
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\)).
Selesaikan \(\cos x = x\) dengan Secant (\(x_0 = 0\), \(x_1 = 1\)) dan Newton-Raphson (\(x_0 = 1\)). Bandingkan iterasi dan jumlah evaluasi fungsi.
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
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.
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.
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
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.