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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем основной матрицы (причём для таких уравнений решение существует и единственно). Назван по имени Габриэля Крамера (1704—1752), предложившего этот метод в 1750 г.[1]

Описание метода[править | править исходный текст]

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

\begin{cases}
a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n = b_1\\
a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n = b_2\\
\cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots\cdots\\ 
a_{n1}x_1 + a_{n2}x_2 + \ldots + a_{nn}x_n = b_n\\
\end{cases}

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

x_i=\frac{1}{\Delta}\begin{vmatrix} 
a_{11} & \ldots & a_{1,i-1} & b_1  & a_{1,i+1} & \ldots & a_{1n} \\
a_{21} & \ldots & a_{2,i-1} & b_2 & a_{2,i+1} & \ldots & a_{2n} \\
\ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\
a_{n-1,1} & \ldots & a_{n-1,i-1} & b_{n-1} & a_{n-1,i+1} & \ldots & a_{n-1,n} \\
a_{n1} & \ldots & a_{n,i-1} & b_n & a_{n,i+1} & \ldots & a_{nn} \\
\end{vmatrix}

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

(c_1x_1+c_2x_2+\dots+c_nx_n)\cdot\Delta = -\begin{vmatrix}
a_{11} & a_{12} & \ldots & a_{1n} & b_1\\
a_{21} & a_{22} & \ldots & a_{2n} & b_2\\
\ldots & \ldots & \ldots & \ldots & \ldots\\
a_{n1} & a_{n2} & \ldots & a_{nn} & b_n\\
c_{1}  & c_{2}  & \ldots & c_{n}  & 0\\
\end{vmatrix}

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

Пример[править | править исходный текст]

Система линейных уравнений:

\begin{cases}
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{cases}

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

\Delta=\begin{vmatrix}
a_{11} & a_{12} & a_{13} \\
a_{21} & a_{22} & a_{23} \\
a_{31} & a_{32} & a_{33} \\
\end{vmatrix},\ \ \Delta_1=\begin{vmatrix}
b_1 & a_{12} & a_{13} \\
b_2 & a_{22} & a_{23} \\
b_3 & a_{32} & a_{33} \\
\end{vmatrix},\ \



\Delta_2=\begin{vmatrix}
a_{11} & b_1 & a_{13} \\
a_{21} & b_2 & a_{23} \\
a_{31} & b_3 & a_{33} \\
\end{vmatrix},\ \ \Delta_3=\begin{vmatrix}
a_{11} & a_{12} & b_1 \\
a_{21} & a_{22} & b_2 \\
a_{31} & a_{32} & b_3 \\
\end{vmatrix}

Решение:

x_1=\frac{\Delta_1}{\Delta},\ \ x_2=\frac{\Delta_2}{\Delta},\ \ x_3=\frac{\Delta_3}{\Delta}

Пример:

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

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

\Delta=\begin{vmatrix}
2 & 5 & 4 \\
1 & 3 & 2 \\
2 & 10 & 9 \\
\end{vmatrix}=5,\ \ \Delta_1=\begin{vmatrix}30&5&4\\150&3&2\\
110 & 10 & 9 \\
\end{vmatrix}=-760,\ \



\Delta_2=\begin{vmatrix}
2 & 30 & 4 \\
1 & 150 & 2 \\
2 & 110 & 9 \\
\end{vmatrix}=1350,\ \ \Delta_3=\begin{vmatrix}
2 & 5 & 30 \\
1 & 3 & 150 \\
2 & 10 & 110 \\
\end{vmatrix}=-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), сравнимой со сложностью метода Гаусса[2].

Литература[править | править исходный текст]

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

Примечания[править | править исходный текст]

  1. Cramer, Gabriel. Introduction à l'Analyse des lignes Courbes algébriques (фр.) 656–659. Geneva: Europeana (1750). Проверено 18 мая 2012.
  2. Ken Habgood and Itamar Arel. 2010. Revisiting Cramer's rule for solving dense linear systems. In Proceedings of the 2010 Spring Simulation Multiconference (SpringSim '10)

См. также[править | править исходный текст]