Menemukan Akar-akar Persamaan Non-Linear

Menemukan Akar-akar Persamaan Non-Linear

Muhtadin, ST. MT.

Metode Numerik By : Muhtadin

Agenda • Metode Tertutup – Biseksi – Regula Falsi • Metode Terbuka – Newton Method


3

Solusi untuk Persamaan Non Linear Akar-akar dari persamaan (y = f(x)) nilai dari x yang menjadikan f(x) = 0.

• Aljabar umum untuk persamaan sederhana, misalkan: – f(x) = 2x – 3 = 0  x = 1.5 – f(x) = x2 – 4x – 5 = 0  x1 = 5 and x2 = -1 • Persamaan Non Linear  lebih sulit dikerjakan. – h(x) = h0(sin(2πx/α)cos(2πtv/ α) + e-x – f(x) = 9.34 – 21.97x + 16.3x3 – 3.7x5 = 0


4

Cara Menemukan Akar Menemukan akar dari persamaan kuadrat.

ax  bx  c  0 2

 b  b 2  4ac x 2a General solution

Untuk fungsi yang kompleks

sin x 1 x2

e

x 1.2


Menggunakan Metode Numerik

5

Graphical Method

F(x) = x2 - 3

X F(X)

0 -3

1 -2 -2 < 0

2 1 1>0

3 6

=> Terdapat sedikitnya satu akar diantara 1 dan 2. Theorema: Jika sebuah fungsi f(x) kontinyu dan f(a)f(b) < 0, maka persamaan f(x) mempunyai paling sedikit satu akar real pada interval (a,b). Plot fungsi pada grafik [a, b]. Metode Numerik By : Muhtadin

6

Graphical Method (cont’d) Plot grafik fungsi dengan menggunakan penggaris dan pensil.

Subplot the graph


7

Root Approximation: The Methods

• Metode Tertutup (bracketing methods) – Pendekatan akar pada interval [a, b]. – Menjamin menemukan minimal 1 (satu) akar. – Bisection dan regula falsi • Metode Terbuka – Menebak terlebih dahulu akar yang dimaksud. – Secara iterative, mendekati akar sebenarnya, menggunakan nilai yang lama. – Terkadang bersifat difergen maupu konvergen. – Newton method


8

Closed Methods Pada sebuah interval, bisa terdapar satu atau lebih akar, atau mungkin tidak ada akar.

– f(a)f(b) < 0  Σ root = odd a

b b

a

– f(a)f(b) > 0  Σ root = zero or even

a

b

a

b

9

Bisection Method

f(x) f(m1)>0

=

a1 a0

m2

b0

=

m1 b1

• Pastikan f(ai) f(bi) < 0 for i = 0,1,2,3,... Metode Numerik By : Muhtadin

10

Example (Bisection Method)

Tentukan akar dari persamaan f(x) = -11 -22x + 17x2 -2.5x3 – Dengan menggunakan metode biseksi, dengan nilai error Ԑa, hingga mendapatkan 3 digit yang sama, dengan nilai awal xi = 0 dan xu = 4


11

• 0th iteration: f(x) = -11 -22x + 17x2 -2.5x3 xl = 0;xu = 4; xr = (0 + 4) / 2 = 2 f(xl) = -11; f(xl) f(xr) = 77

f(xr) = -7;

i

xl

xu

xr

f(xl)

f(xr)

f(xl) f(xr)

0

0

4

2

-11

-7

77


Ea

ea

12

f(x)=-11-22x+17x^2-2.5x^3 20 15 10 5

xu

0 -5 0

0.5

1

1.5

2

2.5

3

3.5

4

-10 -15

xr

-20 xl -25 Metode Numerik By : Muhtadin

13



1st iteration: xl = 2; (∵ f(xl) f(xr) > 0)

xu = 4;

xr = (2 + 4) / 2 = 3

f(xl) = -7; f(xr) = 8.5; f(xl) f(xr) = -59.5 Ea = xrnew – xrold = 3 – 2 = 1 ea = (xrnew – xrold) / xrnew = (3 – 2) / 3 = 0.3333333 i

xl

xu

xr

f(xl)

f(xr)

f(xl) f(xr)

0

0

4

2

-11

-7

77

1

2

4

3

-7

8.5

-59.5


Ea

ea

1

0.3333333 14

f(x)=-11-22x+17x^2-2.5x^3 20 15 10 5

xu xr

0 -5 0

0.5

1

1.5

2

2.5

3

3.5

4

-10 -15

xl

-20 -25 Metode Numerik By : Muhtadin

15

i

xl

xu

xr

f(xl)

f(xr)

f(xl) f(xr)

0

0

4

2

-11

-7

77

1

2

4

3

-7

8.5

2

2

3

2.5

-7

3

2

2.5

2.25

4

2.25

2.5

5

2.375

6

Ea

ea

-59.5

1

0.3333333

1.1875

-8.3125

-0.5

-0.2

-7

-2.91406

20.39844

-0.25

0.1111111

2.375

-2.91406

-0.85059

2.478661

0.125

0.0526316

2.5

2.4375

-0.85059

0.173462

-0.14754

0.0625

0.025641

2.375

2.4375

2.40625

-0.85059

-0.33754

0.287106

-0.03125

-0.012987

7

2.40625

2.4375

2.421875

-0.33754

-0.08175

0.027595

0.015625

0.0064516

8

2.421875

2.4375

2.429688

-0.08175

0.045928

-0.00375

0.007813

0.0032154

9

2.421875

2.429688

2.42578

-0.08175

-0.0179

0.001463

-0.0039

0.0016103

2.425781  10Lanjutkan iterasi hingga dihasilkan nilai pembulatan xl dan xu 2.429688

3



menghasilkan 3 digit yang sama Jawaban : x = 2.43


16

Comments on Bisection Methods • • • •

Two-point method, Bracketing Method. Nilai yang dihitung hanya berdasarkan tanda dari nilai fungsi. Pasti konvergen. Tingkat konvergen rendah. – Setiap step menghasilkan peningkatan akurasi satu binary digit. (one decimal digit / 3.3 steps) – Jika error didefiniskan sebagai Maka setiap kali iterasi dihasilkan error sebesar , dengan mengambil nilai , maka dapat diperoleh jumlah iterasi yang akan dilakukan adalah :


17

Tugas Hitung persamaan f(x) = -4 -2x - x2 + x3 • Dengan nilai awal xi=2 dan xu=3 hingga 3 iterasi.


18

Regula Falsi


19

Regula Falsi Method (False-position Method) f(x)

S xl xu

xr x  xl y  f ( xl )  xu  xl f ( xu )  f ( xl ) xr 

xl f ( xu )  xu f ( xl ) dengan y  0, x  xr f ( xu )  f ( xl ) 20


Algorithm of False-position method • Pilihlah inisialisasi awal f(xr) f(xl) < 0 dan • Ulangi sehingga f ( xr )  

xr 

xl f ( xu )  xu f ( xl ) f ( xu )  f ( xl )

 Jika f(xr) = 0, maka x = xr adalah akar persamaan, STOP  Jika f(xl) f(xr) < 0, gantikan xu

dengan xr.  Jika f(xl) f(xr) > 0, gantikan xl dengan xr. 

Kembali ke perulangan


21

False-position Example



0th iteration: f(x) = -11 -22x + 17x2 -2.5x3 xl = 0; xu = 4; xr = xl f ( xu )  xu f ( xl ) = 1.833333 f ( xu )  f ( xl )

f(xl) = -11; f(xl)f(xr) = 105.5949

i 0

xl

xu 0

xr 4

1.83333 3


f(xr) = -9.59954;

f(xl) -11

f(xu) 13

f(xr)

f(xl)f (xr)

9.59954

105.5949

Ea

ea

22

f(x)=-11-22x+17x^2-2.5x^3 20 15 10 5

xu

0 -5 0

0.5

1

1.5

2

2.5

3

3.5

4

-10 -15 -20 xl

xr

-25 Metode Numerik By : Muhtadin

23



1st iteration: xl = 1.833333; (∵ f(xl) f(xr) > 0) xr =

xu = 4;

xl f ( xu )  xu f ( xl ) = 2.753662 f ( xu )  f ( xl )

f(xl) = -9.59954; f(xl)f(xr) = -49.1918

f(xr) = 5.12439;

Ea = xrnew – xrold = 2.753662 – 1.833333 = 0.920328 ea = (xrnew – xrold) / xrnew = (2.753662 – 1.833333) / 2.753662 = 0.3342199 i

xl

xu

xr

f(xl)

f(xu)

f(xr)

f(xl)f (xr)

1.83333 3

-11

13

9.59954

105.5949

1.833333 2.75366 4 3 By : Muhtadin 2 Metode Numerik

9.59954

13

5.12439

-49.1918

0 1

0

4

Ea

ea

0.92032 8

0.3342199

24

f(x)=-11-22x+17x^2-2.5x^3 xu

20 15

xr

10 5 0 -5 0

0.5

1

1.5

2

2.5

3

3.5

4

-10 -15 -20

xl

-25 Metode Numerik By : Muhtadin

25

i

xl

xu

xr

f(xl)

f(xu)

f(xr)

f(xl)f (xr)

Ea

ea

0

0

4

1.83333 3

-11

13

9.59954

105.5949

1

1.833333 3

4

2.75366 2

9.59954

13

5.12439

-49.1918

0.92032 8

0.3342199

2

1.833333 3

2.75366 2

2.43335 9

9.59954

5.12439

0.10587 4

-1.01635

-0.3203

0.1316301

3

1.833333 3

2.43335 9

2.42681 3

9.59954

0.10587 4

0.00103

0.009928

0.00655

0.0026972

4

2.426813

2.43335 9

2.42688

0.00103

0.10587 4

5E-07

-5.2E-10

6.3E-05

2.609E-05

5 

2.42687 Lanjutkan iterasi hingga xl dan xu memiliki pembulatan 3 2.426813 6 angka yang sama Jawab: x = 2.43


26

Kesimpulan – Regula Falsi • Merupakan two-point method, Bracketing Method. • Pada umumnya, lebih cepat menuju konvergen dibandingkan dengan biseksi


27

Metode Newton-Raphson


28

Newton-Raphson Method

f(x)

x f x 

f(xi)

i,

i

f(xi-1)  xi+2

xi+1

xi

X

f(xi ) xi 1 = xi f (xi )

Derivation

f(x)

f(xi)

AB tan(   AC

B

f ( xi ) f ' ( xi )  xi  xi 1 C 

A

xi+1

xi

Metode Numerik & Komputasi. By : Muhtadin

X

f ( xi ) xi 1  xi  f ' ( xi )

Prasyarat Metode Newton-Raphson • Diperlukan SATU HARGA AWAL (dapat berupa tebakan), dan tebakan harga awal tersebut tidak menyebabkan harga fungsi menjadi tak berhingga. • Persamaan y = f (x) mempunyai turunan yang dapat disebut sebagai y’ = f’(x) dan harus kontinyu di daerah domain jawab. • Turunan fungsi tersebut tidak berharga nol, y’≠ 0 , pada harga xk (pada iterasi ke-k) yang diinginkan


31

Kriteria Penghentian Bilamana SALAH SATU dari syarat berikut ini terpenuhi : • Selisih harga xk (pada iterasi terbaru) dengan xk-1 (pada iterasi sebelumnya) lebih kecil atau sama dengan harga Ԑ, atau dapat dituliskan sebagai: , atau

• Harga fungsi f(xk) (dengan menggunakan harga x pada iterasi terbaru) sudah sangat kecil dan menuju nol atau dapat dikatakan juga lebih kecil atau sama dengan harga Ԑ, yang dapat dituliskan sebagai:


32

Algoritma Newton-Raphson • Tentukan Nilai Awal

• Hitung nilai f(x) • Hitung nilai estimasi akar untuk iterasi selanjutnya,

f(xi ) xi 1 = xi f'(xi ) • Hitung absolut error :

xi 1- xi a = x 100 xi 1 • Ulangi hingga memenuhi syarat kriteria penghentian iterasi


33

Tabel Newton-Raphson


34

Contoh : Newton-Raphson • Menemukan akar persamaan :

f x   x 3-0.165 x 2+3.993 10 - 4


35

Contoh : Newton-Raphson

Hitung

f ' x 

f  x   x 3-0.165 x 2+3.993 10 - 4 f '  x   3 x 2 -0.33 x Asumsi awal f x   0 Untuk

x0  0.05


36

Iterasi 1 Perkiraan akar :

f  x0  x1  x0  f '  x0  3 2  0.05   0.1650.05   3.993  10  4  0.05  2 30.05   0.330.05 

1.118 10  4  0.05   9  10 3  0.05   0.01242   0.06242


37


38

Hitung relative approximate error a pada iterasi 1

a 

x1  x0  100 x1

0.06242  0.05  100 0.06242  19.90%




39

Iterati 2 Perkiraan akar :

f  x1  x2  x1  f '  x1  3 2  0.06242   0.1650.06242   3.993 10  4  0.06242  2 30.06242   0.330.06242 

 3.97781 10 7  0.06242   8.90973  10 3  0.06242  4.4646  10 5   0.06238


40


41


a 

x2  x1  100 x2

0.06238  0.06242  100 0.06238  0.0716 %




42

Iterasi 3 Perkiraan akar :

f  x2  x3  x2  f '  x2  3 2  0.06238   0.1650.06238   3.993 10  4  0.06238  2 30.06238   0.330.06238 

4.44 10 11  0.06238   8.91171 10 3  0.06238   4.9822 10 9   0.06238


43


44


a 

x2  x1  100 x2

0.06238  0.06238  100 0.06238  0%




45

Keuntungan Newton-Raphson • Memiliki tingkat konvergensi yang cepat (quadratic convergence), jika konvergen. • Hanya memerlukan satu buah nilai tebakan


46

Kerugian Newton-Raphson • Divergen pada inflection point Iteration Number

xi

0

5.0000

1

3.6560

2

2.7465

3

2.1084

4

1.6000

5

0.92589

6

−30.119

7

−19.746

18

0.2000


47

Kerugian Newton-Raphson • Division by zero

f x   x 3  0.03 x 2  2.4 10 6  0

Akar dihitung dengan :

xi3  0.03 xi2  2.4 10 6 xi 1  xi  3xi2  0.06 xi Untuk x0  0 atau x0  0.02 dihasilkan pembagian dengan 0


48

Kerugian Newton-Raphson • Root Jumping


49

Quiz • Pada persamaan 𝑓 𝑥 = 𝑥 3 − 4𝑥 2 + 5 = 0, – Tunjukkan bahwa persamaan di atas memiliki solusi untuk selang [0,2]. Jelaskan kondisi-kondisi yang harus dipenuhi sehingga bisa menyimpulkan bahwa fungsi f(x) memiliki akar di dalam interval [0,2]. – Carilah solusi untuk persamaan di atas dengan metode Regula Falsi atau metode newton raphson (sebanyak 3 iterasi).


50

Reference • www.cse.cuhk.edu.hk/~csc2800/tuto/tutorial_03.ppt, By Albert


51

TERIMA KASIH


53

Menemukan Akar-akar Persamaan Non-Linear

Recommend Documents