Metode Numerik : Incremental Search Method

"The only way to learn a new programming language is by writing programs in it." Yup ini adalah kalimat yang saya baca ketika pertama kali belajar bahasa pemrograman dan kali ini saya akan mencoba menerapkannya. Metode Numerik adalah materi yang saya pilih di samping Signal Processing untuk menuliskannya dalam bahasa pemrograman (karena Metode Numerik adalah mata kuliah favorit saya hehehe). Ada banyak bahasan dalam Metode Numerik, namun kali ini saya hanya akan membahas tentang bagaimana cara mencari akar-akar persamaan (roots of equations) menggunakan metode numerik dan menuliskan metode tersebut dalam beberapa bahasa pemrograman yaitu Octave (.m), Julia (.jl), Python (.py) dan C (.c).

Incremental Search Method:

Adalah metode numerik yang digunakan untuk menentukan sebuah interval dimana terdapat sebuah akar penyelesaian dari suatu persamaan f(x) yakni x. Interval ini yang nantinya akan digunakan sebagai Starting Points oleh metode-metode yang akan dijelaskan pada postingan berikutnya untuk menentukan akar penyelesaiannya.

Bagaimana Incremental Search Method ini bekerja? Metode ini sangatlah mudah. Ide dasar dari metode ini yakni: jika f(x1) dan f(x2) memiliki tanda yang berlawan (hasil perhitungannya adalah  [+] positif dan [-] negatif), maka terdapat minimal satu akar penyelesaian dalam interval (x1,x2). Jika intervalnya sangat kecil, bisa jadi hanya terdapat satu akar penyelesaian.

Namun ada beberapa masalah pada metode ini.

1. Jika inkriment cukup besar, maka ada kemungkinan dua akar penyelesaian yang sangat dekat (selisih dari dua akar lebih kecil dari inkriment) tidak terdeteksi.
2. Dua akar penyelesaian yang sama tidak akan terdeteksi.
3. Singularity dari persamaan f(x) dapat menyebabkan salah penentuan akar persamaan.

Dan mungkin saja masih ada beberapa masalah lagi yang tidak masuk dalam list di atas, silahkan disearch di google.

Contoh soal:

$f(x) = x^3 - 10 x^2 + 5$

Misalkan kita ingin mencari interval dimana terdapat sebuah akar penyelesaian dari persamaan di atas. Kita asumsikan kondisi awal untuk interval adalah (0,2) dengan inkriment 0.2.

Berikut ini adalah code-nya

#- Octave

1. Simpan code berikut dengan nama "fungsi.m"

function y = fungsi(x)
  y = x.^3 - 10*x.^2 + 5;

2. Simpan code berikut dengan nama "rootsearch.m"

function [x1,x2] = rootsearch(func,a,b,dx)

x1 = a;
f1 = feval(func,x1);

x2 = a + dx;
f2 = feval(func,x2);

while (f1*f2) > 0.
  if x1 >= b
    x1 = NaN;
    x2 = NaN;
    break
  end
  x1 = x2;
  f1 = f2;
  x2 = x1 + dx;
  f2 = feval(func,x2);
end

3. Terakhir, simpan code berikut dengan nama "main.m" dan run code ini.


close all
clear
clc

a = 0;
b = 2;
dx = 0.2;
[x1,x2] = rootsearch(@fungsi,a,b,dx);
fprintf(stderr,[">>> akar penyelesaian berada dalam rentang (" num2str(x1) ...
  ", " num2str(x2) ")\n"])

Hasilnya seperti di bawah ini

akar penyelesaian berada dalam rentang (0.6, 0.8)

Untuk Octave, code-nya dapat didownload di link ini.


#- Julia

1. Simpan code berikut dengan nama "main.jl"

function fungsi(x)
  return x.^3 - 10*x.^2 + 5
end

function rootsearch(func,a,b,dx)
  x1 = a
  f1 = func(x1)

  x2 = a + dx
  f2 = func(x2)

  while (f1*f2) > 0.0
    x1 >= b && return NaN, NaN
  
    x1 = x2
    f1 = f2
    x2 = x1 + dx
    f2 = func(x2)
  end
 
  return x1, x2
end

a = 0
b = 2
dx = 0.2
x1, x2 = rootsearch(fungsi,a,b,dx)
println(">>> akar penyelesaian berada dalam rentang (",x1,", ",x2,")\n")

Jalankan code main.jl dengan cara ketik di command line Julia

Julia > include("main.jl")

Hasilnya seperti di bawah ini

>>> akar penyelesaian berada dalam rentang (0.6000000000000001, 0.8)

Namun perlu diperhatikan saat menjalankan program ini di Julia, terlebih dahulu pastikan file-nya berada di direktori yang sama dengan Julia. Untuk mengecek lokasi direktori ketik saja

Julia > pwd()

Untuk mengganti direktori gunakan cd() contoh seperti di bawah ini.

Julia > cd("/Lokasi1/Lokasi2/")

Untuk Julia, code-nya dapat didownload di link ini.


#-Python

1. Simpan code berikut dengan nama "main.py" (code berikut berjalan dengan lancar di python3.x)

import math

def fungsi(x):
  return x**3 - 10 * x**2 + 5

def rootsearch(func,a,b,dx):
  x1 = a
  f1 = func(x1)
 
  x2 = a + dx
  f2 = func(x2)
 
  while (f1*f2 > 0.):
    if x1 >= b:
      return float('nan'),float('nan')
    x1 = x2
    f1 = f2
    x2 = x1 + dx
    f2 = func(x2)
  return x1, x2

a = 0
b = 2
dx = 0.2
x1, x2 = rootsearch(fungsi,a,b,dx)
print(">>> akar penyelesaian berada dalam rentang (%f,%f) \n"% (x1,x2))


Buka file di atas menggunakan IDLE python3, kemudian jalankan code main.py dengan cara klik F5 (atau pilih run).

Hasilnya seperti di bawah ini
  
>>> akar penyelesaian berada dalam rentang (0.600000,0.800000)

Untuk Python, code-nya dapat didownload di link ini.


#-C language

1. Simpan code berikut dengan nama "main.c"

# include <stdio.h>
# include <math.h>
# include <stdlib.h>

double func(double);
double *rootsearch(double (*func)(double),double a, double b, double dx);

main()
{
  double a=0., b=2., dx=0.2, *result, x1, x2;
  result = rootsearch(&func,a,b,dx);
  x1 = result[0];
  x2 = result[1];
  free(result);
  printf("\n>>> akar penyelesaian berada dalam rentang (%f,%f)\n\n",x1,x2);
}

double *rootsearch(double (*func)(double),double a, double b, double dx)
{
  double x1, x2, f1, f2, *result, NaN;
  result = (double *) malloc((size_t)(2*sizeof(double)));
 
  x1 = a;
  f1 = func(x1);
 
  x2 = a + dx;
  f2 = func(x2);
 
  while (f1*f2 > 0.)
  {
    if (x1 >= b)
    {
      result[0] = NaN;
      result[1] = NaN;
      return result;
    }
    x1 = x2;
    f1 = f2;
    x2 = x1 + dx;
    f2 = func(x2);
  }
  result[0] = x1;
  result[1] = x2;
  return result;
}

double func(double x)
{
  return (pow(x,3) - 10.*pow(x,2) + 5.);
}

2) compile file berikut, di Ubuntu, buka terminal dan cukup ketik

> gcc -o rootsearch -s -O4 -lm

3) kemudian Run

> ./rootsearch

Hasilnya seperti di bawah ini

>>> akar penyelesaian berada dalam rentang (0.600000,0.800000)


Untuk C, code-nya dapat didownload di link ini.


Selamat mencoba dan semoga bermanfaat.