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

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

Читайте также:
  1. A) на этапе разработки концепций системы и защиты
  2. A) Объективный и системный
  3. B. агроэкосистемой
  4. B. Любая матричная игра имеет решение, по крайней мере, в смешанных стратегиях
  5. Doctor Web для UNIX-систем.
  6. I. Системные программы.
  7. II. Формальная логика как первая система методов философии.
  8. IV. Ямайская валютная система
  9. L.1.1. Однокомпонентные системы.
  10. L.1.2.Многокомпонентные системы (растворы).
  11. V1: Экосистемы. Экология сообществ.
  12. V2: Женская половая система. Особенности женской половой системы новорожденной. Промежность.

В.П. Пинчук

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

Запорожье: ЗНТУ, 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 получаем:

.

 

 


Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)