ROOTS OF NON LINIER EQUATIONS • • • • • •
Metode Bagi dua (Bisection Method) Metode Regula Falsi (False Position Method) Metode Grafik Iterasi Titik-Tetap (Fix Point Iteration) Metode Newton-Raphson Metode Secant
SOLUSI PERSAMAAN KUADRAT TINGKAT 2 f ( x) ax 2 bx c 0 b b 2 4ac x 2a
Persamaan di atas memberi akar-akar penyelesaian untuk fungsi aljabarf(x) Yaitu nilai-nilai x yang memberikan f(x) = 0 Kalau persaamaannya f(x) = e-x - x?
OVERVIEW OF METHODS • Bracketing methods Graphing method Bisection method False position
• Open methods One point iteration Newton-Raphson Secant method
SPECIFIC STUDY OBJECTIVES • Memahami konsep konvergensi dan divergensi. • Memahami bahwa metode tertutup selalu konvergen, sedangkan metode terbuka kadang-kadang divergen. • Konvergensi pada metode terbuka biasanya didapat jika initial guess –nya dekat dengan akar sebenarnya.
METODE TERTUTUP • Graphical • Bisection method • False position method
CARA GRAFIK • Plotkan fungsinya dan tentukan dimana memotong sumbu x. • Lacks precision f(x)=e-x-x • Trial and error 10 8
f(x)
6 4 2 0 -2 -2
-1
0 x
1
2
CARA GRAFIK (LIMITED PRACTICAL VALUE)
f(x)
x
Pembatas atas dan f(x) Bawah memiliki tanda sama. Akar tidak ada atau banyak akar
x
f(x)
f(x) Tanda berbeda, jumlah akar-akar ganjil x
x
BISECTION METHOD • Memanfaatkan beda tanda dua nilai batas • f(xl)f(xu) < 0 dimana l=lower (batas bawah) dan u=upper (batas atas) • Minimal ada satu akar
f(x)
f(x)
x
f(x)
x
x
ALGORITHM • Pilih xu dan xl. Cek beda tanda nilai fungsi keduanya f(xl)f(xu) < 0 • Perkirakan akar xr = (xl + xu) / 2 • Tentukan interval berikut ada di subinterval atas atau subinterval bawah f(xl)f(xr) < 0 then xu baru = xr RETURN f(xl)f(xr) >0 then xl baru = xr RETURN f(xl)f(xr) =0 then root equals xr - COMPLETE
METODE BAGI DUA Asumsi: Fungsi f(x) kontinu dalam interval a0 ,b0 f (a0 ) f (b0 ) 0
do n = 0,1,… m (an bn ) / 2
an 1 an , bn 1 m
if f (a n ) f (m) 0, then else a n 1 m , bn 1 bn if bn1 an 1 or end do
f ( m) 0
exit
BISECTION METHOD
ERROR perkiraanakhir perkiraanawal a 100 perkiraanakhir
CONTOH Gunakan bisection method untuk mencari akar-akar persamaan 8 6 f(x)
•f(x) = e-x - x •xl = -1 xu = 1
10
3.7 1 8282
4 2
-0.6321 2
0 -2 -2
-1
0 x
1
2
SOLUTION 10 8
f(x)
6 4
3.7 1 8282 1
2
-0.6321 2
0 -2 -2
-1
0 x
1
2
SOLUTION
2
f(x)
1
0
0.1 06531
-0.6321 2
-2 -1
0
1 x
2
FALSE POSITION METHOD • “Brute Force” dari metode bagi dua kurang efisien • Menghubungkan dua nilai batas dengan garis lurus • Mengganti kurva menjadi garis lurus memberikan “false position” • Mempercepat perkiraan
next estimate, xr
f(xu)
xl
Based on similar triangles
f xl f xu xr xl xr xu
xu f(xl)
f x u x l x u xr xu f xl f xu
Nilai f(xr) dicek tandanya, kemudian tentukan xu dan xl yang baru berdasarkan perbedaan tanda seperti pada metode bagi dua
REGULA FALSI Asumsi: Fungsi f(x) kontinu dalam interval a0 ,b0 f (a0 ) f (b0 ) 0
do n = 0,1,… w [ f (bn )an f (an )bn ] /[ f (bn ) f (an )]
an 1 an , bn 1 w
if f (an ) f ( w) 0, then else a n 1 w , if end do
bn 1 an 1
bn 1 bn
or
f ( w) 0
exit
REGULA FALSI
CONTOH Tentukan akar persamaan dari persamaan berikut menggunakan false position method, mulai dengan initial estimate xl=4.55 and xu=4.65 30
20
f(x) =
x3 -
98
f(x)
10 0 -1 0 -20 -30 -40 4
4.5 x
5
OPEN METHODS • Simple one point iteration • Newton-Raphson method • Secant method • Pada metode tertutup, akar terdapat di antara kedua interval yang dibatasi batas atas dan bawah
OPEN METHODS • Metode terbuka diharapkan konvergen solution moves closer to the root as the computation progresses
• Metode terbuka; • single starting value, atau • two starting values that do not necessarily bracket the root
• Ada kemungkinan metode ini divergen solution moves farther from the root as the computation progresses
f(x)
The tangent gives next estimate.
f(xi+1 ) xi xi+1 f(xi)
x
Solution can “overshoot” the root and potentially diverge
f(x)
x2
x1 x0
x
SIMPLE ONE POINT ITERATION / METODE TITIK TETAP • Merubah formula untuk memperkirakan akar • Re-arrange fungsi f(x) sehingga ada satu nilai x pada sebelah kiri dari persamaan Contoh, untuk f(x) = x2 - 2x + 3 = 0 Ubah menjadi x = (x2 + 3) / 2
SIMPLE ONE POINT ITERATION • Contoh lain, untuk f(x) = sin x = 0, menjadi x = sin x + x
• Hitung nilai x = g(x) • Perkiraan nilai berikut berdasar pada x i+1 = g(xi)
ITERASI TITIK TETAP
CONTOH
f(x)
• Untuk f(x) = e-x -3x • Ubah menjadi g(x) = e-x / 3 • Initial guess x = 0 16 14 12 10 8 6 4 2 0 -2 -4 -6 -2
-1
0 x
1
2
Initial guess
0.000
g(x)
f(x)
0.333
-0.283
0.239
0.071
39.561
0.263
-0.018
9.016
f(x)
a
16 14 12 10 8 6 4 2 0 -2 -4 -6 -2
-1
0 x
0.256
0.005
2.395
0.258
-0.001
0.612
0.258
0.000
0.158
0.258
0.000
0.041
1
2
METODE NEWTON RAPHSON tangent f(xi)
xi+1
xi
dy tangent f' dx f xi 0 f ' xi xi xi1 rearrange f xi xi1 xi f ' xi
METODE NEWTON-RAPHSON
NEWTON RAPHSON PITFALLS
CONTOH
1 00 80 60 f(x)
Gunakan metode Newton Raphson untuk mencari akarakar dari f(x) = x2 - 11 memakai initial guess xi = 3
40 20 0 -20 0
2
4
6 x
8
10
NEWTON RHAPSON SECANT • Include an upper limit on the number of iterations • Establish a tolerance, s • Check to see if a is increasing
Bagaimana jika turunan fungsinya sulit dipecahkan? SECANT METHOD
SECANT METHOD Memperkirakan turunan menggunakan finite divided difference f xi 1 f xi f ' x xi 1 xi
APAKAH finite divided difference? HINT: dy / dx = y / x Masukkan FDD pada rumus untuk Newton Raphson
f xi xi 1 xi f ' xi
f xi xi 1 xi xi 1 xi f xi 1 f xi
Masukkan perkiraan dengan finite difference pada rumus untuk Newton Raphson
SECANT METHOD
METODE SECANT
SECANT METHOD f xi xi1 xi xi1 xi f xi1 f xi
• Membutuhkan dua nilai perkiraan awal • f(x) tidak harus berbeda tanda, membedakan dengan metode tertutup, false position method.
FALSE POSITION f(x)
2
SECANT METHOD 2 f(x)
1 x
1 new est. Perkiraan baru dipilih dari potongan garis dengan sumbu x
new est.
x
Perkiraan baru bisa diluar batas kurva
SYSTEMS OF NON-LINEAR EQUATIONS • Kita telah mengenal sistem persamaan linier f(x) = a1x1 + a2x2+...... anxn - C = 0 dimana a1 , a2 .... an dan C adalah konstanta
• Maka, perhatikan sistem persamaan non-linier y = -x2 + x + 0.5 y + 5xy = x3
• Selesaikan x dan y
SYSTEMS OF NON-LINEAR EQUATIONS • Buat persamaan sama dengan nol u = x2 + xy – 10 v = y + 3xy2 – 57
• u(x,y) = x2 + xy – 10 = 0 • v(x,y) = y + 3xy2 – 57 = 0 • Solusi adalah nilai-nilai x dan y yang akan memberikan nilai fungsi u dan v sama dengan nol.
METODE TITIK TETAP • Mulai dengan nilai awal x0 = 1.5 dan y0 = 3.5
x1
10 x 0 y 0
y1
57 y 0 3 x1
METODE NEWTON RHAPSON
u(x,y) dan v(x,y)
vi u vi ui y y xi 1 xi ui vi ui vi x y y x vi u ui vi x x yi 1 yi ui vi ui vi x y y x
Versi dua persamaan untuk Newton-Raphson
DETERMINAN JACOBIAN (TAMBAHAN SAJA) vi u ui vi y y xi 1 xi ui vi ui vi x y y x vi u ui vi x x yi 1 yi ui vi ui vi x y y x
THE DENOMINATOR OF EACH OF THESE EQUATIONS IS FORMALLY REFERRED TO AS THE DETERMINANT OF THE JACOBIAN
JACOBIAN (TAMBAHAN JUGA) • The general definition of the Jacobian for n functions of n variables is the following set of partial derivatives:
f1 x1 f 2 ( f1 , f 2 ,..., f n ) x1 ( x1 , x2 ,..., xn ) ... f n x1
f1 x2 f 2 x2 ... f n x2
... ... ... ...
f1 xn f 2 xn ... f n xn
JACOBIAN (INI JUGA TAMBAHAN) • The Jacobian can be used to calculate derivatives from a function in one coordinate sytem from the derivatives of that same function in another coordinate system. • Equations u=f(x,y), v=g(x,y), then x and y can be determined as functions of u and v (possessing first partial derivatives) as follows: u f ( x, y ); f x f / y; f y f / x v g ( x, y ); g x g / x; g y g / y gy x u f x f y gx g y
gx y u f x f y gx gy
• With similar functions for xv and yv. • The determinants in the denominators are examples of the use of Jacobians.
CONTOH u = 2x3 + 2xy – 2 v = 2y + 4xy2 – 3 Mulai dengan nilai awal x0 = 0.5 dan y0 = 1.5
v v u u 2 2 28xy; 4y ; 2x; 6x 2y y x y x
