Главная
Новости
Строительство
Ремонт
Дизайн и интерьер
Полезные советы




05.05.2021


05.05.2021


01.05.2021


23.04.2021


22.04.2021





Яндекс.Метрика





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

19.12.2020

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

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

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

Известно обобщение понятия системы линейных алгебраических уравнений на случай бесконечного множества неизвестных (бесконечная система линейных алгебраических уравнений).

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

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

{ a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = b 2 … a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = b m {displaystyle {egin{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 {displaystyle m} — количество уравнений, а n {displaystyle n} — количество переменных, x 1 , x 2 , … , x n {displaystyle x_{1},x_{2},dots ,x_{n}} — неизвестные, которые надо определить, коэффициенты a 11 , a 12 , … , a m n {displaystyle a_{11},a_{12},dots ,a_{mn}} и свободные члены b 1 , b 2 , … , b m {displaystyle b_{1},b_{2},dots ,b_{m}} предполагаются известными. Индексы коэффициентов в системах линейных уравнений ( a i j {displaystyle a_{ij}} ) формируются по следующему соглашению: первый индекс ( i {displaystyle i} ) обозначает номер уравнения, второй ( j {displaystyle j} ) — номер переменной, при которой стоит этот коэффициент.

Система называется однородной, если все её свободные члены равны нулю ( b 1 = b 2 = … b m = 0 {displaystyle b_{1}=b_{2}=dots b_{m}=0} ), иначе — неоднородной.

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

Решение системы линейных алгебраических уравнений — совокупность n {displaystyle n} чисел c 1 , c 2 , … , c n {displaystyle c_{1},c_{2},dots ,c_{n}} , таких что их соответствующая подстановка вместо x 1 , x 2 , … , x n {displaystyle x_{1},x_{2},dots ,x_{n}} в систему обращает все её уравнения в тождества.

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

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

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

( a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ) ( x 1 x 2 ⋮ x n ) = ( b 1 b 2 ⋮ b m ) {displaystyle {egin{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}}{egin{pmatrix}x_{1}x_{2}vdots x_{n}end{pmatrix}}={egin{pmatrix}b_{1}b_{2}vdots b_{m}end{pmatrix}}}

или:

A x = b {displaystyle Ax=b} .

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

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

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

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

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

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

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

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

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

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

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

x = A ′ x + b ′ {displaystyle mathbf {x} =A^{prime }mathbf {x} +mathbf {b} ^{prime }} ,

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

x n + 1 = A ′ x n + b ′ {displaystyle mathbf {x} _{n+1}=A^{prime }mathbf {x} _{n}+mathbf {b} ^{prime }} .

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

  • Основанные на расщеплении: ( M − N ) x = b ⇔ M x = N x + b ⇒ M x n + 1 = N x n + b {displaystyle (M-N)mathbf {x} =mathbf {b} Leftrightarrow Mmathbf {x} =Nmathbf {x} +mathbf {b} Rightarrow Mmathbf {x} ^{n+1}=Nmathbf {x} ^{n}+mathbf {b} }
  • Вариационного типа: A x = b ⇒ ‖ A x − b ‖ → min {displaystyle Amathbf {x} =mathbf {b} Rightarrow |Amathbf {x} -mathbf {b} | ightarrow min }
  • Проекционного типа: A x = b ⇒ ( A x , m ) = ( b , m ) ∀ m {displaystyle Amathbf {x} =mathbf {b} Rightarrow (Amathbf {x} ,mathbf {m} )=(mathbf {b} ,mathbf {m} )forall mathbf {m} }

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

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