Interpolasi Polinom Newton

Nama    : Zulyarachma Utasaputri

Kelas    : A2.1

Nim      : STI202303597

Interpolasi Polinom Newton

Polinomial Newton, adalah sebuah fungsi polinomial yang digunakan untuk melakukan interpolasi pada sekumpulan titik data yang diketahui.

  • Polinom newton ini memiliki beberapa keunggulan dibandingkan metode interpolasi lainnya, seperti:
  1. Mudah dihitung: Rumus untuk menghitung polinom Newton relatif sederhana dan mudah diimplementasikan.
  2. Akurat: Polinom Newton dapat memberikan hasil yang akurat, terutama untuk data yang halus dan tidak terlalu berfluktuasi.
  3. Efisien: Polinom Newton dapat dihitung dengan cara yang efisien, terutama untuk data dengan banyak titik data.            

Rumus Polinom Newton:

P(x) = f(x0) + f[x0, x1](x - x0) + f[x0, x1, x2](x - x0)(x - x1) 

+ ... + f[x0, x1, ..., xn](x - x0)(x - x1) ... (x - xn-1)

Dimana:

       ·         P(x)  Adalah polinomial Newton yang ingin dicari.

       ·         f(x0), f(x1), ..., f(xn) adalah nilai fungsi pada titik-titik  x0, x1, ..., xn.

       ·         f[x0, x1] adalah selisih pertama antara  f(x0) dan  f(x1).

       ·         f[x0, x1, x2] adalah selisih kedua antara f[x0, x1] dan f[x1, x2].

       ·         ... dan seterusnya.

            Selisih pertama, f[x0, x1], dihitung dengan rumus:

f[x0, x1] = f(x1) - f(x0)

Selisih kedua, f[x0, x1, x2], dihitung dengan rumus:

f[x0, x1, x2] = f[x1, x2] - f[x0, x1]

...` dan seterusnya.

Ø      Polinom Newton dinyatakan dalam hubungan rekursif sebagai berikut:

(i)                 rekurens: Pn(x) = Pn-1(x) + an(x - x0)(x - x1) … (x - xn-1)

(ii)               basis: P0(x) = a

Jadi, tahapan pembentukan polinom Newton adalah sebagai berikut:

P1(x)    = P0(x) + a1(x - x0)

 = a0 + a1(x - x0)

                        P2(x)    = P1(x) + a2(x - x0)(x - x1)

= a0 + a1(x - x0) + a2(x - x0)(x - x1)

                        P3(x)    = P2(x) + a3(x - x0)(x - x1)(x - x2)

= a0 + a1(x - x0) + a2(x - x0)(x - x1) + a3(x - x0)(x - x1)(x - x2)

                        pn(x)     = Pn-1(x) + an(x - x0)(x - x1) … (x - xn-1)

 = a0 + a1(x - x0) + a2(x - x0)(x - x1) + a3(x - x0)(x - x1)(x - x2)

    + … + an(x - x0)(x - x1) … (x - xn-1)

Nilai konstanta a0, a1, a2, ..., an merupakan nilai selisih-terbagi, (divided divided-diffrence diffrence) dengan nilai masing-masing:

a0 = f(x0)

 a1 = f [x1, x0]

a2 = f [x2, x1, x0] …

an = f [xn, xn-1, …, x1, x0]

yang dalam hal ini,








Dengan demikian polinom Newton dapat ditulis dalam hubungan rekursif sebagai

(i)                 rekurens:

Pn(x) = Pn-1(x) + (x - x0) (x - x1) … (x - xn-1) f [xn, xn-1, …, x1, x0]

(ii)               basis:

 P0(x) = f (x0)

atau dalam bentuk polinom yang lengkap sebagai berikut:

Pn(x) =            f (x0) + (x - x0) f [x1, x0] + (x - x0)(x - x1) f [x2, x1, x0]

+ (x - x0) (x - x1) … (x - xn-1) f [xn, xn-1, …, x1, x0]

Nilai selisih terbagi ini dapat dihitung dengan menggunakan tabel yang disebut tabel selisih- terbagi,

  • misalnya tabel selisih-terbagi untuk empat buah titik (n = 3) berikut:

i

xi

Yi = f(xi)

ST - 1

ST - 2

ST - 3

0

1

2

3

x0

x1

x2

x3

f(x0)

f(x1)

f(x2)

f(x3)

f[x1,x0]

f[x2,x1]

f[x3,x1]

f[x2,x1,x0]

f[x3,x2,x1]

f[x3,x2,x1,x0]

                 Keterangan: ST = Selisih-Terbagi

  •  Contoh: Hitunglah f(9.2) dari nilai-nilai (x, y) yang diberikan pada tabel di bawah ini dengan polinom Newton derajat 3.

i

xi

yi

0

1

2

3

8.0

9.0

9.5

11.0

2.079442

2.197225

2.251292

2.397895

 

Penyelesaian:

Tabel selisih-terbagi:

I

xi

yi

ST - 1

ST - 2

ST - 3

0

1

2

3

8.0

9.0

9.5

11.0

2.079442

0.117783

-0.006433

0.000411

2.197225

2.251292

2.397895

0.108134

0.097735

-0.005200

 

     Contoh cara menghitung nilai selisih-terbagai pada tabel adalah:

           

       



   


    Polinom Newton-nya (dengan x0 = 8.0 sebagai titik data pertama) adalah:

    f(x) ≈ P3(x) = 2.079442 + 0.117783(x - 8.0) - 0.006433(x - 8.0)x - 9.0) +

0.000411(x - 8.0)(x - 9.0)(x - 9.5)

    Taksiran nilai fungsi pada x = 9.2 adalah

    f(9.2) ≈ P3(9.2)  = 2.079442 + 0.141340 - 0.001544 - 0.000030

   = 2.219208

    Nilai sejati f(9.2) = ln(9.2) = 2.219203 (7 angka bena).

  •  Contoh: Bentuklah polinom Newton derajat satu, dua, tiga, dan empat yang menghampiri fungsi f(x) = cos(x) di dalam selang [0.0 , 4.0] dan jarak antar titik adalah 1.0. Lalu, taksirlah nilai fungsi di x = 2.5 dengan polinom Newton derajat tiga.

    Penyelesaian: Dengan jarak antar titik 1.0, maka titik yang digunakan adalah pada x0 = 0.0, x1 = 1.0,     x2 = 3.0, x3 = 4.0. Tabel selisih terbaginya adalah:

i

xi

yi

ST - 1

ST - 2

ST - 3

ST - 4

0

1

2

3

4

0.0

1.0

2.0

3.0

4.0

1.0000

0.5403

-0.4161

-0.9900

-0.6536

-0.4597

-0.9564

-0.5739

0.3363

f(x3,x2)

-0.2484

0.1913

0.4551

0.1466

0.0880

-0.0147

    Maka, polinom Newton derajat 1, 2, dan 3 dengan x0 = 0.0 sebagai titik data pertama adalah

cos(x) ≈ p 1 (x) = 1.0000 - 0.4597( x - 0.0)

cos(x) ≈ p 2 (x) = 1.0000 - 0.4597( x - 0.0) - 0.2484( x - 0.0)( x - 1.0)

cos(x) ≈ p 3 (x) = 1.0000 - 0.4597( x - 0.0) - 0.2484( x - 0.0)( x - 1.0)

   + 0.1466( 0.1466( x - 0.0)( x - 1.0)( x - 2.0)

cos(x) ≈ p 4 (x) = 1.0000 - 0.4597( x - 0.0) - 0.2484( x - 0.0)( x - 1.0)

  + 0.1466( x - 0.0)( x - 1.0) ( x - 2.0) –

  0.0147( x - 0.0)( x - 1.0)( x - 2.0)( x - 3.0)



























      

    

    Taksiran nilai fungsi di x = 2.5 dengan polinom derajat tiga adalah

           cos(2.5) ≈ P3(2.5) = 1.0000 - 0.4597(2.5 - 0.0) –

                    0.2484(2.5 - 0.0)(2.5 - 1.0) + 0.1466(2.5 –

                   0.0)(2.5 - 1.0)(2.5 - 2.0)

             ≈ -0.8056

    Nilai sejati f(2.5) adalah

f(2.5) = cos(2.5) = -0.8011

    sehingga solusi hampiran mengandung galat sejati sebesar

ε = -0.8011 - (-0.8056) = -0.004

 

Kelebihan Polinom Newton

  • Karena polinom Newton dibentuk dengan menambahkan satu suku tunggal dengan polinom derajat yang lebih rendah, maka ini memudahkan perhitungan polinom derajat yang lebih tinggi dalam program yang sama [CHA91]. Karena alasan itu, polinom Newton sering digunakan khususnya pada kasus yang derajat polinomnya tidak diketahui terlebih dahulu.
  • Penambahan Penambahan suku -suku polinom polinom secara beruntun beruntun dapat dijadikan kriteria untuk menentukan tercapainya titik berhenti, yaitu apakah penambahan suku-suku yang lebih tinggi tidak lagi secara berarti memperbaiki nilai interpolasi, atau malahan menjadi lebih buruk.
  • Tabel selisih terbagi dapat dipakai berulang-ulang untu k memperkirakan nilai fungsi pada nilai x yang berlainan.

    Galat Interpolasi Polinom











    Dari rumus di atas, galat polinom interpolasi, selain bergantung pada nilai x yang diinterpolasi, juga        bergantung pada turunan fungsi semula.

    Tinjau Q n+1 pada rumus E(x) 
        Q n+1 (x) = ( x - x 0)( x - x 1) ... ( x - x n )

   Misalkan x0, x1, …, xn berjarak sama. Grafik fungsi Q untuk enam titik yang berjarak sama                   ditunjukkan pada Gambar:









Berdasarkan Q6(x) yang berosilasi pada Gambar di atas terlihat bahwa:

  1.  di titik-titik data xi, nilai Q6(xi) = 0, sehingga galat interpolasi E(xi) = 0
  2. di titik tengah selang, nilai Q6(x) minimum, sehingga E(x) juga minimum
  3.  di titik-titik sekitar ujung selang, Q6(x) besar, sehingga E(x) juga besar
  4. bila ukuran selang [x0, x6] semakin besar, amplitudo osilasi meningkat dengan cepat.

Kesimpulan: Galat interpolasi minimum terjadi untuk nilai x di pertengahan selang. Untuk mendapatkan galat interpolasi yang minimum, pilihlah selang [x0,x, xn] sedemikian sehingga x terletak di tengah selang tersebut.



Komentar

Posting Komentar