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

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

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

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

$\{\begin{array}{c}{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}{c}{a}_{11}x+a_{12}y+a_{13}z=b_1\\ a_{21}x+a_{22}y+a_{23}z=b_2\\ a_{31}x+a_{32}y+a_{33}z=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 }}_x=\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 }}_y=\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 }}_z=\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=\frac{{\mathrm{\Delta }}_x}{\mathrm{\Delta }},y=\frac{{\mathrm{\Delta }}_y}{\mathrm{\Delta }},z=\frac{{\mathrm{\Delta }}_z}{\mathrm{\Delta }}$

Пример:

$\{\begin{array}{c}2x+5y+4z=30\\ x+3y+2z=150\\ 2x+10y+9z=110\end{array}$

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

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

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

$x=-\frac{760}{5}=-152,y=\frac{1350}{5}=270,z=-\frac{1270}{5}=-254$

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

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

Применение

Решение систем 2×2 и 3×3

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

Теоретические выкладки

Метод Крамера широко используется в различных выкладках:

• Метод Лагранжа (дифференциальные уравнения)
• Неявно заданные системы: при $F(x,y,u,v)=0$ и $G(x,y,u,v)=0$ считаем, что x и y — зависимые переменные, u и v — независимые. Тогда, например, $\frac{\partial x}{\partial u}=\frac{\left|\begin{array}{cc}-\frac{\partial F}{\partial u}& \frac{\partial F}{\partial y}\\ -\frac{\partial G}{\partial u}& \frac{\partial G}{\partial y}\end{array}\right|}{\left|\begin{array}{cc}\frac{\partial F}{\partial x}& \frac{\partial F}{\partial y}\\ \frac{\partial G}{\partial x}& \frac{\partial G}{\partial y}\end{array}\right|}$.

Литература

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

См. также

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