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

Разделы:

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

{a11x1+a12x2+⋯+a1nxn=b1a21x1+a22x2+⋯+a2nxn=b2…am1x1+am2x2+⋯+amnxn=bm{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}}}

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}

(1)

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

Здесь m{displaystyle m} $m$ — количество уравнений, а n{displaystyle n} $n$ — количество неизвестных. x1, x2, …, xn — неизвестные, которые надо определить. a11, a12, …, amn — коэффициенты системы — и b1, b2, … bm — свободные члены — предполагаются известными[1]. Индексы коэффициентов (aij) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно[2].

Система (1) называется однородной, если все её свободные члены равны нулю (b1 = b2 = … = bm = 0), иначе — неоднородной.

Система (1) называется квадратной, если число m уравнений равно числу n неизвестных.

Решение системы (1) — совокупность n чисел c1, c2, …, cn, таких что подстановка каждого ci вместо xi в систему (1) обращает все её уравнения в тождества.

Система (1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у неё нет ни одного решения.

Совместная система вида (1) может иметь одно или более решений.

Решения c1(1), c2(1), …, cn(1) и c1(2), c2(2), …, cn(2) совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств:

c1(1) = c1(2), c2(1) = c2(2), …, cn(1) = cn(2).

Совместная система вида (1) называется определённой, если она имеет единственное решение; если же у неё есть хотя бы два различных решения, то она называется недоопределённой. Если уравнений больше, чем неизвестных, она называется переопределённой.

Содержание

1 Матричная форма
2 Эквивалентные системы линейных уравнений
3 Методы решения
- 3.1 Прямые методы
- 3.2 Итерационные методы
4 См. также
5 Примечания
6 Ссылки

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

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

(a11a12⋯a1na21a22⋯a2n⋮⋮⋱⋮am1am2⋯amn)(x1x2⋮xn)=(b1b2⋮bm){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}}}

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{displaystyle Ax=b}

Ax = b

Здесь A{displaystyle A}

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

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

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

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

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

Ax =b{displaystyle A{mathbf {x}} ={mathbf {b}}}

A bold{x} = bold{b}

эквивалентна системе

CAx =Cb{displaystyle CA{mathbf {x}} =C{mathbf {b}}}

C A bold{x} = C bold{b}

где C{displaystyle C}

$C$ — невырожденная матрица.

В частности, если сама матрица A{displaystyle A}

$A$ — невырожденная, и для неё существует обратная матрица A−1{displaystyle A^{-1}} $A^{-1}$ , то решение системы уравнений можно формально записать в виде

x=A−1b{displaystyle {mathbf {x}}=A^{-1}{mathbf {b}}}

bold{x} = A^{-1} bold{b}

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

Прямые методы дают алгоритм, по которому можно найти точное решение СЛАУ. И если бы точность была абсолютной, они бы нашли его. Реальная ЭВМ, естественно, работает с погрешностью, поэтому решение будет приближённым.

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

Прямые методы

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

Итерационные методы

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

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

bold{x} = A^prime bold{x} + bold{b}^prime

эквивалентного начальной системе линейных алгебраических уравнений. При итерации x{displaystyle {mathbf {x}}}

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

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

bold{x}_{n+1} = A^prime bold{x}_n + bold{b}^prime

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

Основанные на расщеплении: (M−N)x=b⇔Mx=Nx+b⇒Mxn+1=Nxn+b{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}}} $(M-N)bold{x}=bold{b}Leftrightarrow Mbold{x}=Nbold{x}+bold{b} Rightarrow Mbold{x}^{n+1}=Nbold{x}^n+bold{b}$
Вариационного типа: Ax=b⇒‖Ax−b‖→min{displaystyle A{mathbf {x}}={mathbf {b}}Rightarrow |A{mathbf {x}}-{mathbf {b}}|rightarrow min } $Abold{x}=bold{b}Rightarrow |Abold{x}-bold{b}|rightarrow min$
Проекционного типа: Ax=b⇒(Ax,m)=(b,m)∀m{displaystyle A{mathbf {x}}={mathbf {b}}Rightarrow (A{mathbf {x}},{mathbf {m}})=({mathbf {b}},{mathbf {m}})forall {mathbf {m}}} $Abold{x}=bold{b}Rightarrow (Abold{x},bold{m})=(bold{b},bold{m}) forallbold{m}$

Среди итерационных методов можно отметить самые популярные:

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

См. также

Примечания

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

Ссылки

Куксенко С. П., Газизов Т. Р. Итерационные методы решения системы линейных алгебраических уравнений с плотной матрицей. — Томск: Томский государственный университет, 2007. — 208 с. — ISBN 5-94621-226-5.
Решение СЛАУ онлайн