Что такое метод прогонки

Линейные уравнения. Решение систем линейных уравнений. Метод прогонки.

Метод прогонки (алгоритм Томаса) используют для решения СЛУ типа Ax=F, где A — трёхдиагональная матрица. Это вариант метода последовательного исключения неизвестных.

Система уравнений Ax=F равноценна соотношению:

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

Выразим x_i-1 и x_i через x_i+1, подставим в уравнение, используя это соотношение, (1):

где F_i — правая часть i-го уравнения.

Это соотношение выполняется не завися от решения, если потребовать:

,

,

Получаем из 1-го уравнения:

.

После того, как нашли прогоночные коэффициенты α и β, используем уравнение (2) и получим решение системы. Причем,

.

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

c надиагональной (наддиагональной) матрицей:

Рассчеты проводим в 2 этапа. На 1-ом этапе вычисляем компоненты матрицы C′_i и вектора F′, начиная с i=2 до i=n:

На 2-ом этапе, для i=n,n−1,…,1 вычисляем решение:

Для применимости формул метода прогонки достаточно свойства строгого диагонального преобладания у матрицы A.

Источник

«Метод прогонки»

Содержимое разработки

Государственное бюджетное профессиональное образовательное учреждение

Московской области «Подольский колледж имени А.В. Никулина»

по дисциплине «ЕН Математика»

по теме: «Метод прогонки»

для студентов II курса

15.02.15 Технология металлообрабатывающего производства

Преподаватель первой квалификационной категории

Носова Оксана Васильевна

Специальность: 15.02.15 Технология металлообрабатывающего производства

Дисциплина: ЕН Математика

Тема: Метод прогонки.

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

формирование представлений о системах линейных уравнений с трехдиагональной структурой и методе прогонки,

формирование умений применять знания при решении задач;

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

способствовать развитию логического мышления;

способствовать развитию вычислительных навыков при решении задач по специальности;

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

Тип урока: урок теоретического обучения

1) словесные (лекция);

2) наглядные (мультимедийная презентация, опорный конспект);

3) практические (решение задач).

-Решение систем линейных уравнений

Приветствие. Раздача опорных конспектов

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

Почему? (ответы обучющихся)

Верно. Так, например, если в системе 10 уравнений, то сколько требуется вычислить определителей? (ответы обучющихся)

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

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

И немного из истории решения СЛАУ нам расскажет _______________________(ФИ).

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

(сообщение студента) (3 – 4) мин

Итак, для каких же матриц применим метод прогонки.

Верно, для трехдиагональных мартиц.

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

(1)

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

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

( )

( )

( )

и этапа обратной прогонки, основанного на использовании прогоночных коэффициентов для нахождения неизвестных, начиная с n-го неизвестного

, а затем

,

,…,

.

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

.

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

-Решение систем линейных уравнений

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

Решение. Запишем коэффициенты в матричном виде

Для удобства выпишем матрицы

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

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

Проверка найденных решений (подставить в уравнения системы)

Подведем итог нашего занятия.

Перед вами матрица. Кстати, какая это матрица? (ответы обучающихся)

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

3 – Сегодня на уроке я научился…

1 – Мне было сложно (не сложно) …

2 – Трехдиагональной матрицей называется…

-1 – В чем заключается метод прогонки?

5 – Материал урока мне был … (понятен/непонятен, интересен/ неинтересен).

Домашнее задание. Решить систему методом Крамера и методом прогонки.

Матрица с трехдиагональной структурой:

(1)

Соответствующая ей система линейных алгебраических уравнений:

Алгоритм метода прогонки:

1.Прямая прогонка (вычисление прогоночных коэффициентов)

( )

( )

( )

2.Обратная прогонка (нахождение неизвестных)

,

,

,…,

.

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

Решение. Запишем коэффициенты в матричном виде

Источник

Метод прогонки

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

Запишем систему уравнений в виде

(2.13)

Метод прогонки состоит из двух этапов – прямой прогонки (аналога прямого хода метода Гаусса) и обратной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в вычислении прогоночных коэффициентов Ai,Bi,с помощью которых каждое неизвестное xi выражается через zi+1:

(2.14)

Из первого уравнения системы (2.13) найдем

С другой стороны, по формуле (2.14) Приравнивая коэффициенты в обоих выражениях для х1, получаем

(2.15)

Подставим во второе уравнение системы (2.13) вместо х1его выражение через х2по формуле (2.14):

Выразим отсюда х2 через х3:

Аналогично вычисляют прогоночные коэффициенты для любого номера i:

(2.16)

Обратная прогонка состоит в последовательном вычислении неизвестных xi. Сначала нужно найти хп. Для этого воспользуемся выражением (2.14) при i = п –1 и последним уравнением системы (2.13). Запишем их:

Отсюда, исключая хn-1, находим

Далее, используя формулы (2.14) и вычисленные ранее по формулам (2.15), (2.16) прогоночные коэффициенты, последовательно вычисляем все неизвестные хn—1, xn-2. ,х1. Алгоритм решения системы линейных уравнений вида (2.13) методом прогонки приведен на рис. 2.4.

Рис. 2.4. Алгоритм метода прогонки

При анализе алгоритма метода прогонки надо учитывать возможность деления на нуль в формулах (2.15), (2.16). Можно показать, что при выполнении условия преобладания диагональных элементов, т.е. если , причем хотя бы для одного значения iимеет место строгое неравенство, деления на нуль не возникает, и система (2.13) имеет единственное решение.

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

Источник

Умножение разреженных матриц

Параллельный вариант метода прогонки

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

( 7.29)

с использованием p параллельных потоков.

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

В пределах полосы матрицы, обрабатываемой k-м потоком, можно организовать исключение поддиагональных элементов матрицы (прямой ход метода). Для этого осуществляется вычитание строки i, умноженной на константу , из строки i+1 с тем, чтобы результирующий коэффициент при неизвестной xi в (i+1)-й строке оказался нулевым.

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

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

( 7.30)

Затем выполняется обратный ход алгоритма – каждый поток исключает наддиагональные элементы, начиная с последнего.

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

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

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

( 7.31)

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

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

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

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

Затем следует произвести сборку вспомогательной трехдиагональной системы уравнений в одном потоке, и осуществить ее решение методом прогонки. В соответствии с оценкой (7.26) затраты на выполнение этого чисто последовательного этапа составят порядка 10p операций.

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

( 7.32)

Как результат выполненного анализа, показатели ускорения и эффективности параллельного варианта метода прогонки могут быть определены при помощи соотношений следующего вида:

( 7.33)

Из приведенных соотношений видно, что в случае решения системы уравнений с большим числом неизвестных, при котором , показатели ускорения и эффективности будут определяться как

( 7.34)

Результаты вычислительных экспериментов

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

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

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

Далее рассмотрим эффект, который дает использование встречной прогонки в двух потоках: проведем сравнение параллельной встречной прогонки с правой и левой прогонками. Результаты, отражающие зависимость ускорения по отношению к правой и левой прогонкам от размера задачи N приведены на рис. 7.10.

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

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

Таблица 7.9. Результаты экспериментов (параллельная прогонка)

n, тыс.	1 поток	Параллельный алгоритм
		2 потока		4 потока		6 потоков		8 потоков
		T	S	T	S	T	S	T	S
1680	0,06	0,07	0,94	0,03	2,03	0,03	2,10	0,03	2,03
5040	0,20	0,20	1,00	0,11	1,83	0,09	2,29	0,09	2,14
8400	0,32	0,32	0,99	0,17	1,85	0,15	2,18	0,14	2,26
11760	0,45	0,45	0,98	0,23	1,91	0,20	2,25	0,20	2,20
15120	0,57	0,59	0,97	0,31	1,84	0,26	2,18	0,27	2,16
18480	0,72	0,76	0,95	0,41	1,78	0,32	2,25	0,31	2,31
21840	0,83	0,84	0,99	0,45	1,84	0,38	2,20	0,37	2,22
25200	0,96	0,97	0,99	0,53	1,80	0,43	2,25	0,44	2,19

На рис. 7.12 приведен график зависимости ускорения от числа потоков при использовании модификации алгоритма из п. 1.2.2. Видно, что при p Таблица 7.10. Время решения серии задач с использованием методов прогонки и редукции

NВремя работы метода прогонки (сек)Время работы метода редукции (сек)2560,2020,0315120,4050,07810240,7950,1420480,530,26540961,0450,51481922,0741,092163844,2272,169327688,474,3996553619,119,111

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

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

Таблица 7.11. Результаты решения серии задач параллельным методом редукции

N	1 поток	Параллельный алгоритм
		2 потока		4 потока		6 потоков
	T	T	S	T	S	T	S
2048	0,31	0,31	1,00	0,52	0,61	0,66	0,48
4096	0,59	0,51	1,15	0,78	0,76	0,83	0,72
8192	1,14	0,91	1,26	1,01	1,12	1,09	1,04
16384	2,22	1,47	1,51	1,47	1,51	1,55	1,43
32768	4,46	3,12	1,43	2,51	1,78	2,47	1,81
65536	9,19	5,55	1,65	4,38	2,10	3,96	2,32

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

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

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

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

Источник