수학적 배경

A를 실수의 N x N 행렬, N 실수의 ba 벡터 및 xa 벡터 N 알 수없는 실수로하자. 행렬 방정식은 Ax = b입니다.

Jacobi의 방법은 다음과 같습니다. 분해 A = D + R. 여기서 D는 대각선의 행렬이고 R은 나머지 항목입니다.

초기 추측 솔루션 x0을 만드는 경우 개선 된 솔루션은 x1 = inverse (D) * (b-Rx)입니다. 여기서 모든 곱셈은 행렬-벡터 곱셈이고 inverse (D)는 행렬의 역입니다.

문제 사양

• 입력 : 전체 프로그램은 행렬 A, 벡터 b, 초기 추측 x0 및 ‘오류’숫자 e를 입력으로 받아 들여야합니다.
• 출력 : 프로그램은 최신 솔루션이 실제 솔루션에 따라 최대 e만큼 다르도록 최소 반복 횟수를 출력해야합니다. 이것은 절대 크기의 벡터의 각 성분이 최대 e만큼 다르다는 것을 의미합니다. 반복에는 Jacobi의 방법을 사용해야합니다.

데이터 입력 방법은 귀하의 선택입니다 . 명령 행에서 사용자 고유의 구문 일 수 있으며, 원하는대로 파일에서 입력을받을 수 있습니다.

데이터가 출력되는 방법은 선택입니다 . 이 파일은 사람이 읽을 수있는 한 명령 행에 표시되고 ASCII 아트로 작성된 파일에 쓸 수 있습니다.

추가 세부 사항

진정한 솔루션은 제공되지 않습니다. 진정한 솔루션을 계산하는 방법은 전적으로 귀하에게 달려 있습니다. 예를 들어 Cramer의 규칙에 의해 또는 역을 직접 계산하여 해결할 수 있습니다. 중요한 것은 반복과 비교할 수있는 진정한 솔루션이 있다는 것입니다.

정밀도는 문제입니다. 비교를위한 일부 사람들의 ‘정확한 솔루션’은 다를 수 있습니다. 이 코드 골프의 목적을 위해 정확한 솔루션은 소수점 이하 10 자리 여야합니다.

현재 반복 솔루션의 구성 요소 중 하나라도 실제 솔루션의 해당 구성 요소를 e만큼 초과하는 경우 계속 반복해야합니다.

N의 상한은 사용중인 하드웨어 및 프로그램 실행에 소요되는 시간에 따라 다릅니다. 이 코드 골프의 목적 상 최대 N = 50이라고 가정합니다.

전제 조건

프로그램이 호출되면 다음 사항이 항상 유지된다고 가정 할 수 있습니다.

• N> 1 및 N <51, 즉 스칼라 방정식, 항상 행렬 방정식이 제공되지 않습니다.
• 모든 입력은 실수 필드 위에 있으며 결코 복잡하지 않습니다.
• 행렬 A는 항상 방법이 실제 솔루션으로 수렴되도록하기 때문에 항상 위에서 정의한대로 e 이하의 오류를 최소화하기 위해 여러 반복을 찾을 수 있습니다.
• A는 절대 제로 행렬 또는 항등 행렬 이 아니며 , 즉 하나의 솔루션이 있습니다.

테스트 사례

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

진정한 해결책은 (0.586, 1.138)입니다. 첫 번째 반복은 x1 = (5/9, 1)을 제공하며, 적어도 하나의 구성 요소에 의해 실제 솔루션과 0.04 이상 차이가납니다. 또 다른 반복을 수행하면 x2 = (0.555, 1.148)이 (0.586, 1.138)과 0.04 미만으로 다릅니다. 따라서 출력은

2

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

이 경우 실제 솔루션은 (2.2, -0.8)이고 초기 추측 x0에는 이미 e = 1.0보다 작은 오류가 있으므로 0을 출력합니다. 즉, 반복 할 필요가 없을 때마다 간단히 출력합니다.

0

제출 평가

이것은 모든 표준 허점이 허용되지 않는 코드 골프입니다. 가장 짧은 정확한 완전한 프로그램 (또는 기능), 즉 가장 적은 바이트 수가 이깁니다. 그것은되는 낙담 한 함수에 필요한 많은 단계를 마무리하지만, 당신이 원하는 언어를 사용 티카 같은 사용 것들.

답변

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

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

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}

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

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