# Bab 1. Mencari Akar Persamaan
- https://github.com/cfgnunes/numerical-methods-python/blob/main/solutions.py
- https://open.umn.edu/opentextbooks/textbooks/925
- https://iq.opengenus.org/regula-falsi-method/#:~:text=Like%20Bisection%20method%2C%20Regula%20Falsi,that%20can%20identify%20multiple%20roots.

## 1.0 Pengantar
Salah satu persoalan matematika yang umum adalah persoalan mencari akar dari suatu persamaan, yaitu mencari nilai $x$ yang memenuhi

$$
f(x) = 0 \tag{1.1} \label{Pers1.1}
$$

Secara grafik, solusi atau akar dari $f(x) = 0$ adalah titik potong dari $f(x)$ dan sumbu-$x$. Gambar 1.1 berikut mengilustrasikan solusi atau akar dari $f(x) = 0$.

// tambah gambar.

Tergantung dari sifat dari grafik $f(x)$, Persamaan $(\ref{Pers1.1})$ dapat mempunyai solusi yang unik, solusi lebih dari satu, ataupun tidak mempunyai solusi.

Akar dari persamaan terkadang dapat dicari secara analitik. Sebagai contoh, persamaan $e^{3x} - 2 = 0$ dapat diselesaikan secara analitik untuk mendapatkan sebuah solusi unik $x = {1 \over 3} \ln 2$. Namun, dalam banyak kasus, akar(-akar) persamaan tidak mungkin dicari secara analitik dan harus dicari secara numerik. Persamaan $2-x+\cos x = 0$ adalah salah satu contoh. Gambar 1.1 berikut adalah gambar dari persamaan ini dan dapat dilihat persamaan ini hanya mempunyai satu solusi, yang dapat diaproksimasi dalam akurasi yang diinginkan dengan menggunakan metode numerik.

## 1.1 Solusi Numerik Pencarian Akar Persamaan

Metode numerik pencarian akar persamaan dapat dikategorikan menjadi dua: metode pengurungan dan metode terbuka.


### 1.1.1 Metode Pengurungan
Metode pengurungan (*bracketing method*) didasarkan pada Teorema Nilai Antara (Intermediate Value Theorem) yang menyatakan bahwa diberikan suatu fungsi $f(x)$ yang kontinyu pada suatu interval $[a, b]$, jika $f(a)f(b) < 0$, maka terdapat suatu nilai $c$ dalam interval $[a, b]$ dimana $f(c) = 0$.

Metode pengurungan secara garis besar bekerja seperti berikut: mulai dengan suatu interval $[a, b]$ dimana $f(a)f(b) < 0$, lalu perkecil interval secara bertahap sampai dengan akurasi yang diinginkan didapatkan. Bagaimana interval ini diperkecil bergantung pada metode spesifik yang digunakan. //Metode pengurugan selalu berhasil menghasilkan nilai estimasi dari akar persamaan, oleh karena ini metode pengurungan disebut sebagai metode yang konvergen.//

Terdapat dua metode pengurungan yang umum yaitu:
- Metode Biseksi
- Metode Regula Falsi

### 1.1.2 Metode Terbuka

## 1.2 Metode Biseksi
Metode biseksi adalah metode pengurungan paling sederhana untuk mencari akar persamaan $f(x) = 0$. Secara umum, jika $f(x)$ kontinyu pada interval $[a, b]$ dan $f(x)$ dan $f(b)$ mempunyai tanda berbeda, yaitu

$$
f(a)f(c)<0
$$

maka terdapat setidaknya satu akar diantara $a$ dan $b$.

Metode biseksi secara garis besar bekerja seperti berikut:
* **Langkah 1.** Pilih nilai $a$ dan $b$ dimana interval $[a, b]$ sedemikian sehingga nilai fungsi $f(x)$ berubah tanda sepanjang interval. Ini dapat dilakukan dengan memastikan $f(a)f(b)<0$.
* **Langkah 2.** Cari estimasi dari akar dengan mencari titik tengah interval $c$ dari interval $[a, b]$, yang dapat dihitung dengan
$$
c = \frac {a + b} 2
$$
* **Langkah 3.** Lakukan evaluasi-evaluasi berikut untuk menentukan subinterval dimana akar berada:
* Jika $f(a)f(c)<0$, maka akar berada di subinterval bawah yaitu $[a, c]$. Ulangi Langkah 2 menggunakan subinterval $[a, c]$.
* Jika $f(c)f(b)<0$, maka akar berada di subinterval atas yaitu $[c, b]$. Ulangi Langkah 2 menggunakan subinterval $[c, b]$.
* Jika $f(c) = 0$, maka $c$ adalah akar persamaan; sudahi kalkulasi.

---
**Contoh 1.1** (Sauer Example 1.1) Cari akar fungsi $f(x) = x^3 + x - 1$ menggunakan metode biseksi pada interval $[0, 1]$.

**Solusi.**
$f(0) = -1$ dan $f(1) = 1$, maka akar berada di interval $[0, 1]$.

*Iterasi 1:*
- Titik tengan $[0, 1]$ adalah $c_1 = \frac {0+1} 2 = \frac 1 2$. Nilai $f$ pada $c$, $f(\frac 1 2) = \frac 1 8 + \frac 1 2 - 1 = - \frac 4 8 < 0$. Ini berarti akar berada di $[0, \frac 1 2]$.

---

### Kriteria Penghentian Iterasi

Pada Contoh x.x.x kita menghentikan proses setelah melakukan iterasi sebanyak x kali. Karena pada setiap iterasi kita membelah interval menjadi interval yang lebih kecil, maka kita akan mendapatkan estimasi akar yang semakin mendekati nilai sebenarnya jika kita terus melanjutkan iterasi. Ini berarti semakin banyak iterasi akan semakin kecil error estimasi.

Kita dapat menghentikan proses iterasi dengan menentukan suatu toleransi error.

## 1.3 Metode Regula Falsi

Metode regula falsi yang berarti posisi palsu, adalah metode pengurungan untuk mencari akar persamaan yang lebih efisien dibandingkan metode biseksi.

Kerkurangan dari metode biseksi adalah, dalam membagi interval dari $a$ ke $b$ menjadi dua subinterval yang sama panjang, tidak mempertimbangkan besaran nilai $f(x)$ pada interval tersebut. Sebagai contoh, jika nilai $f(a)$ lebih dekat ke nol dibandingkan nilai $f(b)$, ini berarti kemungkinan besar akar lebih dekat ke $a$ dibandingkan ke $b$. Metode

Metode regula falsi,

- **Regula Falsi dapat lambat sekali konvergen**

## 1.4 Metode Titik Tetap

Titik tetap (*fixed-point*) dari sebuah fungsi $g(x)$ adalah nilai $p$ dimana $g(p) = p$. Metode pencarian solusi dari persoalan titik tetap dapat digunakan untuk mencari solusi dari persoalan pencarian akar.

Misalkan kita ingin menyelesaikan persoalan pencarian akar, $f(x) = 0$. Kita dapat mendefinisikan fungsi $g$ dengan sebuah titik tetap pada $p$ dengan berbagai cara, sebagai contoh, dengan

$$
g(x) = x - f(x)
$$

atau dengan

$$
g(x) = x + 3f(x)
$$

Secara umum, fungsi $g$ dapat didefinisikan dengan bentuk

$$
g(x) = x + \theta f(x)
$$

Titik tetap $p$ ini adalah akar dari persamaan $f(x)$.

Secara grafik, titik tetap dari suatu fungsi $g(x)$ adalah titik potong dari grafik kurva $y = g(x)$ dan $y = x$.

**Contoh x.x.x** Tentukan titik-titik tetap dari fungsi $g(x) = x^2 - 2$.
**Solusi** Titik tetap $p$ dari fungsi $f$ mempunyai sifat

Metode titik tetap (fixed point method) adalah salah satu metode terbuka untuk mencari akar dari $f(x) = 0$.

Ide dasar dari metode ini adalah menulis ulang $f(x) = 0$ sebagai $x = g(x)$ untuk sebuah $g(x)$ yang pantas. Fungsi $g(x)$ dinamakan dengan fungsi iterasi. Titk potong dari $y = g(x)$ dan $y = x$ disebut sebagai sebuah titik tetap dari $g(x)$.

## Iterasi Titik Tetap

Pada banyak kasus, titik point tidak dapat ditentukan secara ekplisit. Sebagai contoh, titik tetap pada fungsi $g(x) = 3^{-x}$ tidak dapat ditentukan secara eksplisit. Namun, kita dapat mencari aproksimasi titik tetap sampai dengan derajat keakurasian yang diinginkan.

Untuk mengaproksimasi titik ttetap dari sebuah fungsi $g$, kita memilih sebuah aproksimasi awal $p_0$ dan

Prosedur dari iterasi titik tetap dimulai dengan tebakan awal $p_0$ dekat titik tetap. Titik berikutnya $p_1$ ditentukan dengan $p_1 = g(p_0)$, dilanjutkan dengan $p_2 = g(p_1)$, dan seterusnya. Gambar x.x mengilustrasikan proses iterasi ini.


def fixed_point(g, pzero, tol, N):
    '''
    Parameters:
    g = fungsi g yang digunakan untuk merepresentasikan fungsi f pada persoalan fixed point
    pzero = tebakan awal nilai titik tetap
    tol = toleransi error
    N = maksimum jumlah iterasi
    
    Return:
    
    '''
    
    n = 1
    while n < N:
        pone = g(pzero)
        
        if np.abs(pone - pzero) < tol:
            print('p =', pone, ' dengan jumlah iterasi n =', n)
            return
        
        pzero = pone
        n += 1
    print('Tidak konvergen. Estimasi terakhir adalah p =', pzero)
    

### Pemilihan Fungsi Iterasi
Seperti yang telah disebutkan sebelumnya, biasanya terdapat lebih dari satu cara untuk menulis ulang persamaan yang diberikan $f(x) = 0$ sebagai $x = g(x)$. Fungsi iterasi $g(x)$ harus dipilih dengan tepat sehingga iterasi konvergen ke titik tetap. Dalam beberapa kasus, lebih dari satu bentuk yang mungkin dapat digunakan secara sukses. Terkadang, tidak ada satupun bentuk yang cocok, yang berarti akar tidak dapat ditemukan dengan metode titik tetap. Ketika terdapat akar lebih dari satu, satu bentuk mungkin digunakan untuk mencari satu akar dan bentuk lain digunakan untuk mencari akar yang lain. Teorema x.x

**Teorema 1.1 (Titik Tengah)**
Misal $g \in C[a, b]$ sedemikian sehingga $g(x) \in [a, b]$ untuk semua $x \in [a, b]$. Misalkan, $g'$ ada pada $(a, b)$

**Teorema 1.1 (Konvergensi dari Iterasi Titik Tetap)**
Misal $r \in I$ adalah titik tetap dari $g(x)$. Anggap $g(x)$ mempunyai derivatif kontinyu dalam interval $I$ dan $|g'(x)| \leq K \leq 1$ untuk semua $x \in I$. Maka, untuk titik awal $x_1 \in I$, iterasi titik-tetap pada Persamaan (x.x) menghasilkan barisan $\{x_n\}$ yang konvergen ke $r$. Lebih lanjut, jika $e_1 = x_1 - r$ dan $e_n = x_n - r$ menotasikan error awal dan error pada iterasi ke-$n$, kita mempunyai

$$
|e_n| \leq K^n | e_1 |
$$

**Bukti**
Misal

### Konvergensi


Perhatikan Gambar di atas. Pola iterasi titik tetap pada (a) dan (c) disebut monoton, karena barisan estimasi titik tetap $x_n$ bergerak ke satu arah. Sedangkan pola iterasi titik tetap pada (b) dan (d) disebut beroskilasi, karena barisan estiasi titik tetap bergerak ke arah yang berbeda pada setiap iterasinya. Lebih lanjut, pada (a) dan (d), nilai mutlak dari slope kurva $g$ pada sekitar titik tetap adalah kurang dari satu, yaitu, $|g'(x)| \leq 1$.

///Dalam kondisi seperti ini, jarak antara estimasi titik tetap pada setiap iterasinya mengecil, yaitu, $|x_{n+1} - x_n| \leq |x_n - x_{n-1}|$, sehingga barisan nilai iterasi ${x_n}$ konvergen//. <- Fallacy.

Sebalikan, pada (b) dan (c), nilai mutlak slope kurva $g$ pada seiktar titik tetap bernilai $|g'(x)| \geq 1$ sehingga menyebabkan jarak antara estimasi titik tetap setiap iterasinya menjadi membesar. Pada kondisi ini, iterasi disebut divergen.

Dari pengamatan kurva di atas kita dapat simpulkan, iterasi titik tetap konvergen jika dalam interval iterasi tersebut berjalan, $|g'(x)| \leq 1$. Dengan kata lain, konvergen terjadi jika bwesaran slope dari $g(x)$ kurang dari slope garis $f(x) = x$. Hasil observasi ini dapat dibuktikan secara teori.

Ingat pada persamaan iterasi titik tetap adalah

$$
x_{i+1} = g(x_i)
$$

Misalkan, solusi sebenarnya adalah
$$
x_r = g(x_r)
$$

Selisihkan kedua persamaan di atas menghasilkan

$$
x_r - x_{i+1} = g(x_r) - g(x_i)
$$

Teorema Nilai-Rataan (mean value theorem) menyatakan bahwa sebuah fungsi $g(x)$ dan derivatif perrtramnaya kontinyu dalam sebuah interval $a \leq x \leq b$, maka terdapat setidaknya sebuah nilai $x = \xi$ dalam interval sedemikian sehingga

$$
g'(\xi) = \frac {g(b) - g(a)} {b - a} \tag{1.x} \label{1.x}
$$

Ruas kanan dari persamaan adalah slope dari sebuah grais yang menghubungkan $g(a)$ dan $g(b)$. Jadi, teorema nilai-rataan menyatakan bahwa terdapat setidaknya satu titik diantara $a$ dan $b$ yang mempunyai slope, yang mempunyai besaran $g'(\xi)$, yang paralel dengan garis yang menghubungkan $g(a)$ dan $g(b)$.

Jika kita tetapkan $a = x_i$ dan $b = x_r$, ruas kanan Persamaan $(\ref{1.x})$ dapat diekpsresikan sebagai

$g(x_r) - g(x_i) = (x_r - x_i)g'(\xi)$

**Kapan metode fixed point tidak konvergen?**


**Bagaimana cara memastikan metode fixed point konvergen?**

## 1.5 Metode Newton-Raphson
Metode Newton-Raphson adalah metode terbuka untuk menyelesaikan $f(x) = 0$ yang paling umum digunakan. Syarat dari metode ini adalah $f'(x)$ adalah kontinyu.

Gambar berikut mengilustrasikan metode Newton-Raphson.

Metode Newton-Raphson bekerja seperti berikut: mulai dengan titik awal $x_1$ dan cari titik $(x_1, f(x_1))$ pada kurva. Gambar garis singgung kurva pada titik tersebut, dan cari titik potong pada sumbu-$x$ dari garis singgung tersebut dan tetapkan sebagai nilai $x_2$. Persamaan yang digunakan untuk mencari garis singgung adalah

$$
y - f(x_1) = f'(x_1)(x - x_1)
$$

Sehingga, titik potong garis singgung pada sumbu-$x$ didapatkan dengan menetapkan $y = 0$ dan menyeleasaikan $x$:

$$
x_2 = x_1 - {f(x_1) \over f'(x_1)}
$$

Setelah $x_2$ didapatkan, temukan titik $(x_2, f(x_2))$, cari garis singgung kurva yang melalui titik tersebut, dan tetapkan $x_3$ sebagai titik potong sumbu-$x$ dari garis singgung. Sehingga $x_3$ dapat dicari dengan

$$
x_3 = x_2 - {f(x_2) \over f'(x_2)}
$$

Lanjutkan proses ini sampai barisan $\{x_n\}$ konvergen ke akar persamaan. Secara umum, $x_n$ dan $x_{n+1}$ terkait satu sama lain melalui

$$
x_{n+1} = x_n - {f(x_n) \over f'(x_n)}, \ n = 1, 2, 3, ...
$$

Kondisi penghentian iterasi untuk metode Newton-Raphson sama seperti pada metode-metode sebelumnya. Kita memilih sebuah toleransi error $\varepsilon > 0$ dan menghentikan iterasi ketika nilai jarak antara $x_{n+1}$ dan $x_n$ kurang dari toleransi error $\varepsilon$ yang diiginkan, yaitu dengan menetapkan kondisi iterasi dengan

$$
|x_{n+1} - x_n| < \epsilon
$$

dimana $\epsilon$ adalah toleransi error.

Seperti pada metode-metode terbuka lainnya, metode Newton-Raphson tidak menjamin kekonvergenan. Ini berarti, solusi bisa tidak dapat ditemukan dan iterasi dapat berjalan terus-menerus karena kondisi penghentian di atas tidak akan terpenuhi. Oleh karena itu, kita harus menetapkan maksimum banyaknya iterasi.

Fungsi `newton` berikut adalah implementasi metode Newton-Raphson.

def newton(f, x1, tol, N):
    

Fungsi `newton` di atas memerlukan input-input berikut:
...

### Konvergensi pada Metode Newton

Pertanyaan

### Sejumlah Catatan untuk Metode Newton

- Ketika metode Newton-Raphson bekerja,

## 1.6 Metode Secant
Satu kekurangan dari metode Newton-Raphson adalah kita perlu memberikan bentuk derivatif dari $f$ secara ekspilisit. Sering kali, $f'(x)$ sulit untuk diekspresikan secara eksplisit. Metode secant mengganti garis singgung dengan sebuah garis yang melewati dua titik. Garis ini disebut dengan garis secant. Perpotongan garis secant pada sumbu-$x$ menjadi


Secant line: $y = \frac {f(x_i) - f(x_{i-1})} {x_i - x_{i-1}}$

$$
x_{i+1} = x_i - \frac {f(x_i)(x_{i+1} - x_i)} {f(x_{i-1}) - f(x_i)} \tag{1.3}\label{Per1.3}
$$

Mulai dengan dua aproksimasi awal $x_0$ dan $x_1$.

masalah potensial dalam pengimplementasian metode Newton-Raphson adalah evaluasi nilai dari derivatif. Meskipun hal ini tidaklah menjadi masalah untuk polinomial, tetapi

Untuk kasus dimana derivatif fungsi tidak dapat ditemukan secara anlitik, derivatif dapat diaproksimasi dengan metode backward finite divided difference seperti pada persamaan

$$
f'(x_i) \approx \frac
$$


---
**Contoh**
Gunakakan metode secant untuk mengestimasi akar dari $f(x) = e^{-x} - x$. Mulai dengan estimasi awal dari $x_0 = 0$ dan $x_1 = 1.0$.

**Solusi**

Iterasi 1:
$\qquad x_0 = 0 \qquad \qquad f(x_0) = e^{0} - 0 = 1.00000$

$\qquad x_1 = 1.0 \qquad \qquad f(x_1) = e^{1.0} - 1.0 = -0.63212$

$\qquad x_2 = 1 - \frac {-0.63212(0 - 1)} {1 - (-0.63212)}$

---