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 − 4 ac 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 kadangkadang 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. -x-x f(x)=e • Lacks precision • 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 Bawah memiliki tanda sama. Akar tidak ada atau banyak akar
f(x)
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 = xr RETURN f(xl)f(xr) >0 then xl = xr RETURN f(xl)f(xr) =0 then root equals xr - COMPLETE
Metode Bagi Dua [a 0 , b0 ]
Asumsi: Fungsi f(x) kontinu dalam interval f ( a 0 ) f (b0 ) < 0
do n = 0,1,… m = ( a n + bn ) / 2
a n +1 = a n , bn +1 = m
if f ( a n ) f ( m ) < 0, then else a n + 1 = m ,
bn +1 = bn
if bn +1 − a n +1 ≤ ε or end do
f (m) = 0
exit
Bisection Method
Error perkiraan akhir − perkiraan εa = perkiraan awal
awal
× 100
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 xu f(xl)
Based on similar triangles
f (x l ) f (x u ) = xr − xl xr − xu f ( x u )( x l − x u ) xr = xu − f (x l ) − f (x u )
Regula Falsi [a 0 , b0 ]
Asumsi: Fungsi f(x) kontinu dalam interval f ( a 0 ) f (b0 ) < 0
do n = 0,1,… w = [ f (bn ) a n − f ( a n )bn ] /[ f (bn ) − f ( a n )]
a n +1 = a n , bn +1 = w
if f ( a n ) f ( w ) < 0, then else a n + 1 = w , if end do
bn + 1 − a n + 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 − xi + 1 rearrange xi + 1
f ( xi ) = xi − f ' ( xi )
Metode Newton-Raphson
Newton Raphson Pitfalls
CONTOH 1 00 80 60 f(x)
Gunakan metode Newton Raphson untuk mencari akar-akar 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 ( x i − 1 ) − f ( xi ) f ' (x) = xi −1 − 1 − xi
APAKAH finite divided difference? HINT: dy / dx = ∆y / ∆x Masukkan FDD pada rumus untuk Newton Raphson
xi +1
f ( xi ) = xi − f ' ( xi )
xi +1
f ( xi )( xi −1 − xi ) = xi − f ( xi −1 ) − f ( xi )
Masukkan perkiraan dengan finite difference pada rumus untuk Newton Raphson
Secant method
Metode Secant
Secant method f ( xi )( xi −1 − xi ) xi +1 = xi − f ( xi−1 ) − 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 ∂vi ∂u − vi ∂y ∂y xi + 1 = xi − ∂ui ∂vi ∂ui ∂vi − ∂x ∂y ∂y ∂x ∂vi ∂u ui − vi ∂y ∂y yi + 1 = yi − ∂ ui ∂ vi ∂ ui ∂ v i − ∂x ∂y ∂y ∂x ui
u(x,y) dan v(x,y)
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 ∂y ∂y 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 ∂ ( f 1 , f 2 ,..., f n ) = ∂x1 ∂ ( x1 , x 2 ,..., x n ) ... ∂f n ∂x1
∂f1 ∂x 2 ∂f 2 ∂x 2 ... ∂f n ∂x 2
... ... ... ...
∂f1 ∂x n ∂f 2 ∂x n ... ∂f n ∂x n
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 = fx fy ∂u gx gy
− gx ∂y = fx fy ∂u 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 = 2 + 8xy; = 4y ; = 2x; = 6x + 2 y ∂y ∂x ∂y ∂x
