Как обосновать правило Рунге для вычисления интеграла?

[andreyka]

В учебниках пишут приближенные равенства.
Например, для формулы третьего порядка точности:
$I-I_{h}\approx ch^3$
$I-I_{h/2}\approx c\left(\frac{h}{2}\right)^3=\frac{1}{8}ch^3$
$I_h-I_{h/2}\approx \frac{7}{8} ch^3$
$ch^3\approx \frac{8}{7}(I_h-I_{h/2})$
$I-I_{h/2}\approx \frac{1}{8} ch^3 = \frac17(I_h-I_{h/2})$
Но ведь на самом деле у нас есть лишь неравенство $|I-I_{h}|\le ch^3$. Как строго обосновать исходя из неравенства?

[worm2]

Строго — думаю, что никак.

[andreyka]

В википедии:
Погрешность вычисления значения интеграла при числе шагов, равном 2n, определяется по формуле Рунге: $\Delta _{2n}\approx \Theta |I_{2n}-I_{n}|$.
Откуда следует ограниченность асимптотически и сверху, и снизу?
Может есть хоть немного более обоснованные рассуждения, чем просто $\approx$ ?

[ewert]

andreyka в сообщении #1421299 писал(а):

Но ведь на самом деле у нас есть лишь неравенство $|I-I_{h}|\le ch^3$. Как строго обосновать исходя из неравенства?

Строго -- никак, разумеется. Хотя есть пусть и эмпирические, но вполне работающие на практике признаки применимости этого правила.

А вот то, что у нас есть лишь неравенства -- это не так. Вот как раз для квадратурных формул известны не только оценки сверху, но и асимптотики типа $I-I_h\sim C\,h^m$. Т.е. строго доказано, что отношение погрешности любой составной квадратурной формулы к соответствующей ей степени шага стремится к некоторой константе.

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

[andreyka]

ewert в сообщении #1421330 писал(а):

andreyka в сообщении #1421299 писал(а):

А вот то, что у нас есть лишь неравенства -- это не так. Вот как раз для квадратурных формул известны не только оценки сверху, но и асимптотики типа $I-I_h\sim C\,h^m$. Т.е. строго доказано, что отношение погрешности любой составной квадратурной формулы к соответствующей ей степени шага стремится к некоторой константе.

Как это доказать, например, для формулы левых прямоугольников?

Оценим погрешность на $i$-ом отрезке:
$\int\limits_{x_i}^{x_{i+1}}f(x)dx-f(x_i)h_i=\int\limits_{x_i}^{x_{i+1}}(f(x)-f(x_i))dx= \\ = \int\limits_{x_i}^{x_{i+1}}f'(\xi_i)(x-x_i)dx=\frac{1}{2}f'(\xi_i)h_i^2, \ \ \xi_i\in[x_i,x_{i+1}]$

На всем интервале:
$\int\limits_{a}^{b}f(x)dx-\sum\limits_{i=0}^{n-1}f(x_i)h_i=\frac{1}{2}\sum\limits_{i=0}^{n-1}f'(\xi_i)h_i^2$

Как из этого доказать асимптотику?

Предположим, что разбиение равномерное $h_i=h$. Тогда погрешность равна $\frac{1}{2}h^2\sum\limits_{i=0}^{n-1}f'(\xi_i)$. Что можно дальше сделать?

-- 20.10.2019, 23:48 --

Быть может $\sum\limits_{i=0}^{n-1}f'(\xi_i)h$ интерпретировать как интегральную сумму?

[ewert]

andreyka в сообщении #1421786 писал(а):

Быть может $\sum\limits_{i=0}^{n-1}f'(\xi_i)h$ интерпретировать как интегральную сумму?

Именно так, именно как интегральную.

Причём что существенно. Подобные оценки погрешности -- лагранжева типа -- есть далеко не для всех квадратурных формул (хотя и для многих). Но они и не обязательны. Достаточно стандартной формулы для погрешности интерполяции: $f(x)-L_n(x)=\frac{f^{(n+1)}\big(\xi(x)\big)}{(n+1)!}\omega_{n+1}(x)$. После формального интегрирования получаем, с одной стороны, погрешность квадратурной формулы на очередном отрезке разбиения. А с другой -- если $f^{(n+1)}$ непрерывна, то её значения на каждом таком отрезке мало отличаются от значения на левом конце (например), и после суммирования по всем отрезкам всё равно получается интегральная сумма для производной.

Вот, в принципе, и всё; правда, там есть ещё нюансы, связанные с фактическим порядком точности квадратурной формулы.

[Евгений Машеров]

Ну, насколько я могу понять, это потому "правило", что строгого обоснования нет. А то была бы теорема. А нестрогое мне видится в том, что если формула точна для многочлена n-ной степени, то делается допущение, что то, что формула "не видит" есть одночлен n+1 степени $Cx^{n+1}$, а не $\Sigma_{i=n+1}^\infty C_i x^i$.

[TOTAL]

Евгений Машеров в сообщении #1421949 писал(а):

... если формула точна для многочлена n-ной степени, то ...

Алгебраическая степень точности здесь непосредственно не играет роли. Речь идет о составной квадратурной формуле и её фактическом порядке точности, т.е. числе $p$ в главном члене погрешности порядка $O(h^p)$.

[ewert]

Евгений Машеров в сообщении #1421949 писал(а):

нестрогое мне видится в том, что если формула точна для многочлена n-ной степени, то делается допущение, что то, что формула "не видит" есть одночлен n+1 степени $Cx^{n+1}$

Это не допущение, а точный факт: погрешность составной формулы имеет асимптотику $C\,h^{n+1}$, где $C\neq0$, тогда и только тогда, когда эта формула верна для всех многочленов степени не выше $n$, но не точна для многочленов степени $(n+1)$. (Естественно, $C\neq0$ для функций общего вида; для каких-то конкретных функций эта константа может оказаться и нулевой.) При этом порядок точности $(n+1)$ в любом случае не меньше, чем количество используемых (в простой формуле) узлов и не больше, чем удвоенное количество узлов.

[Евгений Машеров]

Точный факт - асимптотика, а допущение - что асимптотическое выражение при конечных h принимается за точное.

[TOTAL]

Можно писать не асимптотику, а равенство
$I_{h}=I+Ch^3 + O(h^q), \,\, q>3$,
где константа $C$ не зависит от $h$
(а зависит от квадратурной формулы и подынтегральной функции).

Тогда получим
$I - I_{h/2} = (I_{h/2}- I_{h})/7 + O(h^q)$
Тоже не легче из-за $O(h^q)$

[ewert]

Евгений Машеров в сообщении #1422067 писал(а):

допущение - что асимптотическое выражение при конечных h принимается за точное.

Ну всё-таки не точное, а приближённое. Т.е. точный значок "$\sim$" волевым решением заменяется на "$\approx$". И обосновать такую замену формально, естественно, невозможно. Но вот эмпирически -- можно вполне. Надо просто отслеживать разницы не только для двух, а для трёх или более соседних приближений. Отношение $\frac{I_{2h}-I_h}{I_h-I_{h/2}}$ стремится к $2^m$, где $m$ -- фактический порядок точности. И если устойчиво наблюдается, например, $\left|\frac{I_{2h}-I_h}{2^m(I_h-I_{h/2})}-1\right|<0.1$, то применение правила Рунге можно считать практически обоснованным.

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

-- Чт окт 24, 2019 16:10:57 --

TOTAL в сообщении #1422071 писал(а):

Можно писать не асимптотику, а равенство
$I_{h}=I+Ch^3 + O(h^q), \,\, q>3$,
где константа $C$ не зависит от $h$

Это вообще-то ровно и называется асимптотикой.