 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Метод исключения Гаусса. Схема единственного деления
|
|
Основная идея метода исключений Гаусса состоит в том, что система уравнений (3.1) приводится к эквивалентной ей системе с верхней треугольной матрицей (прямой ход исключений), а затем неизвестные вычисляются последовательной подстановкой (обратный ход исключений).
Рассмотрим сначала простейший метод исключения Гаусса, называемый схемой единственного деления.
Прямой ход состоит из n - 1 шагов. На первом шаге исключается переменная x 1 из всех уравнений, кроме первого. Для этого нужно из второго, третьего, …, n- го уравнений вычесть первое, умноженное на величину
m =, i = 2, 3, …, n. (3.4)
При этом коэффициенты при x 1 обратятся в нуль во всех уравнениях, кроме первого.
Введем обозначения:
a = aij - ma 1 j, b= bi - mb 1(3.5)
Легко убедиться, что для всех уравнений, начиная со второго, a= 0, i = 2, 3, …, n. Преобразованная система запишется в виде:
a 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1 n xn = b 1
ax 2 + ax 3 + … + axn = b
a x 2 + ax 3 + … + axn = b (3.6)
ax 2 + ax 3 + … + axn = b
Все уравнения (3.6), кроме первого, образуют систему (n - 1)-го порядка. Применяя к ней ту же процедуру, мы можем исключить из третьего, четвертого, …, n- го уравнений переменную x 2. Точно так же исключаем переменную x 3 из последних 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 11 x 1 + a 12 x 2 + a 13 x 3 + … + a 1 n xn = b 1
ax 2 + ax 3 + …+ axn = b
ax 3 + …+ axn = b (3.8)
axn = 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/3 n 3 операций для прямого хода и n 2 операций для обратного хода. Таким образом, общее количество операций составляет примерно 2/3 n 3 + n 2.
Пример 3.1.
Применим метод исключения Гаусса по схеме единственного деления для решения системы уравнений:
2.0 x 1 + 1.0 x 2- 0.1 x 3 + 1.0 x 4 = 2.7
0.4 x 1 + 0.5 x 2 + 4.0 x 3- 8.5 x 4 = 21.9
0.3 x 1- 1.0 x 2 + 1.0 x 3 + 5.2 x 4 = -3.9 (3.10)
1.0 x 1 + 0.2 x 2 + 2.5 x 3- 1.0 x 4 = 9.9
Будем делать округление чисел до четырех знаков после десятичной точки.
Прямой ход. 1-ый шаг. Вычислим множители:
m = = = 0.2; m = = = 0.15; m = = = 0.5.
Вычитая из второго, третьего и четвертого уравнений системы (3.10) первое уравнение, умноженное соответственно на m, m, m, получим новую систему:
2.0 x 1 + 1.0 x 2- 0.1 x 3 + 1.0 x 4 = 2.7
0.3 x 2 + 4.02 x 3- 8.70 x 4 = 21.36
-1.15 x 2 + 1.015 x 3 + 5.05 x 4 = -4.305 (3. 11)
-0.30 x 2 + 2.55 x 3-1.50 x 4 = 8.55
2-ой шаг. Вычислим множители:
m = = = - 3.83333; m = = = -1.0.
Вычитая из третьего и четвертого уравнений системы (3.11) второе уравнение, умноженное соответственно на m и m, приходим к системе:
2.0 x 1 + 1.0 x 2- 0.1 x 3 + 1.0 x 4 = 2.7
0.3 x 2 + 4.02 x 3- 8.70 x 4 = 21.36
16. 425 x 3- 28.300 x 4 = 77. 575 (3.12)
6.570 x 3-10.200 x 4 = 29.910
3-ий шаг. Вычислим множитель:
m = = = 0.4.
Вычитая из четвертого уравнения системы (3.12) третье, умноженное на m, приведем систему к треугольному виду:
2.0 x 1 + 1.0 x 2- 0.1 x 3 + 1.0 x 4 = 2.7
0.3 x 2 + 4.02 x 3- 8.70 x 4 = 21.36
16. 425 x 3- 28.300 x 4 = 77. 575 (3.13)
1.12 x 4 = -1.12
Обратный ход. Из последнего уравнения системы (3.13) находим x 4 = 1.000. Подставляя значение x 4в третье уравнение, получим x 3= 2.000. Подставляя найденные значения x 4и x 3 во второе уравнение, найдем x 2 = 3.000. Наконец, из первого уравнения, подставив в него найденные значения x 4, x 3и x 2, вычислим x 1= -1.000.
Итак система (3.10) имеет следующее решение:
x 1= 1.000, x 2 = 2.000, x 3= 3.000, x 4 = - 1.000.
Дата публикования: 2014-11-18; Прочитано: 6619 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
