Metode Newton

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 $f(x)$ dan turunannya $f'(x)$, kita memulai dengan tebakan pertama, $x_{0}$. Hampiran yang lebih baik untuk $x_{1}$ adalah

$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}$.

Deskripsi

Ilustrasi salah satu iterasi metode Newton (fungsi ƒ ditunjukkan dengan warna biru dan garis singgung dalam warna merah). Kita melihat bahwa x_n+1 adalah hampiran yang lebih baik daripada x_nuntuk 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-$x$ (yang dapat dilakukan dengan mudah menggunakan aljabar dasar). Perpotongan dengan sumbu-$x$ ini biasanya merupakan hampiran yang lebih baik ke akar fungsi daripada tebakan awal, dan metode ini dapat diiterasi.

Misalkan $f\colon [a,b]\to \mathbb {R}$ adalah fungsi terturunkan yang terdefinisi pada selang $[a,b]$ dengan nilai merupakan bilangan riil $\mathbb {R}$. Rumus untuk menghampiri akar dapat dengan mudah diturunkan. Misalkan kita memiliki hampiran mutakhir $x_{n}$. Maka kita dapat menurunkan hampiran yang lebih baik, $x_{n+1}$ dengan merujuk pada diagram di kanan. Kita tahu dari definisi turunan pada suatu titik bahwa itu adalah kemiringan garis singgung pada titik tersebut, yaitu:

$f'(x_{n})={\frac {\mathrm {rise} }{\mathrm {run} }}={\frac {\Delta y}{\Delta x}}={\frac {f(x_{n})-0}{x_{n}-x_{n+1}}}$.

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

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$.

Kita memulai proses dengan nilai awal sembarang $x_{0}$. Metode ini biasanya akan mengerucut pada akar, dengan syarat tebakan awal cukup dekat pada akar tersebut, dan bahwa $f'(x_{0})\neq 0$.

Sejarah

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 $x^{P}-N=0$ untuk menemukan akarnya $N$ (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.

Metode Newton pertama kali diterbitkan pada tahun 1685 dalam A Treatise of Algebra both Historical and Practical oleh John Wallis. Pada tahun 1690, Joseph Raphson menerbitkan deskripsi yang disederhanakan dalam Analysis aequationum universalis. 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

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

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

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

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

$f(x)=|x|^{a},\quad 0<a<{\tfrac {1}{2}}$

yang mana akar akan melampaui dan urutan x akan menyimpang. Untuk $a={\frac {1}{2}}$, akar masih akan melampaui, tetapi urutannya akan berosilasi di antara dua nilai. Untuk ${\frac {1}{2}}<a<1$, akar masih akan melampaui tetapi urutannya akan bertemu, dan untuk $a\geq 1$ 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

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

Estimasi awal yang buruk

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

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.

Analisis

- Dalam pengembangan -

Analisis kegagalan

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

- Dalam pengembangan -

Contoh

Akar kuadrat

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

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&10-{\dfrac {10^{2}-612}{2\times 10}}&=&35.6\qquad \qquad \qquad \quad \;\,{}\\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&35.6-{\dfrac {35.6^{2}-612}{2\times 35.6}}&=&{\underline {2}}6.395\,505\,617\,978\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {24.7}}90\,635\,492\,455\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {24.738\,6}}88\,294\,075\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {24.738\,633\,753\,7}}67\dots \end{matrix}}$

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:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}=x_{n}-{\frac {x_{n}^{2}-a}{2x_{n}}}={\frac {1}{2}}{\biggl (}2x_{n}-{\Bigl (}x_{n}-{\frac {a}{x_{n}}}{\Bigr )}{\biggr )}={\frac {1}{2}}{\Bigl (}x_{n}+{\frac {a}{x_{n}}}{\Bigr )}$

i.e. the arithmetic mean of the guess, $x_{n}$ and ${\frac {a}{x_{n}}}$.

Solusi dari $\cos x=x^{3}$

Contohnya dengan tebakan awal $x_{0}=0.5$, 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):

${\begin{matrix}x_{1}&=&x_{0}-{\dfrac {f(x_{0})}{f'(x_{0})}}&=&0.5-{\dfrac {\cos 0.5-0.5^{3}}{-\sin 0.5-3\times 0.5^{2}}}&=&1.112\,141\,637\,097\dots \\x_{2}&=&x_{1}-{\dfrac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0.}}909\,672\,693\,736\dots \\x_{3}&=&\vdots &=&\vdots &=&{\underline {0.86}}7\,263\,818\,209\dots \\x_{4}&=&\vdots &=&\vdots &=&{\underline {0.865\,47}}7\,135\,298\dots \\x_{5}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,1}}11\dots \\x_{6}&=&\vdots &=&\vdots &=&{\underline {0.865\,474\,033\,102}}\dots \end{matrix}}$

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

Lihat pula

• Proses kuadrat-delta Aitken
• Metode bagi dua
• Metode Euler
• Akar kuadrat terbalik cepat
• Penilaian Fisher
• Penurunan gradien
• Akar kuadrat bilangan bulat
• Teorema Kantorovich
• Metode Laguerre
• Metode menghitung akar kuadrat
• Metode Newton dalam pengoptimalan
• Ekstrapolasi Richardson
• Algoritma pencarian akar
• Metode sekan
• Metode Steffensen
• Metode subgradien

Referensi

• Gil, A.; Segura, J.; Temme, N. M. (2007). Numerical methods for special functions. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-634-4. 
• Süli, Endre; Mayers, David (2003). An Introduction to Numerical Analysis. Cambridge University Press. ISBN 0-521-00794-1. 

Further reading

• Kendall E. Atkinson, An Introduction to Numerical Analysis, (1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6
• Tjalling J. Ypma, Historical development of the Newton–Raphson method, SIAM Review 37 (4), 531–551, 1995. DOI:10.1137/1037125.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (edisi ke-Second revised ed. of translation of 1997 French). Berlin: Springer-Verlag. hlm. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. MR 2265882. 
• P. Deuflhard, Newton Methods for Nonlinear Problems. Affine Invariance and Adaptive Algorithms. Springer Series in Computational Mathematics, Vol. 35. Springer, Berlin, 2004. ISBN 3-540-21099-7.
• C. T. Kelley, Solving Nonlinear Equations with Newton's Method, no 1 in Fundamentals of Algorithms, SIAM, 2003. ISBN 0-89871-546-6.
• J. M. Ortega, W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables. Classics in Applied Mathematics, SIAM, 2000. ISBN 0-89871-461-3.
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Chapter 9. Root Finding and Nonlinear Sets of Equations Importance Sampling". Numerical Recipes: The Art of Scientific Computing (edisi ke-3rd). New York: Cambridge University Press. ISBN 978-0-521-88068-8. . See especially Sections 9.4, 9.6, and 9.7.
• Avriel, Mordecai (1976). Nonlinear Programming: Analysis and Methods. Prentice Hall. hlm. 216–221. ISBN 0-13-623603-0. 

Pranala luar

• Hazewinkel, Michiel, ed. (2001) [1994], "Newton method", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 
• (Inggris)

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

• Newton's method, Citizendium.
• Mathews, J., The Accelerated and Modified Newton Methods, Course notes.
• Wu, X., Roots of Equations, Course notes.