Monday, June 22, 2015

Komputasi Numeris: Metode Muller (2)

Pendahuluan

Seperti yang telah dijelaskan sebelumnya, Metode Muller adalah sebuah metode pencarian akar persamaan dengan 3 titik aproksimasi. Seperti halnya Metode Newton-Raphson, metode Muller juga memiliki pendekatan deret Taylor untuk mencari seluruh akar dari sebuah persamaan polinomial seperti dibawah ini:


dapat kita temukan akar-nya satu demi satu menggunakan aturan deflasi sebagai berikut:

dimana x* adalah salah satu akar persamaan dari persamaan polinomial di atas.

Algoritma

Seperti sudah dijelaskan sebelumnya, berikut algoritma Muller:

1. Mulai
2. Metode Muller diawali dengan menentukan 3 variabel x0, x1 dan x2
3. Cari fx0, fx1 dan fx2

4. Cari koefisien a,b dan c persamaan kuadrat berikut menggunakan aturan Cramer
(selengkapnya dapat dibaca di sini)

5. Cari nilai x3 dengan formula:
6. Hitung error = |x3-x2|
7. Rubah koefisien x0=x1, x1=x2 dan x2=x3.
8. Jika error masih lebih besar dari toleransi error yang diberikan, ulangi langkah 3 dan jika tidak, maka tampilkan x3 sebagai akar persamaan.
9. Selesai

Algoritma di atas dapat dimodifikasi untuk mencari akar-akar dari sebuah polinomial menggunakan formula:
Contoh:

Carilah akar-akar polinomial berikut dengan menggunakan metode Muller:
Perhatikan tabel excel berikut:

Keterangan:
  1. Kolom yang a4, a3, a2, a1 dan a0 (berwarna kuning) mewakili koefisien persamaan yang akan dicari.
  2. Kolom x0, x1 dan x2 (berwarna biru) mewakili nilai-nilai aproksimasi. Pada iterasi ke 0, nilai-nilai ini kita berikan sembarang yang penting tidak boleh sama. Perhatikan aturan/ formula Cramer di atas. Pembagi (penyebut) tidak boleh bernilai nol.
  3. Kolom x3 (berwarna merah) adalah nilai aproksimasi berikutnya. (Kita cari setelah seluruh kolom terisi)
  4. Kolom fx0, fx1 dan fx2 (berwarna pink), adalah nilai fungsi dari x0, x1 dan x2.
  5. Nilai a, b dan c (berwarna hijau) adalah koefisien-koefisien persamaan kuadrat Muller.
  6. Kolom b4, b3, b2, b1 dan b0 (berwarna orange) adalah persamaan deflasi dari persamaan sebelumnya atau persamaan yang terbentuk setelah satu akar ditemukan.
  7. Hasil-nya ditemukan pada iterasi ke 7 (diberi tanda merah)

Pencarian akar berikutnya
Pencarian akar berikutnya dilakukan dengan mengganti koefisien a4, a3, a2, a1 dan a0 dengan b4, b3, b2, b1 dan b0 seperti ditunjukkan pada tabel excel sebagai berikut:


Proses ini dapat diulang untuk pencarian akar ke 3 dan 4.

Menulis kode program
Setelah kita pahami algoritma Metode Muller di atas, saatnya menulis kode program. Berikut kode programnya.

//Menulis Identitas Program
/*
Program mencari akar polinomial dengan Metode Muller
Haruno Sajati, S.T., M.Eng.
Prodi Teknik Informatika
Sekolah Tinggi Teknologi Adisutipto
*/

//Deklarasi Header

#include<iostream.h>
#include<math.h>

//Fungsi Utama
void main()
{
  //Deklarasi variabel
  float koeff[10],koefg[10],x0,x1,x2,x3,error,fx0,fx1,fx2,a,b,c,d;
  int j,k,iterasi;

  //Inisialisasi persamaan
  koeff[4]=1;
  koeff[3]=2.8;
  koeff[2]=-0.38;
  koeff[1]=-6.3;
  koeff[0]=-4.2;

  for (k=4;k>=1;k--)
  {
     //Inisialisasi aproksimasi, error dan iterasi
     x0=-0.5;
     x1=0;
     x2=0.5;

     cout <<"Mencari akar ke : " << k << endl;
     error=1;
     iterasi=0;

     //Lakukan perulangan jika error > toleransinya
     while (error>0.00001)
     {
        //Mencari fx0, fx1 dan fx2
        fx0=0;
        for (j=4;j>=1;j--)
        {
          fx0=fx0+(koeff[j]*(pow(x0,j)));
        }
        fx0=fx0+koeff[0];

        fx1=0;
        for (j=4;j>=1;j--)
        {
          fx1=fx1+(koeff[j]*(pow(x1,j)));
        }
        fx1=fx1+koeff[0];

        fx2=0;
        for (j=4;j>=1;j--)
        {
          fx2=fx2+(koeff[j]*(pow(x2,j)));
        }
        fx2=fx2+koeff[0];

        //Mencari koefisien a,b dan c persamaan fiting kuadrat
        c=fx2;
        b=(((x0-x2)*(x0-x2)*(fx1-fx2))-((x1-x2)*(x1-x2)*(fx0-fx2)))/((x0-x2)*(x1-x2)*(x0-x1));
        a=(((x1-x2)*(fx0-fx2))-((x0-x2)*(fx1-fx2)))/((x0-x2)*(x1-x2)*(x0-x1));

        d=(b*b)-(4*a*c);

        //Mencari x3 (aproksimasi berikutnya
        if (b<0)
        {
          x3=((-2*c)/(b-sqrt(d)))+x2;
        }
        else
        {
          x3=((-2*c)/(b+sqrt(d)))+x2;
        }

        //Mencari error
        error=x3-x2;
        if (error<0)
          error*=-1;

        //Perubahan aproksimasi
        x0=x1;x1=x2;x2=x3;
        iterasi++;
    }

    //Menampilkan output
    cout << "Akar persamaan = " << x3 << endl;
    cout << "Jumlah iterasi = " << iterasi << endl;

    //Inisialisasi persamaan berikutnya
    koefg[4]=0;
    for(j=3;j>=0;j--)
    {
      koefg[j]=koeff[j+1]+(koefg[j+1]*x3);
    }

    for(j=4;j>=0;j--)
    {
      koeff[j]=koefg[j];
    }
    cout << "---------------------------------------" << endl;

  }
}


Menjalankan Program

Berikut adalah eksekusi programnya:

 
Semoga bermanfaat

Komputasi Numeris: Metode Muller (1)

Pendahuluan

Metode Muller diperkenalkan oleh David Eugene Muller (1924-2008), seorang profesor matematika dan computer science di University of Illinois.
Mirip dengan metode Newton yang sudah kita bahas sebelumnya di sini dan di sini,  Metode Muller digunakan untuk menyelesaikan sistem persamaan non linier. Berbeda dengan metode Newton, metode Muller tidak membutuhkan persamaan diferensial (turunan) dari persamaan yang akan dicari sehingga formula rumit seperti di bawah ini, tidak perlu dicari persamaan turunannya. Hore!


Metode Muller memiliki prinsip yang mirip dengan Metode Secant hanya saja berbeda dengan metode Secant yang memanfaatkan kurva fitting linear, metode Muller menggunakan kurva fitting berbentuk parabola. Inilah sebabnya berbeda dengan metode Secant yang hanya membutuhkan 2 nilai aproksimasi pembentuk kurva fitting linear, metode muller membutuhkan 3 nilai aproksimasi untuk membentuk kurva fitting parabolic.


Algortima
 
Untuk memahami metode Muller, perhatikan gambar di bawah ini:


Kita memiliki persamaan f(x) yang akan dicari akar persamaannya. Seperti pada metode-metode numeris yang lain, pertama kita tentukan nilai aproksimasi awal. Sesuai dengan yang dijelaskan sebelumnya, metode Muller membutuhkan 3 nilai aproksimasi awal (x0, x1 dan x2) misalnya -0.5, 0 dan 0.5.
Setelah ditentukan nilai x0, x1 dan x2, selanjutnya kita cari nilai f(x0), f(x1) dan f(x2). Jika mengacu pada contoh persamaan:
Persamaan ini memiliki grafik fungsi sebagai berikut:

maka:
f(-0.5) = -2.524232814
f(0.5) = 0.268980884
f(0) = -1

Berarti saat ini, kita sudah memiliki 3 titik sebagai "modal" pembentuk kurva fitting g(x) yaitu:
  1. (x0, f(x0)) = (-0.5, -2.524232814)
  2. (x1, f(x1)) = (0.5, 0.268980884)
  3. (x2, f(x2)) = (0,-1)
Pertanyaan berikutnya adalah bagaimana persamaan parabola yang melewati 3 titik? Untuk menjawab pertanyaan ini, kita substitusikan saja tiga titik tersebut pada persamaan:
sehingga terbentuk tiga persamaan dengan tiga variabel. Persamaan yang terbentuk adalah:
  1. -2.524232814 = 0.25a - 0.5b + c
  2. 0.268980884 = 0.25a + 0.5b + c
  3. -1 = c
Benar! Matriks!. Tiga persamaan dengan tiga variabel tersebut akan kita selesaikan dengan aturan Cramer Method dimana [1]:

sehingga nilai a, b, c berturut-turut adalah sebagai berikut:
a = -0.510503861
b = 2.793213698
c = -1

Sehingga persamaan kuadrat yang terbentuk adalah:
Setelah persamaan parabola g(x) ditemukan, saatnya mencari akar persamaan kuadrat dengan rumus:
Operator +/- ditentukan dari nilai b. Nilai x3 yang terbentuk adalah 0.385117564. Nilai ini akan menggeser x0, x1 dan x2 sebelumnya sehingga iterasi berikutnya x0=x1, x1=x2 dan x2=x3 atau x0=0, x1=-0.5 dan x2=0.385117564.
Perhatikan tabel excel berikut:


Setelah iterasi ke 3 nilai x3 telah "stabil" sehingga dapat dikatakan persamaan tersebut telah ditemukan akarnya.

Listing Program

Setelah kita pahami algoritma metode Muller tersebut, saatnya kita menulis kode programnya:
/*
Program mencari akar persamaan non linear
Menggunakan Metode Muller
Haruno Sajati, S.T., M.Eng.
Program Studi Teknik Informatika
Sekolah Tinggi Teknologi Adisutjipto
*/


//Deklarasi Header
#include<iostream.h>
#include<math.h>

//Fungsi Utama
void main()
{
  //Deklarasi Variabel
  float x0,x1,x2,x3,fx0,fx1,fx2,a,b,c,d,error;
  int iterasi;

  //inisialisasi nilai awal aproksimasi
  x0=-0.5;
  x1=0;
  x2=0.5;

  error=1;
  iterasi=0;

  //Proses diulang selama error > toleransi
  while (error>0.00001)
  {
        fx0 = 4*sin(x0)-pow(2.718282,x0);
        fx1 = 4*sin(x1)-pow(2.718282,x1);
        fx2 = 4*sin(x2)-pow(2.718282,x2);

        c=fx2;
        b=(((x0-x2)*(x0-x2)*(fx1-fx2))-((x1-x2)*(x1-x2)*(fx0-fx2)))/((x0-x2)*(x1-x2)*(x0-x1));
        a=(((x1-x2)*(fx0-fx2))-((x0-x2)*(fx1-fx2)))/((x0-x2)*(x1-x2)*(x0-x1));

        d=(b*b)-(4*a*c);

        if (b<0)
        {
            x3=((-2*c)/(b-sqrt(d)))+x2;
        }
        else
        {
            x3=((-2*c)/(b+sqrt(d)))+x2;
        }

        //Mencari error
        error=x3-x2;
        if (error<0)
        {
            error*=-1;
        }

        //Mencari aproksimasi berikutnya
        x0=x1;x1=x2;x2=x3;

        //Menghitung jumlah iterasi dan proteksi infinit loop
        iterasi++;
        if (iterasi > 40)
        {
            cout << "Gagal ditemukan akarnya" << endl;
            break;
        }
  }

  //Menampilkan hasil
  cout << "Akar persamaan = " << x3 << endl;
  cout << "Jumlah iterasi = " << iterasi << endl;

}


Tampilan Eksekusi Program


Akar berikutnya silahkan dibaca di sini (Metode Muller dengan Deret Taylor)
Semoga bermanfaat

Daftar Pustaka

[1] Komputasi Numeris: Teori dan Aplikasi, P. Buyung Kosasih, Penerbit Andi, Yogyakarta, 2006

Friday, June 19, 2015

Komputasi Numeris: Metode Newton Raphson (2)

Pendahuluan
Pada bagian ini, kita akan membahas mengenai Newton Raphson dengan deret Taylor Method. Dengan menggunakan prinsip ini, seluruh akan persamaan linear polinomial dapat kita temukan. Misal untuk persamaan polinomial:



akar-akar dari persamaan tersebut akan dicari menggunakan metode deflasi yang dijabarkan menjadi:

Dimana x* adalah salah satu akar persamaan yang kita cari. Metode deflasi akan "mengurangi" derajat persamaan hingga derajat persamaan pangkat 2. Setelah itu tinggal diselesaikan menggunakan rumus "abc":
Permasalahannya adalah dari mana koefisien nilai b-nya dan bagaimana metode Newton-Raphson diterapkan. Pertanyaan tersebut sebenarnya adalah pertanyaan tunggal: Bagaimana Metode Newton Raphson dapat menemukan nilai b-nya.

Algoritma
Metode Newton-Raphson dengan memanfaatkan deret Taylor sebenarnya hanya modifikasi dari algoritma Newton-Raphson yang sudah kita pelajari sebelumnya.
Rumus Newton Raphson dirubah menjadi:
Nilai g(x) kita peroleh dengan langkah-langkah sebagai berikut:

Perhatikan contoh berikut. Sebagai contoh persamaan yang akan kita cari akarnya adalah sebagai berikut:
Maka:
a4=1; a3=2.8; a2=-0.38; a1=-6.3 dan a0=-4.2. Dengan nilai aproksimasi awal x0 = 0 maka nilai fx0 dapat dicari f(0) = -4.2

Sehingga:

b3=a4+(b4x0) = 1+0=1
b2=a3+(b3x0) = 2.8
b1=a2+(b2x0) = -0.38
b0=a1+(b1x0) = -6.3
Nilai-nilai b di atas disusun menjadi persamaan g(x) sebagai berikut:
Nilai g(x0) dapat ditemukan yaitu g(0) = -6.3. Setelah nilai x0, fx0 dan gx0 sudah didapatkan, maka x1 dapat dicari = 0 - (-4.2 / -6.3) = -0.6667. Perhatikan formula excel berikut:

Iterasi berikutnya dapat dilihat sebagai berikut:


Dari tabel dapat dilihat pada iterasi ke 7, nilai x tidak lagi "bergerak" secara signifikan, sehingga dapat disimpulkan nilai x telah stabil dan merupakan salah satu akar persamaan di atas.

Akar berikutnya
Proses pencarian akar berikutnya (akar kedua) dilakukan dengan cara mengganti koefisien a pada f(x) dengan koefisien b. Langkah ini secara otomatis ikut mengganti nilai b pada berikutnya. Nilai b yang baru inilah yang nantinya mengganti nilai a (lagi) pada pencarian akar berikutnya.
Perhatikan contoh tabel excel berikut:

Sama seperti proses pencarian akar pertama, proses berakhir setelah terjadi kestabilan nilai x (nilai x saat ini tidak berbeda jauh dengan nilai x sebelumnya) yang ditunjukkan pada iterasi ke 6.
Penncarian akar ke 3 dan ke empat ditunjukkan pada tabel excel berikut:




Selesai. Kita sudah menemukan seluruh akar dari contoh persamaan di atas. Setelah itu saatnya kita menulis kode program dari alur algoritma di atas.

Listing Program

//Menulis identitas program
/*
Algoritma Newton Raphson dengan Deret Taylor
Haruno Sajati, S.T., M.Eng.
Program Studi Teknik Informatika
Sekolah Tinggi Teknologi Adisutjipto Yogyakarta

jati@stta.ac.id

*/

//Deklarasi Header

#include<iostream.h>
#include<math.h>

void main()
{
  int pangkat, i, k, iterasi;
  float a[10], b[10], x, x1, xawal, fa, fb, fc;

  //Inisialisasi persamaan

  pangkat = 4;
  a[4] = 1;
  a[3] = 2.8;
  a[2] = -0.38;
  a[1] = -6.3;
  a[0] = -4.2;

  xawal = 0;

  for (k=pangkat; k>=1; k--)

  {
    b[k]=0;

    cout << "persamaan berikutnya : ";
    for (i=pangkat; i>=0; i--)

    {
      cout << a[i] << "x^" << i << " + ";
    }
    cout << endl;

    fc = 1;
    iterasi=0;
 

    //proses perulangan ketika nilai error > toleransi error
    while (fc > 0.00001)
    {

      for (i=k; i>=1; i--)

      {
        b[i-1] = a[i]+(b[i]*x1);
      }

      //cari pembilang (fx)    

      fa=0;
      for (i=k; i>=1; i--)

      {
        fa = fa + a[i]*pow(x,i);
      }
      fa = fa + a[0];

      //cari penyebut g(x)    

      fb=0;
      for (i=k; i>=1; i--)

      {
        fb = fb + b[i]*pow(x,i);
      }
      fb = fb + b[0];

      //Proses pencarian aprox berikutnya dg Newton-Raphson

      x1=x-(fa/fb);

      //mencari error (fc)

      fc=0;
      for (i=k; i>=1; i--)

      {
        fc = fc + a[i]*pow(x,i);
      }
      fc = fc + a[0];

      if (fc < 0)
        fc = fc*-1;

      //Mengganti aproksimasi sebelumnya dengan saat ini

      x=x1;

      //menghitung jml iterasi. Jika iterasi > 40 maka stop
      iterasi++;
      if (iterasi > 40) 

      {
        cout << "gagal ditemukan\n";
        break;
      }
    }
  

  //Menampilkan output
    cout << "akar persamaan = " << x << endl;
    for (i=pangkat; i>=0; i--)

    {
      a[i]=b[i];
    }
    xawal=x1;

  }
}


Eksekusi Program
Berikut hasil eksekusi dari listing program di atas.

Contoh dapat diunduh di sini

Semoga bermanfaat

Komputasi Numeris: Metode Newton Raphson (1)

Pendahuluan
Metode Newton Raphson diperkenalkan oleh Sir Isaac Newton (1643-1727) dan Joseph Raphson (1648–1715) yang dipergunakan untuk pencarian akar real dari persamaan non linear. Metode Newton Raphson ini memiliki keuntungan dibandingkan metode yang lain seperti Bisection atau Secant karena hanya membutuhkan satu nilai aproksimasi dan jumlah iterasi (konvergensi) yang lebih sedikit terutama jika nilai aproksimasi awal yang dipilih berada "dekat" dengan akar yang akan dicari.

Algoritma

Metode Newton-Raphson memiliki dua macam pendekatan turunan:
1. Geometrical Method
2. Taylor Method (akan dibahas berikutnya)

Geometrical Method.
Metode Newton Raphon dengan metode geometri idenya adalah kita akan menarik garis lurus (linear) yang menyinggung (x0 , f(x0)) dimana x0 adalah aproksimasi awal yang kita tentukan. Perhatikan gambar berikut:
Keterangan:
Garis singgung yang melalui (x0, f(x0)) akan memotong sumbu x di x1. Nilai x1 inilah yang menjadi aproksimasi berikutnya.
Nilai x1 kita peroleh menggunakan formula:


Begitu seterusnya hingga perbedaan nilai x0 dan x1 kurang dari toleransi error yang kita tentukan.
Algoritma metode Newton Raphson dengan metode geometri adalah sebagai berikut:
  1. Mulai
  2. Tentukan nilai aproksimasi awal x0
  3. Cari nilai fx0 dan f'x0
  4. Cari nilai x1 = x0 - (fx0/f'x0)
  5. Cari nilai error  = |x1-x0|
  6. x0 = x1
  7. Jika nilai error > toleransi error maka ulangi langkah 2, jika tidak tampilan x0 sebagai akar persamaan yang dicari
  8. Selesai
Listing Program

Berikut contoh kode program penyelesaian sistem persamaan non linear

dengan metode Newton-Raphson Geometrical Method

//Menulis identitas program
/*
Algoritma Newton Raphson dengan Geometrical Method
Haruno Sajati, S.T., M.Eng.
Program Studi Teknik Informatika
Sekolah Tinggi Teknologi Adisutjipto Yogyakarta

jati@stta.ac.id

*/

//Deklarasi Header
#include<iostream.h>;
#include<math.h>;
 

//Program utama
void main()
{
  float x1,x2,toleransi;
  int iterasi;


  //Step 2: Menentukan aproksimasi awal

  cout << "Masukkan X1 : ";
  cin >> x1;


  toleransi=1;
  iterasi=1;
  x2=0;


  //Step 7: proses perulangan jika error > toleransi error 
  while (toleransi > 0.0001) 
  {
    cout << "Iterasi " << iterasi << endl;
    cout << "X1 = " << x1 << endl;

    //Step 3 dan 4: penentuan aproximasi berikutnya

    x2=x1-((((x1*x1)-(5*x1)+6))/((2*x1)-5));
    cout << "X2 = " << x2 << endl;

    //Step 5: Menghitung nilai error

    toleransi=(x2-x1);
    if (toleransi<0)
    {
      toleransi*=-1;
    }
    cout << "Toleransi = " << toleransi << endl;
    cout << endl;

    
    //Step 6: Perubahan nilai aproksimasi
    x1=x2;

    iterasi++;
  }
  cout << "Akar Persamaan = " << x2 << endl;
}


Berikut tampilan eksekusi programnya:





































Unduh contoh di sini.

Selamat mencoba. Semoga bermanfaat..