Main menu

Метод моментов в электродинамике (MoM): численное решение интегральных уравнений

Как рассчитать антенну мобильного телефона?

В мире вычислительной электродинамики, помимо дифференциальных сеточных методов вроде FDTD (Метод конечных разностей во временной области), существует мощнейший альтернативный класс численных алгоритмов. Когда инженерам необходимо спроектировать сложную проволочную антенну (как на Wi-Fi роутере), рассчитать эффективную площадь рассеяния (ЭПР) истребителя-невидимки или спроектировать микрополосковую плату смартфона, классические 3D-сетки FDTD оказываются крайне неудобными. Моделирование тонких проводов толщиной в доли миллиметра в свободном безграничном пространстве требует слишком мелкой объемной сетки и абсурдного расхода памяти.

В этих случаях индустрия обращается к интегральной формулировке уравнений Максвелла. Физическая суть этой формулировки заключается в законе Био-Савара-Лапласа и потенциалах: электрические токи, текущие по металлическим поверхностям антенны, излучают электромагнитное поле. Интегральное уравнение (например, EFIE — уравнение электрического поля) связывает неизвестное распределение токов на поверхности металла с заданным падающим возбуждающим полем (например, от кабеля питания). Для численного решения этого интегрального уравнения в 1968 году Роджер Харрингтон формализовал универсальный алгоритм, названный Методом моментов (Method of Moments, MoM).

От физического интеграла к матрице сопротивлений

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

Затем интегральное уравнение умножается на весовые (тестовые) функции и интегрируется по всей поверхности детали. В результате этой математической операции бесконечномерное интегральное уравнение превращается в плотную систему линейных алгебраических уравнений (СЛАУ): [Z] * [I] = [V]. В этой формуле вектор [I] — это неизвестные токи, вектор [V] — напряжения (возбуждение), а гигантская матрица [Z] имеет глубочайший физический смысл. Она называется обобщенной матрицей взаимных импедансов (сопротивлений). Каждый элемент этой матрицы описывает электромагнитное влияние (излучение) одной базисной функции тока на другую через открытое пространство.

Сингулярности функции Грина и открытое пространство

Вычисление элементов матрицы импедансов [Z] является самой сложной и ресурсоемкой частью Метода моментов. Внутри интегралов содержится функция Грина свободного пространства (ядро интегрального оператора), которая имеет вид exp(-ikr)/r. Эта функция обратно пропорциональна расстоянию (r) между током источника и точкой наблюдения. Если мы вычисляем самовоздействие элемента (то есть расстояние r стремится к нулю), функция уходит в бесконечность!

Попытка вычислить такой сингулярный интеграл обычным методом Гаусса даст математический мусор. Инженерам приходится использовать специальные аналитические методы выделения особенности для точного вычисления диагональных элементов матрицы. Огромным, неоспоримым преимуществом MoM является то, что этот алгоритм автоматически и идеально строго учитывает условие излучения Зоммерфельда на бесконечности. Волна беспрепятственно улетает в космос, и алгоритму не нужны никакие искусственные поглощающие слои (PML) на границах расчетной области. Сегодня алгоритм MoM (часто ускоренный Быстрым мультипольным методом FMM для борьбы с плотной матрицей) лежит в основе ведущих радиотехнических САПР, таких как Altair FEKO и CST Microwave Studio.

Подробнее

Интерполяция Эрмита: учет значений функции и ее производных в геометрии

Недостатки классической интерполяции Лагранжа

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

Инженеру необходимо жестко контролировать не только то, ГДЕ должна оказаться кривая в данный момент времени, но и КУДА она должна быть направлена (какова ее скорость и ускорение). Эту фундаментальную задачу решает метод интерполяции Шарля Эрмита. Алгоритм Эрмита обобщает интерполяцию Лагранжа на случай, когда в узлах сетки известны (и должны строго соблюдаться) не только значения самой функции, но и значения ее производных до заданного порядка.

Разделенные разности с кратными узлами

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

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

Кубические сплайны Эрмита и сплайны Акимы

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

На каждом интервале между двумя точками строится отдельный полином 3-й степени, который жестко фиксируется 4 условиями: двумя значениями функции по краям и двумя значениями производных по краям. В отличие от обычного кубического сплайна, где производные вычисляются алгоритмом глобально (через решение СЛАУ для обеспечения гладкости второй производной во всех точках), в сплайнах Эрмита производные задаются локально и вручную инженером (или локальными эвристиками). Одной из самых знаменитых реализаций является Сплайн Акимы (Hiroshi Akima, 1970). Алгоритм Акимы вычисляет производные в узлах локально, опираясь на геометрию нескольких соседних точек. В результате сплайн Акимы практически не подвержен паразитным выбросам (overshoots) и изломам в местах резкого изменения данных, являясь золотым стандартом для интерполяции физических табличных данных (например, термодинамических свойств газов) без искусственных осцилляций.

Подробнее

Вычислительная алгебраическая геометрия: базисы Грёбнера и полиномиальные системы

Когда метод Ньютона бессилен

Решение систем нелинейных уравнений — одна из сложнейших задач численного анализа. Если система состоит из многочленов (полиномиальная система), она возникает в криптографии, робототехнике (обратная кинематика манипуляторов), компьютерном зрении и молекулярной химии. Обычно для таких систем применяют многомерный метод Ньютона-Канторовича. Но метод Ньютона — локальный. Он найдет лишь один корень вблизи начальной точки. Что если инженеру нужно найти строго все корни системы (или доказать, что их вообще не существует)? Что если корней бесконечно много и они образуют кривые поверхности (алгебраические многообразия)? Здесь численные приближения пасуют, и в дело вступает вычислительная коммутативная алгебра.

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

Алгоритм Бухбергера: нелинейный аналог исключения Гаусса

Основная идея Бухбергера опирается на понятие идеала в кольце многочленов (множества всех полиномов, которые обращаются в ноль там же, где и исходные уравнения). Любая система задает свой базис этого идеала. Базис Грёбнера — это такой «идеальный» базис, в котором старшие члены полиномов обладают специальным свойством делимости.

Алгоритм Бухбергера берет пары исходных полиномов и вычисляет их S-полиномы (специальные комбинации, в которых искусственно уничтожаются старшие степени, подобно обнулению коэффициентов в методе Гаусса). Затем эти S-полиномы делятся на исходный базис с остатком. Если остаток не равен нулю, он добавляется в систему как новое уравнение (не меняющее корней!). Этот процесс генерации новых полиномов продолжается до тех пор, пока все возможные остатки не станут нулями. Теорема Гильберта о базисе гарантирует, что этот процесс обязательно остановится.

Триумф лексикографического порядка

Самая мощная магия базисов Грёбнера раскрывается при использовании лексикографического порядка сортировки одночленов (как слова в словаре). Если мы вычислим базис Грёбнера с таким порядком, то в полученной эквивалентной системе уравнений последний полином будет содержать только одну неизвестную переменную (например, только z)! Предпоследний полином будет содержать z и y, и так далее. Мы получаем строго треугольную систему.

Теперь решение нелинейной многомерной системы сводится к банальному вычислению корней одного полинома от одной переменной (что можно сделать численно с огромной точностью), а затем обратной подстановкой найденных значений в верхние уравнения системы. Алгоритм Бухбергера, интегрированный в системы компьютерной алгебры (Maple, Mathematica), требует гигантских объемов памяти (сложность алгоритма часто дважды экспоненциальная EXPSPACE), но его способность находить абсолютно все скрытые корни сделала его незаменимым аналитическим инструментом современной прикладной геометрии.

Подробнее

Соц. сети