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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
(перенаправлено с «СЛАУ»)
Система линейных уравнений от трёх переменных определяет набор плоскостей. Точка пересечения является решением

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

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

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

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

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

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

[math]\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 \\ \dots\\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m \\ \end{cases} }[/math]

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

Система называется однородной, если все её свободные члены равны нулю ([math]\displaystyle{ b_1 = b_2 = \dots = b_m = 0 }[/math]), иначе — неоднородной.

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

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

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

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

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

[math]\displaystyle{ \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]\displaystyle{ Ax = b }[/math].

Здесь [math]\displaystyle{ A }[/math] — это матрица системы, [math]\displaystyle{ x }[/math] — столбец неизвестных, а [math]\displaystyle{ b }[/math] — столбец свободных членов. Если к матрице [math]\displaystyle{ A }[/math] приписать справа столбец свободных членов, то получившаяся матрица называется расширенной.

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

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

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

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

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

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

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

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

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

[math]\displaystyle{ \mathbf{x} = A^\prime \mathbf{x} + \mathbf{b}^\prime }[/math],

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

[math]\displaystyle{ \mathbf{x}_{n+1} = A^\prime \mathbf{x}_n + \mathbf{b}^\prime }[/math].

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

  • Основанные на расщеплении: [math]\displaystyle{ (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]\displaystyle{ A\mathbf{x}=\mathbf{b}\Rightarrow \|A\mathbf{x}-\mathbf{b}\|\rightarrow \min }[/math]
  • Проекционного типа: [math]\displaystyle{ A\mathbf{x}=\mathbf{b}\Rightarrow (A\mathbf{x},\mathbf{m})=(\mathbf{b},\mathbf{m}) \forall\mathbf{m} }[/math]

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

Примечания

  1. Ильин В. А., Позняк Э. Г. Линейная алгебра: Учебник для вузов. — 6-е изд., стер. — М.: Физматлит, 2004. — 280 с.
  2. Вержбицкий В. М. Основы численных методов. — М.: Высшая школа, 2009. — С. 80—84. — 840 с. — ISBN 9785060061239.

Ссылки

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