Во Вселенной остались недорешённые СЛАУ ! Помогите решить :)

[Zvezdochet]

Расскажите, пожалуйста, каким методом лучше решать следующую задачу:

Дана (иногда) переопределённая СЛАУ вида Ax+noise=b, где A — матрица коэффициентов, причём количество строк в 1-4 раза больше количества столбцов, x — искомый вектор неизвестных, noise - вектор случайного шума, b — вектор.

Все постоянные, переменные, коэффициенты и неизвестные - являются целыми неотрицательными числами.
Элементы вектора noise неизвестны, целочисленны, случайны и независимы от других переменных; они ограничены сверху - их величина составляет менее 0.01(а часто и 0.001) от элементов вектора b. Их требуется найти, как и вектор x.
В самой матрице А нет нулей, другие величины обычно тоже больше 0.

Необходимо:
найти (или хотя бы оценить) количество возможных решений уравнения;
найти x и noise.

Топикстартер никогда не имел дело с подобными задачами - просьба накидать примерный общий план её решения, на что следует обратить внимание, и конечно набор разных страшных аббревиатур (типа PuLP, МНК, Ridge, CPLEX,...) , которые надо ему гуглить.

Возможно оценить количество решений не полным перебором всего возможного, а как-то проще-быстрее?

[Ende]

Zvezdochet
Пожалуйста, заключайте формулы и обозначения в знаки доллара, чтобы они оформлялись в $\TeX$.

Не Ax+noise=b, а хотя бы $Ax+noise=b$

$Ax+noise=b$

Еще лучше $Ax + \mathrm{noise}=b$

$Ax + \mathrm{noise}=b$

В знаки доллара надо заключать и отдельные обозначения: не "матрица A", но "матрица $A$", и т.д.

[Евгений Машеров]

Первое, что пришло в голову - банальная регрессия. Но, похоже, целочисленность тут принципиально важна.
Тогда задача ЦЛП. Целевая функция - сумма элементов вектора noise (если бы не была оговорена неотрицательность их - то сумма их абсолютных величин).
В принципе, какие-то средства есть в MATLAB, SciPy и NumPy. Но есть и специализированные "решатели".

[Geen]

Давайте посмотрим на "уравнение" $5x+y=13$, к примеру, - сколько у него решений и какие?

[Zvezdochet]

Geen в сообщении #1673807 писал(а):

Давайте посмотрим на "уравнение" $5x+y=13$, к примеру, - сколько у него решений и какие?

Аж две штуки:
${(1;8)}$
${(2;3)}$

Цитата:

Но есть и специализированные "решатели".

Как называются? Что гуглить?
Они умеют считать количество решений?

[Geen]

Zvezdochet в сообщении #1673811 писал(а):

Аж две штуки

И это именно те решения, которые Вам надо найти?

[Zvezdochet]

Да.
(если не обращать внимания на ограничение размера y ),
(решение $(0;13)$ - аналогично)

Причём желательно сначала узнать количество решений, хотя бы примерно.

[Geen]

Zvezdochet в сообщении #1673829 писал(а):

Да.
(если не обращать внимания на ограничение размера y ),
(решение $(0;13)$ - аналогично)

А $(3,-2)$ это решение (а то про noise Вы упомянули только целочисленность)?

[Zvezdochet]

нет, не подходит такое решение.
noise - тоже больше или равно 0

там всё неотрицательно... а матрица - положительна

[Geen]

Ну то есть, на самом деле, у Вас недоопределённая система вида $(A,I)(x,y)^T=b$ и надо найти все её неотрицательные целые решения?

[Zvezdochet]

Ээ-э-э, видимо, да...

[Geen]

Ну что я могу сказать... Как минимум одно решение ($x=0,\ y=b$) есть всегда.

[Zvezdochet]

Я жадина, мне все решения нужны(ну или заранее определённая большая часть от известного количества всех решений)
Тем более, что решение $noise = b$ не подходит из-за ограничения на размер шума(маленький он).

А жирной ссылкой на методы решения недоопределённых СЛАУ - в меня не кинете?

[Geen]

Zvezdochet в сообщении #1673855 писал(а):

А жирной ссылкой на методы решения недоопределённых СЛАУ - в меня не кинете?

Так у Вас целочисленность - это радикально всё усложняет. (Кстати, у Вас не СЛАУ вовсе - с ними-то всё просто было бы - псевдообратная матрица "описывает" все решения.)

Zvezdochet в сообщении #1673855 писал(а):

известного количества всех решений

Как мне кажется, найти количество решений и найти все решения это одна и таже задача.

[B@R5uk]

Евгений Машеров в сообщении #1673806 писал(а):

Тогда задача ЦЛП.

Не, это не задача целочисленного программирования. Она подразумевает оптимизацию некой функции на поверхности некоторого многомерного многогранника, заданного линейными соотношениями и ограничениями на переменные. Здесь же ТСу требуется посчитать "объём" (или "площадь") этого гипергранника: количество точек с целочисленными координатами, которые попадают внутрь него (или на его поверхность — тут я не очень уверен, так как не пытался глубоко вникать).