Модификация метода Шварца для уравнения диффузии дробного порядка

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

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

2) Если отсутствует пространственная декомпозиция - в этом случае отсутствует необходимость интерполяции по пространственной переменной и алгоритм становится прямой комбинацией модифицированного на уравнения дробного порядка параллельного алгоритма и классического последовательного алгоритма конечно-разностного решения таких уравнений.

3.5 Оценка эффективности параллельного алгоритма с декомпозицией по пространству

Сначала приведем оценку трудоемкости последовательного алгоритма решения задачи (3.1.3), (3.1.4), построенного по явной схеме с аппроксимацией дробных производных по формуле Грюнвальда-Летникова. Шаг сетки по пространственной и временной переменным для последовательного алгоритма примем равным соответствующим шагам точной сетки параллельного алгоритма (в этом случае последовательное и параллельное решения будут иметь одинаковый порядок точности). Таким образом, имеем расчетных узлов по пространству и M расчетных узлов по времени. Расчет временного слоя по последовательному алгоритму требует операций. Принимая, как обычно при таких оценках, время выполнения одной операции за единицу, получаем время выполнения последовательного алгоритма равным

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

1) Операций, необходимых для вычисления дробных производных: ;

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

3) Операций, необходимых для расчета значений в узлах грубой сетки: ;

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

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

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

Тогда для ускорения параллельного алгоритма получаем следующую оценку:

(последняя оценка становится справедливой при ). Заметим, что число временных слоев M при использовании явной схемы может оказаться достаточно большим.

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

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

3.6 Оценка эффективности параллельного алгоритма с декомпозицией по времени

Время выполнения последовательного алгоритма оценивается аналогично в разделе 3.5 и составляет (оценка изменилась, поскольку теперь имеем слоев точной сетки по времени).

Оценим время исполнения параллельного алгоритма. Как и ранее, долей последовательного расчета, выполняемого на этапе инициализации алгоритма до начала основной вычислительной процедуры, пренебрегаем. Расчет выполняется на грубой и точной сетках, определенных в (3.2.1).

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

1) Операций, необходимых для вычисления дробных производных: ;

2) Операций, необходимых для вычисления интегралов по явным аналитическим формулам через сплайн-интерполяцию:

3) Операций, необходимых для расчета на грубой сетке по «грубому» методу и уточнению значений U по формуле (17): ;

4) Операций, необходимых для вычисления коэффициентов интерполяционного сплайна:

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

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

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

3.7 Численное решение метода

Для тестирования предлагаемого алгоритма и оценки его точности рассмотрим простейший случай, когда правая часть уравнения (3.7.1) является линейной. Будем решать следующую задачу Коши:

Аналитическое решение задачи (1) имеет вид

где функция МиттагЛеффлера [13]. График решения для трех значений даны на рисунке 1.

Также аналитически может быть вычислен интеграл

где гипергеометрическая функция. Данное представление использовалось для оценки погрешности аппроксимации интеграла в предлагаемом алгоритме.

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

Ошибка решения при номер итерации.

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

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

Заключение

Изложенные выше методы являются основой для построения большинства современных алгоритмов, нацеленных на решение практических задач в геометрически сложных областях. В ходе исследования были рассмотрены метод решения дробно-дифференциальных уравнений переноса на основе модифицированного метода Шварца и двухсеточные параллельные алгоритмы для решения дробно-дифференциальных уравнений аномальной диффузии. Теория данных методов была разработана Лукащуком С.Ю. [9] и рядом других авторов.

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

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

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

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

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

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

1. Бейтмен Г. Высшие трансцендентные функции. / Г. Бейтмен, А. Эрдейи / Эллиптический и автоморфные функции. Функции ламе и Матье, том 2, М., 1967.

2. Бейтмен Г. Высшие трансцендентные функции./Г. Бейтмен, А. Эрдейи/ Эллиптический и автоморфные функции. Функции ламе и Матье, том 2, М., 1967.

3. Гахов Ф. Д. Краевые задачи. - М.: Наука, 1977. - С. 10-638.

4. Гендер М.Д. Оптимизированный метод Шварца, сходящийся со слабой зависимостью./ М.Д. Гендер, Г.Х. Голуб/ Международная конференция методов декомпозиции. Мехико, 2003. - С. 281-283.

5. Кобелев В. Л. Недебаевская релаксация и диффузия в фрактальном пространстве /В. Л. Кобелев, Я. Л. Кобелев, Е. П. Романов/ Докл. РАН, том 361, № 6. 1998, С. 755--758.

6. Копысов С.П. Объектно-ориентированный метод декомпозиции области. / И.В. Красноперов, В.Н. Рычков/ Вычислительные методы и программирование. - Самара, 2003. - С. 3-18.

7. Костицын В.И. Дробные производные в нелинейной динамике. - М.: Наука, 2010. - С. 1-56.

8. Кочубей А. Н. Диффузия дробного порядка /А. Н. Кочубей/ Дифференциальные уравнения, том 26, № 4, 1990, С. 660--670.

9. Лукащук С.Ю. Модификация параллельного алгоритма для решения дифференциальных уравнений дробного порядка. /С.Ю. Лукащук/ Параллельные вычислительные технологии. Труды международной научной конференции. Челябинск: Изд. ЮУрГУ, 2010. С. 519-524.

10. Натансон И. П. Конструктивная теория функций. - М.-Л.: Гостехиздат, 1949. - С. 12-688.

11. Нахушев А. М. Уравнения математической биологии. М., 2003.

12. Нахушев А. М. Дробное исчисление и его применение. М., 2003.

13. Попов А. Ю. Распределение корней функций Миттаг-Леффлера./ А.Ю. Попов, А. М. Седлецкий / Современная математика. Фундаментальные направления, том 40, 2011, С.3-171.

14. Псху А.В. Краевая задача для дифференциального уравнения с частными производными дробного порядка / А.В. Псху/ Изв. Кабардино-Балкарского научного центра РАН, том 1, № 8. 2002, С. 76-78.

15. Псху А.В. Видоизмененная задача Коши для уравнения с частными

производными дробного порядка /А. В. Псху/ Спектральная теория дифференциальных операторов и родственные проблемы: Международная научная конференция, Стерлитамак, Башкортостан, Сборник научных трудов, том 1, 2003, С. 194-198.

16. Самарский А.А. Теория разностных схем. - М.: Наука, 1977.

17. Самарский А.А. Аддитивные схемы для задач математической физики. / В.П. Самарский, В.П. Вабищевич/ - М.: Наука, 1999.

18. Самко С. Г. Интегралы и производные дробного порядка и некоторые их приложения. / С. Г. Самко, А. А Килбас, О. И. Маричев./ Минск, 1987.

19. Таукенова Ф. И. Разностные методы решения краевых задач для дифференциальных уравнений дробного порядка /Ф. И. Таукенова, М. Х. Шхануков-Лафишев / Журнал вычислительной математики и математической физики, том 46, № 10, 2006, С. 1871--1881.

20. Филимонов В.А. Статистические свойства квазифрактальных случайных процессов. - М.: Наука, 2008. - С. 3-18.

21. Хайрер Э. Решение обыкновенных дифференциальных уравнений. /Э. Хайрер, С. Нерсетт, Г. Ваннер/ Нежесткие задачи. М., 1990.

22. Чукбар К. В. Стохастический перенос и дробные производные /К. В. Чукбар/ Журн. эксперим. и теор. Физики, том 108, вып. 5, № 11, 1995, С. 1875--1884.

23. Шхануков-Лафишев М.Х. Разностные схемы для неклассических задач математической физики. - Нальчик: Институт прикладной математики и автоматизации КБНЦ РАН, 2008.

24. Яненко Н.Н. Метод дробных шагов решения многомерных задач математической физики. / Н.Н. Яненко / Лекции для студентов НГУ. - Новосибирск, 1966.

25. Учайкин В.В. Автомодельная аномальная диффузия и устойчивые законы. / В.В. Учайкин/ УФН, том 173, № 8, 2003, C. 847-876.

26. Учайкин В.В. Метод дробных производных. 2008, С. 512.

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

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