Main menu

Численное интегрирование функций с сингулярностями: метод Tanh-Sinh

Когда подынтегральная функция уходит в бесконечность

Классические методы численного интегрирования (квадратуры Ньютона-Котеса, формулы Симпсона или Гаусса) блестяще справляются с гладкими функциями, которые заданы на конечном отрезке. Однако в физических задачах математикам постоянно приходится сталкиваться с интегралами, которые имеют математические особенности — сингулярности. Например, при расчетах потенциала заряженной нити или в задачах механики разрушения (напряжения на кончике трещины) подынтегральная функция может уходить в бесконечность на краях отрезка или иметь вертикальные асимптоты. Классический алгоритм, столкнувшись с бесконечностью (делением на ноль), выдаст ошибку Not-a-Number (NaN) или будет сходиться катастрофически медленно.

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

Магия нелинейных замен переменных

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

Но настоящим прорывом и шедевром японской вычислительной школы стало создание в 1974 году квадратурной формулы гиперболического тангенса-синуса (Tanh-Sinh quadrature, или метод двойной экспоненциальной интеграции). Этот метод был разработан Хидетаси Такахаси и Масатаке Мори. Идея заключается во введении сложнейшей подстановки: x = tanh(pi/2 * sinh(t)). Эта функция обладает потрясающим топологическим свойством: она отображает бесконечный интервал (от минус до плюс бесконечности) строго в конечный отрезок [-1, 1].

Двойное экспоненциальное затухание

При выполнении этой замены дифференциал интегрирования (якобиан) порождает функцию, которая убывает к нулю с феноменальной скоростью — по закону двойной экспоненты: exp(-C * exp(|t|)). Эта скорость убывания настолько сокрушительна, что она способна мгновенно подавить (помножить на ноль) абсолютно любую математическую сингулярность исходной функции на краях отрезка!

После такой замены переменной мы получаем новый, гладкий и колоколообразный интеграл на бесконечной прямой, для вычисления которого применяется самое простое правило трапеций (да, базовая формула трапеций на бесконечном интервале для гладких убывающих функций работает точнее сложных методов Гаусса). Алгоритм Tanh-Sinh позволяет с феноменальной легкостью брать интегралы с любыми концевыми сингулярностями, логарифмическими разрывами или бесконечными производными, достигая невероятной точности в тысячи знаков после запятой в системах произвольной разрядности. Сегодня этот алгоритм встроен в ядра таких мощных математических систем, как MPMath в Python и Boost.Math в C++.

Подробнее

Алгоритмы на графах для разреженных матриц: Катхилл-Макки и минимальная степень

Скрытая угроза прямых решателей: проблема заполнения

Мы неоднократно обращали внимание на то, что огромные системы уравнений (СЛАУ), возникающие в инженерных расчетах, являются сверхразреженными: в них присутствуют миллионы нулей и лишь малая доля значащих чисел. Для их хранения созданы эффективные форматы вроде CSR. Однако если мы попытаемся решить такую систему точным, прямым методом (LU-разложение или разложение Холецкого для симметричных матриц), мы столкнемся с катастрофическим явлением, которое в вычислительной алгебре называется «заполнением» (fill-in).

В процессе прямого исключения переменных (вспомните метод Гаусса), вычитая одну строку из другой, алгоритм неизбежно складывает ненулевые элементы. Если в исходной строке стоял спасительный ноль, то в процессе прямого хода на его месте может появиться значащее число. К концу алгоритма матрица, которая изначально была почти пустой, рискует превратиться в гигантскую, абсолютно плотную структуру. Миллионы нулей исчезнут, алгоритм сожрет всю оперативную память кластера (Out of Memory) и процесс остановится. Как же предотвратить это катастрофическое разрастание данных?

Матрица как топологический граф

Гениальное решение пришло на стыке алгебры и дискретной математики. Любую симметричную матрицу можно представить в виде неориентированного графа. Каждая строка (уравнение) — это узел графа (вершина). Если матричный элемент на пересечении строки A и столбца B не равен нулю, значит между узлом A и узлом B в графе существует физическое ребро связи. Заполнение матрицы в процессе LU-разложения в терминах теории графов означает добавление новых, фиктивных ребер между узлами.

Порядок, в котором мы перечисляем уравнения (нумеруем переменные x1, x2, x3), не меняет физического решения системы, но он критически, на порядки, влияет на уровень заполнения матрицы нулями в памяти! Следовательно, перед тем как запустить вычислительно тяжелое LU-разложение, нам нужно запустить быстрый алгоритм переупорядочивания (эвристику на графе), который найдет оптимальную нумерацию строк и столбцов матрицы для минимизации будущего заполнения.

Ширина ленты и алгоритмы Reverse Cuthill-McKee (RCM)

Первым классом таких алгоритмов стали методы уменьшения ширины ленты (Bandwidth reduction). Исторически самым известным из них является алгоритм Катхилла-Макки (Cuthill-McKee), а точнее его улучшенная версия — обратный алгоритм Катхилла-Макки (RCM). Алгоритм начинает поиск с периферийного узла графа (узла с минимальным количеством связей) и послойно, методом поиска в ширину (BFS), перенумеровывает все связанные с ним узлы. В результате все ненулевые элементы матрицы «сбегаются» и плотно прижимаются к главной диагонали, образуя узкую ленту. Вне этой ленты остаются чистые нули, которые гарантированно никогда не заполнятся при разложении.

Для более сложных и неструктурированных 3D-сеток ленточные алгоритмы уступают место семейству методов минимальной степени (Minimum Degree Algorithm — AMD). Алгоритм AMD работает на опережение: на каждом шаге он симулирует процесс исключения Гаусса и всегда выбирает для исключения ту переменную, узел которой в графе в данный момент имеет наименьшее число соседей (минимальную степень). Это локально жадная эвристика, но она минимизирует создание новых ребер на каждом микрошаге. Сегодня мощнейшие программные комплексы на графах (такие как METIS или Scotch) выполняют глубокое иерархическое разбиение графа матрицы на кластеры, что является обязательным «нулевым» шагом перед любым суперкомпьютерным матричным расчетом.

Подробнее

Метод спектральных элементов: объединение гибкости МКЭ и точности рядов

Объединение гибкости и невероятной точности

Исторически в вычислительной математике сформировались два мощных, но противоположных подхода к решению дифференциальных уравнений в частных производных (УЧП). С одной стороны, метод конечных элементов (МКЭ) предлагает непревзойденную геометрическую гибкость, позволяя разбивать сложнейшие трехмерные детали на миллионы крошечных тетраэдров. Однако классический МКЭ обычно использует базисные полиномы низких порядков (первого или второго), что обеспечивает лишь алгебраическую (медленную) скорость сходимости. С другой стороны, спектральные методы, основанные на рядах Фурье или полиномах Чебышева, обеспечивают экспоненциальную (спектральную) скорость сходимости: при увеличении числа узлов ошибка падает стремительно, достигая машинной точности. Но классические спектральные методы жестко привязаны к простым прямоугольным или сферическим областям и пасуют перед сложной геометрией.

В 1984 году Энтони Патера предложил элегантный математический мост между этими двумя мирами, создав Метод спектральных элементов (Spectral Element Method, SEM). Идея метода заключается в том, чтобы взять лучшее от обоих подходов. Расчетная область со сложной геометрией разбивается на крупные макроэлементы (гексаэдры в 3D или четырехугольники в 2D), подобно тому, как это делается в МКЭ. Эта операция обеспечивает необходимую геометрическую гибкость алгоритма и возможность распараллеливания.

Внутри элемента: полиномы высоких порядков

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

Узлы интерполяции внутри макроэлемента располагаются не равномерно, а сгущаются к границам элемента (так называемые узлы Гаусса-Лобатто-Лежандра). Такое неравномерное распределение математически необходимо для предотвращения катастрофических осцилляций на краях (феномена Рунге) при использовании полиномов 10-й, 15-й или даже 20-й степени. Матрицы масс и жесткости, возникающие при дискретизации по методу Галеркина на таких узлах, вычисляются с использованием спектрально-точных квадратурных формул Гаусса. Благодаря этому массовые матрицы получаются строго диагональными, что позволяет обращать их мгновенно, делая метод невероятно эффективным для нестационарных задач.

Применение в гидродинамике и глобальной сейсмологии

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

Первая область — это прямое численное моделирование (DNS) турбулентных течений несжимаемой жидкости при низких и средних числах Рейнольдса. Программный комплекс Nek5000, разработанный Полом Фишером в Аргоннской национальной лаборатории, использует метод спектральных элементов для расчета гидродинамики ядерных реакторов на крупнейших мировых суперкомпьютерах. Вторая область — это глобальная сейсмология. Распространение сейсмических волн от землетрясений сквозь мантию Земли идеально описывается упругими волновыми уравнениями. Комплекс SPECFEM3D использует метод спектральных элементов для создания высокоточных томографических моделей строения нашей планеты, так как алгоритм позволяет избежать численной дисперсии (искусственного искажения скорости волн), от которой сильно страдают обычные конечно-разностные схемы.

Подробнее

Соц. сети