Numerical
Analiysis adalah studi tentang
algoritma yang menggunakan pendekatan numerik (sebagai lawan umum manipulasi
simbolik) untuk masalah analisis matematika (yang dibedakan dari matematika
diskrit)
Solving Linear Equations
input output
Input Description
: Sebuah m x n matriks A, dan m x 1 vektor b,
mewakili m persamaan linear dengan n variabel.
Kutipan dari The Algoritma Desain Manual:
Pemecahan sistem linear merupakan masalah penting ilmiah dan komersial sehingga
kode yang sangat baik yang tersedia. Ada kemungkinan ada alasan yang baik untuk
melaksanakan solver Anda sendiri, meskipun algoritma dasar (Gaussian eliminasi)
adalah salah satu yang kita pelajari di sekolah tinggi. Hal ini terutama
berlaku jika Anda bekerja dengan sistem yang besar.
Eliminasi
Gauss didasarkan pada kenyataan bahwa solusi untuk sistem persamaan linear
invarian pada skala (mengalikan kedua sisi dengan konstan, yaitu jika x = y,
maka 2x = 2y) dan menambahkan persamaan (yaitu solusi untuk persamaan x = y dan
w = z adalah sama dengan solusi untuk x = y dan x + w = y + z). sisik
eliminasi Gauss dan menambahkan persamaan sehingga dapat menghilangkan setiap variabel
dari semua kecuali satu persamaan, meninggalkan sistem dalam keadaan bahwa
solusi hanya dapat dibaca dari persamaan.
Bandwidth Reduction
input output
Input Description: A G = (V, E) grafik, mewakili n x n matriks M dari nol dan
unsur-unsur non-nol.
Soal: Yang permutasi p dari simpul V
meminimalkan \ max _ {(i, j) \ di E} | p (i) - p (j) |, atau ekuivalen panjang
tepi terpanjang ketika simpul yang diperintahkan pada garis.
Kutipan dari The Algoritma Desain Manual:
pengurangan Bandwidth mengintai sebagai masalah tersembunyi tetapi penting bagi
kedua grafik dan matriks, dan penting untuk melihat bagaimana hal itu timbul
sehingga benar mengenalinya. Diterapkan untuk matriks, itu permutes baris dan
kolom dari matriks jarang sehingga dapat meminimalkan jarak b dari setiap entri
nol dari pusat diagonal. Hal ini penting dalam memecahkan sistem linear, karena
eliminasi Gauss dapat dilakukan di O (n b2) pada matriks bandwidth b. Ini
adalah kemenangan besar atas O umum (n3) algoritma jika b << n.
Bandwidth minimisasi pada grafik muncul dengan
cara yang lebih halus. Mengatur satu set komponen n sirkuit dalam garis pada
papan sirkuit sehingga dapat meminimalkan panjang kawat terpanjang (dan
karenanya waktu tunda) adalah masalah bandwidth, di mana masing-masing simpul
dari graph kami sesuai dengan komponen sirkuit dan ada tepi untuk setiap kawat
menghubungkan dua komponen.
Matrix
Multiplication
input output
Input Description: Sebuah x x y matriks A, dan y x z matriks B.
Masalah: x x z matriks A x B.
Kutipan dari The
Algoritma Desain Manual: Meskipun perkalian matriks merupakan masalah penting
dalam aljabar linier, signifikansi utama untuk algoritma kombinatorial adalah
kesetaraan untuk berbagai masalah lain, seperti penutupan transitif dan
pengurangan, memecahkan sistem linear, dan matriks inversi. Jadi algoritma
cepat untuk perkalian matriks menyiratkan algoritma cepat untuk semua masalah ini.
Perkalian matriks muncul dalam dirinya sendiri dalam menghitung hasil
transformasi koordinat seperti scaling, rotasi, dan translasi untuk robotika
dan komputer grafis.
Algoritma asimtotik lebih cepat untuk perkalian matriks
ada, berdasarkan pintar kekambuhan membagi-dan-menaklukkan. Namun, ini terbukti
sulit untuk program dan memerlukan matriks sangat besar untuk mengalahkan
algoritma sepele.
Daftar Pustaka :
https://en.wikipedia.org/wiki/Numerical_analysis
Daftar Pustaka :
https://en.wikipedia.org/wiki/Numerical_analysis
Baca juga :
0 komentar:
Posting Komentar