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

 [[Файл:Secretsharing-3-point.png|thumb|right|Система линейных уравнений от трёх переменных определяет набор [[Плоскость (геометрия)|плоскостей]]. Точка пересечения является решением]]
'''Система линейных алгебраических уравнений''' (''линейная система'', также употребляются [[аббревиатура|аббревиатуры]] ''СЛАУ'', ''СЛУ'') — [[система уравнений]], каждое уравнение в которой является [[Линейное уравнение|линейным]] — [[Алгебраическое уравнение|алгебраическим уравнением]] первой степени.

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

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

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

== Соглашения и определения ==
Общий вид системы линейных алгебраических уравнений:
: <math>
\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 \\
    \dots\\
    a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m \\
\end{cases}
</math>
Здесь <math>m</math> — количество уравнений, а <math>n</math> — количество переменных, <math>x_1, x_2, \dots, x_n</math> — неизвестные, которые надо определить, коэффициенты <math>a_{11}, a_{12}, \dots, a_{mn}</math> и свободные члены <math>b_1, b_2, \dots, b_m</math> предполагаются известными. Индексы коэффициентов в системах линейных уравнений (<math>a_{ij}</math>) формируются по следующему соглашению: первый индекс (<math>i</math>) обозначает номер уравнения, второй (<math>j</math>) — номер переменной, при которой стоит этот коэффициент<ref name="ilin">Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М.: Физматлит, 2004. — 280 с.</ref>.

{{Якорь|Однородная}}{{Якорь|Неоднородная}}Система называется '''''однородной''''', если все её свободные члены равны нулю (<math>b_1 = b_2 = \dots b_m = 0</math>), иначе — '''''неоднородной'''''.

{{Якорь|Квадратная}}{{Якорь|Прямоугольная}}'''''Квадратная система линейных уравнений''''' — система, у которой количество уравнений совпадает с числом неизвестных (<math>m=n</math>). Система, у которой число неизвестных больше числа уравнений является [[Недоопределённая система|недоопределённой]], такие системы линейных алгебраических уравнений также называются '''''прямоугольными'''''. Если уравнений больше, чем неизвестных, то система является [[Переопределённая система|переопределённой]].

Решение системы линейных алгебраических уравнений — совокупность <math>n</math> чисел <math>c_1, c_2, \dots, c_n</math>, таких что их соответствующая подстановка вместо <math>x_1, x_2, \dots, x_n</math> в систему обращает все её уравнения в [[Тождество (математика)|тождества]].

{{якорь|Совместность}}Система называется '''совместной''', если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения. Решения считаются различными, если хотя бы одно из значений переменных не совпадает. Совместная система с единственным решением называется [[Определённая система уравнений|определённой]], при наличии более одного решения — [[Недоопределённая система|недоопределённой]].

== Матричная форма ==
Система линейных алгебраических уравнений может быть представлена в [[Матрица (математика)#Матрица как запись коэффициентов системы линейных уравнений|матричной форме]] как:
: <math>
\begin{pmatrix}
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{pmatrix}

\begin{pmatrix}
x_1 \\
x_2 \\
\vdots \\
x_n
\end{pmatrix} 
=
\begin{pmatrix}
b_1 \\
b_2 \\
\vdots \\
b_m
\end{pmatrix} 
</math>
или:
: <math>Ax = b</math>.
Здесь <math>A</math> — это матрица системы, <math>x</math> — столбец неизвестных, а <math>b</math> — столбец свободных членов. Если к матрице <math>A</math> приписать справа столбец свободных членов, то получившаяся матрица называется расширенной.

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

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

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

Система линейных алгебраических уравнений <math> A \mathbf{x} \ = \mathbf{b} </math> эквивалентна системе <math>  C A \mathbf{x} \ = C \mathbf{b} </math>, где <math>C</math> — [[невырожденная матрица]]. В частности, если сама матрица <math>A</math> — невырожденная, и для неё существует [[обратная матрица]] <math> A^{-1} </math>, то решение системы уравнений можно формально записать в виде <math> \mathbf{x} = A^{-1} \mathbf{b} </math>.

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

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

Итерационные методы устанавливают процедуру уточнения определённого начального приближения к решению. При выполнении условий сходимости они позволяют достичь любой точности просто повторением итераций. Преимущество этих методов в том, что часто они позволяют достичь решения с заранее заданной точностью быстрее, а также позволяют решать большие системы уравнений. Суть этих методов состоит в том, чтобы найти неподвижную точку матричного уравнения
: <math> \mathbf{x} = A^\prime \mathbf{x} + \mathbf{b}^\prime </math>,

эквивалентного начальной системе линейных алгебраических уравнений. При итерации <math> \mathbf{x} </math> в правой части уравнения заменяется, например, в методе Якоби (метод простой итерации) приближение, найденное на предыдущем шаге:
: <math> \mathbf{x}_{n+1} = A^\prime \mathbf{x}_n + \mathbf{b}^\prime </math>.

Итерационные методы делятся на несколько типов, в зависимости от применяемого подхода:
* Основанные на расщеплении: <math>(M-N)\mathbf{x}=\mathbf{b}\Leftrightarrow M\mathbf{x}=N\mathbf{x}+\mathbf{b} \Rightarrow M\mathbf{x}^{n+1}=N\mathbf{x}^n+\mathbf{b}</math>
* Вариационного типа: <math>A\mathbf{x}=\mathbf{b}\Rightarrow \|A\mathbf{x}-\mathbf{b}\|\rightarrow \min</math>
* Проекционного типа: <math>A\mathbf{x}=\mathbf{b}\Rightarrow (A\mathbf{x},\mathbf{m})=(\mathbf{b},\mathbf{m}) \forall\mathbf{m}</math>

Среди итерационных методов:
* [[Метод Якоби]] ([[метод простой итерации]])
* [[Метод Зейделя|Метод Гаусса — Зейделя]]
* [[Метод релаксации]]
* [[Многосеточный метод]]
* [[Метод Монтанте]]
* [[Метод Абрамова]] (пригоден для решения небольших СЛАУ)
* {{Не переведено|Метод обобщённых минимальных невязок||en|Generalized minimal residual method}}
* [[Метод бисопряжённых градиентов]]
* [[Стабилизированный метод бисопряжённых градиентов]]
* {{Не переведено|Квадратичный метод бисопряжённых градиентов||en|Biconjugate gradient method}}
* [[Метод квази-минимальных невязок]] ([[QMR]])
* [[Метод вращений]]<ref>{{книга|ссылка=|автор=Вержбицкий В. М.|заглавие=Основы численных методов|ответственный=|год=2009|место=М.|издательство=[[Высшая школа (издательство)|Высшая школа]]|том=|страницы=80—84|страниц=840|isbn=9785060061239}}</ref>

== Примечания ==
{{примечания}}

== Ссылки ==
* {{книга |автор=Куксенко С. П., Газизов Т. Р. |заглавие=Итерационные методы решения системы линейных алгебраических уравнений с плотной матрицей |место=Томск |издательство=[[Томский государственный университет]] |год=2007 |страниц=208 |isbn=5-94621-226-5}}
* {{книга |автор=Форсайт Дж., Молер К.|заглавие=Численное решение систем линейных алгебраических уравнений |место=Москва |издательство=[[Мир (издательство)|Мир]] |год=1969 |страниц=166 |isbn=}}

{{Методы решения СЛАУ}}
{{Вектора и матрицы}}

[[Категория:Линейная алгебра]]
[[Категория:Алгебраические уравнения]]
[[Категория:Методы решения СЛАУ|*]]
[[Категория:Численные методы линейной алгебры]]