В линейной алгебре , правило Крамера явная формула для решения системы линейных уравнений с таким количеством уравнений как неизвестные, действительным , когда система имеет единственное решение. Он выражает решение в терминах определителей (квадратной) матрицы коэффициентов и матриц, полученных из нее путем замены одного столбца вектор-столбцом правых частей уравнений. Он назван в честь Габриэля Крамера (1704–1752), который опубликовал правило для произвольного числа неизвестных в 1750 году, [1] [2], хотя Колин Маклорен также опубликовал частные случаи правила в 1748 году.[3] (и, возможно, знал об этом еще в 1729 году). [4] [5] [6]
Правило Крамера, реализованное наивно, вычислительно неэффективно для систем, состоящих из более чем двух или трех уравнений. [7] В случае n уравнений с n неизвестными требуется вычисление n + 1 определителя, в то время как исключение Гаусса дает результат с той же вычислительной сложностью, что и вычисление одного определителя. [8] [9] [ требуется проверка ] Правило Крамера также может быть численно нестабильным даже для систем 2 × 2. [10] Однако недавно было показано, что правило Крамера может быть реализовано за время O ( n 3 ), [11] что сравнимо с более распространенными методами решения систем линейных уравнений, такими как метод исключения Гаусса (последовательно требующий 2,5 раза столько же арифметических операций для всех размеров матриц), демонстрируя при этом сопоставимую числовую стабильность в большинстве случаев.
Общий случай
Рассмотрим систему из n линейных уравнений для n неизвестных, представленных в виде матричного умножения следующим образом:
где матрица A размера n × n имеет ненулевой определитель, а векторвектор-столбец переменных. Тогда теорема утверждает, что в этом случае система имеет единственное решение, индивидуальные значения неизвестных которого определяются выражением:
где матрица, образованная заменой i-го столбца матрицы A вектором-столбцом b .
Более общий вариант правила Крамера [12] рассматривает матричное уравнение
где матрица A размера n × n имеет ненулевой определитель, а X , B - матрицы размера n × m . Данные последовательности а также , позволять - подматрица размера k × k матрицы X со строками в и столбцы в . Позволять- матрица размера n × n, образованная заменойстолбец A настолбец B , для всех. потом
В случае , это сводится к нормальному правилу Крамера.
Правило справедливо для систем уравнений с коэффициентами и неизвестными в любом поле , а не только в действительных числах .
Доказательство
Доказательство правила Крамера использует следующие свойства определителей : линейность по отношению к любому заданному столбцу и тот факт, что определитель равен нулю, когда два столбца равны, что подразумевается тем свойством, что знак определителя меняется при переключении две колонки.
Зафиксируйте индекс j столбца. Линейность означает, что если мы рассматриваем только столбец j в качестве переменной (произвольно фиксируя остальные), результирующая функция [ требуется пояснение ] R n → R (при условии, что элементы матрицы находятся в R ) может быть задана матрицей с одной строкой и n столбцами , действующий на столбец j . Фактически это именно то, что делает разложение Лапласа , записывая det ( A ) = C 1 a 1, j + ⋯ + C n a n, j для некоторых коэффициентов C 1 , ..., C n, которые зависят от столбцов A кроме столбца j (точное выражение для этих сомножителей здесь не важно). Значение Det ( ) является то результатом применения одной строки матрицы L ( J ) = ( С 1 С 2 ⋯ С п ) к колонке J из A . Если L ( j ) применяется к любому другому столбцу k в A , то результатом является определитель матрицы, полученной из A путем замены столбца j копией столбца k , поэтому результирующий определитель равен 0 (случай двух равных столбцы).
Теперь рассмотрим систему из n линейных уравнений от n неизвестных., матрица коэффициентов которого равна A , при этом det ( A ) считается ненулевым:
Если объединить эти уравнения, взяв C 1, умноженное на первое уравнение, плюс C 2, умноженное на второе, и так далее, пока C n умножить на последнее, тогда коэффициент при x j станет C 1 a 1, j + ⋯ + C n a n, j = det ( A ) , а коэффициенты всех остальных неизвестных становятся равными 0; левая часть становится просто det ( A ) x j . Правая часть - это C 1 b 1 + ⋯ + C n b n , то есть L ( j ), примененная к вектору-столбцу b правой части b i . Фактически здесь было умножено матричное уравнение A x = b слева на L ( j ) . Разделив на ненулевое число det ( A ), находим следующее уравнение, необходимое для удовлетворения системы:
Но по построению числитель является определителем матрицы, полученной из A заменой столбца j на b , поэтому мы получаем выражение правила Крамера как необходимое условие для решения. Эту же процедуру можно повторить для других значений j, чтобы найти значения для других неизвестных.
Единственное, что осталось доказать, это то, что эти значения неизвестных, единственно возможные, действительно вместе образуют решение. Но если матрица обратим с обратным А -1 , то х = -1 Ь будет решением, показывая тем самым свое существование. Чтобы увидеть, что A обратима, когда det ( A ) отличен от нуля, рассмотрим матрицу M размера n × n, полученную путем наложения однострочных матриц L ( j ) друг на друга для j = 1, ..., n (это дает сопряженную матрицу для A ). Было показано, что L ( j ) A = (0 ⋯ 0 det ( A ) 0 ⋯ 0), где det ( A ) появляется в позиции j ; отсюда следует, что MA = det ( A ) I n . Следовательно,
Пусть быть п × п матрица с элементами в поле F . потом
где adj ( A ) обозначает сопряженную матрицу , det ( A ) - определитель, а I - единичная матрица . Если det ( A ) отличен от нуля, то обратная матрица A равна
Это дает формулу, обратную A , при условии, что det ( A ) ≠ 0 . Фактически, эта формула работает, когда F - коммутативное кольцо , при условии, что det ( A ) - единица . Если det ( A ) не является единицей, то A не обратим над кольцом (он может быть обратимым над большим кольцом, в котором некоторые неединичные элементы F могут быть обратимы).
Приложения
Явные формулы для малых систем
Рассмотрим линейную систему
который в матричном формате
Предположим, что a 1 b 2 - b 1 a 2 ненулевое. Затем, с помощью определителей , х и у могут быть найдены с правилом Крамера как
Правила для матриц 3 × 3 аналогичны. Дано
который в матричном формате
Тогда значения x, y и z можно найти следующим образом:
Правило Крамера можно использовать для доказательства того, что задача целочисленного программирования , матрица ограничений которой полностью унимодулярна, а правая часть является целой, имеет целочисленные базовые решения. Это значительно упрощает решение целочисленной программы.
Обыкновенные дифференциальные уравнения
Правило Крамера используется для вывода общего решения неоднородного линейного дифференциального уравнения методом вариации параметров .
Геометрическая интерпретация
Геометрическая интерпретация правила Крамера. Площади второго и третьего заштрихованных параллелограммов одинаковы, а второй - раз первый. Из этого равенства следует правило Крамера.
Правило Крамера имеет геометрическую интерпретацию, которую также можно рассматривать как доказательство или просто для понимания его геометрической природы. Эти геометрические аргументы работают в целом, а не только в случае представленных здесь двух уравнений с двумя неизвестными.
Учитывая систему уравнений
его можно рассматривать как уравнение между векторами
Площадь параллелограмма, определяемая а также задается определителем системы уравнений:
В общем случае , когда имеется больше переменных и уравнений, определителя п векторов длины п даст объем этого параллелепипеда определяется теми векторами в п -му мерное евклидово пространства .
Следовательно, площадь параллелограмма, определяемая а также должно быть умноженное на площадь первого, так как одна из сторон была умножена на этот коэффициент. Теперь этот последний параллелограмм, по принципу Кавальери , имеет ту же площадь, что и параллелограмм, определяемый формулой а также
Приравнивание площадей этого последнего и второго параллелограмма дает уравнение
из которого следует правило Крамера.
Прочие доказательства
Доказательство абстрактной линейной алгеброй
Это повторение приведенного выше доказательства на абстрактном языке.
Рассмотрим карту где матрица с участием заменен в -й столбец, как в правиле Крамера. Из-за линейности определителя в каждом столбце эта карта является линейной. Обратите внимание, что он отправляет-й столбец к й базисный вектор (с 1 в -е место), потому что определитель матрицы с повторяющимся столбцом равен 0. Итак, у нас есть линейное отображение, которое согласуется с обратным к на пространстве столбцов; следовательно, он согласен сна промежутке между колонками. С обратима, векторы-столбцы охватывают все , так что наша карта действительно обратна . Правило Крамера следует.
Краткое доказательство
Краткое доказательство правила Крамера [14] можно дать, заметив, что - определитель матрицы
С другой стороны, предполагая, что наша исходная матрица A обратима, эта матрица есть столбцы , где является п -го столбца матрицы А . Напомним, что матрица есть столбцы , и поэтому . Следовательно, используя, что определитель произведения двух матриц является произведением определителей, мы имеем
Доказательство для других похож.
Несовместимые и неопределенные случаи
Система уравнений называется несовместимой или несовместимой, когда нет решений, и неопределенной, когда существует более одного решения. Для линейных уравнений неопределенная система будет иметь бесконечно много решений (если она находится над бесконечным полем), поскольку решения могут быть выражены через один или несколько параметров, которые могут принимать произвольные значения.
Правило Крамера применяется к случаю, когда определитель коэффициента отличен от нуля. В случае 2 × 2, если определитель коэффициента равен нулю, то система несовместима, если определители числителя не равны нулю, или неопределенная, если определители числителя равны нулю.
Для систем 3 × 3 или выше единственное, что можно сказать, когда определитель коэффициента равен нулю, - это то, что если какой-либо из определителей числителя отличен от нуля, то система должна быть несовместимой. Однако наличие всех определителей нуля не означает, что система неопределенна. Простым примером, когда все определители обращаются в нуль (равны нулю), но система по-прежнему несовместима, является система 3 × 3 x + y + z = 1, x + y + z = 2, x + y + z = 3.
Рекомендации
^ Крамер, Габриэль (1750). «Introduction à l'Analyse des lignes Courbes algébriques» (на французском языке). Женева: Europeana. С. 656–659 . Проверено 18 мая 2012 .
^Косинский, А.А. (2001). «Правило Крамера принадлежит Крамеру». Математический журнал . 74 (4): 310–312. DOI : 10.2307 / 2691101 . JSTOR 2691101 .
^Маклаурин, Колин (1748). Трактат по алгебре в трех частях .
^Бойер, Карл Б. (1968). История математики (2-е изд.). Вайли. п. 431.
^Кац, Виктор (2004). История математики (Краткое изд.). Pearson Education. С. 378–379.
^Хедман, Брюс А. (1999). «Более ранняя дата для« правила Крамера » » (PDF) . Historia Mathematica . 26 (4): 365–368. DOI : 10.1006 / hmat.1999.2247 .
^Джо Д. Хоффман; Стивен Франкель (2001). Численные методы для инженеров и ученых, второе издание . CRC Press. п. 30. ISBN 978-0-8247-0443-8.
^Томас С. Шорс (2007). Прикладная линейная алгебра и матричный анализ . Springer Science & Business Media. п. 132. ISBN 978-0-387-48947-6.
^Николас Дж. Хайэм (2002). Точность и устойчивость численных алгоритмов: второе издание . СИАМ. п. 13. ISBN 978-0-89871-521-7.
^Кен Хабгуд; Итамар Арель (2012). «Основанное на конденсации применение правила Крамера для решения крупномасштабных линейных систем» (PDF) . Журнал дискретных алгоритмов . 10 : 98–109. DOI : 10.1016 / j.jda.2011.06.007 .
^Чжиминг Гонг; М. Алдин; Л. Эльснер (2002). «Заметка об обобщенном правиле Крамера» . Линейная алгебра и ее приложения . 340 (1–3): 253–254. DOI : 10.1016 / S0024-3795 (01) 00469-4 .
^Леви-Чивита, Туллио (1926). Абсолютное дифференциальное исчисление (тензорное исчисление) . Дувр. С. 111–112. ISBN 9780486634012.
^Робинсон, Стивен М. (1970). «Краткое доказательство правила Крамера». Математический журнал . 43 (2): 94–95. DOI : 10.1080 / 0025570X.1970.11976018 .
Внешние ссылки
Доказательство правила Крамера
WebApp описательно решает системы линейных уравнений с помощью правила Крамера [ постоянная мертвая ссылка ]