diklatkerja | Metode Iteratif

Metode Interatif

Dalam matematika komputasi, metode iteratif adalah prosedur matematika yang menggunakan nilai awal untuk menghasilkan rangkaian perkiraan solusi yang meningkat terhadap suatu kelas masalah, dengan perkiraan ke-n diturunkan dari perkiraan sebelumnya. Implementasi khusus dari metode iteratif, termasuk kriteria terminasi, adalah algoritma metode iteratif. Suatu metode iteratif dikatakan konvergen jika barisan-barisan yang bersesuaian konvergen pada pendekatan pertama tertentu. Biasanya, analisis konvergensi yang ketat secara matematis dilakukan secara berulang; Namun, prosedur berulang berdasarkan heuristik juga umum dilakukan.

Metode langsung, sebaliknya, berupaya memecahkan masalah dengan menggunakan serangkaian operasi terbatas.Jika tidak ada kesalahan pembulatan, metode langsung memberikan solusi yang akurat (misalnya menyelesaikan sistem persamaan linear dengan eliminasi Gaussian). Untuk persamaan nonlinier, metode iteratif seringkali merupakan satu-satunya pilihan. Namun, metode iteratif juga sering berguna untuk permasalahan linier dengan banyak variabel (terkadang hingga jutaan), dimana metode langsung akan terlalu mahal (dan dalam beberapa kasus tidak mungkin) bahkan dengan daya komputasi terbaik yang tersedia.

Titik tetap yang menarik

Jika persamaan dapat ditulis sebagai f(x) = x dan penyelesaian x adalah titik tarik-menarik tetap dari f, maka kita dapat memulai dari titik x1 pada daerah tarik-menarik x dan himpunan xn+ 1 = f(xn) untuk n 1, dan barisan {xn} n 1 akan konvergen untuk menyelesaikan x. Di sini xn adalah pendekatan atau iterasi ke-n dari x dan xn+1 adalah iterasi berikutnya atau n+1 x. Alternatifnya, metode numerik sering kali menggunakan eksponen dalam tanda kurung. agar tidak mengalihkan perhatian dari petunjuk yang mempunyai arti lain. (Contoh: x(n+1) = f(x(n)).) Jika fungsi f dapat terdiferensiasi kontinu, syarat yang cukup untuk konvergensi adalah bahwa jari-jari spektral turunan dibatasi secara ketat oleh kesatuan di sekitar titik tetap.Jika kondisi ini terpenuhi pada suatu titik tertentu, maka harus ada lingkungan yang cukup kecil (cekungan daya tarik).

Sistem linier

Untuk sistem persamaan linier, 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 operator aslinya; dan berdasarkan kesalahan pengukuran pada hasil (sisa), buatlah “persamaan koreksi” yang proses ini diulangi. Meskipun metode ini mudah untuk diturunkan, diterapkan, dan dianalisis, konvergensi hanya dijamin untuk kelas matriks tertentu.

Definisi

Sebuah metode iteratif didefinisikan oleh

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

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

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

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

$\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

$\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 $\rho (C)$ lebih kecil daripada kesatuan, yaitu

$\rho (C)<1\,.$

Metode iteratif dasar bekerja dengan membagi matriks $A$ menjadi

$A=M-N$

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

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

Dari sini berikut bahwa matriks iterasi diberikan oleh

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

Contoh

Contoh dasar metode iteratif stasioner menggunakan pemisahan matriks $A$ seperti

$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: $M:={\frac {1}{\omega }}I\quad (\omega \neq 0)$

Metode Jacobi: $M:=D$

Metode Jacobi teredam: $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)$

Relaksasi berlebihan berurutan (SSOR): $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 terdiri dari pembuatan basis dari barisan pangkat matriks yang berurutan dikalikan dengan sisa awal (urutan Krylov). Perkiraan solusi kemudian dibuat dengan meminimalkan residu di subruang yang dibuat. Metode prototipe kelas ini adalah metode gradien konjugasi (CG), yang mengasumsikan bahwa matriks sistem A terdefinisi positif secara simetris. Untuk nilai simetris (dan mungkin tak terhingga), metode residu minimum(MINRES) dapat digunakan. Untuk matriks non-simetris, metode seperti metode residu terkecil yang digeneralisasi (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 Risalah tentang Akord dan Sinus dengan sangat presisi. Salah satu metode berulang pertama untuk menyelesaikan sistem linier muncul dalam surat dari Gauss kepada seorang siswa. Dia mengusulkan penyelesaian sistem persamaan 4 x 4 dengan berulang kali mencari suku dengan sisa terbesar.

Teori metode iteratif stasioner tertanam kuat dalam karya D.M. Muda sejak tahun 1950-an. Metode gradien konjugasi juga ditemukan pada tahun 1950-an, terlepas dari pengembangannya oleh Cornelius Lanczos, Magnus Hestenes dan Eduard Stiefel, namun sifat dan penerapannya masih sedikit dipahami pada saat itu. Baru pada tahun 1970-an diketahui bahwa metode adjoint bekerja sangat baik untuk persamaan diferensial parsial, khususnya persamaan elips.

Disadur dari: en.wikipedia.org