ИННОВАЦИИ БИЗНЕСУ

Результат выполнения научно-исследовательской работы.

Укажем операции над элементами матриц и векторов, влияющие на время расчета с их использованием. Эти операции можно разбить на следующие категории: (а) арифметические операции (сложение, вычитание, умножение, деление); ( b) копирование матриц и векторов, а также поиск нужного элемента. Назовем эти операции базовыми операциями. Условимся считать, что время на выполнение базовых операций приблизительно одинаково, т.е. все арифметические операции и операции копирования и поиска занимают одну единицу времени. Теперь для наиболее основных операций над матрицами и векторами рассчитываем затраты времени в единицах базовых операций.

КОПИРОВАНИЕ ВЕКТОРА b _nx1=a_nx1

Базовых операций типа (а): 0

Базовых операций типа ( b): n

Итого базовых операций: 0+ n=n (1)

КОПИРОВАНИЕ МАТРИЦЫ b _nxm=a _nxm

Базовых операций типа (а): 0

Базовых операций типа ( b): nm

Итого базовых операций: 0+ nm=nm (2)

ПРОИЗВЕДЕНИЕ ВЕКТОРОВ a_nx1·b ^t_nx1

Базовых операций типа (а): сумма ( n) произведений ( n) элементов: 2 n

Базовых операций типа ( b): n

Итого базовых операций: 3n (3)

ПРОИЗВЕДЕНИЕ МАТРИЦ a _nxk·b _kxm

Конечная матрица будет c _nxm

Базовых операций типа (а): nm элементов, каждый из которых есть сумма произведений двух векторов (столбец на строку). Всего nm3k (3 n ³)

Базовых операций типа (b): nm

Итого базовых операций: 3nmk+nm (4)

Как частный случай, ПРОИЗВЕДЕНИЕ МАТРИЦЫ НА ВЕКТОР a _nxkx _kx1

Итого базовых операций: 3 nk+n (5)

ОБРАЩЕНИЕ МАТРИЦЫ ОБЩЕГО ВИДА А ^-1_nxn

Под матрицей общего вида понимается то, что ее элементы имеют произвольные значения. Например, диагональную матрицу обратить гораздо проще.

Вычисление обратной матрицы можно провести методом Гаусса с прямым и обратным ходом. Рабочая матрица будет b _nx2n, в которой в начале метода левая половина есть матрица А, а правая - единичная матрица. Метод обрабатывает n строк, каждая из которых умножается на нулевой коэффициент и прибавляется к ( n-1) остальным строкам (векторам длиной 2 n). Таких базовых операций типа (а): n( n-1)3 (2n) = 6 n ²( n-1) = 6 n ³-6n ². После каждого i-го шага внедиагональные элементы первых i столбцов становятся нулевыми (на главной диагонали - единицы), поэтому если не проводить с ними операции, число базовых операций типа (а) равно

(3n ³-2n ²-n)

Базовых операций типа ( b): n ² (копирование конечного результата)

Итого базовых операций: n ³ - 3n ² - n (6)

ОБРАЩЕНИЕ ДИАГОНАЛЬНОЙ МАТРИЦЫ diag (aii) ^-1_nxn

Базовых операций типа (а): n

Итого базовых операций: 2 n (7)

ТРАНСПОРТИРОВАНИЕ МАТРИЦЫ А _nxn

Базовых операций типа (а): 0

Базовых операций типа ( b): n

Итого базовых операций: n (8)