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 $A\mathbf {x} =\mathbf {b}$ dengan eliminasi gauss. Metode iteratif seringkali merupakan satu-satunya pilihan untuk persamaan non-linear. Namun, metode iteratif seringkali 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.^[1]

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 x₁ di cekungan daya tarik dari x, dan misalkan x_n+1 = f(x_n) untuk n ≥ 1, dan barisan {x_n}_n ≥ 1 akan konvergen ke solusi x. Di sini x_n adalah hampiran atau iterasi ke-n dari x, sementara x_n+1 adalah kelanjutan atau iterasi ke n + 1 dari x. Sebagai alternatif, superskrip dalam tanda kurung kurawal seringkali digunakan dalam metode numerik agar tidak mengganggu subskrip dengan arti lain. (Misalnya, x⁽ⁿ⁺¹⁾ = f(x⁽ⁿ⁾).) 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

\mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0

dan untuk sistem linear tertentu $A\mathbf {x} =\mathbf {b}$ dengan solusi pasti $\mathbf {x} ^{*}$ , dan kesalahan dari

\mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.

Metode iteratif disebut linear jika terdapat suatu matriks $C\in \mathbb {R} ^{n\times n}$ sedemikian sehingga : $\mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0$ dan matriks ini disebut matriks iterasi. Metode iteratif dengan matriks iterasi tertentu $C$ disebut konvergen jika berlaku

\lim _{k\rightarrow \infty }C^{k}=0\,.

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

\rho (C)<1\,.

Metode iteratif dasar bekerja dengan pemisahan matriks $A$ menjadi

A=M-N

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

M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b\,,\quad k\geq 0\,.

Dari sini iterasi matriks diberikan oleh

C=I-M^{-1}A=M^{-1}N\,.

Contoh

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

A=D+L+U\,,\quad D:={\text{diag}}((a_{ii})_{i})

dengan $D$ hanya merupakan bagian diagonal dari of $A$ , dan $L$ adalah bagian bagian segitiga bawah dari $A$ , sementara $U$ bagian segitiga atas dari $A$ .

Metode Richhardson: $M:={\frac {1}{\omega }}I\quad (\omega \neq 0)$
Metode Jacobi: $M:=D$
Metode Jacobi terbobot: $M:={\frac {1}{\omega }}D\quad (\omega \neq 0)$
Metode Gauss–Seidel: $M:=D+L$
Metode over-relaksasi (SOR): $M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)$
Metode symmetric successive overrelaxation (SSOR): $M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \not \in \{0,2\})$

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 $A$ adalah simetris pasti-positif. Untuk simetris (dan mungkin tidak terdefinisi) $A$ 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 ^{[butuh rujukan]}.

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

References

^ Amritkar, Amit; de Sturler, Eric; Świrydowicz, Katarzyna; Tafti, Danesh; Ahuja, Kapil (2015). "Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver". Journal of Computational Physics. 303: 222. arXiv:1501.03358  . Bibcode:2015JCoPh.303..222A. doi:10.1016/j.jcp.2015.09.040.

Pranala eksternal

Templat:Algoritma optimasi

[1] Amritkar, Amit; de Sturler, Eric; Świrydowicz, Katarzyna; Tafti, Danesh; Ahuja, Kapil (2015). "Recycling Krylov subspaces for CFD applications and a new hybrid recycling solver". Journal of Computational Physics. 303: 222. arXiv:1501.03358  . Bibcode:2015JCoPh.303..222A. doi:10.1016/j.jcp.2015.09.040.

[1]