Точность численного интегрирования падает с уменьшением разб

[Kevsh]

Почему точность численного интегрирования падает, если уменьшать разбиение отрезка интегрирования? Я не говорю про случаи, когда разбиение становится меньше машинного эпсилона, тут понятно, в чём проблема. Допустим, возьмём формулу Ньютона-Котеса 6-го порядка – ну вот разделил я свой отрезок сначала на 100, потом на 1000 и т.д. – если отрезок относительно небольшой, то очень быстро точность численного интегрирования будет сопоставима с величиной машинного эпсилона. При дальнейших попытках разбить отрезок на более мелкие части погрешность будет только расти. Как так?

[slavav]

Какая оценка ошибки для формулы шестого порядка?

[TOTAL]

Kevsh в сообщении #1553779 писал(а):

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

$1+\varepsilon=1$
Учтите, что для компьютера это равенство верно, даже если $\varepsilon$ гораздо больше наименьшего машинного числа.

[Pphantom]

Kevsh в сообщении #1553779 писал(а):

Как так?

Название "феномен Рунге" (или "явление Рунге") вам что-нибудь говорит? Если нет - посмотрите.

[demolishka]

Kevsh в сообщении #1553779 писал(а):

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

Потому что с уменьшением шага вычисляете Вы точнее, но ошибаетесь чаще. Поэтому если не соблюдать баланс, то погрешность вырастает. А каков баланс - зависит от задачи, метода и его реализации.

[Kevsh]

demolishka
А феноменом Рунге это можно объяснить? Мол, попали на такой набор узлов, при котором всё это дело начинает колебаться, вот и погрешность появилась. Также интересно, почему некоторые методы численного интегрирования далеко не всегда уменьшают погрешность так, как должны (в соответствии со своим порядком). Допустим, при использовании метода левых прямоугольников, интеграл $\int_0^{\frac{\pi}{2}}xcos^2(x)$ при увеличении количества узлов в 10 раз уменьшает свою погрешность в 100 раз. Это проявляется, допустим, если разбивать функция на $(\frac{\pi}{2}-0)/1000$ и $(\frac{\pi}{2}-0)/10000$ частей. По идее погрешность должна уменьшаться в 10 раз...

[demolishka]

Kevsh в сообщении #1553788 писал(а):

А феноменом Рунге это можно объяснить?

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

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

Kevsh в сообщении #1553788 писал(а):

Также интересно, почему некоторые методы численного интегрирования далеко не всегда уменьшают погрешность так, как должны (в соответствии со своим порядком)

Опять же – потому что там перед порядком идут неэффективные константы, которые могут как испортить, так и улучшить погрешность.

[TOTAL]

Kevsh в сообщении #1553788 писал(а):

Также интересно, почему некоторые методы численного интегрирования далеко не всегда уменьшают погрешность так, как должны (в соответствии со своим порядком). Допустим, при использовании метода левых прямоугольников, интеграл $\int_0^{\frac{\pi}{2}}xcos^2(x)$ при увеличении количества узлов в 10 раз уменьшает свою погрешность в 100 раз. Это проявляется, допустим, если разбивать функция на $(\frac{\pi}{2}-0)/1000$ и $(\frac{\pi}{2}-0)/10000$ частей. По идее погрешность должна уменьшаться в 10 раз...

В общем случае всё происходит в согласии с идеей. Но здесь частный случай. Если составная квадратурная формула имеет порядок $p$ (для левых прямоугольников $p=1$), то при условии на подынтегральную функцию на концах отрезка интегрирования $f^{(p-1)}(a)=f^{(p-1)}(b)$ формула имеет более высокий порядок. Убедитесь в этом, поэкспериментируйте с квадратурными формулами другого порядка.

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

Потому, что у нас два источника ошибок. Один - замена интегрируемой функции приближением, позволяющим его проинтегрировать аналитически (в частности, полиномом). А второй - ошибки вычисления ввиду конечной точности машинной арифметики. Чем меньше шаг - тем лучше приближение и меньше вносимая им ошибка. Но чем меньше шаг, тем больше вычислений, и каждая операция вносит погрешность. В какой-то момент ошибка из-за неточности приближения оказывается настолько малой, что дальнейшее дробление шага повышения точности не даёт, но увеличившееся от дробления число операций увеличивает и ошибку от арифметики.

[Pphantom]

Вообще говоря, это более-менее беспредметный спор, пока Kevsh не покажет, что, собственно, он делал. Мы исходим из того, что все сделано настолько оптимально, насколько возможно, а в реальности скорее следует предполагать обратное.

[TOTAL]

$\dfrac{\sin(\pi/3+h)-\sin(\pi/3)}{h}$
Даже без увеличивающегося числа операций возникнут проблемы.
Уменьшайте $h$, следите, сравнивайте с правильным результатом.
Проблема в количестве правильных разрядов при записи числа в компьютере.

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

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

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

Я бы скорее в феномене Рунге искал объяснение такого эффекта, когда порядок метода растёт, а улучшения нет. А при том же порядке, но уменьшении шага видел бы накопление ошибок, число которых в суммарной ошибке обратно пропорционально величине шага.
Но присоединяюсь к общему: "А из зала мне кричат давай подробности!"

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

Небольшой вычислительный эксперимент.
Выбрана для интегрирования функция $y=x^2$ от нуля до 3. Расчёт делался методом прямоугольников (Rect) и Симпсона (который для данной функции точный)
Для наглядности выбран тип данных float (языка С), то есть 6-7 значащих цифр.
Шаг постепенно уменьшался (втрое каждый раз)
Видно, что для метода прямоугольников ошибка (разность с аналитически полученным значением 9) по мере уменьшения шага падает, но начиная с какого-то значения начинает расти.
Для метода Симпсона ошибка нулевая и при большом шаге, но когда шаг уменьшается, накопление ошибок в силу большого числа шагов начинает проявляться, в какой-то момент оба метода близки по погрешности (и она именно вычислительная, а не от низкого порядка метода), а потом погрешность начинает катастрофически расти.

N        h         ErrRect       ErrSimp
0  1.000000000 -4.000000000  0.000000000 
1  0.333333343 -1.444444656  0.000000000 
2  0.111111112 -0.493822098  0.000004768 
3  0.037037037 -0.165981293 -0.000000954 
4  0.012345679 -0.055462837  0.000015259 
5  0.004115226 -0.018441200  0.000065804 
6  0.001371742 -0.005952835  0.000224113 
7  0.000457247 -0.001404762  0.000656128 
8  0.000152416  0.000142097  0.000816345 
9  0.000050805 -0.005940437 -0.005706787 
10  0.000016935 -0.007421494 -0.007340431 
11  0.000005645 -0.005413055 -0.005387306 
12  0.000001882  0.182534218  0.182544708 
13  0.000000627  0.165490150  0.165493965 
14  0.000000209  1.796812057  1.796812057 
15  0.000000070 -1.000000000 -1.000000000 
16  0.000000023 -8.875000000 -8.875000000 
17  0.000000008 -8.984375000 -8.984375000 
18  0.000000003 -8.999755859 -8.999755859 

Взяв более употребительный тип double (14-15 значащих цифр), получил более поздний срыв точности, но эффект тот же.

N        h         ErrRect       ErrSimp
0  1.000000000 -4.000000000  0.000000000 
1  0.333333333 -1.444444444 -0.000000000 
2  0.111111111 -0.493827160  0.000000000 
3  0.037037037 -0.165980796 -0.000000000 
4  0.012345679 -0.055479348  0.000000000 
5  0.004115226 -0.018510051  0.000000000 
6  0.001371742 -0.006171899 -0.000000000 
7  0.000457247 -0.002057509 -0.000000000 
8  0.000152416 -0.000685859  0.000000000 
9  0.000050805 -0.000228622  0.000000000 
10  0.000016935 -0.000076208  0.000000000 
11  0.000005645 -0.000025403  0.000000000 
12  0.000001882 -0.000008468 -0.000000000 
13  0.000000627 -0.000002823 -0.000000000 
14  0.000000209 -0.000000944 -0.000000003 
15  0.000000070 -0.000000316 -0.000000002 
16  0.000000023 -0.000000144 -0.000000040 
17  0.000000008 -0.000000087 -0.000000052 
18  0.000000003  0.000000175  0.000000186  

видим тот же эффект, только отсроченный.

[B@R5uk]

Когда надо проинтегрировать очень точно с мелким разбиением, но в распоряжении только убогий float с одинарной точностью, есть выход! Нужно суммировать деревом: либо деревом в лоб, либо более продвинуто через очередь. Заводите очередь с приоритетом, инициализируете её несколькими первыми слагаемыми. В цикле смотрите на два самых малых слагаемых в очереди. Если они отличаются меньше, чем в 2 раза, то удаляете их из очереди, складываете и результат помещаете назад в очередь. Если два меньших слагаемых различаются больше чем в 2 раза, то вычисляете следующую партию слагаемых и добавляете её в очередь. Когда все слагаемые закончились, то складываете все величины в очереди начиная с меньшей.

Этот поход чем-то напоминает игру 2048. При нём все ошибки округления, возникающие при суммировании и вычислении слагаемых, останутся в младших разрядах мантиссы суммы, а не будут расти из-за сложения несоразмерных величин, как при суммировании в лоб.

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