roots of non linier equationskuliah.ftsl.itb.ac.id/wp-content/uploads/2016/10/slide04...solusi...

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