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

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

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

Содержание

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

Для системы 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), сравнимой со сложностью метода Гаусса.[1]

Примечания

  1. 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).

Wikimedia Foundation. 2010.

Смотреть что такое "Метод Крамера" в других словарях:

  • Метод простой итерации — Содержание 1 Постановка задачи 2 Численные методы решения уравнений 2.1 Метод простой итерации …   Википедия

  • Метод Гаусса — У этого термина существуют и другие значения, см. Метод Гаусса (оптимизация). Метод Гаусса[1]  классический метод решения системы линейных алгебраических уравнений (СЛАУ). Это метод последовательного исключения переменных, когда с помощью… …   Википедия

  • Крамера-Тисдалла метод — (В. Kramer, род. в 1887 г., амер. врач; F. Tisdall, род. в 1893 г., амер. врач) косвенный метод определения калия в моче по количеству осадка, образующегося при добавлении кобальтгексанитрита натрия …   Большой медицинский словарь

  • Крамера катетеризация слуховой трубы — (W. Kramer, 1801 1875, нем. оториноларинголог) метод катетеризации слуховой (евстахиевой) трубы; в качестве ориентира при введении катетера служит задняя поверхность мягкого неба …   Большой медицинский словарь

  • Правило Крамера — Метод Крамера (Крамера правило) способ решения квадратных систем линейных алгебраических уравнений с ненулевым определителем основной матрицы (причём для таких уравнений решение существует и единственно). Создан Габриэлем Крамером в 1750 году.… …   Википедия

  • Формулы Крамера — Метод Крамера (Крамера правило) способ решения квадратных систем линейных алгебраических уравнений с ненулевым определителем основной матрицы (причём для таких уравнений решение существует и единственно). Создан Габриэлем Крамером в 1750 году.… …   Википедия

  • МАКСИМАЛЬНОГО ПРАВДОПОДОБИЯ МЕТОД — метод оценивания неизвестных параметров для распределения случайной величины c по наблюдению её реализаций при параметрич. анализе данных.M. п. м. был предложен P. Э. Фишером (R. A. Fisher) в 1912 и формулируется след, образом. Пусть плотность… …   Физическая энциклопедия

  • Зелигмана-Крамера метод — (М. Seligman, амер. биохимик; P. Kramer) колориметрический метод количественного определения активности липазы в сыворотке крови, основанный на появлении красного окрашивания при взаимодействии продукта расщепления 2 нафтилмиристата сывороточной… …   Большой медицинский словарь

  • Численное решение системы нелинейных уравнений — Содержание 1 Постановка задачи 2 Численные методы решения уравнений 2.1 Метод простой итерации …   Википедия

  • Крамер, Габриэль — В Википедии есть статьи о других людях с такой фамилией, см. Крамер. Габриэль Крамер Gabriel Cramer …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»