2014 dxdy logo

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

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




 
 Неотрицательность решения системы линейных уравнений
Сообщение22.11.2007, 12:46 
Есть ли теория, которая дает необходимые и достаточные условия для матрицы A и столбца B линейной системы уравнений A X = B, (где X, B - столбцы одной размерности) для выполнения условия X>0 (x_n>0)?

 
 
 
 
Сообщение22.11.2007, 13:43 
Аватара пользователя
Да, теория линейного программирования (линейных неравенств) дает полиномиальный ответ на эту задачу. В ее терминах эта задача формулируется как проверка принадлежности вектора $B$ конусу $C = \{ Ax \mid x\geq 0\}$.

P.S. Вот тут диссер вроде есть с обзором результатов: http://polnolunie.baikal.ru/me/mat_prog.htm

 
 
 
 
Сообщение04.12.2007, 00:57 
Аватара пользователя
Вот, реализовал метод сопряженных направлений решения СЛАУ, описанный в работах по приведенной ссылке.
Вот что получилось:
Имеем СЛАУ с несимметричной неположительно определенной матрицей
$Ax = b$
Задается итерационный процесс:
нулевой шаг: $ \ \ x^0  = A^T b$, $ \ \ \beta _0  = 0$, $ \Rightarrow $ $ \ \ \Delta x^1  = A^T Ax^0  - A^T b$.

$t$-тый шаг: $\beta _t  = \frac{{\left( {A^T Ax^{t - 1}  - A^T b} \right)^T A^T A\Delta x^{t - 1} }}{{\left( {\Delta x^{t - 1} } \right)^T A^T A\Delta x^{t - 1} }}$
$|\ \ \ \ \ \ \ \ \ \ \Delta x^t  = A^T Ax^{t - 1}  - A^T b - \beta _t \Delta x^{t - 1} $
$| \ \ \ \ \ \ \ \ \ \ \alpha _t  =  - \frac{{\left( {A^T Ax^{t - 1}  - A^T b} \right)^T \Delta x^t }}{{\left( {\Delta x^t } \right)^T A^T A\Delta x^t }}$
$| \ \ \ \ \ \ \ \ \ \ \ x^t  = x^{t - 1}  + \alpha _t \Delta x^t $
Я не очень разобрал, этот метод является собственной разработкой автора или это стандартная его реализация? Дело в том, что он приводится наряду со стандартными методами Гаусса и Халецкого, но с другой стороны выбор чисел $\alpha _t $ и $\beta _t $, если я правильно понял, предложен автором.

 
 
 
 
Сообщение10.12.2007, 11:39 
maxal писал(а):
Да, теория линейного программирования (линейных неравенств) дает полиномиальный ответ на эту задачу. В ее терминах эта задача формулируется как проверка принадлежности вектора $B$ конусу $C = \{ Ax \mid x\geq 0\}$.

P.S. Вот тут диссер вроде есть с обзором результатов: http://polnolunie.baikal.ru/me/mat_prog.htm


Спасибо.
А нет ли каких-либо условий (полученных теоретически), которым должны удовлетворять матрицы A и B, чтобы x_i \ge 0 (возможно, достаточно только частных условий)?

 
 
 
 
Сообщение18.12.2007, 01:29 
Аватара пользователя
Вот еще почитайте:
Ермолаев Ю.Б. (2003) Линейные неравенства (препринт)

 
 
 
 
Сообщение25.12.2007, 19:07 
maxal писал(а):

Спасибо. То, что нужно.

 
 
 
 
Сообщение30.12.2007, 04:05 
Аватара пользователя
Андрей1, если Вы окончательно разобрались с этими критериями, можете рассказать, вкратце?
Может в интернете Вы встречали реализацию алгоритма в MATLAB?
Меня интересует еще один критерий для столбца неизвестных: нужно чтобы все решения имели общий делитель, который находится среди них :roll:

 
 
 
 
Сообщение30.12.2007, 13:04 
Alik писал(а):
Андрей1, если Вы окончательно разобрались с этими критериями, можете рассказать, вкратце?


Нет еще не разобрался. Но было и есть подозрение, что в линейном случае эта задача должна быть простой и иметь строгое решение.

Alik писал(а):
Может в интернете Вы встречали реализацию алгоритма в MATLAB?
Меня интересует еще один критерий для столбца неизвестных: нужно чтобы все решения имели общий делитель, который находится среди них :roll:

Mathematica функция NMinimize гарантирует, что минимум будет глобальным для квадратичной и линейной целевой функции и линейных ограничениях.

 
 
 
 
Сообщение29.06.2008, 07:20 
Аватара пользователя
Наткнулся еще на такую статью о решении линейных неравенств в целых числах:

D. Chubarov and A. Voronkov "Basis of Solutions for a System of Linear Inequalities in Integers: Computation and Applications"
http://dx.doi.org/10.1007/11549345_23

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group