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. 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. 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. 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. 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.
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.