Вычислительная сложность метода Гаусса с частичным выбором главного элемента

Лекция 9. ВЫЧИСЛИТЕЛЬНАЯ СЛОЖНОСТЬ ПРЯМЫХ МЕТОДОВ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ

1. Вычислительная сложность метода Гаусса с частичным выбором главного элемента.
2. Вычислительная сложность метода Гаусса с полным выбором главного элемента.
3. Сравнение методов Гаусса с частичным и полным выбором главного элемента по точности и вычислительной сложности.
4. Вычислительная сложность метода, основанного на LU-разложении матрицы системы. Сравнение LU-метода и метода Гаусса

Пусть необходимо решить СЛАУ

. (5)

Выбор главного элемента перед исключением в первом столбце матрицы СЛАУ осуществляется в области, ограниченной красным цветом на рис.1, между элементами первого столбца. Для такого выбора потребуется провести операцию сравнения.

Рис.1.

После выбора главного элемента и перестановки соответствующих строк матрицы и соответствующих элементов вектора правой части (это подробно описано в лекции 8), осуществляется пересчет элементов матрицы и вектора правой части, стоящих после перестановки на позициях, ограниченных синим цветом на рис.1. Количество этих элементов - в матрице СЛАУ и в векторе правой части. Пересчет каждого элемента матрицы на 1-м шаге исключения происходит в соответствии с формулой (формула (5) лекции 8):

, (10)

здесь - элементы матрицы СЛАУ после 1-го шага исключения (аналогичной будет формула для пересчета элементов вектора правой части), т.е. требует 3 арифметических операций – 1 умножение, 1 деление, 1 вычитание. Тогда на весь пересчет при первом шаге исключения Гаусса потребуется арифметических операций.

Суммарно на первый шаг метода Гаусса будет затрачено:

Перед проведением исключений во втором столбце матрицы СЛАУ (второй шаг метода Гаусса) выбор главного элемента осуществляется в области, ограниченной красным цветом на рис.2, между элементом второго столбца. Для такого выбора потребуется провести операции сравнения.

Рис.2.

После выбора главного элемента и перестановки соответствующих строк матрицы и соответствующих элементов вектора правой части, осуществляется пересчет элементов матрицы и вектора правой части, стоящих после перестановки на позициях, ограниченных синим цветом на рис.2. Количество этих элементов - в матрице СЛАУ и в векторе правой части. Пересчет каждого элемента матрицы на 2-м шаге исключения происходит в соответствии с формулой (10): , здесь - элементы матрицы СЛАУ после 2-го шага исключения (аналогично для пересчета элементов вектора правой части). Тогда на весь пересчет при втором шаге исключения Гаусса потребуется арифметических операций. Суммарно на второй шаг метода Гаусса будет затрачено:

И т.д. Перед проведением исключений в столбце матрицы СЛАУ для выбора главного элемента потребуется провести операций сравнения. Пересчет при исключении коснется элементов в матрице СЛАУ и элементов в векторе правой части, для чего потребуется арифметических операций. Суммарно на ый шаг метода Гаусса будет затрачено:

Всего для прямого хода метода Гаусса при решении СЛАУ размерами потребуется шаг (()-ый шаг отвечает исключению в -ом столбце матрицы СЛАУ). Учитывая это, можем посчитать полное количество операций для проведения прямого хода метода Гаусса:

Шаг прямого хода метода Гаусса	Количество сравнений для выбора главного элемента	Количество операций для пересчета элементов матрицы и вектора правой части
		3+3
ВСЕГО
Полное количество операций для проведения прямого хода метода Гаусса:

Итак, общее количество операций для проведения прямого хода метода Гаусса:

Результатом прямого хода метода Гаусса является эквивалентная исходной система с верхней треугольной матрицей:

. (20)

Решение полученной СЛАУ осуществляется снизу вверх при помощи последовательной подстановки (обратный ход метода Гаусса). Определим вычислительную сложность обратного хода.

Из последнего уравнения СЛАУ (20):

,

Т.е. для вычисления понадобится 1 арифметическая операция.

Из предпоследнего уравнения СЛАУ (20), имея уже вычисленное на предыдущем шаге значение , получаем:

,

Т.е. для вычисления понадобится 3 арифметических операции. И т.д. Для вычисления из 1-го уравнения СЛАУ (20):

Потребуется арифметических операции. Тогда общее количество операций для решения СЛАУ с треугольной матрицей (обратный ход метода Гаусса) будет определяться как:

.

Таким образом, вычислительная сложность метода Гаусса с частичным выбором главного элемента решения СЛАУ размером равна :