Недоопределенная система
В математике система линейных уравнений или система полиномиальных уравнений считается недоопределенной, если уравнений меньше, чем неизвестных [1] (в отличие от переопределенной системы , где уравнений больше, чем неизвестных). Терминологию можно объяснить с помощью концепции подсчета ограничений . Каждое неизвестное можно рассматривать как доступную степень свободы . Каждое уравнение, введенное в систему, можно рассматривать как ограничение , ограничивающее одну степень свободы.
Таким образом, критический случай (между переопределенностью и недоопределенностью) возникает, когда число уравнений и число свободных переменных равны. Для каждой переменной, дающей степень свободы, существует соответствующее ограничение, устраняющее степень свободы. Недоопределенный случай, напротив, возникает, когда система была недоограничена, то есть когда неизвестных больше, чем уравнений.
Решения недоопределенных систем
Недоопределенная линейная система либо не имеет решений, либо имеет бесконечно много решений.
Например,
является недоопределенной системой без какого-либо решения; любая система уравнений, не имеющая решения, называется несовместной . С другой стороны, система
является последовательным и имеет бесконечное множество решений, таких как ( x , y , z ) = (1, −2, 2) , (2, −3, 2) и (3, −4, 2) . Все эти решения можно охарактеризовать, сначала вычитая первое уравнение из второго, чтобы показать, что все решения подчиняются z = 2 ; использование этого в любом уравнении показывает, что возможно любое значение y , при этом x = −1 − y .
Более конкретно, согласно теореме Руше–Капелли , любая система линейных уравнений (недоопределенная или иная) является несовместной, если ранг расширенной матрицы больше ранга матрицы коэффициентов . Если же, с другой стороны, ранги этих двух матриц равны, то система должна иметь по крайней мере одно решение; поскольку в недоопределенной системе этот ранг обязательно меньше числа неизвестных, то действительно существует бесконечность решений, причем общее решение имеет k свободных параметров, где k — разность между числом переменных и рангом.
Существуют алгоритмы, позволяющие определить, имеет ли недоопределенная система решения, и если имеет, выразить все решения как линейные функции k переменных (то же k , что и выше). Самый простой из них — исключение Гаусса . Подробнее см. в разделе Система линейных уравнений .
Однородный случай
Однородная (все постоянные члены которой равны нулю) недоопределенная линейная система всегда имеет нетривиальные решения (помимо тривиального решения, где все неизвестные равны нулю). Таких решений бесконечно много, они образуют векторное пространство , размерность которого равна разности между числом неизвестных и рангом матрицы системы.
Недоопределенные полиномиальные системы
Основное свойство линейных недоопределенных систем — не иметь решений или иметь их бесконечно много — распространяется на системы полиномиальных уравнений следующим образом.
Система полиномиальных уравнений, в которой меньше уравнений, чем неизвестных, называется недоопределенной . Она либо имеет бесконечно много комплексных решений (или, в более общем смысле, решений в алгебраически замкнутом поле ), либо является несовместной. Она несовместна тогда и только тогда, когда 0 = 1 является линейной комбинацией (с полиномиальными коэффициентами) уравнений (это Nullstellensatz Гильберта ). Если недоопределенная система из t уравнений от n переменных ( t < n ) имеет решения, то множество всех комплексных решений является алгебраическим множеством размерности не менее n - t . Если недоопределенная система выбирается случайным образом, размерность равна n - t с вероятностью единица.
Недоопределенные системы с другими ограничениями и в задачах оптимизации
В общем случае недоопределенная система линейных уравнений имеет бесконечное число решений, если таковые имеются. Однако в задачах оптимизации , которые подчиняются ограничениям линейного равенства, только одно из решений имеет значение, а именно то, которое дает наибольшее или наименьшее значение целевой функции .
В некоторых задачах указывается, что одна или несколько переменных ограничены целыми значениями. Целочисленное ограничение приводит к задачам целочисленного программирования и диофантовых уравнений , которые могут иметь только конечное число решений.
Другой тип ограничения, который появляется в теории кодирования , особенно в кодах исправления ошибок и обработке сигналов (например, сжатое зондирование ), состоит в верхней границе числа переменных, которые могут отличаться от нуля. В кодах исправления ошибок эта граница соответствует максимальному числу ошибок, которые могут быть исправлены одновременно.
Смотрите также
Ссылки
- ↑ Бисва Натх Датта (4 февраля 2010 г.). Численная линейная алгебра и приложения, второе издание. СИАМ. стр. 263–. ISBN 978-0-89871-685-6.
