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

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

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

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

${\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}}}$

где — неизвестные, — коэффициенты системы, — постоянные члены. ^[3] ${\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 независимых векторов, решение гарантировано независимо от правой части, а в противном случае не гарантировано.

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

Векторные уравнения эквивалентны матричному уравнению вида , где A — матрица размером m × n , x — вектор-столбец с n элементами, а b — вектор-столбец с m элементами. ^[4] $${\displaystyle A\mathbf {x} =\mathbf {b} }$$

$${\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).

Решение линейной системы — это присвоение значений переменным таким образом, чтобы каждое из уравнений было удовлетворено. Набор всех возможных решений называется набором решений . ^[5] ${\displaystyle x_{1},x_{2},\dots ,x_{n}}$

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

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

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

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

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

Для 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 несовместны.

Линейная система противоречива , если она не имеет решения, в противном случае она называется согласованной . ^[7] Когда система противоречива, из уравнений можно вывести противоречие , которое всегда можно переписать в виде утверждения 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 , получаем , а подставляя это во второе и третье уравнения, получаем ${\displaystyle x=5+2z-3y}$

${\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)}$

Сокращение количества строк

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

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

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

Тип 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. Сравнение с примером в предыдущем разделе по алгебраическому исключению переменных показывает, что эти два метода фактически одинаковы; разница заключается в том, как записываются вычисления.

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

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

${\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} }$

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

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

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

Совершенно другой подход часто применяется для очень больших систем, которые в противном случае заняли бы слишком много времени или памяти. Идея состоит в том, чтобы начать с начального приближения к решению (которое не обязательно должно быть точным) и изменить это приближение в несколько шагов, чтобы приблизить его к истинному решению. Как только приближение становится достаточно точным, оно принимается за решение системы. Это приводит к классу итерационных методов . Для некоторых разреженных матриц введение случайности повышает скорость итерационных методов. ^[10] Одним из примеров итеративного метода является метод Якоби , в котором матрица разбивается на диагональную и недиагональную компоненты . Начальное предположение используется в начале алгоритма. Каждое последующее предположение вычисляется с использованием итерационного уравнения: ${\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)})}$

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

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

Однородные системы

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

${\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 — любой скаляр , то r u также является решением системы.

Это именно те свойства, которые требуются для того, чтобы набор решений был линейным подпространством R n ^. В частности, набор решений однородной системы совпадает с нулевым пространством соответствующей матрицы 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. "Система уравнений". Britannica . Получено 26 августа 2024 г. .
3. Борегар и Фрели (1973), с. 65.
4. Борегар и Фрели (1973), стр. 65–66.
5. "Системы линейных уравнений" (PDF) . math.berkeley.edu .
6. Каллен (1990), стр. 3.
7. Уайтлоу (1991), стр. 70.
8. Борегар и Фрели (1973), стр. 68.
9. Стерлинг (2009), стр. 235.
10. Хартнетт, Кевин (8 марта 2021 г.). «Новый алгоритм преодолевает ограничение скорости решения линейных уравнений». Журнал Quanta . Получено 9 марта 2021 г.
11. «Метод Якоби».
12. Харроу, Хассидим и Ллойд (2009).

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

• Антон, Говард (1987), Элементарная линейная алгебра (5-е изд.), Нью-Йорк: Wiley , ISBN 0-471-84819-0
• Борегард, Рэймонд А.; Фрейли, Джон Б. (1973), Первый курс линейной алгебры: с дополнительным введением в группы, кольца и поля , Бостон: Houghton Mifflin Company , ISBN 0-395-14017-X
• Берден, Ричард Л.; Фейрес, Дж. Дуглас (1993), Численный анализ (5-е изд.), Бостон: Prindle, Weber and Schmidt, ISBN 0-534-93219-3
• Каллен, Чарльз Г. (1990), Матрицы и линейные преобразования , MA: Dover, ISBN 978-0-486-66328-9
• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Балтимор: Издательство Университета Джонса Хопкинса , ISBN 0-8018-5414-8
• Харпер, Чарли (1976), Введение в математическую физику , Нью-Джерси: Prentice-Hall , ISBN 0-13-487538-9
• Harrow, Aram W.; Hassidim, Avinatan; Lloyd, Seth (2009), "Квантовый алгоритм для линейных систем уравнений", Physical Review Letters , 103 (15): 150502, arXiv : 0811.3171 , Bibcode : 2009PhRvL.103o0502H, doi : 10.1103/PhysRevLett.103.150502, PMID  19905613, S2CID  5187993
• Стерлинг, Мэри Дж. (2009), Линейная алгебра для чайников , Индианаполис, Индиана: Wiley, ISBN 978-0-470-43090-3
• Уайтлоу, TA (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-е изд.). Pearson Prentice Hall.
• Стрэнг, Гилберт (2005). Линейная алгебра и ее приложения .
• Пэн, Ричард; Вемпала, Сантош С. (2024). «Решение разреженных линейных систем быстрее, чем умножение матриц». Comm. ACM . 67 (7): 79–86. arXiv : 2007.10254 . doi :10.1145/3615679.

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

• Медиа, связанные с системой линейных уравнений на Wikimedia Commons