Применение параллельных методов решения систем линейных уравнений ленточных матриц

Параллельные методы решения систем линейных уравнений с ленточными матрицами. Метод "встречной прогонки". Реализация метода циклической редукции. Применение метода Гаусса к системам с пятидиагональной матрицей. Результаты численного эксперимента.

Рубрика Математика
Вид курсовая работа
Язык русский
Дата добавления 21.10.2013
Размер файла 661,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

Применение параллельных методов решения систем линейных уравнений ленточных матриц

1. Параллельные методы решения СЛАУ с ленточными матрицами

К решению систем линейных алгебраических уравнений сводятся многочисленные практические задачи (по некоторым оценкам более 75% всех задач). Можно с полным основанием утверждать, что решение линейных систем является одной из самых распространенных и важных задач вычислительной математики.

Конечно, существует много методов и современных пакетов прикладных программ для решения СЛАУ, но для того, чтобы их успешно использовать, необходимо разбираться в основах построения методов и алгоритмов, иметь представления о недостатках и преимуществах используемых методов.

Часто возникает необходимость в решении СЛАУ с матрицами, которые являются слабо заполненными, т.е. содержат много нулевых элементов. В то же время эти матрицы имеют определенную структуру. Среди таких систем выделим системы с матрицами ленточной структуры, в которых ненулевые элементы располагаются на главной диагонали и на нескольких побочных диагоналях, т.е. , если , где , числа и называют шириной верхней и нижней полуленты, тогда - ширине ленты матрицы (пример одного из видов матриц в Приложении 1).

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

1.1 Метод прогонки для решения СЛАУ с 3-х-диагональными матрицами

1.1.1 Описание метода «прямой прогонки»

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

(1.1)

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

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

(1.2)

Исключая с помощью (1.2) неизвестную в -м уравнении, получим

Это - двучленное уравнение. Оно принимает вид (1. 2), если положить

(1. 3)

(1. 4)

А так как первое уравнение уже имеет двучленный вид, то

(1. 5)

Таким образом, рекуррентные соотношения (1. 3) - (1. 5) полностью определяют прогоночные коэффициенты , (). Уравнение (1. 2) при позволяет определить (), если известно . Для этого последнее уравнение системы (1. 1) сделаем формально трехчленным, вводя в рассмотрение . Сопоставляя тогда уравнение (1. 2) при и уравнения (1. 3) при , видим, что

(1. 6)

Соотношениями (1. 2) - (1. 6) метод прогонки определяется полностью. Рекуррентные соотношения (1. 3) - (1. 6) называют прямой прогонкой. и рекуррентные соотношения (1. 2) - (1. 6) - обратной прогонкой.

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

В случае решения СЛАУ с ленточными матрицами система уравнений (1. 1) имеет векторный вид

(1. 7)

где Равенства (покомпонентные) (1. 2) можно записать в виде

(1. 8)

где , а верхняя двухдиагональная матрица связана коэффициентами :

Кроме того, соотношения (2. 4) также представимы в векторной форме:

(1. 9)

где

есть нижняя двух диагональная матрица. Сравнение равенств (1. 7) и (1. 8), (1.9) при произвольном приводит (для невырожденной матрицы ) к треугольному разложению матрицы :

(1. 10)

Из этого следует, что прогонка является реализацией (для трехдиагональных систем уравнений) метода исключения Гаусса, который и основан на разложении матрицы на треугольные множители.

Реализация метода

Постановка задачи: рассмотрим систему из линейных алгебраических уравнений вида (1.1). В матричном виде система может быть представлена, как

и есть вещественная матрица размера ; и - вектора из элементов.

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

Предположим, что выполнено

(1. 12)

Подставим (1. 12) в -е уравнение системы, получим

(1. 13)

Сравнивая (1. 13) и выражение получим

(1. 14)

Из первого уравнения находим

Затем вычисляем используя (1. 14) при .

Определим из последнего уравнения

Используя находим все

Для реализации алгоритма метода прогонки следует создать модуль с процедурой, параметрами которой должны являться порядок системы, массивы коэффициентов P, Q. Результатом должен быть массив решения Y в точках основной сетки.

Метод прогонки состоит в вычислении прогоночных коэффициентов. Каждое неизвестное выражается через с помощью прогоночных коэффициентов , заданными формулами метода.

1.1.2 Метод «встречной прогонки»

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

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

во втором потоке - вычисляются коэффициенты , при .

При проводится сопряжение решений в форме:

находим значение из системы

В первом потоке находим при , а во втором все при .

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

С помощью встречной прогонки мы сокращаем объем работы в двое, высчитывая прогоночные коэффициенты до . И в это же время начитаем проводить те же вычисления в обратном порядке, начиная с . Прогоночные коэффициенты обратной прогонки обозначим как .

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

Для распараллеливания программы не достаточно модифицировать ее код, необходимо распределить «роли» на процессоры. Метод встречной прогонки возможно распараллелить только на 2 процессора, что уже победа, ведь метод прямой прогонки в чистом виде совершенно непригоден для распараллеливания.

Для удобного анализа результатов программы исходные данные вводятся в файл под названием «in», а результаты получаем в файле «out».

1.2 Метод циклической редукции

1.2.1 Описание

Рассмотрим еще один подход к решению трехдиагональных систем, которые мы теперь будем записывать в виде

(2.1)

Умножим первое уравнение системы (2.1) на и вычтем его из второго, чтобы аннулировать коэффициент при во втором уравнении; это обычный шаг гауссова исключения. Но затем мы умножаем третье уравнение на и также вычитаем его из второго, чтобы исключить коэффициент при во втором уравнении. Так получается новое второе уравнение

Проделаем то же самое с уравнениями 3, 4 и 5: вычтем из уравнения 4 надлежащие кратные уравнений 3 и 5, чтобы получить новое уравнение

Система (2.2) - это трехдиагональная система относительно переменных , и описанный только что процесс можно повторить. В результате получится новая система, в которую входят лишь переменные Будем продолжать действовать указанным образом, пока дальнейшая редукция не станет невозможной. В частности, при редукция закончится единственным финальным уравнением. Решив его, начнем обратную подстановку. Она схематически иллюстрируется для рисунком 2, который представляет собой продолжение рис. 1. Три уравнения на рис. 2 получены после первого шага редукции, показанного на рис. 1; они комбинируются, порождая финальное уравнение относительно единственного неизвестного

Решив его, мы можем затем решить относительно и первое и последнее уравнения редуцированной системы. После этого и можно определить из первого и последнего уравнений исходной системы. Наконец, и можно найти из третьего и пятого исходных уравнений.

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

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

1.2.2 Параллельная реализация

Хотя в те времена, когда он был изобретен, параллельные вычисления вовсе не имелись в виду, этот процесс обладает немалым параллелизмом. Заметим, прежде всего, что операции, ведущие к новым уравнениям для , независимы и могут выполняться одновременно. Предположим, что имеются процессоров и применяется схема хранения, показанная на рис. 3.

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

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

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

Каждая следующая итерация прямого и обратного хода зависит от предыдущей. Распараллеливание по уровням проводить нельзя.

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

1.3 Решение СЛАУ с 5 ти-диагональной матрицей

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

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

Если при решении использовать метод Гаусса, то расчет можно организовать таким образом, чтобы не включать нулевые элементы матрицы. Этим самым экономится требуемая память и уменьшается объем вычислений.

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

(3.1)

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

Для решения системы (3.1) метод исключения Гаусса. Учитывая структуру системы (3.1), легко получим, что обратный ход метода Гаусса должен осуществляться по формулам

(3.2)

Для реализации (3.2) необходимо задать , а также определить коэффициенты используя первое уравнение (3.2), выразим и . Получим

(3.3)

для

Подставляя (3.3) в третье уравнение (3.1), получим

при

Сравнивая это выражение с первым уравнением (3.2), видим, что если положить

(3.4)

где обозначено , то уравнения системы (3.1) для будут удовлетворены.

Рекуррентные соотношения (3.4) связывают и с и . Поэтому, если будут заданы и для , то по формулам (3.4) последовательно можно найти коэффициенты и для

Найдем и для . Из первого уравнения (3.1) и (3.2) для непосредственно получим

(3.5)

Далее подставляя значение (3.3) при во вторую строчку (3.1), получим

(3.6)

Следовательно, второе уравнение (2.3.1) будет выполнено, если положить

(3.7)

Итак, используя (3.4) - (3.7) можно найти и для Осталось определить и , входящие в формулу (3.2).

Воспользуемся для этого четвертым и пятым уравнениями (3.1). Подставляя (3.3) при в четвертое уравнение, найдем, что и определяются по формулам (3.4) для . Найдем теперь . Для этого подставим или где определяется по формуле (3.4) при .

Объединяя полученные выше формулы, запишем алгоритм правой прогонки для системы (3.1) в следующем виде:

где

находятся прогоночные коэффициенты и ;

неизвестные находятся последовательно по формулам

Алгоритм построен.

1.3.2 Модификация, позволяющая эффективное решение системы

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

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

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

2. Результаты численного эксперимента

Для того, что бы ответить на поставленные в начале работы вопросы, численные эксперименты будут проводиться на трех ПК с разными техническими характеристиками.

ПК1

- процессор: Pentium 4 1,7 GHz

- оперативная память: 1,00 Гб

ПК2

- процессор: Pentium Duai-Core CPU 2,10 GHz 2,10 GHz

- оперативная память: 4,00 Гб (доступно 2,97 Гб)

ПК3

- процессор: Intel Core i5-3210M CPU 2,5 GHz 2,5 GHz

- оперативная память: 4,00 Гб

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

Сравним результаты тестирования при изменении размерности матрицы от 30000 до 3800000.

Как и ожидалось, ПК с самыми слабыми характеристиками потратил наибольшее количество времени на решение СЛАУ. Так как ПК1 может работать только с одним потоком, разница между простой встречной прогонкой и распараллеленной несущественна (1,3%). Но по отношению с методом прямой прогонки встречная сокращает время решения задачи на 31%.

Результаты тестирования на ПК 2 показывают, что метод встречной прогонки улучшает показатели на 29%, а при распределении по потокам на 44%.

ПК 3 улучшил результаты своего предшественника еще на 10%, но разница между временем решения СЛАУ простой встречной прогонкой и распараллеленной осталось пропорциональна друг другу.

Заключение

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

В работе реализованы методы решения СЛАУ с трех- и пятидиагональными матрицами. Как оказалось, прямой метод прогонки неудобен для распараллеливания. Представленные модификации алгоритма - встречная прогонка, сами по себе дают хорошие результаты. Разделив процессы с учетом возможностей нескольких процессоров, мы увидели значительное сокращение времени работы программы.

Проведя численные эксперименты на ПК с разными техническими возможностями, мы убедились, что увеличение количества процессоров действительно приводит к сокращению времени счета, но более чем в раз, а при модификации алгоритма и распараллеливании на программном уровне значительно больше (среднее время решения СЛАУ в Приложении 7).

Кол-во раз сокращения времени при переходе от однопроцессорной конфигурации к 2х-процессорной

Метод прямой прогонки (3)

Метод встречной прогонки (3)

Метод встречной прогонки (3) (распарал)

Метод решения СЛАУ (5)

Метод решения СЛАУ (5) (распарал)

2,79514081

2,57557252

3,38900204

2,807692308

3,391304348

Кол-во раз сокращения времени при переходе от однопроцессорной конфигурации к 4х-процессорной

Метод прямой прогонки (3)

Метод встречной прогонки (3)

Метод встречной прогонки (3) (распарал)

Метод решения СЛАУ (5)

Метод решения СЛАУ (5) (распарал)

5,32842105

5,1121212

8,246485261

5,32842105

7,903703704

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

Получив результаты численных экспериментов, стало абсолютно ясно, что параллельные методы решения СЛАУ с ленточными матрицами очень эффективны. Их развитие и применение, безусловно, поднимет на новый уровень нашу науку и различные отрасли промышленности.

Список источников

уравнение матрица ленточный параллельный

1. В.П. Ильин, Ю.И. Кузнецов Трехдиагональные матрицы и их приложения. Москва: Наука 1985 - с. 50-51, 62-64.

2. Харви Дейтел, Пол Дейтел Как программировать на С. Санкт-Петербург: СГТУ 2004 - с. 87 - 419.

3. Баркалов К.А. Параллельные численные методы. Метод прогонки. М.: Мир1975 - с. 56-63, 134-137.

4. Материалы учебного курса «Параллельные численные методы» от Intel http://software.intel.com/ru-ru/articles/courseware_parallel_computation_numerical_methods

5. Белов С.А., Золотых Н.Ю. Численные методы линейной алгебры Н. Новгород, ННГУ 2005 - с. 97-101.

6. Акимова Е.Н. Параллельный алгоритм решения систем уравнений с пятидиагональными матрицами и исследование его устойчивости // Вестник ННГУ. 2009. №2. с. 135-140.

7. Дж. Ортега Введение в параллельные и векторные методы решения линейных систем. Москва: Мир 1991 - с. 151 -154.

8. А.А. Самарский Методы решения сеточных уравнений. Москва: Наука. 1978 - с. 97 - 99.

9. Есаулов А.О., Старченко А.В. Параллельная реализация явного метода Н.И. Булеева http://old.lvk.cs.msu.su/files/mco2005/esaulov.pdf с. 4-7.

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


Подобные документы

  • Понятие и специфические черты системы линейных алгебраических уравнений. Механизм и этапы решения системы линейных алгебраических уравнений. Сущность метода исключения Гаусса, примеры решения СЛАУ данным методом. Преимущества и недостатки метода Гаусса.

    контрольная работа [397,2 K], добавлен 13.12.2010

  • Методы решения систем линейных алгебраических уравнений (СЛАУ): Гаусса и Холецкого, их применение к конкретной задаче. Код программы решения перечисленных методов на языке программирования Borland C++ Builder 6. Понятие точного метода решения СЛАУ.

    реферат [58,5 K], добавлен 24.11.2009

  • Понятие матрицы. Метод Гаусса. Виды матриц. Метод Крамера решения линейных систем. Действия над матрицами: сложение, умножение. Решение систем линейных уравнений методом Гаусса. Элементарные пребразования систем. Математические перобразования.

    лекция [45,4 K], добавлен 02.06.2008

  • Основные действия над матрицами, операция их умножения. Элементарные преобразования матрицы, матричный метод решения систем линейных уравнений. Элементарные преобразования систем, методы решения произвольных систем линейных уравнений, свойства матриц.

    реферат [111,8 K], добавлен 09.06.2011

  • Характеристика способов решения систем линейных алгебраических уравнений (СЛАУ). Описание проведения вычислений на компьютере методом Гаусса, методом квадратного корня, LU–методом. Реализация метода вращений средствами системы программирования Delphi.

    курсовая работа [118,4 K], добавлен 04.05.2014

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

    лабораторная работа [489,3 K], добавлен 28.10.2014

  • Метод главных элементов, расширенная матрица, состоящая из коэффициентов системы и свободных членов. Метод квадратных корней для решения систем с симметричной матрицей коэффициентов. Практическая реализация метода Халецкого: программа на языке Pascal.

    контрольная работа [761,7 K], добавлен 22.08.2010

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

    реферат [66,4 K], добавлен 14.08.2009

  • Основные понятия и теоремы систем линейных уравнений, характеристика методов их решения. Критерий совместности общей системы. Структура общих решений однородной и неоднородной систем. Матричный метод решения и обобщение. Методы Крамера и Гаусса.

    курсовая работа [154,5 K], добавлен 13.11.2012

  • Сущность итерационного метода решения задачи, оценка его главных преимуществ и недостатков. Разновидности итерационных методов решения систем линейных алгебраических уравнений: Якоби, Хорецкого и верхней релаксации, их отличия и возможности применения.

    курсовая работа [39,2 K], добавлен 01.12.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.