Оптимальный метод ODE для фиксированного количества оценок RHS

14

На практике время выполнения численного решения IVP x ( t 0 ) = x 0 часто преобладает продолжительность оценки правой части (RHS) f . Поэтому давайте предположим, что все другие операции выполняются мгновенно (т.е. без затрат на вычисления). Если общая среда для решения IVP ограниченато это равносильно томуограничивая число оценок F до некоторого N N .

x˙(t)=f(t,x(t)) for t[t0,t1]
x(t0)=x0
ffNN

Нас интересует только конечное значение .x(t1)

Я ищу теоретические и практические результаты, которые помогут мне выбрать лучший метод ODE в такой обстановке.

Если, например, то мы можем решить IVP, используя два явных шага Эйлера ширины ( t 1 - t 0 ) / 2 или один шаг ширины tN=2(t1t0)/2 используя метод средней точки. Мне не сразу понятно, какой из них предпочтительнее. Конечно,для больших N можно также подумать о многошаговых методах, итерированных схемах Рунге-Кутты и т. Д.t1t0N

То , что я ищу являются результаты , похожие на те , которые существуют, например, для квадратурных правил: Мы можем выбрать веса { ш I } и связанных с ними точек { х я } такие , что квадратурная правило Σ п я = 1 ш I g ( x i ) является точным для всех многочленов g таких, что d e gn{wi}{xi}i=1nwig(xi)g .deg(g)2n1

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

РЕДАКТИРОВАТЬ: некоторая справочная информация: это для жестких приложений реального времени, то есть результат должен быть доступен до известного срока. Отсюда ограничение количества оценок RHS N как доминирующего фактора затрат. Обычно наши проблемы жесткие и сравнительно небольшие.x(t1)N

РЕДАКТИРОВАТЬ 2: К сожалению, у меня нет точных требований к времени, но можно с уверенностью предположить, что будет довольно маленьким (определенно <100, вероятно, ближе к 10). Учитывая требования в реальном времени, мы должны найти компромисс между точностью моделей (с лучшими моделями, приводящими к более длинному времени выполнения RHS и, следовательно, к более низкомуN ) и точностью метода ODE (с лучшими методами, требующими более высокого уровня). значения N ).NN

Флориан Брукер
источник
Обычное соответствие методов Рунге-Кутты с фиксированным шагом методам Ньютона-Коута применимо к случаю применения метода РК к IVP ; Например, применение классического метода четвертого порядка к этому IVP эквивалентно выполнению правила Симпсона для f ( x ) . y=f(x)f(x)
JM
@JM: я знаю об этом. Я намеревался использовать квадратурные правила только в качестве примера характеристики точности численного метода для определенного набора входных данных, когда число оценок функций ограничено. Кроме того, меня интересуют «настоящие» ODE, то есть те, которые не сводятся к стандартной интеграции.
Флориан Брукер
1
Это становится все интереснее. Теперь число само по себе ничего не значит. Что может быть полезно, так это узнать λ N / T , где T - длина интервала интегрирования, а λ - постоянная Липшица от f по x . Это скажет нам, насколько серьезная проблема на самом деле. Предполагая, что это жестко, вероятным кандидатом является метод BDF 2-го порядка. NλN/TTλfx
Дэвид Кетчон
@DavidKetcheson: меня больше интересует общий подход к выбору подходящего метода для данной проблемы, а не оптимальный метод для конкретной проблемы. У нас есть большее количество моделей, которые сильно различаются по жесткости и срокам.
Флориан Брукер
Вы говорите, что очень дорого оценивать. Вы можете вычислить якобиан вообще? Как насчет некоторого приближения, которое может исправить основную жесткость? Вы не в хорошей форме, если ваша проблема очень жесткая, и у вас нет способа ее исправить. f
Джед Браун

Ответы:

7

Я думаю, что ключевая ссылка для ответа на ваш вопрос - это статья Осии и Шампина . Теперь я приведу некоторые предыстории.

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

S={zC:|P(z)|1}.

Здесь - функция устойчивости метода; см., например, текст Hairer et. и др. Необходимым условием устойчивости является то, что λ h S, где λ пробегает собственные значения якобиана функции f иP(z)λhSλf - размер шага. Это не всегда достаточное условие для нелинейных задач, но обычно это хорошее эмпирическое правило и используется на практике.h

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

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

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

Точность и стабильность эффективности широкого спектра методов могут быть вычислены простым и автоматическим способом с использованием NodePy (отказ от ответственности: NodePy разработан мной).

Дэвид Кетчесон
источник
Спасибо. Статья Осии и Шампина действительно очень интересна. Знаете ли вы похожие результаты для жестких задач? Мне известно, что обычно для этих целей используются неявные методы, но они не имеют априорных ограничений на количество оценок RHS, поэтому в моем случае они бесполезны.
Флориан Брукер
Я не знаю ничего подобного для сложных проблем, но я подозреваю, что что-то существует. Как вы говорите, вопрос более тонкий при использовании неявных методов. Одним из подходов может быть использование методов Розенброка, которые хорошо справляются с жесткими проблемами, но имеют фиксированное количество оценок RHS.
Дэвид Кетчесон
6

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

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

Для нежестких систем:

Существуют ограничения для явных методов Рунге-Кутты, для которых указывается, сколько этапов (оценок RHS) необходимо для достижения определенного порядка точности. После четвертого порядка число этапов превышает порядок точности, и расхождение продолжает расти. Большая книга ODE мясника: http://books.google.com/books/about/Numeric_Methods_for_Ordinary_Different.html?id=opd2NkBmMxsC

делает хорошую работу, объясняя некоторые из этих «несуществующих» доказательств.

Ваш пример квадратурного правила приводит либо к методу многошагового типа, например к Adams-bashforth, либо к так называемым методам спектрально-отложенной коррекции. Для adams-bashforth вам нужна только одна оценка RHS на шаг, но поскольку области стабильности в общем случае для этих методов настолько малы, вы обычно выполняете ту же работу с точки зрения оценок RHS, что и метод Рунге-Кутты с тем же заказ.

Вот статья о спектральной отложенной коррекции:

https://www.google.com/search?q=spectral+deferred+correction&aq=f&oq=spectral+deferred+correction&aqs=chrome.0.57j0l2j62.3336j0&sourceid=chrome&ie=UTF-8

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

Для жестких систем:

Существуют «оптимизированные» временные стимуляторы, но точные теоретические результаты, касающиеся того, насколько хороши они могут быть получены, к сожалению, ограничены некоторыми простыми случаями (и даже те, которые оказались не тривиальной работой). Три стандартных результата говорят, что для методов Рунге-Кутты с этапами: самая отрицательная действительная ось, которую он может включить в область своей стабильности, представляет собой интервал длины 2 S 2 , а самая воображаемая ось, которую он может содержать, - это интервал длины S - 1 , и наибольшая окружность, касающаяся мнимой оси, которую он может содержать, имеет радиус S (все они также взаимоисключающие).S2S2S1S

Reid.Atcheson
источник
2
Может случиться, что использование метода переменного шага (или даже переменного порядка) может быть более эффективным, чем упрямое соблюдение метода фиксированного шага. Можно, например, рассмотреть возможность использования экстраполяционного метода, такого как Bulirsch-Stoer: сделать несколько оценок на некоторых этапах, а затем построить (якобы) более точные оценки из результатов этих этапов.
JM
Правда. На самом деле, многие из оптимальных методов в некотором смысле эквивалентны версии с переменным шагом другого временного степпера. Рунге-Кутта-Чебшев, например, может рассматриваться как прямой Эйлер, применяемый с переменными временными шагами, являющимися чебышевскими точками.
Reid.Atcheson
@JM: Точно. Но есть ли способ судить о точности этих подходов по количеству оценок RHS, кроме численных экспериментов (которые будут очень сложными, учитывая большое количество возможных подходов)?
Флориан Брукер
@ Флориан, не в общем. Я предполагаю, что вы слышали об уравнениях Лоренца?
JM
1
@JM: Да :) Вот почему я упомянул квадратурный пример, где точность измеряется подмножеством (полиномами) исходного проблемного пространства. Я был бы счастлив с результатами, которые работают только для определенного набора проблем.
Флориан Брукер
3

1014f(x)

Конечно, есть исключения (очень большие системы, очень жесткие системы), но в сообществе распространено мнение, что вопрос разработки решателей ODE для «стандартных» систем является решенным. Следовательно, я думаю, что вопрос, который вы задаете, не очень интересен - он затрагивает компонент решения ODE, который больше не имеет значения. Это также может объяснить отсутствие литературы по этому вопросу.

Вольфганг Бангерт
источник
+1. Всякий раз, когда кто-то спрашивает об эффективных средствах решения ODE, я просто предполагаю, что они заинтересованы в огромных системах ODE, возникающих в результате полудискретизации PDE или больших проблем с n-телами.
Дэвид Кетчесон
Не могли бы вы объяснить, как это относится к моему вопросу? Я не вижу связи, так как меня интересует случай, когда оценка f(x)не бесплатная, а настолько дорогая, что количество оценок ограничено.
Флориан Брукер
@DavidKetcheson: это не тот случай, здесь. Скорее, у нас очень строгие требования к времени (жесткие в реальном времени) на слабом оборудовании (встроенные устройства). Сами системы ODE сравнительно невелики.
Флориан Брукер
NNNN
NNN<1000
1

O(dim3)O(dim2)

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

Второй момент: из литературы известно, что решатели, основанные на «дорогих» методах (т.е. явных методах RK), иногда работают быстрее, чем «более дешевые» (явные многошаговые методы).

Подводя итог, я думаю, что вы должны не только учитывать количество оценок RHS.

faleichik
источник
N