Sep 13 2012

Interpolasi Newton


Seperti pada tulisan sebelumnya yang membahas masalah Interpolasi Lagrange, dimana interpolasi secara umum digunakan untuk mengkonstruksi suatu fungsi dari himpunan titik yang diberikan atau yang telah diketahui. Pada tulisan ini akan dibahas interpolasi yang kedua yaitu Interpolasi Newton.

Misal diberikan dua pasangan titik yaitu (x_0, f(x_0)) dan (x_1, f(x_1)) dengan x_0 \neq x_1. Maka dengan menggunakan persamaan garis (P_1(x)) yang telah diturunkan pada Interpolasi Lagrange dengan 2 titik, diperoleh

P_1(x) =  \left[ \dfrac{x-x_1}{x_0-x_1} \right] y_0 + \left[ \dfrac{x-x_0}{x_1-x_0} \right] y_1

= \left[ \dfrac{x-x_1+x_0-x_0}{x_0-x_1} \right] y_0 + \left[ \dfrac{x-x_0}{x_1-x_0} \right] y_1

= \left[ \dfrac{x-x_0}{x_0-x_1} \right] y_0 + \left[ \dfrac{-x_1+x_0}{x_0-x_1} \right] y_0 + \left[ \dfrac{x-x_0}{x_1-x_0} \right] y_1

= \left[ \dfrac{-(x-x_0)}{x_1-x_0} \right] y_0 + y_0 + \left[ \dfrac{x-x_0}{x_1-x_0} \right] y_1

= y_0 + \left[ \dfrac{y_1-y_0}{x_1-x_0} \right] (x-x_0)

P_0(x) = a_0 + a_1(x-x_0)

dengan a_1 = \dfrac{y_1-y_0}{x_1-x_0} atau a_1 = \dfrac{f(x_1)-f(x_0)}{x_1-x_0} dan bentuk ini dinamakan bentuk selisih terbagi (divided differences) dan dapat ditulis a_1 = f[x_1, x_0]

Kemudian Interpolasi Newton untuk 3 titik yaitu (x_0, f(x_0)), (x_1, f(x_1)) dan (x_2, f(x_2)) dengan x_0 \neq x_1 \neq x_2 atau menggunakan polinom derajat 2 diperoleh

P_2(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1)

Substitusi titik-titik (x_0, f(x_0)), (x_1, f(x_1)) dan (x_2, f(x_2)) ke P_2(x)

f(x_0) = a_0 + a_1(x_0-x_0) + a_2(x_0-x_0)(x_0-x_1)

f(x_0) = a_0 + a_1(0) + a_2(0)(x_0-x_1)

a_0 = f(x_0) = f[x_0]

f(x_1) = a_0 + a_1(x_1-x_0) + a_2(x_1-x_0)(x_1-x_1)

f(x_1) = f(x_0) + a_1(x_1-x_0) + a_2(x_1-x_0)(0)

a_1 = \dfrac{f(x_1)-f(x_0)}{x_1-x_0}

= \dfrac{f[x_1]-f[x_0]}{x_1-x_0}

= f[x_1]-f[x_0]

f(x_2) = a_0 + a_1(x_2-x_0) + a_2(x_2-x_0)(x_2-x_1)

f(x_2) = f(x_0) + \left[ \dfrac{f(x_1)-f(x_0)}{x_1-x_0} \right] (x_2-x_0) + a_2(x_2-x_0)(x_2-x_1)

a_2(x_2-x_0)(x_2-x_1) = f(x_2)-f(x_0) + f(x_1)-f(x_1) - \left[ \dfrac{f(x_1)-f(x_0)}{x_1-x_0} \right] (x_2-x_0)

= \left[ \dfrac{f(x_2)-f(x_1)}{x_2-x_1} \right] (x_2-x_1) + \left[ \dfrac{f(x_1)-f(x_0)}{x_1-x_0} \right] (x_1-x_0) -\left[ \dfrac{f(x_1)-f(x_0)}{x_1-x_0} \right] (x_2-x_0)

= \left[ \dfrac{f(x_2)-f(x_1)}{x_2-x_1} \right] (x_2-x_1) + \left[ \dfrac{(f(x_1)-f(x_0))(x_1)-(f(x_1)-f(x_0))(x_0)}{x_1-x_0} \right] - \left[ \dfrac{(f(x_1)-f(x_0))(x_2)-(f(x_1)-f(x_0))(x_0)}{x_1-x_0} \right]

= \left[ \dfrac{f(x_2)-f(x_1)}{x_2-x_1} \right] (x_2-x_1)- \left[ \dfrac{f(x_1)-f(x_0)}{x_1-x_0} \right] (x_2-x_1)

a_2(x_2-x_0) =  \left( \dfrac{f(x_2)-f(x_1)}{x_2-x_1} \right) - \left( \dfrac{f(x_1)-f(x_0)}{x_1-x_0} \right)

a_2 = \dfrac{ \left( \frac{f(x_2)-f(x_1)}{x_2-x_1} \right)-\left( \frac{f(x_1)-f(x_0)}{x_1-x_0} \right)}{x_2-x_0}

= \dfrac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}

Jadi tahap pembentukan rumus Interpolasi Newton adalah sebagai berikut

P_1(x) = a_0 + a_1(x-x_0)

P_2(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1)

P_3(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1) + a_3(x-x_0)(x-x_1)(x-x_2)

.

.

.

P_n(x) = a_0 + a_1(x-x_0) + \ldots + a_n(x-x_0)(x-x_1) \ldots (x-x_{n-1})(x-x_1)(x-x_n)

dengan selisih terbaginya masing-masing

a_0 = f[x_0] = f(x_0) = y_0

a_1 = f[x_0, x_1] = \dfrac{f[x_1]-f[x_0]}{x_1-x_0} = \dfrac{y_1-y_0}{x_1-x_0}

a_2 = f[x_0, x_1, x_2] = \dfrac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}

a_3 = f[x_0, x_1, x_2, x_3] = \dfrac{f[x_1,x_2,x_3]-f[x_0,x_1,x_2]}{x_3-x_0}

.

.

.

a_n = f[x_0, x_1, \ldots, x_3] = \dfrac{f[x_1, \ldots,x_n]-f[x_0, \ldots,x_{n-1}]}{x_n-x_0}

Contoh :

Konstruksikan fungsi f(x) = \cos x dari titik-titik x_0 = 0.2, x_1 = 0.3 dan x_2 = 0.4 menggunakan Interpolasi Newton

Penyelesaian :

a_0 = f[x_0] = f(0.2) = \cos (0.2) = 0.98

a_1 = f[x_0, x_1] = \dfrac{\cos(0.3)- \cos(0.2)}{0.3-0.2}

= \dfrac{0.9553-0.98}{0.1}

= -0.247

f[x_1, x_2] = \dfrac{\cos(0.4)- \cos(0.3)}{0.4-0.3}

= \dfrac{0.9211-0.9553}{0.1}

= -0.332

a_2 = f[x_0, x_1, x_2] = \dfrac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}

= \dfrac{-0.332-(-0.247)}{0.4-0.2}

= -0.425

P_2(x) = a_0 + a_1(x-x_0) + a_2(x-x_0)(x-x_1)

= 0.98 -0.247(x -0.2) -0.425(x -0.2)(x -0.3)

= 0.98 -0.247x + 0.0494 -0.425x^2 + 0.2125x -0.0255

= 1.0039 -0.0345x -0.425x^2

1 comments on “Interpolasi Newton”

Tinggalkan komentar