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

Несколько уравнений степени 1, которые необходимо решать одновременно

Линейная система с тремя переменными определяет набор плоскостей. Точка пересечения является решением.

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

${\displaystyle {\begin{cases}3x+2y-z=1\\2x-2y+4z=-2\\-x+{\frac {1}{2}}y-z=0\end{cases}}}$

представляет собой систему трех уравнений с тремя переменными x , y , z . Решение линейной системы — это присвоение значений переменным таким образом, чтобы все уравнения одновременно удовлетворялись . В приведенном выше примере решение дается упорядоченной тройкой , поскольку она делает все три уравнения действительными. Слово «система» указывает на то, что уравнения следует рассматривать коллективно, а не индивидуально. ${\displaystyle (x,y,z)=(1,-2,-2),}$

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

Очень часто, и в этой статье, коэффициенты уравнений являются действительными или комплексными числами , а решения ищутся в одном и том же наборе чисел, но теория и алгоритмы применимы для коэффициентов и решений в любой области . Для решений в области целостности, такой как кольцо целых чисел , или в других алгебраических структурах , были разработаны другие теории, см. Линейное уравнение над кольцом . Целочисленное линейное программирование — это набор методов поиска «лучшего» целочисленного решения (когда их много). Базисная теория Грёбнера предоставляет алгоритмы, в которых коэффициенты и неизвестные являются полиномами . Тропическая геометрия — еще один пример линейной алгебры в более экзотической структуре.

Элементарные примеры

Тривиальный пример

Система одного уравнения с одним неизвестным

${\displaystyle 2x=4}$

есть решение

${\displaystyle x=2.}$

Однако обычно считается, что линейная система имеет как минимум два уравнения. ^{[ кем? ]}

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

Самый простой вид нетривиальной линейной системы включает два уравнения и две переменные:

${\displaystyle {\begin{alignedat}{5}2x&&\;+\;&&3y&&\;=\;&&6&\\4x&&\;+\;&&9y&&\;=\;&&15&.\end{alignedat}}}$

Один из способов решения такой системы заключается в следующем. Сначала решите верхнее уравнение для : ${\displaystyle x}$ ${\displaystyle y}$

${\displaystyle x=3-{\frac {3}{2}}y.}$

Теперь подставьте это выражение для x в нижнее уравнение:

${\displaystyle 4\left(3-{\frac {3}{2}}y\right)+9y=15.}$

В результате получается одно уравнение, включающее только переменную . Решение дает и подставляет это обратно в уравнение для доходности . Этот метод обобщается на системы с дополнительными переменными (см. «Устранение переменных» ниже или статью об элементарной алгебре ). ${\displaystyle y}$ ${\displaystyle y=1}$ ${\displaystyle x}$ ${\displaystyle x={\frac {3}{2}}}$

Общая форма

Общую систему m линейных уравнений с n неизвестными и коэффициентами можно записать как

${\displaystyle {\begin{cases}a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}=b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\dots +a_{2n}x_{n}=b_{2}\\\vdots \\a_{m1}x_{1}+a_{m2}x_{2}+\dots +a_{mn}x_{n}=b_{m},\end{cases}}}$

где – неизвестные, – коэффициенты системы, – постоянные члены. ^[2] ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$ ${\displaystyle a_{11},a_{12},\dots ,a_{mn}}$ ${\displaystyle b_{1},b_{2},\dots ,b_{m}}$

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

Векторное уравнение

Одна чрезвычайно полезная точка зрения заключается в том, что каждое неизвестное является весом вектора -столбца в линейной комбинации .

${\displaystyle x_{1}{\begin{bmatrix}a_{11}\\a_{21}\\\vdots \\a_{m1}\end{bmatrix}}+x_{2}{\begin{bmatrix}a_{12}\\a_{22}\\\vdots \\a_{m2}\end{bmatrix}}+\dots +x_{n}{\begin{bmatrix}a_{1n}\\a_{2n}\\\vdots \\a_{mn}\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}}$

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

Матричное уравнение

Векторное уравнение эквивалентно матричному уравнению вида

$${\displaystyle A\mathbf {x} =\mathbf {b} }$$

Amnxвектор-столбецnbm^[3]

$${\displaystyle A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{bmatrix}},\quad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}.}$$

матрицы

Набор решений

Множество решений уравнений x − y = −1 и 3 x + y = 9 представляет собой единственную точку (2, 3).

Решением линейной системы является присвоение значений переменным x ₁ , x ₂ , ..., x _n такое , что каждое из уравнений удовлетворяется. Множество всех возможных решений называется множеством решений . ^[4]

Линейная система может вести себя одним из трех возможных способов:

1. Система имеет бесконечно много решений .
2. Система имеет единственное решение .
3. Система не имеет решения .

Геометрическая интерпретация

Для системы, включающей две переменные ( x и y ) , каждое линейное уравнение определяет линию на плоскости xy . Поскольку решение линейной системы должно удовлетворять всем уравнениям, набор решений представляет собой пересечение этих линий и, следовательно, представляет собой либо линию, одну точку, либо пустое множество .

Для трех переменных каждое линейное уравнение определяет плоскость в трехмерном пространстве , а множеством решений является пересечение этих плоскостей. Таким образом, набором решений может быть плоскость, линия, отдельная точка или пустое множество. Например, поскольку три параллельные плоскости не имеют общей точки, множество решений их уравнений пусто; множество решений уравнений трех плоскостей, пересекающихся в одной точке, одноточечное; если три плоскости проходят через две точки, их уравнения имеют по крайней мере два общих решения; на самом деле множество решений бесконечно и состоит из всех прямых, проходящих через эти точки. ^[5]

Для n переменных каждое линейное уравнение определяет гиперплоскость в n -мерном пространстве . Множество решений представляет собой пересечение этих гиперплоскостей и представляет собой плоскость , размерность которой может быть меньше n .

Общее поведение

Множество решений двух уравнений с тремя переменными, вообще говоря, представляет собой прямую.

В общем случае поведение линейной системы определяется соотношением количества уравнений и количества неизвестных. Здесь «в целом» означает, что при конкретных значениях коэффициентов уравнений может иметь место различное поведение.

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

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

Следующие рисунки иллюстрируют эту трихотомию в случае двух переменных:

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

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

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

Характеристики

Независимость

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

Уравнения x - 2 y = -1 , 3 x + 5 y = 8 и 4 x + 3 y = 7 линейно зависимы.

Например, уравнения

${\displaystyle 3x+2y=6\;\;\;\;{\text{and}}\;\;\;\;6x+4y=12}$

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

В более сложном примере уравнения

${\displaystyle {\begin{alignedat}{5}x&&\;-\;&&2y&&\;=\;&&-1&\\3x&&\;+\;&&5y&&\;=\;&&8&\\4x&&\;+\;&&3y&&\;=\;&&7&\end{alignedat}}}$

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

Последовательность

Уравнения 3 x + 2 y = 6 и 3 x + 2 y = 12 несовместны.

Линейная система называется несовместной, если она не имеет решения, в противном случае ее называют совместной . ^[6] Когда система несовместна, из уравнений можно вывести противоречие , которое всегда можно переписать как утверждение 0 = 1 .

Например, уравнения

${\displaystyle 3x+2y=6\;\;\;\;{\text{and}}\;\;\;\;3x+2y=12}$

противоречивы. Фактически, вычитая первое уравнение из второго и умножая обе части результата на 1/6, мы получаем 0 = 1 . Графики этих уравнений на плоскости xy представляют собой пару параллельных линий.

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

${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&y&&\;=\;&&1&\\2x&&\;+\;&&y&&\;=\;&&1&\\3x&&\;+\;&&2y&&\;=\;&&3&\end{alignedat}}}$

противоречивы. Сложение первых двух уравнений дает 3 x + 2 y = 2 , которые можно вычесть из третьего уравнения и получить 0 = 1 . Любые два из этих уравнений имеют общее решение. То же явление может произойти для любого количества уравнений.

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

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

Эквивалентность

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

Решение линейной системы

Существует несколько алгоритмов решения системы линейных уравнений .

Описание решения

Когда множество решений конечно, оно сводится к одному элементу. В этом случае единственное решение описывается последовательностью уравнений, левые части которых — имена неизвестных, а правые — соответствующие значения, например . Если порядок неизвестных фиксирован, например, в алфавитном порядке , решение можно описать как вектор значений, как в предыдущем примере. ${\displaystyle (x=3,\;y=-2,\;z=6)}$ ${\displaystyle (3,\,-2,\,6)}$

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

Например, рассмотрим следующую систему:

${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&3y&&\;-\;&&2z&&\;=\;&&5&\\3x&&\;+\;&&5y&&\;+\;&&6z&&\;=\;&&7&\end{alignedat}}}$

Множество решений этой системы можно описать следующими уравнениями:

${\displaystyle x=-7z-1\;\;\;\;{\text{and}}\;\;\;\;y=3z+2{\text{.}}}$

Здесь z — свободная переменная, а x и y зависят от z . Любую точку в наборе решений можно получить, сначала выбрав значение z , а затем вычислив соответствующие значения x и y .

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

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

${\displaystyle y=-{\frac {3}{7}}x+{\frac {11}{7}}\;\;\;\;{\text{and}}\;\;\;\;z=-{\frac {1}{7}}x-{\frac {1}{7}}{\text{.}}}$

Здесь x — свободная переменная, а y и z — зависимые.

Устранение переменных

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

1. В первом уравнении найдите одну из переменных через другие.
2. Подставьте это выражение в оставшиеся уравнения. В результате получается система уравнений, в которой на одно уравнение меньше и неизвестное.
3. Повторяйте шаги 1 и 2, пока система не сведется к одному линейному уравнению.
4. Решите это уравнение, а затем выполняйте обратную замену, пока не будет найдено полное решение.

Например, рассмотрим следующую систему:

${\displaystyle {\begin{cases}x+3y-2z=5\\3x+5y+6z=7\\2x+4y+3z=8\end{cases}}}$

Решение первого уравнения для x дает x = 5 + 2 z - 3 y , а подстановка этого значения во второе и третье уравнения дает

${\displaystyle {\begin{cases}y=3z+2\\y={\tfrac {7}{2}}z+1\end{cases}}}$

Поскольку левая часть обоих этих уравнений равна y , приравнивая правую часть уравнений. Теперь у нас есть:

${\displaystyle {\begin{aligned}3z+2={\tfrac {7}{2}}z+1\\\Rightarrow z=2\end{aligned}}}$

Подстановка z = 2 во второе или третье уравнение дает y = 8, а значения y и z в первом уравнении дают x = -15. Следовательно, множество решений представляет собой упорядоченную тройку . ${\displaystyle (x,y,z)=(-15,8,2)}$

Сокращение строк

При сокращении строк (также известном как исключение Гаусса ) линейная система представляется как расширенная матрица ^[7]

${\displaystyle \left[{\begin{array}{rrr|r}1&3&-2&5\\3&5&6&7\\2&4&3&8\end{array}}\right]{\text{.}}}$

Затем эта матрица модифицируется с помощью элементарных операций со строками до тех пор, пока не достигнет сокращенной формы эшелона строк . Существует три типа элементарных операций над строками: ^[7]

Тип 1 : Поменяйте местами две строки.

Тип 2 : Умножить строку на ненулевой скаляр .

Тип 3 : добавьте к одной строке скаляр, кратный другой.

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

Существует несколько конкретных алгоритмов сокращения строк расширенной матрицы, самыми простыми из которых являются исключение Гаусса и исключение Гаусса – Жордана . Следующие вычисления показывают исключение Гаусса – Жордана, примененное к приведенной выше матрице:

${\displaystyle {\begin{aligned}\left[{\begin{array}{rrr|r}1&3&-2&5\\3&5&6&7\\2&4&3&8\end{array}}\right]&\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&-4&12&-8\\2&4&3&8\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&-4&12&-8\\0&-2&7&-2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&-3&2\\0&-2&7&-2\end{array}}\right]\\&\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&-3&2\\0&0&1&2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&0&8\\0&0&1&2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&0&9\\0&1&0&8\\0&0&1&2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&0&0&-15\\0&1&0&8\\0&0&1&2\end{array}}\right].\end{aligned}}}$

Последняя матрица имеет форму сокращенного звена строк и представляет систему x = −15 , y = 8 , z = 2 . Сравнение с примером алгебраического исключения переменных из предыдущего раздела показывает, что эти два метода фактически одинаковы; разница заключается в том, как записываются вычисления.

Правило Крамера

Правило Крамера — это явная формула решения системы линейных уравнений, в которой каждая переменная задается частным из двух определителей . ^[8] Например, решение системы

${\displaystyle {\begin{alignedat}{7}x&\;+&\;3y&\;-&\;2z&\;=&\;5\\3x&\;+&\;5y&\;+&\;6z&\;=&\;7\\2x&\;+&\;4y&\;+&\;3z&\;=&\;8\end{alignedat}}}$

дан кем-то

${\displaystyle x={\frac {\,{\begin{vmatrix}5&3&-2\\7&5&6\\8&4&3\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}},\;\;\;\;y={\frac {\,{\begin{vmatrix}1&5&-2\\3&7&6\\2&8&3\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}},\;\;\;\;z={\frac {\,{\begin{vmatrix}1&3&5\\3&5&7\\2&4&8\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}}.}$

Для каждой переменной знаменатель — это определитель матрицы коэффициентов , а числитель — это определитель матрицы, в которой один столбец заменен вектором постоянных членов.

Хотя правило Крамера важно теоретически, оно не имеет практической ценности для больших матриц, поскольку вычисление больших определителей несколько громоздко. (Действительно, большие определители легче всего вычислить с помощью сокращения строк.) Кроме того, правило Крамера имеет очень плохие числовые свойства, что делает его непригодным для надежного решения даже небольших систем, если только операции не выполняются в рациональной арифметике с неограниченной точностью. ^{[ нужна цитата ]}

Матричное решение

Если система уравнений выражена в матричной форме , то все множество решений также можно выразить в матричной форме. Если матрица A квадратная (имеет m строк и n = m столбцов) и имеет полный ранг (все m строк независимы), то система имеет единственное решение, определяемое формулой ${\displaystyle A\mathbf {x} =\mathbf {b} }$

${\displaystyle \mathbf {x} =A^{-1}\mathbf {b} }$

где является обратным A . _ В более общем смысле, независимо от того, m = n или нет, и независимо от ранга A , все решения (если таковые существуют) даются с использованием обратного к A Мура-Пенроуза , обозначаемого следующим образом: ${\displaystyle A^{-1}}$ ${\displaystyle A^{+}}$

${\displaystyle \mathbf {x} =A^{+}\mathbf {b} +\left(I-A^{+}A\right)\mathbf {w} }$

где — вектор свободных параметров, охватывающий все возможные векторы n × 1. Необходимым и достаточным условием существования любого решения(й) является то, что потенциальное решение, полученное с использованием метода удовлетворяет , то есть если это условие не выполняется, система уравнений несовместна и не имеет решения. Если условие выполнено, система совместна и существует хотя бы одно решение. Например, в вышеупомянутом случае, когда A является квадратным и имеет полный ранг, просто равно , и общее уравнение решения упрощается до ${\displaystyle \mathbf {w} }$ ${\displaystyle \mathbf {w} =\mathbf {0} }$ ${\displaystyle A\mathbf {x} =\mathbf {b} }$ ${\displaystyle AA^{+}\mathbf {b} =\mathbf {b} .}$ ${\displaystyle A^{+}}$ ${\displaystyle A^{-1}}$

${\displaystyle \mathbf {x} =A^{-1}\mathbf {b} +\left(I-A^{-1}A\right)\mathbf {w} =A^{-1}\mathbf {b} +\left(I-I\right)\mathbf {w} =A^{-1}\mathbf {b} }$

как уже говорилось ранее, где полностью выпал из решения, оставив только одно решение. В других случаях, однако, остается и, следовательно, бесконечность потенциальных значений вектора свободных параметров дает бесконечность решений уравнения. ${\displaystyle \mathbf {w} }$ ${\displaystyle \mathbf {w} }$ ${\displaystyle \mathbf {w} }$

Другие методы

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

Если матрица A имеет особую структуру, это можно использовать для получения более быстрых и точных алгоритмов. Например, системы с симметричной положительно определенной матрицей можно решать в два раза быстрее с помощью разложения Холецкого . Рекурсия Левинсона — быстрый метод для матриц Теплица . Существуют также специальные методы для матриц со многими нулевыми элементами (так называемые разреженные матрицы ), которые часто встречаются в приложениях.

Совершенно другой подход часто применяется для очень больших систем, которые в противном случае заняли бы слишком много времени или памяти. Идея состоит в том, чтобы начать с начального приближения решения (которое вовсе не обязательно должно быть точным) и в несколько шагов изменить это приближение, чтобы приблизить его к истинному решению. Если приближение становится достаточно точным, оно считается решением системы. Это приводит к классу итерационных методов . Для некоторых разреженных матриц введение случайности повышает скорость итерационных методов. ^[9] Одним из примеров итеративного метода является метод Якоби , при котором матрица разбивается на диагональный компонент и недиагональный компонент . Первоначальное предположение используется в начале алгоритма. Каждое последующее предположение вычисляется с использованием итеративного уравнения: ${\displaystyle A}$ ${\displaystyle D}$ ${\displaystyle L+U}$ ${\displaystyle {\mathbf {x}}^{(0)}}$

${\displaystyle {\mathbf {x}}^{(k+1)}=D^{-1}({\mathbf {b}}-(L+U){\mathbf {x}}^{(k)})}$

Когда разница между предположениями и достаточно мала, говорят, что алгоритм сошелся к решению. ^[10] ${\displaystyle {\mathbf {x}}^{(k)}}$ ${\displaystyle {\mathbf {x}}^{(k+1)}}$

Существует также квантовый алгоритм для линейных систем уравнений . ^[11]

Гомогенные системы

Система линейных уравнений является однородной , если все постоянные члены равны нулю:

${\displaystyle {\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;=\;&&&0\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;=\;&&&0\\&&&&&&&&&&\vdots \;\ &&&\\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;=\;&&&0.\\\end{alignedat}}}$

Однородная система эквивалентна матричному уравнению вида

${\displaystyle A\mathbf {x} =\mathbf {0} }$

где A — матрица размера m × n , x — вектор-столбец с n элементами, а 0 — нулевой вектор с m элементами.

Однородный набор решений

Каждая однородная система имеет по крайней мере одно решение, известное как нулевое (или тривиальное ) решение, которое получается путем присвоения значения нуля каждой из переменных. Если система имеет неособую матрицу ( det( A ) ≠ 0 ), то это также единственное решение. Если система имеет сингулярную матрицу, то существует множество решений с бесконечным числом решений. Этот набор решений имеет следующие дополнительные свойства:

1. Если u и v — два вектора , представляющие решения однородной системы, то векторная сумма u + v также является решением этой системы.
2. Если u — вектор, представляющий решение однородной системы, а r — любой скаляр , то ru также является решением системы.

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

Отношение к неоднородным системам

Существует тесная связь между решениями линейной системы и решениями соответствующей однородной системы:

${\displaystyle A\mathbf {x} =\mathbf {b} \qquad {\text{and}}\qquad A\mathbf {x} =\mathbf {0} .}$

В частности, если p — какое-либо конкретное решение линейной системы A x = b , то весь набор решений можно описать как

${\displaystyle \left\{\mathbf {p} +\mathbf {v} :\mathbf {v} {\text{ is any solution to }}A\mathbf {x} =\mathbf {0} \right\}.}$

Геометрически это говорит о том, что набор решений для A x = b является сдвигом набора решений для A x = 0 . В частности, плоскость для первой системы можно получить путем перевода линейного подпространства однородной системы на вектор p .

Это рассуждение применимо только в том случае, если система A x = b имеет хотя бы одно решение. Это происходит тогда и только тогда , когда вектор b лежит в образе линейного преобразования A.

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

• Расположение гиперплоскостей
• Итеративное уточнение
• Граф Коутса
• LAPACK (бесплатный стандартный пакет для численного решения линейных уравнений; доступен на Fortran , C , C++ )
• Линейное уравнение над кольцом
• Линейный метод наименьших квадратов
• Разложение матрицы
• Расщепление матрицы
• Числовая библиотека NAG (версии решателей LAPACK из библиотеки NAG)
• Алгоритм Рыбицкого Пресса
• Одновременные уравнения

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

1. Антон (1987), с. 2; Берден и Фэйрес (1993), с. 324; Голуб и Ван Лоан (1996), с. 87; Харпер (1976), с. 57.
2. Борегар и Фрели (1973), с. 65.
3. Борегар и Фрели (1973), стр. 65–66.
4. «Системы линейных уравнений» (PDF) . math.berkeley.edu .
5. Каллен (1990), с. 3.
6. Уайтлоу (1991), с. 70.
7. Beauregard & Fraleigh (1973), стр. 68.
8. Стерлинг (2009), с. 235.
9. Хартнетт, Кевин (8 марта 2021 г.). «Новый алгоритм превышает предел скорости решения линейных уравнений». Журнал Кванта . Проверено 9 марта 2021 г.
10. "Метод Якоби".
11. Харроу, хасиды и Ллойд (2009).

Библиография

• Антон, Ховард (1987), Элементарная линейная алгебра (5-е изд.), Нью-Йорк: Wiley , ISBN 0-471-84819-0
• Борегар, Раймонд А.; Фрэли, Джон Б. (1973), Первый курс линейной алгебры: с дополнительным введением в группы, кольца и поля , Бостон: Houghton Mifflin Company , ISBN 0-395-14017-Х
• Берден, Ричард Л.; Фейрес, Дж. Дуглас (1993), Численный анализ (5-е изд.), Бостон: Приндл, Вебер и Шмидт, ISBN 0-534-93219-3
• Каллен, Чарльз Г. (1990), Матрицы и линейные преобразования , Массачусетс: Дувр, ISBN 978-0-486-66328-9
• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Балтимор: Издательство Университета Джона Хопкинса , ISBN 0-8018-5414-8
• Харпер, Чарли (1976), Введение в математическую физику , Нью-Джерси: Прентис-Холл , ISBN 0-13-487538-9
• Харроу, Арам В.; хасидим, Авинатан; Ллойд, Сет (2009), «Квантовый алгоритм для линейных систем уравнений», Physical Review Letters , 103 (15): 150502, arXiv : 0811.3171 , Bibcode : 2009PhRvL.103o0502H, doi : 10.1103/PhysRevLett.103.15050 2, ПМИД  19905613, S2CID  5187993
• Стерлинг, Мэри Дж. (2009), Линейная алгебра для чайников , Индианаполис, Индиана: Wiley, ISBN 978-0-470-43090-3
• Уайтлоу, Т. А. (1991), Введение в линейную алгебру (2-е изд.), CRC Press, ISBN 0-7514-0159-5

дальнейшее чтение

• Экслер, Шелдон Джей (1997), Правильно выполненная линейная алгебра (2-е изд.), Springer-Verlag, ISBN 0-387-98259-0
• Лэй, Дэвид К. (22 августа 2005 г.), Линейная алгебра и ее приложения (3-е изд.), Аддисон Уэсли, ISBN 978-0-321-28713-7
• Мейер, Карл Д. (15 февраля 2001 г.), Матричный анализ и прикладная линейная алгебра, Общество промышленной и прикладной математики (SIAM), ISBN 978-0-89871-454-8, заархивировано из оригинала 1 марта 2001 г.
• Пул, Дэвид (2006), Линейная алгебра: современное введение (2-е изд.), Брукс/Коул, ISBN 0-534-99845-3
• Антон, Ховард (2005), Элементарная линейная алгебра (версия для приложений) (9-е изд.), Wiley International
• Леон, Стивен Дж. (2006), Линейная алгебра с приложениями (7-е изд.), Пирсон Прентис Холл
• Стрэнг, Гилберт (2005), Линейная алгебра и ее приложения

Внешние ссылки

• СМИ, связанные с системой линейных уравнений, на Викискладе?