4.4 — Глава I, §4. Системы линейных уравнений4.4 — Chapter I, §4. Systems of linear equations
Метод Гаусса — единственный из методов этой главы, который работает всегда: для любого числа уравнений, любого числа неизвестных, вырожденной или невырожденной, квадратной или прямоугольной системы. Формулы Крамера (см. 4.3) требуют квадратности и невырожденности; матричный способ — тоже. Метод Гаусса не требует ничего, кроме самих уравнений — и именно поэтому он, а не формулы Крамера, лежит в основе промышленных решателей линейных систем.Gaussian elimination is the only method in this chapter that works always: for any number of equations, any number of unknowns, a singular or non-singular, square or rectangular system. Cramer's rule (see 4.3) requires squareness and non-singularity; so does the matrix method. Gaussian elimination requires nothing but the equations themselves — which is exactly why it, and not Cramer's rule, underlies industrial linear-system solvers.
Одним из наиболее универсальных и эффективных методов решения линейных алгебраических систем является метод Гаусса, состоящий в последовательном исключении неизвестных. Пусть дана система уравненийOne of the most universal and efficient methods for solving linear algebraic systems is the Gauss method, which consists of successively eliminating the unknowns. Consider the system of equations
a11x1 + a12x2 + ... + a1nxn = b1,
a21x1 + a22x2 + ... + a2nxn = b2, (4.3)
...........................
am1x1 + am2x2 + ... + amnxn = bm.Процесс решения по методу Гаусса состоит из двух этапов. На первом этапе (прямой ход) система приводится к ступенчатому (в частности, треугольному) виду:The Gauss method's solution process consists of two stages. In the first stage (the forward pass), the system is reduced to row-echelon (in particular, triangular) form:
a11x1 + a12x2 + ... + a1kxk + ... + a1nxn = b1,
a22x2 + ... + a2kxk + ... + a2nxn = b2,
......................................
akkxk + ... + aknxn = bk,где k ≤ n, a_ii ≠ 0 (i = 1,k). Коэффициенты a_ii называются главными элементами системы. На втором этапе (обратный ход) идёт последовательное определение неизвестных из этой ступенчатой системы.where k ≤ n, a_ii ≠ 0 (i = 1,k). The coefficients a_ii are called the leading (pivot) elements of the system. In the second stage (the backward pass), the unknowns are successively determined from this row-echelon system.
Ключевое наблюдение, которое стоит держать в голове: этот процесс — не новый метод, а систематическое применение элементарных преобразований строк (см. 1.2) в комбинации с фактом, что такие преобразования сохраняют множество решений системы (эквивалентность систем, см. 4.1). Каждый шаг прямого хода — это буквально свойство 6 определителей (см. 2.2) в действии: «прибавить к строке другую строку, умноженную на число».The key observation worth keeping in mind: this process isn't a new method — it's a systematic application of elementary row transformations (see 1.2) combined with the fact that such transformations preserve the solution set of a system (equivalence of systems, see 4.1). Every step of the forward pass is literally property 6 of determinants (see 2.2) in action: "add to a row another row scaled by a number."
Будем считать, что элемент a11 ≠ 0 (если a11 = 0, то первым в системе запишем уравнение, в котором коэффициент при x1 отличен от нуля). Преобразуем систему (4.3), исключив неизвестное x1 во всех уравнениях, кроме первого: умножаем обе части первого уравнения на -a21/a11 и складываем со вторым уравнением; затем умножаем обе части первого уравнения на -a31/a11 и складываем с третьим уравнением. Продолжая этот процесс, получим эквивалентную систему, где во всех уравнениях, кроме первого, отсутствует x1. Аналогичным образом, считая главным элементом новый коэффициент при x2, исключаем x2 из всех уравнений, кроме первого и второго, и так далее.Assume a11 ≠ 0 (if a11 = 0, first write down an equation in which the coefficient of x1 is nonzero). Transform system (4.3), eliminating x1 from all equations except the first: multiply both sides of the first equation by -a21/a11 and add it to the second equation; then multiply both sides of the first equation by -a31/a11 and add it to the third equation. Continuing this process yields an equivalent system in which x1 is absent from every equation except the first. Similarly, treating the new coefficient of x2 as the leading element, eliminate x2 from all equations except the first and second, and so on.
Если в процессе приведения системы к ступенчатому виду появляются нулевые уравнения (0 = 0), их отбрасывают. Если же появляется уравнение вида 0 = b_i, где b_i ≠ 0, это свидетельствует о несовместности системы.If zero equations (0 = 0) arise while reducing the system to row-echelon form, they are discarded. But if an equation of the form 0 = b_i with b_i ≠ 0 arises, this indicates the system is inconsistent.
Второй этап (обратный ход) заключается в решении ступенчатой системы уравнений. Ступенчатая система, вообще говоря, имеет бесчисленное множество решений. В последнем уравнении этой системы выражают первое неизвестное x_k через остальные неизвестные (x_(k+1), ..., x_n). Затем подставляют значение x_k в предпоследнее уравнение и выражают x_(k-1) через (x_(k+1), ..., x_n); находим x_(k-2), ..., x1. Придавая свободным неизвестным (x_(k+1), ..., x_n) произвольные значения, получим бесчисленное множество решений системы.The second stage (backward pass) consists of solving the row-echelon system. A row-echelon system generally has infinitely many solutions. In the last equation of this system, the first unknown x_k is expressed through the remaining unknowns (x_(k+1), ..., x_n). Then the value of x_k is substituted into the second-to-last equation, expressing x_(k-1) through (x_(k+1), ..., x_n); we find x_(k-2), ..., x1. Assigning arbitrary values to the free unknowns (x_(k+1), ..., x_n) yields infinitely many solutions of the system.
Замечание 1. Если ступенчатая система оказывается треугольной, т. е. k = n, то исходная система имеет единственное решение: из последнего уравнения находим x_n, из предпоследнего — x_(n-1), далее поднимаясь по системе вверх, найдём все остальные неизвестные (x_(n-2), ..., x1).Remark 1. If the row-echelon system turns out to be triangular, i.e. k = n, then the original system has a unique solution: x_n is found from the last equation, x_(n-1) from the second-to-last, and moving up through the system, all remaining unknowns (x_(n-2), ..., x1) are found.
Замечание 2. На практике удобнее работать не с системой (4.3), а с расширенной матрицей системы, выполняя все элементарные преобразования над её строками. Удобно, чтобы коэффициент a11 был равен 1 (уравнения переставить местами, либо разделить обе части уравнения на a11 ≠ 0).Remark 2. In practice it's more convenient to work not with system (4.3) but with the augmented matrix of the system, performing all elementary transformations on its rows. It's convenient to make the coefficient a11 equal to 1 (swap equations, or divide both sides of an equation by a11 ≠ 0).
Решить систему методом Гаусса:Solve the system by the Gauss method:
2x1 - x2 + 3x3 - 5x4 = 1,
x1 - x2 - 5x3 = 2,
3x1 - 2x2 - 2x3 - 5x4 = 3,
7x1 - 5x2 - 9x3 -10x4 = 8.Решение. Составляем расширенную матрицу системы и выполняем над её строками элементарные преобразования. Шаг 1 — переставляем строки так, чтобы a11 = 1 (вторая строка системы уже имеет коэффициент 1 при x1, ставим её первой):Solution. Form the augmented matrix of the system and perform elementary transformations on its rows. Step 1 — swap rows so that a11 = 1 (the second equation of the system already has coefficient 1 for x1, so put it first):
| 2 -1 3 -5 1 | | 1 -1 -5 0 2 |
| 1 -1 -5 0 2 | ~ | 2 -1 3 -5 1 |
| 3 -2 -2 -5 3 | | 3 -2 -2 -5 3 |
| 7 -5 -9 -10 8 | | 7 -5 -9 -10 8 |Шаг 2 — исключаем x1 из строк 2, 3, 4, вычитая из них первую строку, умноженную на коэффициент при x1 в этой строке (2, 3 и 7 соответственно):Step 2 — eliminate x1 from rows 2, 3, 4 by subtracting the first row, scaled by the coefficient of x1 in that row (2, 3, and 7 respectively):
строка2 - 2·строка1: (2-2·1, -1-2·(-1), 3-2·(-5), -5-2·0, 1-2·2)
= (0, 1, 13, -5, -3)
строка3 - 3·строка1: (3-3·1, -2-3·(-1), -2-3·(-5), -5-3·0, 3-3·2)
= (0, 1, 13, -5, -3)
строка4 - 7·строка1: (7-7·1, -5-7·(-1), -9-7·(-5), -10-7·0, 8-7·2)
= (0, 2, 26, -10, -6)Получаем:We obtain:
| 1 -1 -5 0 2 |
| 0 1 13 -5 -3 |
| 0 1 13 -5 -3 |
| 0 2 26 -10 -6|Шаг 3 — строка 3 совпадает со строкой 2 (после вычитания строки 2 из строки 3 получаем нулевую строку 0 = 0, отбрасываем её). Строка 4 пропорциональна строке 2 с коэффициентом 2 (после вычитания 2·строка2 из строки 4 тоже получаем нулевую строку — отбрасываем и её):Step 3 — row 3 coincides with row 2 (subtracting row 2 from row 3 gives the zero row 0 = 0, discard it). Row 4 is proportional to row 2 with coefficient 2 (subtracting 2·row2 from row 4 also gives a zero row — discard it too):
строка3 - строка2: (0, 0, 0, 0, 0) → отбрасываем
строка4 - 2·строка2: (0, 2-2, 26-26, -10+10, -6+6) = (0, 0, 0, 0, 0) → отбрасываемОстаётся ступенчатая система из двух уравнений:What remains is a row-echelon system of two equations:
| 1 -1 -5 0 2 |
| 0 1 13 -5 -3 |то есть исходная система свелась к ступенчатой:i.e. the original system reduces to the row-echelon form:
x1 - x2 - 5x3 = 2,
x2 + 13x3 - 5x4 = -3.Обратный ход. Здесь k = 2 < n = 4 — две главные неизвестные (x1, x2), две свободные (x3, x4). Из второго уравнения выражаем x2 через свободные:Backward pass. Here k = 2 < n = 4 — two leading unknowns (x1, x2), two free ones (x3, x4). From the second equation, express x2 in terms of the free unknowns:
x2 = 5x4 - 13x3 - 3.Подставляем в первое уравнение и выражаем x1:Substitute into the first equation and express x1:
x1 = x2 + 5x3 + 2 = (5x4 - 13x3 - 3) + 5x3 + 2 = 5x4 - 8x3 - 1.Поэтому общее решение системы: x2 = 5x4 - 13x3 - 3; x1 = 5x4 - 8x3 - 1 (x3 и x4 свободны). Если положить, например, x3 = 0, x4 = 0, то найдём одно из частных решений этой системы: x1 = -1, x2 = -3, x3 = 0, x4 = 0.So the general solution of the system is: x2 = 5x4 - 13x3 - 3; x1 = 5x4 - 8x3 - 1 (x3 and x4 are free). Setting, e.g., x3 = 0, x4 = 0, we find one particular solution of the system: x1 = -1, x2 = -3, x3 = 0, x4 = 0.
Проверка (не входит в оригинальный текст) для найденного частного решения по первому исходному уравнению: 2·(-1) - (-3) + 3·0 - 5·0 = -2 + 3 = 1 ✓ — совпадает со свободным членом первого уравнения.Check (not part of the original text) for the particular solution found, against the first original equation: 2·(-1) - (-3) + 3·0 - 5·0 = -2 + 3 = 1 ✓ — matches the constant term of the first equation.
Решить систему методом Гаусса:Solve the system by the Gauss method:
x1 + x2 + x3 = 3,
2x1 + 3x2 + 2x3 = 7,
3x1 + x2 + x3 = 5,
5x1 - x2 - x3 = 3.Решение. Составляем расширенную матрицу и выполняем элементарные преобразования над её строками. a11 = 1 уже подходит.Solution. Form the augmented matrix and perform elementary transformations on its rows. a11 = 1 is already suitable.
| 1 1 1 3 |
| 2 3 2 7 |
| 3 1 1 5 |
| 5 -1 -1 3 |Шаг 1 — исключаем x1 из строк 2, 3, 4 (вычитаем первую строку, умноженную на 2, 3 и 5 соответственно):Step 1 — eliminate x1 from rows 2, 3, 4 (subtract the first row scaled by 2, 3, and 5 respectively):
строка2 - 2·строка1: (2-2, 3-2, 2-2, 7-6) = (0, 1, 0, 1)
строка3 - 3·строка1: (3-3, 1-3, 1-3, 5-9) = (0, -2, -2, -4)
строка4 - 5·строка1: (5-5,-1-5,-1-5, 3-15) = (0, -6, -6, -12)| 1 1 1 3 |
| 0 1 0 1 |
| 0 -2 -2 -4 |
| 0 -6 -6 -12|Шаг 2 — исключаем x2 из строк 3, 4, используя строку 2 (коэффициент при x2 в строке 2 уже равен 1): вычитаем строку 2, умноженную на -2 и -6 (т. е. прибавляем удвоенную и умноженную на 6 строку 2):Step 2 — eliminate x2 from rows 3, 4, using row 2 (the coefficient of x2 in row 2 is already 1): subtract row 2 scaled by -2 and -6 (i.e. add row 2 scaled by 2 and by 6):
строка3 - (-2)·строка2 = строка3 + 2·строка2:
(0+0, -2+2, -2+0, -4+2) = (0, 0, -2, -2)
строка4 - (-6)·строка2 = строка4 + 6·строка2:
(0+0, -6+6, -6+0, -12+6) = (0, 0, -6, -6)| 1 1 1 3 |
| 0 1 0 1 |
| 0 0 -2 -2 |
| 0 0 -6 -6 |Шаг 3 — исключаем x3 из строки 4, используя строку 3: строка 4 пропорциональна строке 3 с коэффициентом 3 (-6 = 3·(-2), -6 = 3·(-2)), поэтому строка4 - 3·строка3 = (0, 0, 0, 0) — нулевая строка, отбрасываем её. Также нормируем строку 3, разделив на -2, чтобы получить единицу на диагонали:Step 3 — eliminate x3 from row 4, using row 3: row 4 is proportional to row 3 with coefficient 3 (-6 = 3·(-2), -6 = 3·(-2)), so row4 - 3·row3 = (0, 0, 0, 0) — a zero row, discard it. Also normalize row 3, dividing by -2, to get a one on the diagonal:
строка3 / (-2): (0, 0, 1, 1)Получаем итоговую матрицу:We obtain the final matrix:
| 1 1 1 3 |
| 0 1 0 1 |
| 0 0 1 1 |
| 0 0 0 0 |Полученная матрица соответствует треугольной (в первых трёх строках) системе:The resulting matrix corresponds to the (in its first three rows) triangular system:
x1 + x2 + x3 = 3,
x2 = 1,
x3 = 1.Обратный ход. Здесь k = n = 3 — система треугольная, решение единственно (Замечание 1). Из второго и третьего уравнений сразу читаем x2 = 1, x3 = 1. Подставляем в первое: x1 + 1 + 1 = 3, откуда x1 = 1.Backward pass. Here k = n = 3 — the system is triangular, the solution is unique (Remark 1). From the second and third equations we read off directly x2 = 1, x3 = 1. Substituting into the first: x1 + 1 + 1 = 3, so x1 = 1.
Итак, x1 = 1, x2 = 1, x3 = 1 — единственное решение системы.So, x1 = 1, x2 = 1, x3 = 1 is the unique solution of the system.
Проверка (не входит в оригинальный текст) по четвёртому исходному уравнению (не участвовавшему в финальной ступенчатой системе, раз стало 0=0): 5·1 - 1 - 1 = 3 ✓ — совпадает.Check (not part of the original text) against the fourth original equation (which dropped out as 0=0 in the final row-echelon system): 5·1 - 1 - 1 = 3 ✓ — matches.
В учебных примерах ведущий элемент выбирают, просто чтобы избежать деления на ноль (a11 ≠ 0). На практике (вычисления с плавающей точкой) важно ещё, чтобы ведущий элемент был не просто ненулевым, а достаточно большим по модулю относительно остальных элементов столбца — иначе деление на маленькое число резко усиливает ошибки округления. Стратегия выбора максимального по модулю элемента в столбце (partial pivoting) — стандартная часть промышленной реализации метода Гаусса, не упомянутая в учебном изложении, но критичная для реальных вычислений.In textbook examples, the pivot is chosen simply to avoid division by zero (a11 ≠ 0). In practice (floating-point computation), it also matters that the pivot be not just nonzero but sufficiently large in magnitude relative to the rest of the column — otherwise dividing by a small number sharply amplifies rounding errors. The strategy of picking the largest-magnitude element in a column (partial pivoting) is a standard part of production Gaussian-elimination implementations, unmentioned in the textbook treatment but critical for real computation.
Начинающие иногда пугаются, увидев в процессе прямого хода строку вида (0 0 0 | 5), и начинают искать «ошибку» в предыдущих вычислениях. На самом деле это и есть корректный результат: система несовместна, и дальнейшие шаги не нужны — прямой ход можно останавливать сразу, как только такая строка обнаружена.Beginners sometimes get spooked seeing a row like (0 0 0 | 5) appear during the forward pass and start hunting for an "error" in earlier steps. In fact this is the correct outcome: the system is inconsistent, and no further steps are needed — the forward pass can be stopped as soon as such a row is found.
источникsource
Описание метода (прямой/обратный ход, замечания 1–2) и Примеры 4.4–4.5 — по изданию: Письменный Д. Т. Конспект лекций по высшей математике: полный курс. — 9-е изд. — М.: Айрис-пресс, 2009. — 608 с. — Глава I, §4.4 «Решение систем линейных уравнений методом Гаусса», с. 34–36. Пошаговая расшифровка вычислений в примерах, проверки и раздел «Грабли» — авторское дополнение.Description of the method (forward/backward pass, remarks 1–2) and Examples 4.4–4.5 — from: Pismenny D. T. Lecture Notes on Higher Mathematics: Complete Course. — 9th ed. — Moscow: Iris-press, 2009. — 608 p. — Chapter I, §4.4 "Solving Systems of Linear Equations by the Gauss Method," pp. 34–36. The step-by-step breakdown of the computations in the examples, the checks, and the "Gotchas" section are original additions.