Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Решение систем линейных уравнений, алгоритм Гаусса

Читайте также:
  1. B)& ЭЕМ үшін қолданылатын амалдардың реттелген тізбегі, қандай да бір есепті шешудің алгоритмі.
  2. DSM — система классификации Американской психиатрической ассоциации
  3. E) прокурором утвержден протокол об уголовном проступке и принято решение о направлении уголовного дела в суд
  4. EIS и DSS системы.
  5. ERP-система
  6. GRID- системи
  7. I Объективные характеристики (потребление материальных благ; продолжительность жизни; система образования; время труда; показатель преступности);
  8. I. Общеметодологические (общесистемные) принципы.
  9. I. Судебно-следственная практика формирования системы доказательств по уголовному делу (постановка проблемы).
  10. I.1. Инновационный подход к системе освоения ценностей физической культуры и спорта.

В.П. Пинчук

Анализ и построение алгоритмов. Краткий конспект лекций -

Запорожье: ЗНТУ, 2008.

 

Глава 5

Алгоритмы линейной алгебры

 

1. Умножение матрицы на вектор

2. Умножение матриц

3. Решение систем линейных уравнений, алгоритм Гаусса

4. Обращение матрицы

 

 

Умножение матрицы на вектор

 

Рассмотрим операцию умножения матрицы на вектор:

Y = A× X,

где А – квадратная матрица с размерами n´n, X, Y – векторы.

Формула умножения:

, i = 1.. n.

Несложный анализ дает следующий результат:

t = F(n) = Const×n2.

Отсюда:

F(n) = Q(n2).

 

 

Умножение матриц

 

Рассмтриваем операцию умножения для квадратных матриц:

C = A × B.

Все матрицы имеют размеры n´n. Рабочая формула умножения матриц:

.

Простой анализ алгоритма выполнения этой операции дает:

t = F(n) = Const×n3.

Отсюда:

F(n) = Q(n3).

 

 

Решение систем линейных уравнений, алгоритм Гаусса

 

Следующие задачи относятся к типовым (массовым) задачам линейной алгебры:

- вычисление определителя матрицы;

- получение обратной матрицы;

- решение системы линейных уравнений.

Процедуру решения каждой из этих задач можно разделить на несколько этапов и при этом каждая из них включает приведение матрицы к треугольной форме. Именно этот этап и определяет асимптотический класс функции сложности соответствующего алгоритма.

Напомним, что если исследуемый алгоритм состоит из двух этапов и функция сложности равна сумме:

F(n) = F1(n) + F2(n),

то, по правилам сложения асимптотических классов, слагаемое, имеющее меньшую скорость роста, можно опустить.

Выполним оценку времени выполнения процедуры приведения матрицы к треугольной форме. Будем использовать следующие предположения:

1) матрица имеет размеры n´n;

2) нумерация строк и столбцов матрицы начинается с единицы;

3) выбор главного элемента не будем учитывать.

C учетом сказанного, исследуемый алгоритма может быть представлен следующим образом:

 

for (i = 1; i <= n-1; i++) // внешний цикл

for (j = i+1; j <= n; j++) // средний цикл

{ Q = A[j][i] / A[i][i]; // время = c2

for (k = j; k <= n; k++) // внутренний цикл

A[j][k] = A[j][k] - Q*A[i][k]; // время = c1

}

 

Время выполнения внутреннего цикла равно:

.

Время работы среднего цикла:

.

Время выполнения алгоритма в целом соответствует времени работы внешнего цикла:

.

Теперь поэтапно выполняем суммирование:

Обозначим r = n - i, тогда

.

Отсюда получаем:

и на основе теоремы 1 получаем:

.

 

 




Дата добавления: 2015-04-12; просмотров: 11 | Поможем написать вашу работу | Нарушение авторских прав

<== 1 ==> |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав