Численное решение ОДУ. Методы высоких порядков

[photon]

Не видал ли где на свете ты царицы молодой кто-то выписаные в явном виде выражения для методов, аналогичных Рунге-Кутта, но порядка 7-10? Я максимум встречал 5-6.

[AD]

Вот вёл у нас ЧМы такой персонаж, доц. Григорьев Илья Сергеевич, утверждал, что на практике пользуется восьмым порядком и выше. Всем своим видом показывал, что крутъ, говорят, какое-то международное соревнование выигрывал по численной оптимизации, или как бы это назвать, с командой, естественно. В принципе, я могу мыло даже попытаться раскопать, только здесь постить не буду, не честно это с моей стороны будет. А ссылок чего-то на него не нахожу.

(Оффтоп)

photon в сообщении #281394 писал(а):

Не видал ли где на свете кто-то

Да
Каков вопрос - таков и ответ ^_^

[Zai]

поиск по ключевым словам "численное интегрирование уравнений движения планет" дает ссылку на автореферат, где есть обзор алгоритмов "типа Адамса-Мултона-Коуэлла до 16 порядка"
http://home.samgtu.ru/~pmi/aspir/diss/a ... ynbaev.pdf

[Ajabsandal]

photon в сообщении #281394 писал(а):

Не видал ли где на свете ты царицы молодой кто-то выписаные в явном виде выражения для методов, аналогичных Рунге-Кутта, но порядка 7-10? Я максимум встречал 5-6.

У Гира в его книге: C. W. Gear: Numerical Initial Problems in Ordinary Differential Equations,
Prentice Hall, 1971. Там, кстати, есть и текст его программы.
приводятся формулы для произвольного порядка. Правда это LMM методы, а не Рунге-Кутты.
В статье И.В. Олемской в жур. "Вычислительные технологии" том 9,  №2, 2004 г. приводятся формулы и для Р-К произвольного порядка, в т.ч. и для вложенных методов Р-К.
Интересно отметить, что эксперименты с методами высокого порядка с автоматическим выбором шага и порядка практически не "вылезают" на порядок, больший 3-х. Сомневающиеся могут сами поэкспериментировать с той же программой из книги Гира. А для жестких систем вообще порядок ограничен 6-ю.
Для повышения порядка надо использовать смещение в формуле дифференцирования назад (Modern Numerical Methods for Ordinary Differential Equations - Hardcover (Oct 7, 1976) by G. Hall and J.M. Watt).
Но это потребует дополнительных вычислений, т. к. схема то неявная, да еще и временных слоев больше 2-х.
Конечно нужны эксперименты с такими схемами для ОДУ чтобы почувствовать их преимущество.
Так что методы порядка выше 6 никто в практике и не применяет - овчинка выделки не стоит.

[AlexNew]

Насколько мне известно, все методы выше второго порядка явлюятся численно-нестабильными (если правильно помню не A-стабильными).
Данный вопрос рассмотрел Dahlquist (статья 1963г), называется этат результат second Dahlquist barrier. Именно после появление этой статьи остановилась погоня за методами все болeе и более высоких порядков.
(все неявные методы являются нестабильными - это первый Dahlquist барьер)
На практике имеет смысл ограничится трапецойдным методом (второй порядок) и где нужно уменьшать шаг.

[Ajabsandal]

AlexNew в сообщении #287518 писал(а):

Насколько мне известно, все методы выше второго порядка явлюятся численно-нестабильными (если правильно помню не A-стабильными).
Данный вопрос рассмотрел Dahlquist (статья 1963г), называется этат результат second Dahlquist barrier. Именно после появление этой статьи остановилась погоня за методами все болeе и более высоких порядков.
(все неявные методы являются нестабильными - это первый Dahlquist барьер)
На практике имеет смысл ограничится трапецойдным методом (второй порядок) и где нужно уменьшать шаг.

Так Гир его и опроверг в своей книге, на которую я ссылаюсь. Это он ввел понятие жесткой устойчивости. Для неявнго метода Гира максимальный порядок - 6. Потом это подтвердили и для BDF-метода. А Клиппинджейр показал что если применять смещение в численной формуле представления производной, то порядок можно поднимать и выше 6-ти.

[AlexNew]

Ajabsandal Спасибо, книжку нашел, если кому надо пишите в личку.

[AlexNew]

Gear C.W. Numerical Initial Value Problems in Ordinary Differential Equations (PH, 1971)(0136266061).pdf

http://ifolder.ru/16666970

[Ajabsandal]

AlexNew в сообщении #296859 писал(а):

Gear C.W. Numerical Initial Value Problems in Ordinary Differential Equations (PH, 1971)(0136266061).pdf

http://ifolder.ru/16666970

Сервис iFolder приостановлен следователями 3-й ЧС ГСУ при ГУВД Москвы.
Сегодня, 17.03.2010 в помещении дата-центра, находящегося по адресу 2-ая ул. Энтузиастов д. 5, появились следователи из 3-й ЧС ГСУ при ГУВД Москвы. Они предъявили протокол о необходимости проведения оперативно-розыскных мероприятий с целью поиска улик, размещенных на сайте iFolder.ru

Администрация сервиса предложила сотрудникам оказать максимальное содействие в поиске и получении нужной информации, а также в установлении личности пользователя, который ее разместил. Однако сотрудники милиции отказались от любой помощи и попытались вывезти ВСЕ оборудование Агавы, размещенное в этом дата-центре, для проведения собственной экспертизы. В результате переговоров вывоз оборудования удалось предотвратить, но, к сожалению, в качестве «альтернативы» сотрудники МВД выключили и опечатали все сервера проекта iFolder, а также и другие сервера компании, не имеющие никакого отношения к проекту.

Компания Агава считает произошедшее беспрецедентным событием, которое ставит под угрозу и сомнение факт существования и развития любого бизнеса в Рунете. Мы намерены бороться и отстаивать интересы сервиса и его клиентов, а также заранее благодарим клиентов за информационную или любую другую помощь в этом деле.

[kotoba]

photon

Цитата:

методов, аналогичных Рунге-Кутта, но порядка 7-10?

Конечно, поздновато, но вдруг кто еще искать будет.
На странице Эрнста Хайрера
http://www.unige.ch/~hairer/software.html
лежат готовые программы решения систем ОДУ методом порядка 8.
Это реализации Dormand-Prince 8(5,3), явного метода
класса Рунге-Кутты восьмого порядка с формулами оценки
погрешности порядков 5 и 3 и плотным выводом порядка 7.
Ключевое слово - DOP853, есть вариант и для Си, и для Фортрана.
Табличку восстановить по тексту несложно.

Подробное изложение построения этого метода можно найти в
E. Hairer, S.P. Nørsett, G. Wanner. Solving Ordinary Differential
Equations I: nonstiff problems. Springer-Verlag, Berlin, 2008
Сейчас посмотрел, в Колхозе только русский перевод первого
издания 1987 года, там этого метода еще нет.
Издание 2008 года у меня откуда-то появилось, но источника
уже не помню.
Зато в первом издании есть программа на Фортране для метода
Dormand-Prince 7(8) из статьи P.J. Prince and J.R. Dormand,
High Order Embedded Runge-Kutta Formulae ,
J. Comp. Appl. Math.,7, pp. 67-75, 1981.
Этот же метод реализован в пакете RKSUITE:
http://www.netlib.org/ode/rksuite/rksuite.f
Ключевое слово - "METHD = 3"

AlexNew

Цитата:

все неявные методы являются нестабильными - это первый Dahlquist барьер

Я сейчас читаю книгу
http://www.comlab.ox.ac.uk/nick.trefethen/pdetext.html
(она не издана и доступна на сайте автора бесплатно),
это как раз руководство по"линейной" теории численных методов
решения ODE/PDE.
Так вот, по горячим следам: все неявные многошаговые методы
порядка $\ge$ 2 и все явные многошаговые
методы не обладают А-устойчивостью.

Методы Рунге-Кутты хороши в том числе и тем, что на них этот
барьер не распространяется.

[Ajabsandal]

kotoba писал(а):

Я сейчас читаю книгу
http://www.comlab.ox.ac.uk/nick.trefethen/pdetext.html
(она не издана и доступна на сайте автора бесплатно),
это как раз руководство по"линейной" теории численных методов
решения ODE/PDE.
Так вот, по горячим следам: все неявные многошаговые методы
порядка $\ge$ 2 и все явные многошаговые
методы не обладают А-устойчивостью.

Методы Рунге-Кутты хороши в том числе и тем, что на них этот
барьер не распространяется.

Читайте и другие книги, где написано, какие барьеры распространяются на РК. Обмануть природу не получиться!
Кроме того методами Адамса - (Башфорта или Мултона) практически никто и не пользуется. Рабочие лошадки - Гир или BDF.
Еще посмотрите Нелинейные Многошаговые методы (NLMM).

[AlexNew]

залил
Gear, Numerical Initial Value Problems in Ordinary Differential Equations, сюда
http://www.scribd.com/doc/28941688/Numerical-Initial-Value-Problems-in-Ordinary-Differential-Equations

(Оффтоп)

на scribd.com очень много хороших новых книг.
может кто знает как сделать доступными книги через poiskknig.ru у меня есть много чего интерестного

[olewa]

photon в сообщении #281394 писал(а):

Не видал ли где на свете ты царицы молодой кто-то выписаные в явном виде выражения для методов, аналогичных Рунге-Кутта, но порядка 7-10? Я максимум встречал 5-6.

Метод получения коэффициентов для любого порядка разработал Джон Батчер - так называемый метод деревьев (J. C. Butcher, Rooted Tree Analysis). Но этот алгоритм требует больших вычислительный затрат. В уже упомянутой книге Хайрера в издании 1990 года есть коэффициенты для 8-го порядка, но там ошибка. Может в последующих изданиях ее исправили. Коэффициенты для 10-го и выше порядка вроде бы никто официально не публиковал.
В принципе, применение методов РК высоких порядков не очень разумно, потому что стадии растут слишком быстро - при 8 порядке правая часть вычисляется раз 15, при десятом точно не скажу, но думаю раз 50.

[gerik]

Приветствую.
Вопрос по алгоритму Дормана-Принса 5(4).

В упомянутой книжке E. Hairer, S.P. Nørsett, G. Wanner. Solving Ordinary Differential
Equations I: nonstiff problems. 1990 года:

Цитата:

Возникает естественный вопрос: а почему бы не использовать лучшее из полученных значений, т.е. выражение старшего порядка $\hat y_1$? ...

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

По правилам русского языка, отсюда можно заключить, что в качестве приближения решения будет выбрано значение $\hat y_1$. НО! Я посмотрел исходные тексты, ссылки на которые тут привели, там берётся значение$y_1$, к тому же, коэффициенты для $\hat y_1$(!), данные в книжке в таблице 4.6 не совпадают с оными в приложении самой книги (!) и в исходных текстах по ссылкам.

Более того, формулы для непрерывного продолжения алгоритма тоже основаны на том же значении.

Может я не понял чего? Ткните пальцем.
А может кто разбирался и нашёл ошибку/опечатку? Я пока запутался, прошу помощи.

[sludge addict]

Цитата:

Не видал ли где на свете ты царицы молодой кто-то выписаные в явном виде выражения для методов, аналогичных Рунге-Кутта, но порядка 7-10? Я максимум встречал 5-6.

Бордовицына Т.В. "Современные численные методы в задачах небесной механики" (1984). Насколько помню, там рассматриваются методы Рунге-Куттa до 10-го порядка а также другие методы высоких порядков