Jump to content

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

(Перенаправлено из сверхопределенной системы )

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

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

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

[ редактировать ]

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

[ редактировать ]
#1 Система трёх линейно независимых уравнений, три линии, решений нет.
#2 Система трёх линейно независимых уравнений, три прямые (две параллельные ), решений нет.
#3 Система трех линейно независимых уравнений, три прямые (все параллельные), решений нет.
#4 Система трех уравнений (одно уравнение линейно зависит от остальных), три линии (две совпадающие), одно решение
#5 Система трех уравнений (одно уравнение линейно зависит от остальных), три линии, одно решение
#6 Система трех уравнений (два уравнения, каждое из которых линейно зависит от третьего), три совпадающие прямые, бесконечное количество решений

Рассмотрим систему из трех уравнений и двух неизвестных ( X и Y ), которая переопределена, поскольку 3 > 2, и соответствует диаграмме №1:

Для каждой пары линейных уравнений существует одно решение: для первого и второго уравнений (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) можно записать следующим образом: Обратите внимание, что число строк матрицы коэффициентов (соответствующих уравнениям) превышает число столбцов (соответствующих неизвестным), а это означает, что система переопределена. Ранг этой матрицы равен 2, что соответствует количеству зависимых переменных в системе. [2] Линейная система непротиворечива тогда и только тогда, когда матрица коэффициентов имеет тот же ранг, что и ее расширенная матрица (матрица коэффициентов с добавленным дополнительным столбцом, причем этот столбец является вектор-столбцом констант). Расширенная матрица имеет ранг 3, поэтому система несовместна. Нулевое значение равно 0, что означает, что нулевое пространство содержит только нулевой вектор и, следовательно, не имеет базиса .

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

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

[ редактировать ]

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

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

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

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

[ редактировать ]

В системах линейных уравнений L i = c i для 1 ⩽ i M , в переменных X 1 , X 2 , ..., 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 — разница между количеством переменных и рангом; следовательно, в таком случае существует бесконечное число решений.

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

[ редактировать ]

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

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

[ редактировать ]

Метод обычных наименьших квадратов можно использовать для нахождения приближенного решения переопределенных систем. Для системы формула наименьших квадратов получается из задачи решение которого можно записать с помощью нормальных уравнений , [3] где указывает на транспонирование матрицы , при условии существует (то есть при условии, что A имеет полный ранг столбца ). С помощью этой формулы находится приближенное решение, когда точного решения не существует, и дает точное решение, когда оно существует. Однако для достижения хорошей числовой точности использовать QR-факторизацию A для решения задачи наименьших квадратов. предпочтительнее [4]

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

[ редактировать ]

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

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

Решение проблемы минимизации нормы затем дается как

где на практике вместо расчета нужно выполнить обратную подстановку в правотреугольной системе

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

[ редактировать ]

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

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

Решение проблемы минимизации нормы затем дается как

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

[ редактировать ]

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

или в форме с

где это точка в или и являются действительными или сложными функциями. Система является переопределенной, если . Напротив, система является недоопределенной, если . [5] [6]

В качестве эффективного метода решения переопределенных систем итерация Гаусса-Ньютона локально квадратично сходится к решениям, при которых матрицы Якобиана являются инъективными.

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

[ редактировать ]

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

См. также

[ редактировать ]
  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 .
  5. ^ Дж. М. Ортега и В. К. Рейнбольдт (1970). Итерационное решение нелинейных уравнений с несколькими переменными . Репродукция Academic Press и SIAM 2000.
  6. ^ DJ Bates, AJ Sommese, JD Hauenstein и CW Wampler (2013). Численное решение полиномиальных систем с помощью Бертини . СИАМ. {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: aec54a8c6c824fe2c6c7eb75b9bf6e1f__1721607120
URL1:https://arc.ask3.ru/arc/aa/ae/1f/aec54a8c6c824fe2c6c7eb75b9bf6e1f.html
Заголовок, (Title) документа по адресу, URL1:
Overdetermined system - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)