Memecahkan persamaan matriks dengan metode Jacobi (Revisi)

11

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.

pengguna1997744
sumber
2
Anda benar-benar harus menunggu untuk mendapatkan lebih banyak umpan balik untuk itu, terutama mengingat pos yang ditutup baru-baru ini. Tantangan PPCG biasanya memiliki struktur yang sama dalam spesifikasi, yang biasanya membuatnya mudah dipahami, dan bukannya melelahkan dan membingungkan. Cobalah untuk melihat beberapa tantangan yang cukup masuk akal dan meniru formatnya.
Uriel
@Uriel Saya menyadari hal ini, tapi saya merasa saya sudah teliti dalam spesifikasi saya, dan format sementara tidak pas dengan sebagian besar pertanyaan, dapat dibaca secara linear, dan membimbing pembaca sesuai. Formatnya juga harus mengingat isi masalah itu sendiri.
user1997744
3
" Program lengkap yang benar terpendek " sepertinya Anda hanya mengizinkan program dan bukan fungsi. Saya akan menambahkan "/ function".
Adám
2
Pemformatan +1 membuat atau menghancurkan kemampuan otak saya untuk berkonsentrasi pada pertanyaan
Stephen
1
@ user1997744 Yup, masuk akal. Saya percaya defaultnya adalah bahwa kode lain, seperti fungsi lain atau impor python, diizinkan, tetapi juga termasuk dalam bytecount.
Stephen

Jawaban:

4

APL (Dyalog) , 78 68 65 49 byte

Jenis 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 1sebagai tanda penghitungan, diikuti oleh 0sebagai tanda baca. Ini berarti bahwa bahkan hasil 0 dapat dilihat, tidak ada 1sebelum 0.

{⎕←∨/e<|⍵-b⌹⊃A b e←⍺:⍺∇D+.×b-⍵+.×⍨A-⌹D←⌹A×=/¨⍳⍴A}

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 bahwa
e< e lebih kecil dari
|⍵- nilai absolut x minus
b⌹ 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
  ⍺∇ pada
  D+.× D-kali matriks
  b- minus b
  ⍵+.×⍨ , x, matriks dikalikan dengan
  A- A dikurangi
  ⌹D kebalikan dari D (entri yang tersisa) di
   mana D adalah
   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
 pilih
b⌹ divisi matriks pertama (A) dengan b (memberikan nilai sebenarnya dari x)
⍵- perbedaan antara nilai saat ini dari x dan
| nilai absolut yang
e< 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)
   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 x
  b- kurangi dari
  D+.× produk matriks b dari D dan yang
  ⍺∇ menerapkan fungsi ini dengan diberi A dan sebagai nilai baru x

Adm
sumber
Output harus berupa jumlah iterasi yang diperlukan untuk akurasi e.
Zgarb
-1: Ini bukan solusi. Anda perlu x0 karena seluruh poinnya adalah untuk mengetahui berapa banyak langkah yang diperlukan untuk mendapatkan akurasi yang diinginkan dari titik awal tertentu.
user1997744
@ user1997744 Ah, saya salah mengerti masalahnya. Maaf.
Adám
@ user1997744 Lebih baik?
Adám
1
@ user1997744 Bukan operasi aritmatika, hanya kemampuan membaca unary , di mana memang 0 bukan apa-apa .
Adám
1

Python 3 , 132 byte

f=lambda A,b,x,e:e<l.norm(x-dot(l.inv(A),b))and 1+f(A,b,dot(l.inv(d(d(A))),b-dot(A-d(d(A)),x)),e)
from numpy import*
l=linalg
d=diag

Cobalah online!

Menggunakan solusi rekursif.

notjagan
sumber
@ Adam saya tidak yakin saya cukup mengerti. Saya menafsirkannya sebagai ftidak memiliki nama di dalam blok kode, yang sekarang saya perbaiki; Namun, jika ini adalah masalah yang sama sekali berbeda, itu mungkin masih menjadi masalah.
notjagan
@ Adám Jawaban itu sepertinya menguatkan apa yang saya miliki saat ini; itu adalah fungsi dengan kode pembantu yang mampu bekerja sebagai unit setelah definisinya.
notjagan
Ah, baiklah. Lupakan saja. Saya tidak tahu Python, jadi saya hanya ingin tahu. Kerja bagus!
Adám
Bukankah kriteria berhenti "Ini berarti setiap komponen vektor dalam besaran absolut berbeda paling banyak"? Pada dasarnya max-norm, bukan L2-norm.
NikoNyrh
@NikoNyrh Diperbaiki.
notjagan
1

R , 138 byte

function(A,x,b,e){R=A-(D=diag(diag(A)))
g=solve(A,b)
if(norm(t(x-g),"M")<e)T=0
while(norm((y=solve(D)%*%(b-R%*%x))-g,"M")>e){T=T+1;x=y}
T}

Cobalah online!

terima kasih kepada NikoNyrh untuk memperbaiki bug

Perlu juga dicatat bahwa ada paket R, Rlinsolveyang berisi lsolve.jacobifungsi, mengembalikan daftar dengan x(solusi) dan iter(jumlah iterasi yang diperlukan), tapi saya tidak yakin apakah itu melakukan perhitungan yang benar.

Giuseppe
sumber
Bukankah kriteria berhenti "Ini berarti setiap komponen vektor dalam besaran absolut berbeda paling banyak"? Pada dasarnya max-norm, bukan L2-norm.
NikoNyrh
@NikoNyrh kamu benar! untungnya, normfungsi ini menyediakan bagi saya juga tanpa byte tambahan.
Giuseppe
1

Clojure, 212 198 196 byte

#(let[E(range)I(iterate(fn[X](map(fn[r b d](/(- b(apply +(map * r X)))d))(map assoc % E(repeat 0))%2(map nth % E)))%3)](count(for[x I :while(not-every?(fn[e](<(- %4)e %4))(map -(nth I 1e9)x))]x)))

Diimplementasikan 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 Rdan D:) Input pertama %(A) harus berupa vektor, bukan daftar sehingga assocdapat digunakan.

(def f #(let[R(map assoc %(range)(repeat 0))
             D(map nth %(range))
             I(iterate(fn[X](map(fn[r x b d](/(- b(apply +(map * r x)))d))R(repeat X)%2 D))%3)]
          (->> I
               (take-while (fn[x](not-every?(fn[e](<(- %4)e %4))(map -(nth I 1e9)x))))
               count)))
NikoNyrh
sumber