Modul7.pdf

Modul 7 METODE NEWTON-RAPHSON (Tangent) untuk Solusi Akar PERSAMAAN ALJABAR NON-LINIER TUNGGAL

A. Pendahuluan Pada modul terdahulu, walaupun kecepatan konvergensi telah dapat ditingkatkan secara lumayan berarti pada metode Regula-Falsi, namun pada dasarnya metode tersebut masih memiliki kelemahankelemahan terutama dari persyaratan posisi-posisi harga awalnya (relatif terhadap solusi eksaknya), dan juga cara menebak 2 buah harga awal yang memenuhi persayaratan domain jawab. Di samping itu juga, kecepatan konvergensi superlinier (antara linier dan kuadratis) dari metode Regula-Falsi diperoleh dengan cara perolehan solusi pendekatan di sekitar domain jawab ataupun akar eksak dari grafik y = f (x) dengan bantuan sebuah garis lurus. Dalam modul 7 ini akan dibahas suatu metode solusi baru untuk PANLT yang bekerja berdasarkan GARIS TANGENT (garis singgung) yang menyinggung kurva y = f (x) di suatu titik, sedemikian rupa sehingga akar dari garis lurus yang terbentuk dapat digunakan untuk melakukan pendekatan pada akar eksak dari PANLT (x*) yang dimaksud. Metode ini dikenal seagai Metode Newton-Raphson, yang kinerjanya relatif jauh lebih cepat dalam mencapai konvergensi, karena memiliki laju konvergensi kuadrat. Namun, agar supaya metode ini dapat bekerja dengan baik, harus dipenuhi beberapa persyaratan berikut: ð 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,

Seri Kuliah Metode Numerik (Modul 7: Metode Newton-Raphson untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)

(1/1)

ð Turunan fungsi tersebut tidak berharga nol, y ≠ 0 , pada harga '

xk (pada iterasi ke-k) yang diinginkan, ð Kriteria penghentian iterasi dilakukan bilamana SALAH SATU

syarat berikut telah dipenuhi: (a). Selisih harga xk (pada iterasi terbaru) dengan xk-1 (pada iterasi sebelumnya) lebih kecil atau sama dengan harga ε, atau dapat dituliskan sebagai: ∆xk ≤ ε , atau (b). 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: f ( xk ) ≤ ε B. Solusi Akar PANLT dengan Metode Newton-Raphson Solusi akar (atau akar-akar) dengan menggunakan Metode NewtonRaphson, secara sederhana, dapat diturunkan dari geometri gambar di bawah ini:

Gambar 7.1. Representasi garis tangent pada metode Newton-Raphson.

Seri Kuliah Metode Numerik (Modul 7: Metode Newton-Raphson untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)

(2/2)

Garis tangent yang dimaksudkan pada Gb. 7.1. di atas adalah garis AC, yang berarti juga bahwa tangent dari ∠ CAB (sudut CAB) dapat dituliskan sebagai berikut: CB AB Bila diperhatikan pada gambar di atas, maka akan diperoleh kesamaan-kesamaan berikut: tan(∠ CAB) =

CB =

f ( xn ) − 0 =

AB =

xn − xn +1 , dan

tan(∠ CAB) =

f ( xn )

f ' ( xn )

Sehingga, persamaan tan(∠ CAB) dapat ditulis kembali sebagai: f ( xn ) xn − xn +1

f ' ( xn ) =

atau setelah disusun-ulang, akan diperoleh formula rekursif dari Metode Newton-Raphson: xn +1

=

xn −

f ( xn )

f ' ( xn )

Formula rekursif di atas juga dapat diperoleh dengan cara pengembangan pengembangan deret Taylor pada titik xn, sebagai berikut: f (x ) =

f ( xn ) + ( x − xn ) ⋅ f ( xn ) + '

( x − xn )2 2

f " (ξ ) + L

dengan ξ berada di antara x dan xn. Kemudian, pada saat tercapai solusi eksak, atau x = α , yang berarti juga bahwa f ( x) = 0 , maka akan deperoleh rumus rekursif berikut: α

=

xn −

f ( xn )

f ' ( xn )

−

(α − xn )2 ⋅ f " (ξ n ) 2 f ( xn )

−L

Seri Kuliah Metode Numerik (Modul 7: Metode Newton-Raphson untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)

(3/3)

Dari persamaan di atas, jika iterasi masih atau sedang berlangsung maka formula Newton-Raphson yang lengkap (dengan formula sesatannya) akan diperoleh sebagai berikut: xn +1

=

2  Term  (α − xn ) ⋅



2

xn −

f ( xn )

f ' ( xn )

 f " (ξ n ) + L f (xn ) 

 (α − xn )2 f " (ξ n )  −  ⋅ + L 2 f ( xn )  

merupakan term ‘ketelitian’ dari formula

rekursif perhitungan yang dikembangkan dari deret Taylor, namun dengan alasan bahwa term tersebut juga sekaligus berperan sebagai sesatan (error) dari formula Newton-Raphson, maka Metode Newton-Raphson tersebut di atas sekaligus dapat dikatakan memiliki LAJU KONVERGENSI KUADRATIS, karena adanya term (α − xn )2 .

C. Algoritma Metode Newton-Raphson Berbeda dengan metode-metode sebelumnya, bahkan berbeda dengan Metode Secant yang akan dibahas pada Modul 8, Metode Newton-Raphson ini hanya membutuhkan ‘tebakan’ 1 buah harga awal yang seharusnya terletak di sekitar DOMAIN JAWAB (secara intuitif) nilai akar α, sedemikian rupa sehingga formula tersebut konvergen (menuju ke titik jawab). Hal lain yang harus diperhatikan adalah bahwa Metode NewtonRaphson ini memberikan beban tambahan kepada penggunanya, karena adanya keharusan menghitung fungsi turunan f ' ( xn ) , di setiap iterasi (titik xn ). Hal ini merupakan salah satu kekurangan dari metode ini, mengingat tidak semua fngsi dapat diturunkan atau mempunyai turunan pada suatu interval yang kontinyu. Namun, sekali lagi, analisis tentang kelemahan metode ini masih dapat diterima mengingat kecepatan konvergensinya yang relatif paling baik. Secara ringkas, algoritma Newton-Raphson yang secara prinsip Seri Kuliah Metode Numerik (Modul 7: Metode Newton-Raphson untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)

(4/4)

diambil dari Atkinson (1978), adalah sebagai berikut:

Algoritma NEWRAP(f,df,xold,x,ε,iter,itmax,flag) 1. Set harga variabel-variabel: iter = 0, flag = 0; 2. Set x = xold; 3. x = x - f(x)/df(x); 4. Set iter = iter + 1; 5. Jika abs(x – xold) ≤ ε maka flag = 1 atau jika iter > itmax maka flag = 2 atau jika tidak maka xold = x; 6. Jika flag = 0 ulangi ke nomor 3; 7. Selesai.

Perhatikan dengan baik-baik: bahwa algoritma di atas tidak memperhitungkan adanya kemungkinan harga fungsi turunan yang berharga nol ( f ' ( x) = df ( x) = 0 ). Cobalah analisis atau beri komentar saudara tentang masalah tersebut ! Jika saudara berpendapat harus ada peringatan tentang bahaya fungsi turunan yang berharga nol, bagaimanakah bentuk algoritmanya menurut saudara ?

Adapun ringkasan umum tentang sifat dan karakteristik metode ini adalah sebagai berikut: ð Memerlukan 1 harga awal (≡ x0) ð Konvergensi Kuadrat (paling cepat) ð Sesuai untuk fungsi dan turunannya yang terdefinisi dengan

jelas (≡ kontinyu dan dapat diturunkan pada xn); sebaliknya akan menjadi kendala bila fungsinya dan turunannya tidak jelas ð Divergen bila f ′( xn ) = 0 (≡ titik optimum) Seri Kuliah Metode Numerik (Modul 7: Metode Newton-Raphson untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)

(5/5)

ð Kriteria penghentian iterasi : ∆xn ≤ ε dan atau

f ( xn ) ≤ ε .

Adapun tabel kerja dari metode ini (sesuai dengan algoritmanya), dapat disajikan secara sistematis sebagai berikut: Tabel 7.1. Tabel Kerja Metode Newton-Raphson

n

xn

f(xn)

f’(xn)

0

…

…

…

1

…

…

…

…

…

…

…

D. Listing Program Metode Newton-Raphson Seperti juga problem yang sama pada modul sebelumnya, diberikan persoalan untuk menghitung akar (akar-akar) persamaan f(x) = 0, sebagai berikut: f ( x) ≡

x − e1 x

= 0

Listing program sederhana (non-subroutine) dan program dengan subroutine untuk Metode Newton-Raphson disertakan dalam gambar-gambar 7.2. dan 7.3. di bawah ini, yang ditulis dalam Bahasa FORTRAN 77 (kompatibel dengan Bahasa FORTRAN 90/95): C C C C C C C C

Program: Solusi Persamaan Aljabar Non-Linier Tunggal (PANLT) dengan Metode 'Newton-Raphson' VARIAN: Program sederhana/Non-Subroutine Kondisi proses dinyatakan dalam variabel 'flag' flag = 0; berarti sistem masih dalam proses iterasi flag = 1; berarti proses telah mencapai konvergensi flag = 2; berarti jumlah iterasi maksimum telah terlampaui ------------------------------------------------------------implicit none REAL*8 eps,f,df,x,xold INTEGER flag,iter,maxiter

Seri Kuliah Metode Numerik (Modul 7: Metode Newton-Raphson untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)

(6/6)

WRITE(*,'(A,$)') 'Harga awal untux x (x0) : ' READ(*,*) xold WRITE(*,'(A,$)') 'Jumlah iterasi maksimum : ' READ(*,*) maxiter WRITE(*,'(A,$)') 'Epsilon/kriteria proses : ' READ(*,*) eps iter = 0 flag = 0 x = xold DO WHILE(flag .EQ. 0) x = x - f(x)/df(x) IF (ABS(x - xold) .LE. eps) THEN flag = 1 ELSEIF (iter .GT. maxiter) THEN flag = 2 ELSE iter = iter + 1 xold = x ENDIF ENDDO WRITE(*,*) WRITE(*,*) WRITE(*,*) WRITE(*,*) WRITE(*,*) WRITE(*,*)

'xold = ',xold 'x = ',x 'f(x) = ',f(x) 'df(x) = ',df(x) 'Flag = ',flag 'Jumlah iterasi = ',iter

STOP END

FUNCTION f(x) REAL*8 f,x f = x - exp(1.0D0/x) RETURN END

FUNCTION df(x) REAL*8 df,x df = 1.0D0 + exp(1.0D0/x)/(x**2) RETURN END

Gambar 7.2. Listing program Newton-Raphson sederhana (tanpa subroutine).

Seri Kuliah Metode Numerik (Modul 7: Metode Newton-Raphson untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)

(7/7)

C C C C C C C C

Program: Solusi Persamaan Aljabar Non-Linier Tunggal (PANLT) dengan Metode 'Newton-Raphson' VARIAN: Program dengan Subroutine Kondisi proses dinyatakan dalam variabel 'flag' flag = 0; berarti sistem masih dalam proses iterasi flag = 1; berarti proses telah mencapai konvergensi flag = 2; berarti jumlah iterasi maksimum telah terlampaui ------------------------------------------------------------implicit none external f,df REAL*8 eps,f,df,x,xold INTEGER flag,iter,maxiter WRITE(*,'(A,$)') 'Harga awal untux x (x0) : ' READ(*,*) xold WRITE(*,'(A,$)') 'Jumlah iterasi maksimum : ' READ(*,*) maxiter WRITE(*,'(A,$)') 'Epsilon/kriteria proses : ' READ(*,*) eps iter = 0 flag = 0 x = xold CALL NEWRAP(f,df,xold,x,eps,iter,maxiter,flag) WRITE(*,*) WRITE(*,*) WRITE(*,*) WRITE(*,*) WRITE(*,*) WRITE(*,*)

'xold = ',xold 'x = ',x 'f(x) = ',f(x) 'df(x) = ',df(x) 'Flag = ',flag 'Jumlah iterasi = ',iter

STOP END

C C C C C C C C C C C C C C

SUBROUTINE NEWRAP(ff,dff,xold,x,eps,itnum,itmax,prflag) -------------------------------------------------------Sub-program: Solusi PANLT dengan metode NEWTON-RAPHSON | ff : fungsi f(x) = 0 yang akan dicari akarnya | xold : nilai x-awal di sebelah kiri akar f(x) | x : akar f(x), nilai paruh (antara x0 dan x1) | eps : kriteria atau ketelitian penghitungan | itnum : jumlah iterasi yang dilakukan proses | itmax : jumlah pembatas iterasi untuk proses | prflag : identifikasi untuk konvergensi, yaitu: | 0 = proses sedang/akan berlangsung | 1 = proses mencapai konvergensinya | 2 = jumlah iterasi maksimum (itmax) telah | terlampaui | -------------------------------------------------------REAL*8 eps,ff,dff,x,xold INTEGER prflag,itnum,itmax itnum = 0

Seri Kuliah Metode Numerik (Modul 7: Metode Newton-Raphson untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)

(8/8)

prflag = 0 x = xold DO WHILE(prflag .EQ. 0) x = x - ff(x)/dff(x) itnum = itnum + 1 IF (ABS(x - xold) .LE. eps) THEN prflag = 1 ELSEIF (iter .GT. itmax) THEN prflag = 2 ELSE xold = x ENDIF ENDDO RETURN END

FUNCTION f(x) REAL*8 f,x f = x - exp(1.0D0/x) RETURN END

FUNCTION df(x) REAL*8 df,x df = 1.0D0 + exp(1.0D0/x)/(x**2) RETURN END

Gambar 7.3. Listing program dengan subroutine.

Perhatikan sekali lagi dengan baik-baik: bahwa programprogram di atas juga tidak memperhitungkan adanya kemungkinan harga fungsi turunan yang berharga nol ( f ' ( x) = df ( x) = 0 ) ! Bila saudara anggap perlu, coba perbaiki atau modifikasi programprogram di atas, agar supaya masalah fungsi turunan yang berharga nol dapat dihindari !

Seri Kuliah Metode Numerik (Modul 7: Metode Newton-Raphson untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)

(9/9)

Tugas: Cari akar (akar-akar) dari persamaan-persamaan berikut: (a). f ( x) = e − x ⋅ ln( x) (b). f ( x) =

x 6 − x − 1 dan −B x2

(c). f ( x) = x + e cos( x) ; dengan harga-harga B = 1, 5, 10, 25 dan 50. Analisislah hasil-hasilnya.

E. Pustaka yang bersesuaian Atkinson, Kendal E., “An Introduction to Numerical Analysis”, John Wiley & Sons, Toronto, pp. 52-58, 1978. Atkinson, L.V., Harley, P.J., “An Introduction to Numerical Methods with Pascal”, Addison-Wesley Publishing Co., Tokyo, pp. 63-67, 1983. Bismo, Setijo, “Modul Kuliah Metode Numerik”, TGP-FTUI, 1999.

Seri Kuliah Metode Numerik (Modul 7: Metode Newton-Raphson untuk Solusi PANLT (Persamaan Aljabar Non-Linier Tunggal)

(10/10)