Система линейных алгебраических уравнений

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

Система линейных алгебраических уравнений (линейная система, также употребляются аббревиатуры СЛАУ, СЛУ) — система уравнений, каждое уравнение в которой является линейным — алгебраическим уравнением первой степени.

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

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

Могут обобщаться на случай бесконечного множества неизвестных.

Соглашения и определения

Общий вид системы линейных алгебраических уравнений:

$\{\begin{array}{c}{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\\ \dots \\ a_{m1}{x}_1+a_{m2}{x}_2+\dots +a_{mn}{x}_n=b_m\end{array}$

Здесь $m$ — количество уравнений, а $n$ — количество переменных, $x_1,x_2,\dots ,x_n$ — неизвестные, которые надо определить, коэффициенты $a_{11},a_{12},\dots ,a_{mn}$ и свободные члены $b_1,b_2,\dots ,b_m$ предполагаются известными. Индексы коэффициентов в системах линейных уравнений ($a_{ij}$) формируются по следующему соглашению: первый индекс ($i$) обозначает номер уравнения, второй ($j$) — номер переменной, при которой стоит этот коэффициент.

Шаблон:ЯкорьШаблон:ЯкорьСистема называется однородной, если все её свободные члены равны нулю ($b_1=b_2=\dots =b_m=0$), иначе — неоднородной.

Шаблон:ЯкорьШаблон:ЯкорьКвадратная система линейных уравнений — система, у которой количество уравнений совпадает с числом неизвестных ($m=n$). Система, у которой число неизвестных больше числа уравнений, является недоопределённой, такие системы линейных алгебраических уравнений также называются прямоугольными. Если уравнений больше, чем неизвестных, то система является переопределённой.

Решение системы линейных алгебраических уравнений — совокупность $n$ чисел $c_1,c_2,\dots ,c_n$, таких что их соответствующая подстановка вместо $x_1,x_2,\dots ,x_n$ в систему обращает все её уравнения в тождества.

Шаблон:ЯкорьСистема называется совместной, если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения. Решения считаются различными, если хотя бы одно из значений переменных не совпадает. Совместная система с единственным решением называется определённой, при наличии более одного решения — недоопределённой.

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

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

$\left(\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \cdots & a_{mn}\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right)=\left(\begin{array}{c}{b}_1\\ b_2\\ ⋮\\ b_m\end{array}\right)$

или:

$Ax=b$.

Здесь $A$ — это матрица системы, $x$ — столбец неизвестных, а $b$ — столбец свободных членов. Если к матрице $A$ приписать справа столбец свободных членов, то получившаяся матрица называется расширенной.

Теорема Кронекера — Капелли устанавливает необходимое и достаточное условие совместности системы линейных алгебраических уравнений посредством свойств матричных представлений: система совместна тогда и только тогда, когда ранг её матрицы совпадает с рангом расширенной матрицы.

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

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

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

Система линейных алгебраических уравнений $A𝐱=𝐛$ эквивалентна системе $CA𝐱=C𝐛$, где $C$ — невырожденная матрица. В частности, если сама матрица $A$ — невырожденная, и для неё существует обратная матрица $A^{-1}$, то решение системы уравнений можно формально записать в виде $𝐱=A^{-1}𝐛$.

Методы решения

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

Некоторые прямые методы:

• Метод Гаусса
• Метод Гаусса — Жордана
• Метод Крамера
• Матричный метод
• Метод прогонки (для трёхдиагональных матриц)
• Разложение Холецкого или метод квадратных корней (для положительно-определённых симметричных и эрмитовых матриц)

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

$𝐱=A^{\prime }𝐱+{𝐛}^{\prime }$,

эквивалентного начальной системе линейных алгебраических уравнений. При итерации $𝐱$ в правой части уравнения заменяется, например, в методе Якоби (метод простой итерации) приближение, найденное на предыдущем шаге:

${𝐱}_{n+1}=A^{\prime }{𝐱}_n+{𝐛}^{\prime }$.

Итерационные методы делятся на несколько типов, в зависимости от применяемого подхода:

• Основанные на расщеплении: $(M-N)𝐱=𝐛\iff M𝐱=N𝐱+𝐛\Rightarrow M{𝐱}^{n+1}=N{𝐱}^n+𝐛$
• Вариационного типа: $A𝐱=𝐛\Rightarrow \Vert A𝐱-𝐛\Vert \to \min$
• Проекционного типа: $A𝐱=𝐛\Rightarrow (A𝐱,𝐦)=(𝐛,𝐦)\mathrm{\forall }𝐦$

Среди итерационных методов:

• Метод Якоби (метод простой итерации)
• Метод Гаусса — Зейделя
• Метод релаксации
• Многосеточный метод
• Метод Монтанте
• Метод Абрамова (пригоден для решения небольших СЛАУ)
• Шаблон:Не переведено
• Метод бисопряжённых градиентов
• Стабилизированный метод бисопряжённых градиентов
• Шаблон:Не переведено
• Метод квази-минимальных невязок (QMR)
• Метод вращений

Ссылки

• Шаблон:Книга
• Шаблон:Книга