Метод Крамера

Ме́тод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно).

Описание метода

Для системы $n$ линейных уравнений с $n$ неизвестными (над произвольным полем)

$\{\begin{array}{l}{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\\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\ a_{n1}{x}_1+a_{n2}{x}_2+\dots +a_{nn}{x}_n=b_n\\ \end{array}$

с определителем матрицы системы $\mathrm{\Delta }$, отличным от нуля, решение записывается в виде

$x_i=\frac{1}{\mathrm{\Delta }}\left|\begin{array}{ccccccc}{a}_{11}& \dots & a_{1,i-1}& b_1& a_{1,i+1}& \dots & a_{1n}\\ a_{21}& \dots & a_{2,i-1}& b_2& a_{2,i+1}& \dots & a_{2n}\\ \dots & \dots & \dots & \dots & \dots & \dots & \dots \\ a_{n-1,1}& \dots & a_{n-1,i-1}& b_{n-1}& a_{n-1,i+1}& \dots & a_{n-1,n}\\ a_{n1}& \dots & a_{n,i-1}& b_n& a_{n,i+1}& \dots & a_{nn}\\ \end{array}\right|$

(i-ый столбец матрицы системы заменяется столбцом свободных членов).
В другой форме правило Крамера формулируется так: для любых коэффициентов c₁, c₂, …, c_n справедливо равенство:

$(c_1{x}_1+c_2{x}_2+\dots +c_n{x}_n)\cdot \mathrm{\Delta }=-\left|\begin{array}{ccccc}{a}_{11}& a_{12}& \dots & a_{1n}& b_1\\ a_{21}& a_{22}& \dots & a_{2n}& b_2\\ \dots & \dots & \dots & \dots & \dots \\ a_{n1}& a_{n2}& \dots & a_{nn}& b_n\\ c_1& c_2& \dots & c_n& 0\\ \end{array}\right|$

В этой форме метод Крамера справедлив без предположения, что $\mathrm{\Delta }$ отличен от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы $b_1,b_2,...,b_n$ и $x_1,x_2,...,x_n$, либо набор $c_1,c_2,...,c_n$ состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

Пример

Система линейных уравнений с вещественными коэффициентами:

$\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+a_{13}{x}_3=b_1\\ a_{21}{x}_1+a_{22}{x}_2+a_{23}{x}_3=b_2\\ a_{31}{x}_1+a_{32}{x}_2+a_{33}{x}_3=b_3\\ \end{array}$

Определители:

$\mathrm{\Delta }=\left|\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\\ \end{array}\right|,{\mathrm{\Delta }}_1=\left|\begin{array}{ccc}{b}_1& a_{12}& a_{13}\\ b_2& a_{22}& a_{23}\\ b_3& a_{32}& a_{33}\\ \end{array}\right|,$

${\mathrm{\Delta }}_2=\left|\begin{array}{ccc}{a}_{11}& b_1& a_{13}\\ a_{21}& b_2& a_{23}\\ a_{31}& b_3& a_{33}\\ \end{array}\right|,{\mathrm{\Delta }}_3=\left|\begin{array}{ccc}{a}_{11}& a_{12}& b_1\\ a_{21}& a_{22}& b_2\\ a_{31}& a_{32}& b_3\\ \end{array}\right|$

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

Решение:

$x_1=\frac{{\mathrm{\Delta }}_1}{\mathrm{\Delta }},x_2=\frac{{\mathrm{\Delta }}_2}{\mathrm{\Delta }},x_3=\frac{{\mathrm{\Delta }}_3}{\mathrm{\Delta }}$

Пример:

$\{\begin{array}{l}2x_1+5x_2+4x_3=30\\ x_1+3x_2+2x_3=150\\ 2x_1+10x_2+9x_3=110\\ \end{array}$

Определители:

$\mathrm{\Delta }=\left|\begin{array}{ccc}2& 5& 4\\ 1& 3& 2\\ 2& 10& 9\\ \end{array}\right|=5,{\mathrm{\Delta }}_1=\left|\begin{array}{ccc}30& 5& 4\\ 150& 3& 2\\ 110& 10& 9\\ \end{array}\right|=-760,$

${\mathrm{\Delta }}_2=\left|\begin{array}{ccc}2& 30& 4\\ 1& 150& 2\\ 2& 110& 9\\ \end{array}\right|=1350,{\mathrm{\Delta }}_3=\left|\begin{array}{ccc}2& 5& 30\\ 1& 3& 150\\ 2& 10& 110\\ \end{array}\right|=-1270.$

$x_1=-\frac{760}{5}=-152,x_2=\frac{1350}{5}=270,x_3=-\frac{1270}{5}=-254$

Вычислительная сложность

Метод Крамера требует вычисления $n+1$ определителей размерности $n\times n$. При использовании метода Гаусса для вычисления определителей метод имеет сложность по элементарным операциям сложения-умножения порядка $O(n^4)$, что сложнее, чем метод Гаусса при прямом решении системы. Поэтому метод, с точки зрения затрат времени на вычисления, считался непрактичным. Однако в 2010 году было показано, что метод Крамера может быть реализован со сложностью $O(n^3)$, сравнимой со сложностью метода Гаусса.

Литература

• Мальцев И. А. Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.

См. также

• Метод Гаусса