Вычислительная математика
Трудоемкость метода. Для реализации метода исключения Гаусса требуется примерно 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.3 Метод исключения Гаусса с выбором главного элемента по столбцу
Хотя
метод Гаусса
является точным
методом, ошибки
округления
могут привести
к существенным
погрешностям
результата.
Кроме того
исключение
по формулам
(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.
3.4 Вычисление определителя методом исключения Гаусса
Из курса линейной алгебры известно, что определитель треугольной матрицы равен произведению диагональных элементов. В результате метода исключений Гаусса система линейных уравнений (3.2) с квадратной матрицей A приводится к эквивалентной ей системе (3.8) с треугольной матрицей An. Поэтому
det A = (–1)s det An,
где s – число перестановок строк, (s = 0, если использовался метод Гаусса по схеме единственного деления).Таким образом,
det
A
= (–1)s
a11
a
a
…a
(3.17)
Итак, для вычисления определителя det A необходимо выполнить процедуру прямого хода в методе Гаусса для системы уравнений Ax = 0, затем найти произведение главных элементов, стоящих на диагонали треугольной матрицы и умножить это произведение на (–1)s, где s – число перестановок строк.
Пример 3.3.
Вычислим определитель det A =
![]()
2.0
1.0 0.1 1.0
0.4 0.5 4.0 8.5
0.3 1.0 1.0 5.2
1.0 0.2 2.5 1.0
Данный определитель совпадает с определителем системы, рассмотренной в примере 3.1. Он равен произведению диагональных элементов треугольной матрицы (3.13):
det A = 2.0 Ч 0.30 Ч 16.425 Ч 1.12 = 11.0376.
Если же обратиться к примеру 3.2, то, учитывая, что была одна перестановка строк, т.е. s = 1, получим:
det A = (–1) Ч 2.0 Ч (–1.15) Ч 4.28478 Ч 1.11998 = 11.0375.
3.5 Вычисление обратной матрицы методом исключения Гаусса
Обратной матрицей к матрице A называется матрица A-1, для которой выполнено соотношение:
A A-1 = E, (3.18)
где E – единичная матрица:
1
0 0 … 0
0 1 0 … 0
E = 0 0 1 … 0 . (3.19)
0 0 0 … 1
Квадратная матрица A называется невырожденной, если det A № 0. Всякая невырожденная матрица имеет обратную матрицу.
Вычисление обратной матрицы можно свести к рассмотренной выше задаче решения системы уравнений.
Пусть A – квадратная невырожденная матрица порядка n:
a11
a12
a13
… a1n
a21 a22 a23 … a2n
A = a31 a32 a33 … a3n
an1 an2 an3 … ann
и A-1 – ее обратная матрица:
x11 x12
x13 … x1n
x21 x22 x23 … x2n
A-1 = x31 x32 x33 … x3n
xn1 xn2 xn3 … xnn
Используя соотношения (3.18), (3. 19) и правило умножения матриц, получим систему из n2 уравнений с n2 переменными xij, i, j = 1, 2, …, n. Чтобы получить первый столбец матрицы E, нужно почленно умножить каждую строку матрицы A на первый столбец матрицы A-1 и приравнять полученное произведение соответствующему элементу первого столбца матрицы E. В результате получим систему уравнений:
a11x11
+ a12
x21
+ a13x31
+ … + a1nxn1
= 1
a21x11 +