Ошибка усечения (численное интегрирование)

Ошибки, возникающие при численном интегрировании

Ошибки усечения при численном интегрировании бывают двух видов:

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

Определения

Предположим, что у нас есть непрерывное дифференциальное уравнение

${\displaystyle y'=f(t,y),\qquad y(t_{0})=y_{0},\qquad t\geq t_{0}}$

и мы хотим вычислить приближение истинного решения на дискретных временных шагах . Для простоты предположим, что временные шаги равномерно распределены: ${\displaystyle y_{n}}$ ${\displaystyle y(t_{n})}$ ${\displaystyle t_{1},t_{2},\ldots ,t_{N}}$

${\displaystyle h=t_{n}-t_{n-1},\qquad n=1,2,\ldots ,N.}$

Предположим, мы вычисляем последовательность с помощью одношагового метода вида ${\displaystyle y_{n}}$

${\displaystyle y_{n}=y_{n-1}+hA(t_{n-1},y_{n-1},h,f).}$

Функция называется функцией приращения и может быть интерпретирована как оценка наклона . ${\displaystyle A}$ ${\displaystyle {\frac {y(t_{n})-y(t_{n-1})}{h}}}$

Локальная ошибка усечения

Локальная ошибка усечения — это ошибка, которую наша функция приращения, вызывает в течение одной итерации, предполагая идеальное знание истинного решения на предыдущей итерации. ${\displaystyle \tau _{n}}$ ${\displaystyle A}$

Более формально, локальная ошибка усечения, на шаге вычисляется из разницы между левой и правой частью уравнения для приращения : ${\displaystyle \tau _{n}}$ ${\displaystyle n}$ ${\displaystyle y_{n}\approx y_{n-1}+hA(t_{n-1},y_{n-1},h,f)}$

${\displaystyle \tau _{n}=y(t_{n})-y(t_{n-1})-hA(t_{n-1},y(t_{n-1}),h,f).}$^{[1] [2]}

Численный метод является последовательным, если локальная ошибка усечения равна (это означает, что для каждого существует такое , что для всех ; см. обозначение little-o ). Если функция приращения непрерывна, то метод является последовательным, если и только если . ^[3] ${\displaystyle o(h)}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle H}$ ${\displaystyle |\tau _{n}|<\varepsilon h}$ ${\displaystyle h<H}$ ${\displaystyle A}$ ${\displaystyle A(t,y,0,f)=f(t,y)}$

Кроме того, мы говорим, что численный метод имеет порядок ${\displaystyle p}$ , если для любого достаточно гладкого решения задачи начального значения локальная ошибка усечения равна (это означает, что существуют константы и такие, что для всех ). ^[4] ${\displaystyle O(h^{p+1})}$ ${\displaystyle C}$ ${\displaystyle H}$ ${\displaystyle |\tau _{n}|<Ch^{p+1}}$ ${\displaystyle h<H}$

Глобальная ошибка усечения

Глобальная ошибка усечения представляет собой накопление локальной ошибки усечения по всем итерациям, предполагая идеальное знание истинного решения на начальном временном шаге. ^{[ необходима ссылка ]}

Более формально глобальная ошибка усечения, , в момент времени определяется как: ${\displaystyle e_{n}}$ ${\displaystyle t_{n}}$

${\displaystyle {\begin{aligned}e_{n}&=y(t_{n})-y_{n}\\&=y(t_{n})-{\Big (}y_{0}+hA(t_{0},y_{0},h,f)+hA(t_{1},y_{1},h,f)+\cdots +hA(t_{n-1},y_{n-1},h,f){\Big )}.\end{aligned}}}$^[5]

Численный метод является сходящимся , если глобальная ошибка усечения стремится к нулю при стремлении размера шага к нулю; другими словами, численное решение сходится к точному решению: . ^[6] ${\displaystyle \lim _{h\to 0}\max _{n}|e_{n}|=0}$

Связь между локальными и глобальными ошибками усечения

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

Глобальная ошибка усечения удовлетворяет рекуррентному соотношению:

${\displaystyle e_{n+1}=e_{n}+h{\Big (}A(t_{n},y(t_{n}),h,f)-A(t_{n},y_{n},h,f){\Big )}+\tau _{n+1}.}$

Это следует непосредственно из определений. Теперь предположим, что функция приращения является непрерывной по Липшицу по второму аргументу, то есть существует константа такая, что для всех и и , имеем: ${\displaystyle L}$ ${\displaystyle t}$ ${\displaystyle y_{1}}$ ${\displaystyle y_{2}}$

${\displaystyle |A(t,y_{1},h,f)-A(t,y_{2},h,f)|\leq L|y_{1}-y_{2}|.}$

Тогда глобальная ошибка удовлетворяет границе

${\displaystyle |e_{n}|\leq {\frac {\max _{j}\tau _{j}}{hL}}\left(\mathrm {e} ^{L(t_{n}-t_{0})}-1\right).}$^[7]

Из приведенной выше оценки глобальной ошибки следует, что если функция в дифференциальном уравнении непрерывна по первому аргументу и липшицева по второму аргументу (условие из теоремы Пикара–Линделёфа ), а функция приращения непрерывна по всем аргументам и липшицева по второму аргументу, то глобальная ошибка стремится к нулю по мере того, как размер шага приближается к нулю (другими словами, численный метод сходится к точному решению). ^[8] ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle h}$

Расширение до линейных многошаговых методов

Теперь рассмотрим линейный многошаговый метод , заданный формулой

${\displaystyle {\begin{aligned}&y_{n+s}+a_{s-1}y_{n+s-1}+a_{s-2}y_{n+s-2}+\cdots +a_{0}y_{n}\\&\qquad {}=h{\bigl (}b_{s}f(t_{n+s},y_{n+s})+b_{s-1}f(t_{n+s-1},y_{n+s-1})+\cdots +b_{0}f(t_{n},y_{n}){\bigr )},\end{aligned}}}$

Таким образом, следующее значение для численного решения вычисляется согласно

${\displaystyle y_{n+s}=-\sum _{k=0}^{s-1}a_{k}y_{n+k}+h\sum _{k=0}^{s}b_{k}f(t_{n+k},y_{n+k}).}$

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

${\displaystyle \tau _{n}=y(t_{n+s})+\sum _{k=0}^{s-1}a_{k}y(t_{n+k})-h\sum _{k=0}^{s}b_{k}f(t_{n+k},y(t_{n+k})).}$^[9]

Опять же, метод является последовательным, если и имеет порядок p, если . Определение глобальной ошибки усечения также не изменилось. ${\displaystyle \tau _{n}=o(h)}$ ${\displaystyle \tau _{n}=O(h^{p+1})}$

Связь между локальными и глобальными ошибками усечения немного отличается от более простой настройки одношаговых методов. Для линейных многошаговых методов требуется дополнительная концепция, называемая нулевой устойчивостью, чтобы объяснить связь между локальными и глобальными ошибками усечения. Линейные многошаговые методы, которые удовлетворяют условию нулевой устойчивости, имеют ту же связь между локальными и глобальными ошибками, что и одношаговые методы. Другими словами, если линейный многошаговый метод нулевой устойчивости и последователен, то он сходится. А если линейный многошаговый метод нулевой устойчивости и имеет локальную ошибку , то его глобальная ошибка удовлетворяет . ^[10] ${\displaystyle \tau _{n}=O(h^{p+1})}$ ${\displaystyle e_{n}=O(h^{p})}$

Смотрите также

• Порядок точности
• Численное интегрирование
• Численные обыкновенные дифференциальные уравнения
• Ошибка усечения

Примечания

1. Gupta, GK; Sacks-Davis, R.; Tischer, PE (март 1985). «Обзор последних разработок в решении ОДУ». Computing Surveys . 17 (1): 5–47. CiteSeerX  10.1.1.85.783 . doi :10.1145/4078.4079.
2. Süli & Mayers 2003, стр. 317, называет ошибку усечения. ${\displaystyle \tau _{n}/h}$
3. Сюли и Майерс 2003, стр. 321 и 322.
4. Изерлес 1996, с. 8; Сюли и Майерс 2003, с. 323
5. Süli & Mayers 2003, стр. 317
6. Исерлес 1996, стр. 5
7. Süli & Mayers 2003, стр. 318
8. Süli & Mayers 2003, стр. 322
9. Süli & Mayers 2003, стр. 337, использует другое определение, разделив его по существу на h
10. Süli & Mayers 2003, стр. 340

Ссылки

• Исерлес, Арье (1996), Первый курс численного анализа дифференциальных уравнений , Cambridge University Press , ISBN 978-0-521-55655-2.
• Сюли, Эндре; Майерс, Дэвид (2003), Введение в численный анализ , Cambridge University Press , ISBN 0521007941.

Внешние ссылки

• Заметки об ошибках усечения и методах Рунге-Кутты ^{[ мертвая ссылка ]}
• Ошибка усечения метода Эйлера ^{[ мертвая ссылка ]}