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