Недоопределенная система уравнений Определение

Недоопределенная линейная система либо не имеет решений, либо имеет бесконечно много решений. Например, x + y + z = 1 и x + y + z = 0 — недоопределенная система без какого-либо решения; любая система уравнений, не имеющая решения, называется несовместной. С другой стороны, система x + y + z = 1 и x + y + 2z = 3 непротиворечива и имеет бесконечное множество решений, таких как (x, y, z) = (1, −2, 2), (2, −3, 2) и (3, −4, 2). Все эти решения можно охарактеризовать, сначала вычитая первое уравнение из второго, чтобы показать, что все решения подчиняются z = 2; использование этого в любом уравнении показывает, что возможно любое значение y с x = –1 – y.

В частности, согласно теореме Руше–Капелли, любая система линейных уравнений (недоопределенная или нет) несовместима, если ранг расширенной матрицы больше, чем ранг матрица коэффициентов. Если, с другой стороны, ранги этих двух матриц равны, система должна иметь по крайней мере одно решение; поскольку в недоопределенной системе этот ранг обязательно меньше числа неизвестных, действительно существует бесконечное множество решений, причем общее решение имеет k свободных параметров, где k - разница между числом переменных и рангом.

There are algorithms to decide whether an underdetermined system has solutions, and if it has any, to express all solutions as linear functions of k of the variables (same k as above). The simplest one is Gaussian elimination. See System of linear equations for more details.

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

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

Система полиномиальных уравнений, в которой уравнений меньше, чем неизвестных, называется недоопределенной. Оно либо имеет бесконечно много комплексных решений (или, в более общем случае, решений в алгебраически замкнутом поле), либо несовместно. Это несовместимо тогда и только тогда, когда 0 = 1 является линейной комбинацией (с полиномиальными коэффициентами) уравнений (это гильбертовский Nullstellensatz). Если недоопределенная система t уравнений от n переменных (t < n) имеет решения, то множество всех комплексных решений является алгебраическим множеством размерности не менее n - t. При случайном выборе недоопределенной системы размерность равна n - t с вероятностью единица.

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

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

• Алгоритм

“Underdetermined System.” Wikipedia, Wikimedia Foundation, 16 June 2019, en.wikipedia.org/wiki/Underdetermined_system.