Tło matematyczne

Niech A będzie macierzą N na N liczb rzeczywistych, wektorem ba N liczb rzeczywistych i wektorem xa N nieznanych liczb rzeczywistych. Równanie macierzowe to Ax = b.

Metoda Jacobiego jest następująca: rozkład A = D + R, gdzie D jest macierzą przekątnych, a R jest pozostałymi wpisami.

jeśli stworzysz początkowe rozwiązanie zgadywania x0, ulepszonym rozwiązaniem jest x1 = odwrotność (D) * (b - Rx), gdzie wszystkie mnożenia są mnożeniem macierz-wektor, a odwrotność (D) jest odwrotnością macierzy.

Specyfikacja problemu

• Dane wejściowe : Twój kompletny program powinien przyjąć jako dane wejściowe następujące dane: macierz A, wektor b, początkowe domysły x0 i liczbę „błędów” e.
• Dane wyjściowe : program musi wypisać minimalną liczbę iteracji, tak aby najnowsze rozwiązanie różniło się od rzeczywistego rozwiązania, co najwyżej e. Oznacza to, że każdy komponent wektorów o wartości bezwzględnej różni się co najwyżej e. Do iteracji musisz użyć metody Jacobiego.

Sposób wprowadzania danych jest twoim wyborem ; może to być Twoja własna składnia w wierszu poleceń, możesz pobierać dane wejściowe z pliku, cokolwiek wybierzesz.

Sposób wyprowadzania danych jest twoim wyborem ; może być zapisany do pliku, wyświetlony w wierszu poleceń, zapisany jako sztuka ASCII, cokolwiek, o ile jest czytelny dla człowieka.

Dalsze szczegóły

Nie otrzymujesz prawdziwego rozwiązania: sposób obliczenia prawdziwego rozwiązania zależy wyłącznie od Ciebie. Możesz rozwiązać to na przykład za pomocą reguły Cramera lub bezpośrednio obliczyć odwrotność. Liczy się to, że masz prawdziwe rozwiązanie, aby móc porównać z iteracjami.

Precyzja to problem; „dokładne rozwiązania” niektórych osób mogą się różnić. Do celów tego kodu golfowego dokładne rozwiązanie musi być zgodne z 10 miejscami po przecinku.

Aby być absolutnie jasnym, jeśli choć jeden komponent obecnego rozwiązania iteracyjnego przekracza odpowiadający mu komponent w prawdziwym rozwiązaniu o e, musisz kontynuować iterację.

Górny limit N różni się w zależności od używanego sprzętu i ilości czasu, jaki chcesz poświęcić na uruchomienie programu. Do celów tego kodu golfa załóżmy, że N = 50.

Warunki wstępne

Gdy wywoływany jest twój program, możesz założyć, że przez cały czas obowiązują następujące zasady:

• N> 1 i N <51, tzn. Nigdy nie otrzymasz równania skalarnego, zawsze równania macierzowego.
• Wszystkie dane wejściowe przekraczają pole liczb rzeczywistych i nigdy nie będą skomplikowane.
• Macierz A jest zawsze taka, że ​​metoda jest zbieżna z prawdziwym rozwiązaniem, dzięki czemu zawsze można znaleźć wiele iteracji, aby zminimalizować błąd (jak zdefiniowano powyżej) poniżej lub równy e.
• A nigdy nie jest macierzą zerową lub macierzą tożsamości, tzn. Istnieje jedno rozwiązanie.

Przypadki testowe

A = ((9, -2), (1, 3)), b = (3,4), x0 = (1,1), e = 0.04

Prawdziwe rozwiązanie to (0,586, 1,138). Pierwsza iteracja daje x1 = (5/9, 1), różniąc się o więcej niż 0,04 od prawdziwego rozwiązania, co najmniej jednym składnikiem. Przyjmując kolejną iterację, x2 = (0,555, 1,148), która różni się o mniej niż 0,04 od (0,586, 1,138). Tak więc wynik jest

2

A = ((2, 3), (1, 4)), b = (2, -1), x0 = (2.7, -0.7), e = 1.0

W tym przypadku prawdziwym rozwiązaniem jest (2.2, -0.8), a początkowe przypuszczenie, że x0 ma już błąd mniejszy niż e = 1,0, więc otrzymujemy 0. Oznacza to, że ilekroć nie musisz wykonywać iteracji, po prostu wypisujesz

0

Ocena przedłożenia

To jest golf golfowy, ze wszystkimi standardowymi lukami niniejszym zabronionymi. Najkrótszy poprawny pełny program (lub funkcja), tzn. Najmniejsza liczba bajtów wygrywa. To zniechęca do używania rzeczy jak Mathematica, które owijają się wiele niezbędnych kroków do jednej funkcji, ale korzystają z żadnego języka, który chcesz.

APL (Dyalog) , 78 68 65 49 bajtów

Dokładnie rodzaj problemu, dla którego utworzono APL.

-3 dzięki Erikowi Outgolfer . -11 dzięki ngn .

Anonimowa funkcja poprawki. Bierze A jako lewy argument, a x jako prawy argument. Drukuje wynik do STDOUT jako pionowy unarny, używając 1jako znaczników, a następnie 0interpunkcji. Oznacza to, że można zobaczyć nawet wynik 0, nie ma 1s przed 0.

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

Wypróbuj online!

Objaśnienie w kolejności czytania

Zwróć uwagę, jak kod odczytuje bardzo podobnie do specyfikacji problemu:

{… } Na danym A, b i e oraz na danym x
 ⎕← wypisz,
 ∨/ czy w stwierdzeniu jest jakaś prawda, że
 e< e jest mniejsze niż
 |⍵- wartość bezwzględna x minus
 b⌹ b macierzy podzielona przez
 ⊃A b e pierwszą z A, b, i e (tj. A),
 ←⍺ które są lewym argumentem,
 : a jeśli tak,
  ⍺∇ powtórz na
  D+.× macierz D razy
  b- b minus
  ⍵+.×⍨ x, macierz pomnożona przez
  A- A minus
  ⌹D odwrotność D (pozostałe wpisy),
  ← gdzie D jest
  A× A, gdzie
  =/¨ są równe
  ⍳ współrzędne
  ⍴A kształtu z A (tj. przekątna)

Wyjaśnienie krok po kroku

Rzeczywista kolejność wykonywania od prawej do lewej:

{… } Anonimowa funkcja, gdzie ⍺A jest, a ⍵ jest x:
 A b c←⍺ podziel lewy argument na A, b i e
 ⊃ wybierz pierwszy (A)
 b⌹ podział macierzy za pomocą b (daje prawdziwą wartość x)
 ⍵- różnic między bieżącymi wartościami x a tymi
 | wartościami bezwzględnymi
 e< dopuszczalnymi błąd mniejszy niż te?
 ∨/ prawda dla każdego? (podświetlona LUB redukcja)
 ⎕← wydrukuj wartość logiczną na STDOUT,
 : a jeśli tak:
  ⍴A kształt
  ⍳ Macierz tego kształtu, w którym każda komórka ma własne współrzędne
  =/¨ dla każdej komórki, czy współrzędne pionowe i poziome są równe? (przekątna)
  A× pomnóż komórki A przez
  ⌹ macierz odwrotną macierzy (wyciąga przekątną)
  D← w D (dla przekątnej D )
  ⌹ odwrotny (powrót do normalnego)
  A- odejmij od
  ⍵+.×⍨ macierzy A pomnóż (to samo co iloczyn iloczynu, stąd .), że przy x
  b- odejmij to od
  D+.× iloczynu b macierzy D i
  ⍺∇ zastosuj tę funkcję dla danego A be i że jako nową wartość x

Python 3 , 132 bajty

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

Wypróbuj online!

Używa rozwiązania rekurencyjnego.

R , 138 bajtów

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}

Wypróbuj online!

dzięki NikoNyrh za naprawienie błędu

Warto również zauważyć, że istnieje pakiet R, Rlinsolvektóry zawiera lsolve.jacobifunkcję, zwracającą listę z x(rozwiązaniem) i iter(wymaganą liczbą iteracji), ale nie jestem pewien, czy wykonuje prawidłowe obliczenia.

Clojure, 212 198 196 bajtów

#(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)))

Zaimplementowany bez biblioteki macierzy, iteruje proces 1e9 razy, aby uzyskać poprawną odpowiedź. Nie działałoby to na zbyt źle uwarunkowanych danych wejściowych, ale powinno działać dobrze w praktyce.

Mniej grałem w golfa, byłem całkiem zadowolony z wyrażeń Ri D:) Pierwszym wejściem %(A) musi być wektor, a nie lista, aby assocmożna go było użyć.

(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)))