Глава 1. Свойства и характеристики алгоритма продольно-поперечной прогонки

Министерство образования Республики Беларусь

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

Кафедра вычислительной математики

ДРУЖКИНА

Антонина Игоревна

Свойства и характеристики алгоритма продольно-поперечной прогонки

Курсовая работа

Допущена к защите

“___” _____________ 2016 г

Зав. кафедрой вычислительной математики

кандидат физико-математических наук, доцент П.А. Мандрик

Минск, 2016

АННОТАЦИЯ

Изучаются основы метода переменных направлений (метода продольно-поперечной прогонки) численного решения двумерных параболических уравнений. Описаны некоторые свойства и структуру алгоритма продольно-поперечной прогонки.

АНАТАЦЫЯ

Вывучаюцца асновы метаду пераменных напрамкаў (метаду падоўжна - папярочнай прагонкi) колькаснага рашэння двухмерных парабалічных раўнанняў. Апісаны некаторыя асаблiвасці і структура алгарытму падоўжна - папярочнай прагонкi.

ANNOTATION

Белорусский государственный университет

Факультет Прикладной математики и информатики

Кафедра Вычислительной математики

“Утверждаю”

Заведующий кафедрой

_______________П.А. Мандрик

“___” _______________ 2016 г.

Задание на курсовую работу

Студентке 3 курса 5 группы Дружкиной Антонине Игоревне

1. Тема курсовой работы: Свойства и характеристики алгоритма продольно-поперечной прогонки

2. Исходные данные к курсовой работе:

o Метод переменных направлений (метод продольно-поперечной прогонки) численного решения двумерных параболических уравнений ([1, 2]).

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

o Открытая энциклопедия свойств алгоритмов ([4]).

o Структура описания свойств алгоритмов ([4, 5]).

o Образцовая статья открытой энциклопедии свойств алгоритмов([4, 5]).

Список рекомендуемых источников:

1. Самарский А.А. Теория разностных схем. – М: Наука. 1977. – 656 c. [Электрон. ресурс – \\fpmi-stud\Subfaculty\Каф. Выч. Мат

2. Полевиков В.К. Численные методы математической физики. Курс лекций. – Мн: 2010. - 107 c. [Электрон. ресурс – \\fpmi-stud\Subfaculty\Каф. Выч. Мат\Polevikov]

3. Рычков А.Д. Курсовые работы по параллельным вычислительным технологиям. Пособие [Электронный ресурс] – 2013. Режим доступа: http://csc.sibsutis.ru/sites/csc.sibsutis.ru/files/courses/pvt/%20работы.pdf. Дата доступа: 15.09.2015.

4. Открытая энциклопедия свойств алгоритмов. URL: http://algowiki-project.org

5. Фролов А.В., Воеводин В.В., Коньшин И.Н., Теплов А.М. Исследование структурных свойств алгоритма разложения Холецкого: от давно известных фактов до новых выводов. // Параллельные вычислительные технологии (ПаВТ’2015): Труды международной научной конференции (Екатеринбург, 31марта – 2 апреля 2015 г.). Челябинск: Издательский центр ЮУрГУ, 2015. С. 365–369.

3. Перечень подлежащих разработке вопросов:

§ Изучить основы метода переменных направлений (метода продольно-поперечной прогонки) численного решения двумерных параболических уравнений ([1, 2])

§ Ознакомиться с параллельными алгоритмы, реализующими продольно-поперечную прогонку ([3], рабочие материалы).

§ Ознакомиться с концепцией открытой энциклопедии свойств алгоритмов ([4]).

§ Ознакомиться со схемой, по которой предлагается описывать свойства и структуру алгоритмов ([4, 5]).

§ Описать некоторые свойства и структуру алгоритма продольно-поперечной прогонки.

§ Оформить результаты. Составить компьютерную презентацию к докладу работы на защите.

4. Перечень графического материала:

¯ Логотип БГУ для включения на слайды презентации.

¯ (?) Схемы, поясняющие получение параллельных алгоритмов.

5. Примерный календарный график выполнения работы:

· октябрь-ноябрь – изучение основных теоретических вопросов;

· ноябрь-декабрь – описание, оформление теоретической части работы;

· декабрь-апрель– программирование, практическая реализация задач работы;

· апрель-май – оформление результатов работы (отчета, презентации, приложений), подготовка доклада и отладка презентации на защиту;

· май –выступление с докладом, защита работы на семинаре кафедры.

6. Дата выдачи задания __ октября 2015 г.

7. Срок сдачи законченной курсовой работы __ мая 2016 г.

Руководитель______________ Н.А. Лиходед __. октября 2015 г.

Подпись студента ______________

Дата

Реферат

Курсовая работа, 21 стр., 2 рис., 5 источников.

Ключевые слова: ПРОДОЛЬНО-ПОПЕРЕЧНАЯ ПРОГОНКА, ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ, ТАЙЛИНГ.

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

Цель работы: изучить основы метода переменных направлений (метода продольно-поперечной прогонки) численного решения двумерных параболических уравнений; ознакомиться с концепцией открытой энциклопедии свойств алгоритмов.

Методология проведения работы:

Результаты работы:

Область применения результатов:

ОГЛАВЛЕНИЕ

ПЕРЕЧЕНЬ УСЛОВНЫХ ОБОЗНАЧЕНИЙ.. 5

ВВЕДЕНИЕ. 6

Глава 1. Свойства и характеристики алгоритма продольно-поперечной прогонки 7

1.1 Общее описание алгоритма. 7

1.2 Математическое описание алгоритма. 7

1.3 Вычислительное ядро алгоритма. 10

1.4 Макроструктура алгоритма. 10

1.5 Схема реализации последовательного алгоритма. 10

1.6 Последовательная сложность алгоритма. 11

1.7 Информационный граф. 11

1.8 Описание ресурса параллелизма алгоритма. 11

1.9 Входные и выходные данные алгоритма. 11

Глава 2. Программная реализация алгоритма. 13

2.1 Особенности реализации последовательного алгоритма. 13

2.2 Локальность данных и вычислений. 13

2.3 Возможные способы и особенности параллельной реализации алгоритма 13

2.4 Масштабируемость алгоритма и его реализации. 13

2.5 Динамические характеристики и эффективность реализации алгоритма 13

2.6 Выводы для классов архитектур. 13

2.7 Существующие реализации алгоритма. 13

ЗАКЛЮЧЕНИЕ. 15

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 16

ВВЕДЕНИЕ

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

Для достижения поставленной цели необходимо:

1. Изучить основы метода переменных направлений (метода продольно-поперечной прогонки) численного решения двумерных параболических уравнений.

2. Ознакомиться с параллельными алгоритмы, реализующими продольно-поперечную прогонку ([3], рабочие материалы).

3. Ознакомиться с концепцией открытой энциклопедии свойств алгоритмов.

4. Ознакомиться со схемой, по которой предлагается описывать свойства и структуру алгоритмов.

5. Описать некоторые свойства и структуру алгоритма продольно-поперечной прогонки.

6. Оформить результаты. Составить компьютерную презентацию к докладу работы на защите.

Глава 1. Свойства и характеристики алгоритма продольно-поперечной прогонки