Метод Крамера и метод Гаусса

Два основных практических способа решения систем линейных уравнений — метод Крамера (через определители) и метод Гаусса (последовательное исключение неизвестных). Метод Крамера применим только к квадратным невырожденным системам; метод Гаусса универсален.

Для иллюстрации возьмём одну и ту же систему:

⎩ ⎨ ⎧ x + y + z = 6 2 x - y + z = 3 x + 2 y - z = 2 A = 121 1 - 1 2 11 - 1, B = 632 .

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

Теорема (Крамера). Если определитель квадратной системы $A X = B$ отличен от нуля, $Δ = det A \neq = 0$ , то система определённая (имеет единственное решение), и

x_{i} = \frac{Δ _{i}}{Δ}, i = \overline{1, n},

где $Δ_{i}$ — определитель, полученный из $Δ$ заменой $i$ -го столбца столбцом свободных членов $B$ .

Доказательство. При $det A \neq = 0$ существует обратная матрица, и $X = A^{- 1} B = \frac{1}{Δ} A B$ . Расписывая произведение присоединённой матрицы $A$ на $B$ по строкам, в $i$ -й координате получаем

x_{i} = \frac{A _{1 i} b _{1} + A _{2 i} b _{2} + \dots + A _{ni} b _{n}}{Δ},

а числитель — это в точности разложение определителя $Δ_{i}$ по $i$ -му столбцу (столбцу из $b_{1}, \dots, b_{n}$ ).

Пример. Для нашей системы

Δ = 121 1 - 1 2 11 - 1 = 7.

Заменяя по очереди столбцы на $B = (6, 3, 2)^{T}$ :

Δ_{1} = 632 1 - 1 2 11 - 1 = 7, Δ_{2} = 121632 11 - 1 = 14, Δ_{3} = 121 1 - 1 2 632 = 21.

Отсюда

x = \frac{Δ _{1}}{Δ} = 1, y = \frac{Δ _{2}}{Δ} = 2, z = \frac{Δ _{3}}{Δ} = 3.

Ограничения. Метод Крамера работает только для квадратной системы с $det A \neq = 0$ и требует вычисления $n + 1$ определителей порядка $n$ — при больших $n$ это дорого. Поэтому на практике чаще применяют метод Гаусса.

Метод Гаусса

Идея: элементарными преобразованиями строк расширенной матрицы $\overline{A} = (A ∣ B)$ привести систему к ступенчатому (треугольному) виду — прямой ход, а затем последовательно найти неизвестные снизу вверх — обратный ход. Элементарные преобразования не меняют множества решений.

Пример (та же система). Прямой ход:

121 1 - 1 2 11 - 1 632 R_{2} - 2 R_{1} R_{3} - R_{1} 100 1 - 3 1 1 - 1 - 2 6 - 9 - 4 R_{2} \leftrightarrow R_{3} R_{3} + 3 R_{2} 100110 1 - 2 - 7 6 - 4 - 21 .

Обратный ход:

- 7 z = - 21 \Rightarrow z = 3; y - 2 z = - 4 \Rightarrow y = 2; x + y + z = 6 \Rightarrow x = 1.

Получили то же решение $x = 1, y = 2, z = 3$ .

Метод Жордана–Гаусса. Если продолжить преобразования и обнулить элементы и выше ведущих, приведя левую часть к единичной матрице (приведённый ступенчатый вид), то решение читается сразу — обратный ход не нужен.

Общий случай. Метод Гаусса работает для любой системы $m \times n$ . По ходу преобразований сразу виден ранг и тип системы (ср. теорему Кронекера–Капелли):

строка $(0 \dots 0 ∣ β)$ с $β \neq = 0$ — система несовместна;
после отбрасывания нулевых строк осталось $r$ строк: при $r = n$ решение единственно; при $r < n$ выражаем $r$ базисных неизвестных через $n - r$ свободных и получаем общее решение (бесконечно много решений).

Сравнение методов

	Метод Крамера	Метод Гаусса
Применимость	только квадратные, $det A \neq = 0$	любые $m \times n$
Что даёт	единственное решение по формуле	полное исследование + все решения
Трудоёмкость	$n + 1$ определитель порядка $n$ (дорого)	$\sim n^{3}$ операций (эффективно)

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

Метод Гаусса

Сравнение методов

Related works