Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
PAM 252 Metode Numerik Bab 2 Persamaan Nonlinier Mahdhivan Syafwan Jurusan Matematika FMIPA Universitas Andalas
Semester Genap 2016/2017
1
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Solusi persamaan nonlinier Dua tipe metode
Solusi persamaan nonlinier Misalkan f : [a, b] → R, a < b. Kita ingin menentukan x ∈ [a, b] sedemikian sehingga f (x) = 0. Pada prakteknya, solusi dari f (x) = 0 (disebut juga akar dari f (x)) sulit untuk diselesaikan secara analitik, sehingga diperlukan metode numerik. Metode numerik untuk pencarian akar suatu fungsi pada umumnya merupakan metode iterasi. 1
2
3
2
Tentukan satu atau beberapa tebakan awal terhadap akar dari f (x). Terapkan suatu rumus iterasi/rekursif tertentu yang akan membangkitkan barisan bilangan x0 , x1 , x2 , ... yang diharapkan konvergen ke akar yang ingin dicari. Tetapkan kriteria penghentian iterasi. Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Solusi persamaan nonlinier Dua tipe metode
Dua tipe metode Ada dua tipe metode numerik dalam mencari akar suatu fungsi: Metode pengurung akar yang dicari selalu diapit/dikurung di dalam suatu interval → interval pengapit akar dibuat makin lama makin pendek. Metode terbuka akar tidak perlu diapit. Masing-masing metode mempunyai kelebihan dan kekurangan (akan dibahas nanti).
3
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode bagi dua - dasar teori Teorema Nilai Antara Misalkan f : [a, b] → R adalah fungsi kontinu dan L adalah sebarang titik antara f (a) dan f (b). Maka terdapat c ∈ (a, b) sedemikian sehingga f (c) = L. Bukti detailnya akan diberikan pada kuliah Analisis Riil.
4
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode bagi dua - dasar teori Teorema Bolzano Misalkan a < b, f : [a, b] → R adalah fungsi kontinu, dan f (a)f (b) < 0. Maka terdapat c ∈ (a, b) sedemikian sehingga f (c) = 0. Bukti. Teorema ini adalah kasus khusus dari Teorema Nilai Antara dengan L = 0.
5
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode bagi dua - penerapan
6
1
Tentukan dua buah titik, misalkan a dan b dengan a < b, yang nilai fungsinya berlawanan tanda, yaitu f (a)f (b) < 0. Kedua titik ini merupakan tebakan awal pada metode bagi dua.
2
Berdasarkan Teorema Bolzano, interval [a, b] akan memuat akar f (x).
3
Tetapkan titik tengah dari interval [a, b], sebut titik c. Jadi c = a+b 2 .
4
Ada (a) (b) (c)
5
Jika kasus (a) terjadi, maka proses selesai. Jika kasus (b) atau (c) terjadi, interval pengapit akar dinamakan sebagai a dan b yang baru, lalu ulangi proses yang sama pada iterasi selanjutnya.
tiga kemungkinan yang akan terjadi: f (c) = 0, artinya titik c adalah akar dari f (x) f (a)f (c) < 0, artinya akar berada pada interval [a, c] f (b)f (c) < 0, artinya akar berada pada interval [c, b]
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode bagi dua - ilustrasi
7
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode bagi dua - kekonvergenan & penghentian iterasi Apabila pada setiap langkah iterasi, variabel a, b, c diberi indeks (dimulai dari nol), maka pada iterasi ke-k diperoleh rumus iterasi ck =
ak + bk , 2
k = 0, 1, 2, ...
Dapat ditunjukkan bahwa bk − ak =
b0 −a0 . 2k
[justifikasi!]
Karena akar r dari fungsi f (x) berada pada interval [ak , bk ], maka bk − ak b0 − a0 = k+1 . 2 2 Hubungan di atas menunjukkan bahwa barisan {ck } akan konvergen ke akar r . [buktikan!] |ck − r | ≤
Kriteria penghentian iterasi yang dapat digunakan adalah (bk − ak ) < ǫ, dimana ǫ adalah batas galat yang ditentukan. Q: Jika diberikan ǫ, berapa banyak iterasi yang dibutuhkan? 8
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode bagi dua - algoritma
9
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode bagi dua - algoritma Masukan:
f(x) a, b eps
fungsi yang dicari akarnya tebakan awal batas galat
Keluaran: r akar dari fungsi f(x) Langkah-Langkah : 1. fa:=f(a) 2. fb:=f(b) 3. jika fa*fb > 0 maka “proses gagal”, stop 4. c:=(a+b)/2 5. fc:=f(c) 6. jika fa*fc < 0 6. selagi (b-a) >= eps maka b:=c jika fa*fc < 0 fb:=fc maka b:=c jikatidak fb:=fc jika fa*fc > 0 jikatidak maka a:=c jika fa*fc > 0 fa:=fc maka a:=c jikatidak fa:=fc r:=c, selesai jikatidak 7. jika (b-a) < eps r:=c, selesai maka r:=c, selesai c:=(a+b)/2 8. kembali ke langkah 4 fc:=f(c) 7. r:=c
Untuk ..., variabel vektor (berindeks) tidak digunakan, karena ... 9
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode bagi dua - seberapa bagus?
Robust - selalu konvergen (asalkan syarat-syaratnya terpenuhi). Akurat - hampiran solusi dapat ditingkatkan keakuratannya dengan meningkatkan jumlah iterasinya dan estimasi galat dapat dihitung di setiap iterasi. Efisien - hampiran solusi diperoleh dalam waktu yang relatif singkat - beban kerja komputasi yang diperlukan relatif ringan.
10
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode posisi palsu - penerapan Metode posisi palsu (dikenal juga dengan metode regula falsi) dikembangkan agar memiliki kekonvergenan yang lebih cepat daripada metode bagi dua. 1
Tentukan tebakan awal a, b dengan f (a)f (b) < 0.
2
Buat garis lurus yang menghubungkan titik (a, f (a)) dan (b, f (b)). Garis ini akan memotong sumbu-x dengan titik potongnya, sebut titik c, terletak di antara a dan b. [mengapa?]
3
Dapat ditunjukkan bahwa c = b − f (b)
11
b−a . [justifikasi!] f (b) − f (a)
4
Akar fungsi akan terapit oleh salah satu dari interval [a, c] atau [c, b].
5
Untuk iterasi selanjutnya, interval pengapit akar dinamakan sebagai a dan b yang baru dan proses yang sama diulangi lagi. Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode posisi palsu - ilustrasi
12
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode posisi palsu - kekonvergenan & penghentian iterasi
Apabila pada setiap langkah iterasi, variabel a, b dan c diberi indeks (dimulai dari nol), maka pada iterasi ke-k diperoleh rumus iterasi ck = bk − f (bk )
bk − ak , f (bk ) − f (ak )
k = 0, 1, 2, ...
Sebagai kriteria penghentian iterasi, dapat digunakan |ck+1 − ck | < ǫ, dimana ǫ adalah batas galat. Q: Dapatkah kriteria penghentian iterasi pada metode bagi dua diterapkan pada metode posisi palsu?
13
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode posisi palsu - algoritma
14
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode posisi palsu - algoritma Masukan:
f(x) a, b eps
fungsi yang dicari akarnya tebakan awal batas galat
Keluaran: r akar dari fungsi f(x) Langkah-Langkah : 1. fa:=f(a) 2. fb:=f(b) 3. jika fa*fb > 0 maka “proses gagal”, stop 4. clama:=2*b-a (mengapa? bisa yang lain?) 5. c:=b-fb*(b-a)/(fb-fa) 7. selagi abs(c-clama) >= eps 6. fc:=f(c) jika fa*fc < 0 7. jika fa*fc < 0 maka b:=c maka b:=c fb:=fc fb:=fc jikatidak jikatidak jika fa*fc > 0 jika fa*fc > 0 maka a:=c maka a:=c fa:=fc fa:=fc jikatidak jikatidak r:=c, selesai r:=c, selesai clama:=c 8. jika abs(c-clama) < eps c:=b-fb*(b-a)/(fb-fa) maka r:=c, selesai fc:=f(c) 9. clama:=c 8. r:=c 10. kembali ke langkah 5
14
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode posisi palsu - beberapa catatan
Pada algoritma sebelumnya, untuk ...., pemakaian variabel vektor (berindeks) kembali dihindari karena ... Apa tujuan dari langkah 4 pada algoritma sebelumnya? Apakah nilai awal dari variabel clama dapat diambil yang lain? Jelaskan! Secara umum metode posisi palsu mempunyai kekonvergenan yang lebih cepat daripada metode bagi dua. Namun, ada beberapa kelas fungsi tertentu dimana keadaan berlaku sebaliknya (lihat pembahasan metode modifikasi posisi palsu).
15
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Contoh Terapkan metode bagi dua dan metode posisi palsu dalam menentukan akar dari x sin(x) − 1 = 0 dengan tebakan awal a = 0, b = 2 dan batas galat 0.2 (untuk masing-masing metode, tuliskan rincian hitungannya dan letakkan hasilnya dalam sebuah tabel).
16
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Masalah tebakan awal/lokalisasi akar Cara untuk (membantu) menentukan tebakan awal: Tabulasi nilai - membuat tabel nilai dari fungsi f (x) pada beberapa titik tertentu, lalu ... Menggambar grafik Grafik tunggal - gambarkan grafik f (x) di bidang x − y , lalu ... Grafik ganda - pecah fungsi f (x) menjadi f (x) = g (x) − h(x), gambarkan grafik g (x) dan h(x) pada bidang x − y yang sama, lalu ...
Beberapa kesulitan dalam mencari lokasi akar [jelaskan!]: (a) Adanya dua akar yang lokasinya sangat berdekatan (b) Adanya akar kembar Metode alternatif untuk mengatasi kesulitan di atas dapat dijadikan topik tugas akhir! KASUS KHUSUS: Lokalisasi akar polinom [tugas baca!] 17
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Masalah kekonvergenan pada metode posisi palsu
18
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Bagaimana mengatasinya? Lakukan modifikasi (metode modifikasi posisi palsu): bila selama dua atau lebih iterasi yang berturutan, salah satu ujung interval pengapit akar tidak mengalami perubahan, maka nilai fungsi pada titik tersebut dibuat menjadi setengah dari nilai pada iterasi sebelumnya.
19
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode modifikasi posisi palsu - algoritma
20
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode bagi dua Metode posisi palsu Masalah tebakan awal/lokalisasi akar Metode modifikasi posisi palsu
Metode modifikasi posisi palsu - algoritma
20
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode Newton-Raphson - dasar teori
Teorema Taylor Misalkan n ∈ N, I = [a, b], dan f : I → R sedemikian sehingga f dan turunannya f ′ , f ′′ , ..., f (n) kontinu pada I dan f (n+1) ada pada (a, b). Jika x˜ ∈ I , maka untuk sebarang x ∈ I terdapat titik c di antara x dan x˜ sedemikian sehingga f ′′ (˜ x) (x − x˜)2 f (x) = f (˜ x ) + f ′ (˜ x )(x − x˜) + 2! f (n+1) (c) f (n) (˜ x) (x − x˜)n + (x − x˜)n+1 . +···+ n! (n + 1)! Bukti detailnya akan diberikan pada kuliah Analisis Riil.
21
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode Newton-Raphson - dasar teori Teorema (Metode Newton) Misalkan I = [a, b] dan f : I → R dapat diturunkan dua kali pada I . Andaikan f (a)f (b) < 0 dan terdapat konstanta m dan M sehingga |f ′ (x)| ≥ m > 0 dan |f ′′ (x)| ≤ M untuk x ∈ I dan misalkan K = M/2m. Maka terdapat subinterval I ∗ yang memuat akar r dari persamaan f (x) = 0 sedemikian sehingga untuk sebarang x0 ∈ I ∗ , barisan {xk } yang didefinisikan dengan xk+1 = xk −
f (xk ) untuk setiap k ∈ N ∪ {0}, f ′ (xk )
(1)
ada di I ∗ dan {xk } konvergen ke r . Lebih lanjut, |xk+1 − r | ≤ K |xk − r |2 untuk setiap k ∈ N ∪ {0}. Bukti detailnya akan diberikan pada kuliah Analisis Riil. 22
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
(2)
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode Newton-Raphson - penerapan Misalkan f (x) fungsi kontinu dan x0 adalah tebakan awal terhadap akar dari fungsi tersebut. Buat garis singggung terhadap fungsi f (x) (yaitu f ′ (x)) di titik (x0 , f (x0 )). Jika f ′ (x0 ) 6= 0, maka garis singgung tersebut akan memotong sumbu-x. [mengapa?] Misalkan titik potongnya adalah x1 . Dapat dibuktikan bahwa x1 = x0 − ff′(x(x00)) . [justifikasi secara aljabar dan geometrik!] Selanjutnya proses yang sama dilakukan dengan tebakan awal yang baru, yaitu x1 . Apabila proses ini diteruskan, maka akan diperoleh barisan x0 , x1 , x2 , ..., xk , ... dengan xk+1 = xk −
f (xk ) . f ′ (xk )
Q: Tunjukkan bahwa jika barisan {xk } konvergen, maka limitnya adalah akar dari f (x). 23
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode Newton-Raphson - ilustrasi
24
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode NR - kekonvergenan dan penghentian iterasi Perhatikan kembali pertaksamaan (2) pada Teorema Metode Newton. Misalkan Ek = xk − r adalah galat pada iterasi ke-k. Maka pertaksamaan (2) dapat ditulis |Ek+1 | ≤ K |Ek |2 . Akibatnya, jika |Ek | < 10−m , maka |Ek+1 | < 10−2m K . Dari kenyataan ini, metode Newton-Raphson dikatakan memiliki kekonvergenan kuadratik. Kriteria penghentian iterasi yang dapat dipakai adalah |xk+1 − xk | < ǫ, dimana ǫ adalah batas galat. [kriteria penghentian iterasi yang lain?] Metode Newton-Raphson tidak menjamin proses akan konvergen. Untuk mengatasi terjadinya looping karena proses yang tidak konvergen, maka perlu untuk memberi batas jumlah maksimum iterasinya (hal ini juga merupakan kriteria penghentian iterasi pada metode NR). 25
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Kegagalan metode Newton-Raphson
(a) xk → ∞
(b) xk berosilasi
(c) f ′ (xk ) = 0 atau f ′ (xk ) ≈ 0 26
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode Newton-Raphson - algoritma
27
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode Newton-Raphson - contoh Terapkan metode Newton-Raphson pada fungsi f (x) = x 3 − 3x + 2 dengan tebakan awal x0 = −2.4 dengan batas galat 0.001. Lakukan hal yang sama tetapi dengan tebakan awal 1.2. Apa kesimpulan Anda?
Kesimpulan: Permasalahannya terletak pada bentuk kecekungan fungsi di sekitar akar yang dicari. Fungsi f (x) = x 3 − 3x + 2 memiliki akar eksak x = −2 dengan multiplisitas satu dan x = 1 dengan multiplisitas dua (akar ganda). Metode Newton-Raphson akan lebih lambat konvergen bila akar yang dicari mempunyai multiplisitas lebih dari satu. Mengapa? 28
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Orde kekonvergenan Definisi (orde kekonvergenan) Misalkan barisan {xk }∞ k=0 konvergen ke akar r dari fungsi f (x) dan Ek = r − xk . Jika terdapat konstanta A 6= 0 dan R > 0 dengan |Ek+1 | |r − xk+1 | = lim = A, R k→∞ |Ek |R k→∞ |r − xk | lim
(3)
maka barisan {xk }∞ k=0 disebut konvergen ke r dengan orde kekonvergenan R. Khusus untuk kasus R = 1, 2 berlaku istilah berikut: Jika R = 1, kekonvergenan dari {xk }∞ k=0 dikatakan linier Jika R = 2, kekonvergenan dari {xk }∞ k=0 dikatakan kuadratik.
29
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode Newton-Raphson - orde kekonvergenan Sifat (orde kekonvergenan metode Newton-Raphson) Misalkan iterasi Newton-Raphson menghasilkan barisan {xk }∞ k=0 yang konvergen ke akar r dari fungsi f (x). Jika r adalah akar sederhana (multiplisitas 1), maka |f ′′ (r )| 2 untuk k yang cukup besar. |Ek+1 | ≈ 2|f ′ (r )| |Ek | Jika r adalah akar dengan multiplisitas M, maka |Ek+1 | ≈ untuk k yang cukup besar.
M−1 M |Ek |
Bukti. ...
30
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode Newton-Raphson - pemercepat kekonvergenan TUGAS! Baca dan tulis kembali artikel ”Pemercepat Kekonvergenan” (download dari portal) dengan menjelaskan secara lebih detail perhitungan pada contoh dalam artikel tersebut. Tuliskan algoritmanya.
31
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode Newton-Raphson - hal khusus dan menarik Khusus untuk polinom, perhitungan pada rumus iterasi Newton-Raphson dapat dibuat lebih singkat dan akurat (proses pembulatan di komputer lebih sedikit). −→ tugas baca: ”Modifikasi Metode NR untuk Polinom”. Untuk fungsi dua peubah f (x, y ), akar-akar dari fungsi tersebut dapat dicari dengan memvariasikan salah satu nilai variabel, katakanlah x. Kemudian untuk setiap x dicari solusi untuk y dengan menggunakan metode Newton-Raphson. Namun, masalah muncul apabila terdapat lebih dari satu solusi untuk y sedangkan domain x terbatas (dalam konteks masalah persamaan diferensial, fenomena ini disebut bifurkasi). Contoh: y 2 + x − 5 = 0. −→ salah satu metode alternatif adalah metode pseudo-arc-length. Untuk fungsi kompleks (polinomial), jumlah iterasi yang dibutuhkan oleh metode Newton-Raphson agar konvergen ke salah satu akar dapat menghasilkan suatu gambar yang artistik. 32
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode Newton-Raphson - hal khusus dan menarik
33
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode tali busur - penerapan Metode tali busur (dinamakan juga metode sekan) merupakan pengembangan dari metode Newton Raphson sedemikian sehingga tidak perlu mencari turunan dari fungsi yang akan dicari akarnya. Tentukan dua tebakan awal x0 dan x1 terhadap akar dari fungsi f (x) [tidak perlu mengapit akar]. Lakukan proses iterasi seperti pada metode Newton-Raphson, f (x )−f (x ) kecuali untuk f ′ (xk ) yang dimodifikasi menjadi xkk −xk−1k−1 [mengapa?]. Jadi rumus iterasi pada metode tali busur adalah xk+1 = xk − f (xk )
xk − xk−1 , f (xk ) − f (xk−1 )
k = 1, 2, ...
Q: Misalkan {xk } adalah barisan yang dihasilkan oleh iterasi tali busur untuk menghampiri akar dari f (x). Jika barisan tersebut konvergen, tunjukkan bahwa limitnya adalah akar dari f (x). 34
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode tali busur - ilustrasi
35
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode tali busur - kekonvergenan & penghentian iterasi Sifat (orde kekonvergenan metode tali busur) Misalkan r adalah akar sederhana (multiplisitas 1) dari fungsi f (x) dan {xk }∞ k=0 adalah barisan yang dihasilkan dari iterasi tali busur dan f ′′ (r ) 0,618 k+1 | dengan konvergen ke r . Misalkan Ek = r − xk . Maka |E ≈ 2f ′ (r ) R |Ek | R=
√ 1+ 5 2 .
Bukti. ... Dibandingkan metode Newton-Raphson, metode tali busur mempunyai kekonvergenan yang lebih lambat, tetapi masih lebih cepat dari metode bagi dua dan posisi palsu. Kriteria penghentian iterasi dari metode tali busur adalah |xk+1 − xk | < ǫ, dimana ǫ adalah batas galat. Q: Apakah perlu juga untuk membatasi jumlah maksimum iterasi pada metode ini? 36
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode Newton-Raphson (NR) Metode tali busur/sekan
Metode tali busur - algoritma
37
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier
Pendahuluan Metode pengurung Metode terbuka Perbandingan dua metode
Metode pengurung vs metode terbuka Metode Pengurung
38
Metode Terbuka
Selama proses iterasi, akar fungsi selalu diapit interval
Selama proses iterasi, akar fungsi tidak perlu diapit interval
Proses pasti konvergen
Proses tidak selalu konvergen
Kekonvergenan lebih lambat
Kekonvergenan lebih cepat
Mahdhivan Syafwan
Metode Numerik: Persamaan Nonlinier