Введение

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

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

является системой из трех уравнений с тремя переменными x, y, z. Решением линейной системы является набор значений переменных, при котором все уравнения выполняются одновременно. В приведенном выше примере решением является упорядоченная тройка

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

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

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

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

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

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

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

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

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

Раствор матрицы

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

где – обратная матрица A. В более общем случае, независимо от того, равно ли m=n или нет, и независимо от ранга A, все решения (если они существуют) выражаются с использованием псевдообратной Мура — Пенроуза матрицы A, обозначаемой , следующим образом:

где – вектор свободных параметров, принимающий все возможные значения в виде векторов размера n×1. Необходимым и достаточным условием существования хотя бы одного решения является то, чтобы потенциальное решение, полученное с использованием , удовлетворяло равенству — то есть, чтобы . Если это условие не выполняется, система уравнений несовместна и не имеет решений. Если условие выполняется, система совместна и существует по крайней мере одно решение. Например, в вышеупомянутом случае, когда A квадратная и имеет полный ранг, просто равна и общее уравнение решения упрощается до

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

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

В то время как системы из трех или четырех уравнений могут быть легко решены вручную (см. «Краковиан»), компьютеры часто используются для больших систем. Стандартный алгоритм решения системы линейных уравнений основан на методе Гаусса с некоторыми модификациями. Во-первых, необходимо избегать деления на малые числа, что может привести к неточным результатам. Это можно сделать, переупорядочивая уравнения при необходимости, процесс, известный как выбор главного элемента. Во-вторых, алгоритм не выполняет метод Гаусса напрямую, а вычисляет LU-разложение матрицы A. Это в основном организационный инструмент, но он значительно быстрее, если требуется решить несколько систем с одной и той же матрицей A, но с разными векторами b. Если матрица A обладает определенной структурой, это можно использовать для получения более быстрых или точных алгоритмов. Например, системы с симметричной положительно определенной матрицей можно решить в два раза быстрее с помощью разложения Холецкого. Рекурсия Левинсона – быстрый метод для матриц Топлица. Существуют также специальные методы для матриц с большим количеством нулевых элементов (так называемых разреженных матриц), которые часто встречаются в приложениях. Для очень больших систем часто используется совершенно иной подход, который в противном случае потребовал бы слишком много времени или памяти. Идея заключается в том, чтобы начать с начального приближения к решению (которое не обязательно должно быть точным) и изменять это приближение в несколько шагов, чтобы приблизить его к истинному решению. Как только приближение становится достаточно точным, оно принимается за решение системы. Это приводит к классу итерационных методов. Для некоторых разреженных матриц введение случайности повышает скорость итерационных методов. Одним из примеров итерационного метода является метод Якоби, в котором матрица разделяется на диагональную и недиагональную компоненты. В начале алгоритма используется начальное предположение. Каждое последующее предположение вычисляется с использованием итерационного уравнения:

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

Набор однородных растворов

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