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

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

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

• 1 Решения недоопределенных систем
• 2 Однородный случай
• 3 Недоопределенные полиномиальные системы
• 4 Недоопределенные системы с другими ограничениями и в задачах оптимизации
• 5 См. Также
• 6 Ссылки

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

Например,

$x\; +\; y\; +\; z\; =\; 1\; x\; +\; y\; +\; z\; =\; 0\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; x\; +\; y\; +\; z\; =\; 1\; \backslash \backslash \; x\; +\; y\; +\; z\; =\; 0\; \backslash \; end\; \{align\}\}\}$

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

$x\; +\; y\; +\; z\; =\; 1\; x\; +\; y\; +\; 2\; z\; =\; 3\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; x\; +\; y\; +\; z\; =\; 1\; \backslash \backslash \; x\; +\; y\; +\; 2z\; =\; 3\; \backslash \; end\; \{align\}\}\}$

непротиворечиво и имеет бесконечное количество решений, таких как (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) has solutions, then the set of all complex solutions is an алгебраический набор из размерности, по крайней мере, n - t. Если недоопределенная система выбрана случайным образом, размерность равна n - t с вероятностью единица.

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

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

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

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