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

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

Постановка задачи

ЛЕКЦИЯ 3

Тема: Решение систем линейных алгебраических уравнений

Требуется найти решение системы линейных уравнений:

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

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

a ₃₁ x ₁ + a ₃₂ x ₂ + a ₃₃ x ₃ + … + a _{3 n} x_n = b ₃ (3.1)

.

a_{n 1} x ₁ + a_{n 2} x ₂ + a_{n 3} x ₃ + … + a_nnx_n = b_n

или в матричной форме:

Ax = b, (3.2)

где

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

a ₂₁ a ₂₂ a ₂₃ … a _{2 n} x ₂ b ₂

A = a ₃₁ a ₃₂ a ₃₃ … a _{3 n} x =x _3, b =b ₃

a_{n 1} a_{n 2} a_{n 3} a_nn x_n b_n

По правилу Крамера система n линейных уравнений имеет единственное решение, если определитель системы отличен от нуля (det A 0) и значение каждого из неизвестных определяется следующим образом:

x_j =, j = 1, …, n, (3.3)

где det A_j - определитель матрицы, получаемой заменой j -го столбца матрицы A столбцом правых частей b.

Непосредственный расчет определителей для больших n является очень трудоемким по сравнению с вычислительными методами.

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

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

Этого недостатка лишены итерационные методы, но зато они не всегда сходятся и могут применяться лишь для систем определенных классов.

Среди прямых методов наиболее распространенным является метод исключения Гаусса и его модификации, Наиболее распространенными итерационными методами является метод простых итераций Якоби и метод Зейделя.

Эти методы будут рассмотрены в следующих разделах.

Основная идея метода исключений Гаусса состоит в том, что система уравнений (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

a x ₂ + 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- a x_{k+ 1} - a x_{k+ 2} - … - a x_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-11-29