Математический фон

Пусть A будет матрицей действительных чисел размером N на N, вектором из N действительных чисел и вектором из N неизвестных действительных чисел. Матричное уравнение Ax = b.

Метод Якоби заключается в следующем: разложить A = D + R, где D - матрица диагоналей, а R - остальные записи.

если вы сделаете начальное решение для угадывания x0, улучшенным решением будет x1 = обратное (D) * (b - Rx), где все умножения - это умножение матрицы на вектор, а обратное (D) - обратная матрица.

Спецификация проблемы

• Входные данные : Ваша полная программа должна принять в качестве входных данных следующие данные: матрицу A, вектор b, начальное предположение x0 и число «ошибки» e.
• Вывод : программа должна вывести минимальное количество итераций, чтобы последнее решение отличалось истинным решением не более чем на e. Это означает, что каждый компонент векторов по абсолютной величине отличается не более чем на e. Вы должны использовать метод Якоби для итераций.

Как вводятся данные - ваш выбор ; это может быть ваш собственный синтаксис в командной строке, вы можете взять ввод из файла, что бы вы ни выбрали.

Как данные выводятся на ваш выбор ; он может быть записан в файл, отображен в командной строке, записан как ASCII-арт, что угодно, если он доступен для чтения человеком.

Более подробная информация

Вам не дано истинное решение: как вы рассчитываете истинное решение, полностью зависит от вас. Вы можете решить это, например, по правилу Крамера или напрямую вычислив обратное. Важно то, что у вас есть верное решение, которое можно сравнить с итерациями.

Точность является проблемой; «Точные решения» некоторых людей для сравнения могут отличаться. Для целей этого кода гольф точное решение должно быть верно до 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,04 от (0,586, 1,138). Таким образом, выход

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

Оценка представления

Это код гольф, все стандартные лазейки запрещены. Наименьшая правильная полная программа (или функция), т.е. выигрывает наименьшее количество байтов. Не рекомендуется использовать такие вещи, как Mathematica, которые объединяют множество необходимых шагов в одну функцию, но используют любой язык, который вы хотите.

APL (Dyalog) , 78 68 65 49 байтов

Точно тип проблемы APL был создан для.

-3 спасибо Эрику Аутгольферу . -11 благодаря нгн .

Анонимная инфиксная функция. Принимает A как левый аргумент, а x как правый аргумент. Отпечатки приводят к STDOUT в виде вертикальных одинарных символов с использованием 1меток, за которыми следуют 0знаки пунктуации Это означает, что даже 0-результат можно увидеть, если 1перед символом нет 0.

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

Попробуйте онлайн!

Пояснение в порядке чтения

Обратите внимание, что код читается очень похоже на спецификацию проблемы:

{… } На заданных A, b и e, а также на заданном x
 ⎕← выведите
 ∨/ , есть ли какая-либо истина в утверждении, что
 e< e меньше
 |⍵- абсолютного значения x минус
 b⌹ матрица b, деленная
 ⊃A b e на первое из A, b и e (т. е. A),
 ←⍺ которые являются левым аргументом,
 : и, если это так,
  ⍺∇ рекурсивно на
  D+.× D матрица-времена
  b- b минус
  ⍵+.×⍨ x, матрица умножается на
  A- A минус
  ⌹D инверсия D (оставшиеся записи),
  ← где D - это
  A× A, где
  =/¨ равные
  ⍳ координаты для
  ⍴A фигуры А (то есть диагональ)

Пошаговое объяснение

Фактический порядок выполнения справа налево:

{… } Анонимная функция где ⍺A be и ⍵ is x:
 A b c←⍺ разделить левый аргумент на A, b и e,
 ⊃ выбрав первое (A)
 b⌹ матричное деление с b (дает истинное значение x)
 ⍵- различия между текущими значениями x и  допустимыми
 | абсолютными значениями
 e<ошибка меньше чем у тех?
 ∨/ правда для любого? (горит ИЛИ сокращение)
 ⎕← вывести это логическое значение в STDOUT
 : и, если это так:
  ⍴A форма
  ⍳ матрицы этой формы, где каждая ячейка имеет свои собственные координаты
  =/¨ для каждой ячейки, вертикальные и горизонтальные координаты равны? (по диагонали)
  A× умножить ячейки A на
  ⌹ обратный
  D← запас матрицы (извлекает диагональ) в D (для D iagonal)
  ⌹ обратное (обратно к нормальному)
  A- вычитание из
  ⍵+.×⍨ матрицы A умножить (то же самое, что и скалярное произведение, отсюда и то, .что) с x
  b- вычесть то, что из b
  D+.× матричного произведения D, и
  ⍺∇ применить эту функцию с данным A be, а это как новое значение x

Python 3 , 132 байта

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

Попробуйте онлайн!

Использует рекурсивное решение.

R 138 байт

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}

Попробуйте онлайн!

спасибо NikoNyrh за исправление ошибки

Стоит также отметить, что существует пакет R, Rlinsolveкоторый содержит lsolve.jacobiфункцию, возвращающую список с x(решение) и iter(требуемое количество итераций), но я не уверен, что он выполняет правильные вычисления.

Clojure, 212 198 196 байт

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

Реализованный без матричной библиотеки, он повторяет процесс 1e9 раз, чтобы получить правильный ответ. Это не будет работать на слишком плохо обусловленных входах, но должно работать нормально на практике.

Менее поиграв в гольф, я был вполне доволен выражениями Rи D:) Первый ввод %(A) должен быть вектором, а не списком, чтобы его assocможно было использовать.

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