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

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

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

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

 

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

 

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

 

В этой форме метод Крамера справедлив без предположения, что   отличен от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы   и  , либо набор   состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

Пример

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

 

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

 


 

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

Решение:

 

Пример:

 

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

 


 

 

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

Метод Крамера требует вычисления   определителей размерности  . При использовании метода Гаусса для вычисления определителей, метод имеет сложность по элементарным операциям сложения-умножения порядка  , что сложнее чем метод Гаусса при прямом решении системы. Поэтому метод, с точки зрения затрат времени на вычисления, считался непрактичным. Однако, в 2010 году было показано, что метод Крамера может быть реализован со сложностью  , сравнимой со сложностью метода ГауссаШаблон:-1.

Литература

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

Примечания

  1. Cramer, Gabriel. Introduction à l'Analyse des lignes Courbes algébriques (неопр.) 656–659. Geneva: Europeana (1750). Дата обращения: 18 мая 2012.

См. также