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

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

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

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

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

Например,

${displaystyle {egin{aligned}x+y+z&=1x+y+z&=0end{aligned}}}$

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

${displaystyle {egin{aligned}x+y+z&=1x+y+2z&=3end{aligned}}}$

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

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

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

Однородный корпус

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

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

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

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

Недоопределенные системы с другими ограничениями и в задачах оптимизации

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

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

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

Смотрите также

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

Рекомендации

1. Бисва Натх Датта (4 февраля 2010 г.). Численная линейная алгебра и приложения, второе издание. СИАМ. С. 263–. ISBN  978-0-89871-685-6.