Metode-Metode Umum dalam Zero Finding

Nama: Muhammad Haikal Fikri, NIM: 230605110067, Fakultas: Sains dan Teknologi, Program studi: Teknik Informatika, Universitas: Universitas Islam Negeri Maulana Malik Ibrahim Malang, Dosen pengajar: Prof. Dr. Suhartono, M.Kom, Tanggal kirim: 6 November 2023

Metode-Metode Umum dalam Zero Finding

Memahami Teknik Zero Finding:

Pencarian nol (zero finding), juga dikenal sebagai pencarian akar, adalah proses menemukan nilai variabel yang fungsinya sama dengan nol. Ini adalah konsep dasar dalam matematika dan memiliki banyak aplikasi dalam sains, teknik, dan analisis data.

Metode-Metode Penemuan Nol yang Umum:

A. Metode Bisection:

Metode pembagian dua (bisection) adalah pendekatan langsung untuk menemukan akar fungsi kontinu dalam interval tertentu. Metode ini secara berulang-ulang membagi dua interval dan mempersempit pencarian akar.

Berikut adalah cara kerja Metode Bisection:

1. Pilih sebuah Interval

Anda mulai dengan memilih sebuah interval [a, b] di mana Anda yakin bahwa akar fungsi f(x) ada. Interval ini harus memenuhi dua kriteria:

Fungsi f(x) haruslah kontinu pada [a, b]. Fungsi f(a) dan f(b) harus memiliki tanda yang berlawanan, yaitu f(a) > 0 dan f(b) < 0 atau f(a) < 0 dan f(b) > 0.

2. Temukan Titik Tengah

Hitung titik tengah dari interval [a, b] menggunakan rumus berikut:

c = (a + b) / 2

3. Mengevaluasi Fungsi

Evaluasi fungsi f(c) pada titik tengah c.

4. Perbarui Interval

Berdasarkan tanda f(c), Anda memperbarui interval [a, b] sebagai berikut:

Jika f(c) > 0, perbarui b menjadi c (yaitu, b = c). Jika f(c) < 0, perbarui a ke c (yaitu, a = c). Dalam kedua kasus tersebut, interval baru [a, b] sekarang lebih sempit dari interval sebelumnya.

5. Iterasi

Ulangi Langkah 2 sampai 4 secara berulang-ulang sampai interval menjadi sangat kecil (yaitu, |b - a| lebih kecil dari toleransi yang telah ditentukan) atau nilai fungsi pada titik tengah menjadi sangat dekat dengan nol.

6. Kriteria Konvergensi dan Penghentian

Metode Bisection menjamin konvergensi ke akar fungsi karena terus mempersempit interval. Anda dapat menentukan kriteria penghentian seperti jumlah iterasi maksimum atau tingkat akurasi tertentu (misalnya, |f(c)| < ε) untuk menghentikan proses.

Representasi Visual dalam R - Metode Bisection:

Kita dapat mendemonstrasikan secara visual metode bisection, yang merupakan salah satu teknik pencarian nol yang paling sederhana. Metode ini digunakan untuk menemukan akar dari fungsi kontinu dalam interval tertentu. Berikut adalah contoh bagaimana Anda dapat membuat representasi visual dari metode bisection di R:

# Define a simple function (e.g., f(x) = x^2 - 4)
f <- function(x) {
  return(x^2 - 4)
}

# Define the interval [a, b] where the root exists (e.g., [1, 3])
a <- 1
b <- 3

# Create a plot to visualize the function and the interval
curve(f, from = 0, to = 4, xlab = "x", ylab = "f(x)", main = "Contoh Metode Bisection")
abline(h = 0, col = "red")  # Add a horizontal line at y = 0
abline(v = c(a, b), col = "blue")  # Add vertical lines at the interval boundaries
points(c(a, b), c(0, 0), pch = 16, col = "blue")  # Mark interval boundaries

# Add a title
title(main = "Contoh Metode Bisection", sub = "Cari akar dari f(x) = x^2 - 4", cex.main = 1.2, cex.sub = 0.8)

B. Metode Newton-Raphson:

Metode Newton-Raphson, juga dikenal sebagai metode Newton, adalah teknik berulang yang menggunakan turunan suatu fungsi untuk memperkirakan akarnya.

Berikut adalah cara kerja Metode Newton-Raphson:

1. Pilih Tebakan Awal

Anda mulai dengan memilih tebakan awal, dilambangkan sebagai x₀. Tebakan awal ini harus cukup dekat dengan akar fungsi f(x) yang sebenarnya. Konvergensi metode ini bergantung pada kualitas tebakan awal ini.

2. Hitung Nilai Fungsi dan Turunannya

Evaluasi fungsi f(x) pada tebakan awal, yaitu menghitung f(x₀). Selain itu, hitung turunan dari fungsi tersebut, f’(x₀).

3. Memperbarui Aproksimasi

Gunakan rumus berikut untuk memperbarui aproksimasi akar:

x₁ = x₀ - f(x₀) / f’(x₀)

Rumus ini didasarkan pada gagasan bahwa akar fungsi adalah di mana garis singgung kurva pada titik (x₀, f(x₀)) memotong sumbu x. Titik (x₁, 0) adalah perkiraan baru untuk akar.

4. Iterasi

Ulangi Langkah 2 dan 3 secara berulang hingga Anda mencapai perkiraan yang cukup akurat untuk kebutuhan Anda. Metode ini akan konvergen ke akar yang sebenarnya ketika selisih antara aproksimasi yang berurutan (|xᵢ₊₁ - xᵢ|) menjadi sangat kecil, atau ketika f (xᵢ₊₁) mendekati nol.

5. Kriteria Konvergensi dan Penghentian

Metode ini dapat konvergen dengan cepat ke solusi yang sangat akurat, tetapi juga dapat menyimpang atau terjebak dalam pola osilasi jika tebakan awal buruk. Oleh karena itu, penting untuk menentukan kriteria penghentian untuk membatasi jumlah iterasi. Kriteria penghentian yang umum termasuk jumlah maksimum iterasi, tingkat akurasi tertentu, atau ketika |f (xᵢ) lebih kecil dari toleransi yang diberikan

Representasi Visual dalam R - Metode Newton-Raphson:

Representasi visual dari Metode Newton-Raphson di R. Dalam contoh ini, kita akan memvisualisasikan bagaimana Metode Newton-Raphson secara iteratif menemukan akar sebuah fungsi. Kita akan menggunakan fungsi f(x) = x^3 - 2x^2 - 5 sebagai contoh.

# Define the function f(x) = x^3 - 2x^2 - 5 and its derivative
f <- function(x) {
  return(x^3 - 2*x^2 - 5)
}

f_prime <- function(x) {
  return(3*x^2 - 4*x)
}

# Initial guess
x0 <- 2

# Create a plot to visualize the Newton-Raphson Method
library(ggplot2)

# Iterations
iterations <- 5  # Number of iterations to visualize

data <- data.frame(iteration = numeric(), x = numeric(), f_x = numeric(), f_prime_x = numeric())

# Perform iterations
for (i in 1:iterations) {
  f_x <- f(x0)
  f_prime_x <- f_prime(x0)
  x1 <- x0 - f_x / f_prime_x
  
  data <- rbind(data, data.frame(iteration = i, x = x0, f_x = f_x, f_prime_x = f_prime_x))
  
  x0 <- x1
}

# Create a ggplot
p <- ggplot(data, aes(x, f_x)) +
  geom_line() +
  geom_point(aes(color = factor(iteration)), size = 3) +
  geom_hline(yintercept = 0, color = "red") +
  theme_minimal() +
  labs(
    title = "Contoh Metode Newton-Raphson",
    x = "x",
    y = "f(x)"
  ) +
  scale_color_discrete(name = "Iterasi")

print(p)

Pada kode ini, pertama-tama kita mendefinisikan fungsi f(x) dan turunannya f_prime(x) seperti yang diperlukan untuk Metode Newton-Raphson. Kita mulai dengan tebakan awal x0, dan kita melakukan iterasi melalui metode ini untuk memperkirakan akarnya. Kode ini membuat sebuah plot menggunakan pustaka ggplot2 untuk memvisualisasikan kurva fungsi, pendekatan akar, dan konvergensi saat metode ini melakukan iterasi.

C. Metode Secant:

Metode Secant digunakan untuk menemukan perkiraan akar dari suatu fungsi dalam suatu interval tertentu. Alih-alih menggunakan turunan seperti Metode Newton-Raphson, Metode Secant menggunakan garis secant (garis yang menghubungkan dua titik pada kurva fungsi) untuk mempersempit pencarian akar secara berulang. Metode ini didasarkan pada prinsip bahwa kemiringan garis secant mendekati kemiringan garis singgung pada akar

Berikut adalah cara kerja Metode Secant:

1. Pilih dua titik awal, x0 dan x1, dalam interval di mana Anda yakin bahwa akarnya ada.

2. Hitung garis secant yang melewati (x0, f(x0)) dan (x1, f(x1)).

3. Temukan intersep x dari garis sekan ini, yang menjadi perkiraan baru untuk akar. Hal ini dilakukan dengan menggunakan rumus:

x2 = x1 - (f(x1) * (x1 - x0)) / (f(x1) - f(x0))

4. Ulangi langkah 2 dan 3 sampai akarnya diperkirakan dengan akurasi yang memadai.

Representasi Visual dalam R - Metode Secant:

Kita akan menggunakan fungsi yang sama f(x) = x^3 - 2x^2 - 5

# Define the function f(x) = x^3 - 2x^2 - 5
f <- function(x) {
  return(x^3 - 2*x^2 - 5)
}

# Initial guesses
x0 <- 2
x1 <- 3

# Create a plot to visualize the Secant Method
library(ggplot2)

# Iterations
iterations <- 5  # Number of iterations to visualize

data <- data.frame(iteration = numeric(), x0 = numeric(), x1 = numeric(), x2 = numeric(), f_x0 = numeric(), f_x1 = numeric())

# Perform iterations
for (i in 1:iterations) {
  f_x0 <- f(x0)
  f_x1 <- f(x1)
  x2 <- x1 - (f_x1 * (x1 - x0)) / (f_x1 - f_x0)
  
  data <- rbind(data, data.frame(iteration = i, x0 = x0, x1 = x1, x2 = x2, f_x0 = f_x0, f_x1 = f_x1))
  
  x0 <- x1
  x1 <- x2
}

# Create a ggplot
p <- ggplot(data, aes(x = x2, y = f_x1)) +
  geom_line() +
  geom_point(aes(x = x2, y = f_x1), color = "red", size = 3) +
  geom_hline(yintercept = 0, color = "blue") +
  theme_minimal() +
  labs(
    title = "Metode Secant",
    x = "x",
    y = "f(x)"
  )

print(p)

Pada kode ini, kita mendefinisikan fungsi f(x) dan memilih dua titik awal, x0 dan x1. Metode Secant diterapkan secara iteratif untuk mendekati akar fungsi, dan setiap iterasi divisualisasikan pada sebuah plot menggunakan pustaka ggplot2. Plot menunjukkan kurva fungsi, garis secant, dan konvergensi menuju akar.

Referensi :

Anne Greenbaum, Timothy P.(2012).Numerical Methods.Princeton University Press.

Richard L, Douglas Faires.(2010).Numerical Analysis.Boston.