Русская Википедия:Метод Крамера
Ме́тод Крамера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно)[1].
Описание метода
Для системы <math>n</math> линейных уравнений с <math>n</math> неизвестными (над произвольным полем)
- <math>\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}</math>
с определителем матрицы системы <math> \Delta </math>, отличным от нуля, решение записывается в виде
- <math>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}</math>
(i-ый столбец матрицы системы заменяется столбцом свободных членов).
В другой форме правило Крамера формулируется так: для любых коэффициентов c1, c2, …, cn справедливо равенство:
- <math>(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}</math>
В такой форме метод Крамера справедлив без предположения, что <math>\Delta</math> отличен от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы <math>b_1,b_2,...,b_n</math> и <math>x_1,x_2,...,x_n</math>, либо набор <math>c_1,c_2,...,c_n</math> состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.
Пример
Система линейных уравнений с вещественными коэффициентами:
- <math>\begin{cases}
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{cases}</math>
- <math display="inline">\Delta=\begin{vmatrix}
a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{vmatrix},\ \ \Delta_x=\begin{vmatrix} b_1 & a_{12} & a_{13} \\ b_2 & a_{22} & a_{23} \\ b_3 & a_{32} & a_{33} \\ \end{vmatrix},\ \ </math>
- <math>
\Delta_y=\begin{vmatrix} a_{11} & b_1 & a_{13} \\ a_{21} & b_2 & a_{23} \\ a_{31} & b_3 & a_{33} \\ \end{vmatrix},\ \ \Delta_z=\begin{vmatrix} a_{11} & a_{12} & b_1 \\ a_{21} & a_{22} & b_2 \\ a_{31} & a_{32} & b_3 \\ \end{vmatrix}</math>
В определителях столбец коэффициентов при соответствующей неизвестной заменяется столбцом свободных членов системы.
Решение:
- <math>x=\frac{\Delta_x}{\Delta},\ \ y=\frac{\Delta_y}{\Delta},\ \ z=\frac{\Delta_z}{\Delta}</math>
Пример:
- <math>\begin{cases}
2x + 5y + 4z = 30\\ x + 3y + 2z = 150\\ 2x + 10y + 9z = 110\\ \end{cases}</math>
Определители:
- <math>\Delta=\begin{vmatrix}
2 & 5 & 4 \\ 1 & 3 & 2 \\ 2 & 10 & 9 \\ \end{vmatrix}=5,\ \ \Delta_x=\begin{vmatrix}30&5&4\\150&3&2\\ 110 & 10 & 9 \\ \end{vmatrix}=-760,\ \ </math>
- <math>
\Delta_y=\begin{vmatrix} 2 & 30 & 4 \\ 1 & 150 & 2 \\ 2 & 110 & 9 \\ \end{vmatrix}=1350,\ \ \Delta_z=\begin{vmatrix} 2 & 5 & 30 \\ 1 & 3 & 150 \\ 2 & 10 & 110 \\ \end{vmatrix}=-1270.</math> <math>x=-\frac{760}{5}=-152,\ \ y=\frac{1350}{5}=270,\ \ z=-\frac{1270}{5}=-254</math>
Вычислительная сложность
Метод Крамера требует вычисления <math>n+1</math> определителей порядка <math>n</math>. При использовании метода Гаусса для вычисления определителей метод имеет сложность по элементарным операциям сложения-умножения порядка <math>O(n^4)</math>, что сложнее, чем метод Гаусса при прямом решении системы. Поэтому метод, с точки зрения затрат времени на вычисления, считался непрактичным. Однако в 2010 году было показано, что метод Крамера может быть реализован со сложностью <math>O(n^3)</math>, сравнимой со сложностью метода Гаусса[2].
Литература
- Мальцев И. А. Основы линейной алгебры. — Изд. 3-е, перераб., М.: «Наука», 1970. — 400 c.
Примечания
См. также
- ↑ Шаблон:Cite web
- ↑ 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)
