Введение
Формула решения систем линейных уравнений
В линейной алгебре правило Крамера — это явная формула для решения системы линейных уравнений, имеющей столько же уравнений, сколько неизвестных, и применимая, когда система имеет единственное решение. Она выражает решение через определители (квадратной) матрицы коэффициентов и матриц, полученных из неё заменой одного столбца на столбец свободных членов уравнений. Правило названо в честь Габриэля Крамера, опубликовавшего его для произвольного числа неизвестных в 1750 году, хотя Колин Маклорен также опубликовал частные случаи этого правила в 1748 году и, возможно, был знаком с ним ещё в 1729 году. Реализация правила Крамера в простейшей форме вычислительно неэффективна для систем, состоящих более чем из двух или трёх уравнений. В случае n уравнений с n неизвестными требуется вычисление n + 1 определителей, в то время как метод Гаусса даёт результат с той же вычислительной сложностью, что и вычисление одного определителя. Правило Крамера также может быть численно неустойчивым даже для систем 2×2. Однако правило Крамера можно реализовать с той же вычислительной сложностью, что и метод Гаусса (при этом последовательно требуется вдвое больше арифметических операций и достигается та же численная стабильность при применении одних и тех же матриц перестановок).
In linear algebra, Cramer's rule is an explicit formula for the solution of a system of linear equations with as many equations as unknowns, valid whenever the system has a unique solution. It expresses the solution in terms of the determinants of the (square) coefficient matrix and of matrices obtained from it by replacing one column by the column vector of right sides of the equations. It is named after Gabriel Cramer, who published the rule for an arbitrary number of unknowns in 1750, although Colin Maclaurin also published special cases of the rule in 1748, and possibly knew of it as early as 1729. Cramer's rule implemented in a naive way is computationally inefficient for systems of more than two or three equations. In the case of n equations in n unknowns, it requires computation of n + 1 determinants, while Gaussian elimination produces the result with the same computational complexity as the computation of a single determinant. Cramer's rule can also be numerically unstable even for 2×2 systems. However, Cramer's rule can be implemented with the same complexity as Gaussian elimination, (consistently requires twice as many arithmetic operations and has the same numerical stability when the same permutation matrices are applied).
Найти обратную матрицу
Пусть A — матрица размера n × n с элементами из поля F. Тогда
где adj(A) обозначает присоединенную матрицу, det(A) — определитель, а I — единичная матрица. Если det(A) не равен нулю, то обратная матрица к A равна
Это дает формулу для вычисления обратной матрицы A, при условии det(A) ≠ 0. Фактически, эта формула работает всякий раз, когда F является коммутативным кольцом, при условии, что det(A) является обратимым элементом. Если det(A) не является обратимым элементом, то матрица A не обратима над этим кольцом (однако она может быть обратима над большим кольцом, в котором некоторые необратимые элементы F могут быть обратимыми).
Программирование целыми числами
Правило Крамера может быть использовано для доказательства того, что задача целочисленного программирования, матрица ограничений которой является тотально унимодулярной, а вектор правой части – целочисленным, имеет целочисленные базисные решения. Это существенно упрощает решение задачи целочисленного программирования.
Обычные дифференциальные уравнения
Правило Крамера используется для вывода общего решения нехомогенного линейного дифференциального уравнения методом вариации параметров.
Доказательство абстрактной линейной алгеброй
Это перефразировка вышеуказанного доказательства на абстрактном языке. Рассмотрим отображение, где – это матрица, в которой в th-м столбце подставлен вектор , как в правиле Крамера. Благодаря линейности определителя по каждому столбцу, это отображение является линейным. Заметим, что оно переводит th-й столбец матрицы в th-й базисный вектор (с 1 на th-й позиции), поскольку определитель матрицы с повторяющимся столбцом равен 0. Таким образом, у нас есть линейное отображение, которое совпадает с обратной матрицей на столбцовом пространстве, а значит, совпадает с ней на линейной оболочке столбцового пространства. Поскольку матрица обратима, её столбцовые векторы порождают всё пространство , поэтому наше отображение действительно является обратным к отображению, определяемому правилом Крамера.
Несовместимые и неопределенные случаи
Система уравнений называется несовместной, когда она не имеет решений, и неопределённой, когда имеет более одного решения. Для линейных уравнений неопределённая система будет иметь бесконечно много решений (если она рассматривается над бесконечным полем), поскольку решения могут быть выражены через один или несколько параметров, которые могут принимать любые значения. Правило Крамера применимо в случае, когда главный определитель отличен от нуля. В случае 2×2, если главный определитель равен нулю, то система несовместна, если численные определители не равны нулю, или неопределённа, если численные определители равны нулю. Для систем 3×3 и более высокого порядка, единственное, что можно сказать, когда главный определитель равен нулю, состоит в том, что если хотя бы один из численных определителей не равен нулю, то система должна быть несовместной. Однако, равенство всех определителей нулю не означает, что система неопределённа. Простой пример, когда все определители равны нулю, но система всё равно несовместна, – это система 3×3: x+y+z=1, x+y+z=2, x+y+z=3.