Aljabar linear numerik

Aljabar linear numerik adalah pengkajian algoritme untuk melakukan proses komputasi aljabar linear, terutama operasi matriks, pada komputer. Pengkajian ini sering menjadi bagian paling mendasar di dalam persoalan teknik dan ilmu komputasi, semisal pengolahan citra dan sinyal, komputasi keuangan, simulasi ilmu bahan, biologi struktural, data mining, dan bioinformatika, dinamika fluida, dan banyak ranah lainnya. Ada beberapa perangkat lunak yang sangat bergantung pada pengembangan, analisis, dan penerapan algoritme state-of-the-art untuk menyelesaikan berbagai persoalan aljabar linear numerik, pada porsi yang besar karena peranan matriks di dalam metode beda hingga dan metode unsur hingga.

Persoalan yang lazim di dalam aljabar linear numerik di antaranya komputasi misalnya sebagai berikut: penguraian LU, penguraian QR, penguraian nilai singular, nilai eigen.

Sejarah

Aljabar linier numerik dikembangkan oleh para pelopor komputer seperti John von Neumann, Alan Turing, James H. Wilkinson, Alston Scott Householder, George Forsythe, dan Heinz Rutishauser, dalam rangka untuk menerapkan komputer paling awal untuk masalah dalam matematika berkelanjutan, seperti masalah balistik dan solusi untuk sistem persamaan diferensial parsial.^[1] Upaya serius pertama untuk meminimalkan kesalahan komputer dalam penerapan algoritme pada data nyata adalah karya John von Neumann dan Herman Goldstine pada tahun 1947.^[2] Bidang ini telah berkembang karena teknologi semakin memungkinkan para peneliti untuk memecahkan masalah kompleks pada matriks presisi tinggi yang sangat besar, dan beberapa algoritme numerik menjadi terkenal karena teknologi seperti komputasi paralel telah menjadikannya pendekatan praktis untuk masalah ilmiah.^[1]

Pengkondisian dan 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.^[3]^:140 Masalah klasik lainnya dalam aljabar linear numerik adalah temuan bahwa eliminasi Gaussian tidak stabil, tetapi menjadi stabil dengan diperkenalkannya pivoting.

Metode berulang

Ada dua alasan bahwa algoritme iteratif merupakan bagian penting dari aljabar linear numerik. Pertama, banyak masalah numerik penting yang tidak memiliki solusi langsung; untuk menemukan nilai eigen dan vektor eigen dari matriks sembarang, kita hanya dapat mengadopsi pendekatan iteratif. Kedua, algoritma noniteratif untuk sembarang $m\times m$ matriks membutuhkan $O(m^{3})$ waktu, yang merupakan lantai yang sangat tinggi karena hanya berisi matriks $m^{2}$ nomor. Pendekatan berulang dapat memanfaatkan beberapa fitur dari beberapa matriks untuk mengurangi waktu ini. Misalnya, jika matriks adalah rengga, algoritme iteratif dapat melewati banyak langkah yang harus diikuti oleh pendekatan langsung, bahkan jika langkah-langkah tersebut berlebihan karena matriks yang sangat terstruktur.

Inti dari banyak metode iteratif dalam aljabar linear numerik adalah proyeksi matriks ke dimensi yang lebih rendah Subruang Krylov, yang memungkinkan fitur matriks berdimensi tinggi didekati dengan menghitung secara iteratif fitur ekuivalen dari matriks serupa yang dimulai dari ruang berdimensi rendah dan berpindah secara berurutan. Ketika A simetris dan kita ingin menyelesaikan masalah linear Ax = b , pendekatan iteratif klasiknya adalah metode gradien konjugasi. Jika A tidak simetris, maka contoh solusi iteratif untuk masalah linier adalah metode residual minimal tergeneralisasi dan konjugasi gradien pada normal e. Jika A simetris, maka untuk menyelesaikan soal nilai eigen dan vektor eigen kita bisa menggunakan Algoritma Lanczos, dan jika A non-simetris, maka kita bisa menggunakan iterasi Arnoldi.

Matriks partisi

Untuk banyak masalah dalam aljabar linier terapan, akan berguna untuk mengadopsi perspektif matriks sebagai rangkaian vektor kolom. Misalnya, saat menyelesaikan sistem linear $x=A^{-1}b$ , daripada memahami x sebagai produk dari $A^{-1}$ dengan b , akan membantu jika menganggap x sebagai vektor koefisien pada ekspansi linier b dalam basis yang dibentuk oleh kolom A .^[3]^:8 Memikirkan matriks sebagai rangkaian kolom juga merupakan pendekatan praktis untuk tujuan algoritma matriks. Ini karena algoritme matriks sering kali berisi dua loop bersarang: satu di atas kolom matriks A , dan satu lagi di atas baris A . Misalnya untuk matriks $A^{m\times n}$ dan vektor $x^{n\times 1}$ and $y^{m\times 1}$ , kita bisa menggunakan perspektif partisi kolom untuk menghitung Ax + y sebagai

for j = 1:n
  for i = 1:m
    y(i) = A(i,j)x(j) + y(i)
  end
end

Lihat pula

Analisis numerik, di mana aljabar linear numerik adalah salah satu bidang kekhususannya
Eliminasi gauss, algoritme penting di dalam aljabar linear numerik
BLAS dan LAPACK, pustaka komputer yang dioptimasi dengan baik yang menerapkan algoritme yang paling mendasar di dalam aljabar linear numerik
Daftar perangkat lunak analisis numerik

Catatan

^ ^a ^b Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama golubhist
^ von Neumann, John; Goldstine, Herman H. (1947). "Numerical inverting of matrices of high order" (PDF). Bulletin of the American Mathematical Society. 53 (11): 1021–1099. doi:10.1090/s0002-9904-1947-08909-6. Diarsipkan dari versi asli (PDF) tanggal 2019-02-18. Diakses tanggal February 17, 2019.
^ ^a ^b Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama tb397

Referensi

Leader, Jeffery J. (2004). Numerical Analysis and Scientific Computation. Addison Wesley. ISBN 0-201-73499-0.
Bau III, David; Trefethen, Lloyd N. (1997), Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 978-0-89871-361-9

Pranala luar

Perangkat lunak yang tersedia bebas untuk aljabar numerik di web, ditulis oleh Jack Dongarra dan Hatem Ltaief, Universitas Tennessee

[golubhist-1] Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama golubhist

[2] von Neumann, John; Goldstine, Herman H. (1947). "Numerical inverting of matrices of high order" (PDF). Bulletin of the American Mathematical Society. 53 (11): 1021–1099. doi:10.1090/s0002-9904-1947-08909-6. Diarsipkan dari versi asli (PDF) tanggal 2019-02-18. Diakses tanggal February 17, 2019.

[tb397-3] Kesalahan pengutipan: Tag <ref> tidak sah; tidak ditemukan teks untuk ref bernama tb397

[1]

[2]

[3]