Диссертация (1150625), страница 7
Текст из файла (страница 7)
Если l̄ ∩ l̄ ̸= ∅, то, в силу определения 8, либо l̄ ⊂ l+ , и++−−−−+−−−тогда (l+ ∩ l ) = (l ∩ l ), (l ∩ l ) = (l ∩ l ) = 0, либо l̄ ⊂ l , и тогда (l ∩ l ) =++++−(l− ∩ l ), (l ∩ l ) = (l ∩ l ) = 0. В обоих случаях сумма четырёх слагаемых обращаетсяв ноль.1.2.2Построение квадратуры Qint и анализ дисперсииВводимую далее квадратурную формулу будем рассматривать в рамках частной постановкизадачи численного интегрирования. Пусть X1 , .
. . , X есть ( , )-разбиение единичного гиперкуба, определённое для фиксированного = 2 , ∈ N0 . В таком случае определена обобщённаясистема Хаара { }=1 в соответствии с (1.49).Для удобства дальнейшего изложения введём понятие латинского множества. Определим как прямое произведение гиперкубов : = × × · · · × .⏞⏟(1.50) разОпределение 9. Пусть = (1 , 2 , . . . , ) – некоторая перестановка (1, 2, . . .
, ). Латинскиммножеством (), задаваемым перестановкой (1 , 2 , . . . , ) мы будем называть подмножество , определяемое следующим условием:(1 ,2 , . . . , ) ∈ (1 ,2 , . . . , ) ⇔ ∀ ∈ {1,2, . . . ,} ∈ X .(1.51)Полным латинским множеством назовём подмножество , являющееся объединениемлатинских множеств, задаваемых всевозможными перестановками длины : =⋃︁(1 , 2 , .
. . , ).(1.52)(1 ,2 ,..., )Латинское множество отражает ту же идею, что и элементарные подмножества (1.31)в определениях (,,)-сетей и (,)-последовательностей. В самом деле, элемент =(1 ,2 , . . . , ) ∈ принадлежит какому-либо латинскому множеству в том и только в томслучае, если в каждом из X1 , . . . , X содержится ровно одна из точек 1 ,2 , . . .
, .31Применим теорему 1 к семейству обобщённых функций Хаара (1.49).Теорема 4. Случайная квадратурная формула, точная для первых обобщённых функций Хаара,имеет вид1 ∑︁ ( ), = =1(1.53)где 1 ,2 , . . . , – случайные точки из с совместным распределением, задаваемым плотностью⎧⎪⎨ , (1 ,2 , . . . , ) ∈ ;(1 ,2 , . . . , ) = !⎪⎩0,( , , .
. . , ) ̸∈ .12(1.54)Доказательство.Лемма 1 позволяет применить теорему 1 непосредственно. Для установления точного видасамой формулы и плотности распределения узлов необходимо только получить выражения ∆()и ∆ ().Пусть = (1 ,2 , . . . , ) есть перестановка (1,2, . . .
,). Как известно, чётность перестановки однозначно определяется количеством инверсий в ней. Слагаемое в ∆(), отвечающее перестановке , есть (−1) 1 (1 )2 (2 ) . . . ( ). Из всех произведений такого рода ненулевымиявляются только такие, у которых все узлы расположены в разных подмножествах.
Действительно, если хотя бы две точки попадают в одно и то же подмножество X , то, в силу того,что для любого функция () постоянна ∀ ∈ X , определитель ∆() имеет две одинаковыестроки, и, следовательно, равен нулю. Это означает, что формула корректно определена толькона полном латинском множестве .Далее, ∆ () также есть сумма произведений вида (−1) (1 )2 (2 ) . . . ( ) по всемперестановкам . Если (1 ,2 , .
. . , ) ∈ , то∆ () =(−1) · · ( (1 ) + (2 ) + . . . + ( )) · ,∆() =(−1) · · (1 + 1 + . . . + 1) · ,где ̸= 0 – постоянная вида 2 (2 ) . . . ( ) (она одинакова для всех перестановок , опятьже, в силу кусочной постоянности ()), а > 0 – количество таких произведений, генерируемых всевозможными перестановками. Важно отметить, что ̸= 0: пусть две перестановки1 и 2 отличаются одной транспозицией, тогда они имеют разные знаки (1 2 = −1), но исоответствующие миноры, входящие в ∆ () и ∆(), также отличаются знаком; так, слагаемыеот двух разных перестановок не могут обратить друг друга в ноль. В действительности обе постоянные и могут быть точно установлены, но это излишне, поскольку они не входят ввид формулы, сокращаясь при делении.32В итоге, квадратурная формула имеет вид =11 ∑︁∆ ()= ( (1 ) + (2 ) + . .
. + ( )) = ( ).∆() =1(1.55)Что касается плотности совместного распределения узлов, то она постоянна на . Константуможно легко определить из условия нормировки плотности: объём множества равен!,поэтому константа в плотности является обратной величиной:⎧⎪⎨ , (1 ,2 , . . . , ) ∈ ,(1 ,2 , . . . , ) = !⎪⎩0,( , , . . . , ) ∈/ 12(1.56)Теорема 1 автоматически гарантирует несмещённость формулы (1.53). Для полноты изложения мы приведём и прямое доказательство этого факта.Лемма 2. Случайная квадратурная формула (1.53) с плотностью (1.54) является несмещённойоценкой интеграла для произвольной подынтегральной функции ∈ ℒ1 ( ).Доказательство.
Действительно,· 1 (1 ,2 , . . . , )(1 )(2 ) . . . ( ) =!⎞⎛∫︁∫︁∫︁1⎜⎟= ⎝ (1 )(1 ) + . . . + ( )( )⎠ = ()().∫︁E( ) = ·Теперь, когда свойство несмещённости установлено, ключевым становится вопрос о дисперсии формулы (1.53). Сначала установим, является ли рассматриваемая система функций регулярной.Лемма 3. Система обобщенных функций Хаара {1 , 2 , . . . , } не является регулярной.Доказательство. Для доказательства достаточно указать множество ненулевого объёма, на котором определитель ∆() обращается в ноль. В качестве примера такого множества может выступать X1 × X1 × · · · × X1 : его объём равен1,а ∆() состоит из одинаковых строк.
В действи-тельности, нами уже установлено, что (∆() ̸= 0) =для любого > 1.!,что меньше единицы ( ( ) = 1)Факт отсутствия регулярности означает, что мы не сможем воспользоваться теоремой 2 дляустановления точной дисперсии формулы (1.53). Тем не менее, мы воспользуемся явным видомсамой формулы и плотности распределения её узлов (1.54) и посчитаем дисперсию напрямую.33Теорема 5. Дисперсия формулы (1.53) равна⎞2⎛Var( ) =1∫︁ 2 () −1⎜⎝∫︁1 ∑︁⎟ ()⎠ −( − )2 , <(1.57)∫︁где , ∈ {1, 2, . .
. } и = ().XДоказательство. Вычислим дисперсию непосредственно по определению:⎞2⎛∫︁Var( ) =X⎜2 − ⎝∫︁⎟ ⎠ = − .(1.58)XИнтегралы и рассмотрим отдельно. Относительно интеграла выполнена следующаяцепочка равенств:∫︁1 = 2( (1 ) + (2 ) + . . . + ( ))2 =X−2=!{︃ ∫︁ · 2 (1 )1(1 ,2 ,..., ) (1 ,2 , . . . , )(1 )(2 ) . . . ( )+X+2∑︁ ∫︁}︃ ( ) ( )1(1 ,2 ,..., ) (1 ,2 , . .
. , )(1 )(2 ) . . . ( )< X{︃ ∫︁−2= · 2 (1 )1(1 ,2 ,..., ) (1 ,2 , . . . , )(1 )(2 ) . . . ( )+!X+ ( − 1) ·∑︁ ∫︁}︃ ( ) ( )1(1 ,2 ,..., ) (1 ,2 , . . . , )(1 )(2 ) . . . ( )=< X=−2[ · + ( − 1) · ] .!Нам удалось свести вычисление интеграла к вычислению более простых интегралов и . Рассмотрим :∫︁ =X( − 1)! (1 )1(1 ,2 ,..., ) (1 ,2 , . . . , )(1 )(2 ) . . . ( ) =−12∫︁X 2 ()().34В свою очередь, для справедливо∫︁ = (1 ) (2 )1(1 ,2 ,..., ) (1 ,2 , .
. . , )(1 )(2 ) . . . ( ) =X( − 2)!=−2∫︁ (1 ) (2 )(1 )(2 ) =X1 ̸=X2⎧⎪∫︁( − 2)! ⎨⎫⎪⎬∫︁ (1 ) (2 )(1 )(2 ) − (1 ) (2 )(1 )(2 ) =⎪−2 ⎪⎩2⎭X1 =X2X⎧⎫(︃ ∫︁)︃2⎪⎪∫︁∫︁⎬∑︁( − 2)! ⎨=()()−()()()()=1122⎪−2 ⎪⎩⎭=1XXX⎧⎫(︃ ∫︁)︃2(︃)︃2⎪⎪∫︁⎬∑︁( − 2)! ⎨ ()() −= ()().⎪−2 ⎪⎩⎭=1=XXТаким образом, мы получили выражение для интеграла :−2[ · + ( − 1) · ] =! ⎡∫︁!−2 ⎢!2⎢()()+=! ⎣ −1−2 =⎧(︃⎪⎨ ∫︁⎪⎩X1=∫︁2 ()() +X− ()()X ()()X)︃2(︃ ∫︁)︃2∑︁(︃ ∫︁=1X−∑︁(︃ ∫︁=1X⎫⎤)︃2 ⎪⎬⎥⎥= ()()⎦⎪⎭)︃2 ()().Интеграл определяется тривиально в силу несмещённости формулы:(︃ ∫︁ =)︃2 ()()X.35Наконец,1Var( ) = − =∫︁ 2 ()() −∑︁(︃ ∫︁=1XX)︃2 ()()=)︃2∫︁11 2 ()() − ()() +=XX(︃ ∫︁)︃2(︃ ∫︁)︃2∑︁1 ()() −+ ()() ==1(︃ ∫︁XX)︁1 (︁(1 + 2 + .
. . + )2 − 12 − 22 − . . . − 2 == Var( ) +1 ∑︁= Var( ) −( − )2 , <где1Var( ) =∫︁1 2 ()() −)︃2(︃∫︁X ()()X∫︁есть дисперсия традиционного Монте-Карло, а = ()(), = 1,2, . . . ,.XСледствие. Дисперсия формулы (1.53) не превосходит дисперсии наивного Монте-Карло (1.5):Var( ) = Var( ) − ,где = () =1 ∑︁( − )2 . <(1.59)(1.60)Далее мы будем называть формулу (1.53), обладающую вышеупомянутыми свойствами точности, несмещённости и имеющую дисперсию (1.57), формулой Qint или процедурой Qint.1.2.3Некоторые результаты для теории случайных квадратурных формулВ этом подразделе мы остановимся на новых фактах, которые дополняют теорию случайных квадратурных формул.
Как уже отмечалось, теорема 2 указывает, что в случае регулярныхсистем неравенство для дисперсии (1.22) обращается в равенство. С другой стороны, для некоторых нерегулярных систем истинная дисперсия меньше (например, для обобщённой системыХаара справедливо выражение (1.57) из теоремы 5). Логично попытаться провести черту междуклассами нерегулярных систем, для которых дисперсия меньше, чем оценка сверху (1.22), и длякоторых истинная дисперсия в точности задаётся (1.22).До конца этой главы мы возвращаем общую постановку задачи: X – произвольное непустоемножество, – -конечная мера, (X) = 1. Кроме того, здесь обозначает любое натуральное число, большее 1.
Введём разбиение X на непересекающихся подмножеств, при этом36необязательно равной меры: X =⋃︀X . Для краткости мы будем использовать обозначение=1 () = (1 ) . . . ( ), взятое из книги Ермакова С.М. [6]. Приводимые далее результатычастично изложены в статье автора и Ермакова С.М.
[20].Определим функцию-индикатор для произвольного множества :⎧⎪⎨1, ∈ ,1 () =⎪⎩0, ∈/ .(1.61)Определение 10. Для фиксированного разбиения X1 , . . . , X назовём произвольную ортонормированную систему { }=1 системой со скользящим носителем, если1) для = 1, 2, .
. . , выполнено ( ) = X ;2) система { }=1 линейно независима с константой 1X .Теорема 6. Пусть { }=1 – произвольная система со скользящим носителем. Тогда случайнаяквадратурная формула, точная для { }=1 и построенная в соответствии с теоремой 1, имеетдисперсию, совпадающую с оценкой сверху (1.22).Доказательство.
План доказательства состоит из двух шагов: во-первых, мы применим теорему 1 к набору из + 1 функций, {1X , 1 , . . . , }; во-вторых, мы посчитаем точную дисперсиюполученной формулы и сравним её с верхней границей, предоставленной теоремой 2.Сама формула и плотность распределения узлов зависят от распределения + 1 узлов по подмножествам. В точности как и для формулы Qint, многие комбинации приводят к нулю вопределителях ∆() и ∆ (), и поэтому для них формула определена не будет. Нам необходимо рассмотреть только такие случаи, когда все подмножества X получают ровно по однойточке, кроме одного подмножества, которое получает две. Общий объём множества, где формула корректно определена, составляет {∆() ̸= 0} =(+1)!.2В силу симметрии относительнонумерации 1 , .
. . , +1 , по сути необходимо исследовать единственный случай (обозначим этоусловие за ): 1 , 2 ∈ X1 , +1 ∈ X для всех > 2.Тогда⃒⃒0⃒1 1 (1 )⃒⃒1 ( )012⃒⃒02 (3 )∆() = ⃒⃒1⃒ ......⃒...⃒⃒⃒100...............⃒⃒⃒⃒⃒0⃒∏︁⃒⃒0 (+1 ),⃒ = (1 (2 ) − 1 (1 ))⃒..=2⃒.⃒⃒ (+1 )⃒0и, аналогично,∆ () = ( (1 )1 (2 ) − (2 )1 (1 ))∏︁=2 (+1 ).37Δ ()Формула для условия может быть записана в виде ˜+1 = Δ(), а плотность распределения2(Δ())˜ =узлов – . Эти выражения носят формальный характер и могут быть значительно(+1)!упрощены, но мы не будем этого делать, потому что нас интересует только дисперсия такойформулы, которую мы можем установить и без такого упрощения.Обратимся к выражению дисперсии, получив сначала выражение для математического ожидания квадрата формулы (подсчёт во многом совпадает с доказательством теоремы 5):∫︁2˜ (1 , .
. . , +1 )+1 () =˜+1(1 , . . . , +1 )1=( + 1)!=2( + 1)!∫︁∏︁2 (+1 )+1 () ==2∫︁∫︁X2=( + 1)!( (1 )1 (2 ) − (2 )1 (1 ))2(︀)︀ 2 (1 )12 (2 ) − (1 ) (2 )1 (1 )1 (2 ) (1 )(2 ) =X(︃1 ∫︁ 1)︃ 2 ()() − ⟨, 1 ⟩2 ,X1∫︁2где ⟨·, ·⟩ обозначает скалярное произведение в ℒ : ⟨, ⟩ = ()()().XПроводя суммирование по всем(+1)!2случаям, аналогичным , получаем1122E(˜+1) = ( + 1)!2 ( + 1)!(︃ ∫︁ 2 ()() −= 2 ()() −∑︁)︃⟨, ⟩2==1X∫︁∑︁⟨, ⟩2 .=1XНаконец, дисперсия равна2Var(˜+1 ) = E(˜+1) − E(˜+1 )2 =∫︁∑︁ ()() − ⟨, 1X ⟩ −⟨, ⟩2 ,Xчто в точности совпадает с оценкой по теореме 2.22=1Полученный результат интересен ещё и в контексте таких разбиений, когда все подмножества имеют одинаковую меру: (X ) =1(именно такого рода разбиения мы рассматривали дляпостроения обобщённой системы Хаара и процедуры Qint). В этом случае для формулы (1.53)справедливо {∆() ̸= 0} =!,и эта величина быстро стремится к нулю с ростом .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
