Root Finding

Banyak masalah sains dan teknik pada akhirnya bermuara pada satu pertanyaan: untuk berapa nilai x fungsi f(x) bernilai nol? Titik ekuilibrium sistem, titik impas (break-even) bisnis, dan frekuensi resonansi rangkaian listrik semuanya adalah akar persamaan. Masalahnya, kebanyakan persamaan tidak bisa diselesaikan dengan rumus tertutup, sehingga kita mencari akarnya secara iteratif: mulai dari tebakan, lalu memperbaikinya berulang kali sampai cukup dekat. Chapter ini membangun tiga metode klasik — bisection manual, Newton-Raphson manual, dan fungsi bawaan fzero — lalu membandingkan kecepatan konvergensi dan keandalannya.

Masalah f(x) = 0 dan Interval Pembungkus #

Aturan mainnya: akar adalah nilai x yang membuat f(x) = 0. Alat kunci untuk menjamin akar ada adalah tanda: bila fungsi kontinu di [a, b] dan f(a) * f(b) < 0 (tanda berlawanan), maka minimal satu akar terjebak di antara a dan b — inilah intermediate value theorem dari kalkulus. Contoh yang akan kita pakai sepanjang chapter: f(x) = cos(x) - x.

f = @(x) cos(x) - x;
fprintf('f(0) = %.6f\n', f(0));
fprintf('f(1) = %.6f\n', f(1));

Output yang Dihasilkan:

f(0) = 1.000000
f(1) = -0.459698

Nilai f(0) positif dan f(1) negatif, jadi satu akar pasti berada di interval [0, 1] — akar persamaan cos(x) = x, yang nilainya sebenarnya sekitar 0.73908513.

Bisection: Membelah Interval #

Metode bisection bekerja seperti tebak-tebakan biner: belah interval jadi dua, cari di mana tanda berubah, buang setengah yang tidak memuat akar, ulangi. Mekanisme di balik layar: setiap iterasi memangkas lebar interval menjadi tepat separuh, sehingga galat maksimum (setengah lebar interval) juga terpangkas separuh — konvergensi pasti, walau pelan.

Flowchart di atas merangkum siklusnya: hitung titik tengah c, uji tanda f(a) * f(c), geser salah satu batas ke c, lalu periksa apakah interval sudah cukup sempit. Implementasinya memakai pola while dengan dua penjaga (tol dan maxIter) yang kita kenal dari chapter while loop:

a = 0; b = 1;
tol = 1e-6; maxIter = 100; iter = 0;
while (b - a) > tol && iter < maxIter
    c = (a + b) / 2;
    if f(a) * f(c) < 0
        b = c;   % akar di setengah kiri
    else
        a = c;   % akar di setengah kanan
    end
    iter = iter + 1;
end
fprintf('bisection: akar = %.8f, iterasi = %d\n', (a + b) / 2, iter);

Output yang Dihasilkan:

bisection: akar = 0.73908472, iterasi = 20

Mari kita bedah baris-baris kode di atas:

1. Baris 1 (a = 0; b = 1): interval awal yang tanda fungsinya berlawanan — syarat wajib bisection.
2. Baris 3 (while (b - a) > tol && iter < maxIter): loop berhenti saat lebar interval sudah di bawah toleransi 1e-6, dengan maxIter sebagai jaring pengaman.
3. Baris 5-9 (if f(a) * f(c) < 0): hasil kali negatif berarti tanda berlawanan — akar di setengah kiri, batas b ditarik ke c; selain itu akar di setengah kanan dan a yang ditarik.
4. Baris 13 (fprintf): hasil 0.73908472 akurat sampai 6 desimal; dibutuhkan 20 iterasi karena interval [0,1] harus dibelah 20 kali untuk turun di bawah 1e-6 (2^10 ≈ 1000, jadi 20 pembelahan ≈ faktor satu juta).

Newton-Raphson: Menunggangi Turunan #

Newton-Raphson memakai informasi yang jauh lebih kaya: kemiringan fungsi. Aturannya satu baris: xBaru = x - f(x) / f'(x). Mekanisme di balik layar: MATLAB menarik garis singgung di titik (x, f(x)), lalu melompat ke tempat garis singgung itu memotong sumbu-x — perpotongan itu menjadi tebakan baru yang jauh lebih dekat ke akar.

df = @(x) -sin(x) - 1;   % turunan f(x) = cos(x) - x
x = 1;
for k = 1:50
    xBaru = x - f(x) / df(x);
    fprintf('iter %d: x = %.8f\n', k, xBaru);
    if abs(xBaru - x) < 1e-12
        x = xBaru;
        break;
    end
    x = xBaru;
end
fprintf('newton: akar = %.8f, iterasi = %d\n', x, k);

Output yang Dihasilkan:

iter 1: x = 0.75036387
iter 2: x = 0.73911289
iter 3: x = 0.73908513
iter 4: x = 0.73908513
iter 5: x = 0.73908513
newton: akar = 0.73908513, iterasi = 5

Mari kita bedah baris-baris kode di atas:

1. Baris 1 (df = @(x) -sin(x) - 1): function handle untuk turunan f(x) — Newton menuntut turunan analitik; tanpa turunan, metode ini tidak jalan.
2. Baris 4 (xBaru = x - f(x) / df(x)): rumus inti Newton — tebakan lama dikoreksi sebesar f(x) / f'(x), yaitu sejauh mana garis singgung harus digeser untuk mencapai nol.
3. Baris 6-9 (if abs(xBaru - x) < 1e-12 ... break): konvergensi dinyatakan lewat perubahan tebakan yang sudah sangat kecil, bukan lebar interval seperti bisection.
4. Baris 12 (fprintf): lima iterasi mengalahkan dua puluh iterasi bisection. Perhatikan jejaknya: dari 0.750 ke 0.7391 (3 desimal benar), lalu 0.73908513 (8 desimal benar) — jumlah digit yang benar kira-kira berlipat dua tiap iterasi. Inilah konvergensi kuadratik, jauh lebih cepat daripada pemangkasan separuh milik bisection.

fzero: Solusi Bawaan MATLAB #

Untuk pekerjaan nyata, MATLAB menyediakan fzero(). Fungsi ini menerima function handle dan bracket [a, b], lalu menggabungkan bisection, secant, dan interpolasi kuadratik secara adaptif — kecepatan metode sekantan dengan jaminan keandalan bracket:

akar = fzero(f, [0, 1]);
fprintf('fzero: akar = %.8f\n', akar);

Output yang Dihasilkan:

fzero: akar = 0.73908513

Baris pertama memanggil fzero() dengan bracket [0, 1] — bentuk yang sama dengan interval bisection kita; fzero juga menerima tebakan tunggal seperti fzero(f, 0.5), tetapi bentuk bracket menjamin akar ditemukan. Hasilnya identik dengan Newton (0.73908513) tanpa kita menulis satu baris iterasi pun.

Konvergensi vs Keandalan #

Kecepatan Newton ada harganya. Karena Newton melompat mengikuti garis singgung, fungsi yang landai di dekat akar bisa melempar tebakan makin jauh. Kasus ekstremnya mencari akar g(x) = x^(1/3) = 0: turunannya g'(x) = (1/3) * x^(-2/3) melandai drastis saat x mengecil, dan rumus Newton melempar tebakan berlipat dua dengan ganti tanda:

g  = @(x) x.^(1/3);
dg = @(x) (1/3) * x.^(-2/3);
x = 1;
for k = 1:5
    x = x - g(x) / dg(x);
    fprintf('iter %d: x = %.1f\n', k, x);
end

Output yang Dihasilkan:

iter 1: x = -2.0
iter 2: x = 4.0
iter 3: x = -8.0
iter 4: x = 16.0
iter 5: x = -32.0

Bukannya mendekati nol, tebakan justru melompat 1 -> -2 -> 4 -> -8 -> 16 — Newton divergen meski akarnya tepat di 0 dan berada tepat di antara nilai-nilai itu. Bisection dengan bracket [-1, 1] akan menemukan akar ini tanpa drama. Ketiga metode punya profil yang saling melengkapi:

Berkas contoh.m pada bagian bawah halaman menjalankan ketiga metode ditambah demonstrasi divergensi dalam satu script utuh.

Ringkasan #

Root finding mencari x dengan f(x) = 0 secara iteratif, dan tanda berlawanan f(a) * f(b) < 0 menjamin akar terjebak dalam bracket. Bisection membelah bracket separuh per iterasi — lambat tetapi selalu konvergen (20 iterasi untuk toleransi 1e-6 pada interval [0,1]). Newton-Raphson menunggangi turunan x - f(x)/f'(x) dan konvergen kuadratik (5 iterasi untuk kasus yang sama), tetapi bisa divergen total pada fungsi landai seperti x^(1/3). fzero menggabungkan kekuatan keduanya dan menjadi pilihan default; pilih metode manual saat kita butuh kendali penuh atas proses iterasi.