Join Me On Facebook

Minggu, 25 November 2012

Bentuk Newton


interpolasi polinominal p(x)=anxn+an-1xn-1+...+a1x+a0 adalah bentuk standar. Tetapi ada juga yang menggunakan bentuk lain . Contohnya , kita mencari interpolasi titik dari data (x0,y0),(x1,y1),(x2,y2),(x3,y3).
Jika kita tuliskan P(x)=a3x3+a2x2+a1x+a0
bentuk equivalentnya : p(x)=a3(x-x0)3+p(x)=a2(x-x0)2+p(x)=a1(x-x0)+a0
dari kondisi interpolasi p(x0)=yo maka didapatkan a0=yo , sehingga dapat kita tuliskan menjadi
p(x)=b3(x-x0)(x-x1)(x-x2)+b2(x-x0)(x-x1)+b1(x-x0)+b0 inilah yang disebut newton form dari interpolasi , sehingga kita dapatkan :
p(x0)=b0
p(x1)=b1h1+b0
p(x2)=b2(h1+h2)h2+b1(h1+h2)+b0
p(x3)=b3(h1+h2+h3)(h2+h3)h3+b2(h1+h2+h3)(h2+h3)+b1(h1+h2+h3)+b0
sehingga jika kita tuliskan dalam bentuk matrix:

Operator Refleksi

Berdasarkan operator T:R2 -> R2 yang memetakan tiap vektor dalam gambaran simetris terhadap sumbu y, dimisalkan w=T(x), maka persamaan yang berhubungan dengan x dan w adalah:
x1 = -x = -x + 0y
x2 = y = 0x + y
atau dalam bentuk matrik : \begin{bmatrix} -1 & 0\\ 0 & 1\\ \end{bmatrix} \begin{bmatrix} x\\ y\\ \end{bmatrix} = \begin{bmatrix} w_1\\ w_2\\ \end{bmatrix}
Secara umum, operator pada R2 dan R3 yang memetakan tiap vektor pada gambaran simetrinya terhadap beberapa garis atau bidang datar dinamakan operator refleksi. Operator ini bersifat linier.

Operator Proyeksi

Berdasarkan operator T:R2 -> R2 yang memetakan tiap vektor dalam proyeksi tegak lurus terhadap sumbu x, dimisalkan w=T(x), maka persamaan yang berhubungan dengan x dan w adalah:
x1 = x = x + 0y
x2 = 0 = 0x + 0y
atau dalam bentuk matrik : \begin{bmatrix} 1 & 0\\ 0 & 0\\ \end{bmatrix} \begin{bmatrix} x\\ y\\ \end{bmatrix} = \begin{bmatrix} w_1\\ w_2\\ \end{bmatrix}
Persamaan tersebut bersifat linier, maka T merupakan operator linier dan matrikx T adalah: \begin{bmatrix} T\\ \end{bmatrix} = \begin{bmatrix} 1 & 0\\ 0 & 0\\ \end{bmatrix}
Secara umum, sebuah operator proyeksi pada R2 dan R3 merupakan operator yang memetakan tiap vektor dalam proyeksi ortogonal pada sebuah garis atau bidang melalui asalnya.

Operator Rotasi

Sebuah operator yang merotasi tiap vektor dalam R2 melalui sudut ɵ disebut operator rotasi pada R2. Untuk melihat bagaimana asalnya adalah dengan melihat operator rotasi yang memutar tiap vektor searah jarum jam melalui sudut ɵ positif yang tetap. Unutk menemukan persamaan hubungan x dan w=T(x), dimisalkan ɵ adalah sudut dari sumbu x positif ke x dan r adalah jarak x dan w. Lalu, dari rumus trigonometri dasar x = r cos Θ ; y = r cos Θ dan w1 = r cos (ɵ + ɸ) ; w2= r sin (ɵ + ɸ)
Menggunakan identitas trigonometri didapat:
w1 = r cos ɵ cos ɸ - r sin ɵ sin ɸ
w2 = r sin ɵ cos ɸ + r cos ɵ sin ɸ
kemudian disubtitusi sehingga:
w1 = x cos Θ - y sin Θ
w2 = x sin Θ + y cos Θ
Persamaan di atas merupakan persamaan linier, maka T merupakan operator linier sehingga bentuk matrik dari persamaan di atas adalah: \begin{bmatrix} T\\ \end{bmatrix} = \begin{bmatrix} cos\Theta & -sin\Theta\\ sin\Theta & cos\Theta\\ \end{bmatrix}

Interpolasi Polinomial


Dengan menganggap masalah pada interpolasi polinomial untuk deret n + 1 di titik (x0,y0)...., (xn,yn). Maka, kita diminta untuk menemukan kurva p(x) = amx^m + am-1x^{m-1} + ... + a1x + a0 dari sudut minimum yang melewati setiap dari titik data. Kurva ini harus memenuhi

\begin{matrix}
{y_0}& = &a_mx_0^m &+& a_{m-1}x_0^{m-1} &+...+& a_1x_0 &+& a_0\\
{y_1}& = &a_mx_1^m &+& a_{m-1}x_1^{m-1} &+...+& a_1x_1 &+& a_0\\
\vdots& &\vdots& &\vdots& &\vdots& &\vdots\\
{y_n}& = &a_mx_n^m &+& a_{m-1}x_n^{m-1} &+...+& a_1x_n &+& a_0\\
\end{matrix}

karena xi diketahui, ini akan menuju pada sistem matrik di bawah ini

\begin{bmatrix}
1 & x_0 & x_0^2 & \cdots & x_0^m\\
1 & x_1 & x_1^2 & \cdots & x_1^m\\
\vdots & \vdots & \vdots & \cdots &\vdots\\
1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^m\\
1 & x_n & x_n^2 & \cdots & x_n^m\\
\end{bmatrix}\begin{bmatrix}
a_0\\
a_1\\
\vdots\\
a_{m-1}\\
a_m\\
\end{bmatrix} = \begin{bmatrix}
y_0\\
y_1\\
\vdots\\
y_{n-1}\\
y_n\\
\end{bmatrix}

Ingat bahwa ini merupakan sistem persegi dimana n = m. Dengan menganggap n = m memberikan sistem di bawah ini untuk koefisien interpolasi polinomial p(x):

\begin{bmatrix}
1 & x_0 & x_0^2 & \cdots & x_0^n\\
1 & x_1 & x_1^2 & \cdots & x_1^n\\
\vdots & \vdots & \vdots & \cdots &\vdots\\
1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^n\\
1 & x_n & x_n^2 & \cdots & x_n^n\\
\end{bmatrix}\begin{bmatrix}
a_0\\
a_1\\
\vdots\\
a_{n-1}\\
a_n\\
\end{bmatrix} = \begin{bmatrix}
y_0\\
y_1\\
\vdots\\
y_{n-1}\\
y_n\\
\end{bmatrix} (1)

Matrix di atas diketahui sebagai Matrix Vandermonde; kolom j merupakan elemen pangkat j-1. Sistem linier pada (1) disebut menjadi Sistem Vandermonde.

Contoh soal:
Cari interpolasi polinomial pada data (-1,0),(0,0),(1,0),(2,6) menggunakan Sistem Vandermonde.
Jawab:
Bentuk Sistem Vandermonde(1):
\begin{bmatrix}
1 & x_0 & x_0^2 & x_0^3\\
1 & x_1 & x_1^2 & x_1^3\\
1 & x_2 & x_2^2 & x_2^3\\
1 & x_3 & x_3^2 & x_3^3\\
\end{bmatrix}\begin{bmatrix}
a_0\\
a_1\\
a_2\\
a_3\\
\end{bmatrix} = \begin{bmatrix}
y_0\\
y_1\\
y_2\\
y_3\\
\end{bmatrix}

Untuk data di atas, kita mempunyai

\begin{bmatrix}
1 & -1 & 1 & -1\\
1 & 0 & 0 & 0\\
1 & 1 & 1 & 1\\
1 & 2 & 4 & 8\\
\end{bmatrix}\begin{bmatrix}
a_0\\
a_1\\
a_2\\
a_3\\
\end{bmatrix} = \begin{bmatrix}
0\\
0\\
0\\
6\\
\end{bmatrix}

\begin{bmatrix}
1 & -1 & 1 & -1 & 0\\
1 & 0 & 0 & 0 & 0\\
1 & 1 & 1 & 1 & 0\\
1 & 2 & 4 & 8 & 6\\
\end{bmatrix}

Untuk mendapatkan solusinya, digunakan Gaussian Elimination
\begin{bmatrix}
1 & -1 & 1 & -1 & 0\\
0 & 1 & -1 & 1 & 0\\
0 & 2 & 0 & 2 & 0\\
0 & 3 & 3 & 9 & 6\\
\end{bmatrix} Baris ke-2, ke-3, dan ke-4 dikurangi baris pertama

\begin{bmatrix}
1 & -1 & 1 & -1 & 0\\
0 & 1 & -1 & 1 & 0\\
0 & 1 & 0 & 1 & 0\\
0 & 1 & 1 & 3 & 2\\
\end{bmatrix} Baris ke-3 dibagi dengan 2, sedangkan baris ke-4 dibagi dengan 3

\begin{bmatrix}
1 & -1 & 1 & -1 & 0\\
0 & 1 & -1 & 1 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 1 & 1 & 3 & 2\\
\end{bmatrix} Baris ke-3 dikurangi baris ke-2

\begin{bmatrix}
1 & -1 & 1 & -1 & 0\\
0 & 1 & -1 & 1 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 2 & 2 & 2\\
\end{bmatrix} Baris ke-4 dikurangi baris ke-2

\begin{bmatrix}
1 & -1 & 1 & -1 & 0\\
0 & 1 & -1 & 1 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 1 & 1\\
\end{bmatrix} Baris ke-4 dibagi dengan 2

\begin{bmatrix}
1 & -1 & 1 & -1 & 0\\
0 & 1 & -1 & 1 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 1\\
\end{bmatrix} Baris ke-4 dikurangi baris ke-3
Didapatkan persamaan linier dari persamaan matrix di atas
\begin{matrix}
a_0&+&a_1&+&a_2&+&a_3 &=&0\Longleftrightarrow a_0 = 0\\
& &a_1&-&a_2&+&a_3&=&0\Longleftrightarrow a_1 = -1\\
& & & &a_2& & &=&0\\
& & & & & &a_3&=&1\\
\end{matrix}
Jadi, interpolasinya adalah p(x) = x^3 - x\,'

Tidak ada komentar:

Posting Komentar