1.1 Definisi dan Teorema Dalam Kalkulus Representasi bilangan dalam komputer Algoritma Software Komputer

Daftar Isi Contents

ii

Daftar Tabel

iii

Daftar Gambar

iv

1 Konsep Dasar

1

1.1 Definisi dan Teorema Dalam Kalkulus

. . . . . . . . . . . . . . . .

1

1.2 Representasi bilangan dalam komputer . . . . . . . . . . . . . . . .

4

1.3 Algoritma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

1.4 Software Komputer . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2 Solusi Persamaan Fungsi Polinomial

10

2.1 Metoda Biseksi . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.2 Metoda Newton-Raphson . . . . . . . . . . . . . . . . . . . . . . . .

12

2.3 Metoda Posisi Palsu . . . . . . . . . . . . . . . . . . . . . . . . . .

14

3 Interpolasi dan Aproksimasi Polinomial i

18

DAFTAR ISI

ii

3.1 Norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.2 Konsep Masalah dalam Aproksimasi . . . . . . . . . . . . . . . . .

20

3.3 Solusi Iteratif Untuk Sistem Linier Ax = b . . . . . . . . . . . . . .

21

3.4 Fungsi-Fungsi Aproksimasi . . . . . . . . . . . . . . . . . . . . . . .

24

3.4.1

Interpolasi dan Polinomial Lagrange . . . . . . . . . . . . .

24

3.4.2

Difrensi Terpisah . . . . . . . . . . . . . . . . . . . . . . . .

25

3.4.3

Interpolasi Splin Kubik . . . . . . . . . . . . . . . . . . . . .

33

3.5 Solusi Iteratif Integral Terbatas . . . . . . . . . . . . . . . . . . . .

40

4 Metoda Numeris untuk Sistem Nonlinier

52

4.1 Metoda Titik Tetap . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

4.2 Metoda Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

5 Metoda Numeris Untuk Masalah Nilai Awal

64

5.1 Teori Dasar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

66

5.2 Beberapa Metoda Numeris . . . . . . . . . . . . . . . . . . . . . . .

68

5.2.1

Metoda Euler . . . . . . . . . . . . . . . . . . . . . . . . . .

69

5.2.2

Metoda Runge-Kutta . . . . . . . . . . . . . . . . . . . . . .

74

5.2.3

Metoda Multistep Linier (MML) . . . . . . . . . . . . . . .

79

5.3 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

84

Daftar Tabel 3.1 Difrensi terpisah langkah maju. . . . . . . . . . . . . . . . . . . . .

28

3.2 Difrensi terpisah langkah mundur. . . . . . . . . . . . . . . . . . . .

31

3.3 Data f (x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.1 Data hasil eksekusi program iterasi Newton . . . . . . . . . . . . .

61

5.1 Data hasil eksekusi program metoda Runge-Kutta . . . . . . . . . .

79

iii

Daftar Gambar 1.1 Approksimasi oleh p1 (x) . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2 Approksimasi oleh p2 (x) . . . . . . . . . . . . . . . . . . . . . . . .

3

3.1 Diagram aproksimasi . . . . . . . . . . . . . . . . . . . . . . . . . .

20

3.2 Interpolasi polinomial Lagrange p2 (x) terhadap f (x) . . . . . . . . .

26

3.3 Approksimasi NFDD p4 (x) . . . . . . . . . . . . . . . . . . . . . . .

33

3.4 Approksimasi spline kubik S3 (x) . . . . . . . . . . . . . . . . . . . .

41

3.5 Aturan Trapesium. . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

3.6 Aturan Simpson. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

3.7 Konstruksi automobile . . . . . . . . . . . . . . . . . . . . . . . . .

50

5.1 Diagram kekonvekan untuk D ∈ R2 . . . . . . . . . . . . . . . . . .

67

5.2 Metoda Euler dalam grafik . . . . . . . . . . . . . . . . . . . . . . .

74

5.3 Metoda Runge-Kutta order 2 . . . . . . . . . . . . . . . . . . . . .

80

iv

BAB 1 Konsep Dasar 1.1

Definisi dan Teorema Dalam Kalkulus

Pengembangan metoda numerik tidak terlepas dari pengembangan beberapa definisi dan teorema dalam mata kuliah kalkulus yang berkenaan dengan fungsi polinomial f (x). Oleh karena itu dibawah ini akan diingatkan kembali beberapa definisi dan teorema tersebut. Teorema [a, b], dan sebarang ξ [a, b] akan

1.1.1 (Nilai Tengah) Jika f (x) adalah fungsi kontinyu pada interval didefinisikan m = Infa≤x≤b f (x) dan M = Supa≤x≤b f (x) maka ada pada interval [m, M ], sehingga paling sedikit satu titik ζ di dalam interval memenuhi f (ξ) = ζ

Teorema 1.1.2 (Nilai Rata-Rata) Jika f (x) adalah fungsi kontinyu pada interval [a, b] dan terdefrensialkan pada interval (a, b), maka paling sedikit ada satu titik ξ dalam (a, b) yang memenuhi f (b) − f (a) = f 0 (ξ)(b − a) Teorema 1.1.3 (Integral Nilai Rata-Rata) Jika w(x) adalah fungsi tak negatif 1

BAB 1. KONSEP DASAR

2

dan terintegralkan pada interval [a, b], dan misal f (x) kontinyu pada [a, b] maka Z b Z b w(x)f (x)dx = f (ξ) w(x)dx a

a

untuk semua ξ ∈ [a, b] Teorema 1.1.4 (Teorema Taylor) Jika f (x) mempunyai n+1 turunan kontinyu pada interval [a, b] untuk beberapa n ≥ 0 dan bila x, x0 ∈ [a, b] maka f (x) ≈ pn (x) + Rn+1 (x) (x − x0 ) 0 (x − x0 )n (n) pn (x) = f (x0 ) + f (x0 ) + · · · + f (x0 ) 1! n! Z x 1 Rn+1 (x) = (x − t)n f (n+1) (t)dt n! x0 (x − x0 )n+1 (n+1) = f (ξ) (n + 1)!

(1.1) (1.2) (1.3) (1.4)

untuk ξ antara x0 dan x

4 3 2

p1(x)

1

f(x)

0 −1 −2 −3 −4 −5 0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Gambar 1.1: Approksimasi oleh p1 (x) Deret Taylor ini nantinya akan menjadi konsep dasar pengembangan metoda numeris. Beberapa metoda aproksimasi adalah merupakan hasil ekspansi dan pe-

BAB 1. KONSEP DASAR

3

menggalan dari deret ini. Sehingga deret ini sendiri juga merupakan model aproksimasi terhadap suatu fungsi f (x) sebagaimana digambarkan dalam contoh berikut ini. Contoh 1.1.1 Diketahui f (x) = ln x, tentukan fungsi aproksimasi linear p1 (x) dan kuadratik p2 (x) pada x0 = 1, dan gunakan p1 (x), p2 (x) untuk menghitung ln 1.5.

2

f(x)

1

0 p2(x) −1

−2

−3

−4

−5 0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Gambar 1.2: Approksimasi oleh p2 (x) Penyelesaian 1.1.1 f (x) = ln x maka f (x0 ) = ln 1 = 0, f 0 (x) = 1. Dengan menggunakan teori Taylor kita dapatkan

1 x

maka f 0 (x0 ) =

p1 (x) = ln 1 + (x − 1).1 = x − 1 1 1 p2 (x) = ln 1 + (x − 1).1 + (x − 1)2 . − 1 = (x − 1) − (x − 1)2 2 2 Dengan demikian ln 1.5 dapat ditentukan dengan cara ln 1.5 = p1 (1.5) = 1.5 − 1 = 0.5 1 ln 1.5 = p2 (1.5) = (1.5 − 1) − (1.5 − 1)2 = 0.375 2 Secara grafis aproksimasi dari p1 (x) dan p2 (x) terhadap f (x) = ln x dapat ditunjukkan dalam Gambar 1.2 dan 1.2.

BAB 1. KONSEP DASAR

1.2

4

Representasi bilangan dalam komputer

Komputer dapat melakukan operasi pada bilangan dengan mudah, misal 2 + 2 = 4, 6 : 2 = 3, dengan pasti komputer dapat menjawab dengan benar. Namun √ demikian bila komputer mengoperasikan ( 3)2 maka operasi ini tidak dilakukan ¡ 1 ¢2 dengan cara 3 2 = 3 akan tetapi dengan cara melakukan pengakaran bilangan √ tiga dua kali kemudian keduanya dikalikan. Dapat dipahami bahwa untuk 3 = 1.7320508 . . . mempunyai jumlah desimal (digit) yang tidak terbatas sehingga nilai tersebut hanya merupakan nilai pendekatan. Dalam hal melakukan pendekatan ini komputer melakukan pemotongan (Chopping) atau pembulatan (Rounding) dan selanjutnya dimungkinkan muncul beberapa kesalahan yang secara umum dikenal dengan nama kesalahan pembulatan (Rounding error) dan kesalahan pemotongan (Chopping error). Selanjutnya untuk merepresentasikan bilangan real, komputer pada umumnya menggunakan sistem ”floating-point” dengan basis bilangan 2 (biner), 8(octal) dan 16(hexadecimal). Sedangkan format penyimpanannya dalam memori komputer digambarkan sebagai berikut : x = σ · (·a1 a2 . . . at )β · β e ,

(1.5)

dimana • a1 6= 0, dan 0 ≤ ai ≤ β − 1, a1 kemudian disebut titik radik. • σ adalah tanda dengan nilai σ = +1 atau −1, dan β adalah basis. • e adalah bilangan bulat dengan L ≤ e ≤ U , dimana L, U masing-masing nilai terkecil dan terbesar. • (·a1 a2 . . . at )β adalah mantisa. Bila bilangan real x dinyatakan dalam x = σ · (·a1 a2 . . . at at+1 . . . )β · β e ,

(1.6)

BAB 1. KONSEP DASAR

5

maka representasi pemotongan desimal dapat dinyatakan dalam bentuk floating point f l(x) sebagai berikut f l(x) = σ · (·a1 a2 . . . at )β · β e

(1.7)

Sedangkan representasi pembulatan dapat ditampilkan sebagai ( σ · (·a1 a2 . . . at )β · β e ; 0 ≤ at+1 < β2 f l(x) = σ · [(·a1 a2 . . . at )β + (·0 . . . 01)β ] · β e ; β2 ≤ at+1 < β Dalam hal ini f l(x) 6= x, oleh karena itu kesalahan dapat dimunculkan dalam bentuk ² = x − f l(x), dan kesalahan relatifnya x − f l(x) = ²R x dengan demikian f l(x) = (1 − ²R )x

(1.8)

Jika simbol-simbol operasi mesin komputer dinyatakan dalam ⊕, ª, ⊗ dan ® maka operasi jumlah, kurang, kali dan bagi untuk x dan y dalam komputer dinyatakan sebagai berikut: x ⊕ y = f l(f l(x) + f l(y)) x ª y = f l(f l(x) − f l(y)) x ⊗ y = f l(f l(x) × f l(y)) x ® y = f l(f l(x) ÷ f l(y)). Dengan demikian komputer melakukan floating point terhadap masing-masing komponen bilangan sebelum dan sesudah melakukan operasi. Hal ini bertujuan untuk meminimalkan kesalahan yang dihasilkannya. Secara umum formulasi nilai kesalahannya dari perhitungan aproksimasi terhadap xA (niali eksak) oleh xT (nilai aproksimasi), dapat dinyatakan sebagai E(xA ) = xT − xA

(1.9)

BAB 1. KONSEP DASAR

6

dan kesalahan relatifnya adalah Rel(xA ) =

1.3

xT − xA xT

(1.10)

Algoritma

Teorema 1.3.1 (Algoritma) Algoritma adalah suatu prosedur yang menggambarkan urut-urutan rapi dan logis dengan tujuan memudahkan pengimplementasian suatu masalah. Selanjutnya, sebagai prosedur logis algoritma harus dapat dengan mudah diinterpretasikan dalam fungsi-fungsi khusus pada komputer prog-ramming. Dua simbol yang digunakan dalam algoritma adalah Period (·) dan menunjukan akhir prosedur, dan titik koma (;) memisahkan tugas dalam beberapa langkah. Teknik loop (pengulangan) dalam algoritma dapat dinyatakan dengan ’kontrol penyanggah’ F or i = 1, 2, . . . , n Set xi = ai + i · h ataupun ’kontrol bersyarat’ W hile i < N do Steps 3 − 6 if . . . then,

if . . . then . . . else

Misal suatu algoritma untuk menghitung N X

xi = x1 + x2 + · · · + xN ,

i=1

dapat diuraikan adalah sebagai berikut INPUT N, x1 , x2 , . . . , xn . P OUTPUT SUM= N i=1 xi . Step 1 Set SUM=0.

BAB 1. KONSEP DASAR

7

Step 2

For i = 1, 2, 3, . . . , N do set SU M = SU M + xi . Step 3 OUTPUT (SUM); STOP.

1.4

Software Komputer

Banyak software programming, baik compiler ataupun semi compiler, yang dapat digunakan untuk menyelesaikan masalah numerik, diantaranya adalah 1. Fortran (LINPACK, EISPACK, LAPACK, BLAS, NAG) 2. Matlab yang library-nya berdasarkan EISPACK dan LINPACK + beberapa Matlab Toolbox 3. Maple, Pascal, Fortran , Turbo C+ dan Turbo Basic, dll.

BAB 1. KONSEP DASAR

8

Latihan Tutorial 1 1. Fungsi aproksimasi sebagian besar didasari oleh pengembangan deret Taylor sebutkan teorema Taylor ini. Bila diketahui f (x) = sin x terapkan deret Taylor ini untuk menentukan fungsi aproksimasi kuadratik terhadap f pada x = 0. Kemudian tentukan nilai aproksimasi dari sin 5. Disadari bahwa dalam menghitung nilai sin 5 anda akan mendapatkan kesalahan numeris sebutkan penyebab kesalahan itu. Selanjutnya untuk mengantisipasi kesalahan ini diperlukan format penyimpanan yang baik dalam memori komputer, tentukan format tersebut. Dan bila diberikan nilai eksak xA dan nilai aproksimasi xT , formulasikan kesalahan E(xA ) serta relatif kesalahan Rel(xA ). 2. Tentukan konversi dari masing-masing bilangan dibawah ini kedalam bentuk desimal biasa. (a) (1010101.101)2 (b) (2A3.F F )16 (c) (.101010101 . . . )2 3. Tentukan fungsi aproksimasi p1 (x), p2 (x) dan p3 (x) dari fungsi dibawah ini pada x0 = 1. (a) f (x) = ln x + x (b) g(x) = x2 + 4x + 2 dan tentukan nilai dari ln 3, melalui fungsi aproksimasi f (x). 4. Gunakan deret Taylor untuk menemukan rumusan dari ex , sin x, cos x, e−x 1 dan 1−x pada x0 = 0

2

5. Lakukan pembulatan dan pemotongan terhadap bilangan dibawah ini sampai empat desimal dibelakang koma.

BAB 1. KONSEP DASAR

9

(a) 0.35745397 (b) 4.8975978 (c) −1.098904045 (d) 0.09874329873 dan tentukan nilai kesalahan dan kesalahan relatifnya. 6. Gunakan metoda biseksi untuk menyelesaikan persmaan dibawah ini pada interval yang diberikan (a)

√

x − cos x = 0

pada interval [0, 1]

(b) x3 − 7x2 + 14x − 6 = 0

pada interval [1, 1.32]

(c) 2x cos x − (x + 1)2 = 0

pada interval [−3, −2]

dengan toleransi ² = 1e − 2

BAB 2 Solusi Persamaan Fungsi Polinomial Definition 2.0.1 (Metoda numeris) Metoda numeris adalah suatu model pendekatan dengan menggunakan teknik-teknik kalkulasi berulang (teknik iterasi) untuk mecari penyelesaian hampiran suatu masalah tertentu. Selanjutnya teknik-teknik yang digunakan itu mempunyai potensi membuat suatu nilai kesalahan yang dievaluasi secara bertahap untuk mendapatkan nilai kesalahan yang sangat kecil. Untuk mengawali penjelasan teknik-teknik aproksimasi ini, dalam bab ini akan dimulai dengan pembahasan aproksimasi terhadap suatu titik melalui penyelesaian persamaan fungsi polinomial. f := a1 xn + a2 xn−1 + a3 xn−2 + · · · + an = 0

2.1

Metoda Biseksi

Definition 2.1.1 (Prosedur Biseksi) Misal f adalah fungsi kontinyu terdefi-nisi pada interval [a, b], dimana f (a) berbeda tanda dengan f (b). Dengan teori ”nilai 10

BAB 2. SOLUSI PERSAMAAN FUNGSI POLINOMIAL

11

tengah” maka ada p ∈ (a, b) dengan f (p) = 0 dengan asumsi akar dalam interval (a, b) adalah tungal. Selanjutnya untuk melakukan perhitungan yang akurat kita set a1 = a dan b1 = b dan tentukan p1 lewat 1 p1 = (a1 + b1 ) 2 Jika f (p1 ) = 0, maka p = p1 . Jika tidak, f (p1 ) akan mempunyai tanda yang sama dengan f (a1 ) atau f (b1 ). Jika f (p1 ) dan f (a1 ) mempunyai tanda yang sama maka p ∈ (p1 , b1 ) jika tidak maka p ∈ (a1 , p1 ). Selanjutnya set a2 dan b2 yang baru dan tentukan p2 melalui perhitungan yang sama dengan p1 , dan lakukan pengulangan sampai tingkat akurasi tertentu. Untuk menghentikan pengulangan penghitungan dalam mencari solusi yang akurat harus dikonfirmasikan dengan nilai kesalahan ² (selanjuntya kita sebut toleransi) dimana toleransi dalam hal ini dapat dipilih |pn − pn−1 | < e |pn − pn−1 | < e, |pn | |f (pn )| < e

pn 6= 0

Algoritma Metoda Biseksi INPUT batas interval a, b, ² (Toleransi), Jumlah iterasi maximum (N) OUTPUT nilai aproksimasi p Step 1 Set i=1; F A = f (a) Step 2 While i ≤ N do Steps 3-6 Step 3 Set p = a + (b − a)/2; F P = f (p) Step 4 IF F P = 0, atau (b − a)/2 < ² OUTPUT(p) STOP


12

Step 5 Set i = i + 1. Step 6 If F A · F P > 0 then a = p, F A = F P ; else Set b = p. Step 7 OUTPUT (Metoda gagal setelah N iterasi) STOP.

2.2

Metoda Newton-Raphson

Jika f ∈ C 2 [a, b], dan x¯ ∈ [a, b] adalah nilai aproksimasi terhadap p sehingga f 0 (¯ x) 6= 0 dan |¯ x − p| sangat kecil, maka polynomial Taylor dapat dikembangkan untuk x¯ sebagai: (x − x¯)2 00 f (ξ(x)) + . . . f (x) = f (¯ x) + (x − x¯)f (¯ x) + 2! (x − x¯)2 00 f (x) = f (¯ x) + (x − x¯)f 0 (¯ x) + f (ξ(x)); ξ(x) ∈ (x, x¯). 2 0

(2.1)

Jika f (p) = 0 maka untuk x = p persamaan (5.1) menjadi 0 = f (¯ x) + (p − x¯)f 0 (¯ x) +

(p − x¯)2 00 f (ξ(p)) 2

Telah diasumsikan |¯ x − p| sangat kecil, maka suku ketiga dapatlah diabaikan sehingga 0 = f (¯ x) + (p − x¯)f 0 (¯ x). Formulasikan untuk p didapat p ≈ x¯ −

f (¯ x) . 0 f (¯ x)

Dengan menggati x¯ = pn−1 maka formulasi Newton-Raphson dapat diturunkan untuk menggeneralisasi suatu deret {pn } melalui pn = pn−1 −

f (pn−1 ) , f 0 (pn−1 )

f or n ≥ 1.

(2.2)


13

Sama halnya dengan metoda biseksi, untuk menghentikan pengulangan penghitungan dalam mencari solusi yang akurat harus dikonfirmasikan dengan nilai kesalahan ² yang telah ditentukan sehingga |pn − pn−1 | < e |pn − pn−1 | < e |pn | |f (pn )| < e

pn 6= 0

Algoritma Metoda Newton-Raphson INPUT nilai awal p0 , ² (Toleransi), Jumlah iterasi maximum (N) OUTPUT nilai aproksimasi p Step 1 Set i=1; Step 2 While i ≤ N do Steps 3-6 Step 3 Set p = p0 − f (p0 )/f 0 (p0 ); Step 4 IF |p − p0 | < ² OUTPUT(p) STOP. Step 5 Set i = i + 1. Step 6 Set p0 = p (Perbaharui p0 ) Step 7 OUTPUT (Metoda gagal setelah N iterasi) STOP. Metoda Newton ini lebih baik dibandingkan metoda Biseksi, namun demikian proses menentukan f 0 (x) kadangkala merupakan proses yang lebih susah dibandingkan dengan operasi artmatikanya. Untuk menghindari hal tersebut dikembangkan metoda berikut. Ingat definisi turunan f 0 (pn−1 ) = lim

x→pn−1

f (x) − f (pn−1 ) . x − pn−1

Misal x = pn−2 maka f 0 (pn−1 ) ≈

f (pn−2 ) − f (pn−1 ) f (pn−1 ) − f (pn−2 ) = . pn−2 − pn−1 pn−1 − pn−2


14

Substitusikan rumusan ini kedalam rumusan Newton diperoleh rumus: pn = pn−1 −

f (pn−1 )(pn−1 −pn−2 ) . f (pn−1 )−f (pn−2 )

(2.3)

Rumus ini kemudian disebut Metoda Secant Algoritma Metoda Secant INPUT nilai awal p0 , p1 , ² (Toleransi), Jumlah iterasi maximum (N) OUTPUT nilai aproksimasi p Step 1 Set i=2; q0 = f (p0 ). q1 = f (p1 ). Step 2 While i ≤ N do Steps 3-6 Step 3 Set p = p1 − q1 (p1 − p0 )/(q1 − q0 ). (hitung pi ) Step 4 IF |p − p1 | < ² OUTPUT(p) STOP. Step 5 Set i = i + 1. Step 6 Set p0 = p1 ; (Perbaharui p0 , q0 , p1 , q1 ) q0 = q1 ; p1 = p; q1 = f (p). Step 8 OUTPUT (Metoda gagal setelah N iterasi) STOP.

2.3

Metoda Posisi Palsu

Metoda ini menggabungkan ide metoda biseksi dan metoda secant. Dalam penyelesaian f (x) = 0, ditentukan suatu interval [p0 , p1 ] dimana f kontinyu pada interval ini, dan f (p0 ).f (p1 ) < 0 (berlawanan tanda). Prosedur selanjutnya dapat dilihat dalam algoritma berikut ini.

BAB 2. SOLUSI PERSAMAAN FUNGSI POLINOMIAL Algoritma Metoda Posisi Palsu INPUT nilai awal p0 , p1 , ² (Toleransi), Jumlah iterasi maximum (N) OUTPUT nilai aproksimasi p Step 1 Set i=2; q0 = f (p0 ). q1 = f (p1 ). Step 2 While i ≤ N do Steps 3-7 Step 3 Set p = p1 − q1 (p1 − p0 )/(q1 − q0 ). (hitung pi ) Step 4 IF |p − p1 | < ² OUTPUT(p) STOP. Step 5 Set i = i + 1. q = f (p) Step 6 IF q · q1 < 0 maka p0 = p1 , q0 = q1 Step 7 p1 = p1 , q1 = q Step 8 OUTPUT (Metoda gagal setelah N iterasi) STOP.

15


16

Latihan Tutorial 2 1. Gunakan algoritma biseksi untuk menentukan anilai aproksimasi pada √ dan 3 25

√

3

2. Suatu model yang dipakai untuk mengadakan aproksimasi terhadap suatu masalah adalah metoda numeris, sebutkan definisi formal metoda ini. Selanjutnya implikasi dari penggunaan metoda ini, komputer programming merupakan hal yang sangat penting. Untuk mempermudah menginterpretasikan suatu metoda menjadi suatu programming dibutuhkan algoritma, jelaskan apa yang disebut dengan algoritma. Salah satu algoritma yang digunakan untuk menginterpretasikan proses kalkulasi metoda numeris adalah metoda Newton-Raphson dengan rumusan pn = pn−1 −

f (pn−1 ) , f 0 (pn−1 )

untuk n ≥ 1

Metoda ini adalah metoda yang cukup terkenal, namun proses menentukan f 0 (x) kadangkala merupakan proses yang lebih sulit dibandingkan dengan operasi artmatiknya. Untuk menghindari hal tersebut ditawarkan metoda lain yaitu Metode Secant dengan rumus pn = pn−1 −

f (pn−1 )(pn−1 − pn−2 ) f (pn−1 ) − f (pn−2 )

untuk n ≥ 1.

Uraikan bagaimana metoda Newton dikembangkan sehingga menjadi metoda Secant ini. Kemudian bila kalkulasi iteratif diterapkan terhadap metoda ini, maka kalkulasi berulang (looping) akan terus dilakukan, jelaskan apa yang harus dilakukan untuk menghentikan kalkulasi tersebut. 3. f (x) = −x3 − cos x dan p0 = −1, gunakan metoda Newton Raphson untuk menentukan p2 4. Gunakan algoritma Newton untuk menentukan masing-masing soal dibawah ini dengan tingkat ketelitian (toleransi) e = 1e − 5

BAB 2. SOLUSI PERSAMAAN FUNGSI POLINOMIAL (a) ex + 2−x + 2 cos x − 6 = 0

untuk [1,2]

(b) ln(x − 1) + cos(x − 1) = 0

untuk [1.3,2]

(c) 2x cos 2x − (x − 2)2 = 0

untuk [2,3]

5. Ulangi soal nomor 8 diatas dan gunakan metoda secant 6. Ulangi soal nomor 8 diatas dan gunakan metoda posisi palsu

17

BAB 3 Interpolasi dan Aproksimasi Polinomial 3.1

Norm

Definisi 3.1.1 (Norm vektor) Norm vektor adalah pemetaan dari suatu fungsi terhadap setiap x ∈ IRN yang disimbolkan dengan ||x|| sedemikian hingga memenuhi sifat-sifat dibawah ini 1. ||x|| > 0 untuk x 6= 0, atau ||x|| = 0, untuk x = 0 2. ||αx|| = α||x|| 3. ||x + y|| ≤ ||x|| + ||y|| Contoh ||x||1 =

n X

|xi |

i=1

||x||2 =

µX n

|xi |

2

¶ 12

i=1

18

, (N orm Euclid)

BAB 3. INTERPOLASI DAN APROKSIMASI POLINOMIAL

||x||p =

µX n

|xi |p

19

¶ p1

i=1

||x||∞ = max |xi | 1≤i≤n

Definisi 3.1.2 (Norm matrik) Norm matrik adalah pemetaan dari suatu fungsi terhadap setiap x ∈ IRN ×N yang disimbolkan dengan ||A|| sedemikian hingga memenuhi sifat-sifat dibawah ini 1. ||A|| > 0 untuk A 6= 0, atau ||A|| = 0, untuk A = 0 2. ||αA|| = α||A|| 3. ||A + B|| ≤ ||A|| + ||B|| 4. ||AB|| ≤ ||A||||B|| Contoh

||A||F =

µX n X n

|ai j|

2

¶ 12

(N orm F robenius)

i=1 j=1

||A||v = max x6=0

||Ax|v ||x||v

Definisi 3.1.3 (Ruang Linier (RL)) Himpunan F dikatakan suatu ruang lini-er bila operasi penjumlahan dan perkalian terdefinisi didalamnya sehingga f · g ∈ F dan αf + βg ∈ F untuk ∀f, g ∈ F . Definisi 3.1.4 (Ruang Linier Norm (RLN)) F dikatakan ruang linier norm bila F adalah merupakan RL dan terdapat fungsi norm sehingga 1. ||f || > 0 untuk f 6= 0, atau ||f || = 0, untuk f = 0


20

2. ||αf || = α||f || 3. ||f + g|| ≤ ||f || + ||g|| untuk semua f, g ∈ F

3.2

Konsep Masalah dalam Aproksimasi

Misal f ∈ F dan f ∈ / P maka masalah dalam aproksimasi sebenarnya adalah ∗ menentukan p ∈ P sedemikian hingga ||f − p∗ || ≤ ||f − p||,

∀p ∈ P

kemudian p∗ dikatakan suatu aproksimasi terbaik terhadap f . Hal ini dapat digambarkan dalam diagram Venn berikut ini

f

p

F

p* P

Gambar 3.1: Diagram aproksimasi Beberapa fungsi aproksimasi p(x) untuk menghampiri fungsi f (x) dalam F = C[a, b] adalah sebagai berikut • P = {p : p(x) = a1 + a2 x + · · · + an xn−1 } • P = {p : p(x) =

Pn r=1

ar φr ,

ar ∈ <,

φr ∈ C[a, b]}

BAB 3. INTERPOLASI DAN APROKSIMASI POLINOMIAL • P = {p : p(x) = • P = {p : p(x) =

21

Pn a xr P0n r r } 0 br x

Pn

r=1

αr eλr x }.

Sedangkan dalam F = IRN adalah P = {p : p(x) =

Pn r=1

ar φr ,

ar ∈ IRN ,

φr IRN }

Teorema 3.2.1 (Teorema Weirstrass) Misal f terdefinisi dan terdifrensialkan pada interval [a, b] maka terdapat polinomial p(x) yang juga terdefinisi dan terdifrensialkan pada interval tersebut sedemikian hingga untuk nilai ² > 0 berlaku ||f (x) − p(x)|| < ², dan ∀x ∈ [a, b] Contoh F = C[a, b] dan f ∈ F , tunjukkan bahwa berikut dibawah ini merupakan RLN ¶ p1 µZ b p |f (x)| dx ; 1 ≤ p ≤ ∞ ||f ||p = a

||f ||∞ =

3.3

max |f (x)|

a≤x≤b

Solusi Iteratif Untuk Sistem Linier Ax = b

Suatu sistem linier dapat digambarkan sebagai a11 x1 + a12 x2 + · · · + a1n xn = b1 ; a21 x1 + a22 x2 + · · · + a2n xn = b2 ; a31 x1 + a32 x2 + · · · + a3n xn = b3 ; .. .

(3.1)

ann x1 + an2 x2 + · · · + ann xn = bn . Bila A merupakan matrik yang memuat koefisien variabel x1 , x2 , . . . , xn maka sistem linier itu dapat direduksi sistem Ax = b. Ada banyak metoda yang dapat


22

digunakan dalam menyelesaikan sistem ini. Diantaranya metoda langsung dan metoda iteratif. Namun demikian sesuai dengan perkembangan hardware dan software komputer solusi dengan metoda iteratif ini menjadi sangat populer dan terus dikembangkan. Metoda langsung memanfaakan konsep invers dalam matrik sehingga sistem Ax = b dapat diselesaikan melalui A−1 Ax = A−1 b x = A−1 b Teknik ini dipandang tidak efisien dan efektif, bahkan dimungkinkan suatu sistem tidak dapat diselesaikan karena proses kalkulasi panjang yang harus dikerjakan, yaitu berkenaan dengan penghitungan invers matrik A. Metoda iteratif menguraikan matrik A ini kedalam unsur matrik yang lebih sederhana dan mudah dihitung oleh komputer. Misal A=D-L-U, dimana D adalah matrik diagonal, L adalah negatif matrik segitiga bawah satu tahap dibawah diagonal utama dan U adalah negatif matrik segiatiga atas satu tahap diatas diagonal utama maka sistem diatas dapat dinyatakan sebagai berikut (D − L − U)x = b

(3.2)

Dx − (L + U)x = b Dx = (L + U)x + b x = D−1 (L + U)x + D−1 b x = D−1 (L + U)x + D−1 b. Misal J = D−1 (L + U) maka secara iteratif dapat diformulasikan sebagai xj+1 = Jxj + D−1 b.

(3.3)

Metoda ini disebut metoda Jacobi. Untuk meningkatkan kecepatan tingkat konvergensi dari metoda Jacobi, ditetapkanlah suatu koefisien redaman ω ∈ < sebagai faktor akselerasi terhadap metoda


23

ini sedemikian hingga dapat disajikan dengan bentuk dibawah ini £ ¤ xj+1 = (1 − ω)I + ωJ xj + ωD−1 b.

(3.4)

Metoda ini disebut metoda Jacobi teredam (damped Jacobi). Bentuk lain dari penyederhanaan (3.2) adalah sebagai berikut (D − L)x − Ux = b (D − L)x = Ux + b x = (D − L)−1 Ux + (D − L)−1 b Misal G = (D − L)−1 U maka secara iteratif dapat diformulasikan sebagai xj+1 = Gxj + (D − L)−1 b

(3.5)

Metoda ini disebut metoda Gauss-Seidel. Metoda-metoda iteratif ini dihitung berdasarkan suatu nilai awal yang dalam hal ini x0 , kemudian dengan rumusan itu dilanjutkan perhitungan untuk x1 , x2 , . . . sehingga diperoleh deret {xi }ni=0 . Deret ini akan konvergen terhadap nilai eksak x. Dapat dilihat disini bahwa proses penghitungan secara berulang terjadi sehingga dinamakan model solusi iteratif. Untuk menghentikan proses pengulangan ini, hasilnya harus dikonfirmasikan dengan toleransi ² yang dalam hal ini dapat ditentukan dari nilai dibawah ini ² = ||b − Ax||1 ² = ||b − Ax||2 ² = ||b − Ax||∞


3.4 3.4.1

24

Fungsi-Fungsi Aproksimasi Interpolasi dan Polinomial Lagrange

Polinomial Taylor yang sementara ini sudah cukup baik melakukan interpolasi terhadap suatu fungsi masih memiliki kelemahan diantaranya kekurangakuratan melakukan suatu aproksimasi. Hal ini disebabkan polinomial ini melakukan aproksimasi hanya berdasarkan satu titik tertentu. Dengan demikian interpolasi yang paling akurat hanya terjadi disekitar titik itu. Oleh karena itu diperlukan eksplorasi terhadap polinomial lainnya, polinomial Lagrange misalnya. Polinomial ini mengembangkan interpolasi terhadap suatu fungsi dibeberapa titik terhubung, sehingga interpolasinya berdasarkan titik-titik yang telah ditentukan terlebih dahulu pada fungsi itu. Semakin dekat jarak penentuan titik yang satu dengan titik yang lainnya semakin akurat aproksimasinya. Dengan kata lain tingkat akurasinya ditentukan oleh kedekatan antara titik-titik (grid) pada fungsi tadi. Teorema 3.4.1 (Polinomial Langrange ke-n) Jika x0 , x1 , x2 , . . . adalah bilangan berbeda dan f adalah suatu fungsi yang terdefinisi pada titik-titik ini, maka ada dengan tungggal suatu polinomial p(x) berderajad paling besar n yang memenuhi sifat-sifat berikut f (x) = p(x) dimana pk (x) = f (x0 )Ln,0 (x) + · · · + f (xn )Ln,n (x) =

n X k=0

dan

n Y (x − xi ) Ln,k (x) = (xk − xi ) i=0 i6=k

untuk k=0,1,2,. . . , n

f (xk )Ln,k (x)


25

Dalam hal ini Ln,k (x) dapat ditulis dngan Lk (x) bila dianggap rancu dengan pengertian derajad n. Polinomial Lagrange ini memenuhi sifat sebagai berikut: ( 0 jika i 6= k Ln,k (xi ) = 1 jika i = k Contoh 1 Gunakan titik-titik x0 = 2, x1 = 2.5 dan x2 = 4 untuk menentukan interpolasi polinomial kedua terhadap f (x) = 1/x. Solusi 1 (x − 2.5)(x − 4) = (x − 6.5)x + 10 (2 − 2.5)(2 − 4) (x − 2)(x − 4) (−4x + 24)x − 32 L1 (x) = = (2.5 − 2)(2.5 − 4) 3 (x − 2)(x − 2.5) (x − 4.5)x + 5 L2 (x) = = (4 − 2)(4 − 2.5) 3 L0 (x) =

jika f (x0 ) = f (2) = 0.5, f (x1 ) = f (2.5) = 0.4, f (x2 ) = f (4) = 0.25, maka didapat p2 (x) =

2 X

f (xk )Lk (x)

k=0

= 0.5((x − 6.5)x + 10) + 0.4 = (0.05x − 0.425)x + 1.15

(−4x + 24)x − 32 (x − 4.5)x + 5 + 0.25 3 3

Interpolasi oleh p2 (x) terhadap f (x) dapat digambarkan dibawah ini

3.4.2

Difrensi Terpisah

Difrensi terpisah menyempurnakan interpolasi polinomial Lagrange dengan mengekspresikan bentuk pn (x) dalam pn (x) = a0 + a1 (x − x0 ) + a2 (x − x0 )(x − x1 ) + . . . +an (x − x0 )(x − x1 ) . . . (x − xn−1 )

(3.6)


26

4

3.5

3

2.5

f(x)

2

1.5 p2(x) 1

0.5

0 0

0.5

1

1.5

2

2.5

3

3.5

4

4.5

5

Gambar 3.2: Interpolasi polinomial Lagrange p2 (x) terhadap f (x) dimana a0 , a1 , . . . , an adalah konstanta. Selanjutnya bila kita tentukan x = x0 maka persamaan (3.6) menjadi pn (x0 ) = a0 = f (x0 ) ≈ f [x0 ],

(3.7)

dan x = x1 maka pn (x1 ) = a0 + a1 (x1 − x0 ) = f (x1 ), pn (x1 ) = f (x0 ) + a1 (x1 − x0 ) = f (x1 ), sehingga a1 =

f (x1 ) − f (x0 ) ≈ f [x0 , x1 ], x1 − x0

(3.8)

dengan demikian dapat dikatakan f [xi , xi+1 ] =

f [xi+1 ] − f [xi ] xi+1 − xi

(3.9)

dan f [xi , xi+1 , xi+2 ] =

f [xi+1 , xi+2 ] − f [xi , xi+1 ] xi+2 − xi

(3.10)

sehingga difrensi terpisah ke k f [xi , xi+1 , . . . , xi+k ] =

f [xi+1 , xi+2 , . . . , xi+k ] − f [xi , xi+1 , . . . , xi+(k−1) ] . xi+k − xi

(3.11)


27

Dan terakhir persamaan (3.6) menjadi pn (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 )

(3.12)

Selanjuntya untuk x = x0 + sh x = xi + (s − i)h atau h =

x − xi , s−i

i = 0, 1, 2, . . . , n

maka pn (x) = pn (x0 + sh) = f [x0 ] + shf [x0 , x1 ] + s(s − 1)h2 f [x0 , x1 , x2 ] + · · · + s(s − 1) . . . (s − (n − 1))hn f [x0 , x1 , . . . , xn ] n X s(s − 1) . . . (s − k + 1)hk f [x0 , x1 , . . . , xk ] =

(3.13) (3.14)

k=0

Bukti x−x0 Pada suku kedua dari persamaan (3.13) h dapat µ diganti ¶µ dengan ¶ h = s , pada x−x1 0 suku ketiga h2 dapat diganti dengan h · h = x−x begitu juga suku s s−1 keempat, kelima dan seterusnya. Sekarang kita nyatakan (3.14) dalam ekspresi Ã ! n X s k!hk f [x0 , x1 , . . . , xk ] pn (x) = pn (x0 + sh) = k k=0 dimana

Ã

s k

! =

s(s − 1) . . . (s − k + 1) k!


28

Dan diperkenalkan difrensi langkah maju sebagai berikut 4f (xn ) = f (xn+1 ) − f (xn ) f (x1 ) − f (xn ) 1 f [x0 , x1 ] = = 4 f (x0 ) x1 − x0 h f [x1 , x2 ] − f [x0 , x1 ] 1 1 1 f [x0 , x1 , x2 ] = = [ 4 f (x2 ) − 4 f (x0 )] x2 − x0 2h h h 1 = 4 f (x0 ) 2h2 sehingga f [x0 , . . . , xk ] =

x x0

f (x) f [x0 ]

D. T. I

1 4k f (x0 ) k!hk

(3.15)

D. T. II

D. T. III

f [x0 , x1 ] x1

f [x1 ]

f [x0 , x1 , x2 ] =

f [x1 ,x2 ]−f [x0 ,x1 ] x2 −x0

f [x1 , x2 ] x2

f [x2 ]

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

f [x2 ,x3 ]−f [x1 ,x2 ] x3 −x1

f [x2 , x3 ] x3

f [x3 ]

f [x1 , x2 , x3 , x4 ] = f [x2 , x3 , x4 ] =

f [x3 ,x4 ]−f [x2 ,x3 ] x4 −x2

f [x3 , x4 ] x4

f [x4 ]

f [x1 ,x2 ,x3 ]−f [x0 ,x1 ,x2 ] x3 −x0

f [x2 ,x3 ,x4 ]−f [x1 ,x2 ,x3 ] x4 −x1

f [x2 , x3 , x4 , x5 ] = f [x3 , x4 , x5 ] =

f [x4 ,x5 ]−f [x3 ,x4 ] x5 −x3

f [x3 ,x4 ,x5 ]−f [x2 ,x3 ,x4 ] x5 −x2

f [x4 , x5 ] x5

f [x5 ] Tabel 3.1: Difrensi terpisah langkah maju.


29

Substitusikan ini kedalam persamaan pn (x) = pn (x0 + sh) =

n X k=0

Ã

s k

! k!hk f [x0 , x1 , . . . , xk ]

maka diperoleh bentuk pn (x) = pn (x0 + sh) =

Pn k=0

Ã

s k

! 4k f (x0 ).

Formulasi ini disebut Difrensi Terpisah Langkah Maju Newton (NFDD). Untuk mempermudah dapat disusun suatu tabel difrensi terpisah langkah maju sebagaimana tabel 3.1. Selanjutnya bila urutan itu dibalik yaitu xn , xn−1 , xn−2 , . . . , x0 , maka pn (x) dapat dinyatakan dalam pn (x) = a0 + a1 (x − xn ) + a2 (x − xn )(x − xn−1 ) + . . . +an (x − xn )(x − xn−1 ) . . . (x − x1 )

(3.16)

dimana a0 , a1 , . . . , an adalah konstanta. Misal kita tentukan x = xn maka persamaan (3.16) menjadi pn (xn ) = a0 = f (xn ) ≈ f [xn ],

(3.17)

dan untuk x = xn−1 maka pn (xn−1 ) = a0 + a1 (xn−1 − xn ) = f (xn−1 ), pn (xn−1 ) = f (xn ) + a1 (xn−1 − xn ) = f (xn−1 ), sehingga a1 =

f (xn−1 ) − f (xn ) f (xn ) − f (xn−1 ) = ≈ f [xn , xn−1 ]. xn−1 − xn xn − xn−1

(3.18)


30

Dengan demikian persamaan (3.16) menjadi pn (x) = f [xn ] + f [xn , xn−1 ](x − xn ) + f [xn , xn−1 , xn−2 ](x − xn )(x − xn−1 ) + . . . +f [xn , xn−1 , . . . , x0 ](x − xn )(x − xn−1 ) . . . (x − x1 )

(3.19)

Selanjutnya untuk x = xn + sh x = xn−i + (s + i)h atau h =

x − xn−i , s+i

i = 0, 1, 2, . . . , n − 1

maka pn (x) = pn (xn + sh) = f [xn ] + shf [xn , xn−1 ] + s(s + 1)h2 f [xn , xn−1 , xn−2 ] + · · · + s(s + 1) . . . (s + (n − 1))hn f [xn , xn−1 , . . . , x0 ] n X s(s + 1) . . . (s + k − 1)hk f [xn , xn−1 , . . . , x0 ] =

(3.20)

k=0

Bukti Pada suku kedua dari persamaan (3.16) h dapat µ diganti ¶µdengan¶h = suku ketiga h2 dapat diganti dengan h · h =

xn −xn−1 s

x−xn−2 s+1

xn −xn−1 , s

begitu juga suku

keempat, kelima dan seterusnya. Sehingga kita memiliki ekspresi pn (x) = pn (x0 + sh) =

n X

Ã (−1)k

k=0

dimana

Ã

s k

! = (−1)k

−s k

! k!hk f [xn , xn−1 , . . . , x0 ]

s(s − 1) . . . (s − k + 1) k!

Diperkenalkan juga bentuk difrensi langkah mundur 5f (xn ) = f (xn ) − f (xn−1 ); 5k f (xn ) = 5(5k−1 f (xn ));

n≥1 k≥2

pada


31

maka x x0

f (x) f [x0 ]

D. T. I

D. T. II

D. T. III

f [x1 , x0 ] x1

f [x1 ]

f [x2 , x1 , x0 ] =

f [x1 ,x0 ]−f [x2 ,x1 ] x0 −x2

f [x2 , x1 ] x2

f [x2 ]

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

f [x2 ,x1 ]−f [x3 ,x2 ] x1 −x3

f [x3 , x2 ] x3

f [x3 ]

f [x4 , x3 , x2 , x1 ] = f [x4 , x3 , x2 ] =

f [x4 ]

f [x3 ,x2 ,x1 ]−f [x4 ,x3 ,x2 ] x1 −x4

f [x3 ,x2 ]−f [x4 ,x3 ] x2 −x4

f [x4 , x3 ] x4

f [x2 ,x1 ,x0 ]−f [x3 ,x2 ,x1 ] x0 −x3

f [x5 , x4 , x3 , x2 ] = f [x5 , x4 , x3 ] =

f [x4 ,x3 ]−f [x5 ,x4 ] x3 −x5

f [x4 ,x3 ,x2 ]−f [x5 ,x4 ,x3 ] x2 −x5

f [x5 , x4 ] x5

f [x5 ] Tabel 3.2: Difrensi terpisah langkah mundur. f (xn ) − f (xn−1 ) 1 = 5 f (xn ) xn − xn−1 h 1 f [xn , xn−1 ] − f [xn−1 , xn−2 ] = 2 52 f (xn ) f [xn , xn−1 , xn−2 ] = xn − xn−2 2h f [xn , xn−1 ] =

dan akhirnya f [xn , xn−1 , . . . , x0 ] =

1 5k f (xn ) k!hk

Substitusikan ini kedalam persamaan pn (x) = pn (x0 + sh) =

n X k=0

Ã (−1)k

−s k

! k!hk f [xn , xn−1 , . . . , x0 ]

(3.21)


32

maka diperoleh bentuk pn (x) = pn (x0 + sh) =

Pn

Ã

k k=0 (−1)

−s k

! 5k f (xn ).

Formulasi ini disebut Difrensi Terpisah Langkah Mundur Newton (NBDD). Dalam hal ini dapat pula disusun suatu tabel difrensi terpisah langkah mudur yang disajikan dalam Tabel 3.2. Contoh 2 Suatu data diberikan dalam tabel berikut ini Tentukan interpolasi difrensi x 1.0 1.3 1.6 1.9 2.2

f (x) 0.7651977 0.6200860 0.4554022 0.2818186 0.1103623

Tabel 3.3: Data f (x) terpisal langkah maju p4 terhadap data tersebut dan tentukan nilai aproksimasi dari f (1.5). Solusi 2 Dengan menggunakan difrensi terpisah langkah maju didapatkan tabel berikut ini Sehingga formulasi dari NFDD adalah sebagai berikut p4 (x) = 0.7651977 − 0.4837057(x − 1.0) − 0.1087339(x − 1.0)(x − 1.3) + 0.0658784 .(x − 1.0)(x − 1.3)(x − 1.6) + 0.0018251(x − 1.0)(x − 1.3)(x − 1.6)(x − 1.9)


i 0

xi 1.0

f [xi ] 0.7651977

FDD I

FDD II

FDD III

33

FDD IV

-0.4837057 1

1.3

0.6200860

-0.1087339 -0.5489460

2

1.6

0.0658784

0.4554022

-0.0494433

0.0018251

-0.5786120 3

1.9

0.0680685

0.2818186

0.0118183 -0.5715210

4

2.2

0.1103623

Selanjutnya dapat ditentukan f (1.5) ≈ p4 (1.5) = 0.5118200 Gambar dibawah ini menunjukkan bagaimana p4 (x) menginterpolasi data f (x) 1 0.9 0.8 0.7 0.6 p4(x) 0.5 0.4 0.3 0.2 0.1 0 0.5

1

1.5

2

2.5

3

Gambar 3.3: Approksimasi NFDD p4 (x)

3.4.3

Interpolasi Splin Kubik

Definisi 3.4.1 Fungsi f terdefinisi pada interval [a, b] dan diberikan himpunan titik x0 , x1 , . . . , xn dimana a = x0 < x1 < · · · < xn = b, maka interpolasi splin


34

kubik S untuk f adalah suatu fungsi yang memenuhi beberapa sarat berikut ini 1. S(x) adalah fungsi polinomial kubik, dinotasikan dengan Sj (x), yang terdefinisi pada subinterval [xj , xj+1 ] untuk masing-masing j = 0, 1, . . . , n − 1; 2. S(xj ) = f (xj ) untuk setiap j = 0, 1, . . . , n; 3. Sj+1 (xj+1 ) = Sj (xj+1 ) untuk setiap j = 0, 1, . . . , n − 2; 0 4. Sj+1 (xj+1 ) = Sj0 (xj+1 ) untuk setiap j = 0, 1, . . . , n − 2; 00 5. Sj+1 (xj+1 ) = Sj00 (xj+1 ) untuk setiap j = 0, 1, . . . , n − 2;

6. dan satu diantara sarat batas berikut terpenuhi (a) S 00 (x0 ) = S 00 (xn ) = 0 (sarat batas bebas atau alami); (b) S 0 (x0 ) = f 0 (x0 ) dan S 0 (xn ) = f 0 (xn ) (sarat batas terikat); Selanjutnya jika sarat batas bebas yang terjadi maka splin ini dinamakan Splin Alami, dan sebaliknya bila sarat batas terikat yang terjadi maka disebut Splin Terikat. Splin Kubik Alami Untuk membangun splin kubik ini pertama kali kita tulis interpolasi plonomial kubik Sj (x) = aj + bj (x − xj ) + cj (x − xj )2 + dj (x − xj )3 ;

j = 0, 1, . . . , n − 1 (3.22)

Untuk x = xj , maka Sj (xj ) = aj = f (xj )

(3.23)

dan untuk x = xj+1 maka aj+1 = Sj+1 (xj+1 ) = Sj (xj+1 ) = aj + bj (xj+1 − xj ) + cj (xj+1 − xj )2 + dj (xj+1 − xj )3


35

j = 0, 1, . . . , n − 2. Bila hj = xj+1 − xj aj+1 = aj + bj hj + cj h2j + dj h3j ;

j = 0, 1, . . . , n − 1

(3.24)

Sekarang didefinisikan bn = Sn0 (x) dan turunan pertama (3.22) adalah Sj0 (x) = bj + 2cj (x − xj ) + 3dj (x − xj )2 sehingga 0 bj+1 = Sj+1 (xj+1 ) = Sj0 (xj+1 ), (lihat poin5 . pada definisi)

= bj + 2cj hj + 3dj h2j ; Sekarang permisalkan c =

00 (x) Sn , 2

j = 0, 1, . . . , n − 1.

(3.25)

dan turunan kedua dari (3.22) adalah

Sj00 (x) = 2cj + 6dj (x − xj ) sehingga cj+1 = cj + 3dj hj (cj+1 − cj ) dj = 3hj

(3.26)

Substitusikan persamaan ini ke (3.24)dan (3.25) didapat aj+1 = aj + bj hj + = aj + bj hj +

cj h2j

(cj+1 − cj )h3j ; + 3hj

h2j (2cj + cj+1 ) 3

(3.27)

dan (cj+1 − cj )h2j ; 3hj = bj + hj (cj + cj+1 )

bj+1 = bj + 2cj hj + 3

(3.28)

Ekspresikan persamaan (3.27) dalam bj dan kemudian reduksi indeknya satu kali hj 1 (aj+1 − aj ) − (2cj + cj+1 ). hj 3 hj−1 1 (aj − aj−1 ) − (2cj−1 + cj ). = hj−1 3 bj =

bj−1

(3.29) (3.30)


36

Reduksi juga indek dari persamaan (3.28) satu kali bj = bj−1 + hj−1 (cj−1 + cj )

(3.31)

Substitusikan (3.29) dan (3.30) ke (3.31) 1 1 hj hj−1 (aj+1 − aj ) − (2cj + cj+1 ) = (aj − aj−1 ) − (2cj−1 + cj ) hj 3 hj−1 3 hj−1 (2cj−1 + cj ). + 3 Kelompokkan seluruh variabel c keruas kiri hj 1 hj−1 (2cj−1 + cj ) − hj−1 (cj−1 + cj ) − (2cj + cj+1 ) = − (aj+1 − aj ) 3 3 hj 1 + (aj − aj−1 ) hj−1 3 −hj−1 (2cj−1 + cj ) + 3hj−1 (cj−1 + cj ) + hj (2cj + cj+1 ) = (aj+1 − aj ) hj 3 − (aj − aj−1 ) hj−1 Dengan demikian diperoleh bentuk indek berurut dari koefisien c hj−1 cj−1 + 2(hj−1 + hj )cj + hj cj+1 =

3 3 (aj+1 − aj ) − (aj − aj−1 ), (3.32) hj hj−1

dimana j = 1, 2, . . . , n − 1. Splin kubik alami memenuhi kondisi S 00 (x0 ) = S 00 (xn ) = 0, dengan demikian


37

masing-masing j dapat diformulasikan sebagai berikut j = 0 → c0 = 0; 3 (a2 − a1 ) − h1 3 j = 2 → h1 c1 + 2(h1 + h2 )c2 + h2 c3 = (a3 − a2 ) − h2 .. .

j = 1 → h0 c0 + 2(h0 + h1 )c1 + h1 c2 =

3 (a1 − a0 ); h0 3 (a2 − a1 ); ; h1

j = n − 1 → hn−2 cn−2 + 2(hn−2 + hn−1 )cn−1 + hn−1 cn = −

3

hn−2 j = n → cn = 0.

3 hn−1

(an − an−1 )

(an−1 − an−2 );

Persamaan ini terdiri dari n persamaan dan n variable cj yang akan dicari, dengan kata lain menyelesaikan persamaan ini adalah sama dengan menyelesaikan suatu sistem linier Ax = b, dimana   1 0 0 0   h1  h0 2(h0 + h1 )     0  h 2(h + h ) h 1 1 2 2  A=  0       hn−2 2(hn−2 + hn−1 ) hn−1  0 0 0 1 dan

      b=    

0 3 (a2 − a1 ) − h1 3 (a3 − a2 ) − h2 .. .



     ,    3 3 (a − a ) − (a − a ) n n−1 n−1 n−2  hn−1 hn−2 0 3 (a1 h0 3 (a2 h1

− a0 ) − a1 )



c0 c1 c2 .. .

     x=    c  n−1 cn

          

Matrik A adalah matrik yang elemennya mendominasi diagonal sejajar dengan diagonak utama (strictly diagonally dominant), diluar itu nilainya nol. Hal ini


38

membantu dalam melakukan kalkulasi untuk x. Dengan menggunakan metoda iteratif, sistem linier itu dapat diselesaikan dengan mudah. Algoritma splin kubik alami INPUT n; x0 , x1 , . . . , xn ; a0 = f (x0 ), . . . , an = f (xn ). OUTPUT aj , bj , cj , dj , untuk j = 1, 2, . . . , n − 1(Catatan : Sj (xj ) = aj + bj (x − xj ) + cj (x − xj )2 + dj (x − xj )3 untuk xj ≤ x ≤ xj+1 .) Step 1 for i = 0, 1, . . . , n − 1 dan Set hi = xi+1 − xi . Step 2 for i = 1, . . . , n − 1 dan Set αi = Step 3

Step 4

Step 5

Step 6

Step 7

3 3 (ai+1 − ai ) − (ai − ai−1 ) hi hi−1

Set l0 = 1(Langkah 3,4,5 dan sebagian dari 6 adalah algoritma untuk menyelesaikan sistem linier tridiagonal Ax = b) µ0 = 0; z0 = 0. for i = 1, 2, . . . , n − 1 set li = 2(xi+1 − xi−1 ) − hi−1 µi−1 ; µi = hi /li ; zi = (αi − hi−1 zi−1 )/li . Set ln = 1; zn = 0; cn = 0. for j = n − 1, n − 2, . . . , 0 set cj = zj − µj cj+1 ; bj = (aj+1 − aj )/hj − hj (cj+1 + 2cj )/3; dj = (cj+1 − cj )/(3hj ). OUTPUT(aj , bj , cj , dj , untuk j = 1, 2, . . . , n − 1); STOP.


39

Contoh 3 Tentukan interpolasi splin kubik pada data berikut ini xj 0 1 2 3

aj = f (xj ) 0 1 3 2

Solusi 3 Polinomial kubik dalam hal ini adalah Sj (xj ) = aj + bj (x − xj ) + cj (x − xj )2 + dj (x − xj )3 , dimana j = 1, . . . , n − 1. Karena n = 3 maka j = 1, 2, dengan asumsi j = 0 → c0 = 0 dan j = 3 → c3 = 0 sehingga   1 0 0 0  h 2(h + h ) h1 0   0  0 1 A=   0 h1 2(h1 + h2 ) h2  0 0 0 1 dan

   b= 

0 3 (a2 − a1 ) − h1 3 (a3 − a2 ) − h2 0

 3 (a1 h0 3 (a2 h1

− a0 ) − a1 )

Dengan memasukkan nilai hj dan aj dapatlah berikut  1 0 0  1 4 1  A=  0 1 4 0 0 0

  , 

   x= 

c0 c1 c2 c3

    

diperoleh matrik dan vektor sebagai 0 0 1 1

    

BAB 3. INTERPOLASI DAN APROKSIMASI POLINOMIAL dan

   b= 

0 3 −9 0

40

    

Dengan menyelesaikan sistem itu diperoleh vektor x sebagai berikut     0 c0  c   1.40    1   x= =   c2   −2.60  c3

0

Sedang bj dan dj dapat dihitung dengan menggunakan rumus (3.29) dan (3.26). Hasil selengkapnya dapat dilihat dalam tabel berikut xj 0 1 2 3

aj 0 1 3 2

bj 0.53333 1.93333 0.73333 −

cj 0 1.40 -2.60 0

dj 0.46667 -13.33333 0.86667 −

Grafik dibawah ini menunjukkan interpolasi splin kubik terhadap suatu data ’*’.

3.5

Solusi Iteratif Integral Terbatas

Teknik numeris untuk menghitung integral tertentu yang dikenal sebagai Integrasi Numeris dibutuhkan untuk menyelesaikan atau menghitung nilai integral dimana fungsi yang diintegralkan tidak mempunyai antiturunan yang eksplisit atau fungsi yang antiturunannya tidak mudah ditentukan. Suatu metoda yang cukup dasar sekali adalah metoda numeris kuadratur. Metoda ini menggunakan rumus Rb P jumlah ni=0 ai f (xi ) untuk menghitung nilai approksimasi terhadap a f (x)dx.


41

5

4

3

2

S3(x)

1

0

−1 0

0.5

1

1.5

2

2.5

3

Gambar 3.4: Approksimasi spline kubik S3 (x) Interpolasi fungsi approksimasi metoda ini didasarkan atas pemilihan dan pengembangan interpolasi polinomial Lagrange karena polinomial ini dianggap merupakan fungsi approksimasi yang terbaik p∗. Prosedur penurunannya diawali dengan menentukan himpunan titik-titik berbeda x0 , . . . , xn dari interval [a, b], selanjutnya mengintegralkan polinomial Lagrange dan suku kesalahan pemenggalannya dalam interval [a, b]. n X Pn (x) = f (xi )Li (x) i=0

Z

Z bX n

b

f (x)dx = a

a n X

=

f (xi )Li (x)dx +

a i=0

i=0

ai f (xi ) +

i=0

Z bY n

1 (n + 1)!

Z bY n

(x − xi )

f n+1 (ξ(x)) dx (n + 1)!

(x − xi )f n+1 (ξ(x))dx,

a i=0

dimana ξ(x) ∈ [a, b] untuk setiap x dan Z b ai = Li (x)dx untuk setiap i = 0, 1, 2, . . . , n. a

Dengan demikian secara umum formula kuadratur numeris itu adalah Z b n X f (x)dx ≈ ai f (xi ), a

i=0


42

dengan kesalahan 1 E(f ) = (n + 1)!

Z bY n

(x − xi )f (n+1) (ξ(x))dx.

a i=0

Metoda ini dipandang terlampau sederhana dan tidak cukup akurat untuk mengatasi permasalahan yang lebih komplek. Bila kita cermati formulasi kesalahannya maka rumusan ini digeneralisasi dari pengembangan aproksimasi deret Taylor yang belum diekpansi, sedangkan disadari bahwa akurasi deret Taylor yang belum terekspansi level akurasinya rendah dan penetapan fungsi aproksimasinya hanya berdasarkan pada pengambilan satu titik sampel. Metoda lain yang dipandang lebih akurat adalah aturan Trapesium dan Simpson. Aturan ini dikembangkan dari perluasan interpolasi polinomial Lagrange kesatu dan kedua pada himpunan titik-titik sampel. Misal kita notasikan x0 = a, x1 = b, h = b − a dan polinomial Lagrange linier (x − x0 ) (x − x1 ) f (x0 ) + f (x1 ). P1 (x) = (x0 − x1 ) (x1 − x0 ) maka Z

Z

b

x1

·

f (x)dx = a

x0

1 + 2

Z

¸ (x − x1 ) (x − x0 ) f (x0 ) + f (x1 ) dx (x0 − x1 ) (x1 − x0 ) x1

f 00 (ξ(x))(x − x0 )(x − x1 )dx.

(3.33)

x0

Jika (x − x0 )(x − x1 ) tidak berubah tanda dalam interval [x0 , x1 ] maka teorema nilai ”weighted mean” untuk integral dapat diterapkan dalam suku kesalahannya sehingga diperoleh Z x1 Z x1 00 00 f (ξ(x))(x − x0 )(x − x1 )dx = f (ξ) (x − x0 )(x − x1 )dx x0 x0 · 3 ¸x1 x (x1 + x0 ) 2 00 = f (ξ) − x + x0 x1 x 3 2 x0 = −

h3 00 f (ξ). 6


43

Sebagai konsukwensinya (3.33) akan menjadi · ¸x1 Z b (x − x1 )2 (x − x0 )2 h3 f (x)dx = f (x0 ) + f (x1 ) − f 00 (ξ) 2(x0 − x1 ) 2(x1 − x0 ) 12 a x0 =

x1 − x0 h3 [f (x0 ) + f (x1 )] − f 00 (ξ). 2 12

Dengan demikian untuk h = x1 − x0 kita mendapatkan rumus berikut ini Aturan Trapesium Rb a

f (x)dx = h2 [f (x0 ) + f (x1 )] −

h3 00 f (ξ) 12

(3.34)

Rumus ini disebut aturan Trapesium karena jika f adalah susatu fungsi positif, Rb maka a f (x)dx dapat diapproksimasikan dengan luas dari trapesium sebagaimana digambarkan dalam Gambar 3.5.

y

f P_1

x a=x_0

b=x_1

Gambar 3.5: Aturan Trapesium. Bila kita perhatikan rumus diatas, dapatlah disimpulkan bahwa aturan Trapesium itu akan memberikan solusi eksak terhadap sebarang fungsi yang turunan keduanya adalah sama dengan nol (sebarang polinomial berorder satu atau kurang), karena suku kesalahan trapesium ini meliputi f 00 . Dengan kata lain aturan Trapesium dikatakan berorder satu, dan suku kesalahan pemenggalannya adalah suatu fungsi O(h2 ). Dari sisi ini kita dapat mengatakan bahwa aturan Trapesium juga tidak cukup akurat untuk menyelesaikan persoalan-persoalan yang sangat komplek


44

memandang rendahnya order dari aturan ini sehingga tetap dibutuhkan aturan lainnya. Salah satu metoda yang cukup terkenal adalah aturan Simpson. Aturan Simpson didapat dari mengintegralkan polinomial Lagrange kedua dalam batas [a, b] dengan beberapa titik x0 = a, x2 = b dan x1 = a + h, untuk h = (b−a) , 2 lihat Gambar 3.6. Polinomial Lagrange kedua disajikan dalam P2 (x) =

Sehingga Z b

·

f (x)dx = a

(x − x1 )(x − x2 ) (x − x0 )(x − x2 ) f (x0 ) + f (x1 ) (x0 − x1 )(x0 − x2 ) (x1 − x0 )(x1 − x2 ) (x − x0 )(x − x1 ) + f (x2 ) (x2 − x0 )(x2 − x1 )

(x − x1 )(x − x2 ) (x − x0 )(x − x2 ) f (x0 ) + f (x1 ) (x0 − x1 )(x0 − x2 ) (x1 − x0 )(x1 − x2 ) ¸ (x − x0 )(x − x1 ) + f (x2 ) dx (x2 − x0 )(x2 − x1 ) Z x1 (x − x0 )(x − x1 )(x − x2 ) (3) + f (ξ(x))dx. 6 x0

y

f

P_1 x a=x_0

x_1

b=x_2

Gambar 3.6: Aturan Simpson. Sebagaimana aturan Trapesium, penentuan orde aturan Simpson juga dapat dilihat dari suku kesalahannya. Suku kesalahan rumus ini hanya sampai pada suku


45

kesalahan O(h4 ) yaitu hanya meliputi f (3) sehingga aturan Simpson yang diturunkan dari interpolasi Lagrange hanya berorder dua. Versi yang lebih baik dari aturan Simpson order dua ini adalah aturan yang diturunkan dari ekspansi polinomial Taylor ketiga f terhadap x1 . Misalkan masing-masing x ∈ [a, b] ada bilangan ξ(x) ∈ (x0 , x1 ) maka ekspansi Taylor f (x) = f (x1 ) + f 0 (x1 )(x − x1 ) + + dan

Z

f 00 (x1 ) f 000 (x1 ) (x − x1 )2 + (x − x1 )3 2 6

f (4) (ξ(x)) (x − x1 )4 24 ·

x2

f (x)dx = x0

f 0 (x1 ) (x − x1 )2 2 ¸x2 f 00 (x1 ) f 000 (x1 ) 3 4 + (x − x1 ) + (x − x1 ) 6 24 x0 Z x1 1 + f (4) (ξ(x))(x − x1 )4 dx 24 x0 f (x1 )(x − x1 ) +

(3.35)

Karena (x − x1 )4 tidak pernah bernilai negatif pada interval [x0 , x1 ], maka teori nilai ”Weighted Mean” untuk integral akan menjadi Z x1 Z 1 f (4) (ξ1 ) x2 (4) 4 f (ξ(x))(x − x1 ) dx = (x − x1 )4 dx 24 x0 24 x0 ¯x2 (4) ¯ f (ξ1 ) 5¯ = (x − x1 ) ¯ 120 x0

untuk sebarang ξ1 ∈ (x0 , x2 ). Sementara kita tahu bahwa h = x2 − x1 = x1 − x0 , sehingga (x2 − x1 )2 − (x0 − x1 )2 = (x2 − x1 )4 − (x0 − x1 )4 = 0 (x2 − x1 )3 − (x0 − x1 )3 = 2h3 dan (x2 − x1 )5 − (x0 − x1 )5 = 2h5 Sebagai konsukwensinya persamaan (3.35) dapat ditulis sebagai Z x2 h3 h5 f (x)dx = 2hf (x1 ) + f 00 (x1 ) + f (4) (ξ1 ) 3 60 x0

(3.36)


46

Disisi lain kita memiliki ekspresi 1 1 1 f (x0 + h) = f (x0 ) + f 0 (x0 )h + f 00 (x0 )h2 + f 000 (x0 )h3 + f (4) (ξ1 )h4 2 6 24 1 1 1 f (x0 − h) = f (x0 ) + f 0 (x0 )h − f 00 (x0 )h2 + f 000 (x0 )h3 − f (4) (ξ−1 )h4 2 6 24 dimana x0 − h < ξ−1 < x0 < ξ1 < x0 + h. Dan bila kita jumlahkan kedua ekspansi Taylor ini f (x0 + h) + f (x0 − h) = 2f (x0 ) + f 00 (x0 )h2 +

1 (4) [f (ξ1 +) + f (4) (ξ−1 +)]h4 24

Sederhanakan untuk f 00 (x0 ) didapat f 00 (x0 ) =

1 h2 (4) [f (x − h) − 2f (x ) + f (x + h)] − [f (ξ1 ) 0 0 0 h2 24 +f (4) (ξ−1 +)].

(3.37)

Teorema nilai tengah mengatakan bahwa untuk f (4) ∈ C[x0 − h, x0 + h] maka 1 f (4) (ξ) = [f (4) (ξ1 +) + f (4) (ξ−1 +)]. 2 Dengan demikian kita dapat menulis (3.37) sebagai f 00 (x0 ) =

1 h2 (4) [f (x − h) − 2f (x ) + f (x + h)] − f (ξ), 0 0 0 h2 12

(3.38)

untuk sebarang ξ ∈ (x0 − h, x0 + h). Pada akhirnya (3.36) dapat ditulis dengan mengganti f 00 (x0 ) dengan persamaan (3.38) adalah ½ Z x2 h3 1 f (x)dx = 2hf (x1 ) + [f (x0 ) − 2f (x1 ) + f (x2 )] 3 h2 x0 ¾ h2 (4) h5 − [f (ξ2 ) + f (4) (ξ1 ) 12 60 · ¸ 3 h h5 1 (4) 1 (4) = [f (x0 ) + 4f (x1 ) + f (x2 )] − f (ξ2 ) − f (ξ1 ) 3 12 3 5 Dan ingat sekali lagi bahwa kita dapat mengganti ekspresi ξ1 dan ξ2 dengan ξ ∈ (x0 , x2 ) sehingga aturan Simpson secara umum adalah


47

Aturan Simpson R x2 x0

f (x)dx = h3 [f (x0 ) + 4f (x1 ) + f (x2 )] −

h5 (4) f (ξ) 90

(3.39)

Secara definitif perbincangan order itu dapat ditafsirkan sebagai barometer keakuratan suatu teknik approksimasi. Semakin tinggi order itu berarti semakin luas ekspansi suku kesalahannya, akibatnya kesalahan pemenggalan semakin kecil. Sebagaimana dijelaskan dalam Burden dan Faires definisi derajad keakuratan dapat dijelaskan sebagai berikut: Definisi 3.5.1 (Derajad keakuratan atau presesi) Derajad keakuratan atau presesi dari formulasi kuadratur adalah bilangan bulat positif terbesar n sedemikian hingga formula itu eksak untuk xk , dimana k = 1, 2, . . . , n (1997 : 89). Dengan definisi (5.1.1) ini ditambah kenyataan besarnya order pada masing-masing aturan, maka aturan Trapesium dan Simpson masing-masing mempunyai derajad presesi satu dan tiga. Maka dapatlah disimpulkan bahwa aturan Simpson akan lebih cepat konvergen dibandingkan aturan Trapesium. Artinya aturan Simpson dimungkinkan lebih akurat pendekatannya dalam menghitung nilai integral untuk jumlah iterasi yang sama dari kedua aturan tersebut.


48

Latihan Tutorial 3 1. Buktikan bahwa ||f || = maxa≤x≤b |f (x)| merupakan norm pada C[a, b]. 2. Jika A ∈ IRN ×N , A = AT dan A definit positif matrik, yakni xT Ax > 0 1 untuk seberang vektor x, maka buktikan bahwa ||x||A = (xT Ax) 2 merupakan norm pada IRN 3. Mana diantara berikut ini merupakan norm. (a) dalam IR2 ,

||x|| = max{3|x1 | + 2|x2 |, 2|x1 | + 3|x2 |}. P (b) dalam IRN , ||a|| = max0≤x≤1 | nk=1 ak xk−1 |. 4. Nyatakan teorema aproksimasi Weirstrass untuk f ∈ C[a, b]. Selanjutnya ( ) p1 Rb tunjukkan bahwa untuk ||g||p = w(x)|g(x)|p dx dimana 1 ≤ p ≤ ∞, a dan diberikan ² > 0, maka ∃N = N (²) dan polinomial pN (x) sedemikian hingga 1 ||f − pN || ≤ K p ², untuk sebarang konstanta K > 0 5. Gunakan interpolasi polinomial Lagrange derajad satu, dua dan tiga untuk menentukan nilai aproksimasi dari masing-masing dibawah ini (a) tentukan nilai dari f (8.4) bila diketahui f (8.1) = 16.94410, f (8.3) = 17.56492, f (8.6) = 18.50515 dan f (8.7) = 18.82091. (b) tentukan nilai dari f (0.25) bila diketahui f (0.1) = −0.62049958, f (0.2) = −0.28398668, f (0.3) = 0.00660095 dan f (0.4) = 0.24842440. (c) tentukan nilai daricos 0.750 bila diketahui cos 0.698 = 0.7661, cos 0.733 = 0.7432, cos 0.768 = 0.7193 dan cos 0.803 = 0.6946. 6. Tentukan fungsi aproksimasi Lagrange untuk menginterpolasi fungsi berikut

BAB 3. INTERPOLASI DAN APROKSIMASI POLINOMIAL (a) f (x) = e2x cos 3x, (b) f (x) = sin ln x,

49

x0 = 0, x1 = 0.3, x2 = 0.6 x0 = 2.0, x1 = 2.4, x2 = 2.6

(c) f (x) = cos x + sin x, (d) f (x) = e2x cos 3x,

x0 = 0, x1 = 0.25, x2 = 0.5, x3 = 1.0

x0 = 0, x1 = 0.3, x2 = 0.6

7. Suatu data disajikan dalam tabel dibawah ini maka tentukan x 0.0 f (x) 1.00000

0.2 1.22140

0.4 1.49182

0.6 1.82212

0.8 2.22554

(a) nilai dari f (0.05) dengan menggunakan NFDD (b) nilai dari f (0.65) dengan menggunakan NBDD 8. Polinomial berderajad empat p(x) memenuhi sifat 44 p(0) = 24, 43 p(0) = 6, dan 42 p(0) = 0 dimana 4p(x) = p(x + 1) − p(x). Hitung 42 p(10). 9. Perbincangan aproksimasi lebih luas banyak dikaitkan dengan interpolasi terhadap suatu fungsi f dengan fungsi aproksimasi p. Selanjutnya akurasi interpolasi itu diukur dari kedekatan antara f dan p, secara matematis ditulis dengan ||f −p|| (dibaca : norm(f-p)). Sebutkan definisi norm ini, baik vektor ataupun matrik. Kemudian dengan pemahaman akan norm ini sebutkan apa sebenarnya inti permasalahan (konsep masalah) dalam aproksimasi itu. Jika kita memilih fungsi aproksimasi p tentunya kita pilih fungsi yang terbaik. Dalam hal ini ada beberapa fungsi aproksimasi yang dapat digunakan untuk menginterpolasi fungsi f itu, sebutkan nama-nama fungsi aproksimasi tersebut. Salah satu fungsi aproksimasi yang fleksibel adalah splin kubik. Dengan data dibawah ini tentukan fungsi aproksimasi splin kubik untuk menginterpolasi data f (xj ) dimana xj = 0, 1, 2. 10. Gunakan splin kubik untuk menginterpolasi fungsi-fungsi berikut ini


xj 0 1 2

50

aj = f (xj ) 1 9 2

(a) f (x) = x ln x; dan tentukan f (8.4) dan f 0 (8.4) (b) f (x) = sin(ex − 2); dan tentukan f (0.9) dan f 0 (0.9) (c) f (x) = x cos x − 2x2 + 3x − 1; dan tentukan f (0.25) dan f 0 (0.25) 11. Splin kubik alami S pada interval [0, 2] didefinisikan sebagai ( S0 (x) = 1 + 2x − x3 jika 0 ≤ x < 1, S(x) = 2 3 S1 (x) = a + b(x − 1) + c(x − 1) + d(x − 1) jika 1 ≤ x < 2, tentukan nilai dari a, b, c, dan d. 12. Berikut ini disajikan konstruksi automobile, gunakan splin kubik untuk menginterplosi permukaan atas automobile tersebut.

x_2 x_0 x_1

x_3

x_4 x_5 ... x_n

Gambar 3.7: Konstruksi automobile


51

13. Sebuah mobil bergerak dengan kecepatan dan jarak tertentu pada saat tertentu t, sebagaimana digambarkan dalam tabel berikut. Selanjutnya Waktu (jam) Jarak (km) Kecepatan

0 3 0 225 75 77

5 8 383 623 80 74

13 993 72

(a) gunakan splin kubik untuk mempridiksikan jarak yang ditempuh mobil dan kecepatan pada saat mobile melaju selama 10 jam. (b) Tentukan kecepatan maksimum dari laju mobil tersebut.

BAB 4 Metoda Numeris untuk Sistem Nonlinier Suatu tekanan p dibutuhkan untuk menancapkan suatu plat sirkuler dengan radius r kedalam permukaan keras yang mempunyai panjang D. Plat itu akan ditancapkan sejauh d (dengan D > d) dibawah permukaan. Tekanan itu bervariasi tergantung besarnya radius dari plat sirkuler tadi, semakin besar radius plat semakin besar pula tekanan yang dibutuhkan, sehingga hubungan antara tekanan p dengan radius plat r dapat disajikan sebagai p = k1 ek2 r + k3 r, dimana k1 , k2 dan k3 adalah konstanta yang tergantung pada kedalaman plat itu ditancapkan d dan konsistensi dari permukaan. Selanjutnya untuk menentukan radius minimal plat yang masih memungkinkan plat dapat menahan beban besar akibat dari tekanan dan permukaan keras tadi, pada gambar tiga plat sirkuler dengan radius, dan tekanan yang berbeda ditancapkan bersama dengan kedalaman yang sama. Peristiwa ini menghasilkan persamaan tiga

52

BAB 4. METODA NUMERIS UNTUK SISTEM NONLINIER

m2

m1

r1

r2

53

m

3

r

3

sistem non linier m1 = k1 ek2 r1 + k3 r1 m2 = k1 ek2 r1 + k3 r1 m3 = k1 ek2 r1 + k3 r1 . Untuk menentukan k1 , k2 dan k3 , metoda numeris merupakan alternatif yang baik. Sistem persamaan non linier dapat disajikan dalam bentuk f1 (x1 , x2 , . . . , xn ) = 0 f2 (x1 , x2 , . . . , xn ) = 0 f3 (x1 , x2 , . . . , xn ) = 0 .. .

(4.1)

fn (x1 , x2 , . . . , xn ) = 0 Alternatif lain kita dapat menulis sistem itu dalam fungsi F, yang memetakan Rn terhadap Rn . ¡ ¢T F(x1 , x2 , dots, xn ) = f1 (x1 , x2 , . . . , xn ), f2 (x1 , x2 , . . . , xn ), . . . , fn (x1 , x2 , . . . , xn ) F(x) = 0

(4.2)

Definisi 4.0.1 Suatu fungsi f yang memetakan D ⊂ Rn kedalam R dikatakan kontinyu pada x0 bila lim f (x) = f (x0 ). x→x0


54

Selanjutnya untuk f yang kontinyu pada himpunan domain D dan kontinyu pula disetiap elemen D maka dapat ditulis f ∈ C(D). Definisi 4.0.2 Suatu fungsi F yang memetakan D ⊂ Rn kedalam Rn dengan bentuk F = (f1 (x), f2 (x), . . . , fn (x))T maka lim F(x) = L = (L1 , L2 , . . . , Ln )T

x→x0

jika dan hanya jika limx→x0 fi (x) = Li untuk masing-masing i. Selanjutnya fungsi F akan kontinyu pada x0 ∈ D bila limx→x0 F(x) ada, dan limx→x0 F(x) = F(x0 ) dan bila F kontinyu dalam domain D maka F akan kontinyu pada setiap x ∈ D. dengan simbol yang sama dengan teorema (4.0.2) dalam hal ini ditulis sebagai F ∈ C(D) Teorema 4.0.1 Jika f adalah fungsi yang memetakan D ⊂ Rn kedalam R dan x0 ∈ D, maka jika ditemukan suatu konstanta δ > 0 dan K > 0 dengan ketentuan ¯ ¯ ¯ ∂f (x) ¯ ¯ ¯ ¯ ∂xj ¯ ≤ K, untuk j = 1, 2, . . . , n dan ||x − x0 || < δ,

x∈D

maka f adalah kontinyu pada x0 .

4.1

Metoda Titik Tetap

Definisi 4.1.1 Suatu fungsi G yang memetakan D ⊂ Rn kedalam Rn mempunyai titik tetap pada p ∈ D jika G(p)=p.

BAB 4. METODA NUMERIS UNTUK SISTEM NONLINIER ½

¾ T

Teorema 4.1.1 Jika D =

55

(x1 , x2 , . . . , xn ) |ai ≤ xi ≤ bi ,

i = 1, 2, . . . , n , dan

G adalah fungsi kontinyu yang memetakan D ⊂ Rn kedalam R dengan sifat G(x) ∈ D untuk sebarang x ∈ D, maka G mempunyai titik tetap pada D. Selanjutnya bila G kontinyu pada turunan partialnya dan ditemukan konstanta K < 1 dengan ¯ ¯ ¯ ∂gi (x) ¯ K ¯ ¯ ¯ ∂xj ¯ ≤ n , untuk sebarangx ∈ D, untuk masing-masing j = 1, 2, . . . , n dan masing-masing komponen gi . Maka sederetan bilangan {x[k] }∞ k=0 yang didefinisikan sebagai x[k] = G(x[k−1] ),

untuk masing − masing k ≥ 1

akan konvergen terhadap titik tetap tunggal p ∈ D dan ||x[k] − p||∞ ≤

Kk ||x(1) − x(0) ||∞ . 1−K

(4.3)

Contoh 4.1.1 Buktikan bahwa sistem non linier berikut ini mempunyai titik tetap © ª tunggal pada D = (x1 , x2 , x3 )T | − 1 ≤ xi ≤ 1, i = 1, 2, 3 . 1 = 0 2 x21 − 81(x2 + 0.1)2 + sin x3 + 1.06 = 0 10π − 3 e−x1 x2 + 20x3 + = 0. 3 3x1 − cos(x2 x3 ) −

Penyelesaian 4.1.1 Selesaikan persamaan diatas untuk xi maka 1 1 cos(x2 x3 ) + , 3q 6 1 = x21 + sin x3 + 1.06 − 0.1, 9 1 10π − 3 = − e−x1 x2 − . 20 60

x1 = x2 x3


56

dengan demikian untuk G : Rn → Rn didefinisikan G(x) = (g1 x), g2 x), g3 x))T dimana 1 1 g1 (x1 , x2 , x3 ) = cos(x2 x3 ) + , 3q 6 1 g2 (x1 , x2 , x3 ) = x21 + sin x3 + 1.06 − 0.1, 9 1 10π − 3 g3 (x1 , x2 , x3 ) = − e−x1 x2 − . 20 60 Untuk x = (x1 , x2 , x3 )T ∈ D maka 1 1 |cos(x2 x3 )| + ≤ 0.50, 3q 6 1 x21 + sin x3 + 1.06 − 0.1, |g2 (x1 , x2 , x3 )| = 9 1√ = 1 + sin 1 + 1.06 − 0.1 < 0.09, 9 10π − 3 1 . |g3 (x1 , x2 , x3 )| ≤ | − e−x1 x2 | + 20 60 1 10π − 3 = e+ < 0.61, 20 60 sehingga −1 ≤ gi (x1 , x2 , x3 ) ≤ 1, untuk i = 1, 2, 3, dengan demikian G(x) ∈ D untuk sebarang x ∈ D. |g1 (x1 , x2 , x3 )| ≤

Slanjutnya kita tentukan ¯ ¯ ¯ ∂gi ¯ K ¯ ¯ ¯ ∂xj ¯ ≤ n , Dalam hal ini

¯ ¯ ¯ ∂g1 ¯ ¯ ¯ ¯ ∂x1 ¯ ¯ ¯ ¯ ∂g1 ¯ ¯ ¯ ¯ ∂x2 ¯ ¯ ¯ ¯ ∂g1 ¯ ¯ ¯ ¯ ∂x3 ¯ ¯ ¯ ¯ ∂g2 ¯ ¯ ¯ ¯ ∂x1 ¯

untuk sebarangx ∈ D,

= 0 1 |x3 || sin x2 x3 | ≤ 3 1 ≤ |x2 || sin x2 x3 | ≤ 3 ≤

= 0

1 sin 1 < 0.281 3 1 sin 1 < 0.281 3

BAB 4. METODA NUMERIS UNTUK SISTEM NONLINIER ¯ ¯ ¯ ∂g2 ¯ ¯ ¯ ¯ ∂x2 ¯ ¯ ¯ ¯ ∂g2 ¯ ¯ ¯ ¯ ∂x3 ¯ ¯ ¯ ¯ ∂g3 ¯ ¯ ¯ ¯ ∂x1 ¯ ¯ ¯ ¯ ∂g3 ¯ ¯ ¯ ¯ ∂x2 ¯ ¯ ¯ ¯ ∂g3 ¯ ¯ ¯ ¯ ∂x3 ¯

57

|x1 | 1 p < √ < 0.119 2 9 0.218 9 x1 + sin x3 + 1.06 | cos x3 | 1 p = < √ < 0.119 2 18 0.218 18 x1 + sin x3 + 1.06 =

= 0 |x2 | −x1 x2 1 e ≤ e < 0.14 20 20 |x1 | −x1 x2 1 = e ≤ e < 0.14. 20 20 =

Karena g1 , g2 , g3 terbatas dalam D maka dengan teorema (4.0.1) gi kontinyu pada D, dengan demikian G kontinyu pada D. Selanjutnya dapat disimpulkan bahwa ¯ ¯ ¯ ∂gi (x) ¯ ¯ ¯ ¯ ∂xj ¯ ≤ 0.281, i = 1, 2, 3, j = 1, 2, 3. Dan akhirnya G mempunyai titik tetap tunggal. k 0 1 2 3 4 5

[k]

x1 0.10000000 0.49998333 0.49999593 0.50000000 0.50000000 0.50000000

[k]

x2 0.10000000 0.00944115 0.00002557 0.00001234 0.00000003 0.00000002

[k]

x3 -0.10000000 -0.52310127 -0.52336331 -0.52359814 -0.52359847 -0.52359877

[k]

[k−1]

en = ||x1 − x1

||∞

0.423 9.4 × 10−3 2.3 × 10−4 1.2 × 10−5 3.1 × 10−7

Kemudian untuk menentukan aproksimasi dari titik tetap p itu, kita pilih x[0] = (0.1, 0.1, −0.1)T , dan kalkulasi berikutnya mengikuti proses iterasi berikut 1 1 [k] [k−1] [k−1] x1 = cos(x2 x3 ) + , 3q 6 ¡ 1 [k−1] [k−1] [k] x1 )2 + sin x3 + 1.06 − 0.1, x2 = 9 [k−1] [k−1] 1 10π − 3 [k] x3 = − e−x1 x2 − . 20 60


58

Hasil selengkapnya dapat dilihat dalam tabel di atas. Kemudian, untuk mempercepat konvergensi proses iterasi dapat dilakukan dengan cara [k]

x1

[k]

x2

[k]

x3

1 1 [k−1] [k−1] cos(x2 x3 ) + , 3q 6 1 ¡ [k] 2 [k−1] = x1 ) + sin x3 + 1.06 − 0.1, 9 [k] [k] 10π − 3 1 = − e−x1 x2 − . 20 60

=

dengan hasil sebagai berikut k 0 1 2 3 4

4.2

[k]

x1 0.10000000 0.49998333 0.49997747 0.50000000 0.50000000

[k]

x2 0.10000000 0.02222979 0.00002815 0.00000004 0.00000000

[k]

x3 -0.10000000 -0.52304613 -0.52359807 -0.52359877 -0.52359877

[k]

[k−1]

en = ||x1 − x1

||∞

0.423 9.4 × 10−2 2.3 × 10−5 1.2 × 10−8

Metoda Newton

Metoda Newton untuk menentukan akar persamaan polinomial dapat ditulis sebagai f (pn−1 ) pn = pn−1 − 0 , untuk n ≥ 1. f (pn−1 ) Bila pn = g(pn−1 ) maka metoda ini dapat disajikan dalam g(pn−1 ) = pn−1 −

f (pn−1 ) , f 0 (pn−1 )

atau g(x) = x −

untuk n ≥ 1.

f (x) . f 0 (x)


59

g(x) = x − φ(x)f (x) untuk φ = 1/f 0 (x). Dan dapat juga ditulis dalam G(x) = x − A(x)−1 F(x), dimana A(x) adalah matrix nonsingular (n × n). Salah satu pilihan terbaik untuk matrik ini adalah matrik Jacobian, yaitu  ∂f (x) ∂f (x)  ∂f1 (x) 1 1 . . . ∂x2 ∂xn 1  ∂f∂x ∂f2 (x) ∂f2 (x)  2 (x)  ∂x1  ... ∂x2 ∂xn J(x) =  .. ..   ..  .  .  . ∂fn (x) ∂x1

∂fn (x) ∂x2

...

∂fn (x) ∂xn

sehingga G(x) = x − J(x)−1 F(x). Selanjutnya iterasi functional yang diawali dengan pemilihan x[0] sebagai nilai awal, dapat disajikan dalam bentuk x[k] = G(x[k−1] ) = x[k−1] − J(x[k−1] )−1 F(x[k−1] )

(4.4)

adalah merupakan formulasi Newton untuk solusi sistem nonlinier. Teorema 4.2.1 Misal p adalah solusi dari G(x) = x dimana G = (g1 , g2 , . . . , gn )T memetakan memetakan Rn kedalam Rn . Jika ditemukan δ > 0 dengan sifat 1. 2.

3.

∂gi ∂xj

kontinyu pada Nδ = {x| ||x − p|| < δ},

¯ 2 (x) ¯ ¯ ≤ M , untuk sebarang konstanta M dan sejuga kontinyu, ¯ ∂∂xgji∂x k barang x ∈ Nδ , ∂ 2 gi (x) ∂xj ∂xk

∂gi (p) ∂xk

= 0, dimana i = 1, 2, . . . , n; j = 1, 2, . . . , n dan k = 1, 2, . . . , n


60

maka terdapat bilangan δˆ ≤ δ sedemikian hingga x[k] = G(x[k−1] ) konvergen terhadap titik tetap tunggal p untuk sebarang nilai awal x[0] sepanjang ˆ Selanjutnya ||x[k] − p||∞ ≤ n2 M ||x[k−1] − p||2 , untuk setiap k ≥ 1 ||x − p|| < δ. ∞ 2 Contoh 4.2.1 Ulangi persoalan (4.1.1), gunakan metoda Newton untuk menentukan aproksimasi terhadap p. Penyelesaian 4.2.1 Sistem persamaan nonlinier itu adalah 1 = 0 2 x21 − 81(x2 + 0.1)2 + sin x3 + 1.06 = 0 10π − 3 e−x1 x2 + 20x3 + = 0. 3 3x1 − cos(x2 x3 ) −

sehingga



 3 x3 sin x2 x3 x2 sin x2 x3   J(x) =  2x1 −162(x2 + 0.1) cos x3  −x2 e−x1 x2 −x1 e−x1x 2 20

dan 

3

 J(x[k−1] ) = 

[k−1]

2x1

[k−1] −x[k−1] x[k−1] 2 1

−x2

e

[k−1]

[k−1] [k−1]

x3 sin x2 x3 [k−1] −162(x2 + 0.1) [k−1] [k−1] x2

−x1 e−x1

[k−1]

x2

[k−1] [k−1]

sin x2 x3 [k−1] cos x3

  .

20

Demikian juga 

 [k−1] [k−1] [k−1] 3x1 − cos(x2 x3 ) − 12  [k−1]  [k−1] [k−1] F(x[k−1] ) =  (x1 )2 − 81(x2 + 0.1)2 + sin x3 + 1.06  . [k−1] [k−1] [k−1] e−x1 x2 + 20x3 + 10π−3 . 3 Selanjutnya lakukan kalkulasi dengan prosedur iterasi newton dengan memilih nilai awal x = (0.1, 0.1, −0.1)T akan diperoleh hasil dalam tabel dibawah ini.


k 0 1 2 3 4 5

[k]

x1 0.10000000 0.49998333 0.49999593 0.50000000 0.50000000 0.50000000

[k]

x2 0.10000000 0.00944115 0.00002557 0.00001234 0.00000003 0.00000002

[k]

x3 -0.10000000 -0.52310127 -0.52336331 -0.52359814 -0.52359847 -0.52359877

[k]

61

[k−1]

en = ||x1 − x1

0.423 9.4 × 10−3 2.3 × 10−4 1.2 × 10−5 3.1 × 10−7

Tabel 4.1: Data hasil eksekusi program iterasi Newton

||∞


62

Latihan Tutorial 4 1. Persamaan nonlinier berikut ini mempunyai dua solusi. −x1 (x1 + 1) + 2x2 = 18 (x1 − 1)2 + (x2 − 6)2 = 25 • Berikan pendekatan grafik terhadap sistem itu. • Tentukan solusi dengan toleransi 1e − 5 dalam l∞ norm 2. Metoda Newton untuk menyelesaikan sistem persamaan nonlinier disajikan dalam rumus berikut x[k] = x[k−1] − J(x[k−1] )−1 F(x[k−1] ) Terapkan teknik ini kedalam sistem persamaan berikut untuk menghitung x[1] {gunakan x[0] = (0.1, 0.1, −0.1)T }. 1 = 0 2 x21 − 81(x2 + 0.1)2 + sin x3 + 1.06 = 0 10π − 3 e−x1 x2 + 20x3 + = 0 3 3x1 − cos(x2 x3 ) −

3. Sistem nonlinier berikut: x21 − 10x1 + x22 + 8 = 0 x1 x22 + x1 − 10x2 + 8 = 0 dapat ditransformasikan dalam titik tetap x21 + x22 + 8 10 x1 x22 + x1 + 8 = g2 (x1 , x2 ) = 10

x1 = g1 (x1 , x2 ) = x2


63

• Gunakan teorema yang tertera dalam buku ini untuk menunjukkan bahwa G = (g1 , g2 )t : D ∈ R2 → R2 mempunyai titik tetap unik dalam D = (x1 , x2 )t |0 ≤ x1 , x2 ≤ 1.5 • Terapkan iterasi fungsional untuk menentukan solusi hampiran dari sistem tersebut. • Apakah metoda Seidel dapat mempercepat tingkat konvergensinya. 4. Gunakan metoda Newton untuk menentukan solusi hampiran dari persamaan nonlinier berikut ini. x21 + x2 − 37 = 0 x1 − x22 − 5 = 0 x1 + x2 + x 3 − 3 = 0 x21 + 2x22 − x2 − 2x3 = 0 x21 − 8x22 + 10x3 = 0 x21 −1 = 0 7x2 x3 {gunakan x[0] = (0.1, 0.1, 0)T }

BAB 5 Metoda Numeris Untuk Masalah Nilai Awal Gerak harmonis pendulum (bandul), sebagaimana digambarkan dibawah ini, menunjukkan masalah nilai awal dengan PD order 2. d2 θ g + sin θ = 0 dt2 L θ0 (t0 ) = θ00

θ(t0 ) = θ0 , Dapat juga ditulis sebagai

d2 θ dt2

+ Lg θ = 0, bila θ sangat kecil sekali.

L θ

Dalam hal ini L adalah panjang tali pendulum, g gravitasi bumi dan θ sudut antara pendulum dengan posisi setimbang. Selanjutnya solusi analitik terhadap 64

BAB 5. METODA NUMERIS UNTUK MASALAH NILAI AWAL

65

persamaan difrensial ini tidak efektif dilakukan, mengingat persamaan itu tidak linier. Dengan demikian metoda numeris sangat dibutuhkan. Persamaan difrensial biasa order pertama dapat disajikan dalam bentuk berikut dy = f (x, y) atau y 0 = f (x, y). dx

(5.1)

Solusi dari persamaan ini adalah y(x) yang memenuhi persamaan y 0 (x) = f (, y(x)) di semua titik pada interval domain [a, b]. Selanjutnya persamaan (5.1) dikatakan merupakan masalah nilai awal bila solusi itu memenuhi nilai awal y(a) = y0 , sehingga persamaan itu dapat digambarkan sebagai y 0 = f (x, y),

a≤x≤b

y(a) = y0 . Kemudian bila persamaan ini terdiri dari lebih dari satu persamaan yang sa-ling terkait maka dikatagorikan sebagai sistem persamaan difrensial. Sistem persamaan difrensial order pertama disajikan sebagai berikut. y10 = f1 (t, y1 , y2 , . . . , yn ) y20 = f2 (t, y1 , y2 , . . . , yn ) .. . yn0 = fn (t, y1 , y2 , . . . , yn ). Atau dalam bentuk umum dapat disajikan sebagai yi0 = fi (t, y1 , y2 , . . . , yn ) i = 1, 2, . . . , n dan a ≤ t ≤ b.

(5.2)

dengan nilai awal y1 (a) = α1 , y1 (a) = α2 , . . . , y1 (a) = αn . Metoda numeris pada umumnya diterapkan dalam menyelesaikan sistem persamaan difrensial order satu ini. Sehingga bila fenomena yang dihadapi adalah sistem persamaan difrensial order n maka haruslah ditransformasikan terlebih dahulu kedalam sistem persamaan difrensial order satu.


66

Contoh 5.0.2 Transformasikan sistem persamaan difrensial dibawah ini dalam sistem persamaan difrensial order satu. u000 + u00 v 0 = xv u v0 + v + = cos x 1+x dimana u(0) = −1, u0 (0) = 1, u00 (0) = 1, v(0) = 1 Penyelesaian 5.0.2 Misal y1 = u, y2 = u0 , y3 = u00 dan y4 = v, maka y10 = u0 = y2 , y20 = u00 = y3 , y30 = u000 = xy4 − y3 (cos x − y4 − y40 = v 0 = cos x − y4 −

y1 . 1+x

y1 ), 1+x

Nilai awal seakarang adalah y1 (0) = −1, y2 (0) = 1, y3 (0) = 1, y4 (0) = 1.

5.1

Teori Dasar

Sebelum menyelesaikan suatu model persamaan difrensial terlebih dahulu harus diselidiki apakah persamaan itu mempunyai solusi (existence) atau tidak dan bila solusi itu ada apakah solusi itu tunggal (uniqueness) atau trivial. Pertanyaan ini merupakan hal yang sangat penting untuk didahulukan mengingat betapa kompleknya suatu model fenomena riel yang banyak dimungkinkan tidak dapat diselesaikan dengan metoda analitik ataupun kualitatif. Definisi 5.1.1 (Sarat Lipschitz) Suatu fungsi f (t, y) dikatakan memenuhi sarat Lipschitz dalam variabel y di suatu domain D ∈ R2 jika ada konstanta L > 0 sedemikian hingga ||f (t, y1 ) − f (t, y2 )|| ≤ L||y1 − y2 ||


67

untuk sebarang (t, y1 ), (t, y2 ) ∈ D. Selanjutnya konstanta L disebut sebagai konstanta Lipschitz. Definisi 5.1.2 (Konvek) Suatu himpunan D ∈ R2 dikatakn konvek bila untuk sebarang (t, y1 ), (t, y2 ) ∈ D maka titik ((1−λ)t1 +λt2 , (1−λ)y1 +λy2 ) juga merupakan elemen dari D untuk λ ∈ [0, 1]. Secara geometris dapat digambarkan sebagai berikut

(t , y ) 1

1

(t , y ) 1

(t , y ) 2

1

(t 2 , y 2)

2

Tidak Konvek

Konvek

Gambar 5.1: Diagram kekonvekan untuk D ∈ R2

Teorema 5.1.1 Andaikata f (t, y) terdefinisi dalam himpunan konvek D ∈ R2 dan ada konstanta L > 0 dimana ¯¯ ¯¯ ¯¯ df ¯¯ ¯¯ (t, y)¯¯ ≤ L, untuk semua (t, y) ∈ D, (5.3) ¯¯ dy ¯¯ maka f memenuhi suatu sarat Lipschitz. Teorema 5.1.2 Misal D = {(t, y)|a ≤ t ≤ b, −∞ ≤ y ≤ ∞} dan f (t, y) adalah fungsi kontinyu dalam D, kemudian bila f memenuhi sarat Lipschitz dalam variabel y maka masalah nilai awal y 0 (t) = f (t, y),

a ≤ t ≤ b y(a) = α

mempunyai solusi tunggal y(t) untuk a ≤ t ≤ b.

BAB 5. METODA NUMERIS UNTUK MASALAH NILAI AWAL Contoh 5.1.1 y 0 = 1 + t sin(ty), 0 ≤ t ≤ 2, persamaan ini mempunyai solusi tunggal.

68

y(0) = 0. Tentukan apakah

Penyelesaian 5.1.1 f (t, y) = 1 + t sin(ty), kemudian terapkan teorema nilai ratarata pada buku ”Analisa Numerik I” yaitu untuk sebarang y1 < y2 , maka ada bilangan ξ ∈ (y1 , y2 ) sedmikian hingga f (t, y2 ) − f (t, y1 ) ∂ = f (t, ξ) = t2 cos(tξ). y2 − y1 ∂y Kemudian f (t, y2 ) − f (t, y1 ) = (y2 − y1 )t2 cos(tξ) ||f (t, y2 ) − f (t, y1 )|| = ||(y2 − y1 )t2 cos(tξ)|| ≤ ||y2 − y1 || ||t2 cos(tξ)|| ≤ ||y2 − y1 || || max t2 cos(tξ)|| 0≤t≤2

= 4||y2 − y1 ||. Degan demikian sarat Lipschitz terpenuhi yaitu ||f (t, y1 ) − f (t, y2 )|| ≤ L||y1 − y2 ||, dimana konstanta Lipschitznya adalah L = 4, berarti persamaan itu mempunyai solusi tunggal.

5.2

Beberapa Metoda Numeris

Ada beberapa metoda numeris yang dapat digunakan dalam menyelesaikan masalah nilai awal. Metoda-metoda ini dikembangkan dan dikaji berdasarkan


69

ekspansi deret Taylor. f (x) ≈ pn (x) + Rn+1 (x) (x − x0 ) 0 (x − x0 )n (n) pn (x) = f (x0 ) + f (x0 ) + · · · + f (x0 ) 1! n! Z 1 x Rn+1 (x) = (x − t)n f (n+1) (t)dt n! x0 (x − x0 )n+1 (n+1) = f (ξ) (n + 1)!

(5.4) (5.5) (5.6) (5.7)

untuk ξ antara x0 dan x. Selanjutnya kita mulai dengan masalah y 0 = f (x, y),

a ≤ x ≤ b,

y(a) = y0

(5.8)

Solusi numeris terhadap masalah ini diperoleh dengan membagi doain itu [a, b] kedalam grid yakni xi = a + ih;

i = 0, 1, . . . , n;

h = (b − a)/n.

Dengan demikian x0 = a, dan xn = b, sedangkan h disebut besarnya grid (stepsize). Solusi numerisnya adalah himpunan dari nilai grid y0 = y(x0 = a), y1 , y2 , . . . , yn

(5.9)

Nilai-nilai ini dihitung secara berurutan kemudian hasilnya dipakai sebagai aproksimasi terhadap solusi eksak y(x) sedemikian hingga yn ≈ y(xn ),

5.2.1

n = 0, 1, 2, . . . , n.

Metoda Euler

Deret Taylor secara umum adalah f (x) ≈ f (x0 ) +

(x − x0 ) 0 (x − x0 )2 (2) f (x0 ) + f (x0 ) + . . . . 1! 2!


70

Bila x = x1 maka y(x1 ) = y(x0 ) +

(x1 − x0 ) 0 (x1 − x0 )2 00 y (x0 ) + y (x0 ) + . . . , 1! 2!

sedangkan x1 − x0 = h sehingga secara berurutan disetiap grid dirumuskan (xn+1 − xn ) 0 (xn+1 − xn )2 00 y (xn ) + y (xn ) + . . . 1! 2! h h2 00 h3 000 y(xn+1 ) = y(xn ) + y 0 (xn ) + y (xn ) + y (xn ) + . . . 1! 2! 3! y(xn+1 ) = y(xn ) +

Formulasi Euler memandang bahwa suku-suku setelah suku kedua dapat dipenggal 2 3 n (truncation) mengingat h2! , h3! , . . . , hn! akan mendekati nol, sebagai gantinya kita hitung h 0 y (xn ) 1! = yn + hf (xn , yn )

y(xn+1 ) = y(xn ) + yn+1

(5.10)

secara berulang. Rumus ini kemudian disebut dengan Metoda Euler. Definisi 5.2.1 (Kesalahan global) Kesalahan global didefinisikan sebagai en := y(xn ) − yn Definisi 5.2.2 (Konvergen) Suatu metoda dikatakan konvergen bila max ||y(xi ) − yi || → 0

0≤i≤n

untuk

h→0

Definisi 5.2.3 (Kesalahan Pemenggalan Lokal) Kesalahan pemenggalan lokal adalah kesalahan yang ditimbulkan oleh perumusan suatu metoda dalam bentuk ln := y(xn+k ) − yn+k . Definisi 5.2.4 (Order) Suatu metoda dikatakan berorder p bila ln := O(hp+1 ). Definisi 5.2.5 (Konsisten) Suatu metoda dikatakan konsisten bila ordernya minimal satu.


71

Dapat dibuktikan bahwa metoda Euler adalah berorder satu, hal ini dapat ditelusuri dengan menentukan kesalahan pemenggalan lokal dari metoda tersebut, dengan memperluas rumusan Taylor xn = x0 + nh xn+1 = x0 + (n + 1)h yn+1 ≈ y(xn+1 )

(5.11)

h 0 y (xn ) + 1! h y(xn−1 ) = y(xn ) − y 0 (xn ) + 1! y(xn+1 ) = y(xn ) +

2

3

h 00 h y (xn ) + y 000 (xn ) + . . . 2! 3! 2 h 00 h3 000 y (xn ) − y (xn ) + . . . 2! 3!

(5.12) (5.13) (5.14)

Sehingga kesalahan pemenggalan lokal adalah ln := y(xn+1 ) − yn+1 = (y(xn ) + h2 0 y (xn ) + . . . 2! := O(h1+1 ).

h 0 h2 y (xn ) + y 00 (xn ) + . . . ) − y(xn ) − hy 0 (xn ) 1! 2!

ln := ln

Kemudian suatu metoda harus teruji keakurasiannya dengan meneliti apakah kesalahan yang ditimbulkan dalam perhitungan semakin mengecil pada setiap iterasi (konvergen) artinya untuk h → 0 maka kesalahan global en dari Euler harus mendekati 0. Selanjutnya bila suatu metoda memiliki sifat ini dikatakan bahwa metoda itu memenuhi prinsip dasar (principal property) yang harus dipenuhi. Teorema 5.2.1 Disebarang titik grid xn dalam [a, b] kesalahan global dari metoda Euler memenuhi sifat ||en || ≤

hM2 (b−a)L (e − 1), 2L

dimana L adalah konstanta Lipschitz dan ||y 00 (x)|| ≤ M2 ,

a ≤ x ≤ b.

(5.15)


72

Proof. Solusi numeris metoda Euler yn+1 = yn + hf (xn , yn ), dan ekpansi Taylor h 0 h2 y (xn ) + y 00 (ηn ), xn ≤ ηn ≤ xn+1 . 1! 2! Suku terakhir dari deret ini merupakan ekspresi dari kesalahan pemenggalan lokal. Kurangkan kedua rumus itu dan gunakan terorema sarat Lipschitz diperoleh y(xn+1 ) = y(xn ) +

||en+1 || ≤ ||en ||(1 + hL) +

h2 M2 2

Selanjutnya gunakan fakta bahwa ||e0 || = 0, ||e1 || ≤ 2 hL) h2 M2 , sehingga

h2 M2 2

dan ||e2 || ≤ (1 +

h2 ||en || ≤ M2 (1 + (1 + hL) + · · · + (1 + hL)n−1 ). 2 Dengan menggunakan rumus jumlah deret geometri, didapat (1 + hL)n − 1 h2 M2 2 (1 + hL) − 1 2 h (1 + hL)n − 1 = M2 2 hL h = M2 ((1 + hL)n − 1) 2L Kita memahami bahwa untuk h, L > 0 berlaku ||en || ≤

(1 + hL)n ≤ enhL sedang xn = x0 + (n)h atau h =

xn −x0 n

sehingga

enhL = e(xn −x0 )L ≤ e(b−a)L sehingga ||en || ≤

h M2 (e(b−a)L − 1) 2L

Jelas disini lim ||en || = 0.

h→0

Dengan demikian dikatakan bahwa metoda Euler adalah konvergen. 2


73

Contoh 5.2.1 Gunakan metoda Euler untuk menyelesaikan persamaan difrensial berikut ( dy = f (t, y) = y − t 0 ≤ t ≤ 1 dt y(0) = 0.5 Penyelesaian 5.2.1 Solusi analitik dari persamaan ini adalah y(t) = t + 1 − 0.5et . Selanjutnya dengan menetapkan h = 0.1 dapat dihitung solusi numeris sebagai berikut. n = 0 → t0 = 0 dan y0 = 0.5; y1 = y0 + hf (x0 , y0 ) = 0.5 + 0.1f (0, 0.5) = 0.5500 n = 1 → t1 = 0 + 1 ∗ 0.1 dan y1 = 0.5500; y2 = y1 + hf (x1 , y1 ) = 0.5500 + 0.1f (0.1, 0.5500) = 0.5950, dan seterusnya. Lakukan dengan cara yang sama sehingga diperoleh tabel berikut ini tn 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

yn 0.5000 0.5500 0.5950 0.6345 0.6679 0.6947 0.7142 0.7256 0.7282 0.7210 0.7031

y(tn ) 0.5000 0.5474 0.5893 0.6251 0.6541 0.6756 0.6889 0.6931 0.6872 0.6702 0.6409

en 0.0000 0.0026 0.0057 0.0094 0.0138 0.0191 0.0253 0.0325 0.0410 0.0508 0.0622


74

Dalam visualisasi grafis kedua solusi itu dapat dibandingkan sebagai berikut 0.75

0.7

0.65

0.6

__ : Solusi numeris y_n 0.55

0.5 0

oo : Solusi analitik y(x)

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Gambar 5.2: Metoda Euler dalam grafik

5.2.2

Metoda Runge-Kutta

Metoda Euler adalah metoda yang cukup lama dikenal, namun demikian keakurasian metoda ini masih perlu dipertimbangkan untuk kategori persoalan yang sedekit lebih komplek. Metoda ini hanya bekerja dengan baik pada awal-awal interval domain selanjutnya diujung akhir interval domain biasanya me-ngalami osilasi yang cukup besar (perhatikan gambar 5.2). Untuk meningkatkan keakurasian metoda ini diperlukan proses bertahap dengan mengasumsikan suatu estimasi awal yˆn+1 , kemudian tentukan nilai dari turunan di ujung grid xn de-ngan menghitung f (xn+1 , yˆn+1 ). Selanjutnya selesaikan langkah berikutnya dengan menggunakan rumus rata-rata dua gradien, yang diberikan berikut ini yˆn+1 = yn + hf (xn , yn ) h yn+1 = yn + (f (xn , yn ) + f (xn+1 , yˆn+1 )) 2 Teknik seperti ini lebih akurat daripada metoda Euler.


75

Metoda Runge Kutta mengadobsi teknik diatas dengan representasi sebagai berikut k1 = f (xn , yn ) k2 = f (xn + c2 h, yn + ha21 k1 ) yn+1 = yn + h(k1 + k2 ). Selanjutnya secara umum dapat disajikan dalam bentuk k1 = f (xn , yn ) ki = f (xn + ci h, yn + h

i−1 X

aij kj ),

i = 1, 2, . . . , m

j

yn+1 = yn + h

m X

b i ki .

(5.16)

i=1

Dengan istilah lain metoda ini terkenal dengan nama metoda Ekpslisit Runge Kutta, dan dapat direpresentasikan dalam bentuk tabel berikut 0 c2 c3 .. . cm

dimana ci = bentuk

Pm j=1

aij dan

a21 a31 .. .

a32 .. .

..

am1 b1

am2 b2

... ...

Pm

i=1 bi

. amm−1 bm−1

bm

= 1. Dengan kata lain dapatlah disajikan dalam

c

A bT


0 1

76

1 1 2

1 2

Sebagai contoh metoda Runge-Kutta dua tahap adalah Dengan demikian dapatlah diuraikan k1 = f (x0 , y0 ) k2 = f (x0 + h, y0 + hk1 ) 1 yn+1 = yn + h(k1 + k2 ). 2

(5.17)

Kondisi dari Order Runge-Kutta Order dari metoda Runge-Kutta ditunjukkan dengan jumlah tahap dari metoda tersebut. Contoh diatas adalah metoda Runge-Kutta dua tahap, berarti order dari metoda itu adalah 2. Selanjutnya setiap order metode ini menunjukkan kondisi yang berbeda dari hubungan antara elemen matrik A, vektor c dan b. Teorema 5.2.2 Metoda Runge-Kutta dua tahap yang sekaligus berorder 2 mempunyai sifat sebagai berikut: a21 = c2 b1 + b2 = 1 1 b2 c2 = 2 Proof. Persamaan difrensial adalah y 0 = f (x, y),

y(x0 ) = y0 .


77

Gunakan aturan Chain yakni untuk turunan partial y 00 = fx + fy y 0 = fx + fy f y

000

2

= fxx + 2fxy f + fyy f + fy (fx + fy f ) ∂ ∂ f (x + m, y + n) = f (x, y) + (m + n )f ∂x ∂y 1 ∂ ∂ 2 + (m + n ) f + ... 2 ∂x ∂y

(5.18) (5.19)

(5.20)

Sekarang ingat ekspansi Taylor h 0 h2 h3 y (xn ) + y 00 (xn ) + y 000 (xn ) + . . . 1! 2! 3! 3 2 h h y(x1 ) = y(x0 ) + hy 0 (x0 ) + y 00 (x0 ) + y 000 (x0 ) + . . . 2 6

y(xn+1 ) = y(xn ) +

(5.21)

Perluas k1 dan k2 k2 = f (x0 + c2 h, y0 + ha21 f ) = f (x0 , y0 ) + h(c2 fx + a21 f fy )(x0 , y0 ) h2 2 (c fxx + 2c2 a21 f fxy + a221 f 2 fyy )(x0 , y0 ) + . . . 2 2 Kemudian substitusikan k1 dan k2 kedalam (5.17) dengan mempertimbangkan nilai awal y(x0 ) = y0 . y1 = y0 + h(b1 + b2 )f (x0 , y0 ) + h2 b2 (c2 fx + a21 f fy )(x0 , y0 ) h3 + b2 (c22 fxx + 2c2 a21 f fxy + a221 f 2 fyy )(x0 , y0 ) + . . . 2 y1 ≈ y(x0 ) + h(b1 + b2 )y 0 (x0 ) + h2 b2 (c2 fx + a21 f fy )(x0 , y0 ) h3 + b2 (c22 fxx + 2c2 a21 f fxy + a221 f 2 fyy )(x0 , y0 ) + . . . 2

(5.22)

Suatu metoda dikatakan berorder p bila ln := O(hp+1 ). Dengan demikian untuk order 2 dalam metoda ini, selisih persamaan (5.21) dan (5.22) atau kesalahan pemenggalan lokal l0 = y(x1 ) − y1 = O(h2+1 ), lihat definisi (5.2.3). Artinya sukusuku dari l0 sebelum O(h2+1 ) harus dinolkan. Untuk memenuhi ini maka tidak ada


78

jalan lain pada persamaan (5.22) harus mempunyai sifat a21 = c2 b1 + b2 = 1 1 b2 c2 = 2

2

Sifat kekonvergenan dari metoda ini dapat dianalisa dengan membuktikan teorema berikut ini. Teorema 5.2.3 Disebarang titik grid xn dalam [a, b] kesalahan global dari metoda Runge-Kutta berorder p memenuhi sifat ||en || ≤

hp Mp+1 (b−a)Lˆ (e − 1), ˆ CL

(5.23)

ˆ adalah konstanta Lipschitz. dimana L Buktikan dengan cara yang tidak jauh berbeda dengan pembuktian kekonvergenan pada metoda Euler, dan bila benar maka lim ||en || = 0,

h→0

sehingga metoda Runge-Kutta adalah metoda yang konvergen. Contoh 5.2.2 Gunakan metoda Runge-Kutta order 2 untuk menyelesaikan persamaan yang tertera dalam contoh (5.1.1) Penyelesaian 5.2.2 Dengan memanfaatkan rumus yang diberikan pada (5.17) didapat tabel solusi numeris sebagai berikut.


tn 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0

yn 0.5000 0.5475 0.5895 0.6254 0.6546 0.6763 0.6898 0.6942 0.6886 0.6719 0.6429

y(tn ) 0.5000 0.5474 0.5893 0.6251 0.6541 0.6756 0.6889 0.6931 0.6872 0.6702 0.6409

79

en 0.0000 0.0001 0.0002 0.0003 0.0005 0.0007 0.0009 0.0011 0.0014 0.0017 0.0020

Tabel 5.1: Data hasil eksekusi program metoda Runge-Kutta Dalam grafik dapat digambarkan sebagai berikut Bila kita bandingkan dengan gambar 5.2 maka metoda Runge-Kutta jelas memberikan perbedaan yang segnifikan. Solusi dari metoda ini, yn , menginterpolasi y(xn ) dengan akurat diseluruh interval domain. Berbeda dengan metoda Euler yang akurasinya hanya ditunjukkan pada awal interval domain. Dengan demikian interpolasi oleh hasil metoda ini tidak mengalami osilasi.

5.2.3

Metoda Multistep Linier (MML)

Metoda ini berada dalam satu kelas dengan metoda Runge-Kutta. Dalam arti tingkat keakurasiannya sama-sama berada diatas level metoda Euler. Sedangkan perbandingan dengan metoda Runge-Kutta sendiri tidak dapat dibandingkan, hal ini tergantung kepada kompleknya persoalan.


80

0.7 0.68 0.66 0.64 0.62 0.6 0.58 __ : Solusi numeris

0.56

oo : Solusi analitik 0.54 0.52 0.5 0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Gambar 5.3: Metoda Runge-Kutta order 2 Secara umum metoda multistep didefinisikan sebagai berikut k X i=0

αi yn+i = h

k X

βi fn+i .

(5.24)

i=0

Bila βk = 0 maka metoda ini dikatakan multistep eksplisit dan jika tidak disebut implisit. Selanjutnya metoda ini dapat dispesifikasikan kedalam dua bentuk polinomial, yang dinotasikan dengan ρ dan σ. ρ(s) = αk sk + αk−1 sk−1 + · · · + α0

(ruas kiri)

dan σ(s) = βk sk + βk−1 sk−1 + · · · + β0

(ruas kanan)

Dengan demikian untuk metoda Euler, dapatlah disajikan dalam bentuk (ρ, σ) ≡ (s − 1, 1), yang kemudian disebut metoda satu step.


81

Kondisi dari Order MML Definisi 5.2.6 (Kesalahan pemenggalan lokal) Kesalahan pemenggalan lokal untuk MML didefinisikan sebagai berikut ln = =

k X

αi y(xn+i ) − h

k X

i=0

i=0

k X

k X

i=0

αi y(xn+i ) − h

βi f (xn+i , y(xn+i )) βi y 0 (xn+i ).

(5.25)

i=0

Rumus ini tidak berbeda dengan denifisi (5.2.3), dengan demikian sesuai dengan konsep ekspansi Taylor dapatlah ditulis h (ih)2 00 (ih)3 000 y(xn+i ) = y(xn ) + i y 0 (xn ) + y (xn ) + y (xn ) + . . . 1! 2! 3! (ih)2 000 (ih)3 0000 h y (xn ) + y (xn ) + . . . y 0 (xn+i ) = y 0 (xn ) + i y 00 (xn ) + 1! 2! 3! maka ln

¶ (ih)2 00 (ih)3 000 h 0 = αi y(xn ) + i y (xn ) + y (xn ) + y (xn ) + . . . 1! 2! 3! i=0 µ ¶ k X h 00 (ih)2 000 (ih)3 0000 0 −h βi y (xn ) + i y (xn ) + y (xn ) + y (xn ) + . . . 1! 2! 3! i=0 k X

µ

Kelompokkan semua suku yang mempunyai order h yang sama sehingga diperoleh ln = C0 y(xn ) + C1 hy 0 (xn ) + C2

h2 00 y (xn ) + . . . 2!


82

dimana C0 = αk + αk−1 + · · · + α0 , k k X X C1 = iαi − βi , C2 =

i=0 k X

i=0 2

i αi − 2

i=0

k X

iβi ,

i=0

.. . Cq =

k X i=0

iq αi − q

k X

iq−1 βi ,

q = 2, 3, . . . , p, p + 1, . . . , s.

i=0

Kemudian suatu metoda dikatakan berorder p bila C0 = C1 = · · · = Cp = 0,

sedang Cp+1 6= 0

Contoh 5.2.3 Buktikan bahwa MML berikut ini konsisten dalam order 3. yn+2 + 4yn+1 − 5yn = h(4fn+1 + 2fn ) Penyelesaian 5.2.3 Gunakan sifat-sifat (5.11),(5.12) dan (5.13) sehingga didapat ln = yn+2 + 4yn+1 − 5yn − 4hfn+1 + 2hfn ≈ y(xn+2 ) + 4y(xn+1 ) − 5y(xn ) − 4hy 0 (xn+1 ) − 2hy 0 (xn ) Sederhanakan kedalam y(xn+1 ) ¶ µ h2 00 h3 000 h4 0000 h 0 ln = y(xn+1 ) + y (xn+1 ) + y (xn+1 ) + y (xn+1 ) + y (xn+1 ) + . . . 1! 2! 3! 4! µ 2 h h h3 +4y(xn+1 ) − 5 y(xn+1 ) − y 0 (xn+1 ) + y 00 (xn+1 ) − y 000 (xn+1 ) 1! 2! 3! ¶ µ 4 h h h2 + y 0000 (xn+1 ) + . . . − 4hy 0 (xn+1 ) − 2h y 0 (xn+1 ) − y 00 (xn+1 ) + y 000 (xn+1 ) 4! 1! 2! ¶ 3 h − y 0000 (xn+1 ) + . . . 3!


83

Dengan mengelompokkan suku-suku yang sama diperoleh h ln = 4 y 0000 (xn+1 ) + . . . 4! h 0000 = y (xn+1 ) + · · · = O(h3+1 ) 6 Sehingga terbukti bahwa MML diatas adalah order 3. Tidak dapat dipastikan bahwa bila suatu metoda konsisten akan secara otomatis metoda itu konvergen. Oleh karena itu kita membutuhkan sarat lain yaitu nol-stabil Definisi 5.2.7 (Nol-stabil) Suatu metoda dikatakan memiliki sifat nol-stabil atau memenuhi kondisi akar bila akar dari ρ(s) = 0 memenuhi sifat |sn | ≤ 1. Bila semua sn = 1 maka metoda itu dikatakan sangat stabil. Teorema 5.2.4 Bila MML memenuhi sifat konsisten dan sekaligus nol-stabil maka metoda itu dikatakan konvergen. konsisten + nol-stabil ⇔ konvergen Teorema 5.2.5 Order maksimum dari MML k-step adalah 2k untuk implisit dan 2k − 1 untuk eksplisit. Kemudian MML implisit k-step dengan order p yang mempunyai sifat nol-stabil akan memenuhi sifat p ≤ k + 2 untuk k genap dan p ≤ k + 1 untuk k ganjil, sedangkan MML eksplisit k-step memenuhi sifat p ≤ k. Berikut ini beberapa contoh MML yang banyak dipakai 1. MML eksplisit (a) yn+1 = yn + hfn ,

order 1, dan MML 1-step

(b) yn+2 = yn+1 + h2 (3fn+1 − fn ), (c) yn+3 = yn+2 +

h (23fn+2 12


− 16fn+1 + 5fn ),



84

2. MML implisit (a) yn+1 = yn + h2 (fn+1 + fn ), h (5fn+2 12

(b) yn+2 = yn+1 + (c) yn+3 = yn+2 + 3-step


+ 8fn+1 − fn ),

h (9fn+3 24


+ 19fn+2 − 5fn+1 + fn ),

order 4, dan MML

Contoh 5.2.4 Buktikan bahwa beberapa contoh MML eksplisit maupun implisit diatas memenuhi sifat konsistensi dan nol stabil.

5.3

Kesimpulan

Ada beberapa kesimpulan yang dapat dirangkum dalam modul ini, diantaranya adalah: • Bentuk umum sistem PDB order pertama adalah yi0 = fi (t, y1 , y2 , . . . , yn ) i = 1, 2, . . . , n dan a ≤ t ≤ b.

(5.26)

dengan nilai awal y1 (a) = α1 , y1 (a) = α2 , . . . , y1 (a) = αn . • Misal D = {(t, y)|a ≤ t ≤ b, −∞ ≤ y ≤ ∞} dan f (t, y) adalah fungsi kontinyu dalam D, kemudian bila f memenuhi sarat Lipschitz dalam variabel y, yaitu ||f (t, y1 ) − f (t, y2 )|| ≤ L||y1 − y2 || untuk sebarang (t, y1 ), (t, y2 ) ∈ D dan konstanta L > 0, maka y 0 (t) = f (t, y),

a ≤ t ≤ b y(a) = α

mempunyai solusi tunggal y(t) untuk a ≤ t ≤ b. • Beberapa metoda numeris yang dapat dipakai untuk menyelesaikan PDB dengan masalah nilai awal adalah


85

1. Metoda Euler h 0 y (xn ) 1! = yn + hf (xn , yn )

y(xn+1 ) = y(xn ) + yn+1

(5.27)

2. Metoda Runge-Kutta k1 = f (xn , yn ) ki = f (xn + ci h, yn + h

i−1 X

aij kj ),

i = 1, 2, . . . , m

j

yn+1 = yn + h

m X

b i ki .

(5.28)

i=1

3. Metoda Multistep k X i=0

αi yn+i = h

k X

βi fn+i .

(5.29)

i=0

Bila βk = 0 maka metoda ini dikatakan multistep eksplisit dan jika tidak disebut implisit.


86

Latihan Tutorial 5 1. Suatu sistem PD yang disajikan dalam persamaan berikut z 00 + 2w0 = y + ew , z 0 + sin y 0 + w = 1 + t2 , w0 + y cos t − z 00 = 0, dengan nilai awal z(0) = 1, z 0 (0) = 1, y(0) = 1, w(0) = −20, dapat diselesaikan dengan mudah dalam numerik bila ditransformasikan terlebih dahulu kedalam sistem PD order satu, laku-kan transformasi itu. Kemudian untuk meyakinkan sistem itu dapat mempunyai solusi tunggal terlebih dahulu harus dicek dengan teorema Lipschitz. Sebagai gambaran periksa mana diantara soal berikut ini yang memenuhi teorema Lipschitz: (a) f (t, y) = y cos t,

0 ≤ t ≤ 1,

y(0) = 1

(b) f (t, y) = 1 + t sin y,

0 ≤ t ≤ 2,

y(0) = 0

(c) f (t, y) = 2t y + t2 e2 ,

1 ≤ t ≤ 2,

y(1) = 0

(d) f (t, y) =

4t3 y 1+t4

,

0 ≤ t ≤ 1,

y(0) = 1

dan tentukan besar konstanta Lipschitz dari masing-masing soal ini. p 2. Perhatikan PDB y 0 = −y 2 dan y 0 = |y|. Buktikan bahwa kedua PDB itu tidak memenuhi syarat Lipschitz pada selang interval 0 ≤ x ≤ 1, −∞ ≤ y ≤ ∞, dan pada sebarang nilai awal y(0) = y0 tunjukkan bahwa persamaan pertama tidak mempunyai solusi pada 0 ≤ x ≤ 1. Kemudian Buktikan bahwa persamaan kedua tidak mempunyai solusi tunggal untuk y(0) = 0. 3. Ada beberapa metoda yang dapat dipakai untuk menyelesaikan sistem PD diatas diantaranya dengan metoda yang sederhana dari Euler yn+1 = yn + hf (t, y). Sebagai metoda teknik Euler ini harus memenuhi sifat prinsip kekonvergenan, sekarang tunjukkan apakah metoda ini merupakan metoda yang konvergen (gunakan teorema Lipschitz). Kemudian terapkan metoda ini dalam sistem persamaan order pertama soal no. 1 untuk menghitung y1 .


87

4. Berikan penjelasan lengkap bagaimana metoda Runge-Kutta diformulasikan. Dan Buktikan bahwa metoda Runge-Kutta dua tahap (Runge-Kutta order 2) mempunyai sifat sebagai berikut: a21 = c2 b1 + b2 = 1 1 b2 c2 = 2 5. Perbincangan kekonvergenan dapat ditempuh dengan memahami teorema konsistensi dan nol-stabil. Sebutkan bunyi kedua teorema tadi dan telusuri apakah metoda MML dibawah ini konsisten atau nol-stabil. 1 3 yn+3 + yn+2 − 3yn+1 + yn = 3hf (tn+2 , yn+2 ) 2 2 P P Sebenarnya dengan rumus ki=0 αi yn+i = h ki=0 βi fn+i kita dapat menentukan sendiri koefisien dari metoda ini terlepas dari metoda yang diperoleh itu konvergen atau tidak. Coba gunakan α2 = 1 dan β2 = 0, dan tentukan MML eksplisit step 3 ini, kemudian beri komentar tentang kekonvergenanya.

Daftar Pustaka [1] R. L. Burden and J. D. Faires. Numerical Analysis. Brooks/Cole Publishing Company, 1997. [2] N. J. Higham. Accuracy and Stability of Numerical Algorithms. SIAM Books, Philadelphia, 1996. [3] J. Penny and G. Lindfield. Numerical Methods Using Matlab. Ellis Horwood Limited, 1995. [4] M.J.D. Powell. Approximation Theory and Methods. Cambridge University Press, 1981. [5] G. Strang. Linear Algebra and its Applications. Academic Press, 1988. [6] R. S. Varga. Matrix Iterative Analysis. Prentice-Hall, Inc, Englewood Cliffs, New Jersey, 1962.

88

1.1 Definisi dan Teorema Dalam Kalkulus Representasi bilangan dalam komputer Algoritma Software Komputer

Recommend Documents