Теоретически обоснован рекурсивный матричный алгоритм ортогонализации. Алгоритм реализован в среде "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.

Основное содержание исследования

.

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

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

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

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

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

, .

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

.

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

.

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

.

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

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

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

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

Таблица 1. Статистика счета матрицы Грама

Уже при восьмом порядке аппроксимации требуется около 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.

Размещено на Allbest.ru