Метод исключения Гаусса с выбором главного элемента по столбцу

Метод исключения Гаусса. Схема единственного деления

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

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

Прямой ход состоит из n – 1 шагов. На первом шаге исключается переменная x ₁ из всех уравнений, кроме первого. Для этого нужно из второго, третьего, …, n- го уравнений вычесть первое, умноженное на величину

m = , i = 2, 3, …, n. (3.4)

При этом коэффициенты при x ₁ обратятся в нуль во всех уравнениях, кроме первого.

Введем обозначения:

a = a_ij – ma _{1 j} , b= b_i – mb ₁. (3.5)

Легко убедиться, что для всех уравнений, начиная со второго, a= 0, i = 2, 3, …, n. Преобразованная система запишется в виде:

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

ax ₂ + ax ₃ + … + ax_n = b

ax ₂ + ax ₃ + … + ax_n = b (3.6)

ax ₂ + ax ₃ + … + ax_n = b

Все уравнения (3.6), кроме первого, образуют систему (n – 1)-го порядка. Применяя к ней ту же процедуру, мы можем исключить из третьего, четвертого, …, n- го уравнений переменную x ₂. Точно так же исключаем переменную x ₃ из последних n – 3 уравнений.

На некотором k -ом шаге в предположении, что главный элемент k-ого шага a 0, переменная x _k исключается с помощью формул:

m = ,

a = a– ma,

b= b– mb, i, j = k + 1, k + 2, …, n. (3.7)

Индекс k принимает значения 1, 2, …, n – 1.

При k = n – 1 получим треугольную систему:

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

ax ₂ + ax ₃ + …+ ax_n = b

ax ₃ + …+ ax_n = b (3.8)

ax_n = b

с треугольной матрицей A_n.

Приведение системы (3.1) к треугольному виду (3.8) составляет прямой ход метода Гаусса.

При использовании метода Гаусса нет необходимости в предварительном обосновании существования и единственности решения (т. е. доказательства, что det A ¹ 0). Если на k -ом шаге все элементы a (i = k, k + 1, …, n) окажутся равными нулю, то система (3.1) не имеет единственного решения.

Обратный ход состоит в вычислении переменных. Из последнего уравнения (3.8) определяем x_{n ..}. Подставляя его в предпоследнее уравнение, находим x_{n- 1}, и т. д. Общие формулы имеют вид:

x_n = ,

x_k = (b- ax_{k+ 1} - ax_{k+ 2} - … - ax_n), k = n – 1, n – 2, …, 1 (3.9)

Трудоемкость метода. Для реализации метода исключения Гаусса требуется примерно 2/3 n ³ операций для прямого хода и n ² операций для обратного хода. Таким образом, общее количество операций составляет примерно 2/3 n ³ + n ².

Пример 3.1.

Применим метод исключения Гаусса по схеме единственного деления для решения системы уравнений:

2.0 x ₁ + 1.0 x ₂ – 0.1 x ₃ + 1.0 x ₄ = 2.7

0.4 x ₁ + 0.5 x ₂ + 4.0 x ₃ – 8.5 x ₄ = 21.9

0.3 x ₁ – 1.0 x ₂ + 1.0 x ₃ + 5.2 x ₄ = – 3.9 (3.10)

1.0 x ₁ + 0.2 x ₂ + 2.5 x ₃ – 1.0 x ₄ = 9.9

Будем делать округление чисел до четырех знаков после десятичной точки.

Прямой ход. 1-ый шаг. Вычислим множители:

m = = = 0.2; m = = = 0.15; m = = = 0.5.

Вычитая из второго, третьего и четвертого уравнений системы (3.10) первое уравнение, умноженное соответственно на m, m, m, получим новую систему:

2.0 x ₁ + 1.0 x ₂ – 0.1 x ₃ + 1.0 x ₄ = 2.7

0.3 x ₂ + 4.02 x ₃ – 8.70 x ₄ = 21.36

– 1.15 x ₂ + 1.015 x ₃ + 5.05 x ₄ = – 4.305 (3. 11)

– 0.30 x ₂ + 2.55 x ₃ – 1.50 x ₄ = 8.55

2-ой шаг. Вычислим множители:

m = = = – 3.83333; m = = = –1.0.

Вычитая из третьего и четвертого уравнений системы (3.11) второе уравнение, умноженное соответственно на m и m, приходим к системе:

2.0 x ₁ + 1.0 x ₂ – 0.1 x ₃ + 1.0 x ₄ = 2.7

0.3 x ₂ + 4.02 x ₃ – 8.70 x ₄ = 21.36

16. 425 x ₃ – 28.300 x ₄ = 77. 575 (3.12)

6.570 x ₃ – 10.200 x ₄ = 29.910

3-ий шаг. Вычислим множитель:

m = = = 0.4.

Вычитая из четвертого уравнения системы (3.12) третье, умноженное на m, приведем систему к треугольному виду:

2.0 x ₁ + 1.0 x ₂ – 0.1 x ₃ + 1.0 x ₄ = 2.7

0.3 x ₂ + 4.02 x ₃ – 8.70 x ₄ = 21.36

16. 425 x ₃ – 28.300 x ₄ = 77. 575 (3.13)

1.12 x ₄ = – 1.12

Обратный ход. Из последнего уравнения системы (3.13) находим x ₄ = 1.000. Подставляя значение x ₄ в третье уравнение, получим x ₃ = 2.000. Подставляя найденные значения x ₄ и x ₃ во второе уравнение, найдем x ₂ = 3.000. Наконец, из первого уравнения, подставив в него найденные значения x ₄, x ₃ и x ₂, вычислим x ₁ = – 1.000.

Итак система (3.10) имеет следующее решение:

x ₁ = 1.000, x ₂ = 2.000, x ₃ = 3.000, x ₄ = – 1.000.

Хотя метод Гаусса является точным методом, ошибки округления могут привести к существенным погрешностям результата. Кроме того исключение по формулам (3.7) нельзя проводить, если элемент главной диагонали a равен нулю. Если элемент a мал, то велики ошибки округления при делении на этот элемент. Для уменьшения ошибок округления применяют метод исключения Гаусса с выбором главного элемента по столбцу. Прямой ход так же, как и для схемы единственного деления, состоит из n – 1 шагов. На первом шаге прежде, чем исключать переменную x ₁, уравнения переставляются так, чтобы в левом верхнем углу был наибольший по модулю коэффициент a_{i 1}, i = 1, 2, …, n. В дальнейшем, на k -м шаге, прежде, чем исключать переменную x_k, уравнения переставляются так, чтобы в левом верхнем углу был наибольший по модулю коэффициент a_ik, i = k, k + 1, …, n. После этой перестановки исключение переменной x_k производят, как в схеме единственного деления.

Трудоемкость метода. Дополнительные действия по выбору главных элементов требуют примерно n ² операций, что практически не влияет на общую трудоемкость метода.

Пример 3.2.

Применим метод исключения Гаусса с выбором главного элемента по столбцу для решения системы уравнений (3.10) из примера 3.1. Прямой ход. 1-ый шаг. Так как коэффициент a ₁₁ = 2.0 наибольший из коэффициентов первого столбца, перестановки строк не требуется и 1-ый шаг полностью совпадает с 1-ым шагом примера 3.1. Из второго, третьего и четвертого уравнений исключается переменная x ₁ и система приводится к виду (3.11).

2-ой шаг. Наибольший по модулю коэффициент при x ₂ в системе (3.11) a = – 1.15. Поэтому переставим уравнения следующим образом:

2.0 x ₁ + 1.0 x ₂ – 0.1 x ₃ + 1.0 x ₄ = 2.7

– 1.15 x ₂ + 1.015 x ₃ + 5.05 x ₄ = – 4.305 (3.14)

0.3 x ₂ + 4.02 x ₃ – 8.70 x ₄ = 21.36

– 0.30 x ₂ + 2.55 x ₃ – 1.50 x ₄ = 8.55

Вычислим множители:

m = = = –0.26087 m = = = 0.26087.

Вычитая из третьего и четвертого уравнений системы (3.14) второе уравнение, умноженное соответственно на m и m, приходим к системе:

2.0 x ₁ + 1.0 x ₂ – 0.1 x ₃ + 1.0 x ₄ = 2.7

– 1.15 x ₂ + 1.015 x ₃ + 5.05 x ₄ = – 4.305 (3.15)

4.28478 x ₃ – 7. 38261 x ₄ = 20.23696

2.28522 x ₃ – 2.81739 x ₄ = 9.67305

3-ий шаг. Вычислим множитель:

m = = = 0.53333.

Вычитая из четвертого уравнения системы (3.15) третье, умноженное на m, приведем систему к треугольному виду:

2.0 x ₁ + 1.0 x ₂ – 0.1 x ₃ + 1.0 x ₄ = 2.7

– 1.15 x ₂ + 1.015 x ₃ + 5.05 x ₄ = – 4.305 (3.16)

4.28478 x ₃ – 7. 38261 x ₄ = 20.23696

1.11998 x ₄ = – 1.11998

Обратный ход. Обратный ход полностью совпадает с обратным ходом примера 3.1. Решение системы имеет вид:

x ₁ = 1.000, x ₂ = 2.000, x ₃ = 3.000, x ₄ = – 1.000.

Дата добавления: 2014-01-05