Aljabar linear numerik

Aljabar linear numerik adolah pengkajian algoritme untuak malakukan proses komputasi aljabar linear, tautamo operasi matriks, pado komputer. Pangkajian iko acok manjadi bagian nan paliang mandasar di dalam persoalan teknik jo ilmu komputasi, misalnyo pangolahan citra dan sinyal, komputasi kauangan, simulasi ilmu bahan, biologi struktural, data mining, jo bioinformatika, dinamika fluida, sarato banyak bidang lainnyo. Ado babarapo parangkek lunak nan bagantuang bana pado pangambangan, analisis, jo panerapan algoritme state-of-the-art untuak manyalasaian babagai persoalan aljabar linear numerik, pado bagian nan gadang karano peranan matriks di dalam metode beda hingga jo metode unsur hingga. Masalah nan ado di dalam aljabar linear numerik di antaronyo komputasi contohnyo sabagai berikut: panguraian LU, panguraian QR, penguraian nilai singular, nilai eigen.

Sajarah

Aljabar linier numerik dikambangkan dek para pelopor komputer saparti John von Neumann, Alan Turing, James H. Wilkinson, Alston Scott Householder, George Forsythe, jo Heinz Rutishauser, dalam rangka untuak manerapkan komputer paliang awal untuak masalah dalam matematika nan bakalanjuikan, saparti masalah balistik jo solusi untuak sistem persamaan diferensial parsial. Upaya serius patamo untuak maminimalkan kasalahan komputer dalam panerapan algoritme pado data nan nyato adolah karya John von Neumann jo Herman Goldstine pado taun 1947. Bidang iko alah bakambang karano teknologi nan samakin mamungkinkan para paneliti untuak mamacahan masalah kompleks pado matriks presisi tinggi nan gadang bana, jo babarapo algoritme numerik menjadi terkenal karano teknologi saparti komputasi paralel alah manjadikannyo pandekatan nan praktis untuak masalah ilmiah.

Pengkondisian jo stabilitas

Biarkan masalah adalah fungsi $f:X\to Y$, di mana X adalah ruang vektor data bernorma dan Y adalah ruang vektor bernorma solusi. Untuk beberapa titik data $x\in X$, masalah dikatakan tidak terkondisi jika gangguan kecil di x menghasilkan perubahan besar dalam nilai f(x) . Kita dapat mengukur ini dengan mendefinisikan jumlah kondisi ​​yang mewakili seberapa baik masalah dikondisikan, didefinisikan sebagai

${\widehat {\kappa }}=\lim _{\delta \to 0}\sup _{\|\delta x\|\leq \delta }{\frac {\|\delta f\|}{\|\delta x\|}}$

Ketidakstabilan adalah kecenderungan algoritma komputer, yang bergantung pada aritmatika floating-point, untuk menghasilkan hasil yang berbeda secara dramatis dari solusi matematika yang tepat untuk suatu masalah. Ketika matriks berisi data nyata dengan banyak digit signifikan, banyak algoritma untuk memecahkan masalah seperti sistem persamaan linier atau pengoptimalan kuadrat terkecil dapat menghasilkan hasil yang sangat tidak akurat. Membuat algoritme yang stabil untuk masalah kondisi buruk merupakan perhatian utama dalam aljabar linear numerik. Salah satu contohnya adalah stabilitas triangularisasi perumah tangga membuatnya sangat merampok, sedangkan ketidakstabilan metode persamaan normal untuk menyelesaikan masalah kuadrat terkecil adalah alasan untuk mendukung metode dekomposisi matriks seperti menggunakan dekomposisi nilai singular. Beberapa matriks tetapi memiliki modifikasi langsung yang membuatnya stabil; salah satu contohnya adalah Gram–Schmidt yang tidak stabil, yang dapat dengan mudah diubah untuk menghasilkan stabilitas numerik. Masalah klasik lainnya dalam aljabar linear numerik adalah temuan bahwa eliminasi Gaussian tidak stabil, tetapi menjadi stabil dengan diperkenalkannya pivoting.

Metode baulang

Ado duo alasan bahwa algoritme iteratif marupoan bagian nan penting dari aljabar linear numerik. Patamo, banyak masalah numerik penting nan indak mamiliki solusi lansuang; untuak manamuan nilai eigen jo vektor eigen dari matriks sumbarang, hanyo dapek maadopsi pandekatan iteratif. Kaduo, algoritma noniteratif untuak sumbarang $m\times m$ matriks mambutuhan $O(m^{3})$ wakatu, nan marupoan lantai nan tinggi bana karano hanyo baisi matriks $m^{2}$ nomor. Pandekatan nan baulang dapek mamanfaatkan babarapo fitur dari babarapo matriks untuak mengurangi waktu iko. Misalnyo, jiko matriks adolah rengga, algoritme iteratif dapek malewati banyak langkah nan musti diikuti dek pendekatan lansuang, bahkan jiko langkah-langkah tersebut balabiahan karano matriks tastruktur bana. Inti dari metode nan banyak iteratif dalam aljabar linear numerik adolah proyeksi matriks ka dimensi nan labiah randah Subruang Krylov, nan mamungkinkan fitur matriks nan badimensi tinggi didekati jo maituang sacaro iteratif fitur ekuivalen dari matriks nan saroman nan dimulai dari ruang badimensi randah jo bapindah sacaro barurntun. Katiko A simetris sarato nio manyalasaian masalah linear Ax = b , pandekatan iteratif klasiknyo adolah metode gradien konjugasi. Jiko A indak simetris, mako contoh solusi iteratif untuak masalah linier adolah metode residual minimal tergeneralisasi jo konjugasi gradien pada normal e. Jiko A simetris, mako untuak manyalasaian soal nilai eigen jo vektor eigen bisa manggunoan Algoritma Lanczos, jo jiko A non-simetris, mako bisa manggunoan iterasi Arnoldi.