Praktikum ini membahas tiga metode pencarian akar persamaan nonlinear, yaitu metode Bisection, iterasi Titik Tetap, dan metode Newton. Selanjutnya, ketiga metode dibandingkan berdasarkan jumlah iterasi serta diuji pada beberapa kondisi yang dapat menyebabkan kegagalan atau memperlambat metode Newton.
f1 <- function(x) x^2 - 2
f2 <- function(x) x^3 - x - 1
f3 <- function(x) cos(x) - x
fd1 <- function(x) 2 * x
fd2 <- function(x) 3 * x^2 - 1
fd3 <- function(x) -sin(x) - 1Fungsi berikut melengkapi kerangka kode praktikum. Titik tengah
interval dihitung dengan (a+b)/2. Iterasi dihentikan ketika
setengah lebar interval lebih kecil daripada toleransi.
bisection <- function(f, a, b, tol = 1e-6, maxit = 100) {
if (f(a) * f(b) >= 0) stop("f(a) dan f(b) harus berbeda tanda")
riwayat <- data.frame()
for (k in 1:maxit) {
c <- (a + b) / 2
riwayat <- rbind(riwayat, data.frame(k = k, a = a, b = b, c = c, fc = f(c), batas = (b - a) / 2))
if ((b - a) / 2 < tol) break
if (f(a) * f(c) < 0) b <- c else a <- c
}
list(akar = c, iterasi = k, riwayat = riwayat)
}b1 <- bisection(f1, 1, 2, tol = 0.01)
print(b1$riwayat)## k a b c fc batas
## 1 1 1.00000 2.000000 1.5000000 0.2500000000000 0.5000000
## 2 2 1.00000 1.500000 1.2500000 -0.4375000000000 0.2500000
## 3 3 1.25000 1.500000 1.3750000 -0.1093750000000 0.1250000
## 4 4 1.37500 1.500000 1.4375000 0.0664062500000 0.0625000
## 5 5 1.37500 1.437500 1.4062500 -0.0224609375000 0.0312500
## 6 6 1.40625 1.437500 1.4218750 0.0217285156250 0.0156250
## 7 7 1.40625 1.421875 1.4140625 -0.0004272460938 0.0078125cat("iterasi:", b1$iterasi, " akar:", b1$akar, "\n")## iterasi: 7 akar: 1.4140625b2 <- bisection(f3, 0, 1, tol = 1e-6)
cat("cos x - x: iterasi", b2$iterasi, " akar", b2$akar, "\n")## cos x - x: iterasi 20 akar 0.7390851974Berdasarkan hasil perhitungan, persamaan \(x^2-2=0\) pada interval [1,2] memerlukan 7 iterasi dan menghasilkan hampiran akar 1,4140625. Untuk persamaan \(\cos x-x=0\) pada interval [0,1] dengan toleransi \(10^{-6}\), diperlukan 20 iterasi dengan hampiran akar sekitar 0,7390851974.
bisection(f1, 2, 3)Perintah tersebut menghasilkan error karena nilai fungsi pada kedua ujung interval bertanda sama: \(f(2)=2\) dan \(f(3)=7\). Bisection mensyaratkan perubahan tanda pada interval awal.
(a) Metode Bisection membutuhkan 7 iterasi untuk menyelesaikan \(x^2-2=0\) pada interval [1,2] dengan toleransi 0,01. Hampiran akar yang diperoleh adalah 1,4140625.
(b) Untuk \(\cos x-x=0\) pada interval [0,1], diperlukan 20 iterasi dengan toleransi \(10^{-6}\). Jumlah iterasi mengikuti proses pembagian interval menjadi dua pada setiap langkah.
(c) Perintah bisection(f1, 2, 3)
menghasilkan error karena kedua ujung interval memiliki nilai fungsi
positif. Fungsi menolak interval tersebut karena syarat perubahan tanda
tidak terpenuhi.
(d) Jumlah iterasi Bisection ditentukan oleh lebar interval awal dan toleransi karena panjang interval selalu dibagi dua pada setiap iterasi. Selama syarat perubahan tanda terpenuhi, jumlah pembagian interval yang diperlukan tidak bergantung pada bentuk rinci fungsi.
titik_tetap <- function(g, x0, tol = 1e-6, maxit = 100) {
x <- x0
riwayat <- data.frame(k = 0, x = x0, selisih = NA)
for (k in 1:maxit) {
x_baru <- g(x)
riwayat <- rbind(riwayat, data.frame(k = k, x = x_baru, selisih = abs(x_baru - x)))
if (!is.finite(x_baru) || abs(x_baru) > 1e10)
return(list(akar = NA, iterasi = k, konvergen = FALSE, riwayat = riwayat))
if (abs(x_baru - x) < tol)
return(list(akar = x_baru, iterasi = k, konvergen = TRUE, riwayat = riwayat))
x <- x_baru
}
list(akar = x, iterasi = maxit, konvergen = FALSE, riwayat = riwayat)
}ga <- function(x) (x^2 + 2) / 3
t1 <- titik_tetap(ga, 0, tol = 1e-6)
cat("iterasi:", t1$iterasi, " akar:", t1$akar, "\n")## iterasi: 30 akar: 0.9999983201print(head(t1$riwayat))## k x selisih
## 1 0 0.0000000000 NA
## 2 1 0.6666666667 0.66666666667
## 3 2 0.8148148148 0.14814814815
## 4 3 0.8879743941 0.07315957933
## 5 4 0.9294995082 0.04152511407
## 6 5 0.9546564453 0.02515693704t1b <- titik_tetap(ga, 2.5, maxit = 20)
cat("konvergen:", t1b$konvergen, " iterasi:", t1b$iterasi, "\n")## konvergen: FALSE iterasi: 9print(t1b$riwayat)## k x selisih
## 1 0 2.500000000e+00 NA
## 2 1 2.750000000e+00 2.500000000e-01
## 3 2 3.187500000e+00 4.375000000e-01
## 4 3 4.053385417e+00 8.658854167e-01
## 5 4 6.143311112e+00 2.089925695e+00
## 6 5 1.324675714e+01 7.103446028e+00
## 7 6 5.915885824e+01 4.591210110e+01
## 8 7 1.167256836e+03 1.108097978e+03
## 9 8 4.541635071e+05 4.529962503e+05
## 10 9 6.875483040e+10 6.875437623e+10gA <- function(x) (x + 1)^(1/3)
gB <- function(x) x^3 - 1
tA <- titik_tetap(gA, 1)
tB <- titik_tetap(gB, 1.3, maxit = 50)
cat("A:", tA$konvergen, tA$iterasi, " B:", tB$konvergen, tB$iterasi, "\n")## A: TRUE 9 B: FALSE 8tC <- titik_tetap(cos, 0.5, tol = 1e-6)
cat("cos x: iterasi", tC$iterasi, " x =", tC$akar, "\n")## cos x: iterasi 34 x = 0.7390848229r <- 0.7390851332151607
e <- abs(tC$riwayat$x - r)
rasio <- e[-1] / e[-length(e)]
print(rasio[10:14])## [1] 0.6758381995 0.6721028643 0.6746242449 0.6729282105 0.6740717579cat("|g'(r)| =", sin(r), "\n")## |g'(r)| = 0.6736120292(a) Untuk \(g(x)=(x^2+2)/3\) dengan \(x_0=0\), iterasi membutuhkan 30 langkah dan menuju akar 1. Rasio galat berturutan mendekati \(2/3\), sesuai dengan nilai turunan fungsi di sekitar akar, yaitu \(g'(1)=2/3\).
(b) Ketika nilai awal diubah menjadi \(x_0=2,5\), iterasi tidak konvergen dan nilai iterasi membesar. Hal ini dapat dijelaskan dengan \(g'(x)=2x/3\). Di sekitar \(x=2\), nilai turunannya adalah \(4/3\), lebih besar dari 1 dalam nilai absolut, sehingga iterasi cenderung menjauh dari titik tetap.
(c) Bentuk \(g_A(x)=(x+1)^{1/3}\) konvergen, sedangkan \(g_B(x)=x^3-1\) tidak konvergen untuk nilai awal yang diberikan. Syarat lokal konvergensi titik tetap adalah \(|g'(r)|<1\). Untuk \(g_A\), syarat tersebut terpenuhi di sekitar akar, sedangkan untuk \(g_B\), nilai absolut turunannya lebih besar dari 1.
(d) Untuk \(x=\cos x\), iterasi membutuhkan 34 langkah dengan toleransi \(10^{-6}\). Rasio galat berturutan mendekati \(\sin(r)\), yaitu sekitar 0,673612. Ini menunjukkan konvergensi linear.
(e) Rasio galat hampir konstan karena galat pada setiap langkah kira-kira dikalikan oleh nilai tetap \(|g'(r)|\). Pada persamaan ini, faktor tersebut sekitar 0,6736. Oleh karena itu, galat berkurang secara bertahap dengan perbandingan yang hampir sama pada setiap iterasi.
newton <- function(f, fd, x0, tol = 1e-6, maxit = 100) {
x <- x0
riwayat <- data.frame(k = 0, x = x0, fx = f(x0), selisih = NA)
for (k in 1:maxit) {
d <- fd(x)
if (d == 0)
return(list(akar = NA, iterasi = k, konvergen = FALSE, riwayat = riwayat))
x_baru <- x - f(x) / d
riwayat <- rbind(riwayat, data.frame(k = k, x = x_baru, fx = f(x_baru), selisih = abs(x_baru - x)))
if (abs(x_baru - x) < tol)
return(list(akar = x_baru, iterasi = k, konvergen = TRUE, riwayat = riwayat))
x <- x_baru
}
list(akar = x, iterasi = maxit, konvergen = FALSE, riwayat = riwayat)
}n1 <- newton(f1, fd1, 2, tol = 1e-12)
print(n1$riwayat)## k x fx selisih
## 1 0 2.000000000 2.000000000e+00 NA
## 2 1 1.500000000 2.500000000e-01 5.000000000e-01
## 3 2 1.416666667 6.944444444e-03 8.333333333e-02
## 4 3 1.414215686 6.007304883e-06 2.450980392e-03
## 5 4 1.414213562 4.510614104e-12 2.123899820e-06
## 6 5 1.414213562 4.440892099e-16 1.594724353e-12
## 7 6 1.414213562 -4.440892099e-16 2.220446049e-16cat("iterasi:", n1$iterasi, "\n")## iterasi: 6n3 <- newton(f3, fd3, 0.5, tol = 1e-6)
print(n3$riwayat)## k x fx selisih
## 1 0 0.5000000000 3.775825619e-01 NA
## 2 1 0.7552224171 -2.710331186e-02 2.552224171e-01
## 3 2 0.7391416661 -9.461538062e-05 1.608075096e-02
## 4 3 0.7390851339 -1.180977871e-09 5.653222907e-05
## 5 4 0.7390851332 0.000000000e+00 7.056460971e-10cat("iterasi:", n3$iterasi, " akar:", n3$akar, "\n")## iterasi: 4 akar: 0.7390851332r <- 0.7390851332151607
e <- abs(n3$riwayat$x - r)
cat("e[k+1]/e[k]^2 mulai k = 1:", e[3] / e[2]^2, e[4] / e[3]^2, "\n")## e[k+1]/e[k]^2 mulai k = 1: 0.2170904168 0.2207922788n2 <- newton(f2, fd2, 1.5, tol = 1e-10)
cat("x^3 - x - 1: iterasi", n2$iterasi, " akar", n2$akar, "\n")## x^3 - x - 1: iterasi 5 akar 1.324717957(a) Untuk \(x^2-2=0\) dengan nilai awal \(x_0=2\), metode Newton membutuhkan 6 iterasi dengan toleransi \(10^{-12}\). Hampiran akar mendekati \(\sqrt{2}\), yaitu 1,414213562. Galat dapat dihitung dari nilai mutlak selisih setiap hampiran terhadap \(\sqrt{2}\).
data.frame(
iterasi = n1$riwayat$k,
hampiran = n1$riwayat$x,
galat = abs(n1$riwayat$x - sqrt(2))
)## iterasi hampiran galat
## 1 0 2.000000000 5.857864376e-01
## 2 1 1.500000000 8.578643763e-02
## 3 2 1.416666667 2.453104294e-03
## 4 3 1.414215686 2.123901415e-06
## 5 4 1.414213562 1.594724353e-12
## 6 5 1.414213562 0.000000000e+00
## 7 6 1.414213562 2.220446049e-16(b) Untuk \(\cos x-x=0\) dengan nilai awal 0,5, metode Newton membutuhkan 4 iterasi dengan toleransi \(10^{-6}\). Rasio \(e_{k+1}/e_k^2\) mendekati 0,2208, sesuai konstanta yang dicantumkan pada modul. Hal ini menunjukkan konvergensi kuadratik.
(c) Untuk \(x^3-x-1=0\) dengan nilai awal 1,5, metode Newton membutuhkan 5 iterasi dengan toleransi \(10^{-10}\). Akar hampiran mendekati 1,324717957.
(d) Galat Newton menyusut lebih cepat daripada metode titik tetap pada \(x=\cos x\). Metode titik tetap memiliki konvergensi linear karena \(|g'(r)|\) sekitar 0,6736. Newton memiliki konvergensi kuadratik pada akar sederhana dengan turunan tidak nol, sehingga galat berikutnya kira-kira sebanding dengan kuadrat galat sebelumnya.
for (tl in c(1e-2, 1e-6, 1e-10)) {
cat("tol", tl,
" bisection", bisection(f3, 0, 1, tol = tl)$iterasi,
" titik tetap", titik_tetap(cos, 0.5, tol = tl, maxit = 500)$iterasi,
" newton", newton(f3, fd3, 0.5, tol = tl)$iterasi, "\n")
}## tol 0.01 bisection 7 titik tetap 11 newton 3
## tol 1e-06 bisection 20 titik tetap 34 newton 4
## tol 1e-10 bisection 34 titik tetap 57 newton 5Ringkasan jumlah iterasi:
toleransi <- c(1e-2, 1e-6, 1e-10)
data.frame(
Toleransi = format(toleransi, scientific = TRUE),
Bisection = sapply(toleransi, function(tl) bisection(f3, 0, 1, tol = tl)$iterasi),
Titik_Tetap = sapply(toleransi, function(tl) titik_tetap(cos, 0.5, tol = tl, maxit = 500)$iterasi),
Newton = sapply(toleransi, function(tl) newton(f3, fd3, 0.5, tol = tl)$iterasi)
)## Toleransi Bisection Titik_Tetap Newton
## 1 1e-02 7 11 3
## 2 1e-06 20 34 4
## 3 1e-10 34 57 5Newton menunjukkan pertambahan iterasi paling sedikit ketika toleransi diperkecil. Hal ini karena Newton memiliki konvergensi kuadratik, sedangkan Bisection dan iterasi titik tetap pada contoh ini menunjukkan konvergensi linear.
# (i) Siklus
fs <- function(x) x^3 - 2 * x + 2
fsd <- function(x) 3 * x^2 - 2
print(newton(fs, fsd, 0, maxit = 8)$riwayat$x)## [1] 0 1 0 1 0 1 0 1 0# (ii) Turunan nol
nz <- newton(f1, fd1, 0)
cat("konvergen:", nz$konvergen, "\n")## konvergen: FALSE# (iii) Akar kembar
fk <- function(x) (x - 1)^2
fkd <- function(x) 2 * (x - 1)
nk <- newton(fk, fkd, 3, tol = 1e-10, maxit = 60)
ek <- abs(nk$riwayat$x - 1)
cat("iterasi:", nk$iterasi, "\n")## iterasi: 35print(ek[2:6] / ek[1:5])## [1] 0.5 0.5 0.5 0.5 0.5# (iv) Akar pangkat tiga
fc <- function(x) sign(x) * abs(x)^(1/3)
fcd <- function(x) (1/3) * abs(x)^(-2/3)
print(newton(fc, fcd, 1, maxit = 6)$riwayat$x)## [1] 1 -2 4 -8 16 -32 64(a) Hasil jumlah iterasi untuk ketiga metode ditampilkan pada tabel keluaran kode. Untuk contoh ini, Bisection membutuhkan 7, 20, dan 34 iterasi; titik tetap membutuhkan 11, 34, dan 57 iterasi; sedangkan Newton membutuhkan 3, 4, dan 5 iterasi untuk toleransi berturut-turut \(10^{-2}\), \(10^{-6}\), dan \(10^{-10}\).
(b) Newton mengalami pertambahan iterasi paling sedikit ketika toleransi diperkecil karena konvergensi kuadratik membuat galat berkurang jauh lebih cepat. Bisection dan titik tetap pada contoh ini memiliki konvergensi linear sehingga memerlukan lebih banyak iterasi untuk mencapai toleransi yang lebih kecil.
(c) Kasus siklus. Barisan iterasi berulang antara nilai 0 dan 1. Karena nilai iterasi tidak mendekati akar, metode Newton tidak konvergen pada kasus ini.
(d) Kasus turunan nol. Ketika \(f'(x_0)=0\), rumus Newton tidak dapat
digunakan karena terjadi pembagian dengan nol. Fungsi menangani kondisi
ini dengan mengembalikan akar NA dan status
konvergen = FALSE.
(e) Kasus akar kembar. Untuk \(f(x)=(x-1)^2\), rasio galat berturutan mendekati 0,5. Artinya, galat berkurang menjadi sekitar setengah dari galat sebelumnya. Newton tetap konvergen, tetapi kecepatannya menjadi linear, bukan kuadratik.
(f) Kasus akar pangkat tiga. Dengan nilai awal 1, urutan iterasi menjadi 1, -2, 4, -8, 16, -32, dan 64. Nilai iterasi menjauh dari akar 0. Hal ini terjadi karena perilaku turunan fungsi di sekitar akar menyebabkan langkah Newton bergerak menjauhi akar.
(g) Kesimpulan pemilihan metode. Bisection dipilih ketika tersedia interval yang mengurung akar dan nilai fungsi pada kedua ujung interval berbeda tanda. Metode ini stabil dan terjamin konvergen, meskipun relatif lambat. Iterasi Titik Tetap dipilih ketika persamaan dapat ditulis dalam bentuk \(x=g(x)\) dan memenuhi syarat konvergensi lokal \(|g'(r)|<1\). Metode Newton dipilih ketika turunan fungsi dapat dihitung dan tebakan awal cukup baik, karena konvergensinya kuadratik pada akar sederhana. Namun, Newton perlu digunakan dengan hati-hati apabila turunannya nol, iterasi membentuk siklus, atau tebakan awal menyebabkan iterasi menjauh dari akar.
Berdasarkan praktikum, setiap metode memiliki karakteristik dan kondisi penggunaan yang berbeda. Bisection menawarkan kestabilan dengan syarat perubahan tanda pada interval awal. Titik Tetap bergantung pada pemilihan bentuk fungsi iterasi dan syarat turunannya. Newton dapat mencapai ketelitian dengan jumlah iterasi lebih sedikit, tetapi sensitif terhadap tebakan awal dan perilaku turunan fungsi.