Численные методы. Выпуск IV. Интегралы от быстроосциллирующих функций. Многомерные интегралы

Министерство образования Российской Федерации РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

С.С.Михалкович, А.В.Олифер, А.М.Столяр

ЧИСЛЕННЫЕ МЕТОДЫ Выпуск IV Интегралы от быстро осциллирующих функций. Многомерные интегралы

Методические указания к выполнению индивидуальных заданий на ЭВМ для студентов 2 курса физического факультета

Ростов-на-Дону 2000

Введение В данных указаниях рассматриваются методы приближенного вычисления интегралов от быстро осциллирующих функций и многомерных интегралов. Умение вычислять такие интегралы оказывается принципиально важным для решения некоторых задач радиофизики и ядерной физики соответственно, а также и в других областях. Вычисление интегралов рассматриваемых типов не всегда удается осуществить с помощью готовых процедур, предлагаемых вычислительными пакетами типа Мaple, Мathcad и т.п. Когда же это оказывается возможным, то всегда существует некоторый риск того, что полученный ответ неверен. В такой ситуации большую роль играет глубокое понимание сути численных методов, используемых в стандартных процедурах, и способность, при необходимости, самостоятельно запрограммировать нужный метод. На развитие такого уровня понимания как раз и нацелены описанные ниже практические задания и рекомендации по их решению Общие замечания по поводу составления и тестирования программ для выполнения заданий смотри во Введении к [2].

1. Приближенное интегрирование быстро осциллирующих функций. Формула Филона 1.1. Задание 1) Написать процедуру, реализующую составную квадратурную формулу Филона приближенного интегрирования быстро осциллирующих функций. С помощью этой процедуры найти значение интеграла с точностью не менее 0.01% cогласно правилу Рунге. Зафиксировать N - число подынтервалов, потребовавшихся для достижения заданной точности.

4 2) Применить для вычисления того же самого интеграла составную формулу Симпсона с

N

подынтервалами.

3) Найти приближенное значение интеграла с помощью пакета Maple и определить, насколько от него отличаются значения, найденные в пунктах 1 и 2.

Тестовый пример: 1

∫x e

2 i10 x

dx = cos(10) 25 + 49 sin(10) 250 ≈ −01401909989 . .

−1

Рекомендуемая литература: [3], гл.3, §7.

1.2. О методе Квадратурная формула Филона применяется для приближенного вычисления интегралов вида b

∫ f (x ) ex p(iωx )dx ,

(1)

a

где

выделены относительно медленно меняющийся на интервале [a,b]

множитель f ( x ) и быстро осциллирующий на [a,b] множитель ex p(iωx ) . Последнее

условие

формально

записывается

следующим

образом:

ω(b − a) >> 1 . Функция f ( x ) предполагается гладкой. Заметим, что часто интеграл от быстро осциллирующей функции можно преобразовать к виду (1) с помощью той или иной замены переменной интегрирования.

5 Вывод формулы Филона аналогичен выводу квадратурных формул Ньютона-Котеса. Поскольку функция f ( x ) гладкая, то на [a,b] она приближается с известной погрешностью интерполяционным многочленом. Пусть для определенности это интерполяционный многочлен в форме Лагранжа

( ) f (x 2 ) + P3 (x ) f (x 3 ) ,

L 3 ( x ) = P1 ( x ) f ( x 1 ) + P2 x

построенный по узлам x 1 = a , x 2 = (a + b) 2 , x 3 = b . Как обычно, Pi ( x ) ,

i = 12 , ,3 , суть многочлены второй степени не зависящие от функции f ,

( )

( )

Pi x j = 1 , если i = j , и Pi x j = 0 иначе. В силу того, что f ( x ) ≈ L 3 ( x ) b

b

∫ f (x ) ex p(iωx )dx ≈ ∫ L (x ) ex p(iωx )dx = 3

a

a

3

∑

b− a ⎧ a + b⎫ = ex p⎨iω ⎬ 2 2 ⎭ ⎩

j =1

⎛ b − a⎞ D j ⎜ω ⎟f xj . ⎝ 2 ⎠

( )

(2)

Интеграл от произведения многочлена L 3 ( x ) на функцию ex p(iωx ) вычислен в явном виде. Он представляет собой линейную комбинацию значений функции f ( x ) в точках x 1 , x 2 , x 3 с коэффициентами, не зависящими от функции f ( x ) . Это и есть формула Филона. Аналогично выводятся формулы более высокого порядка. Оценка погрешности формулы Филона R ( f ) полностью определяется погрешностью интерполяции функции f ( x ) многочленом L3 ( x ) и совпадает с оценкой погрешности квадратурной формулы Симпсона для интеграла лишь от одной функции f ( x ) , без быстро осциллирующего множителя:

6 b

R( f ) =

b

∫ ( f (x ) − L (x )) ex p(iωx )dx ≤ ∫ f (x ) − L (x ) dx ≤ 3

3

a

a

(b − a) . 4 ≤ max f ( ) ( x ) 2880 [ a ,b] 5

Составная квадратурная формула Филона строится так же, как и составная квадратурная формула Симпсона: исходный интервал разбивается на подынтервалы, на каждом из которых применяется формула (2). Итоговая расчетная формула, однако, несколько сложнее, чем в случае метода Симпсона. Это связано, в частности, с тем, что множитель ex p(i ⋅ (a + b)) / 2) для каждого подынтервала свой.

1.3. Расчетные формулы В формуле (2) коэффициенты

[

(

) (

)]

) (

)]

D1 ( p) = p−3 2 p cos( p) − sin( p) 2 − p2 + i p2 cos( p) − p sin( p) ,

[

]

D2 ( p) = p−3 4 sin( p) − 4 p cos( p) ,

[

(

D3 ( p) = p−3 2 p cos( p) + sin( p) p2 − 2 + i p sin( p) − p2 cos( p) .

Для

приближенного

интегрирования

функций

вида

f ( x ) cos(ωx )

( f ( x ) sin(ωx ) ) с вещественной функцией f ( x ) , очевидно, следует использовать вещественную (мнимую) части формулы (2). Например,

7 b

∫ a

⎡ b − a ⎢ ⎛ a + b⎞ f ( x ) cos(ωx )dx ≈= cos⎜ ω ⎟⋅ 2 ⎢ ⎝ 2 ⎠ ⎣

⎛ a + b⎞ − sin⎜ ω ⎟⋅ ⎝ 2 ⎠

3

∑ j =1

3

∑ j =1

⎛ ⎛ b − a⎞ ⎞ R e⎜ D j ⎜ ω ⎟⎟ f x j ⎝ ⎝ 2 ⎠⎠

( )

⎤ ⎛ ⎛ b − a⎞ ⎞ Im⎜ D j ⎜ ω ⎟⎟ f x j ⎥ , ⎥ ⎝ ⎝ 2 ⎠⎠ ⎦

( )

где R e ( Im ) обозначают вещественную и мнимую части соответственно.

2. Приближенное интегрирование методом Монте-Карло 2.1. Задание Написать программу для вычисления интеграла методом Монте-Карло. Организовать вывод приближенных значений интеграла для различного числа испытаний в файл. Построить по этим данным график в среде Maple, отметив на графике точное значение интеграла (см. Рис.2). Сравнить результаты, получающиеся при использовании трех последовательностей случайных чисел, сгенерированных стандартным генератором псевдослучайных чисел, и генератором, описанным в приложении А, для “простейшего” и “геометрического” вариантов метода. Тестовый пример:

∫ (1 − x )(1 − x ) ⋅⋅⋅ (1 − x )dx =(4 / 3) , 2 1

G

2 2

2 6

6

(3)

8 где область G - шестимерный куб со стороной равной двум с центром в начале координат:

{

}

G = x = ( x 1 , x 2 ,..., x 6 ) ∈ R 6| | x i | ≤ 1, i = 1,..,6

.

Рекомендуемая литература: [3], гл.5, §8; [4], гл. 3, §2.

2.2. О методе Метод Монте-Карло, или метод статистических испытаний, применяется главным образом для приближенного вычисления многомерных интегралов. Дело в том, что с ростом размерности интеграла d количество узлов для его приближенного вычисления по формулам типа Ньютона-Котеса растет пропорционально N d, где N число узлов, достаточное для приближенного вычисления одномерного “сечения” данного интеграла с требуемой точностью. В то же время для метода Монте-Карло число узлов, необходимое для вычисления подынтегральной функции, не зависит от порядка интеграла. Поэтому, для достаточно больших значений d метод Монте-Карло оказывается единственным реально применимым вычислительным методом. Другими “показаниями” к применению данного метода являются сложная граница области интегрирования, отсутствие областей с резкими изменениями подынтегральной функции и умеренные требования к точности вычислений. Последнее обстоятельство является весьма существенным, так как метод Монте-Карло имеет невысокую скорость сходимости, порядка

N

-1/2

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

9 гральной функции, при необходимости оценив возможность выделения особенностей (ср. с [2]). Характерной особенностью метода Монте-Карло является вероятностный характер получаемого с его помощью ответа: с ростом N повышается вероятность того, что вычисленное значение близкÓ к истинному значению интеграла. Это утверждение справедливо лишь для “истинно случайныx” последовательностей чисел, используемых для теоретического обоснования метода. Поэтому для получения правильных результатов при практическом использовании метода Монте-Карло совершенно необходимо высокое качество генератора псевдослучайных чисел. Итак, пусть имеется d - мерный интеграл

I=

∫

f ( x )dx , G ∈ R d .

(4)

G

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

{ξi }

, i=1..N, - это наугад

выбранные точки области G. Тогда, согласно “простейшему” варианту метода

I ≈ mes(G ) f ± mes(G )

f2 − f

2

N

,

(5)

(ξ i ) .

(6)

где mes( G ) - мера области G,

1 f ≡ N

N

∑ f (ξ ) , i

i =1

f

2

1 ≡ N

N

∑f

2

i =1

Второй член в формуле (5) , как обычно при записи приближенного числа, характеризует (вероятную) ошибку приближения.

10 Суть формул (5), (6) проста. Точное значение интеграла I, разделенного на mes(G ) , - это математическое ожидание случайной величины f ( x ) , порожденной случайной величиной x , равномерно распределенной в области G. Формула

1 mes(G )

∫ G

1 f ( x )dx ≈ N

N

∑ f (ξ ) i

i =1

(см. (5)) - это обычное приближение математического ожидания выборочным средним значением. Приведем также “геометрический” вариант метода. Пусть для простоты интеграл (4) - одномерный: G = [ a, b] , и 0 ≤ f ( x ) ≤ M при x ∈G (Рис. 1). Выберем наугад N точек в прямоугольнике [ a, b] × M . y M

y = f (x )

0 a

b

x

Рис.1. Отношение площади криволинейной трапеции, ограниченной графиком функции y = f ( x ) , к площади прямоугольника (b − a)M приближенно равно доле точек, выбранных случайным образом в прямоугольнике, оказавшихся ниже графика функции. Чем больше взято точек, тем приближение точнее.

11

Пусть Nf из них оказалось ниже графика функции f ( x ) . Тогда значение интеграла, равное площади криволинейной трапеции, пропорционально отношению N

(b − a)M

N . Коэффициент пропорциональности равен величине

f

- площади прямоугольника.

В многомерном случае поступают аналогичным образом. Пусть,

0 ≤ f ( x ) ≤ M , x ∈G (Если, m ≤ f ( x ) ≤ M , m < 0,

x ∈G , то можно пе-

рейти к функции g( x ) ≡ f ( x ) − m ). Берут наугад N точек {ξ i } , i=1..N, в области G . Для каждой такой точки выбирается случайное число ζ i из интервала

[0,M ] .

Пусть Nf

- это количество точек

{ξi }

, для которых

ζ i < f (ξ i ) . Тогда

I=

∫

f ( x )dx ≈ mes(G ) ⋅ M ⋅

G

Nf N

.

(7)

Проиллюстрируем оба варианта метода: “простейший” и “геометрический”, на тестовом примере (3). Сначала применялась формула (5). В данном случае мера mes(G ) области G равна объему шестимерного куба со стороной равной двум, т.е. 64. Таким образом, приближенное значение интеграла вычислялось по формуле

1 I ≈ 64 ⋅ N

N

∑ f( ξ ) . i

(8)

i =1

На рисунке 2 приведены приближенные значения тестового интеграла в зависимости от количества точек, выбранных с помощью встроенного и

12 “внешнего” генераторов случайных чисел соответственно. Каждая точка -

, ] . Обратите это шесть последовательных случайных чисел из интервала [ −11 внимание на меньшие колебания с ростом N приближенных значений интеграла, найденных с помощью внешнего датчика, и на важность удачного выбора значения числа: RandSeed (для встроенного генератора) или idummy (для ran1), в зависимости от которого вычисляется та или иная случайная последовательность. Рассмотрим теперь применение “геометрического” варианта метода (Рис.3). Так как подынтегральная функция в интеграле (2.1) принимает зна-

, ] на G , то, в соответствие с формулой (7), чения из интервала [01

∫ (1 − x )(1 − x ) ⋅⋅⋅ (1 − x )dx ≈ 64 ⋅ N 2 1

2 2

2 6

N

f

.

(9)

G

Из сравнения результатов расчетов по формулам (8), (9) видно, что “геометрический” вариант метода Монте-Карло вычисления многомерных интегралов менее точен, чем “простейший”. В любом случае сходимость достаточно медленная. Существуют различные подходы для ее ускорения. Прежде всего необходимо определить области имеются ли области резкого изменения подынтегральной функции. Для таких областей интегрирование по методу Монте-Карло дает наибольшую ошибку. В простейшем случае интегралы по этим областям вычисляют отдельно. По существу это отражает естественное стремление брать больше случайных точек там, где функция быстро изменяется. Иногда из этих же соображений с самого начала используют подходящее неравномерное распределения случайных точек. Очень полезным оказывается выделение особенностей с помощью явно интегрируемых функций.

13 А

Б

Рис.2. Значения интеграла (3), найденные с помощью формулы (8) (“простейший” вариант метода), для различного числа случайно выбранных точек из области G. Каждая кривая отвечает отдельной последовательности случайных чисел, (А) сгенерированных с помощью датчика случайных чисел встроенного в Turbo Pascal, v.7.0 (Borland Intl) ; RandSeed=1, 48322, -13049; (Б) датчика Парка-Миллера ran1 (приложение А); idummy=-1, -48332, -13049. Горизонтальная линия - точное значение интеграла.

14 A

Б

Рис.3. Значения интеграла (3), найденные с помощью формулы (9) (“геометрический” вариант метода Монте-Карло), для различного числа случайно выбранных точек из области G; (А) кривые полученные с помощью встроенного генератора случайных чисел; стандартная переменная RandSeed=1, 48322, -13049; (Б) с помощью генератора ran1; idummy=-1, -48332, -13049.

15

Приложение А Существует немало хороших алгоритмов вычисления “случайных” чисел (см., например, [5] ). В основе многих из них лежит линейный конгруэнтный метод, согласно которому последовательность случайных чисел получается из соотношения Xn+1 =(a Xn +c) mod m, n>=0, для некоторых специально подобранных значений a, c, m; значение X0 достаточно произвольно. Ниже приведен фрагмент кода, реализующий с небольшими модификациями один из вариантов данного метода, - “минимальный” генератор случайных чисел Парка-Миллера (Park, Miller) c a=75 =16807, с=0, и m=231 -1= 2147483647 ([6]).

const IA=16807; IM=2147483647; IQ=127773; IR=2836; NTAB = 32; NDIV = (1+(IM-1) div NTAB); EPS = 1.2e-7; RNMX = (1.0-EPS);

AM=1.0/IM; MASK=123459876;

function ran1 (var idum:longint):real; { начальное значение idum должно быть ОТРИЦАТЕЛЬНЫМ; } { между последоватнльными обращениями к ran1 значение idum } { не должно меняться } const iy: longint = 0; iv: array [0..NTAB-1] of longint =(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0); var k,j:longint; temp:double; begin if ((idum <= 0) or (iy=0))

16 then begin if (-idum)<1 then idum:=1 else idum:=-idum; for j:=NTAB+7 downto 0 do begin k:=idum div IQ; idum:=IA*(idum-k*IQ)-IR*k; if (idum < 0) then idum:=idum+IM; if (jRNMX) then ran1:=RNMX else ran1:=temp; end;

Варианты заданий по теме “Интегралы от быстро осциллирующих функций” 2

1.

∫

2

2 −2 x

x e

sin(40x )dx

2.

0

0

1

1

3.

∫

ln(1 + x ) sin(60x )dx

4.

2

∫x

−1

∫

1 + x 2 cos(60x )dx

0

0

5.

∫

x 2 e −2 x cos(40x )dx

1

2

sin(40x )dx

6.

∫ 0

1 + x 2 cos(60x )dx

17 1

7.

∫x e

2 −x

2

sin(45x )dx

8.

−2

∫

x 3 e − x cos(40x )dx

10.

15.

17.

∫

2

1 + x 4 sin(40x )dx

12.

−2

2

0

∫

x 2 e2 x cos(40x )dx

14.

2

2

∫

x 2 e2 x cos(50x )dx

16.

∫

−2

−2

3

2

∫

e −3 x cos(45x )dx

18.

∫

∫

1 + x 2 cos(45x )dx

20.

∫ ln(1 + 2x ) cos(45x )dx 1

3

x e −2 x cos(50x )dx

22.

∫ 2

ln(4 − x ) sin(30x )dx

24.

∫

1

−1

2

4

0

1 + x 2 sin(45x )dx

0

2

∫

x e −2 x cos(30x )dx

2

0

∫

∫

x e2 x cos(45x )dx

0

2

25.

∫ ln(x + 3) cos(50x )dx

−2

−2

23.

x 2 e2 x sin(40x )dx

−2

2

21.

∫

−2

−1

19.

∫

x 2 e −2 x sin(40x )dx

0

2

13.

sin(50x )dx

2

−2

11.

2

0

1

9.

∫x

x e − x cos(60x )dx

26.

∫ 0

1 + x 4 sin(50x )dx

x e −2 x cos(50x )dx

18

Варианты заданий по теме “Многомерные интегралы” Во всех заданиях интегралы рассматриваются по области G, представляющей собой четырехмерный куб со стороной s и с центром в точке С=(c1 , c2 , c3 ,c4 ). Интеграл 1

s

C

∫ cos(x

1

+ 2x 2 − x 3 − x 4 )dx

1

(0,0,0,1)

∫ cos(x

1

+ x 2 − 2x 3 − x 4 )dx

2

(-1,0,0,1)

∫ sin(x

1

+ 3x 2 − x 3 + x 4 )dx

1

(0,0,1,0)

∫ sin(x

1

+ 3x 2 − x 3 + x 4 )dx

2

(1,0,0,1)

0.5

(0,1,0,1)

G

2

G

3

G

4

G

5

∫ cos(2x

1

∫ sin(x

1

+ x 2 − 2x 3 + x 4 )dx

1

(-1,-1,0,1)

∫ sin(x

1

+ 3x 2 − 2x 3 + 2x 4 )dx

1

(0,0,0,0)

1

+ 2x 2 − 2x 3 + x 4 )dx

1.5

(2,0,0,1)

∫ sin(x

1

+ x 2 − x 3 + x 4 )dx

2

(-2,0,0,0)

∫ sin(x

1

+ x 2 + x 3 + x 4 )dx

2

(1,0,2,1)

+ 2x 2 − x 3 + x 4 )dx

G

6

G

7

G

8

∫ cos(x G

9

G

10

G

11

∫ cos(x

1

+ x 2 + 2x 3 − 2x 4 )dx

1

(0,2,0,0)

∫ cos(x

1

+ 2x 2 − x 3 − x 4 )dx

0.5

(-1,0,0,-1)

G

12

G

19

13

∫ cos(x

1

+ x 2 − 2x 3 − x 4 )dx

2

(-1,0,0,2)

∫ sin(x

1

+ 3x 2 − x 3 + x 4 )dx

1

(-1,0,2,1)

∫ sin(x

1

+ 3x 2 − x 3 + x 4 )dx

1.5

(1,1,0,1)

1

(-1,0,-2,1)

2

(0,0,0,-1)

G

14

G

15

G

16

∫ cos(2x

1

∫ sin(x

1

+ x 2 − 2x 3 + x 4 )dx

∫ sin(x

1

+ 3x 2 − 2x 3 + 2x 4 )dx

0.5

(2,0,0,0)

∫ sin(x

1

+ x 2 − x 3 + x 4 )dx

1.5

(1,0,0,1)

∫ sin(x

1

+ x 2 + x 3 + x 4 )dx

1

(2,0,0,2)

+ 2x 2 − x 3 + x 4 )dx

G

17

G

18

G

19

G

20

G

21

∫ cos(x

1

+ x 2 + 2x 3 − 2x 4 )dx

2

(1,1,1,1)

∫ cos(x

1

+ 2x 2 − x 3 − x 4 )dx

0.5

(-1,-1,-1,1)

∫ cos(x

1

+ x 2 − 2x 3 − x 4 )dx

2

(-1,0,2,2)

∫ sin(x

1

+ 3x 2 − x 3 + x 4 )dx

1

(0,2,0,1)

∫ sin(x

1

+ 3x 2 − x 3 + x 4 )dx

0.5

(-1,0,-1,1)

∫ sin(x

1

+ x 2 − 2x 3 + x 4 )dx

1

(-1,0,0,2)

G

22

G

23

G

24

G

25

G

26

G

20

Литература 1. Абрамян М.Э., Олифер А.В. Численные методы. Методические указания к выполнению индивидуальных заданий. - Ростов-на-Дону, 1991. 2. Михалкович С.С., Обрезанова О.А., Олифер А.В. Численные методы. Методические указания к выполнению индивидуальных заданий. Выпуск II Ростов-на-Дону, 1995. 3. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. -М.: Наука, 1987. 4. Соболь И.М. Численные методы Монте-Карло. М.: Наука, 1973. 5. Kнут Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. - М.: Мир, 1977. 6. Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical Resipes in C. - Cambridge Univ. Press, 1992.