Эта статья требует внимания специалиста по математике . Июль 2009 г. ) ( |
Численное продолжение - это метод вычисления приближенных решений системы параметризованных нелинейных уравнений,
Параметр , как правило , настоящая скалярный , и решение п -векторных . При фиксированном значении параметра , отображает евклидово п-пространство в себя.
Часто исходное отображение из банахова пространства в себя, а евклидово n-пространство является конечномерным приближением к банаховому пространству.
Устойчивое состояние , или с фиксированной точка , из параметризованного семейства из потоков или карт имеет эту форму, и дискретизация траектории потока или итерацию карты, периодические орбиты и гетероклинические орбиты также могут быть поставлены в виде раствора .
Другие формы [ править ]
В некоторых нелинейных системах параметры указаны явно. В других они неявные, и система нелинейных уравнений записывается
где - n -вектор, а его изображение - вектор n-1 .
Эта формулировка без явного пространства параметров обычно не подходит для формулировок в следующих разделах, поскольку они относятся к параметризованным автономным нелинейным динамическим системам вида:
Однако в алгебраической системе нет различия между неизвестными и параметрами.
Периодические движения [ править ]
Периодическое движение представляет собой замкнутую кривую в фазовом пространстве. То есть, в течение некоторого периода ,
Хрестоматийный пример периодического движения - незатухающий маятник .
Если фазовое пространство является периодическим по одной или нескольким координатам, скажем , с вектором [ требуется пояснение ] , то существует второй вид периодических движений, определяемых
для каждого целого числа .
Первым шагом в написании неявной системы для периодического движения является перемещение периода от граничных условий к ОДУ :
Второй шаг - добавить дополнительное уравнение, фазовое ограничение , которое можно рассматривать как определение периода. Это необходимо, потому что любое решение указанной выше краевой задачи может быть сдвинуто во времени на произвольную величину (время не фигурирует в определяющих уравнениях - динамическая система называется автономной).
Есть несколько вариантов ограничения фазы. Если - известная периодическая орбита при значении параметра около , то Пуанкаре использовал
который утверждает, что лежит в плоскости, ортогональной касательному вектору замкнутой кривой. Эта плоскость называется сечением Пуанкаре .
Для общей задачи лучшим фазовым ограничением является интегральное ограничение, введенное Евсебиусом Доделем, которое выбирает фазу так, чтобы минимизировать расстояние между известной и неизвестной орбитами:
Гомоклинические и гетероклинические движения [ править ]
Определения [ править ]
Компонент решения [ править ]
Компонент решения нелинейной системы - это набор точек, которые удовлетворяют исходному решению и связаны с ним путем решений, для которых и .
Числовое продолжение [ править ]
Численное продолжение представляет собой алгоритм , который принимает в качестве входных данных системы параметризованных нелинейных уравнений и начальное решение , и производит набор точек на компоненте раствора .
Обычная точка [ править ]
Регулярной точкой является точка, в которой якобиан системы полного ранга .
Вблизи регулярной точки компонент решения представляет собой изолированную кривую, проходящую через регулярную точку ( теорема о неявной функции ). На рисунке выше точка - обычная точка.
Особая точка [ править ]
Особая точка - это точка, в которой якобиан F не имеет полного ранга.
Вблизи особой точки компонента решения не может быть изолированной кривой, проходящей через регулярную точку. Локальная структура определяется высшими производными от . На рисунке выше точка пересечения двух синих кривых является особой точкой.
В целом компоненты раствора представляют собой разветвленные кривые . Точки ветвления - особые точки. Нахождение кривых решения , оставляя особую точку, называется переключением ветви, и используют методы из теории бифуркаций ( теорий особенностей , теории катастроф ).
Для конечномерных систем (как определено выше) разложение Ляпунова-Шмидта можно использовать для получения двух систем, к которым применима теорема о неявной функции. Разложение Ляпунова-Шмидта использует ограничение системы на дополнение к нулевому пространству якобиана и образ якобиана.
Если столбцы матрицы являются ортонормированным базисом для нулевого пространства
а столбцы матрицы являются ортонормированным базисом для левого нулевого пространства , тогда система может быть переписана как
где находится в дополнении к пустому пространству .
В первом уравнении, параметризованном нулевым пространством якобиана ( ), якобиан относительно неособен. Итак, теорема о неявной функции утверждает, что существует такое отображение , что и . Второе уравнение (с подставкой) называется уравнением бифуркации (хотя это может быть система уравнений).
Уравнение бифуркации имеет разложение Тейлора, в котором отсутствуют постоянные и линейные члены. Масштабируя уравнения и нулевое пространство якобиана исходной системы, можно найти систему с невырожденным якобианом. Постоянный член в ряду Тейлора масштабированного уравнения бифуркации называется алгебраическим уравнением бифуркации, а теорема о неявной функции, применяемая к уравнениям бифуркации, утверждает, что для каждого изолированного решения алгебраического уравнения бифуркации существует ветвь решений исходной задачи, которая проходит через особую точку.
Другой тип особой точки - это бифуркация точки поворота или бифуркация седло-узел , при которой направление параметра меняется на противоположное при следовании кривой. Красная кривая на рисунке выше показывает поворотный момент.
Особые алгоритмы [ править ]
Продолжение естественного параметра [ править ]
Большинство методов решения нелинейных систем уравнений являются итерационными методами. Для определенного значения параметра сопоставление многократно применяется к первоначальному предположению . Если метод сходится и непротиворечив, то в пределе итерация приближается к решению .
Продолжение естественного параметра - это очень простая адаптация итерационного решателя к параметризованной задаче. Решение при одном значении используется в качестве начального предположения для решения при . При достаточно малом количестве итерация, применяемая к первоначальному предположению, должна сходиться.
Одним из преимуществ естественного продолжения параметров является то, что он использует метод решения проблемы как черный ящик. Все, что требуется, - это дать начальное решение (некоторые решатели всегда начинали с фиксированного начального предположения). Было проделано много работы в области крупномасштабного продолжения по применению более сложных алгоритмов к решателям черного ящика (см., Например, LOCA ).
Однако естественное продолжение параметра не удается в поворотных точках, где разворачивается ветвь решений. Поэтому для проблем с точками поворота необходимо использовать более сложный метод, такой как продолжение псевдодуги (см. Ниже).
Симплициальное или кусочно-линейное продолжение [ править ]
Симплициальное продолжение или кусочно-линейное продолжение (Аллгауэр и Георг) основано на трех основных результатах.
Первый - это
Если F (x) отображает IR ^ n в IR ^ (n-1), существует единственный линейный интерполянт на (n-1) -мерном симплексе, который согласуется со значениями функций в вершинах симплекса.
Второй результат:
(N-1) -мерный симплекс может быть протестирован, чтобы определить, принимает ли уникальный линейный интерполянт значение 0 внутри симплекса.
Подробности см. В статье о кусочно-линейном продолжении .
С помощью этих двух операций этот алгоритм продолжения легко сформулировать (хотя, конечно, эффективная реализация требует более сложного подхода. См. [B1]). Предполагается, что начальный симплекс задан из эталонного симплициального разложения IR ^ n. Исходный симплекс должен иметь по крайней мере одну грань, которая содержит нуль единственного линейного интерполянта на этой грани. Затем проверяются другие грани симплекса, и обычно будет одна дополнительная грань с внутренним нулем. Затем исходный симплекс заменяется симплексом, который лежит на любой грани, содержащей ноль, и процесс повторяется.
Ссылки: Олгауэр и Георг [B1] дают четкое и ясное описание алгоритма.
Продолжение псевдо-длины дуги [ править ]
Этот метод основан на наблюдении, что «идеальной» параметризацией кривой является длина дуги. Псевдо-длина дуги - это аппроксимация длины дуги в касательном пространстве кривой. Результирующий модифицированный метод естественного продолжения делает шаг в псевдо-длине дуги (а не ). Итерационный решатель требуется, чтобы найти точку с заданной длиной псевдодуги, что требует добавления дополнительного ограничения (ограничения псевдо длины дуги) к якобиану n на n + 1. Он дает квадратный якобиан, и если размер шага достаточно мал, модифицированный якобиан имеет полный ранг.
Продолжение псевдо-длины дуги было независимо разработано Эдвардом Риксом и Джеральдом Вемпнером для приложений конечных элементов в конце 1960-х годов и опубликовано в журналах в начале 1970-х годов Х. Б. Келлером. Подробный отчет об этих ранних разработках представлен в учебнике М.А. Крисфилда: Нелинейный конечно-элементный анализ твердых тел и структур, Том 1: Основные концепции, Wiley, 1991. Крисфилд был одним из самых активных разработчиков этого класса методов, которые к настоящему времени являются стандартными процедурами коммерческих нелинейных программ конечных элементов.
Алгоритм представляет собой метод предиктора-корректора. Шаг прогнозирования находит точку (в IR ^ (n + 1)), которая является шагом по касательному вектору в текущем указателе. Корректором обычно является метод Ньютона или его вариант для решения нелинейной системы
где - касательный вектор в точке . Якобиан этой системы - матрица с краем
В регулярных точках, где неизмененный якобиан имеет полный ранг, касательный вектор охватывает нулевое пространство верхней строки этого нового якобиана. Добавление касательного вектора в качестве последней строки можно рассматривать как определение коэффициента нулевого вектора в общем решении системы Ньютона (частное решение плюс произвольное кратное нулевого вектора).
Продолжение Гаусса – Ньютона [ править ]
Этот метод представляет собой вариант продолжения псевдо-длины дуги. Вместо использования касательной в начальной точке в ограничении длины дуги используется касательная в текущем решении. Это эквивалентно использованию псевдообратного якобиана в методе Ньютона и позволяет делать более длинные шаги. [B17]
Продолжение по более чем одному параметру [ править ]
Параметр в описанных выше алгоритмах является действительным скаляром. Большинство физических и конструктивных проблем обычно имеют более одного параметра. Многомерное продолжение относится к случаю, когда является k-вектором.
Применяется та же терминология. Регулярное решение является решением , при котором якобиан полный ранг . Особое решение - это решение, у которого якобиан меньше полного ранга.
Регулярное решение лежит на k-мерной поверхности, которая может быть параметризована точкой в касательном пространстве (нулевом пространстве якобиана). Это снова прямое применение теоремы о неявной функции.
Применение методов численного продолжения [ править ]
Методы численного продолжения нашли широкое распространение при изучении хаотических динамических систем и различных других систем, относящихся к области теории катастроф . Причина такого использования проистекает из того факта, что различные нелинейные динамические системы ведут себя детерминированным и предсказуемым образом в пределах диапазона параметров, которые включены в уравнения системы. Однако для определенного значения параметра система начинает вести себя хаотично, и, следовательно, возникла необходимость следить за параметром, чтобы иметь возможность расшифровать случаи, когда система начинает быть непредсказуемой, и что именно (теоретически) заставляет систему становиться нестабильный.
Анализ продолжения параметров может привести к более глубокому пониманию бифуркаций стабильной / критической точки. Изучение седло-узловых, транскритических, питч-вилок, удвоений периода, Хопфа, вторичных бифуркаций Хопфа (Неймарка) устойчивых решений позволяет теоретически обсудить обстоятельства и явления, которые возникают в критических точках. Продолжение параметров также дает более надежную систему для анализа динамической системы, поскольку она более устойчива, чем более интерактивные численные решения с временным шагом. Особенно в случаях, когда динамическая система склонна к взрыву при определенных значениях параметров (или комбинации значений для нескольких параметров). [2]
Чрезвычайно интересно наличие устойчивых решений (притягивающих или отталкивающих) при изучении нелинейных дифференциальных уравнений с частными производными, где изменение времени в форме алгоритма Крэнка Николсона является чрезвычайно трудоемким, а также нестабильным в случаях нелинейного роста зависимые переменные в системе. Изучение турбулентности - еще одна область, в которой методы численного продолжения использовались для изучения появления турбулентности в системе, начинающейся с малых чисел Рейнольдса. Кроме того, исследования с использованием этих методов предоставили возможность найти устойчивые многообразия и бифуркации на инвариантные торы в случае ограниченной задачи трех тел.в ньютоновской гравитации, а также дали интересное и глубокое понимание поведения таких систем, как уравнения Лоренца .
Программное обеспечение [ править ]
(В разработке) См. Также список группы деятельности SIAM по динамическим системам http://www.dynamicalsystems.org/sw/sw/
- АВТО: Вычисление решений двухточечных краевых задач (TPBVP) с интегральными ограничениями. https://sourceforge.net/projects/auto-07p/ Доступно на SourceForge.
- HOMCONT: Расчет гомоклинических и гетероклинических орбит. Включено в АВТО
- MATCONT: набор инструментов Matlab для числового продолжения и бифуркации [1] Доступен на SourceForge.
- DDEBIFTOOL: Вычисление решений дифференциальных уравнений с запаздыванием. Пакет MATLAB. Доступен в KU Leuven
- PyCont: набор инструментов Python для числового продолжения и бифуркации. Собственные алгоритмы Python для продолжения с фиксированной точкой, сложный интерфейс для AUTO для других типов проблем. Входит в состав PyDSTool
- CANDYS / QA: можно получить в Потсдамском университете [A16]
- МАНПАК: доступно в Netlib [A15]
- PDDE-CONT: http://seis.bris.ac.uk/~rs1909/pdde/
- multifario: http://multifario.sourceforge.net/
- LOCA: https://trilinos.org/packages/nox-and-loca/
- DSTool
- GAIO
- OSCILL8: Oscill8 - это инструмент динамических систем, который позволяет пользователю исследовать многомерное пространство параметров нелинейных ОДУ, используя методы бифуркационного анализа. Доступно на SourceForge .
- MANLAB: Вычисление равновесного, периодического и квазипериодического решения дифференциальных уравнений с использованием ряда Фурье (метод гармонического баланса) развития решения и развития ряда Тейлора (асимптотический численный метод) ветви решения. Доступно в LMA Marseille.
- BifurcationKit.jl: Этот пакет Julia направлен на выполнение автоматического бифуркационного анализа уравнений большой размерности F (u, λ) = 0, где λ∈ℝ, с использованием преимуществ итерационных методов, разреженных формулировок и конкретных аппаратных средств (например, GPU). [2]
Примеры [ править ]
Эта проблема поиска точек, которые F отображает в начало координат, появляется в компьютерной графике как задачи рисования контурных карт (n = 2) или изоповерхности (n = 3). Контур со значением h - это совокупность всех компонент решения Fh = 0
Ссылки [ править ]
- ^ Введение в численные методы продолжения Юджина Л. Аллгауэра и Курта Георга Государственного университета Колорадо 1990
- ^ Engelnkemper, S .; Гуревич С.В.; Uecker, H .; Wetzel, D .; Тиле, У. (7 июля 2018 г.). Вычислительное моделирование бифуркаций и неустойчивостей в гидродинамике . Springer. С. 459–501. arXiv : 1808.02321 . DOI : 10.1007 / 978-3-319-91494-7_13 . ISBN 9783319914930.
Книги [ править ]
[B1] « Введение в методы численного продолжения », Юджин Л. Аллгауэр и Курт Георг, SIAM Classics in Applied Mathematics 45. 2003.
[B2] " Численные методы бифуркаций динамических равновесий ", Вилли Дж. Ф. Говертс, SIAM 2000.
[B3] " Методы Ляпунова-Шмидта в нелинейном анализе и приложениях ", Николай Сидоров, Борис Логинов, Александр Синицын и Михаил Фалалеев, Kluwer Academic Publishers, 2002.
[B4] " Методы теории бифуркаций ", Шуй-Ни Чоу и Джек К. Хейл, Springer-Verlag 1982.
[B5] " Элементы прикладной теории бифуркаций ", Юрий А. Кунецов, Springer-Verlag Applied Mathematical Sciences 112, 1995.
[B6] «Нелинейные колебания, динамические системы и бифуркации векторных полей», Джон Гукенхаймер и Филип Холмс , Springer-Verlag Applied Mathematical Sciences 42, 1983.
[B7] " Элементарная стабильность и теория бифуркаций ", Джерард Йосс и Дэниел Д. Джозеф, Тексты для студентов Springer-Verlag по математике , 1980.
[B8] " Теория сингулярностей и введение в теорию катастроф ", Юнг-Чен Лу, Springer-Verlag, 1976.
[B9] " Глобальные бифуркации и хаос, аналитические методы ", С. Виггинс, Springer-Verlag Applied Mathematical Sciences 73, 1988.
[B10] " Особенности и группы в теории бифуркаций, том I ", Мартин Голубицкий и Дэвид Г. Шеффер, Springer-Verlag Applied Mathematical Sciences 51, 1985.
[B11] " Особенности и группы в теории бифуркаций, том II ", Мартин Голубицкий , Ян Стюарт и Дэвид Г. Шеффер, Springer-Verlag Applied Mathematical Sciences 69, 1988.
[B12] « Решение полиномиальных систем с использованием продолжения для инженерных и научных задач », Александр Морган, Прентис-Холл, Энглвуд Клиффс, Нью-Джерси, 1987.
[B13] « Пути к решениям, фиксированные точки и равновесия », CB Garcia и WI Zangwill, Prentice-Hall, 1981.
[B14] « Теорема о неявной функции: история, теория и приложения », Стивен Г. Кранц и Гарольд Р. Паркс , Бирхаузер, 2002.
[B15] « Нелинейный функциональный анализ », JT Schwartz, Gordon and Breach Science Publishers, Notes on Mathematics and its Applications, 1969.
[B16] « Темы нелинейного функционального анализа », Луи Ниренберг (примечания Ральфа А. Артино), Лекционные заметки А.М.С. Куранта по математике 6, 1974.
[B17] " Методы Ньютона для нелинейных задач - аффинная инвариантность и адаптивные алгоритмы ", П. Деуфлхард, Серия Computational Mathematics 35, Springer, 2006.
Статьи журнала [ править ]
[A1] « Алгоритм кусочно-линейной аппроксимации неявно определенных двумерных поверхностей », Юджин Л. Аллгауэр и Стефан Гнутцманн, Журнал SIAM по численному анализу, том 24, номер 2, 452–469, 1987.
[A2] « Симплициальные методы и методы продолжения для приближений, неподвижных точек и решений систем уравнений », Элльгауэр и К. Георг, SIAM Review, том 22, 28–85, 1980.
[A3] « Алгоритм кусочно-линейной аппроксимации неявно определенного многообразия », Юджин Л. Аллгауэр и Филип Х. Шмидт, Журнал SIAM по численному анализу, том 22, номер 2, 322–346, апрель 1985 г.
[A4] « Построение контуров кусочно-линейными приближениями », Дэвид П. Добкин , Сильвио В.Ф. Леви, Уильям П. Терстон и Аллан Р. Уилкс, Транзакции ACM по графике, 9 (4) 389-423, 1990.
[A5] « Численное решение бифуркационных и нелинейных задач на собственные значения », Х. Б. Келлер, в «Приложениях теории бифуркаций», изд. П. Рабиновица, Academic Press, 1977.
[A6] « Локально параметризованный процесс продолжения », WC Rheinboldt и JV Burkardt, ACM Transactions on Mathematical Software, Volume 9, 236–246, 1983.
[A7] « Нелинейные числа » Э. Доедель, Международный журнал бифуркаций и хаоса , 7 (9): 2127-2143, 1997.
[A8] « Нелинейные вычисления », Р. Зейдел, Международный журнал бифуркаций и хаоса , 7 (9): 2105-2126, 1997.
[A9] « Об алгоритме движущегося каркаса и триангуляции равновесных многообразий », WC Rheinboldt, In T. Kuper, R. Seydel, and H. Troger eds. «ISNM79: Бифуркация: анализ, алгоритмы, приложения», страницы 256-267. Бирхаузер, 1987.
[A10] « О вычислении многомерных многообразий решений параметризованных уравнений », WC Rheinboldt, Numerishe Mathematik, 53, 1988, страницы 165-181.
[A11] « О симплициальной аппроксимации неявно определенных двумерных многообразий », М.Л. Бродзик и В.К. Райнбольдт, «Вычислительная техника и математика с приложениями», 28 (9): 9-21, 1994.
[A12] " Вычисление симплициальных приближений неявно определенных p-многообразий ", М.Л. Бродзик, Вычислительная техника и математика с приложениями, 36 (6): 93-113, 1998.
[A13] « Новый алгоритм двумерного численного продолжения », Р. Мелвилл и Д.С. Макки, «Компьютеры и математика с приложениями», 30 (1): 31-46, 1995.
[A14] « Многопараметрическое продолжение: вычисление неявно определенных k-многообразий », ME Henderson, IJBC 12 [3]: 451-76, 2003.
[A15] « MANPACK: набор алгоритмов для вычислений на неявно определенных многообразиях », WC Rheinboldt, Comput. Математика. Applic. 27 страниц 15–9, 1996.
[A16] « CANDYS / QA - программная система для качественного анализа нелинейных динамических систем », У. Фейдел и У. Янсен, Int. J. Бифуркация и хаос, т. 2 шт. 4. С. 773–794, World Scientific, 1992.