PENDEKATAN NEAR MINIMAKS SEBAGAI PENDEKATAN FUNGSI Lilik Prasetiyo Pratama Jurusan Matematika, FMIPA UNS
1. LATAR BELAKANG Tidak semua fungsi mudah dievaluasi, terlebih fungsi yang rumit. Pendekatan dengan polinomial merupakan pendekatan sederhana fungsi. Pendekatan minimaks adalah pendekatan polinomial terbaik sebab pendekatan tersebut dapat meminimumkan eror maksimum polinomial pendekatan fungsi pada seluruh interval dan eror pendekatan bersifat equal ripple. Namun, pendekatan minimaks sulit dikonstruksi sehingga perlu pendekatan lain dengan eror yang bersifat near equal ripple. Pendekatan yang mendekati pendekatan minimaks tersebut dikenal sebagai pendekatan near minimaks.
2. PERUMUSAN MASALAH Dari latar belakang dapat dirumuskan tiga masalah, yaitu (1) bagaimana menurunkan ulang algoritma near minimaks, (2) bagaimana menerapkan algoritma pendekatan near minimaks pada suatu kasus, dan (3) bagaimana menganalisis eror hasil penerapan kasus tersebut.
3. TUJUAN Tujuan penulisan artikel ini adalah (1) dapat menurunkan ulang algoritma near minimaks, (2) dapat menerapkan algoritma pendekatan near minimaks pada suatu kasus, dan (3) dapat menganalisis eror hasil penerapan kasus.
Pendekatan Near Minimaks Sebagai Pendekatan Fungsi
4. PEMBAHASAN 4.1. Pendekatan Minimaks. Menurut May [3], jika φ(x; a0 , a1 , . . . , an ) pendekatan f (x) pada interval [a, b], maka maksimum eror pendekatan sebesar E = maks |f (x) − φ(x; a0 , a1 , . . . , an )|. a≤x≤b
Pendekatan minimaks (pendekatan terbaik) f (x) dihasilkan dari pemilihan parameter a0 , a1 , . . . , an sedemikian sehingga nilai E yang dihasilkan minimum. Jika maks |f (x) − p∗n (x)| ≤ maks |f (x) − pn (x)|
a≤x≤b
a≤x≤b
untuk semua polinomial pn (x) berderajat n, maka polinomial p∗n (x) merupakan pendekatan minimaks dari f (x). Eror pendekatan minimaks memiliki sifat equal ripple yaitu f (x) − p∗n (x) memiliki n + 2 nilai ekstrim dengan tanda yang saling berganti dan n + 1 akar (May [3]). 4.2. Polinomial Chebyshev. Akan ditunjukkan polinomial Chebyshev memiliki sifat equal ripple pada interval [-1,1]. Untuk x ∈ [−1, 1], polinomial Chebyshev didefinisikan dengan Tn (x) = cos(n arccos x), untuk setiap n ≥ 0,
(4.1)
sehingga T0 (x) = 1 dan T1 (x) = x. Untuk n > 1, jika diambil subsitusi θ = arccos x, persamaan (4.1) menjadi Tn (θ(x)) ≡ Tn (θ) = cos(nθ), dengan θ ∈ [0, π]. Dengan hubungan rekursi diperoleh 2xTn (x) − Tn−1 (x) = cos nθ cos θ − sin nθ sin θ = cos(n + 1)θ = Tn+1 (x). Karena Tn (x) = cos nθ, maka polinomial Chebyshev memiliki sifat equal ripple pada interval [-1,1]. Dengan demikian, dikonstruksi pendekatan dengan eror yang bersifat equal ripple dari polinomial Chebyshev. 4.3. Konstruksi Pendekatan Near Minimaks. Polinomial Chebyshev Tn (x) berderajat n ≥ 1 memiliki n akar sederhana pada 2k + 1 x ¯k = cos π, k = 1, 2, . . . , n. 2n Lebih lanjut, Tn (x) memiliki nilai ekstrim, x ¯0 , pada kπ x ¯0k = cos , dengan Tn (¯ x0k ) = (−1)k , k = 0, 1, 2, . . . , n. n
Pendekatan Near Minimaks Sebagai Pendekatan Fungsi
Polinomial monik (polinomial dengan koefisien pangkat tertinggi sama dengan satu) Chebyshev ∼
T n (x) diturunkan dari polinomial Chebyshev Tn (x) dengan dikalikan ∼
∼
T 0 (x) = 1 dan T n (x) = ∼
1 2n−1
dan diperoleh
1 Tn (x), n ≥ 2. 2n−1 ∼
Karena T n (x) merupakan kelipatan Tn (x), akar-akar T n (x) juga terletak pada 2k + 1 x ¯k = cos π, k = 1, 2, . . . , n 2n ∼
dan nilai ekstrim T n (x), untuk n ≥ 1, terletak pada ∼ (−1)k kπ , dengan T n (¯ x0k ) = n−1 , k = 0, 1, 2, . . . , n. x ¯0k = cos n 2 ∼
Misal Πn menotasikan himpunan semua polinomial monik berderajat n. Burden dan Faires ∼
[2] menyatakan bahwa polinomial T n (x) memiliki sifat 1 2n−1
∼
∼
= maks |T n (x)| ≤ maks |Pn (x)|, untuk semua Pn (x) ∈ Πn . x∈[−1,1]
(4.2)
x∈[−1,1]
Jika x0 , . . . , xn ∈ [−1, 1] dan f fungsi pada interval [-1,1], maka untuk setiap x ∈ [−1, 1] terdapat ξx ∈ [−1, 1] sedemikian sehingga f (x) − P (x) =
f n+1 (ξx ) (x − x0 )(x − x1 ) . . . (x − xn ), (n + 1)!
dengan P (x) polinomial interpolasi. Karena ξx tertentu, maka untuk meminimumkan eror di sekitar titik-titik x0 , . . . , xn , akan dicari x0 , . . . , xn yang meminimumkan |(x − x0 )(x − x1 ) . . . (x − xn )| pada interval [-1,1]. Karena (x − x0 )(x − x1 ) . . . (x − xn ) polinomial monik berderajat n + 1, dari (4.2) minimum diperoleh jika ∼
(x − x0 )(x − x1 ) . . . (x − xn ) = T n (x). Nilai maksimum |(x − x0 )(x − x1 ) . . . (x − xn )| akan minimum jika xk merupakan n + 1 akar ∼
pertama T n (x) atau dengan kata lain, xk = x ¯k = cos ∼
Karena maks |T n (x)| = x∈[−1,1]
1 2n ,
2k + 1 π, k = 0, 1, n. 2n + 2
maka
1 = maks |(x − x ¯0 )(x − x ¯1 ) . . . (x − x ¯n )| ≤ maks |(x − x0 )(x − x1 ) . . . (x − xn )|, 2n x∈[−1,1] x∈[−1,1] untuk sembarang x0 , x1 , . . . , xn pada interval [-1,1]. Akibatnya P (x) (polinomial interpolasi berderajat sekurang-kurangnya n dengan titik-titik interpolasi pada akar-akar Tn+1 (x)) merupakan pendekatan near minimaks (Burden dan Faires [2]).
Pendekatan Near Minimaks Sebagai Pendekatan Fungsi
Untuk titik-titik pada interval [a, b] digunakan transformasi 1 ((b − a)¯ xk + a + b), k = 0, 1, . . . , n 2
∼
xk =
(4.3)
∼
yang mentransformasikan x ¯k pada interval [-1,1] ke xk pada interval [a, b] yang bersesuaian. Titik-titik (4.3) disebut titik Chebyshev. Jadi, untuk menurunkan pendekatan minimaks (pendekatan near minimaks), dicari polinomial interpolasi pada titik-titik Chebyshev. 5. PENERAPAN KASUS Diberikan dua kasus pendekatan near minimaks. Kasus pertama adalah pendekatan near minimaks pada fungsi eksponensial dan kasus kedua adalah pendekatan near minimaks pada fungsi invers tangen. Proses perhitungan menggunakan software Mathematica 7.0
Kasus 5.1. Kasus diambil dari Burden dan Faires [2] halaman 517. Akan dicari pendekatan near minimaks fungsi f (x) = e−x , x ∈ [−1, 1] berderajat dua, tiga, dan empat. Berdasarkan soal diketahui a = −1, b = 1, dan n = 2, 3, dan 4. Untuk pendekatan berderajat dua, fungsi f (x) = e−x diinterpolasi pada titik-titik 2k + 1 ∼ π , k = 0, 1, 2. xk = cos 6 Tabel selisih terbagi Newton untuk titik-titik Chebyshev tersebut terlihat pada Tabel 1. Tabel 1. Tiga titik Chebyshev, fungsi e−x pada titik-titik Chebyshev, dan formula selisih terbagi Newton. ∼
∼
xk
f (xk )
0.866025
0.42062
∼
Df [xk ]
∼
D2 f [xk ]
-0.66901 0
1
0.532042 -1.59053
-0.866025
2.37744
Jadi, pendekatan f (x) = e−x berderajat dua adalah p2 (x) = 0.42062 + (x − 0.866025) (−0.66901 + (x) (0.532042)) . Untuk pendekatan berderajat tiga, fungsi f (x) = e−x diinterpolasi pada titik-titik 2k + 1 ∼ xk = cos π , k = 0, 1, 2, 3. 8 Tabel selisih terbagi Newton untuk titik-titik Chebyshev tersebut terlihat pada Tabel 2.
(5.1)
Pendekatan Near Minimaks Sebagai Pendekatan Fungsi
Tabel 2. Empat titik Chebyshev, fungsi e−x pada titik-titik Chebyshev, dan formula selisih terbagi Newton. ∼
∼ xk
f (xk )
0.92388
0.396976
∼
∼
∼
D2 f [xk ]
Df [xk ]
D3 f [xk ]
-0.526709 0.382683
0.682029
0.381059 -1.02459
-0.382683
1.46621
-0.175176 0.704742
-1.94538 -0.92388
2.51904
Jadi, pendekatan f (x) = e−x berderajat tiga adalah p3 (x) =0.396976 + (x − 0.92388)(−0.526709 + (x − 0.382683) (0.381059 + (x + 0.382683)(−0.175176)))
(5.2)
Dengan cara yang sama diperoleh pendekatan f (x) = e−x berderajat empat, yaitu p4 (x) =0.386333 + (x − 0.951057)(−0.465833 + (x − 0.587785)(0.305239 + (x)(−0.136026 + (x + 0.587785)(0.0434341))))
(5.3)
Akan dibandingkan eror masing-masing pendekatan. Eror pendekatan berderajat dua (5.1) berupa garis putus-putus, berderajat tiga (5.2) berupa garis tebal, dan berderajat empat (5.3) berupa garis tipis. Eror
Eror 0.006
0.045
0.001
0.01 -1
-0.75
-0.5
x -0.01
0.25
0.5
1
-1
-0.75
-0.5
x -0.001
0.25
0.5
1
-0.004 -0.045
-0.006
Gambar 1. Eror pendekatan berderajat dua dan berderajat tiga dari f (x) = e−x (kiri) serta berderajat tiga dan berderajat empat dari f (x) = e−x (kanan).
Dari Gambar 1 terlihat bahwa eror pendekatan berderajat dua, tiga, dan empat bersifat ripple dan harga mutlak ekstrimnya berkisar di 0.045 (berderajat dua), 0.006 (berderajat tiga) dan 0.001 (berderajat empat). Karena harga mutlak ekstrimnya berkisar pada suatu nilai
Pendekatan Near Minimaks Sebagai Pendekatan Fungsi
tertentu, maka eror pendekatan berderajat dua, tiga, dan empat bersifat near equal ripple. Karena eror pendekatan bersifat near equal ripple maka pendekatan berderajat dua, tiga, dan empat adalah pendekatan near minimaks. Pendekatan dengan polinomial berderajat empat adalah pendekatan terbaik sebab memiliki eror maksimum yang lebih kecil daripada polinomial berderajat dua dan tiga. Kasus 5.2. Kasus diambil dari Atkinson [1] halaman 244. Akan dicari pendekatan near minimaks fungsi f (x) = tan−1 x, x ∈ [0, 1] berderajat dua, tiga, empat, dan lima. Berdasarkan soal diketahui a = 0, b = 1, dan n = 2, 3, 4 dan 5. Untuk pendekatan berderajat dua, fungsi f (x) = tan−1 x diinterpolasi pada titik-titik 1 xj = 2
∼
2j + 1 cos π + 1 , j = 0, 1, 2. 6
Tabel selisih terbagi Newton untuk titik-titik Chebyshev tersebut terlihat pada Tabel 3 Tabel 3. Tiga titik Chebyshev, fungsi tan−1 x pada titik-titik Chebyshev, dan formula selisih terbagi Newton. ∼
∼
xj
f (xj )
0.933013
0.750758
∼
Df [xj ]
∼
D2 f [xj ]
0.663052 0.5
0.463648
-0.2924 0.916279
0.0669873
0.0668874
Jadi, pendekatan f (x) = tan−1 x berderajat dua adalah p2 (x) = 0.750758 + (x − 0.933013)(0.663052 + (x − 0.5)(−0.2924)).
(5.4)
Dengan cara yang sama diperoleh pendekatan f (x) = tan−1 x berderajat tiga, empat, dan lima, yaitu p3 (x) =0.766001 + (x − 0.96194)(0.595385 + (x − 0.691342) (−0.310666 + (x − 0.308658)(−0.0588263))),
(5.5)
p4 (x) =0.773011 + (x − 0.975528)(0.561594 + (x − 0.793893)(−0.302744 + (x − 0.5)(0.00549626 + (x − 0.206107)(0.1426)))),
(5.6)
Pendekatan Near Minimaks Sebagai Pendekatan Fungsi
dan p5 (x) =0.776807 + (x − 0.982963)(0.542876 + (x − 0.853553)(−0.291586 + (x − 0.62941) (0.0421715 + (x − 0.37059)(0.113265 + (x − 0.146447)(−0.0558006))))).
(5.7)
Akan dibandingkan eror masing-masing pendejatan. Eror pendekatan near minimaks berderajat dua (5.4) berupa garis putus-putus, berderajat tiga (5.5) berupa garis tebal, berderajat empat (5.6) berupa garis tipis, dan berderajat lima (5.7) berupa garis putus-putus tebal. Eror
Eror 0.003
0.000085
0.001
0.000025 Π
Π
Π
12
6
4
x 1
-0.000025
Π
Π
Π
12
6
4
x 1
-0.001
-0.000085 -0.003
Gambar 2. Eror pendekatan berderajat dua dan berderajat tiga dari f (x) = tan−1 x (kiri) serta berderajat empat dan lima dari f (x) = tan−1 x (kanan).
Dari Gambar 2 dan Gambar 3, eror pendekatan berderajat dua, tiga, empat, dan lima bersifat ripple. Harga mutlak ekstrim pada eror pendekatan berderajat dua tidak berkisar pada nilai tertentu yang hampir sama dan eror pada x = 0 cukup besar sehingga eror pendekatan berderajat dua tidak near equal ripple. Dengan demikian pendekatan berderajat dua bukan pendekatan near minimaks. Harga mutlak ekstrim pendekatan berderajat tiga, empat, dan lima berkisar di nilai 0.00005. Karena harga mutlak ekstrimnya berkisar pada suatu nilai tertentu, maka eror pendekatan berderajat tiga, empat, dan lima bersifat near equal ripple. Dengan demikian pendekatan berderajat tiga, empat, dan lima merupakan pendekatan near minimaks. Pendekatan dengan polinomial berderajat lima adalah pendekatan terbaik sebab memiliki eror maksimum yang lebih kecil daripada polinomial berderajat empat. 6. KESIMPULAN Dari pembahasan dan penerapan kasus, diperoleh kesimpulan (1) pendekatan near minimaks fungsi diperoleh dari polinomial interpolasi pada titik-titik Chebyshev, (2) eror pendekatan near minimaks bersifat near equal ripple,
Pendekatan Near Minimaks Sebagai Pendekatan Fungsi
(3) dari Kasus 1 pendekatan near minimaks adalah pendekatan berderajat empat bila dibandingkan dengan derajat dua dan tiga dan dari Kasus 2 pendekatan near minimaks adalah pendekatan berderajat lima bila dibandingkan dengan derajat dua, tiga, dan empat. Pustaka [1] Atkinson, K. E., An Introduction to Numerical Analysis, John Wiley and Sons, New York, 1987. [2] Burden, R. L. and Faires, J. D., Numerical Analysis, Brooks/Cole, California, 2001. [3] May, R. L., Approximation and Quadrature, Royal Melbourne Institute of Technology Ltd, Melbourne, 1991.
Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, UNS, Jl. Ir. Sutami 36A, Kentingan, Surakarta, 57126
