2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Вырожденная система линейных уравнений. Как решить?
Сообщение01.06.2016, 19:38 


30/06/14
47
Есть система линейных уравнений, число переменных до 50
Значения переменных ограничены, и могут быть целыми числами от 0 до 3
Коэффициенты могут быть либо 0, либо 1
Известно, что система может быть вырожденной.
Также имеется дополнительное условие: Нам известно количество переменных принимающих каждое из допустимых значений (т.е. 0..3).
Разумеется, что сама система может иметь очень много решений. Но нужно найти те переменные, которые принимают однозначные значения, т.е. которые во всех решениях системы принимают одно и то же значение, или убедиться, что таких переменных нет. Также по возможности проверить систему на совместимость.

Например в системе:
$x_1+x_2+x_3+x_4=5$
$x_1+x_2=5$

Понятно что $x_3=0$ и $x_4=0$

Что можно применить для решения таких систем? Метод перебора не подходит, из-за огромного кол-ва вариантов.
Какие есть для подобных задач численные методы/алгоритмы? Или что вы можете посоветовать?

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение01.06.2016, 20:29 


04/07/15
137
Как можно понять, коэффициенты Вам известны, чем тогда плох тот же метод Гаусса? Что касается появления свободных переменных в процессе решения, то перебор вариантов решения несложно программируется, потому что у Вас будет четверичная система счисления, и количество решений будет конечным. То есть, Вы можете сначала оценить количество всех решений сверху, исходя из количества разрядов, а потом из него выбрать подходящие. Не кажется сложным.

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение01.06.2016, 21:29 


30/06/14
47
EXE в сообщении #1128067 писал(а):
Как можно понять, коэффициенты Вам известны, чем тогда плох тот же метод Гаусса?

Коэффициенты-то известны, но среди них очень много нулевых. И количество уравнений часто бывает что составляет 20-30% от количества переменных.
А перебор вариантов... допустим у меня 40 переменных, по 2 бита на каждую, итого 80 битов. Перебирать такое нереально. Ибо это такое громадное число вариантов (как минимум с 24 нулями), и еще каждый нужно проверить чтобы он не противоречил системе.

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение01.06.2016, 21:44 


04/07/15
137
Вы говорите о количестве свободных переменных?
Что Вас смущает в большом количестве нулевых коэффициентов?
Обоснуйте, пожалуйста, чётче проблему с битами и с 24 нулями.
И каким образом из моего сообщения можно сделать вывод о предложении перебора?

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение02.06.2016, 08:47 
Аватара пользователя


31/05/15
20

(Оффтоп)

glukmaker в сообщении #1128046 писал(а):
Например в системе:
$x_1+x_2+x_3+x_4=5$
$x_1+x_2=5$

Понятно что $x_3=0$ и $x_4=0$



Вообще-то, понятно, что $x_3=-x_4$.

А на самом деле все совсем просто.
Учебник по линейной алгебре удовлетворит ваши потребности на 100%. Оттуда вы узнаете как выглядит общее решение для любой системы линейных уравнений, на что оно натягивается и кучу других интересных вещей.


Также, я прикинул, что любая реализация библиотек aka матлаба, которая сейчас есть почти в любом языке, сведёт вашу работу к минимуму.

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение02.06.2016, 09:01 
Заслуженный участник
Аватара пользователя


15/10/08
11536

(Оффтоп)

Octagon в сообщении #1128168 писал(а):
Вообще-то, понятно, что $x_3=-x_4$.

glukmaker в сообщении #1128046 писал(а):
Значения переменных ограничены, и могут быть целыми числами от 0 до 3

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение02.06.2016, 14:11 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Совсем без перебора не получится, т.к. вопрос о существовании гамильтонова цикла в графе с $v$ и $e$ ребрами сводится к такой системе с $v$ уравнениями и $e$ неизвестными: неизвестные - ребра, $0$, если соответствующее ребро не берем, $1$, если берем. Уравнения - сумма переменных, соответствующих ребрам, инцидентным каждой вершине, равна $2$. Ограничение на количество - $v$ единиц, $e - v$ нулей.

edit: бред (см. ниже)

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение02.06.2016, 14:31 
Заслуженный участник


26/10/14
380
Новосибирск
mihaild в сообщении #1128230 писал(а):
Уравнения - сумма переменных, соответствующих ребрам, инцидентным каждой вершине, равна $2$.

С такими уравнениями решение системы не обязано быть гамильтоновым циклом.

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение03.06.2016, 11:33 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
А если так?
Взяли граф, хотим найти независимое множество из $n$ вершин. Взяли по переменной $x_i$ для каждой вершины (будет $0$, если вершина не входит в множество, и $1$, если входит), $y_j$ для каждого ребра (будет $0$, если одна из инцидентных ребру вершин входи в множество, $1$, если не входит).
Для каждого ребра $k$, соединяющего вершины $i$ и $j$ пишем $x_i + x_j + y_k = 1$. Пишем уравнение $\sum\limits_i x_i = n$. Далее перебираем все варианты, сколько нулей среди значений переменных (число вариантов линейно по размеру графа).
Делаем независимое множество из решения: берем все вершины, соответствующие равным единице $x$. Оно независимо, т.к. если бы вершины $i$ и $j$ из него соединялись ребром $k$, то было бы $x_i + x_j + y_k \geqslant 2$.
Делаем решение из независимого множества: говорим, что у нас число единиц равно $n$ плюс число ребер, не соединенных ни с одной вершиной из независимого множества. Если $i$-я вершина принадлежит множеству, берем $x_i = 1$, иначе $x_i = 0$. Для ребер, не соединенных ни с одной вершиной множества, берем $y = 1$, для остальных $y = 0$. Все уравнения выполняются, ограничение на количество тоже.

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение03.06.2016, 18:38 
Заслуженный участник


26/10/14
380
Новосибирск
mihaild
Теперь очень даже правдоподобно.
Да, сложная задача получается.

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение03.06.2016, 19:18 
Заслуженный участник


25/02/11
1786
glukmaker в сообщении #1128046 писал(а):
Или что вы можете посоветовать?

Системы компьютерной алгебры. Можно попробовать впрямую решать. А еще они линейные целочисленные системы $\mod\ 4$ умеют решать эффективно. Давая ответ в параметрическом виде, типа $(c_1+2 c_2,0,1,c_2,\dots)$. Переменные, на чьих местах нет параметров, и принимают только одно значение. Правда, потом придется выяснять, нет ли других таких переменных, поскольку решений исходной системы может быть меньше. И вообще, является ли какое-либо из полученных решений решением исходной системы. Если решений не очень много (скажем, порядка $10^7$), то проверить вполне реально.

 Профиль  
                  
 
 Re: Вырожденная система линейных уравнений. Как решить?
Сообщение03.06.2016, 19:53 


17/10/08

1313
Для данного варианта потребуется эффективный решатель целочисленных линейных задач (ЦЛЗ). Из бесплатных или условно бесплатных могу посоветовать CBC и SCIP.

Алгоритм следующий.
1. Решить исходную задачу ЦЛЗ.
2. Если решений нет, то конец.
3. Если решение есть, то обозначим допустимое решение через $y_j$
4. Для каждой переменной $x_j$ рассмотреть два варианта, когда $x_j>y_j$ и $x_j<y_j$.
5. Для каждого варианта решить задачу ЦЛЗ. Если есть хотя бы одно решение, то $x_j$ неоднозначна. Если нет, - то однозначна.

Описанный алгоритм может быть усовершенствован. Например,
* найденные однозначные переменные сразу фиксировать.
* если в любом найденном допустимом решении п.5 некоторая переменная отличается от решения п.2, то такая переменная неоднозначна и, если она не рассматривалась в п. 4 и п. 5, то и не нужно рассматривать.

В принципе, задачи с 50-ю целочисленными переменными должны решаться. Если, конечно, это не специально подобранных пример.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group