Разработка коллокационных схем параллельного управления шагом в эволюционных уравнениях

УДК 004.272.2:519.63 DOI: 10.20998/2411-0558.2018.24.03

О. А. ДМИТРИЕВА, д-р техн. наук, проф., зав. каф. ДонНТУ,

Покровск,

Н. Г. ГУСЬКОВА, асп. ДонНТУ, Покровск, Высшая техническая

школа университета прикладных наук, Бинген, Германия

РАЗРАБОТКА КОЛЛОКАЦИОННЫХ СХЕМ ПАРАЛЛЕЛЬНОГО УПРАВЛЕНИЯ ШАГОМ В

ЭВОЛЮЦИОННЫХ УРАВНЕНИЯХ

Работа посвящена вопросам параллельного управления шагом интегрирования по переменной времени при сведении эволюционных уравнений методом прямых к задаче Коши. Численная реализация осуществляется коллокационными блочными разностными схемами с изменяемыми размерностями опорных и расчетных блоков. Программное формирование расчетных формул позволяет отслеживать динамику вычислительного процесса и автоматически переходить на схемы растяжения - сжатия шага. Приведенные теоретические положения подкреплены экспериментальными исследованиями на тестовых задачах. Ил.: 9. Библиогр.: 13 назв.

Ключевые слова: управление шагом; эволюционные уравнения; метод прямых; коллокационные блочные разностные схемы; изменяемые размерности.

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

Анализ литературы. Известно, что с помощью метода прямых [1, 2], который обеспечивает дискретизацию по пространственным переменным, можно свести исходное эволюционное уравнение с частными производными к задаче Коши

© О. А. Дмитриева, Н.Г. Гуськова, 2018

и' = и

Однако после сведения уравнения с частными производными к задаче Коши для СОДУ возникают проблемы, которые для исходной задачи не были характерными. Так, если рассматриваются явные шаблоны реализации, то выбор шага интегрирования по времени определяется выполнением условия Куранта [3] и напрямую зависит от величины шага по пространственной переменной. Для случая неявных разностных схем шаг по времени регламентируется физической природой решаемой задачи и порядками аппроксимации разностной схемы (схем) [4]. Когда речь идет о численном решении сформированной системы ОДУ, возникают дополнительные возможности, связанные с аппроксимацией более высокого порядка (р-уточнение), локальным контролем ошибок и автоматическим изменением шага интегрирования (т-уточнение) [5, 6]. Существенное влияние на погрешность получаемого решения будут оказывать также вопросы, связанные с изменением шага по пространственной переменной (Л-уточнение) [7]. Однако в этом случае простое уменьшение пространственного шага на некоторый коэффициент у приводит к увеличению размерности формируемой СОДУ на этот же коэффициент [8], что значительно усложняет решение. Поэтому в этой статье будут рассматриваться вопросы, связанные только с т-уточнением, что особенно актуально при численном решении жестких дифференциальных уравнений [8, 9]. При этом актуальными являются вопросы соотнесения погрешностей результатов и времени, затрачиваемого на получение решения. Для управления шагом в работе предлагается использовать коллокационные блочные методы [9, 10] и методы типа Биккарта [4, 11], которые позволяют обеспечивать параллельное управление шагом интегрирования для целого блока точек.

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

Разработка коллокационных схем для управления шагом.

Рассмотренный в [9, 10] подход, связанный с контролем локальной погрешности на основе сопоставления решений, полученных с разными порядками в совпадающих точках блока, оказывается очень результативным при решении нежестких уравнений и систем и может быть использован для оценки погрешности полученного решения. Но, к сожалению, такой подход не может обеспечивать изменение шага интегрирования во время счета. Этот вопрос становится наиболее

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

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

а также два множества точек, которые будут формировать расчетные блоки:

При этом проще всего связать шаги интегрирования тп^ и тп

соотношениями тп^ =2тп2 . Тогда между размерностями расчетных

блоков должно будет выполняться соотношение = 2^2 . Счет, как и для случаев, описанных в [9], будет выполняться параллельно для двух расчетных схем с одинаковыми размерностями опорных блоков и с различающимися в / раз размерностями расчетных блоков. Канонический вид многошаговых коллокационных методов с числом опорных точек т и числом расчетных точек ¿1 и ¿2 соответственно, будет иметь вид:

1п,1 = По + тп фп-т+Ь По \, 1 = -(т -1) >-(т - 2) >...Д

п,1

1 . = tn,0 + тп2 е ^п,> 1 = 1,2,...3¿2.

п 1 ' ^ ' ' ^ -

где u

n,i n,i n ,i n,i

соответственно,

tn>ТщТП2- шаги интегрирования в опорном блоке, в блоках размерностью si и S2,

Fn,j = tn + jtn,un,j) - правые части уравнения (1) в точках, j = (m - 1), - (m - 2), ..., 0,

Fi!j = j(tn + jtn1,un, j), j = 1,2,•••,s1, Fn,j = j(tn + jtn2 , un, j ), j = 1,2,•••, s2,

a(1), ¿(1), 2), 2) - коэффициенты расчетных схем (2).

i,j i,j i,j i,j

Рис. 1. Схема закрепления опорных, расчетных и промежуточных точек

Для разграничения рассчитанных и искомых точек можно ввести соответствующие обозначения и представить их в виде векторов:

ип = {ип,у}, п = 1,2,..., у = -(т-1),-(т-2),...,0 - вектор

посчитанных точек,

ип+1 = {ип,у}, п = 1,2,..., у = 1,2,...,Sl - вектор искомых точек для

блока ¿1,

Уп+1 = {ип,у}, п = 1,2,..., у = 1,2,...,¿2 - вектор искомых точек для блока ¿2,

у = Ц'п + утп,ип,у ), п = 1,2,..., у = -(т -1),-(т - 2)-.,0,

¥п+1,у = 9 ('п + , ип,у ), п = 1,2,..., у = 1,2,..., ¿Ь

^п+1,] = V (1п + Тп2, ип,] ), п = 1,2,..., ] = 1,2,..., ¿2 - соответственно, вектора правых частей уравнения (1) в известных и искомых точках,

№. в«, а( 2) , В ' - матрицы коэффициентов разностных схем, 11п о = [нп о)е ~ решение в точке 0 . е - единичный вектор размерности

Тогда в векторной форме система уравнений (2) будет иметь вид:

ип+1 = ип,0 +тпв

Уп +1 = ип,0 + тпВ((¥п +Тп2 А( 2)^п+1.

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

коэффициентов и формирования матриц А» , В ' с размерностями ¿1 х т

и ¿1 х ¿1, А(2), В(2) с размерностями ¿2 х т и ¿2 х ¿2 вычисления многошаговым блочным методом, представленным в виде систем нелинейных уравнений (3), можно свести к следующим итерационным процессам:

ип+1 = ип^е +ТпВ

и(п^Чи^е + ТпВ(1)^п) + Тп1 А(1)), п = 1,2,..., г = 1,2,...,¿1,

1

= ип,0е + ТпВ( 2) Ъ

^п(^+1)=(ип,0е +ТпВ(2)Ъп) + Тп2 А(2^ п = 1,2,..., г = 1,2,...,¿2.

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

значений ^+1, ^(+)1 в расчетных блоках осуществляется на основе

многошагового предикторного метода Адамса [3], что позволяет повысить точность начального приближения. Вычисление приближенных

значений ^+1 , ^+1 решения задачи Коши в каждом следующем

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

Численная реализация метода прямых с управлением шагом по переменной времени (т -уточнение). Эксперименты по управлению шагом интегрирования по переменной времени (т -уточнение) проводились для разных значений шага дискретизации по пространству, исходя из величины которого (Л-уточнение) определялось число уравнений n в системе ОДУ (n = 10, n = 20, n = 40). Для тестовых задач с известным точным решением точные значения использовались для формирования значений в m начальных точках. Для случаев, когда точное решение отсутствовало, требуемые множества начальных значений определялись одношаговым методом с сопоставимой точностью. В качестве начальных приближений Fn i, Fn 2,...,Fn s для

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

В качестве одного из примеров рассматривалась эволюционная тестовая задача [12]

2

du 2 д u г г^ ^ч

— = а2^, t e[ío,T], х е[0,1]

dt дх

с известным точным решением, с граничными условиями u (0, t ) = u (i, t ) = 0, в начальном условии которого содержится параметр жесткости к

u

Как показано в [12], методы без управления шагом даже для невысоких значений параметра к не могут обеспечить заявленную точность вычисления. На рис. 2 - 5 приведены графики изменения шага по переменной времени и графики накопленных погрешностей, полученные с помощью разностных схем (4) с размерностями блоков 2 х 2 и 2 х 4. Динамика изменения шага также исследовалась в зависимости от шага дискретизации по пространству, параметра

жесткости к, который принимал значения в интервале 1 ^ 10, и от величины заданной глобальной погрешности е.

Еще один класс тестов выполнялся для параболического уравнения с известным точным решением, описанного в [13]. Рассматривается однородное уравнение теплопроводности (5) со значениями параметров Ь = 1, Т = 1, а = 1 с начальным условием

и

граничными условиями второго рода

ди

Step 0.008

Рис. 2. Автоматическое изменение шага интегрирования для задачи (5-6) в

методе прямых, п = 10, к = 2,е = 10 6

Рис. 3. Графики глобальной погрешности численного решения задачи (5-6) в методе прямых,

п = 10, к = 2,е = 10-6

Step 0.008

0.006

0.004

0.002

Г

5.ХЮ"8

100 200 300 400 500

Рис. 4. - Автоматическое изменение шага интегрирования для задачи (5-6) в методе прямых,

-б.х10"8

-1.ХЮ"7

Рис. 5. Графики глобальной погрешности численного решения задачи (5-6) в методе прямых,

n = 10, к = 10, е = 10

-6

n = 10, к = 10,е = 10

-6

Шаг дискретизации по пространству определялся размерностью системы обыкновенных дифференциальных уравнений п = 10, 20, И =Ып.

Величина глобальной погрешности е задавалась на уровне е = Метод прямых реализовывался с помощью разностных схем (4) с размерностями опорного и расчетных блоков 2 х 2 (2 х 4) и 3 х 3 (3 х 6). Результаты численного моделирования приведены в виде диаграмм изменения шага (рис. 6, 8) и графиков распределения глобальной погрешности численного решения (рис. 7, 9).

Step 0.008

0.006 0.004 0.002

I I I I I I I I

200 400 600 800

Рис. 6. Автоматическое изменение шага интегрирования для задачи (5,78) в методе прямых, п = 10, е = 10 6

Error

2.К10-7

1.Х10-7

-1.Х10-7 0.2 0.4 0.6 0.8

-2.Х10-7

Рис. 7. Графики глобальной погрешности численного решения задачи (5,7-8) в методе прямых,

п = 10, е = 10-6

Step 0.0020

0.0015

0.0010

0.0005

200 400 600 800 1000 1

Рис. 8. Автоматическое изменение шага интегрирования для задачи (5,7-

8) в методе прямых, п = 10, е = 10 9

Рис. 9. Графики глобальной погрешности численного решения задачи (5,7-8) в методе прямых,

n = 10,£ = 10

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

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

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

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

Список литературы:

1. Schiesser W. Method of Lines Analysis of Turing Models / W. Schiesser. - 2017. -Published. - 268 р.

2. Shakeri F. The method of lines for solution of the one-dimensional wave equation subject to an integral conservation condition / F. Shakeri, M. Dehghan // Journal Computers & Math. with Appl. - 2008. - Vol. 56. - № 9. - P. 2175-2188.

3. Фельдман Л.П. Чисельш методи в шформатищ / Л.П. Фельдман, А.1. Петренко,

0.А. Дмитрieва. - К.: Видавнича група BHV, 2006. - 480 с.

4. Bickart T.A. An efficient solution process for implicit Runge-Kutta methods / T.A. Bickart // SIAM Journal Numerical Analysis. - 1977. - Vol. 14. - № 8. - P. 1022-1027.

5. Atkinson K. Numerical solution of ordinary differential equations // K. Atkinson, W. Han, D. Stewart. - Wiley-Interscience, John Wiley & Sons, 2009. - 252 р.

6. Hairer E. Solving Ordinary Differential Equations / E. Hairer, G. Wanner// Second revised edition. - Springer-Verlag. - 2010. - 586 р.

7. Butcher J. Numerical Methods for Ordinary Differential Equations / J. Butcher. - John Wiley & Sons, 2016. - 538 р.

8. Dmytriyeva О. Introduction of an irregular grid with respect to the spatial coordinate for the method of lines / O. Dmytriyeva, N. Huskova // Advanced Information Systems and Technologies: proceedings of the VI international scientific conference, Sumy, May 16-18 2018 / Edited by S. I. Protsenko, V. V. Shendryk - Sumy: Sumy State University, 2018 - Р. 30-33.

9. Дмитрieва О.А. Паралельне моделювання динашчних об'екпв зi сконцентрованими параметрами / О.А. Дмитрieва. - Харшв: "Ноулщж", 2014. - 335 с.

10. Дмитриева О.А Управление шагом интегрирования при параллельной реализации коллокационных методов / О.А. Дмитриева // Радиоэлектронные и компьютерные системы. - 2014. - № 5 (69). - С. 119-123.

11. Дмитриева О.А. Разработка и обоснование параллельных одношаговых блочных методов типа Биккарта / О.А. Дмитриева // Системы обработки информации. - 2014. -№ 7 (123). - С. 121-126.

12. Cash J. New finite difference schemes for parabolic equations / Cash J. // Society for Industrial and Applied Mathematics J. - 1984. - Vol. 21. - № 3. - P. 433-446.

13. Schiesser W. Differential Equation Analysis in Biomedical Science and Engineering / W. Schiesser. - John Wiley & Sons, 2014. - 440 p.

References:

1. Schiesser, W. (2017), "Method of Lines Analysis of Turing Models", Published, 268 р.

2. Shaken, F. and Dehghan, M. (2008), "The method of lines for solution of the one-dimensional wave equation subject to an integral conservation condition", J. Computers & Math. with Appl., Vol. 56, № 9, pp. 2175-2188.

3. Feldman, L., Petrenko, A. and Dmytriyeva, O. (2006), "Numerical methods in computer science", Publishing group BHV, Kiev, 480 p.

4. Bickart, Т. (1977), "An efficient solution process for implicit Runge-Kutta methods", SIAM Journal Numerical Analysis, Vol. 14, № 8, pp. 1022-1027.

5. Atkinson, K., Han, W. and Stewart, D. (2009), "Numerical solution of ordinary differential equations", Wiley-Interscience, John Wiley & Sons, 252 р.

6. Hairer, E. and Wanner, G. (2010), "Solving Ordinary Differential Equations", SpringerVerlag, 586 р.

7. Butcher, J. (2016), "Numerical Methods for Ordinary Differential Equations", John Wiley & Sons, 538 р.

8. Dmytriyeva, O. and Huskova, N. (2018), "Introduction of an irregular grid with respect to the spatial coordinate for the method of lines", Advanced Information Systems and Technologies: proceedings of the VI international scientific conference, May 16-18, 2018, Sumy, pp. 30-33.

9. Dmytriyeva, O. (2014), "The parallel simulation of dynamic objects with concentrated parameters", Noulidzh, Kharkiv, 335 p.

10. Dmytriyeva, O. (2014), "Control of integration step for parallel realization of collocation block methods", J. Radio-electronic and computer systems, Vol. 69, No. 5, pp. 119-123.

11. Dmitrieva, O.A. (2014), "Development and support of parallel one-step block methods such of Bickart", Information processing systems, Vol. 7, No. 123, pp. 121-126.

12. Cash, J. (1984), "New finite difference schemes for parabolic equations", Society for Industrial and Applied Mathematics J., Vol. 21, No. 3, pp. 433-446.

13. Schiesser, W. (2014), "Differential Equation Analysis in Biomedical Science and Engineering", John Wiley & Sons, 440 p.

Статью представил д-р техн. наук, проф. ДонНТУБашков Е.А.

Поступила (received) 05.05.2018

Dmytriyeva Olga, Dr.Sci.Tech, Professor

Donetsk National Technical University

Pl. Shibankova, 2, Pokrovsk, Ukraine, 85301

Tel.: +38 (050) 998-11-75, e-mail: olha.dmytriieva@donntu.edu.ua

ORCID ID: 0000-0001-8921-8433

Huskova Nadiia, PhD student

Donetsk National Technical University,

Higher Technical School of the University of Applied Sciences,

Berlinstraße, Bingen, Germany 109, 55411,

Tel.:+49 (6721) 4090, e-mail: huskovanadiia@gmail.com

ORCID ID: 0000-0002-5901-4189

УДК 004.272.2:519.63

Розробка колокацшних схем паралельного управлшня кроком в еволюцшних ршмямиях / Дмитрieва О.А., Гуськова Н.Г. // Вiсник НТУ "ХП1". Серш: 1нформатика та моделювання. - Харшв: НТУ "ХП1". - 2018. - № 24 (1300). - С. 25 - 36.

Робота присвячена питаниям паралельного управлшня кроком штегрування за змшною часу при зведенш еволюцшних рiвнянь методом прямих до задачi Кошi. Чисельна реалiзацiя здшснюеться колокацiйними блоковими рiзницевими схемами i3 змiнними розмiрностями опорних i розрахункових блоков. Програмне формування розрахункових формул дозволяе вiдстежувати динамiку обчислювального процесу i автоматично переходити на схеми розтягування - стиснення кроку. Теоретичш положення, що наводяться, пiдкрiпленi експериментальними дослщженнями на тестових завданнях. 1л.: 9. Бiблiогр.: 13 назв.

Ключовi слова: управлiння кроком; еволюцiйнi рiвняння; метод прямих; колокацiйнi блочнi рiзницевi схеми; змiннi розмiрностi.

УДК 004.272.2:519.63

Разработка коллокационных схем параллельного управления шагом в эволюционных уравнениях / Дмитриева О. А., Гуськова Н.Г. // Вестник НТУ "ХПИ". Серия: Информатика и моделирование. - Харьков: НТУ "ХПИ". - 2018. - № 24 (1300). -С. 25 - 36.

Работа посвящена вопросам параллельного управления шагом интегрирования по переменной времени при сведении эволюционных уравнений методом прямых к задаче Коши. Численная реализация осуществляется коллокационными блочными разностными схемами с изменяемыми размерностями опорных и расчетных блоков. Программное формирование расчетных формул позволяет отслеживать динамику вычислительного процесса и автоматически переходить на схемы растяжения - сжатия шага. Приведенные теоретические положения подкреплены экспериментальными исследованиями на тестовых задачах. Ил.: 9. Библиогр.: 13 назв.

Ключевые слова: управление шагом; эволюционные уравнения; метод прямых; коллокационные блочные разностные схемы; изменяемые размерности.

UDC 004.272.2:519.63

Development of collocation schemes for parallel control of step applicable to the evolution equations / Dmytriyeva O., Huskova N. // Herald of the National Technical University "KhPI". Subject issue: Information Science and Modelling. - Kharkov: NTU "KhPI". - 2018. - №. 24 (1300). - P. 25 - 36.

The paper is devoted to the problems of parallel control of integration step over time variable when evolution equations are reduced by the method of lines to the Cauchy problem. Numerical realization is carried out by collocation block difference schemes using varying dimensions of reference and calculation blocks. The program formation of calculation formulas allows to monitor the dynamics of the computational process and automatically switch to stretching schemes - step compression. These theoretical positions are supported by experimental studies of test problems. Figs.: 9. Refs.: 13 titles.

Keywords: step control; evolution equations; method of lines; collocation block difference schemes; varying dimensions.