(Pertemuan 2) Metode Root-Finding: Secant, Regula-Falsi, Finite-Difference

Secant Method, Regula-Falsi Method, Finite-Difference

Offline di Departemen Matematika
Author

Aslab Mata Kuliah Praktikum Metode Numerik

Published

March 10, 2025

Kembali ke Metode Numerik

Materi Pembahasan:

  1. Finite-Difference Newton Method

  2. Secant Method

  3. Regula-False Method

  4. Sequence Barisan

  5. Aitken Method

  6. Steffensen Method

  7. Diskusi

Praktikum Metode Numerik PTA 2024-2025
Departemen Matematika FMIPA Universitas Indonesia

Metode Newton dengan Beda Hingga (Finite-Difference Newton’s Method)

Salah satu kekurangan Metode Newton yang biasa adalah harus mengetahui rumus turunannya secara analitik. Sebelum adanya CAS seperti SymPy, turunan analitik harus dihitung secara manual dengan kalkulus. Kalau bentuk rumus untuk \(f(x)\) sangat rumit, perhitungan turunan menjadi jauh lebih rumit. Untuk menghindari menghitung turunan secara analitik, kita dapat menggunakan definisi turunan (yang menggunakan limit):

\[f'(x) = \lim_{h \rightarrow 0} \frac{f(x+h) - f(x)}{h}\]

dengan memilih nilai \(h\) yang cukup kecil (sayangnya, kita tidak bisa membuat limit \(h\) menuju nol). Nilai \(h\) yang cukup kecil itu disebut suatu beda hingga (finite difference).

Sehingga, modifikasi metode Newton ini bisa disebut Metode Newton dengan Beda Hingga (Finite-Difference Newton’s Method). Untuk fungsi \(f\) yang kontinu, akar persamaan \(f(x) = 0\) bisa ditentukan dengan iterasi sebagai berikut:

\[\begin{align*} p_n &= p_{n-1} - \frac{f(p_{n-1})}{\left(\frac{f\left(p_{n-1}+h\right)-f(p_{n-1})}{h}\right)} \\ &= p_{n-1} - \frac{f(p_{n-1})h}{f(p_{n-1}+h)-f(p_{n-1})} \end{align*}\]

dengan tebakan awal \(p_0\). Perhatikan bahwa \(f'(p_{n-1})\) pada metode Newton yang biasa itu telah digantikan dengan

\[f'(p_{n-1}) \approx \frac{f(p_{n-1}+h) - f(p_{n-1})}{h}\]

Tujuan modifikasi tersebut adalah agar iterasi dapat dilakukan pada titik di mana turunannya tidak ada, atau ketika turunan analitik sulit diperoleh.

def FiniteDifferenceNewton(f,fp,p0,tolerance):
    p = p0 - f(p0)/fp(p0)
    abs_error = abs(p-p0)
    p0 = p

    while abs_error > tolerance:
        p = p0 - f(p0)/fp(p0)
        abs_error = abs(p-p0)
        p0 = p
    return p
from numpy import sin, cos, tan, log, exp, sqrt

formula = input("Masukkan fungsi: ")
def f(x):
    return eval(formula)

def fp(x, h=10**(-12)):
    return (f(x+h)-f(x))/h

starting_point = eval(input("Masukkan titik awal iterasi: "))
tolerance = eval(input("Masukkan toleransi aproksimasi: "))

akar_fd = FiniteDifferenceNewton(f,fp,starting_point,tolerance)

print(f"Akar dari persamaan f(x) = {formula} adalah x = {akar_fd}")
Masukkan fungsi: 2*x - 3*cos(x) + exp(-5*x) - 9
Masukkan titik awal iterasi: -1
Masukkan toleransi aproksimasi: 10**(-7)
Akar dari persamaan f(x) = 2*x - 3*cos(x) + exp(-5*x) - 9 adalah x = -0.5073224866379543

Metode Secant

Pada Metode Newton dengan Beda Hingga, nilai \(h\) konstan. Kalau kita punya dua tebakan awal yang saling dekat, misal \(p_0\) dan \(p_1\), kita bisa saja memanfaatkannya dengan memasang \(h = p_1 - p_0\). Bahkan, ketika iterasi \(p_n\) sudah semakin dekat menuju akar, jarak antara \(p_{n-1}\) dan \(p_{n-2}\) menjadi semakin kecil. Sehingga, dengan memasang nilai \(h = p_{n-2} - p_{n-1}\) atau \(h = p_{n-1} - p_{n-2}\), kita berhasil membuat limit \(h\) menuju nol.

Modifikasi ini disebut Metode Secant, dengan iterasi sebagai berikut untuk menentukan penyelesaian \(f(x) = 0\) dengan fungsi \(f\) yang kontinu:

\[\begin{align*} p_n &= p_{n-1} - \frac{f(p_{n-1})}{\left(\frac{f(p_{n-1})-f(p_{n-2})}{p_{n-1}-p_{n-2}}\right)} \\ &= p_{n-1} - \frac{f(p_{n-1})(p_{n-1} - p_{n-2})}{f(p_{n-1}) - f(p_{n-2})} \end{align*}\]

Dibandingkan Metode Newton yang biasa, Metode Secant menggantikan \(f'(p_{n-1})\) dengan

\[f'(p_{n-1}) \approx \frac{f(p_{n-1}) - f(p_{n-2})}{p_{n-1} - p_{n-2}}\]

sehingga, tidak seperti Metode Newton yang hanya memerlukan satu tebakan awal, Metode Secant membutuhkan dua tebakan awal, yaitu \(p_0\) dan \(p_1\). Namun, dibandingkan dengan Metode Newton dengan Beda Hingga, nilai \(h\) atau beda hingga tersebut tidak perlu ditentukan secara manual.

Menariknya, Metode Secant memiliki order of convergence = \(\phi \approx 1.618\).

def Secant(f,p0,p1,tolerance):
    p = p1 - (f(p1)*(p1-p0))/(f(p1)-f(p0))
    abs_error = abs(p-p1)
    p0 = p1
    p1 = p

    while abs_error > tolerance:
        p = p1 - (f(p1)*(p1-p0))/(f(p1)-f(p0))
        abs_error = abs(p-p1)
        p0 = p1
        p1 = p
    return p
from numpy import sin, cos, tan, log, exp, sqrt
formula = input("Masukkan formula fungsi: ")

def f(x):
    return eval(formula)

titik_1 = eval(input("Masukkan titik awal pertama: "))
titik_2 = eval(input("Masukkan titik awal kedua: "))
tolerance = eval(input("Masukkan toleransi aproksimasi: "))

akar_secant = Secant(f,titik_1,titik_2,tolerance)

print(f"Akar dari persamaan f(x) = {formula} adalah x = {akar_secant}")
Masukkan formula fungsi: 2*x - 3*cos(x) + exp(-5*x) - 9
Masukkan titik awal pertama: -1
Masukkan titik awal kedua: -2
Masukkan toleransi aproksimasi: 10**(-7)
Akar dari persamaan f(x) = 2*x - 3*cos(x) + exp(-5*x) - 9 adalah x = -0.5073224866425831

Metode Regula Falsi

Sejauh ini, kita sudah membahas beberapa metode root-finding atau aproksimasi akar, yaitu:

  • Metode Bisection
  • Metode Fixed-Point
  • Metode Newton biasa (dengan turunan analitik)
  • Metode Newton dengan Beda Hingga (finite-difference Newton’s method)
  • Metode Secant

Di antara semua metode tersebut, hanya Metode Bisection yang dijamin konvergen menuju akar di interval yang diberikan; semua metode lain ada kemungkinan divergen (menjauh dari akar, seperti metode fixed-point) atau gagal karena terjadi pembagian nol. Sayangnya, Metode Bisection termasuk metode yang pelan di antara metode numerik lainnya.

Untuk menjaga jaminan kekonvergenan oleh Metode Bisection tetapi memperbaiki kecepatan kekonvergenannya, kita bisa memodifikasi Metode Bisection, yaitu memodifikasi cara menentukan \(p\) yang baru yang akan mempersempit interval. Perhatikan bahwa Metode Bisection membutuhkan dua “tebakan awal” (lebih tepatnya dua batasan interval), sedangkan metode di atas yang juga membutuhkan dua tebakan awal hanyalah Metode Secant.

Apakah kita bisa menggunakan Metode Bisection, tetapi dengan modifikasi menentukan \(p\) seperti Metode Secant, agar mendapatkan order of convergence seperti Metode Secant?

Jawabannya adalah bisa, dan modifikasi tersebut dinamakan Metode Regula Falsi. Sehingga, Metode Regula Falsi bisa disebut perpaduan antara Metode Bisection dan Metode Secant.

Sebenarnya, perbedaan algoritma Metode Bisection dan Metode Regula Falsi hanya di satu baris saja, yaitu mengubah baris

\[p=\frac{a+b}{2}\]

menjadi

\[p = b - \frac{f(b)(b-a)}{f(b) - f(a)}\]

sesuai Metode Secant. Perhatikan bahwa Metode Secant biasanya membutuhkan dua tebakan awal yang tidak harus sama dengan batasan interval, sedangkan Metode Regula Falsi secara otomatis menggunakan kedua batasan interval \([a,b]\) sebagai dua tebakan awal.

Untuk pembuatan kode Metode Regula Falsi, kami serahkan ke kalian. Gampang, kok! Tinggal mengubah beberapa baris saja (baris yang menentukan nilai \(p\) yang baru) pada kode Metode Bisection, yaitu mengambil baris tersebut dari kode Metode Secant, kemudian menyesuaikan kedua tebakan awal menjadi kedua batasan interval.

Seperti Metode Secant, Metode Regula Falsi juga memiliki order of convergence = \(\phi \approx 1.618\).

def RegulaFalsi(f, p0, p1, tol, n = 1000):

    i = 2
    q0 = f(p0)
    q1 = f(p1)

    while i < n:
        p = p1 - q1*(p1 - p0)/(q1 - q0)

        if abs(p - p1) < tol:
            return p

        i += 1

        q = f(p)

        if q * q1 < 0 :
            p0 = p1
            q0 = q1

        p1 = p
        q1 = q

    return "Aproksimasi Gagal"
from numpy import sin, cos, tan, log, exp, sqrt, pi
formula = input("Masukkan formula fungsi: ")

def f(x):
    return eval(formula)

titik_1 = eval(input("Masukkan titik awal pertama: "))
titik_2 = eval(input("Masukkan titik awal kedua: "))
tolerance = eval(input("Masukkan toleransi aproksimasi: "))

akar_falsi = RegulaFalsi(f, titik_1, titik_2, tolerance)

print(f"Akar dari persamaan f(x) = {formula} adalah x = {akar_falsi}")

Apa itu barisan? (penjelasan tanpa kode)

Suatu “barisan” (sequence) adalah sekumpulan angka yang berurut. Artinya, pada suatu barisan, ada yang bisa disebut angka pertama (atau suku pertama), angka kedua (suku kedua), angka ketiga (suku ketiga), dan sebagainya. Banyaknya suku bisa berhingga maupun tak terhingga.

Suku-suku pada suatu barisan itu bisa saja ditentukan secara manual atau sesuka hati, atau bisa juga menggunakan rumus. Intinya, suku-suku suatu barisan itu bisa diperoleh dari manapun, bahkan dari hasil iterasi metode numerik (\(p_0\), \(p_1\), \(p_2\), \(p_3\), …) juga bisa.

Oleh karena itu, contoh barisan berhingga adalah hasil iterasi fixed-point, misalnya dengan \(g(x) = 1 + \frac{1}{x}\), tebakan awal \(p_0 = 2\), dan batas toleransi \(10^{-7}\):

\[\begin{align*} (& 1.5, 1.6666666666666665, 1.6, \\ & 1.625, 1.6153846153846154, \\ & 1.619047619047619, \dots, \\ & 1.6180339631667064) \end{align*}\]

Proses tersebut berakhir setelah 17 iterasi, sehingga barisan tersebut memiliki 17 suku.

Barisan tersebut bisa diberi nama, seperti \(p_n\) dengan \(n = 1, 2, 3, \dots, 17\), yang bisa dituliskan \(\left\{p_n\right\}_{n=1}^{17}\) dengan kurung kurawal.

Contoh barisan tak berhingga adalah barisan aritmetika dan barisan geometri, seperti:

\[(-5, -2, 1, 4, 7, 10, 13, 16, 19, \dots)\]

\[\left(16, 8, 4, 2, 1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots\right)\]

Barisan tak berhingga dengan nama \(p_n\) yang mulai dari suku \(n=1\) bisa ditulis \(\left\{p_n\right\}_{n=1}^{\infty}\) dengan kurung kurawal, atau singkatnya \((p_n)\) saja dengan kurung biasa (dengan begitu, biasanya ada asumsi bahwa barisan tersebut tak berhingga).

Metode Aitken

Alexander Aitken menemukan bahwa, untuk sembarang barisan (termasuk sembarang metode numerik) yang memiliki kekonvergenan linier, untuk nilai \(n\) yang besar, berlaku

\[\frac{p_{n+1} - p}{p_n - p} \approx \frac{p_{n+2} - p}{p_{n+1} - p}\]

di mana \(p\) adalah nilai yang ingin dicari, sedangkan \(p_n\), \(p_{n+1}\), dan \(p_{n+2}\) adalah tiga suku barisan (atau tiga hasil aproksimasi) berturut-turut. Artinya, perbandingan error (error ratio) antar dua pasang hasil iterasi (diperoleh dari tiga hasil iterasi berturut-turut) menjadi kurang lebih sama. Dengan manipulasi aljabar, diperoleh

\[p \approx p_n - \frac{\left(p_{n+1} - p_n\right)^2}{p_{n+2} - 2p_{n+1} + p_n}\]

seolah-olah ada jalur pintas untuk langsung mendapatkan nilai yang ingin dicari.

Tentu saja, sebelum menggunakan rumus ini, kita perlu menemukan tiga hasil aproksimasi pertama, yaitu \(p_0\), \(p_1\), dan \(p_2\). Kemudian, barulah kita tentukan \(p_3\) menggunakan rumus Aitken (hasil rumus Aitken biasa disebut \(\hat{p}_n\), sehingga bisa ditulis \(p_3 = \hat{p}_0\), karena perhitungan \(p_3\) memanfaatkan \(p_0\), \(p_1\) dan \(p_2\)).

Variabel \(\hat{p}\) biasa disebut p-hat atau p-cap (kata “hat” atau “cap” artinya topi).

Apabila kita definisikan \(\Delta p_n = p_{n+1} - p_n\) dan \(\Delta^2 p_n = p_{n+2} - 2p_{n+1} + p_n\), rumus Aitken bisa ditulis

\[\hat{p}_n = p_n - \frac{(\Delta p_n)^2}{\Delta^2 p_n}\]

sehingga teknik ini biasa disebut Aitken’s delta-squared (\(\Delta^2\)) method.

Catatan: dalam pembahasan metode Aitken/Steffensen, penulisan \(\Delta^2\) BUKAN berarti \((\Delta)^2\). Itu hanya penulisan saja.

Secara umum, apabila kita punya suku-suku suatu barisan yang berturut-turut yaitu \(p_1, p_2, p_3, \dots, p_{k-3}, p_{k-2}, p_{k-1}, p_{k}\), maka rumus Aitken bisa digunakan untuk menentukan \(\hat{p}_1, \hat{p}_2, \hat{p}_3, \dots, \hat{p}_{k-3}, \hat{p}_{k-2}\), yang semuanya merupakan aproksimasi nilai yang lebih akurat untuk hasil konvergen dari barisan tersebut (dengan asumsi kekonvergenan linier).

Perhatikan: - Kita hanya bisa berhenti sampai \(\hat{p}_{k-2}\), karena perhitungannya membutuhkan \(p_{k-2}\), \(p_{k-1}\) dan \(p_k\). - Harus ada minimal 3 suku yang diketahui, artinya \(k \ge 3\).

def Aitken(p):
    k = len(p)
    if k < 3:
        return "Maaf, dibutuhkan minimal 3 suku yang diketahui."
    
    # kalau lanjut ke sini, artinya k >= 3
    list_phat = []
    for i in range(k-2):
        Delta = p[i+1] - p[i]
        DeltaSquared = p[i+2] - 2 * p[i+1] + p[i]
        phat = p[i] - (Delta)**2 / DeltaSquared
        list_phat.append(phat)
    return list_phat
try:
    # input suatu list
    p = eval(input("Masukkan list suku-suku yang diketahui: "))
except:
    print("Maaf, terjadi error. Harap masukkan list dengan benar.")
else: # kalau tidak terjadi error 
    print("Berikut hasil metode Aitken:") 
    print(Aitken(p))
Masukkan list suku-suku yang diketahui: [2, 1.5, 1.6666666666666665, 1.6, 1.625]
Berikut hasil metode Aitken:
[1.625, 1.619047619047619, 1.6181818181818182]

Metode Steffensen: Penerapan Metode Aitken pada Metode Fixed Point

Aitken hanya menemukan rumus. Johan Frederik Steffensen menemukan bahwa, karena Metode Fixed-Point memiliki kekonvergen linier, metode Aitken bisa digunakan untuk mempercepat Metode Fixed-Point.

Secara umum, apabila kita berselang-seling antara menggunakan suatu metode dan rumus Aitken (misalnya setelah memperoleh tiga hasil aproksimasi), kita dapat mempercepat kekonvergenan (accelerating convergence), seolah-olah order of convergence menjadi lebih besar dari 1. Namun, bagaimana cara selang-selingnya?

Menurut Steffensen, rumus Aitken bisa digunakan tiap tiga iterasi fixed-point, yaitu untuk \(p_3\), \(p_6\), \(p_9\), dan seterusnya.

Kita bisa memodifikasi rumus Aitken dengan menggeser indeks \(n\), yaitu menukar \(n\) dengan \(n-3\), untuk mendapatkan rumus iterasi:

\[\hat{p} = p_{n-3} - \frac{\left(p_{n-2} - p_{n-3}\right)^2}{p_{n-1} - 2p_{n-2} + p_{n-3}}\]

dan dalam hal ini, kita juga bisa mendefinisikan \(\Delta_1 = p_{n-2} - p_{n-3}\) dan \(\Delta_2 = p_{n-1} - 2p_{n-2} + p_{n-3}\) untuk mendapatkan bentuk:

\[\hat{p} = p_{n-3} - \frac{(\Delta_1)^2}{(\Delta_2)}\]

def Steffensen(g, p0, tolerance):
    # list semua nilai p agar mudah diakses
    list_p = [p0]

    # nilai sementara
    abs_error = tolerance + 1 

    iterasi = 1 # penghitung banyaknya iterasi
    while abs_error >= tolerance:
        if iterasi % 3 == 0: # untuk kelipatan tiga, gunakan rumus Aitken
            pn_3 = list_p[iterasi - 3] # p_(n-3)
            pn_2 = list_p[iterasi - 2] # p_(n-2)
            pn_1 = list_p[iterasi - 1] # p_(n-1)
            Delta1 = pn_2 - pn_3
            Delta2 = pn_1 - 2 * pn_2 + pn_3
            pn = pn_3 - (Delta1)**2 / Delta2
        else: # selain kelipatan 3, gunakan fixed point
            pn_1 = list_p[iterasi - 1]
            pn = g(pn_1)
        
        list_p.append(pn)
        abs_error = abs( pn - pn_1 )
        iterasi += 1
    
    # return bukan hanya p, tetapi juga banyaknya iterasi
    return pn, iterasi
from numpy import sin, cos, tan, log, exp, sqrt

formula = input("Masukkan formula g(x): ")

def g(x):
    return eval(formula)

starting_point = eval(input("Masukkan titik awal iterasi: "))
tolerance = eval(input("Masukkan batas toleransi: "))

p_steffensen, i_steffensen = Steffensen(g, starting_point, tolerance)

print("Metode Steffensen")
print("Hasil: " + str(p_steffensen))
print("setelah banyaknya iterasi: " + str(i_steffensen))

print("Bandingkan banyaknya iterasi dengan Metode Fixed-Point biasa:")

fixpoint_hasil, fixpoint_tabel = FixedPoint(g, starting_point, tolerance)
print(fixpoint_tabel)
Masukkan formula g(x): 1 + 1/x
Masukkan titik awal iterasi: 2
Masukkan batas toleransi: 10**(-7)
Metode Steffensen
Hasil: 1.618033988749648
setelah banyaknya iterasi: 11
Bandingkan banyaknya iterasi dengan Metode Fixed-Point biasa:
+---------+--------------------+
| iterasi |    Aproksimasi     |
+---------+--------------------+
|    1    |        1.5         |
|    2    | 1.6666666666666665 |
|    3    |        1.6         |
|    4    |       1.625        |
|    5    | 1.6153846153846154 |
|    6    | 1.619047619047619  |
|    7    | 1.6176470588235294 |
|    8    | 1.6181818181818182 |
|    9    | 1.6179775280898876 |
|   10    | 1.6180555555555556 |
|   11    | 1.6180257510729614 |
|   12    | 1.6180371352785146 |
|   13    | 1.6180327868852458 |
|   14    | 1.618034447821682  |
|   15    | 1.618033813400125  |
|   16    | 1.6180340557275543 |
|   17    | 1.6180339631667064 |
+---------+--------------------+