- •«Санкт-Петербургский государственный электротехнический университет «лэти» им. В.И.Ульянова (Ленина)» (сПбГэту «лэти»)
- •Выпускная квалификационная работа бакалавра Тема: решение тропических линейных уравнений с трехдиагональными матрицами
- •Санкт-Петербургский государственный электротехнический университет
- •(СПбГэту “лэти”)
- •Задание на выпускную квалификационную работу
- •Реферат
- •Определения, обозначения и сокращения
- •Введение
- •1 Тропические системы линейных уравнений
- •Определение тропической математики
- •Тропические многочлены и матрицы
- •1.3 Решение тропической системы линейных уравнений
- •1.4 Описание алгоритма Григорьева
- •1.5 Пример работы алгоритма Григорьева
- •1.6 Тропические рекуррентные последовательности
- •2 Алгоритм гаусса и трёхдиагональные матрицы
- •2.1 Метод Гаусса-Жордана
- •2.2 Алгоритм Гаусса
- •2.3 Схема выбора главного элемента
- •Трёхдиагональные матрицы и метод прогонки
- •Сравнение алгоритмов гаусса и григорьева
- •3.1 Сравнение шагов алгоритма Гаусса и алгоритма Григорьева
- •3.2 Переупорядочивание строк и столбцов
- •Модификация алгоритма григорьева для трёхдиагональных матриц
- •4.1 Идеи модификации алгоритма Григорьева
- •4.2 Модификация программы
- •5 Экономическое обоснование
- •5.1 Обоснование целесообразности исследования
- •5.2 Трудоёмкость и календарный план
- •5.3 Оценка величины заработной платы и социальных отчислений участников исследования и разработки
- •5.4 Расчёт амортизации
- •5.5 Расчёт себестоимости разработки системы
- •Заключение
- •Список литературы
- •Приложение а
- •Приложение б
3.2 Переупорядочивание строк и столбцов
В разделе 1.4 уже говорилось о том, что для корректной работы алгоритма Гаусса используют схему выбора главного элемента. Она гарантирует, что первый ненулевой элемент каждой строки будет лежать на главной диагонали, и при этом он будет максимальным по модулю из всех вариантов, которые могли бы получиться при другом расположении столбцов или строк. Такая схема, если определитель матрицы отличен от нуля, всегда приводит к единственному решению.
В алгоритме Григорьева отражён и этот подход. В разделе 1.4 сказано, что порядок добавления столбцов во множество J неоднозначен. Выбирая, какой столбец добавить следующим, мы можем менять порядок строк и столбцов: на -ой итерации спуска тот элемент, из-за которого столбец добавляется в J, должен оказаться на главной диагонали. То есть, переходя к терминологии раздела 1.4, если на k-ой итерации в строке l есть строгий минимум по не лежащим в J столбцам, и он лежит в строке p, то нужно поменять строки и столбцы так, чтобы этот минимум оказался на главной диагонали, т. е.
, при , , ; , , ,
где – это элемент матрицы системы из уравнения в системе, а его индекс показывает, что элемент стоит на главной диагонали в -ой строке. Такие перестановки позволяют говорить о том, что если c – это мощность множества J, то все минимумы первых c строк будут лежать не выше главной диагонали матрицы. Если затем переставить на позиции строки, минимумы которых вовсе не лежат на не принадлежащих J столбцах, то будет гарантировано, что для всех остальных строк будет выполняться, что
то есть найдётся хотя бы два таких столбца вне множества J, что в них будут лежать минимумы каждой из этих строк.
Польза от таких перестановок заключается в следующем: если матрица размера будет тропически невырожденной, то решений системы нет, алгоритм должен будет остановить работу – аналогично алгоритму Гаусса, где в схеме с выбором главного элемента существование решения определяется по невырожденности подматрицы.
Вывод
В разделе 3 приведено сравнение двух алгоритмов – алгоритма Гаусса и его тропического аналога, алгоритма Григорьева. Все описанные идеи – это результат исследования, аналогичных рассуждений в источниках найдено не было.
Подводя итог сравнения, отмечу, что аналогия просматривается не всегда или не во всех пунктах интуитивно понятна мне. Поэтому в четвёртом разделе будут сформулированы только идеи и попытки их переноса между областями математики, которые могут не привести к желаемым результатам.
Модификация алгоритма григорьева для трёхдиагональных матриц
Так как для трёхдиагональных матриц существует описанная в разделе 2.4 модификация, стоит попробовать придумать аналогичный ей алгоритм, немного изменив алгоритм Григорьева.
4.1 Идеи модификации алгоритма Григорьева
Пользуясь разделом 2.4, выделим основные моменты, которые могут оказаться важными при переходе к тропической математике.
Во-первых, нулём (нейтральным по сложению элементом) в тропической математике является бесконечность, поэтому матрица имеет вид:
где при .
Во-вторых, для вычисления прогоночных коэффициентов используется только три (а для первой и последней строк два) элемента матрицы системы в каждой строке. Аналог такой идеи очевиден: минимумы стоит искать не по всей строке, а по трём элементам, лежащим на известных местах. Таким образом, вместо просмотра m элементов для поиска минимума и подсчёта числа его повторений в строке нужно просмотреть только три – с сложность уменьшается до , то есть константной сложности.
В-третьих, в методе прогонки на элементы накладываются определенные условия-неравенства, выполнение которых гарантирует существование решения, в то время как в алгоритмах Гаусса и Григорьева имеет решения только невырожденная в соответствующих терминах матрица. Переносить их на алгоритм Григорьева бессмысленно, ведь они возникли для исключения деления на 0.
В-четвёртых, есть реализации метода прогонки, в которых предполагается распараллеливание: матрица делится на подматрицы, в которых и происходит исключение переменных, лежащих ниже главной диагонали. В алгоритм Григорьева перенести это не удастся – в нём важно количество минимумов, а значит, нельзя разбивать строки. Также изменения затрагивают весь столбец: к нему, если он добавлен во множество J, добавляется константа. Соответственно, распараллелить эту задачу иным способом, чем искать и считать минимумы, а потом изменять столбцы в разных потоках, не удастся.
В-пятых, по внешнему виду матрицы очевидно, что можно оптимизировать поиск перманента: ведь в классических терминах от перманента останутся лишь три слагаемых. Так как тропический перманент – это минимум из сумм элементов перестановок, о чём говорится в разделе 2, а добавление бесконечности к чему угодно даёт бесконечность, в перманенте так же стоит учитывать только три диагонали матрицы. Таким образом, проверять матрицу на вырожденность становится проще, а значит, если эта проверка выполняется на каждой итерации спуска (раздел 1.4), то выигрыш во времени становится ощутимым. Стоит отметить, что известное рекуррентное соотношение его вычисления также просто переносится в тропическую математику: для матрицы размера перманент, обозначенный как , вычисляется через и :
Теперь заменим тропические операции их аналогами классической математики:
|
(4.1) |
Сложность вычисления перманента в таком варианте линейна. Но такое решение позволяет узнать только то, чему равен искомый минимум, а для невырожденности матрицы необходимо подсчитывать количество таких минимумов.