Сверхдетерминированная система - Overdetermined system

В математика, а система уравнений Считается сверхопределенный если уравнений больше, чем неизвестных.^[1]^[2]^{[нужна цитата ]} Переназначенная система почти всегда непоследовательный (не имеет решения) при построении со случайными коэффициентами. Однако переопределенная система будет иметь решения в некоторых случаях, например, если какое-то уравнение встречается в системе несколько раз или если некоторые уравнения линейные комбинации из других.

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

Системы уравнений

Пример в двух измерениях

# 1 Система трех линейно независимых уравнений, трех строк, без решений

# 2 Система трех линейно независимых уравнений, три строки (две параллельно ), решений нет

# 3 Система трех линейно независимых уравнений, трех линий (все параллельны), без решений

# 4 Система трех уравнений (одно уравнение линейно зависит от других), трех строк (две совпадают), одно решение

# 5 Система трех уравнений (одно уравнение линейно зависит от других), трех строк, одного решения

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

Рассмотрим систему 3 уравнения и 2 неизвестных ( $Икс$ и $Y$ ), которая переопределена, потому что 3> 2, и которая соответствует Диаграмме # 1:

{Displaystyle {начало {выровнено} Y & = - 2X-1 Y & = 3X-2 Y & = X + 1.end {выровнено}}}

Существует одно решение для каждой пары линейных уравнений: для первого и второго уравнений (0,2, −1,4), для первого и третьего (−2/3, 1/3), а для второго и третьего (1,5, 2,5 ). Однако не существует решения, удовлетворяющего всем трем одновременно. На диаграммах № 2 и 3 показаны другие конфигурации, которые несовместимы, поскольку нет точки на всех линиях. Системы этой разновидности считаются непоследовательный.

Единственные случаи, когда переопределенная система действительно имеет решение, продемонстрированы на диаграммах №4, 5 и 6. Эти исключения могут возникать только тогда, когда переопределенная система содержит достаточно линейно зависимый уравнения, что количество независимых уравнений не превышает количества неизвестных. Линейная зависимость означает, что некоторые уравнения могут быть получены путем линейного комбинирования других уравнений. Например, Y = Икс + 1 и 2Y = 2Икс + 2 линейно зависимые уравнения, потому что второе можно получить, взяв дважды первое.

Матричная форма

Любую систему линейных уравнений можно записать в виде матрица Предыдущую систему уравнений (на схеме 1) можно записать следующим образом:

{displaystyle {egin {bmatrix} 2 & 1 -3 & 1 -1 & 1 end {bmatrix}} {egin {bmatrix} X Y end {bmatrix}} = {egin {bmatrix} -1 -2 1 end { bmatrix}}}

Обратите внимание, что строки матрица коэффициентов (соответствующих уравнениям) больше столбцов (соответствующих неизвестным), что означает, что система переопределена. В классифицировать этой матрицы равно 2, что соответствует количеству зависимые переменные в системе.^[3] Линейная система непротиворечива если и только если матрица коэффициентов имеет тот же ранг, что и ее расширенная матрица (матрица коэффициентов с добавленным дополнительным столбцом, который является вектор-столбцом констант). Расширенная матрица имеет ранг 3, поэтому система несовместима. В ничтожность равно 0, что означает, что пустое пространство содержит только нулевой вектор и поэтому не имеет основа.

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

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

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

Рассмотрим систему линейных уравнений: L_я = 0 для 1 ≤ я ≤ M, а переменные Икс₁, Икс₂, ..., Икс_N, где каждый L_я представляет собой взвешенную сумму Икс_яс. потом Икс₁ = Икс₂ = ... = Икс_N = 0 всегда является решением. Когда M < N система недоопределенный и всегда есть бесконечное множество дальнейших решений. На самом деле размерность пространства решений всегда не меньше N − M.

За M ≥ N, не может быть никакого решения, кроме того, что все значения равны нулю. Будет бесконечное множество других решений только тогда, когда система уравнений имеет достаточно зависимостей (линейно зависимых уравнений), чтобы количество независимых уравнений не превышало N - 1. Но с M ≥ N количество независимых уравнений может достигать N, и в этом случае единственное решение - тривиальное.

Неоднородный корпус

В системах линейных уравнений L_я=c_я для 1 ≤ я ≤ M, в переменных Икс₁, Икс₂, ..., Икс_N уравнения иногда линейно зависимы; на самом деле количество линейно независимых уравнений не может превышать N+1. Возможны следующие случаи переопределенной системы с N неизвестные и M уравнения (M>N).

M = N+1 и все M уравнений линейно независимый. Этот случай не дает решения. Пример: Икс = 1, Икс = 2.
M > N но только K уравнения (K < M и K ≤ N+1) линейно независимы. Существуют три возможных подслучая:
- K = N+1. Этот случай не дает решений. Пример: 2Икс = 2, Икс = 1, Икс = 2.
- K = N. Этот случай дает либо единственное решение, либо отсутствие решения, последнее возникает, когда вектор коэффициентов одного уравнения может быть воспроизведен взвешенной суммой векторов коэффициентов других уравнений, но эта взвешенная сумма, примененная к постоянным членам других уравнений, дает не копировать постоянный член одного уравнения. Пример с одним решением: 2Икс = 2, Икс = 1. Пример без решения: 2Икс + 2у = 2, Икс + у = 1, Икс + у = 3.
- K < N. В этом случае либо бесконечно много решений, либо нет решения, последнее происходит так же, как и в предыдущем подслучае. Пример с бесконечным множеством решений: 3Икс + 3у = 3, 2Икс + 2у = 2, Икс + у = 1. Пример без решения: 3Икс + 3у + 3z = 3, 2Икс + 2у + 2z = 2, Икс + у + z = 1, Икс + у + z = 4.

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

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

Точные решения

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

Примерные решения

Методика обыкновенный метод наименьших квадратов может использоваться для поиска приближенного решения переопределенных систем. Для системы ${displaystyle Ax = b,}$ формула наименьших квадратов получается из задачи

{displaystyle min _ {x} Vert Ax-bVert,}

решение которого можно записать с нормальные уравнения,^[4]

{displaystyle x = (A ^ {mathrm {T}} A) ^ {- 1} A ^ {mathrm {T}} b,}

куда ${displaystyle {mathrm {T}}}$ указывает на матрица транспонировать, при условии ${displaystyle (A ^ {mathrm {T}} A) ^ {- 1}}$ существует (то есть при условии А имеет полный ранг столбца ). С помощью этой формулы приближенное решение находится, когда точного решения не существует, и дает точное решение, когда оно существует. Однако для достижения хорошей числовой точности используйте QR-факторизация из А для решения задачи наименьших квадратов является предпочтительным.^[5]

В общем использовании

Эту концепцию также можно применить к более общим системам уравнений, таким как системы полиномиальных уравнений или же уравнения в частных производных. В случае систем полиномиальных уравнений может случиться так, что переопределенная система имеет решение, но ни одно уравнение не является следствием других, и что при удалении любого уравнения новая система имеет больше решений. Например, ${displaystyle (x-1) (x-2) = 0, (x-1) (x-3) = 0}$ имеет единственное решение ${displaystyle x = 1,}$ но каждое уравнение само по себе имеет два решения.