Metode Iterasi (Komputasi Teknik)

Banyak persamaan matematika yang dapat diselesaikan secara exact tetapi jauh lebih banyak lagi yang hanya dapat diselesaikan dengan metode numeric.

Istilah `` iteratif'' metode mengacu pada berbagai teknik yang menggunakan aproksimasi untuk mendapatkan solusi yang lebih akurat untuk sistem linier di setiap langkah. 

Untuk mencari solusi dari persamaan f(x) = 0 digunakan sejumlah proses trial dan error yang sering juga disebut metode iterasi.

Solusi dari persamaan di atas disebut akar persamaan f(x)=0

Ada beberapa tipe metode iterasi yaitu:

1. Metode Bisection

Metode bisection sangat sederhana dan dapat diandalkan. Metode ini sering digunakan untuk mendapatkan pendekatan kasar solusi yang kemudian digunakan sebagai titik awal untuk metode yang lebih cepat konvergen. Metode dijamin konvergen ke akar dari fungsi f jika fungsi f kontinu pada interval (a,b). Fungsi f(a) dan f(b) memiliki tanda yang berlawanan. Absolte error dibelah dua pada setiap langkah iterasi sehingga metode akan konvergen secara linear yang relatif lambat. Jika p1 = (a + b) / 2 adalah titik tengah dari interval awal, dan pn adalah titik tengah interval pada langkah ke-n, maka perbedaan antara pn dan solusi p dibatasi.

Algoritmanya sebagai berikut

INPUT: Function f, endpoint values a, b, tolerance TOL, maximum iterations NMAX

CONDITIONS: a < b, either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0

OUTPUT: value which differs from a root of f(x)=0 by less than TOL

N ← 1

While N ≤ NMAX { limit iterations to prevent infinite loop

  c ← (a + b)/2 new midpoint

  If (f(c) = 0 or (b – a)/2 < TOL then { solution found

    Output(c)

    Stop

  }

  N ← N + 1 increment step counter

  If sign(f(c)) = sign(f(a)) then a ← c else b ← c new interval

}

Output("Method failed.") max number of steps exceede

2. Metode False Position

Metode bisection menjamin konvergensi pada akarnya tetapi relative lambat dan sulit untuk diaplikasikan untuk system persamaan non linear dua atau lebih. Metode false position merupakan salah satu cara untuk mengatasi hal ini. Kita mulai dengan melokasikan interval mula-mula (x₁,x₂), dan diasumsikan fungsi berubah tanda hanya sekali di dalam interval ini. Sekarang kita mendapatkan x₃ di dalam interval ini, yang didapat dari persimpangan antara sumbu x dan garis lurus melalui (x₁,f(x₁)) dan (x₂,f(x₂)).

Sekarang kita memilih interval yang baru dari dua pilihan (x1,x3) dan (x3,x2) tergantung di interval mana fungsi berubah tanda.

Metode false position berbeda dari metode bisection hanya di dalam pilihan pembagian interval pada masing-masing iterasi. Metode ini lebih cepat konvergen ke akar karena merupakan algoritma yang menggunakan bobot yang sesuai dari ujung mula titik x1 dan x2 dengan menggunakan informasi tentang fungsi, atau data dari masalah. Dengan kata lain, mencari x3 adalah prosedur statis dalam kasus metode bisection karena untuk x1 dan x2 yang diberikan, ini memberikan x3 yang identik, tidak peduli apa fungsi kita ingin memecahkan. Di sisi lain, metode false position menggunakan informasi tentang fungsi untuk mendapatkan di x3.

3. Metode Newton Raphson

Metode Newton-Raphson adalah suatu metode iterasi untuk menyelesaikan persamaan f(x)=0, di mana f diasumsikan mempunyai turunan kontinu f’.

Metode ini secara umum digunakan karena sederhana dan cepat.

Idenya adalah memperkirakan grafik f dengan tangent yang cocok.

Menggunakan nilai x₀ didapat dari grafik f, x₁ adalah titik persimpangan dari sumbu x dan tangent kurva f pada x₀. Maka

Langkah kedua kita menghitung x₂ = x₁ – f(x₁)/f’(x₁), langkah ketiga diulang lagi x₃ dari x₂ menggunakan rumus yang sama. 

Algoritmanya adalah

Jika terjadi f’(x_n) = 0 untuk beberapa n (lihat algoritma baris 2) ,lalu mulai lagi dengan nilai tebakan baru x₀.

Pada baris 4 adalah criteria terminasi. Jika urutan x_n konvergen dan memenuhi criteria, kita mendapatkan hasil yang akurat.

4. Metode Secant

    Metode ini menggunakan garis perkiraan berdasarkan interpolasi. Kita asumsikan mempunyai perkiraan dua akar α, katakanlah x₀ dan x₁. Kemudian kita menghasilkan sebuah fungsi linear

Garis ini sering disebut garis secant.  Persamaannya adalah

i

Ini linear dalam x; dan dengan evaluasi arah, ini memenuhi kondisi interpolasi. Kita sekarang menyelesaikan persamaan q(x)=0 , ditandai dengan akar x₂. 

Kita sekarang dapat mengulangi proses tersebut. Gunakan x₁ dan x₂ untuk membuat garis secant yang lainnya

Hal mendasar perbandingan dari beberapa metode iterasi di atas adalah:

1. Laju konvergensi

2. Jumlah usaha komputer setiap iterasi

3. Sensitivitas metode terhadap nilai awal dan nilai tengah

Metode Bisection : 

- urutan konvergensi : satu bit per iterasi

- Evaluasi fungsi per iterasi : 1

- Kehandalan konvergensi : dijamin konvergen

Metode False Position: 

- urutan konvergensi : satu bit per iterasi

- Evaluasi fungsi per iterasi : 1

- Kehandalan konvergensi : dijamin konvergen

Metode Newton Raphson: 

- urutan konvergensi : dua bit per iterasi

- Evaluasi fungsi per iterasi : 2

- Kehandalan konvergensi : ssensitif terhadap nilai awal.Akan konvergen dengan cepat jika dekat akar

Metode Secant: 

- urutan konvergensi : 1.62 bit per iterasi

- Evaluasi fungsi per iterasi : 1

- Kehandalan konvergensi : tidak dijamin konvergen jika tidak dekat dengan akar. Metode ekonomis