Содержание к диссертации
Введение
ГЛАВА I. Разделяющие системы разбиений конечного множества . 15
1.1. Основные понятия .' 15
1.2. Связь мевду-F(л Д) -иКъ,4*0 -планами 22
1.3. Построение FCVV,K.) -планов на основе кодов Радемахера 33
1.4. Границы длин К и ЫСп.,4К.) -кодов 40
ГЛАВА II. Блоковая передача информации в отмиршцем канале множественного доступа с обратной связью и последовательные планы экспериментов для линейной модем 47
2.1. Постановка задачи 47
2.2. Рекуррентный метод получения верхних границ 54
2.3. Диаграммный метод получения верхних границ 58
ГЛАВА III Последовательные и случайные планы экспериментов для линейной модели с условием несоизмеримости .. 73
3.1. Основные понятия 73
3.2. Случайные планы экспериментов для линейной модели с условием несоизмеримости факторов над 1-1-,0-,1] 77
3.3. Последовательные планы экспериментов для линейной модели с условием несоизмеримости факторов над TL 88
А. Вспомогательные результаты 88
Б. Построение плана экспериментов 91
В. Оценка числа экспериментов в плане 99
Литература
- Построение FCVV,K.) -планов на основе кодов Радемахера
- Границы длин К и ЫСп.,4К.) -кодов
- Рекуррентный метод получения верхних границ
- Случайные планы экспериментов для линейной модели с условием несоизмеримости факторов над 1-1-,0-,1]
Введение к работе
Многие сложные явления, зависящие от большого числа факторов, определяются достаточно точно лишь небольшим их числом, называемых "значимыми"» Влияние остальных факторов несущественно и сравнимо с погрешностью измерений, проводимых при изучении явления. Эксперименты по поиску значимых факторов называются отсеивающими.
Одним из первых примеров применения отсеивающих экспериментов (ОЭ) были принятые в США. по предложению Р.Дор$мана [ 34 ] двухэтапные групповые проверки на реакцию Вассермана крови солдат, отправляемых на фронт, с целью обнаружения больных некоторым редким заболеванием. Во время массового обследования было замечено, что разумнее анализировать пробу крови целой группы людей. Если такая объединённая проба не содержит определённых антител, имеющихся только у больных, то, значит, ни один из обследуемых не болен. В противном случае среди них есть хотя бы один больной. Индивидуальное обследование проводилось лишь в тех группах, где было замечено наличие больных. Это значительно сократило число анализов, так как количество больных солдат невелико.
Аналогичные процедуры проверки крови доноров успешно апробированы в СССР по предложению М.Б.Малютова в отделении переливания крови Института хирургии им, А.В.Вишневского АМН СССР для выявления доноров, больных гепатитом. Соответствующие анализы используют дорогостоящие импортные реактивы и уменьшение их
числа даёт большой экономический эффект.
К модели отсеивающих экспериментов по существу сводится проектирование систем технической диагностики (обнаружения неисправности) некоторых больших электронных комплексов бортовой аппаратуры (например, судов), если эти комплексы обладают избыточностью, т.е. продолжают выполнять свою задачу при выходе из строя небольшого числа элементов [II] . Другая такая модель возникает при кодировании заявок в сети ЭВМ с множественным доступом к каналу связи [ 3 ] .
В 1959 г. для планирования и анализа отсеивающих экспериментов был предложен метод, получивший в литературе название метода случайного баланса (МСБ). Он был опубликован в [32] со ссылкой на Ф.Саттерзвайта [40] , успешно применявшего его в течение нескольких лет в промышленности. Основные идеи этого метода высказывались и ранее [28] . Вообще, метод случайного планирования имеет корни в Фишеровской идее рандомизации. МСБ вызвал резкую дискуссию [33] и был отвергнут большинством статистиков, основным возражением которых было постулируемое превосходство регулярного планирования над случайным. При этом упускалось из вида, что задача построения оптимального регулярного плана отсеивающих экспериментов сложна, в то время как случайное планирование оказывается весьма близким к оптимальному. Критике МСБ способствовала неясность, отсутствие каких-либо оценок применимости и эффективности случайного планирования в [40] . После дискуссии упоминание о МСБ исчезло со страниц зарубежной периодики.
В нашей стране по инициативе В.В.Налимова МСБ был освоен, модифицирован [27, 29, 30] и проверен на модельных и іірикладннх
примерах, где во многих случаях он оказался весьма эффективным.
Первое продвижение по пути обоснования МСБ сделал Л.Д.Ме-шалкин [ 23, 24 ] . В последущем цикле работ [ 15 - 21 ] на модельных задачах была выяснена связь МСБ с теорией передачи информации, объяснившая глногие казавшиеся парадоксальными рекомендации МСБ.
В шестидесятые годы А.Реньи опубликовал цикл исследований по применениям идей теории информации в математической статистике, среди которых к нашей теме непосредственное отношение имеют работы по методам поиска (см. [38] , а также обзор [IV] ). Эти исследования были вызваны логическим развитием теории, а не приложениями (хотя считают, что стимулом этих исследований явилось происшествие, в котором А.Реньи не смог найти причину неисправности автомобиля). Под влиянием работ А.Реньи появились по крайней мере два подхода в приложении идей теории информации к планированию эксперимента. Во-первых, это работы И.Вайда [2] , исследовавшего для общей дискретной схемы случайного планирования эксперимента вопрос об асимптотике средней вероятности ошибки. Во-вторых, это работа [41] Дж.Сриваставы. В ней для общей линейной модели без ошибок экспериментов находится условие однозначного восстановления всех значимых факторов, если их число не превосходит S .
В настоящее время работы по планированию отсеивающих экспериментов получили дальнейшее развитие. Появилась целая школа математиков, связанных с семинаром, работающим в МГУ, получен ряд весьма интересных результатов. Из них мы особенно отмечаем
работы А.Г.Дьячкова [ 5 - 10 ] , М.Б.Малютова [15 - 21 ] , а также работы других математиков (см. [22, 25, 26] ).
Целью нашей работы является построение и оценка длины последовательных, статических и случайных планов для линейной модели планирования отсеивающих экспериментов при определённых ограничениях, наложенных на класс допустимых экспериментов и множество исследуемых факторов.
В главе I изучаются статические F(A,k)- и Р(Д,4К)- планы и связанное с ними понятие разделяющей системы разбиений конечного множества. Понятие разделяющей системы было введено А.Реньи [37] в связи с задачами теории информации, рассматривалось Д.Катоной [35] и другими авторами (см. [I, 5, 17, 31, 42] ).
— —*
FCft-A)" и FСп.,4К:) - планы введены в [17] для S = I. Нами
установлена связь между F(n,K:)-zF(ri,4K) - планами для произвольного 5 , а также получено выражение для длины ЫС^Ю- кода через длину некоторого определённого Ы(Д, *0 - кода.
Теорема I.I. Пуста П = 11^^ >,...» it. у к, _п Тогда:
к і n.pu L > 1 ?
s*i NC*,*ub NU/\i) , ^е il.L» {[Си-С кр/ОПJ npuUUZ,
s+t Индексы г и t однозначно определяются из условий:
s+i
S+i S+i S+i
Здесь и всюду в дальнейшем через Гхі и\_х] будем обозначать ближайшее сверку и снизу vixtE. целые числа. Отметим, что для любых xeR и WfclNX справедливы тождества:
1^1-ни.
("to^Txll = її ^і*! , x»i.
Через [ ю.] будем обозначать множество натуральных чисел от I до а .
Следствие 1.2. Пусть к. f,... г к. s 7 а >, кі+ YL К і Тогда:
Получены нижние и верхние оценки величины N С ft, 4 к.) и изучено её асимптотическое поведение в некоторых случаях.
Теорема 1.2. Пусть к1 = ... = к. = к, ^ n/Cs+1). Тогда:
п.
^w^; і і к'ъ s Отсюда при s = І получаем усиление результата Д.Катоны из І35]
Следствие 1.4. При г\>к. справедливо неравенство:
Ь>
3*Д
-1 .
ЦиС^/Ю
ЫСп,к.) = NCa,4R.) ^
-а*
Этот результат получен также независимо И.Вегенером (си. [І, 421).
Следствие 1.5. Пусть к.1= > = к. s = к. = осп) приа-^+оо Тогда:
Ы(лД) = N(i\,4*) =
-о9 ^ti
Cl+oci))
Следствие 1.6. Пусть я= oct\) при а - -v <*> . Тогда:
Єо,
9г* а
ЬЦи-Л)= NO,4n) =
^оо Ох/К) t
Теотэема 1.3. Имеют место неравенства:
(1+ осі))
ас п.-о
4 NCft,4K.Kmax<
Следствие 1.7. При w »[( nruxx kl)-Cs + С K-O] / Я + 1 справедливо равенство:
NC^,^k.) =
2,0v-l)
1=1
- 10 ~ Следствие 1«8« Имеют место неравенства:
Теорема 1.4» Пусть N^lN такое, что
Тогда Ы (.*,**) * Ь*о
Следствие 1.9. Пусть ft t = f 1pt'M при t*i,...,5'iS;
где E t> = 1 : ftp = о См) при I > s' . Тогда:
E=1it ^
tUp)
Отметим, что для s« s' = I результат этого следствия впервые получен в работе [35] , и для s = s' - вероятностными методами в
работе [5] .
б'
Следствие 1.10« Пусть к. t = [Cp_-u. "\ при C = l,...,s'4S7 где се>о , о < е < 1 , nt=o
1-е CL-er)- Е с
Б главе II изучается линейная модель поиска [ 36 ] двух дефектных элементов. Построена последовательная стратегия, улучшающая границы для числа экспериментов последовательных планов из
- II -
работ [22, 361 . Обозначим через N(A,m.) минимальную длину последовательного плана, определяющего дефектные элементы в двух группах из п и m элементов, каждая из которых содерзкит ровно по одному дефектному. Нами получен следующий результат. При а 4 га справедливо неравенство:
С помощью этого неравенства установлена новая нижняя граница области пропускной способности с нулевой ошибкой при блоковой передаче информации с обратной связью по суммирующему каналу с множественным доступом.
Предположим, что имеются два источника, которые синхронно в дискретные моменты времени подают сигналы X е[0,1}(оС = I, 2). Эти сигналы поступают в суммирующий канал с обратной связью и результат У { О, I, 2 } передаётся без искажений адресату (рис.0.1).
С помощью неравенства (2.15) установлена новая нижняя граница Р Q. L области пропускной способности канала при блоковой передаче информации. На рисунке 0.2 приведена для сравнения простейшая верхняя граница этой области (граница кооперативного кодирования) Р S Т L .
Б главе III продолжается изучение МСБ для линейной модели, начатое в работах [20, 23, 24] .
Для случая несоизмеримости факторов над множеством [о,± 1} нами указан метод анализа результатов случайных экспериментов, позволяющий с вероятностью не меньшей 1-f) ( 0 < у> < I ) определить все факторы при условии, что проведено не менее
- 12 ~
обратная связь
а.
О
Р = ( 0; I ), S L = ( I; 0 ), Т Q = ( 0,75; 0,75 ).
( 0,58496; I ), ( I; 0,58496 ),
Рис.0.2.
- із -
a* -f tog,, Сгг-и + 1) - ЄоІІ у
экспериментов. Ошибка в определении факторов исключается. Здесь через п. обозначено общее количество факторов, а через п. -количество значимых факторов, которое может быть заранее неизвестно и определится в ходе экспериментов.
На основе метода анализа случайных экспериментов построен алгоритм, определяющий номера и значения всех значимых факторов. Оценено математическое ожидание М е случайного момента Т остановки работы алгоритма в предположении, что известна верхняя граница & числа значимых факторов и ;
t 4> + to^ (Л-к.) , ^<5<а,
-V- оо
Отметим, что полученные результаты применимы, когда s «п. и обобщаются на ситуацию, при которой допускаются ошибки результатов измерений проводимых экспериментов.
Для случая несоизмеримости факторов над TL построен последовательный план, определяющий все факторы не более чем за
экспериментов. Здесь іг - общее количество факторов, ft - количество значимых факторов, к. —> + оо , П :> к: >> 2, » С = - tcxT1 зе - I < 1,7, где зе = 0,773... - корень уравнения К. сх)=х ; Ь-Сэс) = - х too^x - С 1-х) foo^Cl-X) -энтропия Шеннона.
Основные результаты диссертации опубликованы в работах [12, 13, 14,.-4].
Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук профессору К.А.Рыбникову за руководство работой. Он также благодарен сотрудникам кафедры теории вероятностей механико-математического факультета МГУ М.Б.Меныпикову и А.Г.Дьячкову за постановки некоторых задач и ценные советы при их обсуждении. Автор признателен участникам семинаров по комбинаторному анализу, теории информации и планированию эксперимента, коллективу кафедры теории вероятностей мех-мата МГУ за внимание и поддержку во время работы над диссертацией.
Автор выражает глубокую благодарность механико-математическому факультету МТУ, его профессорам, преподавателям и сотрудникам, за переданные ему знания и годы, проведённые на факультете.
Построение FCVV,K.) -планов на основе кодов Радемахера
Следующая нижняя граница для N С п., К. ) получена Д.Катоной L35] применением свойства субаддитивности энтропии: N(n,) Цг«г/ k( t/rO . (1-ю) В дальнейшем мы покажем, что во многих случаях указанная граница будет асимптотически оптимальной.
В этом параграфе мы рассмотрим один из наиболее важных случаев поставленной задачи: rcL=... = fcs = it. В силу нера s венства W , к. + /_, К : достаточно считать, что к. 4 «x/cs + i)
Построение FCh.74 к.) - планов мы будем производить на основе s - кодов Радемахера. Так называется любая детектирующая матрица размерами Г я, П." п составленная из чисел
Для получения какого-либо конкретного ъ - кода Радемахера достаточно взять ближайшую сверху к. П степень числа ъ + 1 и, выбрав любые їх чисел, меньшие этой степени, записать их в столбцы в системе счисления по основанию S + і .
Пусть IX в: 3, s = I. Построим все неэквивалентные с точностью до перестановки столбцов 5 - коды Радемахера для этого случая: в 16, к. =4.
Здесь мы разбили строки кода Радемахера на 2 группы по 2 строки в каждой. Каждую из этих групп заменили на группу из 3 строк таким образом, что число единиц в каждой строке стало равным 4, причём столбцы подкода, образованного любой такой группой из трёх строк FCtt, ) - плана, равны тогда и только тогда, когда равны соответствующие им столбцы подкода, образованного соответствующей группой из двух строк плана Радемахера.
Введём некоторые вспомогательные понятия. Пусть R»RCK,S)-произвольный s - код Радемахера длины к. , t - натуральное число, s0 , ... , st - произвольные натуральные числа из множества {.0,1,...,5} . Нетрудно заметить, что любая подматрица М х ПРИ X t Х0 t содержит каждый из С s + і) столбцов высоты t , состоящих из чисел 0,1,..., ь , к. раз. Обозначим количество строк подматрицы М через Т . Аналогично, М содержит каждый из С 5+ І) столбцов высоты Г , состоящих из чисел 0,1,..., 5 , С s + l) к раз.
Обозначим через L матрицу, составленную из к. одинаковых столбцов высоты t , представляющих собой запись в столбец цифр числа ju. ( = 0,1, ... , cs-vi) - I ) в системе счисления по основанию $ +1. Выпишем последовательно одну за другой все Cs+i) матриц 1м и полученную матрицу обозначим через М 0 . Припишем сверху к матрице М ма трицу М0 и результат обозначим через М .
Матрица М содержит t + r cjs + i l строк и (s+i) -к столбцов, которые попарно различны. Элементами М Л являются числа 0,1,..,, s . Следовательно, М является "о - кодом Радемахера. Доказательство теоремы 1.2 основано на построении FCn.,K_b л плана, исходя иг Ъ - кода Радемахера М , где натуральное число t однозначно определяется из условия (s + i)t-i 4 а/к. Cs +. Для каждого X = о, ... , Х0 - I построим матрицу М \ Г ч-к 1 составленную из а столбцов высоты Все координаты каждого столбца нулевые, за исключением, быть может, одной, равной где е С S3 , и в М каждый такой столбец входит не более К раз. При этом два столбца в М равны тогда и только тогда, когда равны два столбца с соответствующими номерами в М . Понятно, что в каждой строке М . число t є si содержится не более к. раз.
Аналогичным образом построим матрицу М . Она будет Коор П - К CS + l) t_t: состоять из и столбцов высоты K--S динаты каждого из этих столбцов либо все нули, либо все, за исключением одной, равной I , где е t$3 Каждый такой ненулевой столбец входит в М л, не более к. раз, а нулевой столбец - не более С 5 +і) -к: раз. Столбцы в п. располагаются таким образом, что из условия равенства двух столбцов в М х следует равенство соответствующих столбцов в М , В каждую строку М х число t & L s входит не более к раз.
Отметим, что указанными свойствами матрицы М0 , г\ t , ... , МЛ определяются, вообще говоря, не однозначно. Для нас важно, что такие матрицы всегда найдутся. Выпишем последовательно матрицы М 0 , М t ,... ,М одну под другой и ре / зультат обозначим через М . Понятно, что М является детектирующей матрицей, пос кольку все столбцы в М , а значит и в М попарно различ ны. В каждую строку М число L L ь! входит не более к: раз.
Границы длин К и ЫСп.,4К.) -кодов
Множество всех столбцов разбивается на классы эквивалентности по отношению подобия. Ясно, что мощность каждого такого класса является делителем числа N . Матрицу, составленную из всех столбцов одного класса эквивалентности, назовём блоком. Каждое из чисел 0, I, ... , Ъ встречается во всех строках блока одинаковое число раз.
Рассмотрим блок размера N N , порождённый столбцом, на первых L Ы местах которого стоят единицы, а остальные числа - нули. Нетрудно показать, что для любого натурального числа можно выбрать г столбцов этого блока так, что число единиц в любых двух строках матрицы, образованной этими t столбцами, будет отличаться не более чем на I. Эту матрицу мы будем называть неполным блоком.
Лемма 1.4. Для любых натуральных чисел Ы71 Ы,т.4 ) существует детектирующая (0,1) - матрица размерами N tn , каждый столбец которой содержит единиц, а число единиц в любых двух строках отличается не более чем на I.
Построение указанной детектирующей (0,1) - матрицы производится блоками с использованием в случае необходимости в конце подходящего неполного блока. В. Bollo&cxs , J. Ccxtcxm-ios , Gr. K.a_torux , T . Neraetz. , &. StctSE независимо показали [35] -, что при п. / jr клк,+ п + і
В обзоре С17] приведено наиболее простое известное доказательство этого факта. А.Г.Дьячков поставил нам задачу получить аналогичный результат для произвольного s Теорема 1.3. Справедливы неравенства: Доказательство. По определению NCti, 4 к.) - кода общее количество его чисел, отличных от нуля, не превосходит М- С К-» .
Обозначим через п. г количество столбцов кода, содержащих ъ ненулевых чисел, Ч- = О, I, Пока Отсюда следует первое неравенство. Пусть жем, что тогда существует F ( п , 4 к. ) - план размера N п., Пусть число tets3 такое, что K /. Обозначим через
Гч t детектирующую матрицу, содержащую столбцов высоты N , состоящих из N - 2 нулей и двух чисел, равных , причём количество в любых двух строках отличается не более чем на единицу. Поскольку и по лемме 1.4 М р_ существует. Отметим, что если хотя бы одно из чисел N или к. і - I четно, то в каждую строку число I входит ровно к. t - I раз. Если N и К- - I нечётны, то в N - I строку і входит К. t - І раз, а в одну строку К t - 2 раз.
Выпишем последовательно один за другим нулевой столбец высоты N , s N столбцов высоты Ы , содержащих по одному ненулевому элементу s} , матрицы М. і для tecs] таких что К-о 2. Если N нечётно, то рассмотрим числа для которых к. t - і нечётно. Обозначим эти числа Пусть L е ( 8 є [ г] ) - номер строки матрицы М , в которую число 2 раз. Матрицы М ( в ИЗ ) можно выбрать такими, что добиться, например, переставляя строки матриц П р_ ). Выпишем тогда после столбцов высоты N таких, что столбец с номером [ V i \ 3 содержит ровно два ненулевых элемента 2,1-1 и її расположенных в позициях і-г,_1 и il, .
В результате получим некоторую матрицу CVC[ , составленную из некоторого количества столбцов m и N строк. Если N или і четно, то в каадую её строку число t е cs] входит к.е раз. Если N и і нечётны, то это утверждение также остаётся справедливым, за исключением строки с номером и числа L х , которое входит в эту строку
Оценим m. . Рассмотрим матрицу TY\ , составленную из матриц М1 , ... , М. s и добавленных к ним \-т \ столб цов. Каждая строка tf)T содержит L- К-е.- -) ненулевых элементов, исключая быть может строку с номером L г , которая мо ь жет содержать Li t -) " ненулевой элемент. Поскольку каждый столбец еЩ содержит 2 ненулевых элемента, то их число равно
Рекуррентный метод получения верхних границ
Таким образом, мы показали эквивалентность двух задач. Следовательно, N Cn., nrO = N Cn,m). (2.9) Дальнейшее изложение будем вести на языке теории планирования отсеиващих экспериментов. Из соотношений (2.3 - 2,6) и (2,9) получаем следующие тривиальные нижние границы для N(v\,m.y.
Неравенствам (2,10 - 2,12) можно дать простую геометрическую интерпретацию. Будем изображать множество пар С ={ С ее, Ь) аеА, Ь} = А Ь прямоугольником на плоскости lb. , а пару (с- , Ь ) - клеткой этого прямоугольника. Предположим, что в некотором эксперименте мы выбрали подмножества A L = А ftL s Ь . Пусть ч - результат эксперимента. Если и = 2, то дефектная пара элементов находится в выбранном множест ве пар С = Л1 . Если Ц = I, то эта пара находится в множестве
Так как после каждого эксперимента количество клеток множества С , среди которых находится та, что отвечает дефектной паре, в одном из трёх случаев уменьшается не более чем в 3 раза, то справедлива оценка (2.10). Так как после каждого эксперимента количество элементов множества В , среди которых содержится дефектный, в одном из случаев уменьшается не более чем в 2 раза, то справедлива оценка (2.II).
Пусть п = Г 1 7 пп - і t рде XSJ - натуральное число, R.j_ и В.;. - положительные действительные числа, ( V. , R а ) будем называть парой допустимых скоростей при блоковой передаче информации с обратной связью по суммирующему каналу множественного доступа, если найдётся такое натуральное N 0 , что при N / N 0 выполняется неравенство: М" С х, яг.) 4 N . Множество пар ( & j. » R- ) допустимых скоростей образует на координатной плоскости О R L R. область пропускной способности канала. Неравенство (2,16) устанавливает нижнюю границу J? Q. L этой области при блоковой передаче информации. На рисунке 0,2 (стр. 12) приведена для сравнения её простейшая верхняя граница (граница кооперативного кодирования), соответствующая неравенству (2.5).
Действительно, пусть I -М= Ч ь у \Ъ\= m m. . Разделим множество А на частей по п. г элементов, а множество - 55 ft - на па t , по п\ г, элемента в каждой части. Проделав N ( ft t, па1 ) экспериментов, мы узнаем, в каком из a - т. прямоугольников множества С = К & находится дефектная пара и за N ( п. , m ) экспериментов выделим её из этого прямоугольника.
Воспользовавшись предложением 2.1 и тем, что Ы (2.,5) = получаем (2.13). М.В.Меньшиков и М.НДромов [22] показали, что N (9,14) = 5, и получили оценку (2.14).
Находя значения t = М (К.Д) при больших (специально подобранных) К и , оценку (2.14) можно улучшить. Однако, даже незначительные улучшения требуют трудоёмких вычис-» лений, которые при больших к и t оказываются практически невыполнимыми.
Так как всякое ограниченное сверху подмножество действительных чисел иглеет точную верхнюю грань, то существует
Покажем, что «С = и. т. п. . Зададим ся произвольным О и подберём к. -, IN таким образом, чтобы выполнялось неравенство оС С к. , С) , -. .
Пусть t = МСк.,П . тогда оС (к. Д) = 4к . Воспользовавшись предложением 2.1, получим: Последовательность оС(п.Лп) ограничена: ( , 1) 0 Следовательно, существуют нижний и верхний пределы: сначала к нижнему, а потом и к верхнему пределам, получим: оС , / «I , t у L. Так как число t о выбирается произвольно, то оС= оС = . Следовательно, существует предел Покажем теперь, как можно получить верхнюю границу для величины КГ ( tx7ra ) , если известна аналогичная граница ддяЖгуь).
Ниже предлагается новый метод получения верхних границ величины N С п. 1 m.) , которые окажутся лучше известных оценок (2.13) и (2,14), В 2.3 строится несложный алгоритм, из которого следует, что с , Г = а,&2.&1! 771 ... .
Диаграммный метод получения верхних границ. Определение 2.2. Подмножества 2) , 2) s С называются независимыми, если Эксперименты будем проводить таким образом, что после каждого из них область возможного расположения дефектной пары будет состоять из нескольких независимых квадратов - подквадра-тов квадрата С ( n= m ). Они будут либо все одинаковые, либо двух видов, причём в последнем случае стороны больших квадратов будут в 2 раза длиннее. При проведении нового эксперимента каж V» / / / дни такой подквадрат С = А Е будет разбиваться совершенно аналогично тому, как это происходило с самим квадратом С при проведении одного эксперимента ( рис, 2.1 ). Точнее, всякое разбиение квадрата С индуцирует разбиение на квадрате С :
Отметим, что и всякое разбиение некоторого числа независимых подквадратов квадрата С можно дополнить ( быть может неоднозначно ) до некоторого разбиения всего квадрата С так, что последнее будет индуцировать на этих подквадратах первоначальное разбиение. Именно в силу последнего обстоятельства разбиения независимых квадратов (подквадратов квадрата С ) можно производить независимо друг от друга.
Случайные планы экспериментов для линейной модели с условием несоизмеримости факторов над 1-1-,0-,1]
Множество ІК действительных чисел является бесконечномерным векторным пространством над полем рациональных чисел (& . При этом u) L , ... , э n R линейно независимы тогда и только тогда, когда они несоизмеримы над 1L . Пусть М. - конечное подмножество в R . Произвольный максимальный набор М г линейно независимых векторов из П называется базисом М . Любые два базиса ҐІ равномощны. Количество элементов в М г называется рангом М и обозначается
Построение плана экспериментов. Построение последовательного плана экспериментов осуществляется в 2 этапа. Проводится серия из Г too г п. 1 экспериментов. Зада дим их строками произвольного 2 - кода Радемахера X. длины
Пусть Ч - результаты экспериментов I этапа ( І є [Г loo и 1 ] ) Рассмотрим произвольный набор чисел Утвервдается, что и, , ... , UL несоизмеримы над 4L тогда и только тогда, когда они несоизмеримы над множеством
Покажем, что они будут также соизмеримы и над А. . Обозначим через М подмножество в В. , состоящее из тех и только тех ненулевых действительных чисел, которые содержатся в наборе (отметим, что в наборе U . , ... , и. одно и тоже действительное число может встретиться несколько раз, а в JM оно войдёт лишь один раз). Рассмотрим произвольный базис М , в М . Пусть неизвестные нам номера всех значимых факторов ; . Имеем:
Следовательно,
Обозначим через X. подматрицу матрицы X , образованную пересечением строк с номерами и столбцов с номерами Так как п 0 О , то из (3.2) следует, что её строка ї 0 принадлежит линейной оболочке остальных строк. Покажем, что строки матрицы X с номерами линейно независимы. В самом деле, если для некоторых , целых чисел m t X , неравных нулю однов ременно, то что невозможно, поскольку набор Mr = [ 4У » 9 У у } (.о) г? СР) является базисом в М . Пусть строки матрицы Л . Тогда векторы X , ... , х Ч линейно независимы и X є Q к. принадлежит их линейной оболочке. Согласно следствию 3.1 найдутся целые числа такие что причём n.0 О . Но тогда С / x v і = ДОЯ всех ft L к. ] и то есть у , у ,..., соизмеримы над А . Поэтому L , ... , L также соизмеримы над А . і Замечание. Из приведённых выше рассуждений следует, что если набор результатов экспериментов несоизмерим над 7L (или над А. ), то 9 к. .
Действительно, строки соответствзпющей матрицы X линейно независимы и их количество Р не превосходит количества столбцов К- .
Обозначим через У множество, состоящее из ненулевых действительных чисел, которые содержатся в наборе U и Выберем в У базис У ( = I u. ....
Это можно сделать, например, по очереди перебрав числа из Ч и выбрав те из них, которые соизмеримы с предыдущими над А. . Для каждого найдутся целые числа ft0 t 11 »«» а t такие, что е CL Имеем: и в силу несоизмеримости факторов над если Удалим из матрицы X строки с номерами и все столбцы с номерами I такими для некоторого
Утверждается, что в полученной матрице X 0 все столбцы будут попарно различны. Действительно, если это не так, то найдутся два столбца в X с номерами і . + і такие, что X = при. Посколь ку все столбцы в X попарно различны, то xi0li xi \ для некоторого. Так как и то отсюда следует, что по крайней мере одно из следующих двух равенств не выполнено:
Поэтому хотя бы один из столбцов с номером или будет вычеркнут из X и не войдёт в X 0 что противоречит предположению.
Итак, после завершения анализа серии из Г iocj п. 1 экспериментов мы получили (0,1) - матрицу X 0 размерами С0х т0) столбцы которой попарно различны и соответствуют факторам, среди которых содержатся все значимые, а строки соответствуют экспериментам, результаты которых несоизмеримы над А. .
Справедливы неравенства: Действительно, m_m. С К- Я п! ) к. и 10 Г СскипЛ. Неравенство t о -К- следует из сделанного выше замечания.
Матрица X 0 получена из X вычёркиванием столбцов, соответствующих незначимым факторам. Поэтому все значимые факторы соответствуют некоторым столбцам в X о . Поскольку число столбцов матрицы Х0 равно пг0 , а число значимых факторов равно к. , то к 4 m 0 . Так как все столбцы в X о попарно различны, то т0 4 2, . II этап. Последовательное планирование в дальнейшем проводится по следующей схеме.
