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

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

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

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

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

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

Соглашения и определенияПравить

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

$\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+\cdots <!--\; \cdots \; -->+a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots <!--\; \cdots \; -->+a_{2n}{x}_n=b_2\\ \dots <!--\; \dots \; -->\\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots <!--\; \cdots \; -->+a_{mn}{x}_n=b_m\end{array}$${\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}}$ 

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

Система называется однородной, если все её свободные члены равны нулю ($b_1=b_2=\cdots <!--\; \cdots \; -->=b_m=0$$b_{1}=b_{2}=\dots =b_{m}=0$ ), иначе — неоднородной.

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

Решение системы линейных алгебраических уравнений — совокупность $n$$n$  чисел $c_1,c_2,\dots <!--\; \dots \; -->,c_n$$c_{1},c_{2},\dots ,c_{n}$ , таких что их соответствующая подстановка вместо $x_1,x_2,\dots <!--\; \dots \; -->,x_n$$x_{1},x_{2},\dots ,x_{n}$  в систему обращает все её уравнения в тождества.

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

Матричная формаПравить

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

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

или:

$Ax=b$$Ax = b$ .

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

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

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

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

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

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

Методы решенияПравить

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

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

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

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

$\mathbf{x}=A^{\mathrm{\prime <!--\; \prime \; -->}}\mathbf{x}+{\mathbf{b}}^{\mathrm{\prime <!--\; \prime \; -->}}$$\mathbf {x} =A^{\prime }\mathbf {x} +\mathbf {b} ^{\prime }$ ,

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

${\mathbf{x}}_{n+1}=A^{\mathrm{\prime <!--\; \prime \; -->}}{\mathbf{x}}_n+{\mathbf{b}}^{\mathrm{\prime <!--\; \prime \; -->}}$$\mathbf {x} _{n+1}=A^{\prime }\mathbf {x} _{n}+\mathbf {b} ^{\prime }$ .

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

• Основанные на расщеплении: $(M-<!--\; -\; -->N)\mathbf{x}=\mathbf{b}\iff <!--\; \iff \; -->M\mathbf{x}=N\mathbf{x}+\mathbf{b}\Rightarrow <!--\; \Rightarrow \; -->M{\mathbf{x}}^{n+1}=N{\mathbf{x}}^n+\mathbf{b}$$(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}$ 
• Вариационного типа: $A\mathbf{x}=\mathbf{b}\Rightarrow <!--\; \Rightarrow \; -->\Vert <!--\; \Vert \; -->A\mathbf{x}-<!--\; -\; -->\mathbf{b}\Vert <!--\; \Vert \; -->\to <!--\; \to \; -->min$$A\mathbf {x} =\mathbf {b} \Rightarrow \|A\mathbf {x} -\mathbf {b} \|\rightarrow \min$ 
• Проекционного типа: $A\mathbf{x}=\mathbf{b}\Rightarrow <!--\; \Rightarrow \; -->(A\mathbf{x},\mathbf{m})=(\mathbf{b},\mathbf{m})\mathrm{\forall <!--\; \forall \; -->}\mathbf{m}$$A\mathbf {x} =\mathbf {b} \Rightarrow (A\mathbf {x} ,\mathbf {m} )=(\mathbf {b} ,\mathbf {m} )\forall \mathbf {m}$ 

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

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

СсылкиПравить

• Куксенко С. П., Газизов Т. Р. Итерационные методы решения системы линейных алгебраических уравнений с плотной матрицей. — Томск: Томский государственный университет, 2007. — 208 с. — ISBN 5-94621-226-5.
• Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. — Москва: Мир, 1969. — 166 с.