Metode Iteratif

Dipublikasikan oleh Siti Nur Rahmawati

22 Agustus 2022, 13.03

www.tamboenman.xyz

Dalam matematika komputasi, metode iteratif adalah prosedur matematika yang menggunakan nilai awal untuk menghasilkan urutan peningkatan solusi perkiraan untuk kelas masalah, di mana pendekatan ke-n diturunkan dari yang sebelumnya. Implementasi spesifik dari metode iteratif, termasuk kriteria terminasi, adalah algoritma dari metode iteratif. Metode iteratif disebut konvergen jika barisan yang bersesuaian konvergen untuk aproksimasi awal yang diberikan. Sebuah analisis konvergensi matematis ketat dari metode iteratif biasanya dilakukan; namun, metode iteratif berbasis heuristik juga umum.

Sebaliknya, metode langsung berusaha memecahkan masalah dengan urutan operasi yang terbatas. Dengan tidak adanya kesalahan pembulatan, metode langsung akan memberikan solusi eksak (misalnya, menyelesaikan sistem persamaan linear A\mathbf {x} =\mathbf {b}  dengan eliminasi Gauss). Metode iteratif seringkali merupakan satu-satunya pilihan untuk persamaan nonlinier. Namun, metode iteratif seringkali berguna bahkan untuk masalah linier yang melibatkan banyak variabel (kadang-kadang dalam urutan jutaan), di mana metode langsung akan sangat mahal (dan dalam beberapa kasus tidak mungkin) bahkan dengan daya komputasi terbaik yang tersedia.

Titik tetap yang menarik

Jika suatu persamaan dapat dimasukkan ke dalam bentuk f(x) = x, dan solusi x adalah titik tetap tarik-menarik dari fungsi f, maka dapat dimulai dengan titik x1 pada cekungan tarik-menarik x, dan misalkan xn+ 1 = f(xn) untuk n 1, dan barisan {xn}n 1 akan konvergen ke solusi x. Di sini xn adalah aproksimasi atau iterasi ke-n dari x dan xn+1 adalah iterasi berikutnya atau n+1 dari x. Sebagai alternatif, superskrip dalam tanda kurung sering digunakan dalam metode numerik, agar tidak mengganggu subskrip dengan arti lain. (Misalnya, x(n+1) = f(x(n)).) Jika fungsi f terdiferensialkan secara kontinu, syarat yang cukup untuk konvergensi adalah bahwa jari-jari spektral turunan dibatasi secara ketat oleh satu di sekitar titik tetap. Jika kondisi ini berlaku pada titik tetap, maka lingkungan yang cukup kecil (cekungan tarik-menarik) harus ada.

Sistem linier

Dalam kasus sistem persamaan linear, dua kelas utama metode iteratif adalah metode iteratif stasioner, dan metode subruang Krylov yang lebih umum.

Metode iteratif stasioner

pengantar

Metode iteratif stasioner menyelesaikan sistem linier dengan operator yang mendekati yang asli; dan berdasarkan pengukuran kesalahan dalam hasil (sisa), bentuk "persamaan koreksi" yang proses ini diulang. Meskipun metode ini sederhana untuk diturunkan, diimplementasikan, dan dianalisis, konvergensi hanya dijamin untuk kelas matriks yang terbatas.

Definisi

Sebuah metode iteratif didefinisikan oleh

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

dan untuk sistem linier tertentu {\displaystyle A\mathbf {x} =\mathbf {b} } dengan solusi eksak {\displaystyle \mathbf {x} ^{*}}kesalahan oleh

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

Metode iteratif disebut linier jika terdapat matriks{\displaystyle C\in \mathbb {R} ^{n\times n}} sedemikian itu

{\displaystyle \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 berikut ini berlaku

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

Sebuah teorema penting menyatakan bahwa untuk suatu metode iteratif dan matriks iterasinya C konvergen jika dan hanya jika jari-jari spektralnya {\displaystyle \rho (C)} lebih kecil daripada kesatuan, yaitu

{\displaystyle \rho (C)<1\,.}

Metode iteratif dasar bekerja dengan membagi matriks A menjadi

{\displaystyle A=M-N}

dan di sini matriks M harus mudah dibalik. Metode iteratif sekarang didefinisikan sebagai

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

Dari sini berikut bahwa matriks iterasi diberikan oleh

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

Contoh

Contoh dasar metode iteratif stasioner menggunakan pemisahan matriks A seperti

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

di mana D hanyalah bagian diagonal dari A, dan L adalah bagian segitiga bawah dari A. Masing-masing, U adalah bagian segitiga atas dari A.

Metode Richardson: {\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}

Metode Jacobi: {\displaystyle M:=D}

Metode Jacobi teredam: {\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}

Metode Gauss–Seidel: {\displaystyle M:=D+L}

Metode over-relaksasi (SOR): {\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}

Relaksasi berlebihan berurutan (SSOR): {\displaystyle M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \not \in \{0,2\})}

Metode iteratif stasioner linier juga disebut metode relaksasi.

Metode subruang Krylov

Metode subruang Krylov bekerja dengan membentuk basis dari barisan pangkat matriks yang berurutan dikalikan dengan residual awal (urutan Krylov). Pendekatan ke solusi kemudian dibentuk dengan meminimalkan residu atas subruang yang terbentuk. Metode prototipikal dalam kelas ini adalah metode gradien konjugasi (CG) yang mengasumsikan bahwa matriks sistem {\displaystyle A}A adalah pasti-positif simetris. Untuk simetris (dan mungkin tidak terbatas) {\displaystyle A}Satu bekerja dengan metode residual minimal (MINRES). Dalam kasus matriks non-simetris, metode seperti metode residual minimal umum (GMRES) dan metode gradien bikonjugasi (BiCG) telah diturunkan.

Konvergensi metode subruang Krylov

Karena metode ini membentuk basis, terbukti bahwa metode tersebut konvergen dalam N iterasi, di mana N adalah ukuran sistem. Namun, dengan adanya kesalahan pembulatan, pernyataan ini tidak berlaku; apalagi, dalam praktiknya N bisa sangat besar, dan proses iteratif mencapai akurasi yang cukup jauh lebih awal. Analisis metode ini sulit, tergantung pada fungsi spektrum operator yang rumit.

Prakondisi

Operator aproksimasi yang muncul dalam metode iteratif stasioner juga dapat digabungkan dalam metode subruang Krylov seperti GMRES (sebagai alternatif, metode Krylov yang telah diprakondisikan dapat dianggap sebagai percepatan metode iteratif stasioner), di mana mereka menjadi transformasi dari operator asli ke kondisi yang mungkin lebih baik. satu. Konstruksi preconditioners adalah area penelitian yang besar.

Sejarah

Jamshīd al-Kāsh menggunakan metode iteratif untuk menghitung sinus 1° dan dalam The Treatise of Chord and Sine dengan presisi tinggi. Metode iteratif awal untuk memecahkan sistem linier muncul dalam surat Gauss kepada seorang siswanya. Dia mengusulkan pemecahan sistem persamaan 4-kali-4 dengan berulang kali memecahkan komponen di mana sisa adalah yang terbesar [rujukan?].

Teori metode iteratif stasioner didirikan dengan kokoh dengan karya D.M. Muda mulai tahun 1950-an. Metode gradien konjugasi juga ditemukan pada 1950-an, dengan pengembangan independen oleh Cornelius Lanczos, Magnus Hestenes dan Eduard Stiefel, tetapi sifat dan penerapannya disalahpahami pada saat itu. Baru pada tahun 1970-an disadari bahwa metode berbasis konjugasi bekerja sangat baik untuk persamaan diferensial parsial, terutama tipe eliptik.

 

Sumber Artikel: en.wikipedia.org