Недоопределенная система

В математике система линейных уравнений или система полиномиальных уравнений считается недоопределенной, если уравнений меньше, чем неизвестных. (в отличие от переопределенной системы , где уравнений больше, чем неизвестных). Терминологию можно объяснить, используя концепцию подсчета ограничений . Каждое неизвестное можно рассматривать как доступную степень свободы . Каждое уравнение, введенное в систему, можно рассматривать как ограничение , ограничивающее одну степень свободы.

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

Решения недоопределенных систем

Недоопределенная линейная система либо не имеет решения, либо имеет бесконечно много решений.

Например,

${\begin{aligned}x+y+z&=1\\x+y+z&=0\end{aligned}}$

— недоопределенная система, не имеющая решения; Любая система уравнений, не имеющая решения, называется несовместной . С другой стороны, система

${\begin{aligned}x+y+z&=1\\x+y+2z&=3\end{aligned}}$

является непротиворечивым и имеет бесконечное количество решений, таких как ( 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 с вероятностью единица.

системы с другими ограничениями и в

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

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

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

См. также

• Переопределенная система
• Регуляризация (математика)