Cara memilih metode untuk menyelesaikan persamaan linear

31

Sepengetahuan saya, ada 4 cara untuk memecahkan sistem persamaan linear (koreksi saya jika ada lebih banyak):

  1. Jika matriks sistem adalah matriks kuadrat peringkat penuh, Anda dapat menggunakan Aturan Cramer;
  2. Hitung invers atau pseudoinverse dari matriks sistem;
  3. Gunakan metode dekomposisi matriks (eliminasi Gaussian atau Gauss-Jordan dianggap sebagai dekomposisi LU);
  4. Gunakan metode berulang, seperti metode gradien konjugat.

Bahkan, Anda hampir tidak pernah ingin menyelesaikan persamaan dengan menggunakan aturan Cramer atau menghitung invers atau pseudoinverse, terutama untuk matriks dimensi tinggi, jadi pertanyaan pertama adalah kapan harus menggunakan metode dekomposisi dan metode iteratif, masing-masing. Saya kira itu tergantung pada ukuran dan properti dari matriks sistem.

Pertanyaan kedua adalah, sepengetahuan Anda, metode dekomposisi atau metode iteratif seperti apa yang paling cocok untuk matriks sistem tertentu dalam hal stabilitas dan efisiensi numerik.

Sebagai contoh, metode gradien konjugat digunakan untuk menyelesaikan persamaan di mana matriksnya simetris dan pasti positif, meskipun itu juga dapat diterapkan ke persamaan linear dengan mengonversi ke . Juga untuk matriks pasti positif, Anda dapat menggunakan metode dekomposisi Cholesky untuk mencari solusinya. Tapi saya tidak tahu kapan harus memilih metode CG dan kapan harus memilih pembusukan Cholesky. Perasaan saya adalah kita sebaiknya menggunakan metode CG untuk matriks besar.Ax=bATAx=ATb

Untuk matriks persegi panjang, kita dapat menggunakan dekomposisi QR atau SVD, tetapi sekali lagi saya tidak tahu bagaimana memilih salah satunya.

Untuk matriks lain, sekarang saya tidak bagaimana memilih pemecah yang tepat, seperti matriks Hermitian / simetris, matriks jarang, matriks band dll.

chaohuang
sumber
1
Hai @chaohuang, dan selamat datang di SciComp! Anda mungkin ingin melihat diskusi ini: scicomp.stackexchange.com/questions/81/…
Paul
Hai @ Paul, terima kasih atas komentar Anda, apakah utas itu hanya tentang matriks jarang atau matriks apa pun?
chaohuang
6
Pertanyaan Anda memiliki cakupan luas dan mungkin agak terlalu luas untuk format Tanya Jawab yang kami miliki di sini di stackexchange ... apakah ada kelas sistem matriks tertentu yang Anda minati?
Paul
3
@chaohuang Ada banyak buku tentang hal ini. Pertanyaan ini agak seperti bertanya kepada dokter bagaimana mereka memilih perawatan "secara umum". Jika Anda ingin mengajukan pertanyaan yang tidak spesifik untuk kelas masalah tertentu, Anda harus menempatkan dalam pekerjaan untuk menjadi cukup akrab dengan bidang tersebut untuk mengajukan sesuatu yang tepat. Kalau tidak, jelaskan masalah khusus yang Anda khawatirkan.
Jed Brown
2
Dari FAQ: Jika Anda dapat membayangkan seluruh buku yang menjawab pertanyaan Anda, Anda terlalu banyak bertanya. Ada seluruh jurnal, dan ratusan buku, terkait dengan pertanyaan ini.
David Ketcheson

Jawaban:

45

Pertanyaan Anda agak seperti menanyakan obeng mana yang akan dipilih tergantung pada drive (slot, Phillips, Torx, ...): Selain ada terlalu banyak , pilihan juga tergantung pada apakah Anda ingin hanya mengencangkan satu sekrup atau merakit sebuah seluruh set rak perpustakaan. Namun demikian, dalam jawaban parsial untuk pertanyaan Anda, berikut adalah beberapa masalah yang harus Anda ingat ketika memilih metode untuk menyelesaikan sistem linear . Saya juga akan membatasi diri saya pada matriks yang dapat dibalik; kasus-kasus sistem yang kelebihan atau tidak ditentukan adalah masalah yang berbeda dan harus benar-benar menjadi pertanyaan yang terpisah.SEBUAHx=b

Seperti yang Anda catat dengan benar, opsi 1 dan 2 benar: Menghitung dan menerapkan matriks terbalik adalah ide yang sangat buruk, karena jauh lebih mahal dan sering kurang stabil secara numerik daripada menerapkan salah satu algoritma lainnya. Itu membuat Anda memiliki pilihan antara metode langsung dan berulang. Hal pertama yang perlu dipertimbangkan bukanlah matriks , tetapi apa yang Anda harapkan dari solusi numerik ˜ x :SEBUAHx~

  1. Seberapa akurat seharusnya? Apakah harus menyelesaikan sistem hingga presisi mesin, atau apakah Anda puas dengan ˜ x memuaskan (katakanlah) ˜ x - x < 10 - 3 , di mana x adalah solusi yang tepat?x~x~x~-x<10-3x
  2. Seberapa cepat Anda membutuhkannya? Satu-satunya metrik yang relevan di sini adalah waktu jam di komputer Anda - metode yang menskala dengan sempurna pada sekelompok besar mungkin bukan pilihan terbaik jika Anda tidak memilikinya, tetapi Anda memiliki salah satu kartu Tesla baru yang mengkilap.

Karena tidak ada makan siang gratis, Anda biasanya harus memutuskan pertukaran antara keduanya. Setelah itu, Anda mulai melihat matriks (dan perangkat keras Anda) untuk memutuskan metode yang baik (atau lebih tepatnya, metode yang Anda bisa temukan implementasi yang baik). (Perhatikan bagaimana saya menghindari menulis "terbaik" di sini ...) Properti paling relevan di sini adalahSEBUAH

  • The Struktur : Is simetris? Apakah padat atau jarang? Terikat?SEBUAH
  • Nilai eigen : Apakah semuanya positif (yaitu, apakah pasti positif)? Apakah mereka terkelompok? Apakah beberapa dari mereka memiliki ukuran yang sangat kecil atau sangat besar?SEBUAH

Dengan pemikiran ini, Anda kemudian harus menjelajah literatur (besar) dan mengevaluasi berbagai metode yang Anda temukan untuk masalah spesifik Anda. Berikut adalah beberapa pernyataan umum:

  • 1000HAI(n2)HAI(n3)SEBUAH

    Ini juga berlaku untuk matriks sparse (besar) jika Anda tidak mengalami masalah memori: Matriks jarang pada umumnya tidak memiliki dekomposisi LU yang jarang, dan jika faktor-faktor tidak sesuai dengan memori (cepat), metode ini menjadi tidak dapat digunakan.

    SEBUAH

  • SEBUAHSEBUAH

  • Jika Anda berulang kali harus menyelesaikan sistem linear dengan matriks yang sama dan sisi kanan yang berbeda, metode langsung masih bisa lebih cepat daripada metode berulang karena Anda hanya perlu menghitung dekomposisi sekali. (Ini mengasumsikan solusi berurutan; jika Anda memiliki semua sisi kanan pada saat yang sama, Anda dapat menggunakan metode blok Krylov.)

Tentu saja, ini hanyalah pedoman yang sangat kasar: Untuk setiap pernyataan di atas, kemungkinan ada matriks yang sebaliknya benar ...

Karena Anda meminta referensi dalam komentar, berikut adalah beberapa buku teks dan makalah ulasan untuk Anda mulai. (Tidak satu pun dari ini - maupun set - yang komprehensif; pertanyaan ini terlalu luas, dan terlalu tergantung pada masalah khusus Anda.)

Christian Clason
sumber
2
Saya suka analogi Anda tentang obeng!
Paul
@chaohuang Jika ini menjawab pertanyaan Anda, Anda harus menerimanya. (Jika tidak, silakan tunjukkan apa yang hilang.)
Christian Clason
@ChristianClason menerimanya. Saya sedang menunggu dan berharap seseorang dapat menjelaskan masalah matriks persegi panjang. Karena sudah lama, saya kira tidak akan pernah ada jawaban seperti ini :(
chaohuang
@chaohuang Terima kasih. Jika Anda masih tertarik pada matriks persegi panjang, Anda harus mengajukan pertanyaan (ditautkan) pada "Cara memilih metode untuk menyelesaikan sistem yang ditentukan secara berlebihan".
Christian Clason
Di sini referensi tentang penggunaan metode iteratif untuk memecahkan sistem persamaan linear yang jarang dan besar.
chaohuang