Learning Never Ends

Wednesday, March 29, 2017

Metode Pencarian Akar

A. METODE TERTUTUP

A.1. Metode Bagi-Dua

Metode Bagi-Dua adalah algoritma pencarian akar pada sebuah interval. Interval tersebut membagi dua bagian, lalu memilih dari dua bagian ini dipilih bagian mana yang mengandung akar dan bagian yang tidak mengandung akar dibuang. Hal ini dilakukan berulang-ulang hingga diperoleh akar persamaan atau mendekati akar persamaan. Metode ini berlaku ketika ingin memecahkan persamaan f(x) = 0 dengan f merupakan fungsi kontinyu.

Prosedur Metode Bagi-Dua :

Misal dijamin bahwa f(x) adalah fungsi kontinyu pada interval [a, b] dan f(a)f(b) < 0. Ini artinya bahwa f(x) paling tidak harus memiliki akar pada interval [a, b]. Kemudian definisikan titik tengah pada interval [a, b] yaitu c := $\frac{a+b}{2}$ . Dari sini kita memperoleh dua subinterval yaitu [a, c] dan [c, b]. Setelah itu, cek apakah f(a)f(c) < 0 atau f(b)f(c) < 0 ? Jika f(a)f(c) < 0 maka b = c (artinya titik b digantikan oleh titik c yang berfungsi sebagai titik b pada iterasi berikutnya), jika tidak maka a = c. Dari iterasi pertama kita memperoleh interval [a, b] yang baru dan titik tengah c yang baru. Kemudian lakukan pengecekan lagi seperti sebelumnya sampai memperoleh error yang cukup kecil.

Contoh :

Carilah akar dari x³ + 4x² – 10 = 0 pada interval [1, 2].

Penyelesaian :

Dalam penyelesaian ini saya akan menggunakan sampai iterasi ke-10 dan menggunakan 5 angka dibelakang koma.

f(x) = x³ + 4x² – 10

f(1) = (1)³ + 4(1)² – 10 = -5

f(2) = (2)³ + 4(2)² – 10 = 14

f(1.5) = (1.5)³ + 4(1.5)² – 10 = 2.375

f(1.25) = (1.25)³ + 4(1.25)² – 10 = -1.79687

f(1.375) = (1.375)³ + 4(1.375)² – 10 = 0.16210

f(1.3125) = (1.3125)³ + 4(1.3125)² – 10 = -0.84838

f(1.34375) = (1.34375)³ + 4(1.34375)² – 10 = -0.35098

f(1.35938) = (1.35938)³ + 4(1.35938)² – 10 = -0.09632

f(1.36719) = (1.36719)³ + 4(1.36719)² – 10 = 0.03239

f(1.36329) = (1.36329)³ + 4(1.36329)² – 10 = -0.03200

f(1.36524) = (1.36524)³ + 4(1.36524)² – 10 = 0.000016

f(1.36426) = (1.36426)³ + 4(1.36426)² – 10 = -0.01601

f(1.36329) = (1.36329)³ + 4(1.36329)² – 10 = -0.00784

n	a	B	c = (a + b)/2	f(a)	f(b)	f(c)	f(a)f(c)	f(b)f(c)
1 2 3 4 5 6 7 8 9 10	1 1 1.25 1.25 1.3125 1.34375 1.35938 1.35938 1.36329 1.36329	2 1.5 1.5 1.375 1.375 1.375 1.375 1.36719 1.36719 1.36524	1.5 1.25 1.375 1.3125 1.34375 1.35938 1.36719 1.36329 1.36524 1.36426	– – – – – – – – – –	+ + + + + + + + + +	+ – + – – – + – + –	– + – + + + – + – +	+ – + – – – + – + –

Jadi akar yang diperoleh dari f(x) = x³ + 4x² – 10 menggunakan 10 iterasi adalah 1.36426

A.2. METODE REGULA FALSI

Metode Regular Falsi adalah panduan konsep dimulai dengan pemilihan dua titik awal x₀ dan x₁ sedemikian sehingga f(x₀) dan f(x₁) berlawanan tanda atau f(x₀)f(x₁) < 0. Kemudian menarik garis l dari titik f(x₀) dan f(x₁) sedemikian sehingga garis l berpotongan pada sumbu – x dan memotong kurva / grafik fungsi pada titik f(x₀) dan f(x₁). Sehingga Metode Regular Falsi ini akan menghasilkan titik potong pada sumbu-x yaitu x₂ yang merupakan calon akar dan tetap berada dalam interval [x₀, x₁]. Metode ini kemudian berlanjut dengan menghasilkan berturut-turut interval [x_n-1, x_n] yang semuanya berisi akar f.

Prosedur Metode Regular Falsi

Menentukan interval titik awal x₀ dan x₁ sedemikian sehingga f(x₀)f(x₁)<0.
Setelah itu menghitung x₂ = x₁ – $\frac{f(x_1)[x_1-x_0]}{f(x_1)-f(x_0)}$ . Kemudian periksa apakah f(x₀)f(x₂) < 0 atau f(x₁)f(x₂) < 0, jika f(x₀)f(x₂) < 0 maka x₀ = x₀atau x₂ = x₁, jika tidak maka x₁ = x₁atau x₂ = x₀. Kemudian ulangi terus langkah-langkah tersebut sampai ketemu ‘akar’ yang paling mendekati ‘akar yang sebenarnya’ atau mempunyai error yang cukup kecil.

Secara umum, rumus untuk Metode Regular Falsi ini adalah sebagai berikut

x_n+1 = x_n – $\frac{f(x_n)[x_n-x_{n-1}]}{f(x_n)-f(x_{n-1})}$

Untuk mendapatkan rumus tersebut, perhatikan gambar diatas.

syarat : f(x₀)f(x₁) < 0

pandang garis l yang melalui (x₀, f(x₀)) dan (x₁, f(x₁)) sebagai gradien garis, sehingga diperoleh persamaan gradient sebagai berikut

$\frac{f(x_1)-f(x_0)}{x_1-x_0}$ = $\frac{f(x_1)-y}{x_1-x_2}$

karena x₂ merupakan titik potong pada sumbu – x maka f(x₂) = 0 = y, sehingga diperoleh

$\frac{f(x_1)-f(x_0)}{x_1-x_0}$ = $\frac{f(x_1)-0}{x_1-x_2}$

x₁ – x₂ = $\frac{f(x_1)[x_1-x_0]}{f(x_1)-f(x_0)}$

x₂ = x₁ – $\frac{f(x_1)(x_1-x_0)}{f(x_1)-f(x_0)}$

atau jika ditulis secara umum menjadi

x_n+1 = x_n – $\frac{f(x_n)[x_n-x_{n-1}]}{f(x_n)-f(x_{n-1})}$

Contoh :

Tentukan akar dari 4x³ – 15x² + 17x – 6 = 0 menggunakan Metode Regular Falsi sampai 9 iterasi.

Penyelesaian :

f(x) = 4x³ – 15x² + 17x – 6

iterasi 1 :

ambil x₀ = -1 dan x₁ = 3

f(-1) = 4(-1)³ – 15(-1)² + 17(-1) – 6 = -42

f(3) = 4(3)³ – 15(3)² + 17(3) – 6 = 18

x₂ = (3) – $\frac{(18)[3-(-1)]}{18-(-42)}$ = 1.8

f(1.8) = 4(1.8)³ – 15(1.8)² + 17(1.8) – 6 = -0.672

f(3) f(1.8) < 0 maka ambil x₀ = x₂ = 1.8 dan x₁ = 3

iterasi 2 :

x₂ = (3) – $\frac{(18)[3-1.8]}{18-(-0.672)}$ = 1.84319

f(1.84319) = 4(1.84319)³ – 15(1.84319)² + 17(1.84319) – 6 = -0.57817

f(3) f(1.84319) < 0 maka ambil x₀ = x₂ = 1.84319 dan x₁ = 3

iterasi 3 :

x₂ = (3) – $\frac{(18)[3-1.84319]}{18-(-0.57817)}$ = 1.87919

f(1.87919) = 4(1.87919)³ – 15(1.87919)² + 17(1.87919) – 6 = -0.47975

f(3) f(1.87919) < 0 maka ambil x₀ = x₂ = 1.87919 dan x₁ = 3

iterasi 4 :

x₂ = (3) – $\frac{(18)[3-1.84319]}{18-(-0.47975)}$ = 1.90829

f(1.90829) = 4(1.90829)³ – 15(1.90829)² + 17(1.90829) – 6 = -0.38595

f(3) f(1.90829) < 0 maka ambil x₀ = x₂ = 1.90829 dan x₁ = 3

iterasi 5 :

x₂ = (3) – $\frac{(18)[3-1.90829]}{18-(-0.38595)}$ = 1.93120

f(1.93120) = 4(1.93120)³ – 15(1.93120)² + 17(1.93120) – 6 = -0.30269

f(3) f(1.93120) < 0 maka ambil x₀ = x₂ = 1.93120 dan x₁ = 3

iterasi 6 :

x₂ = (3) – $\frac{(18)[3-1.93120]}{18-(-0.30269)}$ = 1.94888

f(1.94888) = 4(1.94888)³ – 15(1.94888)² + 17(1.94888) – 6 = -0.23262

f(3) f(1.94888) < 0 maka ambil x₀ = x₂ = 1.94888 dan x₁ = 3

iterasi 7 :

x₂ = (3) – $\frac{(18)[3-1.94888]}{18-(-0.23262)}$ = 1.96229

f(1.96229) = 4(1.96229)³ – 15(1.96229)² + 17(1.96229) – 6 = -0.17597

f(3) f(1.96229) < 0 maka ambil x₀ = x₂ = 1.96229 dan x₁ = 3

iterasi 8 :

x₂ = (3) – $\frac{(18)[3-1.96229]}{18-(-0.17597)}$ = 1.97234

f(1.97234) = 4(1.97234)³ – 15(1.97234)² + 17(1.97234) – 6 = -0.13152

f(3) f(1.97234) < 0 maka ambil x₀ = x₂ = 1.97234 dan x₁ = 3

iterasi 9 :

x₂ = (3) – $\frac{(18)[3-1.97234]}{18-(-0.13152)}$ = 1.97979

n	x₀	x₁	x₁	f(x₀)	f(x₁)	f(x₂)
1 2 3 4 5 6 7 8 9	-1 1.8 1.84319 1.87919 1.90829 1.93120 1.94888 1.96229 1.97234	3 3 3 3 3 3 3 3 3	1.8 1.84319 1.87919 1.90829 1.93120 1.94888 1.96229 1.97234 1.97979	-42 -0.672 -0.57817 -0.47975 -0.38595 -0.30269 -0.23262 -0.17597 -0.13152	18 18 18 18 18 18 18 18 18	-0.672 -0.57817 -0.47975 -0.38595 -0.30269 -0.23262 -0.17597 -0.13152 -0.09741

Jadi akar dari persamaan 4x³ – 15x² + 17x – 6 = 0 menggunakan Metode Regular Falsi adalah 1.97979

A. METODE TERBUKA

B.1. Metode Titik Tetap

Metode Titik Tetap adalah suatu metode pencarian akar suatu fungsi f(x) secara sederhana dengan menggunakan satu titik awal. Perlu diketahui bahwa fungsi f(x) yang ingin dicari hampiran akarnya harus konvergen. Misal x adalah Fixed Point (Titik Tetap) fungsi f(x) bila g(x) = x dan f(x) = 0.

Teorema :

Diketahui g(x) fungsi kontinu dan {X_n} adalah barisan yang terbetuk oleh Fixed Point Iteration, maka

Jika $Lim_{n \to \infty}$ X_n = x maka x adalah Fixed Point fungsi g(x).

Sumber gambar : karlcalculus

Prosedur Metode Titik Tetap

Misal f(x) adalah fungsi yang konvergen dengan f(x) = 0, maka untuk mencari nilai akarnya atau hampiran akarnya kita terlebih dahulu mengubah kedalam bentuk x = g(x). Kemudian tentukan nilai titik awal, misal x₁. Setelah itu disubstitusikan titik awalnya ke persamaan g(x) sedemikian sehingga g(x₁) = x₂, setelah itu titik x₂ yang diperoleh substitusikan lagi ke g(x) sedemikian sehingga g(x₂) = x₃. Jadi apabila ditulis iterasinya akan menjadi

x₁ (penetuan titik awal)

x₂= g(x₁) (iterasi pertama)

x₃= g(x₂) (iterasi kedua)

x_n= g(x_n-1) (iterasi ke-n)

Iterasi ini akan berhenti jika x = g(x) dan f(x) = 0 atau sudah mencapai nilai error yang cukup kecil (|x_n– x_n-1| < $\varepsilon$ ).

Contoh :

Selesaikan persamaan x – e^-x = 0 dengan menggunakan Fixed Point dengan 10 iterasi atau sampai dua angka dibelakang koma tidak berubah.

Penyelesaian :

f(x) = x – e^-x

ubah terlebih dahulu kedalam bentuk x = g(x), sehingga diperoleh x = e^-x

misal kita ambil titik awalnya x₁ = 0.5, maka iterasinya adalah x_n+1 = e^-x_{n} akan diperoleh

x₁ = 0.5 (penetuan titik awal)

f(x₁) = 0.5 – e^-0.5 = -0.1065

x₂= g(x₁) = e^-0.5 = 0.6065 (iterasi pertama)

f(x₁) = 0.6065 – e^-0.6065 = 0.0612

x₃= g(x₂) = e^-0.6065 = 0.5452 (iterasi ke-2)

f(x₁) = 0.5452 – e^-0.5452 = -0.0345

x₄= g(x₃) = e^-0.5452 = 0.5797 (iterasi ke-3)

f(x₁) = 0.5797 – e^-0.5797 = 0.0196

x₉= g(x₈) e^-0.5664 = 0.5675 (iterasi ke-9)

f(x₁) = 0.5 – e^-0.5 = -0.1065

x₁₀= g(x₉) e^-0.5675 = 0.5669 (iterasi ke-10)

f(x₁) = 0.5 – e^-0.5 = -0.1065

sehingga apabila ditulis dalam bentuk table akan diperoleh

n	x_n	g(x_n-1)	f(x_n)
1 2 3 4 5 6 7 8 9 10	0.5 0.6065 0.5452 0.5797 0.5600 0.5712 0.5648 0.5684 0.5664 0.5675	0.6065 0.5452 0.5797 0.5600 0.5712 0.5648 0.5684 0.5664 0.5675 0.5669	-0.1065 0.0612 -0.0345 0.0196 -0.0112 0.0006 -0.0003 0.00019 -0.00011 0.00005

Jadi hampiran akar yang diperoleh menggunakan Fixed Point adalah 0.5675

Contoh 2 :

Hitunglah hampiran akar dari persamaan x² – 2x – 3 = 0 pada interval [1, 4] menggunakan Fixed Point.

Penyelesaian :

Misal persamaan x² – 2x – 3 = 0 diubah menjadi x(x – 2) – 3 = 0 sehingga diperoleh x = $\frac{3}{x-2}$ dan iterasinya menjadi x_n+1 = $\frac{3}{x_n-2}$ . ambil titik awal x₁ = 4.

Sehingga apabila ditulis dalam tabel diperoleh :

n	x_n	g(x_n-1)	f(x_n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19	4 1.5 -6 -0.375 -1.2631 -0.9193 -1.0276 -0.9908 -1.003 -0.999 -1.00033 -0.9989 -1.00036 -0.99988 -1.00004 -0.99998 -1.00001 -0.99999 -1.00000	1.5 -6 -0.375 -1.2631 -0.9193 -1.0276 -0.9908 -1.003 -0.999 -1.00033 -0.9989 -1.00036 -0.99988 -1.00004 -0.99998 -1.00001 -0.99999 -1.00000 -1.00000	5 -3.75 45 -2.1093 1.1216 -0.3162 0.1111 -0.0367 0.012 -0.00039 0.00013 -0.00043 0.00014 -0.00004 0.000016 -0.000008 0.00004 -0.000004 0

Jadi akar dari f(x) = x² – 2x – 3 = 0 adalah -1

Sekarang bagaimana jika fungsi pada Contoh 2 kita ubah menjadi x = $\frac{x^3+1}{3}$ ? Berapa nilai akarnya? Pada kasus ini jika menggunakan Fixed Point maka kita tidak akan menemukan hampiran akarnya karena fungsi tersebut divergen. Bagaimana cara kita bisa menentukan bahwa fungsi tersebut divergen atau konvergen? Perhatikan teorema dibawah ini.

Teorema :

Diketahui g kontinu pada [a, b] dan paling sedikit memiliki satu akar pada [a, b] jika |g'(x)| $\leq$ M < 1, $\forall$ x $\epsilon$ [a, b] maka iterasi x_n+1 = g(x_n) dengan x_i $\epsilon$ [a, b] menghasilkan barisan {X_n} konvergen yaitu $Lim_{n \to \infty}$ x_n = L $\Leftrightarrow$ {X_n} $\rightarrow$ 0

x = $\frac{x^3+1}{3}$ = g(x)

g'(x) = 3x², dimana 3x² $\geq$ 0, maka menurut Teorema diatas g(x) divergen.

INGAT : dalam Fixed Point, g(x) harus konvergen. Jika divergen, maka tidak bisa dilakukan perhitungan akar menggunakan Fixed Point ini

B.2. METODE NEWTON RAPHSON

Metode Newton-Raphson adalah metode pencarian akar suatu fungsi f(x) dengan pendekatan satu titik, dimana fungsi f(x) mempunyai turunan. Metode ini dianggap lebih mudah dari Metode Bagi-Dua (Bisection Method) karena metode ini menggunakan pendekatan satu titik sebagai titik awal. Semakin dekat titik awal yang kita pilih dengan akar sebenarnya, maka semakin cepat konvergen ke akarnya.

Prosedur Metode Newton :

menentukan x₀ sebagai titik awal, kemudian menarik garis lurus (misal garis l) yang menyinggung titik f(x₀). Hal ini berakibat garis l memotong sumbu – x di titik x₁. Setelah itu diulangi langkah sebelumnya tapi sekarang x₁ dianggap sebagai titik awalnya. Dari mengulang langkah-langkah sebelumnya akan mendapatkan x₂, x₃, … x_n dengan x_n yang diperoleh adalah bilangan riil yang merupakan akar atau mendekati akar yang sebenarnya.

Perhatikan gambar diatas untuk menurunkan rumus Metode Newton-Raphson

persamaan garis l : y – y₀ = m(x – x₀)

y – f(x₀) = f'(x₀)(x – x₀)

x₁ adalah perpotongan garis l dengan sumbu – x

0 – f(x₀) = f'(x₀)(x₁ – x₀)

y = 0 dan x = x₁ maka koordinat titik (x₁, 0)

– $\frac{f(x_{0})}{f'(x_{0})}$ = (x₁ – x₀)

x₁ = x₀ – $\frac{f(x_{0})}{f'(x_{0})}$

x₂ = x₁ – $\frac{f(x_{1})}{f'(x_{1})}$

x_n = x_n-1– $\frac{f(x_{n-1})}{f'(x_{n-1})}$ untuk n = 1, 2, 3, …

Contoh :

Tentukan akar dari persamaan 4x³ – 15x² + 17x – 6 = 0 menggunakan Metode Newton-Raphson.

Penyelesaian :

f(x) = 4x³ – 15x² + 17x – 6

f’(x) = 12x² – 30x + 17

iterasi 1 :

ambil titik awal x₀ = 3

f(3) = 4(3)³ – 15(3)² + 17(3) – 6 = 18

f’(3) = 12(3)² – 30(3) + 17 = 35

x₁ = 3 – $\frac{18}{35}$ = 2.48571

iterasi 2 :

f(2.48571) = 4(2.48571)³ – 15(2.48571)² + 17(2.48571) – 6 = 5.01019

f’(2.48571) = 12(2.48571)² – 30(2.48571) + 17 = 16.57388

x₂ = 2.48571 – $\frac{5.01019}{16.57388}$ = 2.18342

iterasi 3 :

f(2.18342) = 4(2.18342)³ – 15(2.18342)² + 17(2.18342) – 6 = 1.24457

f’(2.18342) = 12(2.18342)² – 30(2.18342) + 17 = 8.70527

x₃ = 2.18342 – $\frac{1.24457}{8.70527}$ = 2.04045

iterasi 4 :

f(2.04045) = 4(2.04045)³ – 15(2.04045)² + 17(2.04045) – 6 = 0.21726

f’(2.04045) = 12(2.04045)² – 30(2.04045) + 17 = 5.74778

x₄ = 2.04045 – $\frac{0.21726}{5.74778}$ = 2.00265

iterasi 5 :

f(3) = 4(2.00265)³ – 15(2.00265)² + 17(2.00265) – 6 = 0.01334

f’(2.00265) = 12(2.00265)² – 30(2.00265) + 17 = 5.04787

x₅ = 2.00265 – $\frac{0.01334}{5.04787}$ = 2.00001

iterasi 6 :

f(2.00001) = 4(2.00001)³ – 15(2.00001)² + 17(2.00001) – 6 = 0.00006

f’(2.00001) = 12(2.00001)² – 30(2.00001) + 17 = 5.00023

x₆ = 2.00001 – $\frac{0.00006}{5.00023}$ = 2.00000

iterasi 7 :

f(2) = 4(2)³ – 15(2)² + 17(2) – 6 = 0

jika disajikan dalam tabel, maka seperti tabel dibawah ini.

n	x_n	f(x_n)	f'(x_n)
0 1 2 3 4 5 6	3 2.48571 2.18342 2.04045 2.00265 2.00001 2.00000	18 5.01019 1.24457 0.21726 0.01334 0.00006 0.00000	35 16.57388 8.70527 5.74778 5.04787 5.00023 5.00000

karena pada iteasi ketujuh f(x₆) = 0 maka akar dari persamaan tersebut adalah x = 2.

B.3. METODE SECANT

Pada Metode Newton-Raphson memerlukan syarat wajib yaitu fungsi f(x) harus memiliki turunan f'(x). Sehingga syarat wajib ini dianggap sulit karena tidak semua fungsi bisa dengan mudah mencari turunannya. Oleh karena itu muncul ide dari yaitu mencari persamaan yang ekivalen dengan rumus turunan fungsi. Ide ini lebih dikenal dengan nama Metode Secant. Ide dari metode ini yaitu menggunakan gradien garis yang melalui titik (x₀, f(x₀)) dan (x₁, f(x₁)). Perhatikan gambar dibawah ini.

Persamaan garis l adalah

$\frac{x-x_1}{x_0-x_1}$ = $\frac{y-f(x_1)}{f(x_0)-f(x_1)}$

Karena x = x₂ maka y = 0, sehingga diperoleh

$\frac{x_2-x_1}{x_0-x_1}$ = $\frac{0-f(x_1)}{f(x_0)-f(x_1)}$

x₂ – x₁ = $-\frac{f(x_1)[x_0-x_1]}{f(x_0)-f(x_1)}$

x₂ = x₁ – $\frac{f(x_1)[x_0-x_1]}{f(x_0)-f(x_1)}$

= x₁ – $\frac{f(x_1)[x_1-x_0]}{f(x_1)-f(x_0)}$

secara umum rumus Metode Secant ini ditulis

x_n+1 = x_n – $\frac{f(x_n)[x_n-x_{n-1}]}{f(x_n)-f(x_{n-1})}$

Prosedur Metode Secant :

Ambil dua titik awal, misal x₀ dan x₁. Ingat bahwa pengambilan titik awal tidak disyaratkan alias pengambilan secara sebarang. Setelah itu hitung x₂ menggunakan rumus diatas. Kemudian pada iterasi selanjutnya ambil x₁ dan x₂ sebagai titik awal dan hitung x₃. Kemudian ambil x₂ dan x₃ sebagai titik awal dan hitung x₄. Begitu seterusnya sampai iterasi yang diingankan atau sampai mencapai error yang cukup kecil.

Contoh :

Tentukan salah satu akar dari 4x³ – 15x² + 17x – 6 = 0 menggunakan Metode Secant sampai 9 iterasi.

Penyelesaian :

f(x) = 4x³ – 15x² + 17x – 6

iterasi 1 :

ambil x₀ = -1 dan x₁ = 3 (ngambil titik awal ini sebarang saja, tidak ada syarat apapun)

f(-1) = 4(-1)³ – 15(-1)² + 17(-1) – 6 = -42

f(3) = 4(3)³ – 15(3)² + 17(3) – 6 = 18

x₂ = (3) – $\frac{(18)[3-(-1)]}{18-(-42)}$ = 1.8

iterasi 2 :

ambil x₁ = 3 dan x₂ = 1.8

f(1.8) = 4(1.8)³ – 15(1.8)² + 17(1.8) – 6 = -0.672

x₃ = (1.8) – $\frac{(-0.672)[1.8-(3)]}{-0.672-18}$ = 1.84319

iterasi 3 :

ambil x₂ = 1.8 dan x₃ = 1.84319

f(1.84319) = 4(1.84319)³ – 15(1.84319)² + 17(1.84319) – 6 = -0.57817

x₄ = (1.84319) – $\frac{(-0.57817)[1.84319-1.8]}{-0.57817-(0.672)}$ = 2.10932

iterasi 4 :

ambil x₃ = 1.84319 dan x₄ = 2.10932

f(2.10932) = 4(2.10932)³ – 15(2.10932)² + 17(2.10932) – 6 = 0.65939

x₅ = (2.10932) – $\frac{(0.65939)[2.10932-1.84319]}{0.65939-(-0.57817)}$ = 1.96752

iterasi 5 :

ambil x₄ = 2.10932 dan x₅ = 1.96752

f(1.96752) = 4(1.96752)³ – 15(1.96752)² + 17(1.96752) – 6 = -0.15303

x₆ = (1.96752) – $\frac{(-0.15303)[1.96752-2.10932]}{-0.15303-0.65939)}$ = 1.99423

iterasi 6 :

ambil x₅ = 1.96752 dan x₆ = 1.99423

f(1.99423) = 4(1.99423)³ – 15(1.99423)² + 17(1.99423) – 6 = -0.02854

x₇ = (1.99423) – $\frac{(-0.02854)[1.99423-1.96752]}{-0.02854-(-0.15303)}$ = 2.00036

iterasi 7 :

ambil x₆ = 1.99423 dan x₇ = 2.00036

f(2.00036) = 4(2.00036)³ – 15(2.00036)² + 17(2.00036) – 6 = 0.00178

x₈ = (2.00036) – $\frac{(0.00178)[2.00036-1.99423]}{0.00178-(-0.02854)}$ = 2.00000

iterasi 8 :

ambil x₇ = 2.00036 dan x₈ = 1.999996

f(1.999996) = 4(1.999996)³ – 15(1.999996)² + 17(1.999996) – 6 = -0.0002

x₉ = (1.999996) – $\frac{(-0.0002)[1.999996-2.00036]}{-0.0002-0.00178}$ = 2.0000

iterasi 9 :

ambil x₈ = 1.999996 dan x₉ = 2.00000

f(2.00000) = 4(2.00000)³ – 15(2.00000)² + 17(2.00000) – 6 = 0.00000

x₁₀ = (2.00000) – $\frac{(0.00000)[2.00000-1.999996]}{0.00000-(-0.00002)}$ = 0.00000

n	x_n-1	x_n	x_n+1	f(x_n-1)	f(x_n)	f(x_n+1)
1 2 3 4 5 6 7 8 9	-1 3 1.8 1.84319 2.10932 1.96752 1.99423 2.00036 2.00000	3 1.8 1.84319 2.10932 1.96752 1.99423 2.00036 2.00000 2.00000	1.8 1.84319 2.10932 1.96752 1.99423 2.00036 2.00000 2.00000 2.00000	-42 18 -0.672 -0.57817 0.659 39 -0.15303 -0.02854 0.00178 -0.00002	18 -0.672 -0.57817 0.65939 -0.15303 -0.02854 0.00178 -0.00002 0.00000	-0.672 -0.57817 0.65939 -0.15303 -0.02854 0.00178 -0.00002 0.00000 0.00000

Jadi salah satu akar dari 4x³ – 15x² + 17x – 6 = 0 adalah 2

Wednesday, March 22, 2017

DERET TAYLOR dan ANALISA GALAT

2.1        Definisi Deret Taylor
Andaikan f dan semua turunannya, f’, f’’, f’’’, …., menerus di dalam selang [a, b]. Misalkan xₒ ϵ [a, b], maka untuk nilai-nilai xₒ dan x ϵ [a, b], f(x) dapat diperluas (diekspansi) ke dalam deret taylor:

          Persamaan di atas merupakan penjumlahan dari suku-suku (term) yang disebut deret. Untuk memudahkan penulisan suku-suku selanjutnya kita menggunakan tanda ellipsis (…). Jika dimisalkan x – xₒ = h, maka f(x) dapat juga ditulis sebagai

Contoh:
Hampiri fungsi f(x) = sin(x) ke dalam deret Taylor di sekitar xₒ = 1.
Penyelesaian:
Kita harus menentukan turunan sin(x) terlebih dahulu sebagai berikut
f(x) = sin(x)
f’(x) = cos(x)
f’’(x) = -sin(x)
f’’’(x) = -cos(x)
f⁽⁴⁾(x) = sin(x),
dan seterusnya.
Maka,

Bila dimisalkan x – 1 = h, maka

= 0.8415 + 0.5403h + 0.4208h²+ 0.0901h³ + 0.0351h⁴ + …
Kasus khusus adalah bila fungsi diperluas di sekitar xₒ = 0, maka deretnya dinamakan deret Maclaurin, yang merupakan deret Taylor baku.
          Deret Taylor yang dipotong sampai suku orde ke-n dinamakan deret Taylor terpotong dan dinyatakan oleh:

Yang dalam hal ini,
                              , xₒ < c < x
Disebut galat atau sisa (residu).
Dengan demikian deret Taylor yang dipotong sampai suku orde k-n dapat ditulis sebagai
f(x) = P_n(x) + R_n(x)
yang dalam hal ini,

Contoh:
Sin(x) jika dihampiri dengan deret Taylor orde 4 di sekitar xₒ = 1 adalah:

Yang dalam hal ini,
                  , 1 < c < x
Deret Taylor terpotong di sekitar xₒ = 0 disebut deret Maclaurin terpotong
Contoh:
Hitunglah hampiran nilai cos(0.2), sudut dinyatakan dalam radian, dengan deret Maclaurin sampai suku orde n = 6.
Penyelesaian:
Cos(0.2) 1 – 0.2²/2 + 0.2⁴/24 – 0.2⁶/720 = 0.9800667
(sampai tujuh angka di belakang koma)
2.2     Analisis Galat
          Galat berasosiasi dengan seberapa dekat solusi hampiran terhadap solusi sejatinya.semakin kecil galatnya, semakin teliti solusi numerik yang didapatkan.
Misalkan â adalah nilai hampiran terhadap nilai sejati a, maka selisih
ε = a – â
disebut galat. Sebagai contoh, jika â = 10.5 adalah nilai hampiran dari a = 10.45, maka galatnya adalah ε = -0.01. Jika tanda galat (positif atau negatif) tidak dipertimbangkan, maka galat mutlak didefinisikan sebagai
ǀεǀ =ǀa – âǀ
Untuk mengatasi interpretasi nilai galat, maka galat harus dinormalkan terhadap nilai sejatinya. Sehingga dinamakan galat relatif.
Galat relatif didefinisikan sebagai

Atau dalam persentase

Karena galat dinormalkan terhadap nilai sejati, maka galat relatif tersebut dinamakan juga galat relatif sejati.
Dalam praktek kita tidak mengetahui nilai sejati a, karena itu galat ε seringkali dinormalkan terhadap solusi hampirannya, sehingga galat relatifnya dinamakan galat relatif hampiran.

Contoh:
Misalkan nilai sejati = 10/3 dan nilai hampiran = 3.333. Hitunglah galat, galat mutlak, galat relatif, dan galat relatif hampiran.
Penyelesaian:
Galat = 10/3 – 3.333 = 10/3 – 3333/1000 = 1/3000 = 0.000333…
Galat mutlak = ǀ0.000333…ǀ = 0.000333…
Galat relatif = (1/3000)/(10/3) = 1/1000 = 0.0001
Galat relatif hampiran = (1/3000)/3.333 = 1/9999
2.3        Sumber Utama Galat Numerik
Secara umum terdapat dua sumber utama penyebab galat dalam
perhitungan numerik:

Galat pemotongan (truncation error)
Galat pembulatan (round-off error)

Selain kedua galat ini, masih ada sumber galat lain, antara lain:

Galat eksperimental
Galat pemrograman

2.3.1   Galat Pemotongan
Galat pemotongan mengacu pada galat yang ditimbulkan akibat
Penggunaan hampiran sebagai pengganti formula eksak. Tipe galat pemotongan bergantung pada metode komputasi yang digunakan untuk penghampiran sehingga kadang-kadang ia disebut juga galat metode. Misalnya, turunan pertama fungsi f di x, dihampiri dengan formula

Yang dalam hal ini h adalah lebar absis x_i+1dengan x_i.
Untuk mencari nilai maksimum yang mungkin dari ǀ R_nǀ dalam selang yang diberikan , yaitu:

Contoh:
Gunakan deret Taylor orde 4 di sekitar xₒ = 1 untuk menghampiri ln(0.9) dan berikan taksiran untuk galat pemtongan maksimum yang dibuat.
Penyelesaian:
Tentukan turunan fungsi f(x) = ln(x) terlabih dahulu
f(x) = ln(x)                      f(1)=0
f’(x) = 1/x                        f’(1)=1
f’’(x) = -1/x²f’’(1)=-1
f’’’(x) = 2/x³f’’’(1)=2
f⁽⁴⁾(x) = -6/x⁴f⁽⁴⁾(1)=-6
f⁽⁵⁾(x) = 24/x⁵                   f⁽⁵⁾(c)=24/c⁵
Deret Taylornya adalah
ln(x) = (x-1) – (x-1)²/2 + (x-1)³/3 – (x-1)⁴/4 + R₄(x)
dan
ln(0.9) = -0.1 – (-0.1)²/2 + (-0.1)³/3 – (-0.1)⁴/4 + R₄(x) = -0.105358 + R₄(x)
juga

Dan nilai Max |24/c⁵| di dalam selang 0.9 < c < 1 adalah pada c = 0.9 (dengan mendasari pada fakta bahwa pada suatu pecahan nilainya semakin membesar bilamana penyebut dibuat lebih kecil). Sehingga

Jadi ln(0.9) = -0.1053583 dengan galat pemotongan lebih kecil dari 0.0000034.
Deret Taylor dapat digunakan unuk menghitung integral fungsi yang sulit diintegralkan secara analitik (bahkan adakalanya tidak dapat dihitung secara analitik).
Contoh: Hitunglah hampiran nilai secara numerik, yaitu fungsi dihampiri dengan deret Maclaurin orde 8.
Penyelesaian:
Deret Maclaurin orde 8 dalam fungsi adalah

Dengan demikian, maka

2.3.2   Galat Pembulatan
Perhitungan dengan metode numerik hampir selalu menggunakan bilangan riil. Semua bilangan riil tidak dapat disajikan secara tepat di dalam komputer, sehingga keterbatasan komputer dalam menyajikan bilangan riil yang menghasilkan galat disebut galat pembulatan. Misalnya sebuah komputer hanya dapat merepresentasikan bilangan riil dalam 6 digit angka, maka representasi bilangan 1/6 = 0.1666666666… di dalam komputer 6-digit tersebut adalah 0.166667.
Kebanyakan komputer digital mempunyai dua buah cara penyajian bilangan riil, yaitu bilangan titik-tetap (fixed point) dan bilangan titik-kambang (floating point). Dalam format bilangan titik-tetap setiap bilangan disajikan dengan jumlah tempat desimal yang tetap, misalnya 62.358, 0.013, 1.000. sedangkan dalm format bilangan titik-kambang setiap bilangan disajikan dengan jumlah digit berarti yang sudah tetap, misalnya
0.6238 x 10³                              0.1714 x 10^-13
Atau ditulis juga
0.6238E+03                              0.1714E-13
Digit berarti di dalam format bilangan titik-kambang disebut juga angka bena (significant figure).
Contohnya:
43.123                   memiliki 5 angka bena (yaitu 4,3,1,2,3)
0.0000012             memiliki 2 angka bena (yaitu 1,2)
270.0090               memiliki 7 angka bena (yaitu 2,7,0,0,0,9,0)
2.3.3. Galat Total
          Galat akhir atau galat total atau pada solusi numerik merupakan jumlah galat pemotongan dan galat pembulatan. Misalnya menggunakan deret Maclaurin orde-4 untuk menghampiri cos(0.2) sebagai berikut:
Cos(0.2) ≈ 1 – 0.2²/2 + 0.2⁴/24 ≈ 0.9800667

                             Galat                                    Galat
                          Pemotongan                 Pembulatan
2.4        Orde Penghampiran
Di dalam metode numerik, fungsi f(x) sering diganti dengan fungsi hampiran yang lebih sederhana. Satu cara mengungkapkan ketelitian penghampiran ini adalah dengan menggunakan notasi O-Besar (Big-Oh).
Contoh:
e^h = 1 + h + h²/2! + h³/3! + h⁴/4! + O(h⁵)
ln(x+1) = x – x²/2 + x³/3 – x⁴/4 + x⁵/4 + O(h⁵)
Sin(h) = h – h³/3! + h⁵/5! + O(h⁷) (bukan O(h⁶), karena suku orde 6 = 0)
Cos(h)=1–h²/4!+h⁴/6!–h⁶/6!+O(h⁸) (bukan O(h⁷), karena suku orde 7=0)
2.5        Bilangan Titik-Kambang
Bilangan riil di dalam computer umumnya disajikan dalam format bilangan titik-kambang. Bilangan titik-kambang ditulis sebagai
a = ± m x B^p = ± 0.d₁d₂d₃d₄d₅d₆ …d_n x B^p
yang dalam hal ini,
m = mantisa (riil). d₁d₂d₃d₄d₅d₆ …d_n adalah digit atau bit mantisa yang
       nilainya dari 0 sampai B – 1, n adalah panjang digit (bit) mantisa.
B = basis sistem bilangan yang dipakai (2, 8, 10, 16, dan sebagainya)
P = pangkat (berupa bilangan bulat), nilainya dari –p_min sampai +p_maks
Sebagai contoh, bilangan riil 245.7654 dinyatakan sebagai 0.2457654 x 10³ dalam format bilangan titik kambang dengan basis 10.
2.5.1 Bilangan Titik-Kambang Ternormalisasi
Bilangan titik-kambang juga dapat dituliskan sebagai
a = ± (mb) x
Misalnya, 245.7654 dapat ditulis sebagai
0.2457654 X atau
2.457654 X atau
0.02457654 X , dan sebagainya
Agar bilangan titik-kambang dapat disajikan secara seragam, kebanyakan sistem komputer menormalisasikan formatnya sehingga semua digit mantisa selalu angka bena. Karena alasan itu, maka digit pertama mantisa tidak boleh nol.
2.5.2 Epsilon Mesin
Satu ukuran yang penting dalam aritmetika komputer adalah seberapa kecil perbedaan antara dua buah nilai yang dapat dikenali oleh komputer. Ukuran yang digunakan untuk membedakan suatu bilangan riil dengan bilangan riil berikutnya adalah epsilon mesin. Epsilon mesin distandarisasi dengan menemukan bilangan titik-kambang terkecil yang bila ditambahkan dengan 1 memberikan hasil yang lebih besar dari 1. Dengan kata lain, jika epsilon mesin dilambangkan dengan maka
1+
(bilangan yang lebih kecil dari epsilon mesin didefinisikan sebagai nol dalam komputer).
2.5.3 Pembulatan pada Bilangan Titik-Kambang
Ada dua teknik pembulatan yang lazim dipakai oleh komputer, yaitu pemenggalan (chopping ) dan pembulatan ke digit terdekat
(in-rounding).

1. Pemenggalan (chopping )

Misalkan adalah bilangan titik-kambang dalam basis 10:
= . x
misalkan adalah banyak digit mantis komputer. Karena digit mantis lebih banyak dari digit mantis komputer, maka bilangan dipotong sampai digit saja:
( ) = x

2. Pembulatan ke digit terdekat ( in-rounding )

Misalkan adalah bilangan titik-kambang dalam basis 10:
          = . x
Misalkan adalah jumlah digit mantis komputer. Karena digit mantis lebih banyak dari digit mantis komputer, maka bilangan dibulatkan sampai digit.
Contohnya, bilangan x di dalam komputer hipotesis dengan 7 digit mantis dibulatkan menjadi fl =0.3141593 x dengan galat sebesar 0.00000035…. contoh ini memperlihatkan bahwa pembulatan ke digit terdekat menghasilkan galat yang lebih rendah daripada pemenggalan.
2.5.4 Aritmetika Bilangan Titik-Kambang
Operasi aritmetika pada bilangan titik-kambang meliputi operasi penambahan dan pengurangan, operasi perkalian, dan operasi pembagian.
2.5.4.1 Operasi penambahan dan Pengurangan
Terdapat dua buah kasus serius yang menyebabkan timbulnya galat pembulatan pada operasi penjumlahan dua buah bilangan titik-kambang:
Kasus 1 : Penjumlahan (termasuk pengurangan) bilangan yang sangat kecil ke (atau dari) bilangan yang lebih besar menyebabkan timbulnya galat pembulatan.
Galat pembulatan pada kasus 1 ini terjadi karena untuk menjumlahkan dua buah bilangan yang berbeda relatif besar, pangkatnya harus disamakan terlebih dahulu (disamakan dengan pangkat bilangan yang lebih besar).
2.5.4.2 Operasi Perkalian dan Pembagian
Operasi perkalian dan pembagian dua buah bilangan titik-kambang tidak memerlukan penyamaan pangkat seperti halnya pada penjumlahan perkalian dapat dilakukan dengan mengalikan kedua mantis dan menambahkan kedua pangkatnya. Pembagian dikerjakan dengan membagi mantis dan mengurangkan pangkatnya.
2.6     Perambatan Galat
Galat yang dikandung dalam bilangan titik-kambang merambat pada hasil komputasi. Misalkan terdapat dua bilangan dan (nilai sejati) dan nilai hampirannya masing-masing dan , yang mengandung galat masing-masing dan jadi, kita dapat menulis
          =
Dan

Berikut adalah bagaimana galat merambat pada hasil penjumlahan dan perkalian dan .
Untuk penjumlahan,

Jadi, galat hasil penjumlahan sama dengan jumlah galat masing-masing operand.
Untuk perkalian,

Yang bila kita susun menjadi

Dengan mengandaikan bahwa dan , maka galat relatifnya adalah

2.7     Kondisi Buruk
Suatu persoalan dikatakan berkondisi buruk (ill conditioned ) bila jawabannya sangat peka terhadap perubahan kecil data (misalnya perubahan kecil akibat pembulatan). Bila kita mengubah sedikit data , maka jawabannya berubah sangat besar (drastis ). Lawan dari berkondisi buruk adalah berkondisi baik (well conditioned ). Suatu persoalan dikatakan baik bila perubahan kecil data hanya mengakibatkan perubahan kecil pada jawabannya.
Sebagai contoh, tinjau persoalan menghitung akar persamaan kuadrat di bawah ini. Disini kita hanya mengubah nilai-nilai tetapan c-nya saja:
(i)           akar-akarnya dan
Sekarang, ubah 3.99 menjadi 4.00:
(ii)      akar-akarnya
Ubah 4.00 menjadi 4.001:
(iii)        akar-akarnya imajiner
Dapat dikatakan bahwa persoalan akar-akar persamaan kuadrat diatas berkondisi buruk, karena dengan pengubahan sedikit saja data masukannya (dalam hal ini nilai koefisien c ), ternyata nilai akar-akarnya berubah sangat besar.
2.8     Bilangan Kondisi
Kondisi komputasi numerik dapat diukur dengan bilangan kondisi. Bilangan kondisi merupakan ukuran tingkat sejauh mana ketidakpastian dalam diperbesar oleh Bilangan kondisi dapat dihitung dengan bantuan Deret taylor. Fungsi diuraikan di sekitar sampai suku orde pertama:

Galat relatif hampiran dari adalah

Dan galat relatif hampiran dari adalah

          Bilangan kondisi didefinisikan sebagai nisbah (ratio) antara galat relatif hampiran dan
          Bilangan kondisi
Arti dari bilangan kondisi adalah:
–      Bilangan kondisi = 1 berarti galat relatif hampiran fungsi sama dengan galat relatif
–      Bilangan kondisi lebih besar dari 1 berarti galat relatif hampiran fungsi besar
–      Bilangan kondisi lebih kecil dari 1 berarti galat relatif hampiran fungsi kecil (kondisi baik)
Suatu komputasi dikatakan berkondisi buruk jika bilangan kondisinya sangat besar, sebaliknya berkondisi baik bila bilangan kondisinya sangat kecil.


lebih lengkapnya silahkan download file berikut ini