2. PERSAMAAN NON-LINIER

2.

Bab PERSAMAAN NON-LINIER

Di dalam matematika aplikasi pencarian akar persamaan f(x)=0 sering dijumpai. Biasanya jawaban analitis dari persamaan diatas tidak ada, sehingga harus dicari jawaban numeriknya yang biasa dilaksanakan dengan metode iterasi.

2.1. Metode Bagi Paruh (Bisection) Jika terdapat suatu f(x) yang menerus ∈ [a,b] dan f(a)f(b) < 0, maka menurut Teorema 1.1 paling tidak f(x) mempunyai satu akar f(x) mempunyai satu akar ∈ [a,b].

♦ Algoritma Bisect(f, a, b, akar, ε) 1. Hitung c := (a+b)/2 2. Jika b – c ≤ ε , maka akar:= c, dan ‘ exit’ D:\My Documents\Publikasi\Metoda Numerik\Metoda Numerik.doc (2028 Kb)

3. Jika {tanda f(b)•tanda f(c)} i 0, maka a := c , jika tidak b := c 4. Kembali ke langkah nomor 1.

♦ Definisi Suatu deret hasil suatu iterasi {xn|nj0} dikatakan menuju ke titik derajat p j1 , jika

α − x n +1 ≤ c α − x n

p

dengan

n≥0

untuk beberapa nilai c>0. Jika p=1, deretnya disebut menuju ke titik secara linier. Pada kasus ini diperlukan nilai c<1; c disebut laju linier dari xn menuju . Ada beberapa metode yang membutuhkan definisi yang agak berbeda dengan diatas yaitu α − x n +1 ≤ c n α − x0 n ≥ 0

Metoda Numerik Ir. Djoko Luknanto, M.Sc., Ph.D.

hal. 16 Jack la Motta

Persamaan Non-Linier

Buku kuliah

♦ Tingkat kelajuan metode bagi paruh dinyatakan dalam 1 α − c n ≤ ( ) n (b − a) 2 y

c = (a+b)/2

c = (a+b)/2

nilai awal

c = (a+b)/2

metode ini diulang-ulang sampai abs (c-b) < ε

abaru

abaru

α

f(b)>0

bbaru b nilai

x

f(a)<0 y=f(x)

akar sesungguhnya yang akan dicari

Gambar 5 Metoda Bagi Paruh untuk mencari akar

2.2. Metode Newton

D:\My Documents\Publikasi\Metoda Numerik\Metoda Numerik.doc (2028 Kb)

Deret Taylor:

1 f ( x) = f ( x n ) + ( x − x n ) f ' ( x n ) + ( x − x n ) 2 f " ( x n ) + ... 2 atau menurut Teorema 1.4 1 f ( x) = f ( x n ) + ( x − x n ) f ' ( x n ) + ( x − x n ) 2 f " (ξ ) 2 dengan ξ diantara xn dan x. Jika akar dari f(x), salah satunya adalah α, maka f (x = α ) = 0 1 f ( x) = f ( x n ) + (α − x n ) f ' ( x n ) + (α − x n ) 2 f " (ξ ) = 0 2 jadi

α = xn −

f ( xn ) 1 f " (ξ ) − (α − x n ) 2 f ' ( xn ) f ' ( xn ) 2

maka α dapat didekati dengan




Buku kuliah

x n +1 = x n −

dengan ‘errornya’

α − x n +1 = −

f ( xn ) f ' ( xn )

n≥0

f " (ξ ) (α − x n ) 2 2 f ' ( xn )

n≥0

Untuk nilai n ∞, ξ

α dan xn α, jadi f " (α ) α − x n +1 = − (α − x n ) 2 2 f ' (α ) = konstanta × (α − x n ) 2

Sehingga metode Newton dikatakan mempunyai derajat kelajuan = 2 y y=f(x) grs singgung

akar sesungguhnya

α

nilai awal x1

x0

x


Gambar 6 Metoda Newton untuk mencari akar

♦ Algoritma Newton (f, df, x0, ε, akar, itmax, ierr) 1. Keterangan : df adalah f’(x), itmax adalah iterasi maximum, ierr adalah ‘error flag’ 2. noiter:=1 3. penyebut:=df(x0) 4. jika penyebut = 0 maka ierr:=2, dan ‘exit’ 5. x1:= x0 - f(x0)/penyebut 6. jika |x1 – x0|iε, maka ierr:= 0, akar:= x1, dan ‘exit’ 7. jika noiter = itmax maka ierr:= 1, dan ’exit’ 8. noiter:= noiter +1, x0:=x1, dan ulangi langkah 3.




Buku kuliah

2.3. Metode Sekan Dengan menggunakan sifat segitiga sebangun diperoleh

BD CD = BA CE f ( x1 ) − f ( x0 ) f ( x1 ) − 0 = x1 − x0 x1 − x 2 x1 − x 0 atau Jadi x 2 = x1 − f ( x1 ) f ( x1 ) − f ( x0 ) x n − x n −1 x n +1 = x n − f ( x n ) f ( x n ) − f ( x n −1 ) y

n ≥1

y=f(x) D akar sesungguhnya

nilai awal x0

x2

x3 E


A

C x α x1 nilai awal B

Gambar 7 Metoda Sekan untuk mencari akar Metode sekan dapat dijabarkan dari metode Newton dimana f ' ( xn ) =

f ( x n ) − f ( x n −1 ) x n − x n −1

Derajat Konvergensi:

• untuk metode Newton p = 2 • untuk metode sekan p = ½(1+√5) = 1,618 • untuk metode ‘bisection’ p = 1




Buku kuliah

2.4. Akar dari Persamaan Polinomial p(x) = a0 + x(a1 + x(a2+…+x(an-1 + anx)…)

(A)

p(x) = a0 + a1x + a2x2+…+ anxn

(B)

atau

Pada Pers.(A) terdapat n perkalian & pertambahan, sedangkan dalam Pers.(B) terdapat: (2n–1) perkalian & pertambahan. Oleh karena itu dalam pemrograman komputer lebih disukai bentuk dalam Pers.(A), karena lebih efisien. Pers. (A) jika ditulis dalam FORTRAN menjadi

10

p = a(n) do 10 i = n,1,-1 p = p*x + a(i–1)


Untuk menghitung akar dari persamaan p(x) = 0 akan digunakan Metoda Newton. Untuk keperluan itu polinomial p(x) akan dimodifikasi sebagai berikut Disyaratkan: bn = an bk = ak + zbk+1 , k = n–1, n–2,… , 0 Dari syarat ini p(x) dapat ditulis sebagai p(x) = b0 + (x– z)q(x) dengan q(x) = b1 + b2x +…+ bnx n-1 sehingga p’(x) = (x– z)q’(x) + q(x) p’(z) = q(z)

♦ Algoritma: Polynew (a, n, x, ε, itmax, akar, b, ier) 1. Keterangan: a adalah vektor coef. dengan dimensi n, itmax adalah iterasi maksimum, b adalah vektor coef. dari polinomial yang baru, ier adalah indikator adanya error. 2. noiter: = 1 3. x: = x0 , bn := c := an 4. Untuk k = n-1, …, 1, bk := ak+ zbk+1, c := bk + zc 5. b0:= a0 + zb1 6. Jika c = 0, ier := 2, dan ‘exit 7. x1:= x0 – b0/c 8. Jika ⏐x1 – x0⏐≤ε , ier :=0 ,akar:= x1, dan ‘exit’ 9. Jika noiter:= itmax, ier:= 1, dan ‘exit’




Buku kuliah


10. noiter:= noiter + 1, x0:= x1 , ulangi langkah ketiga.



3.

Bab TEORI INTERPOLASI

Jika kita mempunyai satu set data: (x0, y0) , (x1, y1), …, (xn, yn) maka dalam bab ini akan di jelaskan bagaimana harus mencarti polinomial yang melalui, data di atas. Jika polinomial ini ditulis sebagai: p(x) = a0 + a1x +… + anxn maka jika data diatas disubstitusikan akan didapat (n+1) persamaan dengan (n+1) variabel tidak diketahuinya yaitu: a 0 + a1 x 0 + L + a n x 0n = y 0

M a0

M + a1 x n

+ L + an x

n n

=

yn


Persamaan diatas jika diselesaikan akan menghasilkan a0, …, an sehingga polinomial p(x) dapat dicari .

3.1. Metoda Beda Terbagi Newton Notasi yang digunakan: f [xo ,x1 , ... ,x n ] =

f [x1 , ...,x n ] − f [x1 , ...,x n ] x n -x0

Contoh Order 0:

ƒ[x0] =ƒ[xn] f [x1 ] − f [x0 ] Order 1: f [x0 , x1 ] = x1 − x0 f [x1 , x 2 ] − f [x0 , x1 ] Order 2: f [x0 , x1 , x 2 ] = x 2 − x0 f [x1 , x 2 , x3 ] − f [x 0 , x1 ] Order 3: f [x0 , x1 , x 2 , x3 ] = x 2 − x0



Teori Interpolasi

Buku kuliah

Rumus beda terbagi Newton: pn(x) = ƒ[x0]+ (x3-x0)ƒ[x0,x1]+(x3-x0)(x-x1)ƒ[x0,x1]+… +(x–x0)…(x–xn-1)ƒ[ x0,x1,…,xn ] Contoh: Kita buat tabel beda terbagi berdasarkan polinomial ƒ(x) = x3 – 2x2 + 7x – 5 i 0 1 2 3

xi 0.0 1.0 3.0 4.0

Keterangan:

1 − (− 5) =6 1− 0 55 − 25 C= = 30 4−3 30 − 12 =6 E= 4 −1 A=

f[xi] -5.0 1.0 25.0 55.0

f[xi, xi+1] 6 12 30

f2[ ] 2 6

f3[ ] 1

25 − 1 = 12 3 −1 B− A D= =2 3−0 E−D F= =1 4−0 B=

Contoh hitungan pn(x=0.5) = ?

• p1(x) = -5 + (x-0)6 = 6x – 5 ∴ p1 (0.5) = -2


• p2(x) = -5 + (x-0)6 + (x-0)(x–1)2 = 2x2 + 4x – 5 ∴ p2 (0.5) = -2,5

• p3(x) = -5 + (x-0)6 + (x-0)(x–1)2 +(x-0)(x-1)(x-3)1 = x3 – 2x2 + 7x – 5 ∴ p2 (0.5) = -15/8 = - 1.875

♦ Algoritma metoda beda terbagi Newton Divdif (d, x , n) 1. Keterangan: d dan x adalah vektor f(xi) dan xi = 0,1,…,n. Pada saat ‘exit’ di akan terisi oleh nilai f [x0,…,xi] 2. Kerjakan s/d langkah 4 untuk i = 1, 2 ,… ,n 3. Kerjakan sampai dengan langkah 4 untuk j = n, n-1, i 4. dj := (dj -dj-1) /(x-xj-1) 5. ’exit’



Teori Interpolasi

Buku kuliah

Interp(d, x, t, p) 1. Keterangan: Pada awalnya d dan x adalah vektor dari ƒ[x0,…,xi] dan xi, i = 0, 1 , …, n. Pada saat ‘exit’ p akan berisi pn(t). 2. p := dn 3. Kerjakan s/d langkah 4 untuk i = n-1 , n--2, …, 0 4. p := di + (t– xi)p 5. ‘ exit’

3.2. Interpolasi dengan tabel beda hingga 3.2.1. Beda Maju Notasi: Δƒ(xi) = ƒ(xi+1) - ƒ(xi) dengan xi = x0 + ih, i = 0, 1, 2, 3, … Untuk r ≥ 0, Δr+1ƒ(z) = Δrƒ(z+h) - Δr ƒ(z) Δrƒ(z) disebut ‘ beda maju order r ,‘ Δ disebut ‘operator beda maju ‘

Δ0ƒ(x) Δƒ(x)

= ƒ(x) = Δ0ƒ(z+h) - Δ0ƒ(z) = ƒ(x+h) - ƒ(x) 2 Δ ƒ(x) = Δƒ(x+h) - Δƒ(x) Contoh hitungan : Kita gunakan polinomial x3 – 2x2 + 7x – 5 dengan h = 1,0


Contoh:

i 0 1 2 3 4

xi 0.0 1.0 2.0 3.0 4.0

f(xi) -5.0 1.0 9.0 25.0 55.0

6 8 16 30

Δ2ƒ 2 8 14

Δ3ƒ 6 6

Δ4ƒ 0

Korelasi antara ‘beda maju’ dengan ‘ beda terbagi’ f [x0 , x1 ] =


f [x1 ] − f [x0 ] f ( x 0 + h) − f ( x 0 ) Δf ( x 0 ) = = x1 − x 0 h h


Teori Interpolasi

Buku kuliah

f ( x 2 ) − f ( x1 ) f ( x1 ) − f ( x0 ) − Δ2 f ( x0 ) x 2 − x1 x1 − x0 f [x0 , x1 , x 2 ] = = x 2 − x0 2h 2 Secara umum:

f [x0 , x1 ,..., x n ] =

Δn f ( x 0 ) n! h n

Akan dijabarkan rumus interpolasi ‘beda maju’ dari rumus interpolasi ‘beda x − x0 terbagi’ Newton. Didefinisikan α = yang menunjukkan letak titik x h terhadap x0. Jadi misalnya α = 1.6, maka x terletak pada jarak 6/10 dari x1 ke arah x2. Diinginkan rumus untuk: (x – x0) (x – x1) … (x – xk) dinyatakan dalam α x – xj = x0 + αh – (x0 + jh) = (α-j)h Jadi (x – x0) (x – x1) … (x – xk) = α(α -1)… (α -k)hk+1 sehingga n 2 Δf 0 2 Δ f0 n Δ f0 + α (α − 1)h + ... + α (α − 1)...(α − n + 1)h p n ( x) = f 0 + αh h n! h n 2! h 2


Jika didefinisikan koefisien binomial sbb: ⎛ α ⎞ α (α − 1)...(α − k + 1) ⎜⎜ ⎟⎟ = , k>0 dan k! ⎝k⎠

⎛α ⎞ ⎜⎜ ⎟⎟ = 1 ⎝0⎠ maka didapat rumus interpolasi ‘beda maju’ sbb: n ⎛α ⎞ x − x0 p n ( x ) = ∑ ⎜⎜ ⎟⎟Δ j f ( x 0 ) dengan α = h j=0 ⎝ j ⎠ Contoh hitungan: p(x=1.5) = ? x − x 0 1.5 − 1.0 = = 1.5 α= h 1.0 1) p1(x) = ƒ(x0) + αΔƒ(x0) = -5 + 1.5 (6) = 4 2) p2(x) = ƒ(x0) + αΔƒ(x0) + α(α-1)∆2f(x0)/2! = -5 + 1.5 (6) + 1.5 (0.5)2/2! = 4.75



Teori Interpolasi

Buku kuliah

3.2.2. Beda Mundur ∇ƒ(z) = ƒ(z) - ƒ(z-h) ∇r+1ƒ(z) = ∇rƒ(z) - ∇rƒ(z-h)

Notasi:

rj1

Rumus interpolasinya n x − x ⎛−1−α ⎞ ⎛ j −1−α ⎞ j ⎟⎟ = 1 ⎟⎟∇ f ( x0 ) dengan α = 0 , ⎜⎜ p n ( x) = ∑ ⎜⎜ j h j =0 ⎝ ⎝ 0 ⎠ ⎠ i -4 -3 -2 -1 0

xi 0.0 1.0 2.0 3.0 4.0

f(xi) -5.0 1.0 9.0 25.0 55.0

6 8 16 30

∇ 2ƒ 2 8 14

∇ 3ƒ 6 6

∇ 4ƒ 0


Contoh hitungan: p(x=3.5) = ? x − x − 3.5 + 4.0 = = 0.5 α= 0 h 1.0 1) p1(x) = ƒ(x0) + (-α)∇ƒ(x0) = 55 + (-0.5) 30 = 40 2) p2(x) = p1(x) + (-α)(-α+1)∇2f(x0)/2! = 40 + (-0.5)(0.5)14/2! = 38.25 3) p3(x) = p2(x) + (-α)(-α+1) (-α+2)∇3f(x0)/3! = 38.25 + (-0.5)(0.5)(1.5)6/3! = 37.875

3.3. Lagrange Polinomial Lagrange dibentuk dengan fomulasi berikut: n

p n ( x ) = ∑ Li ( x ) f (xi ) i =0 n

Li ( x ) = ∑ j =0 j ≠i

x − xj xi − x j

i = 0,1,..., n

Contoh:

x − x1 x − x0 f ( x0 ) + f ( x1 ) x0 − x1 x − x01 (x − x1 )(x − x2 ) f (x ) + (x − x0 )(x − x2 ) f (x ) + (x − x0 )(x − x1 ) f (x ) p2 ( x ) = (x0 − x1 )(x0 − x2 ) 0 (x1 − x0 )(x1 − x2 ) 1 (x2 − x0 )(x2 − x12 ) 2 pi ( x ) =



Teori Interpolasi

Buku kuliah

Contoh: hitung p2 ( x ) yang melalui titik-titik (0,15); (1,1); (3,25)

( ( x − x1 )( x − x2 ) x − 1)( x − 3) x 2 − 4 x + 3 = = L0 ( x ) = (x0 − x1 )(x0 − x2 ) (0 − 1)(0 − 3) 3 2 (x − x0 )(x − x2 ) = (x − 0)(x − 3) = x − 3x L1 ( x ) = (x1 − x0 )(x1 − x2 ) (1 − 0)(1 − 3) −2 2 (x − x01 )(x − x1 ) = (x − 0)(x − 1) = x − x L2 ( x ) = (x2 − x0 )(x2 − x1 ) (3 − 0)(3 − 1) 6 Jadi p 2 (x ) = L0 ( x ) × (− 5) + L1 ( x ) × (1) + L2 ( x ) × (25) = 2 x 2 + 4 x − 5

3.4.

Beberapa fakta penting dari’beda terbagi’


1.

f (m ) (ξ ) untuk ξ ∈ X {x0 , x1 ,..., x n } m! artinya interval terkecil dimana x 0 , x1 ,..., x m tercakup! Contoh: f (0 ) (ξ ) f [x0 ] = = f ( x0 ) 0! f (x1 ) − f ( x0 ) f [x0 , x1 ] = = f ' (ξ ) ξ ∈ [x0 , x1 ] x1 − x0 1 f [x0 , x1 , x2 ] = f ' (ξ ) ξ ∈ X {x0 , x1 , x 2 } 2 f [x0 , x1 ,....., xm ] =

dimana

X {x0 ,..., x m }

2. Jika f ( x ) adalah polynomial derajad m, maka ⎧polinomial derajad m − n − 1 n < m − 1 ⎪ f [x 0 ,..., x n , x ] = ⎨a m n = m −1 ⎪0 n > m −1 ⎩ dengan f ( x ) = a m x m + a m −1 x m −1 + ... + a1 x + a0

3. Kesalahan dalam interpolasi

(x − x0 )(x − x1 )...(x − xn ) (n+1) (ξ x ) f (n + 1)! ξ x ∈ Η{x0 ,...., x n , x}

f (x ) − p n (x ) = dengan 4.

d f [x 0 ,..., x n , x ] = f [x 0 , x,..., x n , x, x ] dx



Bab

4. INTEGRASI NUMERIS

4.1. Rumus trapesium dan Simpson Pada bab ini akan dibicarakan cara menghitung integral secara numeris dari b

∫

I(f) =

f(x)dx

a

dimana [a,b] berhingga y

y=f(x) (b,f(b))


y =p1(x)

(a,f(a)) x a

b Gambar 8 Konsep integrasi trapesium

Rumus trapesium pada dasarnya adalah mendekati f(x) dengan garis lurus yang melalui (a,f(a)) dan (b,f(b)) b−a [ f (a) − f (b)] I1 ( f ) = 2



Integrasi Numeris

Buku kuliah

Error: x −a ⎧x − b ⎫ f (b)⎬ f (a) + f (x) − p1(x) = f (x) − ⎨ b −a ⎩a −b ⎭ = (x − a)(x −b) f [a,b, x]

ingat definisi ‘beda terbagi f[a,b,x]. Jadi ‘error’: b

1 E1( f ) = ∫ f (x)dx− (b − a)[f (a) + f (b)] 2 a b

= ∫(x − a)(x −b) f [a,b, x]dx a

dengan harga tengah integral, didapat: b

E1( f ) = f [a, b,ξ]∫ (x −a)(x −b)dx a ≤ξ ≤ b a

⎛1 ⎞⎛ 1 ⎞ = ⎜ f "(η)⎟ ⎜− (b −a)3 ⎟ ⎝2 ⎠⎝ 6 ⎠ 3 (b −a) =− f "(η) 12

η∈[a, b]

Jika interval [a,b] dibagi menjadi n pias sehingga untuk nj1, h = (b-a)/n dan xj = a + jh, j = 0,1,…,n, didapat: b


I(f) =

∫

f(x)dx =

xj

∑ ∫

f(x)dx

j =1 x j −1

a

=

n

n

∑

j =1

⎧h ⎫ h3 − − f ( x ) f ( x ) f " (η j ) ⎬ ⎨ j −1 j 12 ⎩2 ⎭

[

]

dengan xj-1injixj. Sehingga integralnya dapat didekati dengan 1 ⎤ ⎡1 I n ( f ) = h ⎢ f 0 + f1 + ... + f n =1 + f n ⎥ 2 ⎦ ⎣2 Kesalahan In(f) terhadap I(f) adalah En ( f ) = I ( f ) − En ( f ) n

= ∑− j =1

=−

n ≥1

h3 f " (η j ) 12

⎤ h3n ⎡ 1 n ⎢ ∑ f " (η j )⎥ 12 ⎣ n j =1 ⎦

Perlu diingat bahwa



Integrasi Numeris

Buku kuliah

Min f " ( x) ≤

a ≤ x ≤b

1 n f " ( x) ∑ f " (η j ) ≤ Max a ≤ x ≤b n j =1

karena f”(x) menerus pada a i x i b, maka h3n En ( f ) = − f " (η ) η ∈ [a, b] 12 h 2 (b − a) f " (η ) =− 12 (b − a ) 3 =− f " (η 12n 2 ~ Estimasi kesalahan asimtotis E n ( f )

Limit n →∞

En ( f ) = Limit n →∞ h2

⎡ 1 n ⎤ ⎢− ∑ f " (η j )h⎥ ⎣ 12 j =1 ⎦

=−

⎡n ⎤ 1 Limit ⎢∑ f " (η j )h ⎥ 12 n→∞ ⎣ j =1 ⎦

=−

1 f " ( x)dx 12 ∫a

b


h2 ~ maka En ( f ) ≡ − { f ' (b) − f ' (a )} 12 Definisi: ~ Jika En(f) adalah kesalahan eksak, sedangkan En ( f ) adalah estimasi darinya, maka ~ En ( f ) disebut estimasi kesalahan asimtotis dari En(f) jika: ~ ~ En ( f ) En ( f ) − En ( f ) = 1 atau Limit =0 Limit n →∞ E ( f ) n →∞ En ( f ) n

4.1.1. Rumus trapesium terkoreksi ~ Dengan menggunakan En ( f ) , rumus trapesium dapat ditingkatkan menjadi: ~ CTn ( f ) = I n ( f ) + E n ( f )

1 ⎤ h2 ⎡1 = h ⎢ f 0 + f1 + ... + f n =1 + f n ⎥ − { f ' (b) − f ' (a )} 2 ⎦ 12 ⎣2



2. PERSAMAAN NON-LINIER

Recommend Documents