Metode Newton

Metode Newton mendekati akar f, yaitu bilangan r dengan $f(r) = 0$, melalui pengulangan satu langkah. Pada perkiraan saat ini $x_n$, ambil garis singgung kurva di $(x_n, f(x_n))$, yaitu $L(x) = f(x_n) + f'(x_n)(x - x_n)$. Di dekat $x_n$, garis singgung tetap dekat dengan kurva, sehingga titik potongnya dengan sumbu x adalah perkiraan yang lebih baik untuk titik potong kurva. Menyelesaikan $L(x) = 0$ memberi perkiraan berikutnya. Pada grafik, setiap langkah mengikuti garis putus-putus tipis dari $x_n$ menuju kurva, lalu mengikuti garis singgung menuju sumbu.

Tuliskan $e_n = x_n - r$ untuk galat. Jika r akar sederhana ($f'(r) \ne 0$) dan f mempunyai turunan kedua yang kontinu, pengembangan Taylor untuk langkah tersebut memberi $e_{n+1} \approx \frac{f''(r)}{2f'(r)}\,e_n^2$ setelah $x_n$ dekat dengan r. Menguadratkan galat kira-kira menggandakan jumlah digit benar. Untuk x² − 2 dari x₀ = 1, galatnya 0.086, 0.0025, 2.1 × 10⁻⁶, dan 1.6 × 10⁻¹², dan tampilan memperlihatkan $e_n/e_{n-1}^2$ mendekati $1/(2\sqrt2) \approx 0.354$. Jauh dari akar, tidak ada jaminan seperti itu. Ketika $f''(r) = 0$, suku kuadrat hilang dan prosesnya lebih cepat lagi: untuk arctan x, galatnya sekitar $-\tfrac23 e_n^3$, dipangkatkan tiga pada setiap langkah.

Langkah ini memerlukan $f'(x_n) \ne 0$. Garis singgung mendatar tidak pernah bertemu sumbu, dan yang hampir mendatar bertemu sumbu jauh: untuk x² − 2 dari 0.1, langkah pertama mencapai 10.05. Metode ini juga bisa gagal tanpa menjauh. Untuk x³ − 2x + 2, garis singgung di 0 mendarat di 1, yang di 1 kembali ke 0, dan titik awal dekat 0 tertarik ke siklus ini: barisannya tetap terbatas, tetapi tidak mempunyai limit. Untuk arctan x, ada batas α ≈ 1.3917, yaitu bilangan yang memenuhi $2\alpha = (1 + \alpha^2)\arctan\alpha$. Titik awal dengan |x₀| < α konvergen, sedangkan yang di luar batas mendarat semakin jauh di sisi lain. Opsi «Semua titik awal» mewarnai sumbu x menurut hasil akhir setiap titik awal. Untuk x³ − 2x + 2, sekitar seperlima [−3, 3] berakhir dalam siklus, termasuk pita sempit yang berkumpul menuju titik dengan garis singgung mendatar $\pm\sqrt{2/3}$. Memulai dari bilangan kompleks mengubah pita-pita itu menjadi fraktal Newton.

Pada akar berulang, $f'(r) = 0$ juga berlaku dan konvergensi kuadratik hilang. Untuk $(x - 1)^2$, langkahnya tepat $x_{n+1} = (x_n + 1)/2$, sehingga galat menjadi setengah setiap langkah. Ini konvergensi linear, sekitar 3.3 langkah untuk setiap angka desimal baru. Di dekat akar dengan multiplisitas m, rasio $e_{n+1}/e_n$ menuju $(m - 1)/m$.