Ме́тод Кра́мера (правило Крамера) — способ решения систем линейных алгебраических уравнений с числом уравнений равным числу неизвестных с ненулевым главным определителем матрицы коэффициентов системы (причём для таких уравнений решение существует и единственно).
Описание метода Для системы линейных уравнений с неизвестными (над произвольным полем)
с определителем матрицы системы , отличным от нуля, решение записывается в виде
(-й столбец матрицы системы заменяется столбцом свободных членов).
В другой форме правило Крамера формулируется так: для любых коэффициентов c1, c2, …, cn справедливо равенство:
В такой форме метод Крамера справедлив без предположения, что отличен от нуля, не требуется даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы и , либо набор состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.
Пример Система линейных уравнений с вещественными коэффициентами:
Определители:
В определителях столбец коэффициентов при соответствующей неизвестной заменяется столбцом свободных членов системы.
Решение:
Численный пример, дана система 3 уравнений:
Определители этой системы:
Отсюда:
Вычислительная сложность Метод Крамера требует вычисления определителей каждый порядка . При использовании метода Гаусса для вычисления определителей метод Крамера имеет сложность по элементарным операциям типа сложение-умножение порядка , что сложнее, чем метод Гаусса при прямом решении системы. Поэтому метод Крамера с точки зрения трудоёмкости вычислений считался непрактичным. Но в 1983 году был предложен алгоритм решения системы по правилу Крамера за операций Malaschonok G. I. Solution of a system of linear equations in an integral domain, Zh. Vychisl. Mat. i Mat. Fiz. V.23, No. 6, 1983, 1497—1500, (Russian), https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=4484&option_lang=rus U.S.S.R. Comput. Math. Math. Phys., 23:6 (1983), 133—135. (Engl.transl.) https://doi.org/10.48550/arXiv.1711.09452.
В этом алгоритме могут применяться перестановки точно такие, как в методе Гаусса. Поэтому, если использовать приближенные методы вычислений, то решение будет более устойчивым, чем решение по методу Гаусса так как первые шаги вычисляются без погрешности, пока еще нет округления чисел.
В 1991 году был опубликован алгоритм со сложностью операцийMalaschonok G. I. Algorithms for the solution of systems of linear equations in commutative rings. Effective methods in Algebraic Geometry, Progr. Math., V. 94, Birkhauser Boston, Boston, MA, 1991, 289—298. https://arxiv.org/abs/1711.11471.
В 1997 году был предложен алгоритм решения системы по правилу Крамера со сложностью равной сложности матричного умноженияMalashonok G. I. Recursive Method for the Solution of Systems of Linear Equations // Computational Mathematics / A. Sydow Ed. — Proceedings of the 15th IMACS World Congress, Vol. I. — Berlin: Wissenschaft & Technik Verlag, 1997. — P. 475—480. https://arxiv.org/abs/1703.10232. Например, для алгоритма умножения Штрассена, этот алгоритм вычисляет решение за операций.
Однако, англоязычные читатели эти алгоритмы не заметили и в 2010 году было показано, что метод Крамера может быть реализован со сложностью , сравнимой со сложностью метода Гаусса''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).
Применение
Решение систем 2×2 и 3×3 Любые методы, связанные с тождественными алгебраическими преобразованиями исходной системы уравнений, чреваты возникновением делением на ноль, а метод Крамера всегда даст решение, если оно существует.
Теоретические выкладки Метод Крамера широко используется в различных выкладках: Метод Лагранжа (дифференциальные уравнения). Неявно заданные системы: при и считаем, что x и y — зависимые переменные, u и v — независимые. Тогда, например, .
См. также Метод Гаусса
Примечания
Литература Мальцев А. И. Основы линейной алгебры. — Изд. 3-е, перераб. — М.: «Наука», 1970. — 400 c.
Категория:Методы решения СЛАУ Категория:Определители