Metode iteratif

Dalam Matematika komputasi, metode iteratif (bahasa Inggris: iterative method) adalah prosedur matematis yang menggunakan nilai awal untuk menghasilkan rangkaian perbaikan hampiran solusi untuk suatu kelas permasalahan, dengan hampiran ke-n diturunkan dari hampiran sebelumnya.

Implementasi spesifik dengan kriteria penghentian untuk suatu metode iteratif, seperti penurunan gradien, hill climbing, metode Newton, atau metode quasi-Newton, seperti BFGS, merupakan sebuah algoritma dari metode iteratif tersebut. Metode iteratif dikatakan konvergen, jika  barisan yang bersesuaian konvergen untuk hampiran awal yang diberikan. Analisis konvergensi matematis yang ketat dari metode iteratif biasanya dilakukan, tetapi metode iteratif berbasis heuristik juga umum dilakukan.

Sebaliknya, metode langsung (direct method) berusaha untuk memecahkan masalah dengan serangkaian operasi yang terbatas. Tanpa adanya kesalahan pembulatan, metode langsung akan menghasilkan solusi yang tepat, contohnya dalam menyelesaikan sistem persamaan linier  dengan eliminasi gauss. Metode iteratif sering kali merupakan satu-satunya pilihan untuk persamaan non-linear. Namun, metode iteratif sering kali berguna untuk masalah linear yang melibatkan banyak variabel (terkadang hingga jutaan variabel), yang metode langsung akan sangat mahal (dan dalam sebagian kasus mustahil). Bahkan dengan menggunakan daya komputasi terbaik yang ada.

Titik tetap atraktif
Jika suatu persamaan dapat dinyatakan dalam bentuk f(x) = x dan suatu solusi x adalah titik tetap atraktif dari fungsi f, maka dapat dimulai dengan titik x1 di cekungan daya tarik dari x, dan misalkan xn+1 = f(xn) untuk n ≥ 1, dan barisan {xn}n ≥ 1 akan konvergen ke solusi x. Di sini xn adalah hampiran atau iterasi ke-n  dari x, sementara xn+1 adalah kelanjutan atau iterasi ke n + 1 dari x. Sebagai alternatif, superskrip dalam tanda kurung kurawal sering kali digunakan dalam metode numerik agar tidak mengganggu subskrip dengan arti lain. (Misalnya, x(n+1) = f(x(n)).) IJika fungsi f is terdiferensialkan secara kontinu, syarat yang cukup untuk dapat konvergen adalah bahwa jari-jari spektral turunannya  dibatasi secara ketat di dalam ketetanggaan titik tetap. Jika kondisi ini berlaku pada titik tetap, maka harus ada ketetanggaan yang cukup kecil (cekungan daya tarik; basin of attraction).

Sistem linier
Dalam kasus sistem persamaan linear, dua kelas utama dari metode iteratif adalah
metode iteratif stasioner, dan metode Subruang Krylov yang lebih umum.

Metode iteratif stasioner
 Pengenalan 
Metode iteratif stasioner menyelesaikan sistem linear dengan menggunakan operator yang mendekati yang asli; dan berdasarkan pengukuran kesalahan dalam hasil (sisa), membentuk pengulangan "persamaan koreksi. Meskipun metode-metode ini sederhana untuk diturunkan, diimplementasikan, dan dianalisis, konvergensi hnya dijamin untuk kelas matriks yang terbatas.

Definisi
Sebuah metode iteratif didefinisikan oleh

dan untuk sistem linear tertentu  dengan solusi pasti , dan kesalahan dari

Metode iteratif disebut linear jika terdapat suatu matriks  sedemikian sehingga :
dan matriks ini disebut matriks iterasi.
Metode iteratif dengan matriks iterasi tertentu  disebut konvergen jika berlaku

Sebuah teorema penting menyatakan bahwa untuk suatu metode iteratif dan matriks iterasi -nya konvergen; jika dan hanya jika jari-jari spektralnya  lebih kecil dari kesatuan, yakni

Metode iteratif dasar bekerja dengan  pemisahan matriks  menjadi

dan di sini, matriks  dapat dengan mudah diinverskan. Metode iteratifnya sekarang didefinisikan sebagai

Dari sini iterasi matriks diberikan oleh

Contoh
Contoh dasar dari metode iteratif stasioner menggunakan pemisahan matriks  sedemikian sehingga

dengan  hanya merupakan bagian diagonal dari of , dan  adalah bagian bagian segitiga bawah dari , sementara  bagian segitiga atas dari .
 Metode Richhardson: 
 Metode Jacobi: 
 Metode Jacobi terbobot: 
 Metode Gauss–Seidel: 
 Metode over-relaksasi (SOR): 
 Metode symmetric successive overrelaxation (SSOR): 
Metode iteratif linear stasioner juga disebut metode relaksasi.

Metode subruang Krylov
Metode subruang Krylov bekerja dengan membentuk sebuah basis dari barisan pangkat matriks yang berurutan dikalikan dengan residual awal (Barisan Krylov). 
Hampiran solusi kemudian dibentuk dengan menimalkan resiud atau subruang yang terbentuk. Metode prototipikal dalam kelas ini adalah Metode gradien konjugasi (CG) yang mengasumsikan bahwa matriks sistem  adalah simetris pasti-positif.
Untuk simetris (dan mungkin tidak terdefinisi)  mungkin bekerja metode residual minimal (MINRES).
Dalam kasus matriks non-simetris, metode seperti metode residu minimal tergeneralisasi (GMRES) dan metode gradien bikonjugasi (BiCG) sudah banyak digunakan.

Konvergensi metode subruang Krylov
Karena metode ini membentuk suatu basis, maka terbukti bahwa metode ini konvergen dalam N iterasi, dengan N adalah ukuran sistem. Namun, dengan adanya kesalahan pembulatan, pernyataan ini tidak berlaku. Selain itu, dalam praktiknya N bisa sangat besar, dan proses iterasi mencapai akurasi yang cukup jauh sebelumnya. Analisis terhadap metode ini sulit, tergantung pada fungsi yang kompleks dari operator.

 Prekondisi 
Operator hampiran yang muncul dalam metode iteratif stasioner juga dapat dimasukkan dalam metode subruang Krylov seperti GMRES (sebagai alternatif, prekondisi Metode Krylov dapat dianggap sebagai percepatan metode iteratif stasioner), yang mana metode ini menjadi transformasi dari operator asli ke operator yang mungkin lebih baik. Konstruksi prekondisi adalah area penelitian yang besar.

 Sejarah
Jamshīd al-Kāshī menggunakan metode iteratif untuk menghitung sinus 1° dan  dalam Risalah korda dan sinus dengan presisi tinggi. 
Metode iteratif awal untuk menyelesaikan sistem linear muncul dalam surat Gauss kepada seorang muridnya.  Ia mengusulkan untuk menyelesaikan sistem persamaan 4 x 4 dengan menyelesaikan secara berulang-ulang komponen yang memiliki sisa terbesar .

Teori metode iteratif stasioner telah terbentuk kokoh dengan penelitian D.M. Young yang dimulai pada tahun 1950-an. Metode gradien konjugasi juga ditemukan pada tahun 1950-an, dengan pengembangan independen oleh Cornelius Lanczos, Magnus Hestenes dan Eduard Stiefel, tetapi sifat dan penerapannya disalahartikan pada saat itu. Hanya pada tahun 1970-an barulah disadari bahwa metode berbasis konjugasi bekerja dengan sangat baik untuk persamaan diferensial parsial, terutama tipe eliptik.

 Lihat juga 

 Ekspresi bentuk tertutup
 Penyempurnaan iteratif
 Metode Kaczmarz
 Kuadrat terkecil non-linear
 Analisis numerik
 Algoritma pencarian akar

Referensi

 Pranala luar 
Templat untuk Solusi Sistem Linear
 Y. Saad: Iterative Methods for Sparse Linear Systems,  1st edition, PWS 1996


Kategori:Analsis numerik