УДК 518.5.

ОЦЕНКА ЭФФЕКТИВНОСТИ РЕСУРСОСБЕРЕЖЕНИЯ РЕКУРСИВНОГО МАТРИЧНОГО АЛГОРИТМА ОРТОГОНАЛИЗАЦИИ

Б,

Россия, Липецк, Липецкий ГТУ

Теоретически обоснован рекурсивный матричный алгоритм ортогонализации. Алгоритм реализован в среде "Mathematica". Разработана методика планирования потребного объема вычислений под ограниченные ресурсы компьютера. Методика апробирована на задачах теории упругости для трехмерного тела.

Recursive matrix algorithm of orthogonalization is theoretical founded. The algorithm is realized in the environment of the "Mathematica". The method was developed for planning required volume of calculations under the limited resources of the computer. Methodology is approved on the problems of the elasticity theory for three-dimensional body.

Среди энергетических методов с современных позиций заявил себя метод граничных состояний (МГС), опирающийся на понятия пространств внутренних и граничных состояний среды, их гильбертов изоморфизм, представление результирующего состояния рядом Фурье по элементам ортонормированного базиса [1]. Его особенности: ориентация на компьютерные алгебры; высокая точность и аналитическая форма промежуточных и финишных результатов счета; облегченность тестирования на каждом этапе решения; удобство интерпретации результатов счета; самодостаточность при оценке адекватности (отпадает необходимость сравнения с результатами, полученных иными методами); решение основных задач сводится к рутинному вычислению коэффициентов Фурье.

НЕ нашли? Не то? Что вы ищете?

Основная трудность метода связана с ортогонализацией исходного базиса состояний. Возникает необходимость в разработке алгоритма, который обладает качествами: надежность результатов ортогонализации; возможность пополнения ортонормированного базиса посредством наращивания его отрезка; возможность «заказывать» величину приращения базиса, исходя из доступного ограниченного времени счета.

Теоретическое обоснование рекурсивно-матричного алгоритма ортогонализации

В основе разработки означенного алгоритма лежит известная теорема Гильберта - Шмидта [2]. На ее основе авторами разработан рекурсивно-матричный машинно-ориентированный алгоритм ортогонализации, в котором процесс Шмидта переписан в форме, использующей лишь перекрестные скалярные произведения элементов исходного базиса, которые сведены в матрицу Грама: .

Алгоритм вычисления левого матричного множителя H, переводящего исходный базис в ортонормированный по правилу , состоит в следующей последовательности шагов:

а) заготавливаются нулевые матрица и ее вспомогательный «предшественник» размерностью ;

б) на первом шаге ортогонализации кладется ;

в) выполняется перебор шагов ортогонализации . На каждом шаге проводятся вычисления в соответствии с г). По завершении перебора процесс формирования левого ортогонализирующего множителя для исходного базиса построен;

г) для диагонального элемента полагается . Поддиагональные элементы матрицы-«предшественника» вычисляются по правилу

, .

Вывод заключен в преобразованиях, в которых учтено, что при :

.

Вычисляется квадрат нормы -го ортогонального элемента .

Это выражение получено из рассмотрения скалярного произведения:

.

Вся строка ортогонализирующего множителя нормируется: .

Проверку адекватности результата можно провести двумя способами. Во-первых, должно выполняться тождество (норма матрицы , вычисленная любым способом, служит основанием для суждения о погрешности численной реализации метода). Во-вторых, выборочные тесты вида , где - символ Кронекера, также являются основой для положительного заключения об адекватности. Описание алгоритма можно найти в публикации [3].

Оценка эффективности ресурсосбережения

В результате численных экспериментов по построению матрицы Грама в среде Mathematica 5 на IBM PC-совместимом компьютере с процессором INTEL Pentium4 (2400 MHz 512k 533 MHz) были получены следующие статистические данные, приведенные в табл.1, где p – максимальный порядок многочленов, n – количество удерживаемых элементов базиса, t – время расчета матрицы Грама (в секундах).

Таблица 1

Статистика счета матрицы Грама

p

1

2

3

4

8

n

6

21

42

69

237

t, с

1

29

221

1005

39414

Уже при восьмом порядке аппроксимации требуется около 11 часов непрерывного времени счета для построения матрицы Грама на достаточно мощном компьютере.

Построены зависимости времени вычисления матрицы Грама от порядка многочленов p, при помощи которых описывается внутренне состояние среды. Функция регрессии соответствует многочлену третьего, – четвертого порядка. Сопоставление при малых убеждает в том, что удачной аппроксимацией является .

Посредством выполнения линейной регрессии статистических данных на базах многочленов и были построены зависимости времени вычисления матрицы Грама от длины удерживаемого отрезка базиса. Результаты регрессии в этих случаях практически не отличаются (, - законы регрессий, построенных на многочленах третьего и четвертого порядков соответственно), поэтому используем многочлен третьего порядка: . Построена зависимость длины базиса от времени вычисления матрицы грамма (рис.1):

.

Функции N и F строились как взаимно-обратные. Если длина удерживаемого базисного отрезка находится в «рабочем» диапазоне от 100 до 400, то погрешность составляет около 0.5%. Таким образом, можно считать .

Обработка статистических материалов позволяет дать ответы на ряд вопросов практического содержания:

Рис.1. Зависимость длины базиса от времени построения матрицы Грамма

1.  Зависимость времени счета от длины удерживаемого базисного отрезка позволяет оценить необходимое время расчета в часах матрицы Грамма размерности : (час).

2.  Та же зависимость позволяет оценить необходимое время счета для пополнения базиса длиной на элементов: (час).

3.  Зависимость длины базиса от времени построения матрицы Грамма позволяет оценить длину отрезка базиса, которую можно нарастить за фиксированное (ограниченное) время , откуда следует: . Цепочка преобразований позволяет дать оценку .

Вышеприведенные зависимости определяют методику оценки длины приращения отрезка ортонормированного базиса «под ограниченные компьютерные ресурсы».

Литература

1.  Пеньков, граничных состояний для решения задач линейной механики. [Текст] / , // Дальневосточный математический журнал. — 2001. — Т.2, №2. — С.115-137.

2.  , Фомин теории функций и функционального анализа. – 7-е изд. – М.: ФИЗМАТЛИТ, 2004. – 572 с.

3.  Пеньков, алгоритмы метода граничных состояний [Текст] / , // Научно-методический семинар преподавателей теоретической механики вузов России: тезисы докладов (5-9 октября 2009 г.) / Юж.-Рос. гос. техн. Ун-т. – Новочеркасск: ЮРГТУ, 2009. – С. 29-31.

, д. ф.-м. н., профессор. Липецкий ГТУ, профессор. *****@***ru, 6-19.

, к. ф.м. н. Липецкий ГТУ, доцент.

*****@***ru 2-08.