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

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

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

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

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

Вычислительная сложность метода Гаусса с частичным выбором главного элемента - student2.ru . (5)

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

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

Рис.1.

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

Вычислительная сложность метода Гаусса с частичным выбором главного элемента - student2.ru , (10)

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

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

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

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

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

Рис.2.

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

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

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

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

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

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

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

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

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

Вычислительная сложность метода Гаусса с частичным выбором главного элемента - student2.ru . (20)

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

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

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

Т.е. для вычисления Вычислительная сложность метода Гаусса с частичным выбором главного элемента - student2.ru понадобится 1 арифметическая операция.

Из предпоследнего уравнения СЛАУ (20), имея уже вычисленное на предыдущем шаге значение Вычислительная сложность метода Гаусса с частичным выбором главного элемента - student2.ru , получаем:

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

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

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

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

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

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

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

Наши рекомендации