«Санкт-Петербургский государственный электротехнический университет «лэти» им. В.И.Ульянова (Ленина)» (сПбГэту «лэти»)

Выпускная квалификационная работа бакалавра Тема: решение тропических линейных уравнений с трехдиагональными матрицами

Санкт-Петербург

2020

Санкт-Петербургский государственный электротехнический университет

“ЛЭТИ” им. В. И. Ульянова (Ленина)

(СПбГэту “лэти”)

Задание на выпускную квалификационную работу

Место выполнения ВКР: _ кафедра АМ_______________________________

2. Объект и предмет исследования

Объект исследования – решение систем тропических линейных уравнений. Предмет исследования – алгоритм Григорьева

3. Цель

Построение оптимизации алгоритма Григорьева для трёхдиагональных матриц

4. Исходные данные

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

5. Содержание

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

7. Дополнительные разделы

Экономическое обоснование ВКР

8. Результаты

Программная реализация построенного преобразования алгоритма для узкого класса матриц требует меньше времени и памяти, чем реализация общего алгоритма.

Санкт-Петербургский государственный электротехнический университет

“ЛЭТИ” им. В. И. Ульянова (Ленина)

(СПбГЭТУ “ЛЭТИ”)

КАЛЕНДАРНЫЙ ПЛАН

выполнения выпускной квалификационной работы

Реферат

Пояснительная записка содержит: 55 с., 6 рис., 7 табл., 2 приложения, 20 источников литературы.

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

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

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

ABSTRACT

Grigoriev algorithm is tropical counterpart of Gaussian elimination designed for solving systems of tropical linear equations. The study aims to explore the algorithm and find ways to specialize it for equarions which can be represented with tridiagonal matrices.

The study contains basic definitions of tropical algebra, which is required for Grigoriev algorithm exploration, it's comparison with Gaussian elimination and shows attempts to create tropical counterpart of Thomas algorithm (which is simplified form of Gaussian elimination).

Tropical linear systems are widely used for designing neural networks and for solving tropical differential equations, hence the specialization of Grigoriev algorithm can lead to more effective ways of solving problems in this fields.

СОДЕРЖАНИЕ

«Санкт-Петербургский государственный электротехнический университет 1

ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ 9

ВВЕДЕНИЕ 11

1 ТРОПИЧЕСКИЕ СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ 12

1.1 Определение тропической математики 12

1.2 Тропические многочлены и матрицы 13

1.3 Решение тропической системы линейных уравнений 16

1.4 Описание алгоритма Григорьева 18

1.5 Пример работы алгоритма Григорьева 22

1.6 Тропические рекуррентные последовательности 24

Вывод 26

2 АЛГОРИТМ ГАУССА И ТРЁХДИАГОНАЛЬНЫЕ МАТРИЦЫ 27

2.1 Метод Гаусса-Жордана 27

2.2 Алгоритм Гаусса 28

2.3 Схема выбора главного элемента 28

2.4 Трёхдиагональные матрицы и метод прогонки 29

Вывод 31

3 СРАВНЕНИЕ АЛГОРИТМОВ ГАУССА И ГРИГОРЬЕВА 32

3.1 Сравнение шагов алгоритма Гаусса и алгоритма Григорьева 32

3.2 Переупорядочивание строк и столбцов 34

Вывод 35

4 МОДИФИКАЦИЯ АЛГОРИТМА ГРИГОРЬЕВА ДЛЯ ТРЁХДИАГОНАЛЬНЫХ МАТРИЦ 36

4.1 Идеи модификации алгоритма Григорьева 36

4.2 Модификация программы 38

Вывод 40

5 ЭКОНОМИЧЕСКОЕ ОБОСНОВАНИЕ 41

5.1 Обоснование целесообразности исследования 41

5.2 Трудоёмкость и календарный план 41

5.3 Оценка величины заработной платы и социальных отчислений участников исследования и разработки 42

5.4 Расчёт амортизации 45

5.5 Расчёт себестоимости разработки системы 47

Вывод 49

ЗАКЛЮЧЕНИЕ 50

СПИСОК ЛИТЕРАТУРЫ 51