Численный метод решения систем линейных алгебраических уравнений на основе метрического алгоритма

Размещено на http://www.allbest.ru/

Технологический институт (филиал) ДГТУ в г. Азове

Численный метод решения систем линейных алгебраических уравнений на основе метрического алгоритма

В.Н. Таран

Е.Ю. Бойко,

А.М. Долженко

Для решения прикладных задач и составления прогнозов в различных сферах деятельности в большинстве случаев используется математическое моделирование. Все математические модели в той или иной степени сводятся к решению систем линейных алгебраических уравнений. Так как при решении реальных задач в качестве входных данных используется огромное количество параметров, то системы становятся большими или сверхбольшими, что приводит к длительным и трудоемким вычислениям.

Для решения систем линейных уравнений вида A·x=B существует множество методов. Их можно разделить на точные (позволяют найти решение за определенное количество шагов) и итерационные (позволяют найти решения в результате последовательных приближений). В отличие от точных методов, основным достоинством итерационных методов является том, что они могут применяться для решения больших систем. Наиболее распространенный метод решения таких задач - симплексный. Однако из-за громоздкости таблиц, содержащих большое количество неизвестных, и большого объема вычислительных работ, этот метод, как и многие другие, не всегда может применяться на практике. Другой метод решения таких систем -- метод декомпозиции (разложения), суть которого заключается в разложении исходной системы на подсистемы, для каждой из которых необходимо решать подзадачу меньшей размерности [1].

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

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

Постановка задачи

Цель настоящей статьи - описать численный метод решения систем линейных алгебраических уравнений на основе метрического алгоритма.

В рамках проводимого исследования решены следующие задачи:

- разработан метрический алгоритм, позволяющий находить решения систем линейных алгебраических решений с заданной точностью;

- разработан численный метод решения систем линейных алгебраических уравнений, основанный на метрическом алгоритме;

- проведено программное кодирование данного алгоритма.

Описание метода

Необходимо решить систему линейных алгебраических уравнений вида:

,

где ,

- евклидово пространство,

Для решения этой задачи большой размерности n метод Крамера не применим. Действительно, точные методы решения применяют для систем уравнений порядка , для итерационных - . Среди приближенных методов наибольшее применение получили: метод Гаусса, метод отражений, метод простой итерации, метод Зейделя и т.д. Однако на практике очень часто приходится решать задачи, в которых размерность может достигать и выше. В этих условиях традиционные методы не позволяют находить решения, т.к. требуются большие вычислительные ресурсы и время выполнения вычислений очень большое.

Поэтому в современном исполнении данная задача может быть решена с использованием множества компьютеров, объединенных в сеть, так называемых Grid-системах [7].Идея облачной самоорганизации заключается в том, что реализация алгоритма и все вычисления будут производиться не на одном дорогостоящем компьютере, а в облаке на множестве компьютеров (агентов), как показано на рис.1. Таким образом, задача «распараллеливается», т.е. каждому агенту системы «поручаются» отдельные вычисления, а затем в центре обработки результаты анализируются и определяется лучший [8-9].

В данном алгоритме используется так называемый перебор случайных возможных решений. На каждой итерации генерируется множество решений, из которых выбирается "лучшее" (близкое к истинному). Именно такие решения являются ценными для следующих итераций. Так, шаг за шагом, система стремится к нахождению решения задачи с заранее установленной точности.

Рис. 1 - Структурная схема

Данный алгоритм получил название метрический в связи с тем, что в его основу легло понятие метрики. Метрика - это функция, с помощью которой измеряется расстояние между решениями. Именно с помощью метрики определяется агент, который сгенерировал "лучшее" решение на данной итерации. Метрика обладает следующими свойствами:

,

,

,

.

Опишем алгоритм, состоящий из шести шагов [10].

Пусть имеется M компьютеров.

Шаг 1. Получение входных данных.

Каждый компьютер получает матрицу A при неизвестных.

Шаг 2. Генерация случайных векторов.

На каждом компьютере генерируется предполагаемые решения - случайные векторы из n случайных чисел.

Шаг 3. Преобразование случайных векторов из пространства решений в пространство сравнений.

На каждом из M компьютеров происходит умножение вектора на матрицу A. Таким образом, в результате умножения получаем следующие векторы:

.

Векторы образуют пространство сравнений, в котором, в частности, находится вектор B.

Шаг 4. Преобразование сдвига случайных векторов.

Множество векторов подвергается преобразованию сдвига:

.

Шаг 5. Определение расстояния в пространстве сравнений.

Определяется расстояние в евклидовом пространстве сравнений:

где - проекция вектора на n-ую координату евклидова пространства.

Шаг 6. Определение минимального расстояния в пространстве сравнений.

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

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

,

где - решение задачи,

-норма евклидового пространства.

Практическая апробация алгоритма

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

M=10, N=2, , ,.

На первой итерации случайным образом сгенерировано 10 векторов (рис.2).

Рис.2 - Генерация векторов на итерации №1

После проводимых вычислений значение метрики для вектора (0,25;1,03) минимально, поэтому агент, получивший это решение, становится центром генерации на следующем этапе (рис.3).

Рис.3 - Генерирование векторов на итерации №2

Таким образом происходят вычисления до тех пор, пока не будет .

На 10-ой итерации вектор принимает значение (1,014;1,987) (рис.4).

Рис.4 - Итерация №10

Таким образом, после проведения вычислений найдено решение заданной системы линейных алгебраических уравнений: (1,014;1,987) с допустимой погрешностью .

Заключение

В статье представлен новый численный метод решения больших систем линейных алгебраических уравнений, основанный на метрическом алгоритме. Эффект самоорганизации и облачные технологии позволяют по-новому взглянуть на проблему решения прикладных задач в различных сферах деятельности, в том числе, в промышленности, экономике, образовании, в области управления проектами и разработки программного обеспечения.

Литература

1. Лэсдон Л.Д. Оптимизация больших систем. М.: Наука, 1975, 432 с.

2. Бойко Е.Ю. Облачные технологии в оценке оптимального плана//Научно-техническая конференция профессорско-преподавательского состава, сотрудников и студентов АТИ ДГТУ по итогам работы за 2012-2013 гг. Донской государственный технический университет, Азовский технологический институт. Азов, 2013. С. 45-48.

3. Таран В.Н., Бойко Е.Ю. Метрический подход к решению систем линейных алгебраических уравнений// Транспорт: наука, образование, производство, труды международной научно-практической конференции. 2016. С. 325-327.

4. Таран В.Н., Бойко Е.Ю., Долженко А.М. Программа для реализации метрического алгоритма решения систем линейных алгебраических уравнений. Свидетельство о регистрации программ ЭВМ от 06.02.2017 № 2017611577.

5. Moradi, M.Dezfuli, M.A.Safavi, A new time optimizing probabilistic load balancing algorithm in grid computing // Department of Computer and IT, Engineering, Amirkabir University of Technology, Tehran, Iran, 2010, vol. 1, pp. v1232-v1237.

6. Hewwit C. ORGs for Scalable, Robust, Privacy-Friendly Client Cloud Computing / Carl Hewwit // IEEE Internet Computing, vol. 12, no. 5. - NY, USA, Sep.-Oct. 2008. -Pp. 96-99. - DOI: 10.1109/MIC.2008.107.

7. Курейчик В.М., Таран А.Е., Ляпунова И.А Реализация муравьиного алгоритма на ГРИД-системе// Вестник Ростовского государственного университета путей сообщения. 2015. №4(60). С. 48-52.

8. Таран А.Н., Гусева Л.Л. Применение облачных информационных технологий к задачам межотраслевого баланса // Информационные технологии в экономических исследованиях: материалы научно-практической конференции. Ростов н/Д: ДГТУ,2013.- 141 с.

Аннотация

В статье рассматриваются проблемы математического моделирования больших систем. Научная новизна работы заключается в реализации нового численного метода решения систем линейных алгебраических уравнений, основанного на целенаправленном хаотическом поиске, стохастических вычислениях и использовании облачных технологий. читателей.

Ключевые слова: системы линейных алгебраических уравнений, облачные технологии, самоорганизация, метрика.