Метод исключения Гаусса с выбором главного элемента по столбцу
Метод исключения Гаусса. Схема единственного деления
Основная идея метода исключений Гаусса состоит в том, что система уравнений (3.1) приводится к эквивалентной ей системе с верхней треугольной матрицей (прямой ход исключений), а затем неизвестные вычисляются последовательной подстановкой (обратный ход исключений).
Рассмотрим сначала простейший метод исключения Гаусса, называемый схемой единственного деления.
Прямой ход состоит из n – 1 шагов. На первом шаге исключается переменная x1 из всех уравнений, кроме первого. Для этого нужно из второго, третьего, …, n-го уравнений вычесть первое, умноженное на величину
m
= 
, i = 2, 3, …, n. (3.4)
При этом коэффициенты при x1 обратятся в нуль во всех уравнениях, кроме первого.
Введем обозначения:
a
= aij – ma1j , b
= bi – mb1. (3.5)
Легко убедиться, что для всех уравнений, начиная со второго, a
= 0, i = 2, 3, …, n. Преобразованная система запишется в виде:
a11x1 + a12 x2 + a13x3 + … + a1nxn = b1
a
x2 + a
x3 + … + a
xn = b
a
x2 + a
x3 + … + a
xn = b
(3.6)
a
x2 + a
x3 + … + a
xn = b
Все уравнения (3.6), кроме первого, образуют систему (n – 1)-го порядка. Применяя к ней ту же процедуру, мы можем исключить из третьего, четвертого, …, n-го уравнений переменную x2. Точно так же исключаем переменную x3 из последних n – 3 уравнений.
На некотором k-ом шаге в предположении, что главный элемент k-ого шага a
0, переменная xk исключается с помощью формул:
m
= 
,
a
= a
– ma
,
b= b
– mb
, i, j = k + 1, k + 2, …, n. (3.7)
Индекс k принимает значения 1, 2, …, n – 1.
При k = n – 1 получим треугольную систему:
a11x1 + a12 x2 + a13x3 + … + a1nxn = b1
ax2 + ax3 + …+ axn = b
a
x3 + …+ a
xn = b
(3.8)
a
xn = b
с треугольной матрицей An.
Приведение системы (3.1) к треугольному виду (3.8) составляет прямой ход метода Гаусса.
При использовании метода Гаусса нет необходимости в предварительном обосновании существования и единственности решения (т. е. доказательства, что det A ¹ 0). Если на k-ом шаге все элементы a
(i = k, k + 1, …, n) окажутся равными нулю, то система (3.1) не имеет единственного решения.
Обратный ход состоит в вычислении переменных. Из последнего уравнения (3.8) определяем xn... Подставляя его в предпоследнее уравнение, находим xn-1, и т. д. Общие формулы имеют вид:
xn = 
,
xk = 
(b- a
xk+1 - a
xk+2 - … - a
xn), k = n – 1, n – 2, …, 1 (3.9)
Трудоемкость метода.Для реализации метода исключения Гаусса требуется примерно 2/3n3 операций для прямого хода и n2 операций для обратного хода. Таким образом, общее количество операций составляет примерно 2/3n3 + n2.
Пример 3.1.
Применим метод исключения Гаусса по схеме единственного деления для решения системы уравнений:
2.0x1 + 1.0x2 –0.1x3 + 1.0x4 = 2.7
0.4x1 + 0.5x2 + 4.0x3 –8.5x4 = 21.9
0.3x1 –1.0x2 + 1.0x3 + 5.2x4 = – 3.9 (3.10)
1.0x1 + 0.2x2 + 2.5x3 –1.0x4 = 9.9
Будем делать округление чисел до четырех знаков после десятичной точки.
Прямой ход.1-ый шаг. Вычислим множители:
m
= 
= 
= 0.2; m= 
= 
= 0.15; m
= 
= 
= 0.5.
Вычитая из второго, третьего и четвертого уравнений системы (3.10) первое уравнение, умноженное соответственно на m, m, m, получим новую систему:
2.0x1 + 1.0x2 –0.1x3 + 1.0x4 = 2.7
0.3x2 + 4.02x3 –8.70x4 = 21.36
–1.15x2 + 1.015x3 + 5.05x4 = – 4.305 (3. 11)
– 0.30x2 + 2.55x3 – 1.50x4 = 8.55
2-ой шаг. Вычислим множители:
m= 
= 
= – 3.83333; m
= 
= 
= –1.0.
Вычитая из третьего и четвертого уравнений системы (3.11) второе уравнение, умноженное соответственно на mи m, приходим к системе:
2.0x1 + 1.0x2 –0.1x3 + 1.0x4 = 2.7
0.3x2 + 4.02x3 –8.70x4 = 21.36
16. 425x3 –28.300x4 = 77.575 (3.12)
6.570x3 – 10.200x4 = 29.910
3-ий шаг. Вычислим множитель:
m
= 
= 
= 0.4.
Вычитая из четвертого уравнения системы (3.12) третье, умноженное на m, приведем систему к треугольному виду:
2.0x1 + 1.0x2 –0.1x3 + 1.0x4 = 2.7
0.3x2 + 4.02x3 –8.70x4 = 21.36
16. 425x3 –28.300x4 = 77.575 (3.13)
1.12x4 = –1.12
Обратный ход.Из последнего уравнения системы (3.13) находим x4 = 1.000. Подставляя значение x4 в третье уравнение, получим x3 = 2.000. Подставляя найденные значения x4 и x3 во второе уравнение, найдем x2 = 3.000. Наконец, из первого уравнения, подставив в него найденные значения x4, x3 и x2, вычислим x1 = –1.000.
Итак система (3.10) имеет следующее решение:
x1 = 1.000,x2 = 2.000, x3 = 3.000, x4 = – 1.000.
Хотя метод Гаусса является точным методом, ошибки округления могут привести к существенным погрешностям результата. Кроме того исключение по формулам (3.7) нельзя проводить, если элемент главной диагонали aравен нулю. Если элемент aмал, то велики ошибки округления при делении на этот элемент. Для уменьшения ошибок округления применяют метод исключения Гаусса с выбором главного элемента по столбцу. Прямой ход так же, как и для схемы единственного деления, состоит из n – 1 шагов. На первом шаге прежде, чем исключать переменную x1, уравнения переставляются так, чтобы в левом верхнем углу был наибольший по модулю коэффициент ai1, i = 1, 2, …, n. В дальнейшем, на k-м шаге, прежде, чем исключать переменную xk, уравнения переставляются так, чтобы в левом верхнем углу был наибольший по модулю коэффициент aik, i = k, k + 1, …, n. После этой перестановки исключение переменной xk производят, как в схеме единственного деления.
Трудоемкость метода.Дополнительные действия по выбору главных элементов требуют примерно n2 операций, что практически не влияет на общую трудоемкость метода.
Пример 3.2.
Применим метод исключения Гаусса с выбором главного элемента по столбцу для решения системы уравнений (3.10) из примера 3.1. Прямой ход.1-ый шаг. Так как коэффициент a11 = 2.0 наибольший из коэффициентов первого столбца, перестановки строк не требуется и 1-ый шаг полностью совпадает с 1-ым шагом примера 3.1. Из второго, третьего и четвертого уравнений исключается переменная x1 и система приводится к виду (3.11).
2-ой шаг. Наибольший по модулю коэффициент при x2 в системе (3.11) a= –1.15. Поэтому переставим уравнения следующим образом:
2.0x1 + 1.0x2 –0.1x3 + 1.0x4 = 2.7
–1.15x2 + 1.015x3 + 5.05x4 = – 4.305 (3.14)
0.3x2 + 4.02x3 –8.70x4 = 21.36
– 0.30x2 + 2.55x3 – 1.50x4 = 8.55
Вычислим множители:
m= = 
= –0.26087 m= = 
= 0.26087.
Вычитая из третьего и четвертого уравнений системы (3.14) второе уравнение, умноженное соответственно на mи m, приходим к системе:
2.0x1 + 1.0x2 –0.1x3 + 1.0x4 = 2.7
–1.15x2 + 1.015x3 + 5.05x4 = – 4.305 (3.15)
4.28478x3 – 7.38261x4 = 20.23696
2.28522x3 – 2.81739x4 = 9.67305
3-ий шаг. Вычислим множитель:
m= = 
= 0.53333.
Вычитая из четвертого уравнения системы (3.15) третье, умноженное на m, приведем систему к треугольному виду:
2.0x1 + 1.0x2 –0.1x3 + 1.0x4 = 2.7
–1.15x2 + 1.015x3 + 5.05x4 = – 4.305 (3.16)
4.28478x3 – 7.38261x4 = 20.23696
1.11998x4 = –1.11998
Обратный ход.Обратный ход полностью совпадает с обратным ходом примера 3.1. Решение системы имеет вид:
x1 = 1.000,x2 = 2.000, x3 = 3.000, x4 = – 1.000.