Latar Belakang Matematika
Misalkan A menjadi N oleh N matriks bilangan real, vektor ba dari bilangan real N dan vektor xa N bilangan real yang tidak diketahui. Persamaan matriks adalah Ax = b.
Metode Jacobi adalah sebagai berikut: mendekomposisi A = D + R, di mana D adalah matriks diagonal, dan R adalah entri yang tersisa.
jika Anda membuat solusi tebakan awal x0, solusi yang ditingkatkan adalah x1 = terbalik (D) * (b - Rx) di mana semua perkalian adalah perkalian vektor-matriks dan kebalikan (D) adalah kebalikan matriks.
Spesifikasi Masalah
- Input : Program lengkap Anda harus menerima sebagai input data berikut: matriks A, vektor b, tebakan awal x0, dan nomor 'kesalahan' e.
- Output : Program harus menampilkan jumlah iterasi minimum sehingga solusi terbaru berbeda dengan solusi sebenarnya, paling banyak e. Ini berarti setiap komponen vektor dalam besaran absolut berbeda paling banyak e. Anda harus menggunakan metode Jacobi untuk iterasi.
Bagaimana data dimasukkan adalah pilihan Anda ; itu bisa menjadi sintaks Anda sendiri pada baris perintah, Anda bisa mengambil input dari file, apa pun yang Anda pilih.
Bagaimana data dikeluarkan adalah pilihan Anda ; itu dapat ditulis ke file, ditampilkan di baris perintah, ditulis sebagai seni ASCII, apa pun, selama itu dapat dibaca oleh manusia.
Keterangan lebih lanjut
Anda tidak diberi solusi yang benar: bagaimana Anda menghitung solusi yang benar sepenuhnya terserah Anda. Anda dapat menyelesaikannya dengan aturan Cramer misalnya, atau menghitung invers secara langsung. Yang penting adalah Anda memiliki solusi yang benar untuk dapat dibandingkan dengan iterasi.
Presisi adalah masalah; 'solusi pasti' sebagian orang untuk perbandingan mungkin berbeda. Untuk keperluan golf kode ini solusi yang tepat harus benar untuk 10 tempat desimal.
Untuk menjadi sangat jelas, jika bahkan satu komponen dari solusi iterasi Anda saat ini melebihi komponen yang sesuai dalam solusi yang benar oleh e, maka Anda harus tetap iterasi.
Batas atas ke N bervariasi berdasarkan perangkat keras apa yang Anda gunakan dan berapa banyak waktu yang Anda habiskan untuk menjalankan program. Untuk keperluan golf kode ini, asumsikan maksimum N = 50.
Prasyarat
Ketika program Anda dipanggil, Anda bebas untuk menganggap bahwa yang berikut ini berlaku setiap saat:
- N> 1 dan N <51, yaitu Anda tidak akan pernah diberi persamaan skalar, selalu persamaan matriks.
- Semua input melebihi bidang bilangan real, dan tidak akan pernah kompleks.
- Matriks A selalu sedemikian rupa sehingga metode konvergen ke solusi yang benar, sehingga Anda selalu dapat menemukan sejumlah iterasi untuk meminimalkan kesalahan (sebagaimana didefinisikan di atas) di bawah atau sama dengan e.
- A tidak pernah menjadi matriks nol atau matriks identitas, yaitu ada satu solusi.
Uji Kasus
A = ((9, -2), (1, 3)), b = (3,4), x0 = (1,1), e = 0.04
Solusi sebenarnya adalah (0,586, 1,138). Iterasi pertama memberikan x1 = (5/9, 1), berbeda lebih dari 0,04 dari solusi sebenarnya, oleh setidaknya satu komponen. Mengambil iterasi lain yang kami temukan, x2 = (0,555, 1,148) yang berbeda kurang dari 0,04 dari (0,586, 1,138). Jadi outputnya adalah
2
A = ((2, 3), (1, 4)), b = (2, -1), x0 = (2.7, -0.7), e = 1.0
Dalam hal ini solusi sebenarnya adalah (2.2, -0.8) dan tebakan awal x0 sudah memiliki kesalahan kurang dari e = 1.0, jadi kami output 0. Artinya, setiap kali Anda tidak perlu membuat iterasi, Anda cukup mengeluarkan
0
Penilaian Pengajuan
Ini adalah kode golf, dengan semua celah standar yang tidak diizinkan. Program lengkap yang benar terpendek (atau fungsi), yaitu jumlah byte terendah menang. Hal ini dianjurkan untuk menggunakan hal-hal seperti Mathematica yang membungkus banyak langkah yang diperlukan menjadi satu fungsi, tetapi menggunakan bahasa apapun yang Anda inginkan.
sumber
Jawaban:
APL (Dyalog) ,
78686549 byteJenis masalah yang sebenarnya dibuat untuk APL.
-3 Terima kasih kepada Erik the Outgolfer . -11 Terima kasih kepada ngn .
Fungsi infiks anonim. Membawa A menjadi argumen kiri dan x sebagai argumen kanan. Hasil cetak ke STDOUT sebagai vertikal unary menggunakan
1
sebagai tanda penghitungan, diikuti oleh0
sebagai tanda baca. Ini berarti bahwa bahkan hasil 0 dapat dilihat, tidak ada1
sebelum0
.Cobalah online!
Penjelasan dalam urutan membaca
Perhatikan bagaimana kode membaca sangat mirip dengan spesifikasi masalah:
{
…}
Pada A, b, dan e yang diberikan, dan x yang diberikan,⎕←
cetak∨/
apakah ada kebenaran dalam pernyataan bahwae<
e lebih kecil dari|⍵-
nilai absolut x minusb⌹
b matriks-dibagi dengan⊃A b e
yang pertama dari A, b, dan e (yaitu A)←⍺
yang merupakan argumen kiri:
dan jika demikian, muncul kembali⍺∇
padaD+.×
D-kali matriksb-
minus b⍵+.×⍨
, x, matriks dikalikan denganA-
A dikurangi⌹D
kebalikan dari D (entri yang tersisa) di←
mana D adalahA×
A di mana=/¨
ada⍳
koordinat yang sama untuk⍴A
bentuk A (yaitu diagonal)Penjelasan langkah demi langkah
Urutan eksekusi aktual dari kanan ke kiri:
{
…}
Fungsi anonim di mana⍺
A menjadi dan ⍵ adalah x:A b c←⍺
pisahkan argumen kiri menjadi A, b, dan e⊃
pilihb⌹
divisi matriks pertama (A) dengan b (memberikan nilai sebenarnya dari x)⍵-
perbedaan antara nilai saat ini dari x dan|
nilai absolut yange<
dapat diterima kesalahan kurang dari itu?∨/
berlaku untuk apa saja? (lit. ATAU reduksi)⎕←
mencetak Boolean ke STDOUT:
dan jika demikian:⍴A
bentuk⍳
matriks A dari bentuk itu di mana setiap sel adalah koordinatnya sendiri=/¨
untuk setiap sel, apakah koordinat vertikal dan horizontal sama? (diagonal)A×
kalikan sel-sel A dengan toko⌹
invers matriks (ekstrak diagonal)D←
dalam D (untuk D iagonal)⌹
invers (kembali ke normal)A-
kurangi dari⍵+.×⍨
matriks A, gandakan (hal yang sama dengan produk titik, maka the.
) yang dengan xb-
kurangi dariD+.×
produk matriks b dari D dan yang⍺∇
menerapkan fungsi ini dengan diberi A dan sebagai nilai baru xsumber
e
.Python 3 , 132 byte
Cobalah online!
Menggunakan solusi rekursif.
sumber
f
tidak memiliki nama di dalam blok kode, yang sekarang saya perbaiki; Namun, jika ini adalah masalah yang sama sekali berbeda, itu mungkin masih menjadi masalah.R , 138 byte
Cobalah online!
terima kasih kepada NikoNyrh untuk memperbaiki bug
Perlu juga dicatat bahwa ada paket R,
Rlinsolve
yang berisilsolve.jacobi
fungsi, mengembalikan daftar denganx
(solusi) daniter
(jumlah iterasi yang diperlukan), tapi saya tidak yakin apakah itu melakukan perhitungan yang benar.sumber
norm
fungsi ini menyediakan bagi saya juga tanpa byte tambahan.Clojure,
212198196 byteDiimplementasikan tanpa perpustakaan matriks, ini mengulangi proses 1e9 kali untuk mendapatkan jawaban yang benar. Ini tidak akan bekerja pada input yang terlalu buruk tetapi dalam praktiknya harus bekerja dengan baik.
Kurang golf, saya cukup senang dengan ekspresi
R
danD
:) Input pertama%
(A) harus berupa vektor, bukan daftar sehinggaassoc
dapat digunakan.sumber