1. Search with fixed step size

Metode ini merupakan teknik pencarian minimum dari sebuah fungsi dengan menggunakan titik awal dan ukuran langkah yang tetap. Metode ini mengasumsikan fungsi tersebut unimodal pada interval pencarian.

Algoritma:

1. Mulai dengan titik tebakan awal, misalnya \(x_1\).

2. Hitung \(f_1 = f(x_1)\).

3. Asumsikan ukuran langkah \(s\), temukan \(x_2 = x_1 + s\).

4. Hitung \(f_2 = f(x_2)\).

5. Jika \(f_2 < f_1\), dan karena kita mencari minimum, maka lanjutkan pencarian ke arah \(x_2\) dengan mengevaluasi \(x_3, x_4,\) dan seterusnya, sampai \(f_i > f_{i-1}\).

6. Jika \(f_2 > f_1\), arahkan pencarian ke arah berlawanan dengan mengevaluasi \(x_{-1}, x_{-2},\) dan seterusnya.

7. Jika \(f_2 = f_1\), maka minimum dianggap berada di antara \(x_1\) dan \(x_2\).

8. Proses pencarian dihentikan ketika nilai fungsi mulai meningkat, dan titik minimum diperkirakan berada di antara \(x_{i-1}\) dan \(x_i\) atau di antara \(x_{-j+1}\) dan \(x_{-j}\) tergantung arah yang diambil.

Contoh dan Kode R:

Misalkan kita ingin mencari minimum fungsi \(f(x) = x^2 + 4x + 6\) dengan titik awal \(x_1 = 0\) dan ukuran langkah \(s = 0.001\).

Kode R:

f <- function(x) x^2 + 4*x + 6
x1 <- 0
s <- 0.001
f1 <- f(x1)
x2 <- x1 + s
f2 <- f(x2)

# Menentukan arah pencarian
if (f2 > f1) {
  s <- -s
  x2 <- x1 + s
  f2 <- f(x2)
}

# Pencarian minimum
while(TRUE) {
  x_new <- x2 + s
  f_new <- f(x_new)
  if (f_new > f2) {
    break
  }
  x1 <- x2
  f1 <- f2
  x2 <- x_new
  f2 <- f_new
}

# Menentukan titik minimum
if (s > 0) {
  x_min <- (x1 + x2) / 2
} else {
  x_min <- (x1 + x2 - s) / 2
}

cat("Titik minimum diperkirakan berada di:", x_min, "dengan nilai f(x) =", f(x_min),"\n")

## Titik minimum diperkirakan berada di: -1.999 dengan nilai f(x) = 2.000001

Dalam contoh ini, kita memulai dari \(x_1 = 0\) dan menghitung \(f_1\). Kemudian kita mengambil langkah sebesar \(s = 0.001\) dan menghitung \(f_2\) di \(x_2 = x_1 + s\). Kita mengikuti algoritma seperti yang dijelaskan di atas untuk menentukan arah pencarian dan menemukan minimum.

Berikut adalah kurva asli dari f:

curve(f, from=-2.5,-1.5)

2. Exhaustive Search

Pencarian eksaustif adalah metode untuk menyelesaikan masalah di mana interval di mana optimum dapat berada diketahui secara finite. Ini dilakukan dengan mengevaluasi fungsi tujuan pada sejumlah titik yang sama rata dalam interval dan mengurangi interval ketidakpastian.

Algoritma:

1. Tentukan titik awal \(x_s\) dan titik akhir \(x_f\) dari interval ketidakpastian.

2. Pilih \(n\) titik yang sama rata di dalam interval \([x_s, x_f]\).

3. Evaluasi fungsi \(f(x)\) pada ke-\(n\) titik tersebut.

4. Temukan pasangan titik di mana terjadi penurunan nilai fungsi dan kemudian peningkatan, yang menandakan bahwa interval minimum berada di antara mereka.

5. Perkecil interval ketidakpastian dengan memilih interval di antara titik-titik ini sebagai interval baru.

6. Panjang interval ketidakpastian akhir, \(L_n\), dapat dihitung sebagai \(L_n = \frac{2}{n+1} L_0\), di mana \(L_0 = x_f - x_s\).

Contoh: Temukan minimum dari \(f = x(x - 1.5)\) di interval \([0.0, 1.0]\) hingga dalam 10% dari nilai eksak.

Untuk akurasi 10%, kita membutuhkan setidaknya \(n = 9\) titik evaluasi.

Kode R:

f <- function(x) x * (x - 1.5)
xs <- 0.0
xf <- 1.0
n <- 9 + 2 # nilai nol dan 1 dimasukan pada syntax, jadi n = 9 + 2
x_values <- seq(xs, xf, length.out = n)[c(-1,-n)]
f_values <- sapply(x_values, f)

# Cari interval dengan minimum
min_index <- which.min(f_values)
if (min_index > 1 && min_index < n) {
  interval <- c(x_values[min_index-1], x_values[min_index+1])
} else {
  interval <- c(xs, xf)
}

# Hitung panjang interval ketidakpastian
L0 <- xf - xs
Ln <- (interval[2] - interval[1])
cat("Interval ketidakpastian akhir: ", interval, "\n")

## Interval ketidakpastian akhir:  0.6 0.8

cat("Panjang interval ketidakpastian awal (L0): ", L0, "\n")

## Panjang interval ketidakpastian awal (L0):  1

cat("Panjang interval ketidakpastian akhir (Ln): ", Ln, "\n")

## Panjang interval ketidakpastian akhir (Ln):  0.2

cat("Rasio Ln/L0: ", Ln/L0, "\n")

## Rasio Ln/L0:  0.2

Dalam contoh ini, kita memulai dengan interval \([0.0, 1.0]\) dan membaginya menjadi 9 titik yang sama rata untuk mengevaluasi fungsi. Kemudian, kita menemukan interval di mana nilai fungsi menurun kemudian meningkat, yang mengindikasikan bahwa minimum berada di interval tersebut. Interval ketidakpastian akhir \(L_n\) dan rasionya terhadap \(L_0\) dihitung dan ditampilkan.

Berikut adalah hasil perhitungan dari exhaustive search

rbind(x_values,f_values)

##           [,1]  [,2]  [,3]  [,4] [,5]  [,6]  [,7]  [,8]  [,9]
## x_values  0.10  0.20  0.30  0.40  0.5  0.60  0.70  0.80  0.90
## f_values -0.14 -0.26 -0.36 -0.44 -0.5 -0.54 -0.56 -0.56 -0.54

Dapat terlihat bahwa nilai x7 dan x8 memiliki nilai f(x) yang sama. Artinya, kita bisa memilih nilai x optimum berada di 0.75.

3. Dichotomous Search

Pencarian Dikhotomis adalah metode pencarian sekuensial yang membagi interval ketidakpastian menjadi dua bagian yang hampir sama besar dengan melakukan eksperimen di dua titik yang sangat dekat dengan tengah interval. Berdasarkan nilai fungsi objektif di dua titik tersebut, setengah dari interval dieliminasi dari pertimbangan lebih lanjut.

Algoritma:

1. Tentukan interval awal ketidakpastian dengan titik awal \(x_s\) dan titik akhir \(x_f\), serta panjang interval \(L_0 = x_f - x_s\).

2. Pilih \(δ\), yang merupakan bilangan positif kecil, untuk menentukan seberapa dekat eksperimen akan dilakukan di tengah interval.

3. Hitung dua titik eksperimen \(x_1 = \frac{L_0}{2} - \frac{δ}{2}\) dan \(x_2 = \frac{L_0}{2} + \frac{δ}{2}\).

4. Evaluasi fungsi objektif \(f_1 = f(x_1)\) dan \(f_2 = f(x_2)\).

5. Jika \(f_1 < f_2\), maka interval baru akan menjadi \([x_s, x_2]\), jika tidak, interval baru akan menjadi \([x_1, x_f]\).

6. Ulangi langkah 2-5 pada interval baru hingga interval ketidakpastian mencapai ukuran yang diinginkan.

Contoh: Cari minimum dari \(f = x(x - 1.5)\) dalam interval \(0.0, 1.0\) hingga 10% dari nilai eksak.

Kode R:

f <- function(x) x * (x - 1.5)
xs <- 0.0
xf <- 1.0
L0 <- xf - xs
delta <- 0.001
n <- 6 # Karena n harus genap dan ≥ 5 sesuai perhitungan, kita menggunakan n=6

# Melakukan eksperimen
for (i in 1:(n/2)) {
  x1 <- (xs + xf)/2 - delta/2
  x2 <- (xs + xf)/2 + delta/2
  f1 <- f(x1)
  f2 <- f(x2)
  
  if (f1 < f2) {
    xf <- x2
  } else {
    xs <- x1
  }
}

# Titik tengah interval akhir diambil sebagai titik optimum
x_opt <- (xs + xf)/2
f_opt <- f(x_opt)

cat("Titik optimum diperkirakan: ", x_opt, "\n")

## Titik optimum diperkirakan:  0.8121875

cat("Nilai fungsi di titik optimum: ", f_opt, "\n")

## Nilai fungsi di titik optimum:  -0.5586327

Dalam kode di atas, kita memulai dengan interval \([0.0, 1.0]\) dan menggunakan \(δ = 0.001\) untuk menentukan kedekatan eksperimen dengan tengah interval. Kita melakukan iterasi proses pencarian dikhotomis sebanyak \(n/2\) kali, di mana \(n\) adalah jumlah total eksperimen yang diinginkan. Interval ketidakpastian diperkecil setelah setiap iterasi berdasarkan perbandingan nilai fungsi, dan akhirnya titik optimum diperkirakan berada di tengah interval ketidakpastian terakhir.

Berikut adalah kurva dari fungsi yang digunakan:

curve(f,-1,3)

4. Fibonacci Search Method

Metode Fibonacci adalah teknik pencarian minimum dari suatu fungsi satu variabel yang menggunakan deret Fibonacci untuk menentukan titik-titik eksperimen secara sekuensial. Ini memungkinkan pengurangan interval ketidakpastian dengan efisien.

Keterbatasan:

1. Interval awal ketidakpastian harus diketahui.

2. Fungsi harus unimodal di interval awal.

3. Optimum eksak tidak dapat ditentukan, hanya interval akhir ketidakpastian.

4. Jumlah evaluasi fungsi harus ditentukan sebelumnya.

Algoritma:

1. Tentukan interval awal ketidakpastian \([a, b]\) dan total jumlah eksperimen \(n\).

2. Gunakan deret Fibonacci untuk menghitung posisi eksperimen: \(F_0 = F_1 = 1\) dan \(F_n = F_{n-1} + F_{n-2}\).

3. Letakkan dua eksperimen pertama \(x_1\) dan \(x_2\) di dalam interval dengan menggunakan rasio Fibonacci.

4. Evaluasi fungsi di \(x_1\) dan \(x_2\), buang interval yang tidak mengandung minimum berdasarkan evaluasi tersebut.

5. Lanjutkan proses dengan menghitung posisi eksperimen baru dan mengurangi interval ketidakpastian.

Contoh:

Cari minimum dari \(f(x) = x(x - 1.5)\) dalam interval \([0,3]\) menggunakan metode Fibonacci dengan \(n = 6\).

Kode R:

# Fungsi Objektif
f <- function(x) x * (x - 1.5)

# Fungsi objektif tugas kuliah
# f <- function(x) {
#   return(0.65 - (0.75 / (1 + x^2)) - 0.65 * x * atan(1 / x))
# }

# Fungsi untuk menghasilkan n bilangan Fibonacci pertama
fibonacci <- function(n) {
  fn <- c(1, 1)
  for (i in 3:(n+1)) {
    fn <- c(fn, (fn[i-1] + fn[i-2]))
  }
  return(fn[-1])
}

# Metode Pencarian Fibonacci
fib_search <- function(f, xl, xr, n){
  F = fibonacci(n) # Call the fibonnaci number function
  L0 <<- xr - xl # Initial interval of uncertainty
  R1 = L0 # Initial Reduction Ratio
  Li = (F[n-2]/F[n])*L0
  xll <- c()
  xrr <- c()
  
  R = Li/L0
  Lb=c()
  
  for (i in 2:n)
  {
    if (Li > R1/2) {
      x1 = xr - Li
      x2 = xl + Li
    } else {
      x1 = xl + Li
      x2 = xr - Li
    }
    f1 = f(x1)
    f2 = f(x2)
    
    if (f1 < f2) {
      xr = x2
      
    } else if (f1 > f2) {
      xl = x1
    } else {
      xl = x1
      xr = x2
    }
    Li = (F[n - i]/F[n - (i - 2)])*R1 # New interval of uncertainty
    R1 = xr - xl
    R = c(R, Li/L0)
    Lb = c(Lb,Li)
    xll = c(xll,xl)
    xrr = c(xll,xr)
  }
  
  list1 <- list(x1, f(x1), R, Lb, xll, xrr) # Membuat sebagai list sehingga bisa dipanggil keluar dengan fungsi return.
  names(list1) <- c("x", "f(x)", "R", "L*", "a", "b") # Memberi nama pada elemen suatu list.
  list2 <- list(x2, f(x2), R, Lb, xll, xrr)
  names(list2) <- c("x", "f(x)", "R", "L*", "a", "b")
  if (f1 <= f2) {
    return(list1) # Final result
  } else {
    return(list2) # Final result 
  }
}

# Menjalankan pencarian Fibonacci
xl <- 0
xr <- 3
n <- 6
result <- fib_search(f, xl, xr, n)

# Menampilkan hasil
print(result)

## $x
## [1] 0.6923077
## 
## $`f(x)`
## [1] -0.5591716
## 
## $R
## [1] 0.38461538 0.38461538 0.23076923 0.15384615 0.07692308
## 
## $`L*`
## [1] 1.1538462 0.6923077 0.4615385 0.2307692
## 
## $a
## [1] 0.0000000 0.0000000 0.4615385 0.4615385 0.6923077
## 
## $b
## [1] 0.0000000 0.0000000 0.4615385 0.4615385 0.6923077 0.9230769

Kode R di atas menggunakan deret Fibonacci untuk mempersempit pencarian minimum fungsi. Pada setiap iterasi, kode menghitung dua titik eksperimen baru dan membandingkan nilai fungsi di titik-titik tersebut untuk menentukan interval mana yang akan dijaga. Proses ini diulangi sampai mencapai jumlah eksperimen yang diinginkan, yang pada akhirnya memberikan estimasi titik minimum fungsi.

Berikut adalah kurva dari fungsi yang digunakan

curve(f,-2,2)

5. Golden Section Method

Metode Golden Section adalah teknik pencarian minimum untuk fungsi satu variabel yang menggunakan golden ratio dalam pemilihan titik eksperimen. Berbeda dengan metode Fibonacci, jumlah total eksperimen tidak perlu ditentukan sebelumnya dan dapat diputuskan selama perhitungan.

Golden Ratio:

Golden Ratio (simbolisasi dengan \(\varphi\)) adalah nilai yang diperoleh dari persamaan kuadrat \(\varphi^2 - \varphi - 1 = 0\), yang memiliki solusi positif \(\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618\). Nilai ini sering digunakan dalam desain dan seni karena propertinya yang estetis dan sering ditemukan dalam pola alam.

Algoritma:

1. Tentukan interval awal ketidakpastian \([a, b]\).

2. Hitung \(L_2 = \frac{b - a}{\varphi^2}\) dan letakkan dua eksperimen pertama \(x_1\) dan \(x_2\) menggunakan rasio ini.

3. Evaluasi fungsi di \(x_1\) dan \(x_2\), dan buang bagian interval yang tidak mengandung minimum.

4. Lanjutkan proses dengan memperbarui posisi eksperimen baru berdasarkan golden ratio

5. Ulangi sampai interval ketidakpastian mencapai akurasi yang diinginkan.

Contoh:

Minimalkan fungsi \(f(x) = 0.65 - [0.75 / (1 + x^2)] - 0.65x \tan^{-1}(1/x)\) menggunakan metode Golden Section dengan \(n = 6\).

Kode R:

f <- function(x) {
  return(0.65 - (0.75 / (1 + x^2)) - 0.65 * x * atan(1 / x))
}

# Konstanta golden ratio
phi <- (1 + sqrt(5)) / 2

# Metode Golden Section
golden_section_search <- function(f, a, b, n) {
  # Menentukan interval awal ketidakpastian
  L0 <- b - a
  # Menghitung titik eksperimen pertama
  L2 <- L0 / phi^2
  x1 <- a + L2
  x2 <- b - L2
  f1 <- f(x1)
  f2 <- f(x2)
  
  for (i in 1:(n-1)) {
    if (f1 > f2) {
      a <- x1
      x1 <- x2
      L2 <- L0 / phi^(i+1)
      x2 <- b - L2
      f1 <- f2
      f2 <- f(x2)
    } else {
      b <- x2
      x2 <- x1
      L2 <- L0 / phi^(i+1)
      x1 <- a + L2
      f2 <- f1
      f1 <- f(x1)
    }
  }
  
  # Menentukan titik terakhir dan nilai fungsi
  x_final <- (a + b) / 2
  f_final <- f(x_final)
  
  return(list(x = x_final, f_x = f_final))
}

# Menjalankan metode Golden Section
a <- 0
b <- 3
n <- 20
result <- golden_section_search(f, a, b, n)

# Menampilkan hasil
print(result)

## $x
## [1] 0.480781
## 
## $f_x
## [1] -0.3100205

Dalam contoh kode di atas, metode Golden Section digunakan untuk mencari minimum fungsi. Pada setiap iterasi, posisi eksperimen diperbarui berdasarkan rasio emas, dan interval ketidakpastian dipotong menjadi bagian yang lebih kecil. Proses ini berlanjut hingga jumlah iterasi yang ditentukan tercapai atau hingga interval ketidakpastian mencukupi keakuratan yang diinginkan. Akhirnya, titik terakhir dan nilai fungsinya dihitung dan dikembalikan sebagai hasil.

Berikut adalah kurva dari fungsi:

curve(f,-3,3)

Perbandingan Kebaikan Metode Eliminasi

1. Interpolasi Kuadratik

Metode Interpolasi Kuadratik adalah teknik optimisasi satu dimensi yang tidak memerlukan turunan fungsi. Metode ini menggunakan nilai-nilai fungsi untuk menentukan langkah yang meminimalkan fungsi dengan cara mendekati fungsi dengan polinomial kuadratik dan mencari minimum dari polinomial tersebut.

Algoritma:

1. Normalisasi Vektor S (jika diperlukan): Dalam beberapa kasus, langkah pertama adalah normalisasi vektor pencarian. Ini tidak selalu diperlukan dalam optimisasi satu dimensi.

2. Tahap Awal: Tentukan tiga titik, \(\lambda = A\), \(\lambda = B\), dan \(\lambda = C\) di mana \(A < B < C\), dan hitung nilai fungsi di ketiga titik tersebut, \(f_A\), \(f_B\), dan \(f_C\).

3. Hitung Koefisien: Gunakan nilai fungsi yang dihitung untuk menyelesaikan koefisien \(a\), \(b\), dan \(c\) dari polinomial kuadratik yang mendekati fungsi \(f(\lambda)\): \[ h(\lambda) = a + b\lambda + c\lambda^2 \]

4. Cari Minimum Kuadratik: Temukan nilai \(\lambda^*\) yang meminimalkan \(h(\lambda)\) menggunakan rumus: \[ \lambda^* = -\frac{b}{2c} \] dan memeriksa kondisi kecukupan \(c > 0\).

5. Ulangi atau Refit: Jika \(\lambda^*\) cukup dekat dengan minimum sebenarnya \(\lambda^*\), proses selesai. Jika tidak, gunakan \(\lambda^*\) untuk menghitung nilai fungsi baru dan lakukan refitting dengan memilih dua titik terbaik dari \(A\), \(B\), \(C\), dan \(\lambda^*\) berdasarkan nilai fungsi mereka.

6. Kriteria Konvergensi: Ulangi proses interpolasi kuadratik sampai perbedaan antara \(h(\lambda^*)\) dan \(f(\lambda^*)\) lebih kecil dari suatu toleransi \(\epsilon\), atau sampai perubahan dalam \(\lambda^*\) antara iterasi kurang dari toleransi lain.

Contoh: Minimalkan fungsi \(f(x) = 0.65 - \left[ \frac{0.75}{(1 + x^2)} \right] - 0.65x \tan^{-1}(1/x)\) dalam interval antara 0 dan 10 dengan toleransi \(\epsilon = 10^{-4}\).

Kode R:

# Fungsi objektif yang akan diminimalkan
phi.f <- function(x) {
  return(0.65 - (0.75 / (1 + x^2)) - 0.65 * x * atan(1 / x))
}

# Implementasi metode interpolasi kuadratik
quadraticinterpolation <- function(phi.f, l = 0, u = 1, eps = 1e-6)
{
  #polynomials evaluated at 3 points(l, m, u) for interpolation: phi_fl, phi_fm, phi_fu
  if(l == u)
  {
    l <- 0
  }
  m <- (l + u)/2
  phi.fl <- phi.f(l)
  phi.fm <- phi.f(m)
  phi.fu <- phi.f(u)


  #a, b and c are coefficients of the polynomial (hx)
  y <- ((l - m)*(m - u)*(u - l))
  a <- (phi.fl*m*u*(u - m) + phi.fm*u*l*(l - u) + phi.fu*l*m*(m - l))/y
  b <- (phi.fl*(m^2 - u^2) + phi.fm*(u^2 - l^2) + phi.fu*(l^2 - m^2))/y
  c <- -(phi.fl*(m - u) + phi.fm*(u - l) + phi.fu*(l - m))/y

  alpha <- -b/(2*c)
  falpha <- phi.f(alpha)

  ncf <- 4

  hx <- function(x)  c*x^2 + b*x + a #environment global

  while((abs((hx(alpha) - falpha)) > eps))
  {
    #choice of l, m and C new values
    if(alpha <= m)
    {
      if(phi.fm >= falpha){
        u <- m; phi.fu <- phi.fm
        m <- alpha; phi.fm <- falpha
      }else{
        l <- alpha; phi.fl <- falpha
      }
    }else{
      if(phi.fm >= falpha){
        l <- m; phi.fl <- phi.fm
        m <- alpha; phi.fm <- falpha
      }else{
        u <- alpha; phi.fu <- falpha
      }

    }

    #refitting the function
    y <- ((l - m)*(m - u)*(u - l))
    a <- (phi.fl*m*u*(u - m) + phi.fm*u*l*(l - u) + phi.fu*l*m*(m - l))/y
    b <- (phi.fl*(m^2 - u^2) + phi.fm*(u^2 - l^2) + phi.fu*(l^2 - m^2))/y
    c <- -(phi.fl*(m - u) + phi.fm*(u - l) + phi.fu*(l - m))/y

    #quadratic interpolation

    alpha <- -b/(2*c)
    falpha <- phi.f(alpha)
    ncf <- ncf + 1

  }
  message("Method: Quadratic Interpolation. Number of calls of the objective function: ", ncf)
  return(alpha)
}

# Menentukan interval awal dan ketelitian
l <- -3
u <- 5
eps <- 1e-4

# Mencari minimum fungsi menggunakan metode interpolasi kuadratik
alpha_min <- quadraticinterpolation(phi.f, l, u, eps)

## Method: Quadratic Interpolation. Number of calls of the objective function: 11

# Hasil
cat("Nilai alpha yang meminimalkan fungsi adalah:", alpha_min, "\n")

## Nilai alpha yang meminimalkan fungsi adalah: -0.4856592

cat("Nilai minimum fungsi adalah:", phi.f(alpha_min), "\n")

## Nilai minimum fungsi adalah: -0.3100079

Berikut adalah kurva dari fungsi:

curve(phi.f,-3,3)

Dalam kode ini, kita mengimplementasikan proses interpolasi kuadratik sebagaimana dijelaskan dalam algoritma dan menggunakan fungsi untuk mencari nilai minimum \(\lambda\) yang meminimalkan fungsi objektif yang diberikan.

2. Newton-Raphson

Metode Newton-Raphson adalah teknik optimisasi yang menggunakan pendekatan kuadratik untuk menemukan titik minimum atau akar dari suatu fungsi. Ini didasarkan pada ekspansi seri Taylor dari fungsi dan menggunakan turunan pertama dan kedua untuk menentukan arah dan langkah yang diperlukan untuk mencapai minimum. Metode ini juga dikenal dengan konvergensi kuadratik, yang berarti bahwa kesalahan dalam estimasi titik minimum berkurang secara eksponensial di setiap iterasi, asalkan titik awal cukup dekat dengan minimum sebenarnya.

Algoritma:

1. Mulailah dengan tebakan awal \(\lambda_1\) untuk titik minimum \(\lambda^*\).

2. Hitung nilai fungsi \(f(\lambda)\), turunan pertama \(f'(\lambda)\), dan turunan kedua \(f''(\lambda)\) di titik \(\lambda_i\).

3. Gunakan nilai-nilai ini untuk menghitung perbaikan titik estimasi berikutnya menggunakan formula: \[ \lambda_{i+1} = \lambda_i - \frac{f'(\lambda_i)}{f''(\lambda_i)} \]

4. Ulangi proses ini hingga \(|f'(\lambda_{i+1})|\) cukup kecil (misalnya, kurang dari \(\varepsilon\) yang telah ditentukan).

Contoh:

Temukan minimum dari fungsi \(f(\lambda) = 0.65 - \frac{0.75}{1 + \lambda^2} - 0.65\lambda \tan^{-1}\left(\frac{1}{\lambda}\right)\) menggunakan Metode Newton-Raphson dengan titik awal \(\lambda_1 = 0.1\) dan \(\varepsilon = 0.01\) untuk pemeriksaan konvergensi.

Kode R:

# Memuat paket numDeriv
library(numDeriv)

newton.raphson <- function(f, a, b, tol = 1e-5, n = 1000) {
  x0 <- a # Nilai awal diatur ke batas bawah yang diberikan
  k <- numeric(n) # Inisialisasi untuk menyimpan hasil iterasi
  
  # Periksa batas atas dan bawah untuk melihat apakah pendekatan menghasilkan 0
  fa <- f(a)
  if (fa == 0.0) {
    return(a)
  }
  
  fb <- f(b)
  if (fb == 0.0) {
    return(b)
  }
  
  for (i in 1:n) {
    # Turunan pertama f'(x0)
    dx <- genD(func = f, x = x0)$D[1]
    # Menghitung nilai berikutnya x1
    x1 <- x0 - (f(x0) / dx)
    k[i] <- x1 # Menyimpan x1
    # Jika perbedaan antara x0 dan x1 cukup kecil, keluarkan hasilnya.
    if (abs(x1 - x0) < tol) {
      root.approx <- tail(k, n=1)
      res <- list('root approximation' = root.approx, 'iterations' = i)
      return(res)
    }
    x0 <- x1 # Jika Newton-Raphson belum mencapai konvergensi, tetapkan x1 sebagai x0 dan lanjutkan
  }
  warning('Too many iterations in method')
}

# Fungsi objektif yang ingin kita temukan akarnya
f <- function(x) {
  0.65 - 0.75 / (1 + x^2) - 0.65 * atan(1 / x)
}

# Menjalankan Metode Newton-Raphson
result <- newton.raphson(f, a = 0, b = 1, tol = 1e-5, n = 1000)

# Menampilkan hasil
print(result)

## $`root approximation`
## [1] 0
## 
## $iterations
## [1] 2

Berikut adalah kurva dari fungsi:

curve(f,-5,5)

Dalam contoh kode di atas, kita mendefinisikan fungsi objektif f, serta turunan pertama dan kedua dari f. Kemudian kita menerapkan Metode Newton-Raphson dengan titik awal dan toleransi yang ditentukan. Fungsi mengembalikan titik di mana f mencapai minimum lokal, dan kita mencetak jumlah panggilan fungsi serta nilai minimum.