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

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

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

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

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

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

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

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

[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 с.