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
aacbbx
cbxaxxf
24
0)(2
2
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 methodsGraphing methodBisection methodFalse position
• Open methodsOne point iterationNewton-RaphsonSecant 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• Trial and error f(x)=e-x-x
-2
0
2
4
6
8
10
-2 -1 0 1 2
x
f(x)
CARA GRAFIK (LIMITED PRACTICAL VALUE)
x
f(x)
x
f(x)
x
f(x)
x
f(x)
Pembatas atas dan Bawah memiliki tanda sama. Akar tidak ada atau banyak akar
Tanda berbeda, jumlah akar-akar ganjil
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
x
f(x)
x
f(x)
x
f(x)
ALGORITHM• Pilih xu dan xl. Cek beda tanda nilai fungsi
keduanyaf(xl)f(xu) < 0
• Perkirakan akarxr = (xl + xu) / 2
• Tentukan interval berikut ada di subinterval atas atau subinterval bawahf(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 00 ,ba
0)()( 00 bfaf
do n = 0,1,…2/)( nn bam
if ,0)()( mfaf n then ,1 nn aa mbn 1
else ,1 ma n nn bb 1
if 11 nn ab exitend do
or 0)( mf
BISECTION METHOD
ERROR
100
akhir
awalakhira perkiraan
perkiraanperkiraan
•f(x) = e-x - x•xl = -1 xu = 1
CONTOHGunakan bisection method untuk mencari akar-akar persamaan
3.7 18282
-0.63212
-2
0
2
4
6
8
10
-2 -1 0 1 2
x
f(x)
SOLUTION
3.7 18282
-0.63212
1
-2
0
2
4
6
8
10
-2 -1 0 1 2
x
f(x)
-0.63212
1
0.106531
-2
0
2
-1 0 1 2
x
f(x)
SOLUTION
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
xl
xuf(xl)
f(xu)next estimate, xr
f xx x
f xx x
x xf x x xf x f x
l
r l
u
r u
r uu l u
l u
Based on similar triangles
Nilai f(xr) dicek tandanya, kemudian tentukan xu dan xl yang baruberdasarkan perbedaan tanda seperti pada metode bagi dua
REGULA FALSI
Asumsi: Fungsi f(x) kontinu dalam interval 00 ,ba
0)()( 00 bfaf
do n = 0,1,…)]()(/[])()([ nnnnnn afbfbafabfw
if ,0)()( wfaf n then ,1 nn aa wbn 1
else ,1 wa n nn bb 1
if 11 nn ab exit
end do
or 0)( wf
REGULA FALSI
CONTOH
Tentukan akar persamaan dari persamaan berikut menggunakan false position method, mulai dengan initial estimate xl=4.55 and xu=4.65
f(x) = x3 - 98-40
-30
-20
-10
0
10
20
30
4 4.5 5
x
f(x)
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
The tangentgives next estimate.xi
f(x)
x
f(xi)
xi+1
f(xi+1 )
Solution can “overshoot”the root and potentiallydiverge
x0
f(x)
x
x1x2
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 = 0Ubah menjadix = (x2 + 3) / 2
SIMPLE ONE POINT ITERATION
• Contoh lain, untuk f(x) = sin x = 0,menjadix = sin x + x
• Hitung nilai x = g(x)• Perkiraan nilai berikut berdasar pada
x i+1 = g(xi)
ITERASI TITIK TETAP
CONTOH
• Untuk f(x) = e-x -3x• Ubah menjadi g(x) = e-x / 3• Initial guess x = 0
-6-4-202468
10121416
-2 -1 0 1 2
x
f(x)
Initial guess 0.000
g(x) f(x) a
0.333 -0.283
0.239 0.071 39.561
0.263 -0.018 9.016
0.256 0.005 2.395
0.258 -0.001 0.612
0.258 0.000 0.158
0.258 0.000 0.041
-6-4-202468
10121416
-2 -1 0 1 2
x
f(x)
METODE NEWTON RAPHSON
tangent
dydx
f
f xf xx x
rearrange
x xf xf x
ii
i i
i ii
i
'
'
'
0
1
1
f(xi)
xi
tangent
xi+1
METODE NEWTON-RAPHSON
NEWTON RAPHSONPITFALLS
CONTOH
Gunakan metode Newton Raphson untuk mencari akar-akar dari f(x) = x2 - 11 memakai initial guess xi = 3
-20
0
20
40
60
80
100
0 2 4 6 8 10
x
f(x)
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
f x f x f xx xi i
i i
'
1
1
Memperkirakan turunan menggunakan finite divided difference
APAKAH finite divided difference? HINT: dy / dx = y / x
Masukkan FDD pada rumus untuk Newton Raphson
SECANT METHOD
ii
iiiii
i
iii
xfxfxxxfxx
xfxfxx
1
11
1 '
Masukkan perkiraan dengan finite difference pada rumus untuk Newton Raphson
METODE SECANT
SECANT METHOD
• Membutuhkan dua nilai perkiraan awal• f(x) tidak harus berbeda tanda,
membedakan dengan metode tertutup, false position method.
ii
iiiii xfxf
xxxfxx
1
11
x
f(x)
1
2
new est.
x
f(x)
1
new est.
2
FALSE POSITION
SECANT METHOD
Perkiraan baru dipilih dari potongangaris dengan sumbu x
Perkiraan baru bisa diluar batas kurva
SYSTEMS OF NON-LINEAR EQUATIONS
• Kita telah mengenal sistem persamaan linierf(x) = a1x1 + a2x2+...... anxn - C = 0dimana a1 , a2 .... an dan C adalah konstanta
• Maka, perhatikan sistem persamaan non-liniery = -x2 + x + 0.5y + 5xy = x3
• Selesaikan x dan y
SYSTEMS OF NON-LINEAR EQUATIONS
• Buat persamaan sama dengan nolu = x2 + xy – 10v = 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
1
01
001
357
10
xyy
yxx
METODE NEWTON RHAPSON
xv
yu
yv
xu
xuv
xvu
yy
xv
yu
yv
xu
yuv
yvu
xx
iiii
ii
i
ii
iiii
ii
i
ii
1
1
Versi dua persamaan untuk Newton-Raphson
u(x,y) dan v(x,y)
DETERMINAN JACOBIAN (TAMBAHAN SAJA)
xv
yu
yv
xu
xuv
xvu
yy
xv
yu
yv
xu
yuv
yvu
xx
iiii
ii
i
ii
iiii
ii
i
ii
1
1THE DENOMINATOROF EACH OF THESEEQUATIONS ISFORMALLYREFERRED TOAS THE DETERMINANTOF THEJACOBIAN
JACOBIAN (TAMBAHAN JUGA)
• The general definition of the Jacobian for nfunctions of n variables is the following set of partial derivatives:
n
nnn
n
n
n
n
xf
xf
xf
xf
xf
xf
xf
xf
xf
xxxfff
...............
...
...
),...,,(),...,,(
21
2
2
2
1
2
1
2
1
1
1
21
21
JACOBIAN (INI JUGATAMBAHAN)
• 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:
• With similar functions for xv and yv.• The determinants in the denominators are examples of
the use of Jacobians.
yx
yx
x
yx
yx
y
yx
yx
ggff
guy
ggff
gux
yggxggyxgvxffyffyxfu
/;/);,(/;/);,(
CONTOH
u = 2x3 + 2xy – 2v = 2y + 4xy2 – 3Mulai dengan nilai awal x0 = 0.5 dan y0 = 1.5
yxxux
yuy
xvxy
yv 26;2;4;82 22