Metode Newton: Temukan Akar Secara Cepat dengan Pendekatan Iteratif

Beberapa persamaan memang tidak memiliki solusi aljabar yang rapi.

Anda bisa melakukan faktorisasi dan substitusi sesuka hati, tetapi sebagian persamaan tidak memiliki bentuk tertutup. Misalnya, polinomial berderajat lima atau lebih tinggi tidak memiliki solusi aljabar umum. Fungsi yang mencampurkan eksponensial dengan polinomial, seperti e^x = 3x, masuk dalam kategori yang sama. Dalam kasus seperti ini, Anda memerlukan pendekatan lain.

Metode Newton adalah pendekatan tersebut. Ia menemukan akar secara numerik dengan membuat tebakan yang semakin cerdas—masing-masing dipandu oleh garis singgung fungsi pada perkiraan saat ini.

Dalam artikel ini, saya akan memandu Anda melalui rumus di balik Metode Newton, cara kerjanya langkah demi langkah, kapan ia konvergen, dan kapan tidak—dengan contoh konkret agar teorinya mudah dipahami.

Mencari topik matematika lain yang perlu Anda ketahui sebagai data scientist? Baca postingan blog kami Deret Geometri: Rumus, Konvergensi, dan Contoh untuk melihat penerapannya di bidang keuangan, fisika, dan CS.

Apa Itu Metode Newton?

Metode Newton adalah teknik iteratif untuk mencari akar suatu fungsi. Akar adalah nilai masukan ketika fungsi bernilai nol.

Anda memulai proses ini dengan tebakan awal. Lalu, metode ini menggunakan geometri fungsi pada titik tersebut untuk membuat tebakan yang lebih baik. Ulangi prosesnya, dan setiap iterasi membawa Anda lebih dekat ke akar sebenarnya.

Itulah gagasan utamanya. Anda hanya perlu aturan pembaruan yang cerdas dan dapat diulang yang mengonvergensi ke jawabannya.

Rumus Metode Newton

Inti Metode Newton adalah satu aturan pembaruan yang Anda terapkan berulang-ulang hingga cukup dekat dengan akar.

Berikut rumusnya:

Rumus Metode Newton

Setiap iterasi mengambil perkiraan saat ini x_n dan menghasilkan yang lebih baik, x_{n+1}. Anda terus memperbarui hingga hasilnya cukup dekat dengan nol.

Rumusnya memiliki tiga komponen:

• x_n - perkiraan akar Anda saat ini

• f(x_n) - nilai fungsi pada perkiraan tersebut

• f'(x_n) - turunan fungsi pada perkiraan tersebut, yang memberi tahu kemiringan garis singgung

Jika f(x_n) besar, Anda jauh dari akar. Jika f'(x_n) curam, fungsi berubah cepat, sehingga Anda bisa mengambil langkah lebih besar. Rasio f(x_n) / f'(x_n) memberi tahu Anda seberapa jauh harus bergerak—dan Anda mengurangkannya dari tebakan saat ini untuk mendekat.

Jika f'(x_n) bernilai nol atau mendekati nol, rumusnya tidak akan benar-benar bekerja. Anda akan membagi dengan nol, yang berarti metode tidak bisa menghasilkan perkiraan berikutnya. Saya akan membahas ini lebih detail pada bagian keterbatasan.

Cara Kerja Metode Newton

Metode Newton mengikuti empat langkah yang sama pada setiap iterasi.

1. Pilih tebakan awal: Pilih nilai awal x_0 di suatu tempat dekat akar. Anda tidak perlu tepat—cukup cukup dekat sehingga fungsi berperilaku dapat diprediksi di sekitar titik itu. Saya akan membahas apa arti "cukup dekat" pada bagian konvergensi.

2. Hitung nilai fungsi: Evaluasi f(x_0). Ini memberi tahu seberapa jauh fungsi dari nol pada perkiraan saat ini. Jika f(x_0) = 0, selesai—Anda telah menemukan akarnya.

3. Hitung turunannya: Evaluasi f'(x_0). Ini memberi kemiringan fungsi di x_0, yang merupakan kemiringan garis singgung pada titik tersebut.

4. Perbarui perkiraan: Terapkan aturan pembaruan sesuai rumus pada bagian sebelumnya.

Dan selesai!

Nilai baru x_1 ini adalah tempat garis singgung memotong sumbu-x. Secara geometris, Anda menggambar garis lurus yang menyentuh kurva di x_0 dan mengikutinya turun hingga nol. Titik perpotongan itulah tebakan Anda berikutnya yang lebih baik.

Lalu ulangi. Masukkan x_1 kembali ke langkah 2 hingga 4 untuk mendapatkan x_2, kemudian x_3, dan seterusnya. Setiap iterasi menggambar garis singgung baru pada titik yang diperbarui dan mencari di mana ia memotong sumbu-x.

Proses berhenti ketika f(x_n) cukup dekat dengan nol—biasanya ketika nilainya berada di bawah ambang kecil yang Anda tentukan di awal.

Interpretasi Geometris Metode Newton

Bayangkan sebuah kurva pada grafik—itulah fungsi Anda f(x). Akar adalah tempat kurva memotong sumbu-x. Anda belum tahu di mana tepatnya, jadi Anda mulai dengan tebakan x_0 di suatu titik pada sumbu-x.

Pada setiap langkah, Anda memplot titik (x_0, f(x_0)) pada kurva, lalu menggambar garis singgung di titik itu—garis lurus yang menyentuh kurva di sana dan mengikuti kemiringannya. Garis singgung itu tidak horizontal. Ia miring, dan jika Anda mengikutinya turun, ia memotong sumbu-x di suatu titik. Perpotongan itu adalah perkiraan berikutnya, x_1.

Lalu ulangi. Di x_1, Anda menggambar garis singgung baru dan mencari di mana ia memotong sumbu-x. Itu memberi Anda x_2. Setiap garis singgung adalah pendekatan linear lokal dari kurva, dan setiap titik perpotongan mendarat lebih dekat ke akar sebenarnya.

Grafik di bawah menunjukkan dua iterasi Metode Newton yang diterapkan pada f(x) = x^2 - 2, dimulai dari x_0 = 2.5:

Bagan interpretasi geometris

Ini berhasil karena garis singgung adalah pendekatan garis lurus terbaik dari suatu kurva pada titik mana pun. Semakin dekat Anda ke akar, semakin garis singgung menyerupai kurva itu sendiri—dan semakin akurat langkah berikutnya.

Dalam praktiknya, perkiraan tidak sekadar merayap menuju akar. Mereka melompat ke sana dengan cepat, sering kali menggandakan jumlah angka desimal yang benar pada setiap iterasi.

Contoh Langkah demi Langkah Metode Newton

Mari terapkan Metode Newton pada f(x) = x^2 - 2. Akar fungsi ini adalah x = sqrt(2) ≈ 1.4142—dengan kata lain, kita menghitung akar kuadrat dari 2.

Turunannya adalah f'(x) = 2x, sehingga aturan pembaruan menjadi:

Contoh (aturan pembaruan)

Mari mulai dengan tebakan awal x_0 = 2.5.

Iterasi 1:

Contoh (iterasi 1)

Iterasi 2:

Contoh (iterasi 2)

Iterasi 3:

Contoh (iterasi 3)

Hanya setelah tiga iterasi, kita sudah akurat hingga empat angka desimal. Galat turun dari 1.086 pada x_0 menjadi 0.0001 pada x_3—dan terus berkurang di setiap langkah.

Berikut cara kerja perkiraan dan nilai galat ini secara visual:

Gambaran visual perkiraan dan galat

Panel kiri menunjukkan bagaimana setiap perkiraan semakin mendekati sqrt(2) ≈ 1.4142, sementara panel kanan menunjukkan galat yang semakin kecil pada skala log—setiap iterasi kurang lebih menguadratkan ketelitian iterasi sebelumnya.

Konvergensi Metode Newton

Metode Newton dapat berkonvergensi dengan cepat, tetapi hanya dalam kondisi yang tepat.

Ketika tebakan awal dekat dengan akar dan fungsi halus di wilayah tersebut, metode ini menunjukkan konvergensi kuadratik. Itulah istilah teknis untuk apa yang Anda lihat pada contoh: setiap iterasi kira-kira menguadratkan galat dari iterasi sebelumnya. Dua angka desimal yang benar menjadi empat, empat menjadi delapan, dan seterusnya.

Dua syarat perlu terpenuhi agar ini berhasil:

• Tebakan awal yang baik: Semakin dekat x_0 ke akar sebenarnya, semakin cepat metode ini berkonvergensi. Jika Anda mulai terlalu jauh, garis singgung pada titik itu bisa mengarahkan Anda ke arah yang salah.
• Fungsi yang berperilaku baik: Fungsi perlu halus dan terdiferensialkan dekat akar. Tikungan tajam atau daerah datar dapat mengganggu pendekatan garis singgung.

Mode kegagalan paling umum adalah turunan mendekati nol. 

Jika f'(x_n) mendekati nol, Anda membagi dengan angka yang sangat kecil dalam aturan pembaruan, yang mengirimkan perkiraan berikutnya jauh dari akar. Dalam kasus terburuk, f'(x_n) = 0 dan perhitungan berhenti bekerja karena Anda tidak dapat membagi dengan nol.

Titik awal yang buruk juga dapat menyebabkan metode berosilasi atau divergen. Alih-alih mendekati akar, perkiraan melompat bolak-balik atau semakin jauh pada setiap iterasi.

Metode Newton memberikan hasil terbaik jika persiapannya baik. Tebakan awal yang masuk akal dan fungsi yang halus sudah cukup untuk membuatnya konvergen—dan konvergen cepat.

Keunggulan Metode Newton

Ketika kondisinya tepat, Metode Newton sulit ditandingi.

Keunggulan terbesar adalah konvergensi kuadratik. Sebagian besar metode numerik mendekati akar dengan laju linear, artinya setiap iterasi mengurangi galat dengan jumlah tetap. Metode Newton justru menguadratkan galat, yang berarti akurasinya meningkat cepat hanya dengan sedikit iterasi.

Metode ini juga serbaguna. Anda bisa menerapkannya pada berbagai fungsi—polinomial, trigonometri, eksponensial—tanpa mengubah apa pun. Itulah mengapa ia muncul di begitu banyak bidang, dari simulasi rekayasa hingga pelatihan model machine learning.

Keterbatasan Metode Newton

Sebagai imbalan kecepatan itu, Metode Newton memiliki sejumlah tuntutan. Berikut beberapa keterbatasan yang perlu diingat:

• Memerlukan turunan: Anda membutuhkan ekspresi analitik untuk f'(x) sebelum menjalankan satu iterasi pun. Untuk fungsi yang turunannya sulit dihitung (atau tidak ada), Anda memerlukan pendekatan lain.

• Peka terhadap tebakan awal: Jika Anda mulai terlalu jauh dari akar, metode ini bisa mengarahkan ke arah yang salah.

• Mungkin tidak berkonvergensi: Jika fungsi memiliki daerah datar atau kurva tajam, pendekatan garis singgung tidak akan bekerja.

• Dapat divergen atau berosilasi: Dalam kasus buruk, perkiraan gagal berkonvergensi dan semakin jauh dari akar atau memantul bolak-balik tanpa henti.

Jadi sebelum menggunakan Metode Newton, pastikan Anda memahami fungsi Anda.

Metode Newton vs Metode Pencarian Akar Lainnya

Metode Newton bukan satu-satunya cara untuk menemukan akar, dan tidak selalu yang paling tepat untuk Anda.

Dua metode lain yang sering muncul: metode bagi dua (bisection) dan metode secant. Berikut penjelasan singkatnya.

Metode bagi dua

Metode bagi dua adalah yang paling sederhana di antara ketiganya. Anda mulai dengan interval [a, b] di mana fungsi berganti tanda—artinya ada akar di suatu tempat di dalamnya. Lalu Anda berulang kali membagi dua interval tersebut, mempertahankan bagian yang masih mengandung pergantian tanda.

Metode ini bekerja, tetapi lambat. Galat berkurang setengah setiap iterasi, yang berarti konvergensi linear. Namun metode ini dijamin berhasil selama fungsinya kontinu dan interval awal Anda membatasi sebuah akar. Tidak memerlukan turunan.

Metode secant

Metode secant adalah kerabat dekat Metode Newton. Alih-alih menghitung turunan secara analitik, metode ini mendekatinya menggunakan dua perkiraan sebelumnya:

Rumus metode secant

Ini adalah pendekatan yang baik ketika turunan sulit dihitung. Konsekuensinya adalah kecepatan konvergensi—metode secant lebih cepat daripada bagi dua tetapi lebih lambat daripada Metode Newton.

Aplikasi Metode Newton

Metode Newton hadir di berbagai bidang sains, rekayasa, dan machine learning. Berikut penjelasan tepatnya.

Menyelesaikan persamaan secara numerik

Penerapan paling langsung. Ketika suatu fungsi tidak memiliki solusi bentuk tertutup, Metode Newton menemukan akarnya. Ini sering muncul dalam komputasi ilmiah—misalnya mencari titik kesetimbangan pada reaksi kimia atau menyelesaikan persamaan transendental dalam pemrosesan sinyal.

Optimisasi

Mencari minimum atau maksimum suatu fungsi f(x) berarti mencari di mana turunannya f'(x) = 0. Itu adalah masalah pencarian akar—yang berarti Metode Newton dapat diterapkan. Anda cukup menjalankan algoritme pada f'(x) alih-alih f(x), menggunakan turunan kedua f''(x) menggantikan turunan pertama.

Varian ini disebut Metode Newton untuk optimisasi, dan ia berkonvergensi lebih cepat daripada gradient descent pada fungsi yang halus dan berperilaku baik.

Machine learning

Dalam machine learning, melatih model berarti meminimalkan fungsi loss. Metode Newton dan variannya muncul di beberapa tempat di sini.

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) adalah pengoptimal quasi-Newton yang mendekati turunan kedua untuk menghindari menghitungnya secara langsung. Ini adalah pilihan standar untuk regresi logistik dan masalah cembung lainnya. Metode Newton juga menjadi dasar pembaruan Newton-Raphson yang digunakan dalam pemodelan statistik, seperti generalized linear models.

Fisika dan rekayasa

Metode Newton ada di mana-mana dalam simulasi dan desain. Insinyur menggunakannya untuk menyelesaikan sistem persamaan nonlinier yang menggambarkan sistem fisik—misalnya analisis tegangan struktural dan dinamika fluida. Dalam setiap kasus, masalah dasarnya berujung pada mencari di mana sekumpulan persamaan bernilai nol.

Kesalahan Umum pada Metode Newton

Sebagian besar kesalahan pada Metode Newton bermuara pada empat hal yang sama. Berikut ulasannya:

• Memulai terlalu jauh dari akar: Tebakan awal yang buruk adalah alasan paling umum metode ini menjadi divergen atau berosilasi. Jika Anda tidak memiliki intuisi yang baik tentang letak akar, plot fungsi terlebih dahulu. Ini akan memberi tahu Anda di mana harus mulai.

• Turunan yang salah: Aturan pembaruan bergantung pada f'(x). Turunan yang keliru—baik karena kesalahan perhitungan maupun kesalahan pengodean—menghasilkan perkiraan yang salah sejak iterasi pertama, dan galatnya bertambah pada iterasi-iterasi berikutnya.

• Tidak memeriksa pembagian dengan nol. Jika f'(x_n) bernilai nol atau sangat mendekatinya, langkah pembaruan tidak dapat bekerja. Tambahkan pemeriksaan pada implementasi Anda: jika turunan berada di bawah ambang kecil tertentu, hentikan dan laporkan kegagalan daripada menghasilkan hasil yang tidak masuk akal.

• Berhenti terlalu dini. Menghentikan iterasi sebelum perkiraan berkonvergensi membuat Anda mendapatkan jawaban yang tampak dekat tetapi sebenarnya tidak. Tetapkan kondisi penghentian pada galat aktual—baik |f(x_n)| atau |x_{n+1} - x_n| jatuh di bawah ambang yang Anda pilih secara cermat, bukan sekadar jumlah iterasi tetap.

Kesimpulan

Metode Newton adalah salah satu alat paling berguna dalam komputasi numerik. Satu aturan pembaruan, diterapkan berulang kali, dapat menemukan akar hingga presisi sewenang-wenang hanya dalam beberapa iterasi.

Anda membayar kecepatan itu dengan sejumlah kondisi. Anda memerlukan tebakan awal yang baik, fungsi yang tidak datar, fungsi yang tidak penuh puncak tajam, dan turunan yang tidak nol agar konvergensi cepat tercapai. Pahami saja kondisi-kondisi ini, dan Anda akan tahu kapan harus menggunakan Metode Newton dan kapan harus menggunakan metode lain (seperti bagi dua atau secant).

Cara terbaik membangun intuisi itu adalah berlatih pada contoh sederhana. Mulailah dengan f(x) = x^2 - 2, coba berbagai titik awal, dan amati apa yang terjadi. Lanjutkan ke fungsi dengan banyak akar atau daerah datar dan lihat di mana metode ini gagal.

Jika Anda menyukai konsep optimisasi melalui iterasi, Anda harus mengetahui gradient descent. Baca Gradient Descent dalam Machine Learning: Telaah Mendalam untuk mempelajari bagaimana ia mengoptimalkan model untuk machine learning.