Solusi persamaan kuartik

Apakah ada implementasi C terbuka untuk solusi persamaan kuartik:

a x ⁴ + b x ³ + c x ² + d x + e = 0

$ax⁴+bx³+cx²+dx+e=0$

Saya sedang memikirkan implementasi solusi Ferrari. Di Wikipedia saya membaca bahwa solusinya adalah stabil komputasi hanya untuk beberapa kombinasi tanda yang mungkin dari koefisien. Tapi mungkin saya beruntung ... Saya mendapat solusi pragmatis dengan menyelesaikan secara analitis menggunakan sistem aljabar komputer dan mengekspor ke C. Tetapi jika ada implementasi yang diuji saya lebih suka menggunakan ini. Saya mencari metode cepat dan memilih untuk tidak menggunakan pencari akar umum.

Saya hanya membutuhkan solusi nyata.

polynomials nonlinear-equations roots kelas tinggi
sumber

Apakah Anda membutuhkan semua solusi (nyata) secara bersamaan? Seperti yang dikatakan GertVdE di bawah ini, jika Anda memiliki masalah stabilitas dengan solusi formulir tertutup, sebenarnya tidak ada alasan bagus untuk tidak menggunakan beberapa algoritma pencarian root.

Godric Seer

Saya merasa lucu bahwa ini ditandai dengan aljabar nonlinier, karena Anda bisa menghitung nilai eigen dari matriks pendamping, yang sudah dalam bentuk Hessenberg dan menerapkan sapuan QR akan sangat sederhana.

Victor Liu

Lihatlah pemecah kubik / kuartik yang diterbitkan dalam ACM TOMS (Algoritma 954) . Kode yang membuatnya menjadi jurnal itu biasanya berkualitas sangat tinggi. Makalah itu sendiri ada di belakang paywall tetapi kodenya dapat diunduh dari tautan ini .

GoHokies

... (nanti diedit) kode ACM ditulis dalam FORTRAN 90 tetapi kesan pertama saya adalah bahwa seseorang dapat memanggilnya dari C tanpa berusaha keras.

GoHokies

@ Gookies Saya pikir Anda harus mengubah komentar Anda menjadi jawaban karena saya pikir itu adalah jawaban yang baik untuk pertanyaan ini. Terutama karena kertas yang terhubung berhasil menghindari ketidakstabilan numerik yang biasa, dan itu sama sekali bukan hal yang sepele untuk dilakukan.

Kirill

Jawaban:

Saya akan sangat menyarankan untuk menggunakan solusi bentuk tertutup karena mereka cenderung sangat tidak stabil secara numerik. Anda perlu sangat berhati-hati dalam cara dan urutan evaluasi Anda terhadap parameter diskriminan dan lainnya.

Contoh klasik adalah yang untuk persamaan kuadrat . Menghitung akar sebagai akan membuat Anda mendapat masalah untuk polinomial di mana sejak saat itu Anda mendapatkan pembatalan di pembilang. Anda perlu menghitung . $ax^2+bx+c=0$

x_{1, 2} = \frac{- b \pm \sqrt{b^{2} - 4 Sebuah c}}{2 Sebuah}

$x_{1,2} = \frac{-b \pm \sqrt{b^2-4ac}}{2a}$

b ≫ 4 a c

$b\gg 4ac$

x_{1} = \frac{- (b + s saya g n (b) \sqrt{b^{2} - 4 Sebuah c})}{2 Sebuah}; x_{2} = \frac{c}{Sebuah} \frac{1}{x_{1}}

$x_1 = \frac{-(b+sign(b)\sqrt{b^2-4ac})}{2a}; x_2 = \frac{c}{a}\frac{1}{x_1}$

Higham dalam karya besarnya "Akurasi dan Stabilitas Algoritma Angka" (edisi ke-2, SIAM) menggunakan metode pencarian langsung untuk menemukan koefisien polinomial kubik yang mana solusi kubik analitik klasik memberikan hasil yang sangat tidak akurat. Contoh yang dia berikan adalah . Untuk polinomial ini akar dipisahkan dengan baik dan karenanya masalahnya tidak dikondisikan. Namun, jika ia menghitung akar menggunakan pendekatan analitis, dan mengevaluasi polinomial pada akar ini, ia memperoleh residu dari sambil menggunakan metode standar yang stabil (metode matriks pengiring) , residunya berurutan $[a,b,c] = [1.732, 1, 1.2704]$ $\mathcal{O}(10^{-2})$ $\mathcal{O}(10^{-15})$ . Dia mengusulkan sedikit modifikasi pada algoritma, tetapi bahkan kemudian, dia dapat menemukan satu set koefisien yang mengarah ke residu dari yang pasti tidak baik. Lihat p480-481 buku yang disebutkan di atas. $\mathcal{O}(10^{-11})$

Dalam kasus Anda, saya akan menerapkan metode Bairstow . Ia menggunakan kombinasi iterasi dari iterasi Newton pada bentuk kuadrat (dan kemudian akar kuadrat dipecahkan) dan deflasi. Ini mudah diimplementasikan dan bahkan ada beberapa implementasi yang tersedia di web.

GertVdE
sumber

Bisakah Anda jelaskan apa yang Anda maksud dengan "Saya akan sangat menyarankan agar tidak menggunakan solusi formulir tertutup karena cenderung tidak stabil secara numerik." Apakah ini hanya berlaku untuk polinomial tingkat 4 atau apakah ini aturan umum?

NoChance

@EmmadKareem Saya telah memperbarui jawaban saya di atas.

GertVdE

Lihat ini:

Pemecahan Quartics dan cubics untuk Graphics , awalnya diterbitkan di Graphics Gems V . Kode aslinya ada di sini . Lihat juga ini dan ini .
Metode Universal Memecahkan Persamaan Kuartik .

lhf
sumber

x_{1} = - 1.602644912244132 e + 00

$x_1 = -1.602644912244132e+00$

O (10^{- 8})

$\mathcal{O}(10^{-8})$

O (10^{- 7})

$\mathcal{O}(10^{-7})$

O (10^{- 15})

$\mathcal{O}(10^{-15})$ . Terserah Anda apakah ini cukup baik (untuk grafik komputer mungkin, untuk beberapa aplikasi lain, itu tidak akan)

GertVdE

Resep numerik dalam c memberikan ekspresi bentuk tertutup untuk akar kuadratik dan kubik nyata yang mungkin memiliki presisi yang layak. Karena solusi aljabar kuartik melibatkan pemecahan kubik dan kemudian menyelesaikan dua kuadrat mungkin bentuk kuartik tertutup dengan presisi yang baik tidak keluar dari pertanyaan.

Nemocopperfield
sumber

Saya baru saja mendapatkan akar dari contoh kubik yang dikutip dalam 2e-16 (sedikit lebih presisi dari mengapung saya) menggunakan resep numerik dalam rumus c (tekan et al) kubik. Jadi ada alasan untuk berharap.

Nemocopperfield