Решение системы линейных алгебраических уравнений. Метод Гаусса

Суть метода заключается в последовательном исключении неизвестных. Рассмотрим систему линейных уравнений:

Разделим обе части 1-го уравнения на a₁₁ > 0, затем: 1) умножим на а₂₁ и вычтем из второго уравнения 2) умножим на а₃₁ и вычтем из третьего уравнения и т.д. Получим:, где d_1j = a_1j/a₁₁, j = 2, 3, …, n+1. d_ij = a_ij - a_i1d_1j i = 2, 3, …, n; j = 2, 3, …, n+1. Далее повторяем эти же действия для второго уравнения системы, потом - для третьего и т.д.

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод (который также называют методом последовательного исключения неизвестных) известен в различных вариантах уже более 2000 лет.

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

1.1.1. Схема единственного деления. Рассмотрим сначала простейший вариант метода Гаусса, называемый схемой единственного деления.

Прямой ход состоит из n - 1 шагов исключения.

1-й шаг. Целью этого шага является исключение неизвестного x ₁ из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a ₁₁ ¹ 0. Будем называть его главным элементом 1- го шага.

Найдем величины

q_{i 1} = a_{i 1}/ a ₁₁ (i = 2, 3, …, n),

называемые множителями 1- го шага. Вычтем последовательно из второго, третьего, …, n- го уравнений системы первое уравнение, умноженное соответственно на q_{2 1}, q ₃₁, …, q_{n 1}. Это позволит обратить в нуль коэффициенты при x ₁ во всех уравнениях, кроме первого. В результате получим эквивалентную систему

a ₁₁ x ₁ + a ₁₂ x ₂ + a ₁₃ x ₃ + … + a _{1 n}x_n = b ₁ ,

a ₂₂⁽¹⁾ x ₂ + a ₂₃⁽¹⁾ x ₃ + … + a _{2 n} ⁽¹⁾ x_n = b ₂⁽¹⁾ ,

a ₃₂⁽¹⁾ x ₂ + a ₃₃⁽¹⁾ x ₃ + … + a _{3 n} ⁽¹⁾ x_n = b ₃⁽¹⁾,

...............

a_{n 2}⁽¹⁾ x ₂ + a_{n 3}⁽¹⁾ x ₃ + … + a_nn ⁽¹⁾ x_n = b_n ⁽¹⁾.

в которой a_ij ⁽¹⁾ и b_ij ⁽¹⁾ вычисляются по формулам

a_ij ⁽¹⁾ = a_ij − q_{i 1} a _{1 j} , b_i ⁽¹⁾ = b_i − q_{i 1} b ₁.

2-й шаг. Целью этого шага является ислючение неизвестного x ₂ из уравнений с номерами i = 3, 4, …, n. Пусть a ₂₂⁽¹⁾ ≠ 0, где a ₂₂⁽¹⁾ ­– коэффициент, называемый главным (или ведущим) элементом 2- го шага. Вычислим множители 2-го шага

q_{i 2} = a_{i 2}⁽¹⁾ / a ₂₂⁽¹⁾ (i = 3, 4, …, n)

и вычтем последовательно из третьего, четвертого, …, n- го уравнения системы второе уравнение, умноженное соответственно на q ₃₂, q ₄₂, …, q_{m 2}. В результате получим систему

a ₁₁ x ₁ + a ₁₂ x ₂ + a ₁₃ x ₃ + … + a _{1 n}x_n = b ₁ ,

a ₂₂⁽¹⁾ x ₂ + a ₂₃⁽¹⁾ x ₃ + … + a _{2 n} ⁽¹⁾ = b ₂⁽¹⁾ ,

a ₃₃⁽²⁾ x ₃ + … + a _{3 n} ⁽²⁾ x_n = b ₃⁽²⁾ ,

...................

a_{n 3}⁽²⁾ x ₃ + … + a_nn ⁽²⁾ x_n = b_n ⁽²⁾ .

Здесь коэффициенты a_ij ⁽²⁾ и b_ij ⁽²⁾ вычисляются по формулам

a_ij ⁽²⁾ = a_ij ⁽¹⁾ – q_{i 2} a _{2 j} ⁽¹⁾, b_i ⁽²⁾ = b_i ⁽¹⁾ – q_{i 2} b ₂⁽¹⁾.

Аналогично проводятся остальные шаги. Опишем очередной k- й шаг.

k- й шаг. В предположении, что главный (ведущий) элемент k- го шага a_kk ^{( k –1)} отличен от нуля, вычислим множители k-го шага

q_ik = a_ik ^{(k –1)} / a_kk ^{(k –1)} (i = k + 1, …, n)

и вычтем последовательно из (k + 1)-го, …, n -го уравнений полученной на предыдущем шаге системы k -e уравнение, умноженное соответственно на q_{k +1, k}, q_{k +2, k}, …, q_nk.

После (n - 1)-го шага исключения получим систему уравнений

a ₁₁ x ₁ + a ₁₂ x ₂ + a ₁₃ x ₃ + … + a _{1 n} x_n = b ₁ ,

a ₂₂⁽¹⁾ x ₂ + a ₂₃⁽¹⁾ x ₃ + … + a _{2 n} ⁽¹⁾ x_n = b ₂⁽¹⁾ ,

a ₃₃⁽²⁾ x ₃ + … + a _{3 n} ⁽²⁾ x_n = b ₃⁽²⁾ ,

....................

a_nn ^{(n –1)} x_n = b_n ^{(n –1)} .

матрица A ^{( n -1)} которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

Обратный ход. Из последнего уравнения системы находим xn. Подставляя найденное значение x_n в предпоследнее уравнение, получим x_{n –1}. Осуществляя обратную подстановку, далее последовательно находим x_{n –1}, x_{n –2}, …, x ₁. Вычисления неизвестных здесь проводятся по формулам

x_n = b_n ^{( n –1)} / a_nn ^{( n –1)},

x_k = (b_n ^{( k –1)} – a_{k , k +1}^{( k –1)} x_{k +1} – … – a_kn ^{( k –1)} x_n) / a_kk ^{( k –1)}, (k = n – 1, …, 1).

Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы a_kk ^{( k –1)}. Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

. Метод Гаусса с выбором главного элемента по столбцу (схема частичного выбора). Описание метода. На k -м шаге прямого хода коэффициенты уравнений системы с номерами i = k + 1, …, n преобразуются по формулам

a_ij ^{( k )} = a_ij ^{( k –1)} − q_ika_kj, b_i ^{( k )} = b_i ^{( k –1)} − q_ikb_k ^{( k –1)}, i = k + 1, …, n.

Интуитивно ясно, что во избежание сильного роста коэффициентов системы и связанных с этим ошибок нельзя допускать появления больших множителей q_ik.

В методе Гаусса с выбором главного элементоа по столбцу гарантируется, что | q_ik | ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k -м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент a_ikk при неизвестной x_k в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером i_k меняют местами с k -м уравнением системы для того, чтобы главный элемент занял место коэффициента a_kk ^{( k -1)}. После этой перестановки исключение неизвестного x_k производят, как в схеме единственного деления.

Метод Гаусса с выбором главного элемента по всей матрице (схема полного выбора). В этой схеме допускается нарушение естественного порядка исключения неизвестных.

На 1-м шаге мтода среди элементов a_ij определяют максимальный по модулю элемент a_{i 1 j 1}. Первое уравнение системы и уравнение с номером i ₁ меняют местами. Далее стандартным образом производят исключение неизвестного x_{i 1}из всех уравнений, кроме первого.

На k -м шаге метода среди коэффициентов a_ij ^{( k –1)} при неизвестных в уравнениях системы с номерами i = k, …, n выбирают максимальный по модулю коэффициент a_ikjk ^{( k -1)}. Затем k -е уравнение и уравнение, содержащее найденный коэффициент, меняют местами и исключают неизвестное x_jk из уравнений с номерами i = k + 1, …, n.

На этапе обратного хода неизвестные вычисляют в следующем порядке: x_jn, x_{jn– 1}, …, x_{j 1}.