Численные методы. Оценка погрешности метода Симпсона.

[svloyso]

Добрый день.
Мне необходимо запрограммировать вычисление определенного интеграла методом Симпсона. Возник вопрос с выбором шага при заданном $\varepsilon$.
В курсе на Интуите предложен алгоритм, который сравнивает значения интеграла, вычисленные с шагом $h$ и $\frac{h}2$. И дробит шаг до тех пор, пока разница этих интегралов не станет меньше $\varepsilon$.
Но в таком случае может возникнуть такая ситуация на неком промежутке:


То есть, когда функция в точках $0, \frac{h}4, \frac{h}2, \frac{3h}4, h $ будет принимать такие значения, по которым метод Симпсона построит аналогичную параболу как в случае с шагом $h$, так в случае с шагом $\frac{h}2$. В таком случае их разница будет меньше $\varepsilon$ и вычисления прекратятся, но интеграл останется вычисленным с недопустимой погрешностью.
Такие случаи как-нибудь можно предусмотреть или избежать, или это неустранимый недостаток этого метода?

[AlexValk]

"Это неустранимый недостаток метода". . Более того - это общий недостаток всех (с небольшими оговорками) методов численного интегрирования.
Все "детерминированные" методы численного интегрирования можно обмануть, подсунув им две отличающиеся вне узлов интегрирования функции, но в самих узлах, совпадающие между собой. Правда, чтобы построить такие контрпримеры надо знать положение узлов интегрирования, с которыми работает данный метод.
Некоторым исключением являться метод Монте-Карло, который работает со случайными узлами. Но и тут, если знать алгоритм генерации случайных чисел (и он не привязан к моменту запуска, сигнатуре железа компьютера и т.п.), то и его можно гарантировано обмануть.

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

[svloyso]

Благодарю Вас, AlexValk за подробный ответ. Я уж думал, не дождусь :)

[mserg]

Так, к слову. Для достижения «гарантированной» точности можно использовать интервальную арифметику. Она позволяет на интервале оценивать верхнюю и нижнюю границу функции. Оценив на интервале интегрирования границы функции, можно прикинут интервал, в который попадает «площадь». Если точность неудовлетворительна, интервал можно поделить пополам и оценить «площадь» уже на более коротких интервалах. Если точность опять недостаточна, то нужно поделить интервал с наибольшей погрешностью "площади". И т.д., пока не будет достигнута необходимая точность, или пока не лопнет терпение, или пока погрешность из-за большого числа интервалов не начнет ухудшать точность. Таким образом, метод сам дробит интервал на неравные кусочки там где надо.
Более высокую сходимость может дать еще и наличие производной. Ее также можно оценивать на интервале, а через нее (если подумать) и площадь.

Это, конечно, не панацея, но мощный и надежный по части точности результатов инструмент.