Solusi eksplisit yang stabil secara numerik dari sistem linear kecil

11

Saya memiliki sistem linear yang tidak homogen

A x = b

$Ax=b$

di mana $A$ adalah nyata $n\times n$ matriks dengan $n\leq 4$ . Nullspace dari $A$ dijamin dari dimensi nol sehingga persamaan memiliki invers yang unik $x=A^{-1} b$ . Karena hasilnya masuk ke sisi kanan dari ODE, yang ingin saya pecahkan dengan menggunakan metode adaptif, penting agar solusinya halus sehubungan dengan variasi kecil elemen $A$ dan $b$ . Karena persyaratan ini dan dimensi kecil, saya berpikir untuk mengimplementasikan formula eksplisit untuk $A^{-1} b$ . Elemen-elemennya bisa nol atau mengambil nilai yang sangat berbeda. Pertanyaan saya adalah apakah ini masuk akal bagi Anda dan jika ada ekspresi stabil yang diketahui untuk ini. Saya mengkode dalam C untuk sistem x86.

linear-algebra ode kelas tinggi
sumber

Saya tahu ini datang sangat terlambat, tapi di sini adalah saran saya: karena eliminasi Gaussian dengan pivoting total diketahui stabil, masuk akal untuk membuat hard-code algoritma untuk ukuran kecil. Berputar memperumit masalah karena ada

(n!)^{2}

$(n!)^2$ cara untuk memilih pivot yang berurutan, yang mengarah ke

(n!)^{2}

$(n!)^2$ rangkaian formula yang berbeda; Anda dapat mengurangi kompleksitas ini dengan menukar apa yang perlu ditukar, mengurangi jumlah kasus menjadi

1^{2} + 2^{2} + \dots n^{2}

$1^2+2^2+\cdots n^2$ .

Yves Daoust

6

Sebelum menerapkan formula eksplisit, saya akan bertanya pada diri sendiri pertanyaan: "apakah itu layak?":

Apakah layak menghabiskan waktu menulis, men-debug dan memvalidasi formula eksplisit ini sementara Anda dapat dengan mudah menautkan ke BLAS + LAPACK yang menggunakan eliminasi Gaussian klasik?
Apakah Anda berharap mendapatkan stabilitas? Saya tidak berpikir pemrograman rumus eksplisit (seperti aturan Cramer) akan memberi Anda stabilitas yang lebih baik, sebaliknya.
Apakah Anda berharap untuk mendapatkan kecepatan? Apakah Anda sudah membuat profil seluruh program Anda? Berapa lama waktu yang dihabiskan untuk menyelesaikan sistem 4x4 ini?
Berapa probabilitas bahwa dalam waktu satu tahun, Anda meningkatkan model dan Anda membutuhkan 5 persamaan, bukan 4?

Saran saya: gunakan kombinasi BLAS / LAPACK terlebih dahulu, lihat apakah itu berfungsi, profil seluruh program, minta siswa untuk mengimplementasikan formula eksplisit (maaf, menjadi sarkastik di sini) dan membuat perbandingan pada kecepatan dan kekokohan.

GertVdE
sumber

Upaya yang saya perlukan untuk mengimplementasikannya adalah sekitar 15 menit, karena saya cukup memasukkan matriks 1x1, 2x2, 3x3, dan 4x4 umum ke dalam CAS (Maple untuk saya) dan membaliknya. Ini akan mengembalikan hasil eksplisit (seperti C) (diduga berdasarkan aturan Cramer). Poin kedua Anda benar-benar perhatian saya. Dalam hasilnya akan ada produk pesanan yang lebih tinggi dari elemen matriks. Jelas ini dapat menyebabkan kesalahan karena 'pembatalan' dari istilah yang berbeda. Tetapi pertanyaannya adalah, apakah mungkin untuk menulis hasilnya dalam bentuk di mana ini tidak terjadi. Kecepatan bukanlah perhatian utama di tempat ini.

highsciguy

6

Satu-satunya hasil terbalik eksplisit yang saya ketahui adalah Aturan Cramer , yang baru-baru ini terbukti dapat dihitung dalam waktu (seperti eliminasi Gaussian; meskipun tidak yakin dengan konstanta di depan faktor utama). $\mathcal{O}(n^{3})$

$A$ $A$ $\det(A) \neq 0$ $x$ $b$ $x$ $A$

Agar aman, mungkin yang terbaik adalah memastikan bahwa juga tidak kekurangan peringkat secara numerik (yaitu, tidak memiliki nilai singular yang kecil). $A$

Masalah dengan Aturan Cramer's adalah bahwa sifat stabilitasnya tidak diketahui kecuali untuk (yang maju stabil, tetapi tidak mundur stabil). (Lihat Akurasi dan Stabilitas Algoritma Numerik , edisi ke-2, oleh N. Higham.) Itu tidak dianggap sebagai algoritma yang dapat diandalkan; Eliminasi Gaussian dengan Partial Pivoting (GEPP) lebih disukai. $n = 2$

Saya akan mengharapkan masalah dengan menggunakan BLAS + LAPACK untuk melakukan GEPP dalam penyelesaian ODE akan ada perbedaan hingga digunakan dalam metode ODE implisit. Saya tahu bahwa orang telah menyelesaikan program linier sebagai bagian dari evaluasi sisi kanan, dan karena mereka melakukannya dengan naif (hanya menyambungkan program linear ke sisi kanan, memanggil algoritma simpleks), mereka sangat mengurangi keakuratan program mereka. solusi yang dihitung dan secara substansial meningkatkan waktu yang dibutuhkan untuk menyelesaikan masalah. Teman sekerja saya menemukan cara untuk menyelesaikan masalah seperti itu dengan cara yang jauh lebih efisien, akurat; Saya harus melihat apakah publikasi ini sudah dirilis. Anda mungkin memiliki masalah serupa terlepas dari apakah Anda memilih untuk menggunakan GEPP atau Aturan Cramer's.

Jika ada cara Anda dapat menghitung matriks Jacobian analitik untuk masalah Anda, Anda mungkin ingin melakukan itu untuk menyelamatkan diri Anda dari sakit kepala numerik. Akan lebih murah untuk mengevaluasi, dan mungkin lebih akurat, daripada perkiraan perbedaan yang terbatas. Ekspresi untuk turunan dari matriks invers dapat ditemukan di sini jika Anda membutuhkannya. Mengevaluasi turunan dari matriks invers sepertinya akan membutuhkan setidaknya dua atau tiga penyelesaian sistem linier, tetapi semuanya akan dengan matriks yang sama dan sisi kanan yang berbeda, sehingga tidak akan jauh lebih mahal daripada sistem linear tunggal. memecahkan.

Dan jika ada cara Anda dapat membandingkan solusi yang dihitung dengan solusi dengan nilai parameter yang diketahui, saya akan melakukan itu, sehingga Anda dapat mendiagnosis apakah Anda telah menemukan salah satu dari jebakan numerik ini.

Geoff Oxberry
sumber

Ketika Anda menulis dengan lancar di sini, maksud Anda bahwa itu juga mulus ketika dievaluasi dengan ketepatan terbatas, yaitu stabil (itulah yang saya coba katakan). Lihat juga komentar saya untuk jawaban GertVdE. Saya pikir saya dapat mengecualikan matriks yang hampir tunggal (saya kira dalam kasus seperti itu analisis masalah fisik saya harus dirumuskan ulang).

highsciguy

1

A

$A$

det (A) \neq 0

$\det(A) \neq 0$

n

$n$

A

$A$

-2

Tidak yakin itu bisa membantu tetapi saya hanya berpikir ketika Anda berbicara tentang solusi stabil, Anda berbicara tentang metode perkiraan. Ketika Anda menghitung hal-hal secara eksplisit, stabilitas tidak memiliki akal. Itu mengatakan Anda harus menerima solusi perkiraan jika Anda ingin mendapatkan stabilitas.

ctNGUYEN
sumber

5

Perkiraan titik-mengambang (pembulatan, pembatalan, dll.) Semuanya masuk dalam stabilitas. Bahkan jika Anda memiliki rumus untuk jawabannya, Anda harus mengetahui apakah rumus itu dapat dihitung secara akurat dalam aritmatika presisi-terbatas.

Bill Barth

Saya tidak melihat jawaban ini sama negatifnya dengan yang orang lain lihat. Tentu saja masalah stabilitas ada juga untuk hasil yang eksplisit. Tapi saya percaya ctNGUYEN hanya ingin mengatakan solusi perkiraan seperti ekspansi dalam jumlah kecil sebenarnya bisa lebih tepat daripada hasil eksplisit penuh yang, saya pikir, benar. Dalam arti tertentu saya meminta solusi eksplisit yang menangani kasus-kasus sulit seperti itu, sehingga formula akan selalu stabil.

highsciguy

Solusi eksplisit yang stabil secara numerik dari sistem linear kecil

Jawaban: