Решение избыточной СЛАУ с ограничениями

[Andrey_Kireew]

Имеется СЛАУ следующего вида:
$A\cdot x=b$, где $A$ - прямоугольная матрица, $x, b$ векторы
число неизвестных в несколько раз больше числа уравнений, но число значений, которые они могут принимать ограничено числом уравнений (в принципе может быть всего 2 значения), но какая именно переменная какое значение принимает не ясно

являются ли задачи такого типа известными, если да, то сообщите пожалуйста где можно о них почитать
какие подходы к их решению применяются?
возможно ли вообще точно определить принадлежность переменных соответствующим классам?

[Brukvalub]

А просто перебрать все возможные комбинации конечного числа значений и проверить их подстановкой - не вариант?

[Andrey_Kireew]

Brukvalub в сообщении #1092251 писал(а):

А просто перебрать все возможные комбинации конечного числа значений и проверить их подстановкой - не вариант?

это единственное что мне пока пришло в голову, но тут есть сложности:
1 - значения внутри классов в общем случае неизвестны, нужно задаваться начальными приближениями, но для выбранных начальных приближений распределение переменных по классам может отличаться от истинного
2- число вариантов очень велико, так для 100 переменных (а это минимум) число вариантов $2^{100}$, из за этого сплошной перебор на практике неосуществим

у меня есть идея использовать градиентный алгоритм в котором после каждого уточнения выполняется кластеризация переменных на заданное число классов $N$ (равное или меньше числа уравнений), затем все переменные заменяются наиболее вероятным значением в соответствующем кластере
таким образом точно в направлении градиента корректируются значения только $N$ переменных, а остальные только "тянутся за ними"
но бутет ли сходится этот алгоритм к верному решению? и существует ли вообще единственное решение задачи в такой постановке?

[svv]

А что такое классы? Что, для всех переменных, входящих в один класс, значение одно и то же? И известно, какие переменные входят в один класс?

[Andrey_Kireew]

svv в сообщении #1092317 писал(а):

А что такое классы? Что, для всех переменных, входящих в один класс, значение одно и то же? И известно, какие переменные входят в один класс?

классы - это дискретные значения, которые могут принимать переменные
определить распределение переменных по этим классам на основании системы уравнений и есть главная задача
другими словами нужно решить систему для дискретных переменных (не знаю насколько корректным будет это выражение)

[svv]

А, интересно, эти значения — 0 и 1? (Хотя, если это и не так, систему можно привести к такому виду заменой неизвестных.)

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

Смахивает на задачу дискретной оптимизации. В качестве целевой функции - минимизация невязки (вообще говоря, если переменные принимают дискретное множество значений, то точного решения может и не быть, скажем, если все $a_{i,j}$ чётные, переменные принимают значения 0 или 1, но среди $b_i$ затесалось нечётное.
Вообще говоря, NP-полная задача или ещё хуже, но для многих классов таких задач есть практически работающие алгоритмы.

[Andrey_Kireew]

хочу уточнить, что матрица $A$, так же как и переменные $x$, так же как и свободные члены - это не целые, а действительные числа

[Brukvalub]

(Оффтоп)

Andrey_Kireew в сообщении #1092419 писал(а):

хочу уточнить, что матрица $A$, так же как и переменные $x$, так же как и свободные члены - это не целые, а действительные числа

А также, уточняю, что я загадал вам всем рехбус-крохсфорд. Теперь мучайтесь, отгадывайте, а я раз в неделю буду подкидывать крохи информации, чтобы тема не затухала!

[iifat]

Вы нам обещали избыточную СЛАУ, а вместо неё подсовываете нечто мне лично непонятное. Определённо могу сказать одно: ничего общего с СЛАУ это не имеет. Не уверен, что вам тут помогут, если вы таки сформулируете постановку задачи, но могу обещать твёрдо, что без таковой вам не помогут ни здесь, ни где ещё. Внятную, чёткую и полную постановку задачи, свободную от не имеющих к неё отношения терминов.

[Andrey_Kireew]

Вот формулировка задачи:
$A\cdot x=b$, $a_{i,j}\in R$, $x \in Q^m$, $b\in R^n$,
Q - конечное множество действительных чисел, например $Q^4=${1.5, 4.718, 6.121, 23.02},
m - число уравнений,
R - множество действительных чисел,
n - число неизвестных

[Someone]

То есть, число допустимых значений неизвестных равно числу уравнений?

-- Ср янв 20, 2016 12:15:24 --

Ещё вопрос. Вы пишете в заголовке темы об избыточной системе уравнений. Этот термин означает, что в системе уравнений больше, чем неизвестных, то есть, $m>n$. Это действительно так? Или Вы всё-таки имели в виду неопределённую систему уравнений, в которой, наоборот, $m<n$?

P.S. Формулы, содержащие один символ, тоже нужно писать по правилам, то есть, со знаками доллара.

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

Как вариант:
$\min \Sigma_i|\Sigma_j A_{i,j}(\Sigma_k Q_k z_{j,k})-b_i|$
$z_{j,k}\in \{0,1\}$
$\Sigma_k z_{j,k}=1$

[Andrey_Kireew]

Someone в сообщении #1092549 писал(а):

Ещё вопрос. Вы пишете в заголовке темы об избыточной системе уравнений. Этот термин означает, что в системе уравнений больше, чем неизвестных, то есть, $m>n$. Это действительно так? Или Вы всё-таки имели в виду неопределённую систему уравнений, в которой, наоборот, $m<n$?

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

[Brukvalub]

Евгений Машеров, речь-то идет не о критерии , что считать решением, а об эффективном алгоритме отыскания некого подобия решения.