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

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

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

Переопределенные линейные системы уравнений

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

Рассмотрим систему из трех уравнений и двух неизвестных ( $X$ и $Y$ ), которая переопределена, поскольку 3 > 2, и соответствует диаграмме №1: ${\begin{aligned}Y&=-2X-1\\Y&=3X-2\\Y&=X+1.\end{aligned}}$

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

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

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

Любую систему линейных уравнений можно записать в виде матричного уравнения.Предыдущую систему уравнений (на схеме №1) можно записать следующим образом: ${\begin{bmatrix}2&1\\-3&1\\-1&1\\\end{bmatrix}}{\begin{bmatrix}X\\Y\end{bmatrix}}={\begin{bmatrix}-1\\-2\\1\end{bmatrix}}$ Обратите внимание, что число строк матрицы коэффициентов (соответствующих уравнениям) превышает количество столбцов (соответствующих неизвестным), а это означает, что система переопределена. Ранг этой матрицы равен 2, что соответствует количеству зависимых переменных в системе. ^[2] Линейная система непротиворечива тогда и только тогда, когда матрица коэффициентов имеет тот же ранг, что и ее расширенная матрица (матрица коэффициентов с добавленным дополнительным столбцом, причем этот столбец является вектор-столбцом констант). Расширенная матрица имеет ранг 3, поэтому система несовместна. Нулевое значение равно 0, что означает, что нулевое пространство содержит только нулевой вектор и, следовательно, не имеет базиса .

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

Однородный случай

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

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

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

Неоднородный случай

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

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

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

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

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

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

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

Метод обычных наименьших квадратов можно использовать для нахождения приближенного решения переопределенных систем. Для системы $A\mathbf {x} =\mathbf {b} ,$ формула наименьших квадратов получается из задачи $\min _{\mathbf {x} }\lVert A\mathbf {x} -\mathbf {b} \rVert ,$ решение которого можно записать с помощью нормальных уравнений , ^[3] $\mathbf {x} =\left(A^{\mathsf {T}}A\right)^{-1}A^{\mathsf {T}}\mathbf {b} ,$ где ${\mathsf {T}}$ указывает на транспонирование матрицы , при условии $\left(A^{\mathsf {T}}A\right)^{-1}$ существует (то есть при условии, что A имеет полный ранг столбца ). С помощью этой формулы находится приближенное решение, когда точного решения не существует, и дает точное решение, когда оно существует. Однако для достижения хорошей числовой точности использовать QR-факторизацию A для решения задачи наименьших квадратов. предпочтительнее ^[4]

Использование QR-факторизации

QR -разложение (высокой) матрицы $A$ — представление матрицы в виде произведения,

A=QR,

где $Q$ представляет собой (высокую) полуортонормированную матрицу, охватывающую диапазон матрицы $A$ , и где $R$ представляет собой (маленькую) квадратную право-треугольную матрицу.

Решение проблемы минимизации нормы $\|Ax-b\|^{2}$ затем дается как

x=R^{-1}Q^{T}b,

где на практике вместо расчета $R^{-1}$ нужно выполнить обратную подстановку в правотреугольной системе

Rx=Q^{T}b.

Использование разложения по сингулярным значениям

Разложение по сингулярным значениям (SVD) (высокой) матрицы $A$ — представление матрицы в виде произведения,

A=USV^{T},

где $U$ представляет собой (высокую) полуортонормированную матрицу, охватывающую диапазон матрицы $A$ , $S$ представляет собой (маленькую) квадратную диагональную матрицу с неотрицательными сингулярными значениями вдоль диагонали, и где $V$ представляет собой (маленькую) квадратную ортонормированную матрицу.

Решение проблемы минимизации нормы $\|Ax-b\|^{2}$ затем дается как

x=VS^{-1}U^{T}b.

Переопределенные нелинейные системы уравнений

В конечномерных пространствах систему уравнений можно записать или представить в виде

$\left\{{\begin{array}{ccc}f_{1}(x_{1},\ldots ,x_{n})&=&0\\\vdots &\vdots &\vdots \\f_{m}(x_{1},\ldots ,x_{n})&=&0\end{array}}\right.$

или в форме $\mathbf {f} (\mathbf {x} )=\mathbf {0}$ с

$\mathbf {f} (\mathbf {x} )=\left[{\begin{array}{c}f_{1}(x_{1},\ldots ,x_{n})\\\vdots \\f_{m}(x_{1},\ldots ,x_{n})\end{array}}\right]\;\;\;{\mbox{and}}\;\;\;\mathbf {0} =\left[{\begin{array}{c}0\\\vdots \\0\end{array}}\right]$

где $\mathbf {x} =(x_{1},\ldots ,x_{n})$ это точка в $R^{n}$ или $C^{n}$ и $f_{1},\ldots ,f_{m}$ являются действительными или сложными функциями. Система является переопределенной, если $m>n$ . Напротив, система является недоопределенной, если $m<n$ . ^[5]^[6]

В качестве эффективного метода решения переопределенных систем итерация Гаусса-Ньютона локально квадратично сходится к решениям, при которых матрицы Якобиана $\mathbf {f} (\mathbf {x} )$ являются инъективными.

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

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

См. также

Ссылки

^ Нежный, Джеймс Э. (6 декабря 2012 г.). Численная линейная алгебра для приложений в статистике . Спрингер. ISBN 9781461206231 .
^ Стивенс, Скотт А. «Системный анализ – ранг и недействительность» (PDF) . Математика 220 — Раздаточные материалы по матрицам . Пенсильванский государственный университет . Проверено 3 апреля 2017 г.
^ Антон, Ховард; Роррес, Крис (2005). Элементарная линейная алгебра (9-е изд.). Джон Уайли и сыновья, Inc. ISBN 978-0-471-66959-3 .
^ Трефетен, Ллойд; Бау, III, Дэвид (1997). Численная линейная алгебра . ISBN 978-0898713619 .
^ Дж. М. Ортега и В. К. Рейнбольдт (1970). Итерационное решение нелинейных уравнений с несколькими переменными . Репродукция Academic Press и SIAM 2000.
^ DJ Bates, AJ Sommese, JD Hauenstein и CW Wampler (2013). Численное решение полиномиальных систем с помощью Бертини . СИАМ. {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[1] Нежный, Джеймс Э. (6 декабря 2012 г.). Численная линейная алгебра для приложений в статистике . Спрингер. ISBN 9781461206231 .

[2] Стивенс, Скотт А. «Системный анализ – ранг и недействительность» (PDF) . Математика 220 — Раздаточные материалы по матрицам . Пенсильванский государственный университет . Проверено 3 апреля 2017 г.

[3] Антон, Ховард; Роррес, Крис (2005). Элементарная линейная алгебра (9-е изд.). Джон Уайли и сыновья, Inc. ISBN 978-0-471-66959-3 .

[4] Трефетен, Ллойд; Бау, III, Дэвид (1997). Численная линейная алгебра . ISBN 978-0898713619 .

[OrtRhe-5] Дж. М. Ортега и В. К. Рейнбольдт (1970). Итерационное решение нелинейных уравнений с несколькими переменными . Репродукция Academic Press и SIAM 2000.

[BSHW-6] DJ Bates, AJ Sommese, JD Hauenstein и CW Wampler (2013). Численное решение полиномиальных систем с помощью Бертини . СИАМ. {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[1]

[2]

[3]

[4]

[5]

[6]