IF Notes

Newton-Raphson dan Versi Rekursif Pencarian Akar

7 min read

Back to IF5100 Pemrograman untuk Data Analitik

Newton-Raphson dan Versi Rekursif Pencarian Akar

Questions/Cues

  • Apa ide inti metode Newton-Raphson, dan mengapa ia disebut gradient-based?
  • Apa hubungan Newton-Raphson dengan backpropagation pada neural network?
  • Bagaimana rumus umum x_(r+1) = x_r - f(x_r)/f'(x_r) diturunkan menjadi kode untuk akar kuadrat?
  • Bagaimana bentuk rekursif dari bisection search dan Newton-Raphson?
  • Mengapa dibutuhkan helper function untuk membuat versi rekursif dari fungsi-fungsi ini?

Reference Points

  • IF5100 — Simple-Numerical Programs (Slides 5-8)

Newton-Raphson adalah metode pencarian akar yang berbasis gradien (gradient-based) — alih-alih membagi dua interval seperti bisection, ia mengikuti garis singgung (tangent line) dari fungsi di titik tebakan saat ini untuk melompat langsung ke perkiraan akar berikutnya. Karena memanfaatkan informasi arah (turunan/gradien), konvergensinya jauh lebih cepat dibanding bisection search.

Metode ini bukan sekadar trik numerik kecil: algoritma optimisasi di balik backpropagation pada pelatihan neural network memakai prinsip yang sama — bergerak mengikuti gradien fungsi menuju titik optimal — hanya saja dilakukan dalam ruang berdimensi sangat tinggi (jutaan parameter), bukan satu variabel seperti di sini.

Rumus umum Newton-Raphson berlaku untuk fungsi polinomial apa pun:

Idenya: pada tebakan x_r, kita hitung nilai fungsi f(x_r) dan kemiringan garis singgungnya f'(x_r). Garis singgung ini kita ikuti sampai memotong sumbu-x — titik potong itulah tebakan berikutnya, x_(r+1). Diulangi terus, tebakan akan mendekati akar sebenarnya dengan sangat cepat karena setiap langkah “melompat” mengikuti bentuk kurva, bukan sekadar membagi interval secara membabi-buta.

flowchart LR
    X0["x_0 (tebakan awal)"] -->|"ikuti garis singgung di x_0"| X1["x_1 (lebih dekat ke akar)"]
    X1 -->|"ikuti garis singgung di x_1"| X2["x_2 (lebih dekat lagi)"]
    X2 -->|"..."| XR["x_r ≈ akar sebenarnya"]

Newton-Raphson untuk Akar Kuadrat

Untuk mencari akar kuadrat dari x, kita cari akar dari fungsi f(guess) = guess**2 - x (nilai guess di mana f(guess) = 0 berarti guess**2 = x, yaitu guess adalah akar kuadrat x). Turunannya f'(guess) = 2*guess. Substitusi ke rumus umum:

guess_baru = guess - (guess**2 - x) / (2*guess)

def sqrt_nr(x, epsilon=0.01):
    """
    square root newton raphson.
    """
    guess = x/2
    while abs(guess**2 - x)>=epsilon:
        print(guess)
        guess = guess - ((guess**2-x)/(2*guess))
 
    print(f"{guess} is close to square root of {x}")

Tebakan awal guess = x/2 cukup sembarang (asalkan tidak nol, karena 2*guess menjadi pembagi). Dibandingkan bisection search yang butuh puluhan iterasi untuk presisi tinggi, Newton-Raphson biasanya konvergen hanya dalam beberapa iterasi saja karena laju konvergensinya kuadratik (jumlah digit presisi kira-kira berlipat ganda tiap iterasi), bukan sekadar linear/logaritmik seperti bisection.

Pertanyaan alami: bisakah sqrt_bs dan sqrt_nr — yang aslinya ditulis iteratif memakai while — ditulis ulang secara rekursif? Ini menyambung langsung ke konsep base case dan recursive step yang sudah dibahas sebelumnya di materi Rekursi: base case di sini adalah kondisi “tebakan sudah cukup dekat” (abs(ans**2 - x) < epsilon), dan recursive step adalah “perbarui tebakan, lalu panggil ulang fungsi dengan tebakan baru”.

Perlu dicatat trade-off yang sama seperti dibahas di materi rekursi sebelumnya: versi rekursif menghabiskan lebih banyak memori dibanding versi iteratif, karena setiap pemanggilan rekursif menambah stack frame baru yang menyimpan local scope pemanggilan tersebut — sedangkan versi iteratif hanya memakai satu frame yang diperbarui berulang lewat loop.

Catatan istilah: "Recurrence?" "Recurrence?" padahal yang dimaksud adalah rekursi (recursion, fungsi memanggil dirinya sendiri), bukan recurrence relation (relasi rekurens) dalam analisis algoritma. Isinya hanya pertanyaan "bisakah kamu membuat versi rekursif dari bisection dan Newton-Raphson?" beserta peringatan memori stack frame.

Slide menamai bagian ini

Slide Newton-Raphson (slide 7) sendiri hanya menyatakan “much faster convergence even compared to bisection” tanpa tabel atau grafik pembanding. Sebagai gambaran (dihitung dengan kode di atas, x = 24): untuk epsilon = 0.01, 0.0001, 0.000001, Newton-Raphson butuh 4, 4, 5 iterasi sedangkan bisection butuh 9, 16, 26 iterasi.

Bisection Search, Versi Rekursif

def sqrt_bs_helper(x, epsilon=0.01):
    """
    square root bisection, recursive
    """
    def sqrt_bs_recc(low, high):
        ans = (high + low) / 2.0
        if abs(ans**2 - x) < epsilon:
            print(ans, 'is close to square root of', x)
            return ans
        print('low =', low, 'high =', high, 'ans =', ans)
        if ans**2 < x:
            return sqrt_bs_recc(ans, high)
        else:
            return sqrt_bs_recc(low, ans)
 
    low = 0.0
    high = max(1.0, x)
    return sqrt_bs_recc(low, high)

Newton-Raphson, Versi Rekursif

def sqrt_nr_helper(x, epsilon=0.01):
    """
    square root newton raphson, recursive
    """
    def sqrt_nr_recc(guess):
        if abs(guess**2 - x) >= epsilon:
            print(guess)
            return sqrt_nr_recc(guess -
                    ((guess**2 - x) / (2 * guess)))
        print(f"{guess} is close to square root of {x}")
        return guess
 
    return sqrt_nr_recc(x / 2)

Mengapa Perlu Helper Function

Poin yang tidak langsung terlihat: kenapa tidak langsung menulis sqrt_bs(low, high) rekursif begitu saja seperti factorial(n)? Sebabnya, fungsi rekursif untuk masalah ini butuh parameter tambahan (low dan high untuk bisection) atau nilai yang ditutup dalam closure (x dan epsilon untuk Newton-Raphson) yang tidak seharusnya dipikirkan ulang oleh pemanggil setiap kali memanggil fungsi. Pemanggil dari luar hanya ingin memanggil sqrt_bs_helper(x) — bukan sqrt_bs_recc(0.0, max(1.0, x)) dengan menghitung sendiri batas awalnya.

Solusinya: buat fungsi helper luar yang tidak rekursif, satu-satunya tugasnya adalah menginisialisasi state awal (low, high, atau menutup x/epsilon lewat closure) lalu memanggil fungsi rekursif bagian dalam (sqrt_bs_recc / sqrt_nr_recc) untuk pertama kali. Fungsi rekursif bagian dalam ini bisa didefinisikan di dalam fungsi helper (nested function) sehingga otomatis mendapat akses ke x dan epsilon dari enclosing scope tanpa perlu diteruskan ulang sebagai parameter di setiap pemanggilan rekursif. Pola ini — helper function membungkus fungsi rekursif — sangat umum ketika rekursi butuh state tambahan yang bukan bagian dari “antarmuka” alami fungsi tersebut bagi pemanggil.

Summary

Newton-Raphson adalah metode pencarian akar berbasis gradien yang mengikuti garis singgung fungsi di setiap tebakan, memakai rumus umum x_(r+1) = x_r - f(x_r)/f'(x_r) — prinsip yang sama dipakai (dalam dimensi jauh lebih tinggi) oleh optimizer di balik backpropagation. Untuk akar kuadrat, f(guess) = guess**2 - x dan f'(guess) = 2*guess, sehingga update-nya guess - (guess**2-x)/(2*guess); konvergensinya kuadratik, jauh lebih cepat dari bisection. Baik sqrt_bs maupun sqrt_nr bisa ditulis ulang secara rekursif (base case: tebakan cukup dekat; recursive step: perbarui tebakan lalu panggil ulang), namun rekursi butuh memori stack frame ekstra. Karena recursive step butuh parameter tambahan (low/high) atau closure (x/epsilon) yang tidak seharusnya dipikirkan pemanggil, dipakai pola helper function: fungsi luar non-rekursif menginisialisasi state lalu memanggil fungsi rekursif bagian dalam (nested function) untuk pertama kali.

Graph View

Backlinks