Metode Newton

Apa itu metode Newton?

Metode Newton, disebut juga metode Newton–Raphson, adalah cara menghampiri solusi f(x)=0 dengan garis singgung. Nilai x tempat f bernilai nol adalah akar f dan solusi persamaan itu. Untuk persamaan linear ax+b=0 dan kuadrat ax^2+bx+c=0 ada rumusnya, tetapi untuk kebanyakan persamaan, seperti x^3-x-1=0 atau \cos x=x, tidak ada, dan bilangan adalah satu-satunya jawaban. Metode ini cepat dan sederhana, dan dipakai di kalkulator, di perangkat lunak, dan di bidang teknik di mana pun persamaan sulit harus diselesaikan.

Gagasannya. Misalkan x_0 tebakan kasar suatu akar. Di dekat x_0 kurva y=f(x) hampir sama dengan garis singgungnya (ini adalah linearisasi f), dan garis mudah diselesaikan. Jadi ambil titik x_1 tempat garis singgung di \left(x_0,f(x_0)\right) memotong sumbu-x: biasanya ia lebih dekat ke akar daripada x_0. Lalu lakukan hal yang sama di x_1 untuk mendapat x_2, dan lanjutkan sampai bilangannya berhenti berubah.

Rumusnya. Garis singgung di \left(x_n,f(x_n)\right) adalah y=f(x_n)+f'(x_n) (x-x_n). Garis itu memotong sumbu-x di tempat y=0: 0=f(x_n)+f'(x_n)(x-x_n) ⇒ x=x_n-(f(x_n))/(f'(x_n))\qquadjika f'(x_n)\ne0. Nilai ini adalah hampiran berikutnya: x_n+1=x_n-(f(x_n))/(f'(x_n)) Setiap langkah naik (atau turun) dari x_n ke kurva lalu menyusuri garis singgung ke sumbu.

Prosedurnya. 1. Tebak hampiran pertama x_0, dengan bantuan grafik, atau perubahan tanda f pada suatu selang (Teorema Nilai Antara). 2. Pakai rumus untuk mendapat x_1, x_2, dan seterusnya. 3. Berhenti ketika langkahnya lebih kecil daripada ketelitian yang kamu perlukan, dan periksa bahwa f(x_n) dekat dengan nol.

Persamaan seperti f(x)=g(x) diselesaikan dengan menerapkan metode pada f(x)-g(x), dan pertanyaan seperti "di mana kurva y=x^3-x memotong garis y=1?" sama dengan mencari akar x^3-x-1.

Bagaimana metode Newton bekerja pada persamaan nyata?

Tiga contoh memperlihatkan metode ini bekerja: akar kuadrat, kubik dengan satu akar real, dan persamaan dari astronomi.

Contoh 1: akar kuadrat 2. Hampiri akar positif f(x)=x^2-2. Dengan f'(x)=2x rumusnya menjadi x_n+1=x_n-(x_n^2-2)/(2x_n)=(x_n)/(2)+\frac1x_n. Dari x_0=1 kita dapat x_1=\frac32=1,5, lalu x_2=(17)/(12)≈1,41667 dan x_3=(577)/(408)≈1,41422. Nilai sebenarnya √2=1,41421356…, sehingga galatnya sekitar 0,414, 0,086, 0,0025, dan 0,000002, dan langkah berikutnya benar sampai dua belas desimal. Setiap langkah kira-kira melipatduakan banyaknya angka benar.

Contoh 2: kubik. Tentukan absis tempat kurva y=x^3-x memotong garis y=1. Itu adalah akar f(x)=x^3-x-1. Karena f(1)=-1 dan f(2)=5, Teorema Nilai Antara memberi akar di (1,2). Dengan f'(x)=3x^2-1, x_n+1=x_n-(x_n^3-x_n-1)/(3x_n^2-1). Mulai dari x_0=1 memberi x_1=1,5, x_2=1,347826087, x_3=1,325200399, x_4=1,324718174, dan x_5=1,324717957, dan x_6 sama dengannya sampai sembilan desimal: f(x_5) nol sejauh ketelitian hitung. Kurvanya cekung ke atas untuk x>0, karena f''(x)=6x>0, sehingga begitu hampiran ada di kanan akar, garis singgungnya berada di bawah kurva dan hampiran turun tetap menuju akar. Mulai jauh lebih jauh, di x_0=3, tetap berhasil, dalam tujuh langkah; bahkan setiap awal di kanan \frac1√3 menuju akar ini.

Contoh 3: sebuah planet. Untuk menghitung posisi planet, astronom menyelesaikan persamaan seperti x=1+0,5\sin x (persamaan Kepler, dengan x dalam radian). Fungsi f(x)=x-1-0,5\sin x memiliki f'(x)=1-0,5\cos x, dan grafik menunjukkan akar di dekat 1,5. Satu langkah dari x_0=1,5 memberi x_1=1,5-\frac1,5-1-0,5\sin1,51-0,5\cos1,5≈1,49870, yang sudah merupakan akar sampai lima desimal.

Ketik sebuah fungsi dan nilai awal di bawah, atau pilih salah satu contoh. Penggeser mengambil langkah satu per satu, dan gambar menunjukkan tiap garis singgung: naik ke kurva, lalu menyusuri garis singgung ke sumbu.

Seberapa cepat metode Newton konvergen?

Di dekat akar sederhana metode Newton konvergen secara kuadrat: galatnya kira-kira dikuadratkan di setiap langkah, sehingga banyaknya angka benar kira-kira berlipat dua. Tulis e_n=x_n-r untuk galat, dengan r akarnya. Jika f memiliki turunan kedua kontinu dan f'(r)\ne0, maka e_n+1=(f''(\xi))/(2f'(x_n)) e_n^2\qquaduntuk suatu \xi di antara x_n dan r. Bukti. Rumus Taylor di x_n, dihitung di akar, memberi 0=f(x_n)-f'(x_n)e_n+\frac12f''(\xi)e_n^2, yaitu f'(x_n)e_n-f(x_n)=\frac12f''(\xi)e_n^2. Maka e_n+1=e_n-(f(x_n))/(f'(x_n))=(f'(x_n)e_n-f(x_n))/(f'(x_n))=(f''(\xi))/(2f'(x_n)) e_n^2. ∎ Ketika x_n→ r ini berarti (e_n+1)/(e_n^2)→(f''(r))/(2f'(r)). Untuk √2 konstantanya (2)/(2·2√2)≈0,354, dan tabel di bawah menunjukkan rasionya dekat dengan itu.

Perbandingan dengan bisection. Metode bisection membagi dua selang di setiap langkah, kenaikan sekitar 0,3 angka per langkah, sehingga sepuluh angka memerlukan sekitar tiga puluh tiga langkah. Metode Newton memerlukan empat atau lima, tetapi ia memerlukan turunan, awal yang baik, dan tanpa jaring pengaman.

Ini hasil lokal. Rumus |e_n+1|\le M e_n^2, dengan M batas untuk (|f''|)/(2|f'|) di dekat akar, memberi M|e_n|\le(M|e_0|)^2^n. Jadi jika galat pertama memenuhi M|e_0|<1 metodenya konvergen, dan sangat cepat; jika awalnya lebih jauh, tidak ada yang dijanjikan.

Akar ganda. Jika f(x)=(x-r)^m g(x) dengan m>1 maka f'(r)=0 dan argumen di atas gagal: galat hanya mengecil dengan faktor (m-1)/(m) di setiap langkah. Untuk (x-1)^2 galatnya dibagi dua, seperti pada bisection; untuk (x-1)^6 hanya seperenam galat yang hilang di setiap langkah. Untuk f(x)=(x-1)^40 dan x_0=2 faktornya (39)/(40), dan setelah 100 langkah hampirannya masih sekitar 1,08. Memakai x_n+1=x_n-m(f(x_n))/(f'(x_n)) mengembalikan konvergensi kuadrat bila m diketahui.

Berhenti. Untuk akar sederhana langkah |x_n+1-x_n| yang kecil berarti galatnya lebih kecil lagi. Jangan hanya mengandalkan |f(x_n)|: kurva datar seperti (x-1)^40 memiliki f(x) di bawah 10^-15 padahal x masih 0,4 dari akarnya.

Pilih satu kasus di bawah: tabel memberi galat, angka benar, dan kedua rasio, dengan bisection di sebelahnya untuk akar sederhana.

Kapan metode Newton gagal?

Metode Newton tidak selalu konvergen, dan ketika konvergen, ia dapat menuju akar yang tidak kamu maksud. Jika ia konvergen, limitnya adalah akar: ketika x_n→ L dan f dan f' kontinu dengan f'(L)\ne0, mengambil n→∞ pada rumus memberi (f(L))/(f'(L))=0. Masalahnya adalah apakah ia konvergen sama sekali. Kegagalan yang lazim adalah berikut.

1. Garis singgung mendatar. Jika f'(x_n)=0 garis singgung tidak pernah memotong sumbu dan rumusnya membagi dengan nol; jika f'(x_n) hanya sangat kecil tebakan berikutnya terlempar jauh.
2. Siklus. Untuk f(x)=x^3-2x+2 dan x_0=0 garis singgung di 0 memotong sumbu di 1, dan garis singgung di 1 memotongnya di 0: hampirannya 0,1,0,1,… selamanya, sedangkan akar nyatanya dekat -1,77. Dalam buku, fungsi f(x)=√(x-r) untuk x\ge r dan -√(r-x) untuk x<r berayun antara r-h dan r+h dengan cara yang sama.
3. Menjauh. Untuk f(x)=x^(1/3) akarnya 0, tetapi x_n+1=x_n-3x_n=-2x_n, sehingga hampirannya 1,-2,4,-8,… Kasus lain adalah \arctan x: jika |x_0| lebih besar dari sekitar 1,3917, tempat 2x=(1+x^2)\arctan x, setiap langkah mendarat lebih jauh daripada sebelumnya.
4. Akar yang keliru. \sin x memiliki akar di setiap kelipatan π, tetapi dari x_0=1,7 garis singgungnya hampir mendatar, tebakan berikutnya 9,40, dan barisan menetap di 3π. Jika mulai terlalu jauh, metode dapat melewatkan akar yang kamu inginkan.
5. Akar yang datar. Di akar berkelipatan m>1 konvergensinya hanya linear, seperti di atas.

Daerah tarikan. Himpunan nilai awal yang menuju satu akar disebut daerah tarikannya. Daerah tarikan akar yang berbeda biasanya dipisahkan oleh batas sederhana, tetapi dapat saling menyelip dalam pola halus. Untuk f(x)=x^3-x, dengan akar -1, 0, dan 1, setiap awal di atas \frac1√3≈0,577 menuju 1, setiap awal di antara -\frac1√5 dan \frac1√5 menuju 0, dan di antara \frac1√5≈0,447 dan \frac1√3 akar yang dicapai berubah dengan setiap pergeseran kecil awalnya. Jadi perubahan kecil pada x_0 dapat mengubah jawabannya.

Pengaman. Gambar fungsinya lebih dahulu; mulai dari selang [a,b] dengan f(a)f(b)<0 dan kembali ke langkah bisection bila langkah Newton keluar dari selang; batasi banyaknya langkah; berhenti berdasarkan |x_n+1-x_n| dan |f(x_n+1)| sekaligus.

Widget pertama menunjukkan tiap kegagalan dengan langkahnya, dan yang kedua mewarnai nilai awal menurut akar yang dicapainya.

Di mana metode Newton dipakai?

Metode Newton ada di balik akar kuadrat dan pembagian banyak kalkulator dan program, dan di balik setiap masalah yang berujung pada penyelesaian satu persamaan.

Akar kuadrat. Untuk f(x)=x^2-a rumusnya x_n+1=\frac12\left(x_n+\frac ax_n\right): ganti tebakan dengan rata-rata x_n dan \frac ax_n, yang satu terlalu kecil dan yang lain terlalu besar. Untuk x^n-a turunannya lenyap menjadi x_n+1=((n-1) x_n+(a)/(x_n^ n-1))/(n). Pembagian. Untuk f(x)=\frac1x-a akarnya \frac1a dan rumusnya menyederhana menjadi x_n+1=x_n(2-a x_n), tanpa pembagian sama sekali: komputer dapat mencari kebalikan hanya dengan perkalian dan pengurangan, asalkan 0<x_0<\frac2a.

Optimisasi. Nilai ekstrem g ada di akar g' (lihat soal optimisasi), sehingga metode Newton yang diterapkan pada f=g' memberi x_n+1=x_n-(g'(x_n))/(g''(x_n)). Pada banyak peubah gagasan yang sama, dengan gradien dan turunan kedua, adalah inti optimisasi numerik dan penyelesaian sistem persamaan.

Persamaan lain. Tempat dua kurva berpotongan, posisi planet pada orbitnya, jarak terdekat kapal selam ke pelampung, keseimbangan campuran kimia: masing-masing adalah persamaan tanpa rumus dan dengan tebakan awal yang baik.

Cobalah kedua aturan di bawah. Ubah a, indeks akar, dan awalnya, dan perhatikan angka benarnya.

Bagaimana menulis kode metode Newton?

Dalam kode, metode Newton adalah perulangan tiga baris; ketelitiannya ada pada aturan berhenti. Berhenti ketika langkahnya kecil relatif terhadap x, menyerah setelah sejumlah langkah tetap, dan menolak membagi bila turunannya nol. SymPy dapat mencarikan f', dan tanpanya selisih pusat (f(x+h)-f(x-h))/(2h) adalah pengganti yang baik. Perulangan yang sama pada x^3-2x+2 dari 0 memperlihatkan siklusnya: iterasinya 0,1,0,1,…

import sympy as sp

x = sp.symbols('x')


def newton(f, x0, steps=6):
    """Newton's method for f(x) = 0, with f' found symbolically: the list of approximations."""
    g, dg = sp.lambdify(x, f), sp.lambdify(x, sp.diff(f, x))
    xs = [x0]
    for _ in range(steps):
        xs.append(xs[-1] - g(xs[-1]) / dg(xs[-1]))
    return xs


print([round(v, 10) for v in newton(x ** 2 - 2, 1.0)])
print([round(v, 10) for v in newton(x ** 3 - x - 1, 1.0)])
print([round(v, 10) for v in newton(x ** 3 - x - 1, 3.0, 8)])
print([round(v, 10) for v in newton(x ** 3 - 2 * x + 2, 0.0, 5)])
print(sp.nsolve(x ** 3 - x - 1, x, 1))
# [1.0, 1.5, 1.4166666667, 1.4142156863, 1.4142135624, 1.4142135624, 1.4142135624]
# [1.0, 1.5, 1.347826087, 1.325200399, 1.324718174, 1.3247179572, 1.3247179572]
# [3.0, 2.1153846154, 1.6042477584, 1.377421441, 1.3271331185, 1.3247233751, 1.3247179573, 1.3247179572, 1.3247179572]
# [0.0, 1.0, 0.0, 1.0, 0.0, 1.0]
# 1.32471795724475

// Newton's method with a central-difference derivative, a step limit and a flat-tangent check
const newton = (f, x0, { tol = 1e-12, max = 50 } = {}) => {
  let x = x0
  for (let n = 0; n < max; n++) {
    const h = 1e-6 * (1 + Math.abs(x))
    const d = (f(x + h) - f(x - h)) / (2 * h)
    if (d === 0 || !Number.isFinite(d)) return { x, n, status: 'flat' }
    const next = x - f(x) / d
    if (Math.abs(next - x) < tol * (1 + Math.abs(x))) return { x: next, n: n + 1, status: 'converged' }
    x = next
  }
  return { x, n: max, status: 'unfinished' }
}
const r1 = newton((x) => x ** 3 - x - 1, 1)
;[+r1.x.toFixed(10), r1.n, r1.status]                      // [1.3247179572, 6, 'converged']
const r2 = newton((x) => Math.cos(x) - x, 1)
;[+r2.x.toFixed(10), r2.n, r2.status]                      // [0.7390851332, 5, 'converged']: cos x = x
const r3 = newton((x) => x * x - 1, 0)
;[r3.x, r3.n, r3.status]                                    // [0, 0, 'flat']: the tangent at 0 is horizontal
const r4 = newton(Math.sin, 1.7)
;[+r4.x.toFixed(10), r4.n, r4.status]                      // [9.4247779608, 4, 'converged']: not the root 0 but 3 pi
newton((x) => x ** 3 - 2 * x + 2, 0, { max: 8 }).status    // 'unfinished': the iterates go 0, 1, 0, 1, ...

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main() {
  double a = 2;
  double x = 1;                                          // the first guess
  for (int n = 0; n <= 5; n++) {
    printf("%d %.12f %.12f\n", n, x, fabs(x - sqrt(a)));
    x = (x + a / x) / 2;                                 // Newton's method for x*x - a = 0
  }
  return 0;
}

/* output:
0 1.000000000000 0.414213562373
1 1.500000000000 0.085786437627
2 1.416666666667 0.002453104294
3 1.414215686275 0.000002123901
4 1.414213562375 0.000000000002
5 1.414213562373 0.000000000000
*/

Siapa yang menemukan metode Newton?

Gagasan memperbaiki tebakan akar berumur empat ribu tahun, dan metode ini memakai nama Newton dan Raphson karena cara mereka menuliskannya, bukan karena mereka yang pertama memperbaiki tebakan.

• Babilonia, sekitar 1800–1600 SM. Lempeng tanah liat YBC 7289 memberi √2 sebagai 1;24,51,10 dalam basis 60, yaitu 1,41421296…, benar sampai enam desimal. Merata-ratakan tebakan dan bilangan dibagi tebakan, aturan pada Contoh 1, adalah cara yang mungkin untuk mendapatkannya.
• Heron dari Aleksandria, abad pertama. Heron menjelaskan aturan perata-rataan untuk akar kuadrat, itulah sebabnya rumus itu disebut juga metode Heron.
• Isaac Newton, 1669. Dalam De analysi, ditulis pada 1669 dan dicetak pada 1711, Newton menyelesaikan y^3-2y-5=0 dengan mulai dari 2, menulis y=2+p, membuang pangkat p di atas satu, dan mengulang pada polinom baru. Itu proses aljabar pada persamaannya, bukan rumus untuk x_n+1.
• Joseph Raphson, 1690. Raphson menerbitkan cara mengulang satu rumus untuk polinom, tanpa menulis ulang persamaan setiap kali, yang merupakan bentuk metode yang kita pakai.
• Thomas Simpson, 1740. Simpson menjelaskan metode itu dengan turunan, bentuk x-(f(x))/(f'(x)), untuk persamaan apa pun dan bahkan untuk dua persamaan sekaligus.
• Fourier dan Cauchy, 1820-an. Joseph Fourier dan Augustin-Louis Cauchy mempelajari kapan metode ini konvergen.
• Cayley, 1879. Arthur Cayley bertanya akar mana yang dicapai metode Newton dari awal di bidang kompleks. Untuk kuadrat bidang terbelah di sepanjang garis; untuk kubik batasnya menjadi fraktal yang kemudian dipelajari Julia dan Fatou.
• Kantorovich, 1948. Leonid Kantorovich membuktikan teorema konvergensi yang hanya memerlukan syarat di titik awal, dan yang berlaku untuk sistem persamaan.

Kesalahan apa yang sering terjadi pada metode Newton?

Kesalahan paling umum pada metode Newton adalah sembilan hal berikut, masing-masing dengan pernyataan yang benar.

Latihan: uji pemahamanmu

Soal-soal ini mencampur semua yang dibahas di atas. Jika jawabanmu belum tepat, perhatikan petunjuk yang tersedia, lalu coba kembali.

Ringkasan: metode Newton sekilas

• Rumusnya: x_n+1=x_n-(f(x_n))/(f'(x_n)), nol garis singgung di x_n; ia memerlukan f'(x_n)\ne0.
• Cara memakainya: tulis persamaan sebagai f(x)=0, pilih x_0 dari grafik atau perubahan tanda, beriterasi, dan berhenti ketika langkah dan f(x_n) sama-sama kecil.
• Kecepatan: kuadrat di akar sederhana, e_n+1=(f''(\xi))/(2f'(x_n))e_n^2; linear, dengan rasio (m-1)/(m), di akar berkelipatan m.
• Kegagalan: garis singgung mendatar, siklus (x^3-2x+2 dari 0), menjauh (x^(1/3), \arctan x jauh di luar), akar yang keliru (\sin x dari 1,7).
• Daerah tarikan: awal yang mencapai tiap akar; batas di antaranya dapat sangat halus.
• Dengan tangan: \frac12\left(x+\frac ax\right) untuk √ a dan x(2-ax) untuk \frac1a.
• Pengaman: selang dan bisection sebagai cadangan, batas langkah, dan pemeriksaan langkah serta |f|.
• Berikutnya: antiturunan, kebalikan dari diferensiasi.
• Kode: perulangan dengan aturan berhenti; SymPy lambdify dan diff, atau selisih pusat.

Glosarium: istilah penting

Akar

Bilangan r tempat fungsi bernilai nol, f(r) = 0, sehingga merupakan solusi persamaan f(x) = 0.

Metode Newton

Iterasi yang mengganti setiap hampiran akar dengan titik tempat garis singgung fungsi memotong sumbu-x.

Iterasi

Mengulang rumus yang sama, setiap kali pada hasil langkah terakhir, untuk menghasilkan barisan hampiran.

Konvergensi kuadrat

Laju yang galatnya kira-kira dikuadratkan di setiap langkah, sehingga banyaknya angka benar berlipat dua.

Akar ganda

Akar tempat turunannya juga nol, sehingga fungsi memiliki faktor (x − r) berpangkat m yang lebih besar dari satu.

Daerah tarikan

Himpunan nilai awal tempat suatu iterasi konvergen ke akar tertentu.

Metode bisection

Metode pencarian akar yang membagi dua selang tempat fungsi berubah tanda; ia lebih lambat daripada metode Newton tetapi tidak dapat gagal di dalam selang.

Pertanyaan yang sering diajukan

Referensi

1. Joel Hass, Christopher Heil, Maurice D. Weir et al. (2023). Thomas' Calculus: Early Transcendentals in SI Units (15th ed.), Section 4.7: Newton's Method. Pearson.
2. James Stewart (2015). Calculus (8th ed.), section 4.8: Newton’s Method. Cengage Learning.
3. Joseph Raphson (1690). Analysis aequationum universalis. London.
4. Thomas Simpson (1740). Essay on the Several Parts of the Doctrine of Fluxions, Section on the Resolution of Equations. London.

Artikel terkait

• Linearisasi dan Diferensial: Linearisasi dan diferensial: hampiran garis singgung L(x) = f(a) + f′(a)(x − a), df = f′(x) dx, perkiraan, galat, dan perubahan persen, dengan contoh dan kode.
• Optimisasi Terapan: Optimisasi terapan dengan turunan: empat langkah soal cerita maksimum dan minimum, geometri, hukum Snell, biaya marjinal dan persediaan, dengan contoh dan kode.
• Kecekungan dan Penggambaran Kurva: Kecekungan dan penggambaran kurva: turunan kedua, titik belok, Uji Turunan Kedua, dan tujuh langkah menggambar grafik, dengan contoh dan kode.
• Teorema Nilai Rata-rata: Teorema Nilai Rata-rata dan Teorema Rolle: pernyataan, bukti, cara mencari c, kecepatan dan laju, serta akibatnya tentang fungsi konstan, dengan contoh dan kode.