wiki

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

Разделы:

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

Содержание

1 Описание метода
2 Пример
3 Вычислительная сложность
4 Литература
5 Примечания
6 См. также

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

Для системы n{displaystyle n}

$n$ линейных уравнений с n{displaystyle n} $n$ неизвестными (над произвольным полем)

{a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯an1x1+an2x2+…+annxn=bn{displaystyle {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}}}

{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}}

с определителем матрицы системы Δ{displaystyle Delta }

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

xi=1Δ|a11…a1,i−1b1a1,i+1…a1na21…a2,i−1b2a2,i+1…a2n…………………an−1,1…an−1,i−1bn−1an−1,i+1…an−1,nan1…an,i−1bnan,i+1…ann|{displaystyle 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}}}

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 справедливо равенство:

(c1x1+c2x2+⋯+cnxn)⋅Δ=−|a11a12…a1nb1a21a22…a2nb2……………an1an2…annbnc1c2…cn0|{displaystyle (c_{1}x_{1}+c_{2}x_{2}+dots +c_{n}x_{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}}}

(c_{1}x_{1}+c_{2}x_{2}+dots +c_{n}x_{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}}

В этой форме метод Крамера справедлив без предположения, что Δ{displaystyle Delta }

$Delta$ отличен от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы b1,b2,…,bn{displaystyle b_{1},b_{2},…,b_{n}} $b_{1},b_{2},...,b_{n}$ и x1,x2,…,xn{displaystyle x_{1},x_{2},…,x_{n}} $x_{1},x_{2},...,x_{n}$ , либо набор c1,c2,…,cn{displaystyle c_{1},c_{2},…,c_{n}} $c_{1},c_{2},...,c_{n}$ состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

Пример

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

{a11x1+a12x2+a13x3=b1a21x1+a22x2+a23x3=b2a31x1+a32x2+a33x3=b3{displaystyle {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}}}

{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}}

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

Δ=|a11a12a13a21a22a23a31a32a33|, Δ1=|b1a12a13b2a22a23b3a32a33|, {displaystyle 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 ={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}},

Δ2=|a11b1a13a21b2a23a31b3a33|, Δ3=|a11a12b1a21a22b2a31a32b3|{displaystyle 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}}}

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}}

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

Решение:

x1=Δ1Δ, x2=Δ2Δ, x3=Δ3Δ{displaystyle x_{1}={frac {Delta _{1}}{Delta }}, x_{2}={frac {Delta _{2}}{Delta }}, x_{3}={frac {Delta _{3}}{Delta }}}

x_{1}={frac {Delta _{1}}{Delta }}, x_{2}={frac {Delta _{2}}{Delta }}, x_{3}={frac {Delta _{3}}{Delta }}

Пример:

{2×1+5×2+4×3=30×1+3×2+2×3=1502×1+10×2+9×3=110{displaystyle {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}}}

{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}}

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

Δ=|2541322109|=5, Δ1=|305415032110109|=−760, {displaystyle 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 ={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,

Δ2=|23041150221109|=1350, Δ3=|253013150210110|=−1270.{displaystyle 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.}

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.

x1=−7605=−152, x2=13505=270, x3=−12705=−254{displaystyle x_{1}=-{frac {760}{5}}=-152, x_{2}={frac {1350}{5}}=270, x_{3}=-{frac {1270}{5}}=-254}

$x_{1}=-{frac {760}{5}}=-152, x_{2}={frac {1350}{5}}=270, x_{3}=-{frac {1270}{5}}=-254$

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

Метод Крамера требует вычисления n+1{displaystyle n+1}

$n+1$ определителей размерности n×n{displaystyle ntimes n} $ntimes n$ . При использовании метода Гаусса для вычисления определителей, метод имеет сложность по элементарным операциям сложения-умножения порядка O(n4){displaystyle O(n^{4})} $O(n^{4})$ , что сложнее чем метод Гаусса при прямом решении системы. Поэтому метод, с точки зрения затрат времени на вычисления, считался непрактичным. Однако, в 2010 году было показано, что метод Крамера может быть реализован со сложностью O(n3){displaystyle O(n^{3})} $O(n^{3})$ , сравнимой со сложностью метода Гаусса Шаблон:-1.

Литература

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

Примечания

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

См. также

Метод Гаусса