Metode Newton

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas

Dalam analisis numerik, metode Newton (juga dikenal sebagai metode Newton–Raphson), yang mendapat nama dari Isaac Newton dan Joseph Raphson, merupakan metode yang paling dikenal untuk mencari hampiran terhadap akar fungsi riil. Metode Newton sering konvergen dengan cepat, terutama bila iterasi dimulai "cukup dekat" dengan akar yang diinginkan. Namun bila iterasi dimulai jauh dari akar yang dicari, metode ini dapat meleset tanpa peringatan. Implementasi metode ini biasanya mendeteksi dan mengatasi kegagalan konvergensi.

Diketahui fungsi dan turunannya , kita memulai dengan tebakan pertama, . Hampiran yang lebih baik untuk adalah

.

Deskripsi[sunting | sunting sumber]

Ilustrasi salah satu iterasi metode Newton (fungsi ƒ ditunjukkan dengan warna biru dan garis singgung dalam warna merah). Kita melihat bahwa xn+1 adalah hampiran yang lebih baik daripada xnuntuk akar x dari fungsi f.

Gagasan metode ini adalah sebagai berikut: kita memulai dengan tebakan awal yang cukup dekat terhadap akar yang sebenarnya, kemudian fungsi tersebut dihampiri dengan garis singgungnya (yang dapat dihitung dengan alat-alat kalkulus, dan kita dapat menghitung perpotongan garis ini dengan sumbu- (yang dapat dilakukan dengan mudah menggunakan aljabar dasar). Perpotongan dengan sumbu- ini biasanya merupakan hampiran yang lebih baik ke akar fungsi daripada tebakan awal, dan metode ini dapat diiterasi.

Misalkan adalah fungsi terturunkan yang terdefinisi pada selang dengan nilai merupakan bilangan riil . Rumus untuk menghampiri akar dapat dengan mudah diturunkan. Misalkan kita memiliki hampiran mutakhir . Maka kita dapat menurunkan hampiran yang lebih baik, dengan merujuk pada diagram di kanan. Kita tahu dari definisi turunan pada suatu titik bahwa itu adalah kemiringan garis singgung pada titik tersebut, yaitu:

.

Di sini, melambangkan turunan fungsi . Maka dengan aljabar sederhana kita mendapatkan

.

Kita memulai proses dengan nilai awal sembarang . Metode ini biasanya akan mengerucut pada akar, dengan syarat tebakan awal cukup dekat pada akar tersebut, dan bahwa .

Sejarah[sunting | sunting sumber]

Nama "metode Newton" berasal dari deskripsi Isaac Newton tentang kasus khusus metode pada De analysi per aequationes numero terminorum infinitas (ditulis pada 1669, diterbitkan pada 1711 oleh William Jones) dan di De metodis fluxionum et serierum infinitarum (ditulis tahun 1671, diterjemahkan dan diterbitkan sebagai Metode Fluksion tahun 1736 oleh John Colson). Namun, metodenya sangat berbeda dari metode modern yang diberikan di atas. Newton menerapkan metode ini hanya untuk polinomial, dimulai dengan perkiraan akar awal dan mengekstraksi urutan koreksi kesalahan. Dia menggunakan setiap koreksi untuk menulis ulang polinomial dalam hal kesalahan yang tersisa, dan kemudian menyelesaikan koreksi baru dengan mengabaikan suku-suku yang lebih tinggi.Dia tidak secara eksplisit menghubungkan metode dengan turunan atau menyajikan rumus umum. Newton menerapkan metode ini pada masalah numerik dan aljabar, menghasilkan deret Taylor dalam kasus terakhir.

Newton mungkin telah memperoleh metodenya dari metode yang serupa tetapi kurang tepat oleh Vieta. Inti dari metode Vieta dapat ditemukan dalam karya Matematikawan Persia Sharaf al-Din al-Tusi, sedangkan penggantinya Jamshīd al-Kāshī menggunakan metode penyelesaian Newton untuk menemukan akarnya (Ypma 1995). Kasus khusus metode Newton untuk menghitung akar kuadrat telah dikenal sejak zaman kuno dan sering disebut metode Babylonian.

Metode Newton digunakan oleh matematikawan Jepang abad ke-17 Seki Kōwa untuk menyelesaikan persamaan variabel tunggal, meskipun hubungannya dengan kalkulus tidak ada.[1]

Metode Newton pertama kali diterbitkan pada tahun 1685 dalam A Treatise of Algebra both Historical and Practical oleh John Wallis.[2] Pada tahun 1690, Joseph Raphson menerbitkan deskripsi yang disederhanakan dalam Analysis aequationum universalis.[3] Raphson juga menerapkan metode ini hanya untuk polinomial, tetapi ia menghindari proses penulisan ulang Newton yang membosankan dengan mengekstrak setiap koreksi berturut-turut dari polinomial asli. Kemungkinkannya untuk mendapatkan ekspresi berulang yang dapat digunakan kembali untuk setiap masalah. Akhirnya, pada tahun 1740, Thomas Simpson mendeskripsikan metode Newton sebagai metode berulang untuk menyelesaikan persamaan nonlinier umum menggunakan kalkulus, yang pada dasarnya memberikan gambaran di atas. Dalam publikasi yang sama, Simpson juga memberikan generalisasi sistem dua persamaan dan mencatat bahwa metode Newton dapat digunakan untuk menyelesaikan masalah optimasi dengan mengatur gradien ke nol.

Arthur Cayley pada tahun 1879 dalam Masalah imajiner Newton-Fourier adalah orang pertama yang memperhatikan kesulitan dalam menggeneralisasi metode Newton ke akar kompleks polinomial dengan derajat lebih besar dari 2 dan unit kompleks. Ini membuka jalan untuk mempelajari teori iterasi fungsi rasional.

Pertimbangan praktis[sunting | sunting sumber]

Metode Newton adalah teknik yang sangat ampuh — secara umum konvergensi adalah kuadrat: karena metode ini menyatu pada akar, perbedaan antara akar dan aproksimasi dikuadratkan (jumlah digit akurat kira-kira berlipat ganda) di setiap langkah. Namun, ada beberapa kesulitan dengan metode ini.

Kesulitan dalam menghitung turunan dari suatu fungsi[sunting | sunting sumber]

Metode Newton mengharuskan turunannya dapat dihitung secara langsung. Ekspresi analitis untuk turunan mungkin tidak dapat diperoleh dengan mudah atau mahal untuk dievaluasi. Dalam situasi ini, mungkin tepat untuk memperkirakan turunan dengan menggunakan kemiringan garis melalui dua titik terdekat pada fungsi tersebut. Menggunakan pendekatan ini akan menghasilkan sesuatu seperti metode garis potong yang konvergensinya lebih lambat daripada metode Newton.

Kegagalan metode untuk menyatu dengan akar[sunting | sunting sumber]

Penting untuk meninjau Bukti konvergensi kuadrat metode Newton sebelum menerapkannya. Secara khusus, salah satunya harus meninjau asumsi yang dibuat dalam pembuktian. Untuk situasi di mana metode gagal untuk bertemu, itu karena asumsi yang dibuat dalam pembuktian ini tidak terpenuhi.

Melampaui[sunting | sunting sumber]

Jika turunan pertama tidak berperilaku baik di sekitar akar tertentru, metode mungkin melampaui batas, dan menyimpang dari akar tersebut. Contoh fungsi dengan satu akar, yang turunannya tidak berperilaku baik di sekitar akar, adalah

yang mana akar akan melampaui dan urutan x akan menyimpang. Untuk , akar masih akan melampaui, tetapi urutannya akan berosilasi di antara dua nilai. Untuk , akar masih akan melampaui tetapi urutannya akan bertemu, dan untuk akar tidak akan melampaui batas sama sekali.

Dalam beberapa kasus, metode Newton dapat distabilkan dengan menggunakan relaksasi berlebih yang berurutan, atau kecepatan konvergensi dapat ditingkatkan oleh kami.

Titik stasioner[sunting | sunting sumber]

Jika titik stasioner dari fungsi tersebut ditemukan, turunannya adalah nol dan metode ini akan berhenti karena pembagian dengan nol.

Estimasi awal yang buruk[sunting | sunting sumber]

Kesalahan besar dalam perkiraan awal dapat menyebabkan non-konvergensi algoritme. Untuk mengatasi masalah ini, sering kali kita dapat membuat linierisasi fungsi yang sedang dioptimalkan menggunakan kalkulus, log, diferensial, atau bahkan menggunakan algoritme evolusioner, seperti terowongan stokastik. Estimasi awal yang baik mendekati estimasi parameter akhir yang optimal secara global. Dalam regresi nonlinier, jumlah kesalahan kuadrat (SSE) hanya "mendekati" parabola di wilayah estimasi parameter akhir. Perkiraan awal yang ditemukan di sini akan memungkinkan metode Newton-Raphson untuk segera bertemu. Hanya di sini matriks Hesse SSE bernilai positif dan turunan pertama SSE mendekati nol.

Mitigasi takkonvergensi[sunting | sunting sumber]

Dalam implementasi yang kuat dari metode Newton, adalah umum untuk menempatkan batasan pada jumlah iterasi, mengikat solusi ke interval yang diketahui mengandung akar, dan menggabungkan metode dengan lebih banyak.

Konvergensi lambat untuk akar multiplisitas lebih besar dari 1[sunting | sunting sumber]


Analisis[sunting | sunting sumber]

- Dalam pengembangan -

Analisis kegagalan[sunting | sunting sumber]

Metode Newton hanya dijamin konvergen jika kondisi tertentu terpenuhi. Bila asumsi yang dibuat dalam bukti konvergensi kuadrat terpenuhi, metode tersebut akan bertemu. Untuk subbagian berikut, kegagalan metode untuk konvergen menunjukkan bahwa asumsi yang dibuat dalam bukti tidak terpenuhi.


Generalisasi[sunting | sunting sumber]

- Dalam pengembangan -

Contoh[sunting | sunting sumber]

Akar kuadrat[sunting | sunting sumber]


Contohnya, untuk mencari akar kuadrat dari 612 dengan tebakan awal x0 = 10, urutan yang diberikan oleh metode Newton adalah:

dimana angka yang benar digarisbawahi. Dengan hanya beberapa iterasi, salah satunya dapat memperoleh solusi yang akurat untuk banyak tempat desimal.

Menyusun ulang rumus sebagai berikut menghasilkan metode Babilonia untuk mencari akar kuadrat:

i.e. the arithmetic mean of the guess, and .

Solusi dari [sunting | sunting sumber]

Contohnya dengan tebakan awal , urutan yang diberikan oleh metode Newton adalah (perhatikan bahwa nilai awal 0 akan mengarah ke hasil yang tidak ditentukan, menunjukkan pentingnya menggunakan titik awal yang dekat dengan solusi):

Digit yang benar digarisbawahi dalam contoh di atas. Khususnya, benar sampai 12 tempat desimal. Kita melihat bahwa jumlah digit yang benar setelah koma desimal bertambah dari 2 (untuk ) ke 5 dan 10, menggambarkan konvergensi kuadrat.

Lihat pula[sunting | sunting sumber]

Catatan[sunting | sunting sumber]

  1. ^ "Chapter 2. Seki Takakazu". Japanese Mathematics in the Edo Period. National Diet Library. Diakses tanggal 24 Februari 2019. 
  2. ^ Wallis, John (1685). Risalah Aljabar, baik Historis maupun Praktis. Oxford: Richard Davis. doi:10.3931/e-rara-8842. 
  3. ^ Raphson, Joseph (1697). Analisis Æequationum Universalis (dalam bahasa Latin) (edisi ke-2nd). London: Thomas Bradyll. doi:10.3931/e-rara-13516. 
Kesalahan pengutipan: Tag <ref> dengan nama "Colli and Girault, 2017" yang didefinisikan di <references> tidak digunakan pada teks sebelumnya.

Referensi[sunting | sunting sumber]

Further reading[sunting | sunting sumber]

Pranala luar[sunting | sunting sumber]

Templat:Wikibooks category

Weisstein, Eric W. "Newton's Method". MathWorld. 

Templat:Isaac Newton Templat:Algoritme pengoptimalan Templat:Algoritme pencarian root