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

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

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

Определения

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

${\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]

Численный метод последовательный если локальная ошибка усечения ${\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)}$.^[3]

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

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

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

Более формально, глобальная ошибка усечения, ${\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]

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

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

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

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

${\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]

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

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

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

${\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]

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

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

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

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

Заметки

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

использованная литература

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

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

• Примечания к ошибкам усечения и методам Рунге-Кутта
• Ошибка усечения метода Эйлера