автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Алгебраические свойства матриц планов экспериментов

Р Г Б ОД

2 Ц АПР 1995

МОСКОВСКИЙ ПЕДАГОГИЧЕСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени В.И.ЛЕНИНА

Диссертационный Совет К 053.01.16

На правах рукописи

ИЛЛАРИОНОВ Владимир Владимирович

АЛГЕБРАИЧЕСКИЕ СВОЙСТВА МАТРИЦ ПЛАНОВ ЭКСПЕРИМЕНТОВ

05.13.17 — теоретические основы информатики, 01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва — 1995

Работа выполнена в Московском педагогическом государственном университете им. В.И. Ленина.

Научный руководитель:

доктор физико-математических наук А.М. САИНЬКО

Официальные оппоненты:

доктор физико-математических наук, профессор А.В. МИХАЛЕВ

доктор физико-математических наук И.И. ЦИТОВИЧ

Ведущая организация: Институт проблем передачи информации РАН.

Защита диссертации состоится ......1995 г. в

часов на заседании Диссертационного Совета К 053.01.16 по защите диссертаций на соискание ученой степени кандидата физико-математических наук в Московском педагогагческом государственном университете им. В.И. Ленина по адресу: 107140,Москва, Краснопрудная ул., д. 14, математический факультет МПГУ им. В.И. Ленина, ауд. 301.

С диссертацией можно ознакомиться в библиотеке МПГУ им. В.И. Ленина по адресу: 119435, Москва, Малая Пироговская ул., д. 1.

Автореферат разослан «..<.£,..»......./..„..........1995 года.

Ученый секретарь иссертационного Совета Э.И. КУЗНЕЦОВ

ОЕЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Большой вклад в разработку теории решения задач поиска внесли А.Г.Дьячков, Г.Катона, М.Б.Малютов, Л.Д.Мешалкин, А.Реньи.

Для решения ряда задач поиска проводятся эксперименты, которые называются отсеиЕащими. При этом желательно минимизировать экспериментальные и вычислительные затраты. Разработкой методов отсеивания существенных факторов занимается раздел математической теории поиска, называемый планированием отсеивающих экспериментов.

Диссертационная работа посвящена одному из направлений в теории планирования отсеивавдих экспериментов. Это направление связано с поиском существенных факторов в линейной модели. В данной модели рассматривается линейная функция вида

у = е1х1+...+ 9п^п , (1)

в которой з<п коэффициентов из 61,.-., 8п отличны от нуля. Необходимо найти номера этих существенных или значимых коэф-

фициентов и их; значения.

Для решения этой задачи поиска проводятся тт тестов. В кавдом тесте переменные х^, ,...,п принимают значения из фиксированного множества {0,1,... ,д-1}, называемого алфавитом. В практических приложениях также используются алфавиты вида (-1,...,-1,0,1,..I), либо {-£,...,-1,1П. В этом случае полагают д=21+1, либо q=2l соответственно. В результате получают систему линейных уравнений вида

У(В)=Х-В, (2)

где Х=5хи1, г^еСОИ.....д-1}, е=(81,...,91г)г, Ы.....и,

/=1.....п, причем только а<п компонент вещественного вектора

8 отличны от нуля.

Матрицу X называют матрицей плана эксперимента и она для решения системы (2) должна обладать свойством разделения: для любых векторов в(2', у которых не более чем а не-

нулевых координат и у которых координаты принадлежат, возможно, некоторому подмножеству множества вещественных чисел, имеет место Х-8(1V Х-е(2).

Первоначально были предложены эвристические алгоритмы поиска существенных факторов в (1), основанные на методе случайного баланса1, который является сочетанием метода случайного конструирования матрицы плана X и упрощенного метода пофакторного анализа.

Л.Д.Мешалкин обнаружил2, что при выборе существенных коэффициентов линейкой функции вида (1) из абсолютно непрерывного б-мерного распределения возможно построение матрицы вида X для решения системы (2), обладающей свойством разделения для одного подмножества множества индексов {1.....п.).

При этом матрица плана X должна обладать следующим алгебраическим свойством: столбцы матрицы с номерами, совпадающими с номерами существенных факторов, должны быть линейно неза-

1Satterthwaite Р.Е. Random Balance Experimentation // Technometries, 1959. Ш.

2Мешалкин Л.Д. К обоснованию метода случайного баланса // Заводская лаборатория. 1970. Вып.З. С.316-318.

висимы, а каждый из оставшихся столбцов линейно не зависит от указанных столбцов. При

т > з + logg(n-a+1) - lof^ß (3)

возможно построение двоичной матрицы с вышеуказанным свойством, причем доля соответствующих матриц в общем ансамбле т*п двоичных матриц не меньше 1-ß, G<ß<1. Решение системы (2) в этом случае возможно только при случайной генерации матрицы плана эксперимента. Работа. Л.Д.Мешалкина2 была первой попыткой теоретического обоснования метода случайного баланса.

В общем случае для решения системы (2) необходимо и достаточно* чтобы матрица X обладала следующим свойством: любые 2з ее столбцов должны быть линейно независимы3. Матрицы g таким свойством называют йв-невырожденными. Построе-ение таких матриц является сложной задачей. Необходимо также знать, при каких параметрах т,п и з существуют 2а-невырон-денные матрицы.

М.Б.Малютов показал*, что при

т > 23+10^ [у (4)

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

1 - (L]2_m+2e- <5>

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

3Srivaatava J.N. Designs for searching nomegligable effects / In: A surrey of statistical designs and linear models. Amsterdam: North-Holland Puhl., 1975. P. 249-256.

4Малютов М.Б. Математические модели и результаты в

теории отсеивающих экспериментов / Вопросы кибернетики. М.: Сов. редко. 19ТТ. Вып. 35.

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

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

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

Методологическую основу работы составляют современные метода комбинаторного анализа, теории кодирования, целочисленного программирования.

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

Апробация работы. Результаты исследования докладывались на научно-методическом семинаре кафедры информатики и дискретной математики МПГУ им.В.И.Ленина, на международной конференции "Современные проблемы теории чисел" в г.Туле (сентябрь 1993 г.).

Структура и обьем диссертации. Работа состоит из введения, двух глав, заключения и списка использованной литерату-

5Вычислителызые сети (адаптивность, помехоустойчивость, надежность) / Самойленко G.M., Давыдов A.A., Золотарев В.В., Третьякова Е.И. М.: Наука. 1981.

ры. Она содержит 102 страницы основного текста, 53 наименований использованной литературы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава является вспомогательной, вторая глава содержит основные результаты.

В § 1.1 рассматривается одна общая схема задач поиска. Большое количество задач поиска можно формализовать следующим образом. Пусть К - некоторое коммутативное кольцо с едицицей 1. Через Ьп , где обозначим множество векторов-столбцов х=(х1,...»я )г с координатами из I. Весом »(г) вектора х (в смысле Хэмминга) называется число его ненулевых координат. Через

п

(х,у) = 2 х1у1 {=1

обозначим скалярное произведение векторов х и у. Если Хс^1 к ней", то отображение Х-+К, определяемое по правилу

tu: х-*[х,и), хаХ,

назовем тестом. С помощью тестов моделируют некоторые элементарные акты процесса поиска.

Совокупность тестов Е=Н У назовем эксперимен-

1 та

том, 1/в =(и1.....и^У - планом эксперимента,

матрицей плана эксперимента. Результаты эксперимента характеризуются вектором отклика

'где у {х)=Ц {х))т .

1 та

Задача поиска. Пусть имеются два подмножества в Е": область поиска X и область допустимых экспериментов В. Требуется найти такой план эксперимента и' = В, чтобы отображение-отклик ув : х-*-уЕ(х) было инъективным.

Кратко приведенную выше задачу будем записывать в виде тройки . План эксперимента Е будем называть опти-

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

Для всякого подмножества ХсЕ™ введем обозначение:

Lg=íxЩw(x)^8}.

Важный частный случай задачи поиска У возникает в случае,

когда , где з<п. В этом случае удается получать планы,

являющиеся решениями и имеющие значительно меньше тестов, чем размерность вектора п. Совокупность тестов Е в этом случае называют также отсеивающим экспериментом, а построение подходящего плана - планированием отсеивающих экспериментов.

Задачу поиска

где ^(д)={0,1,...,о-1}, назовем линейной моделью. Множество будем называть алфавитом задачи поиска или просто алфавитом. Целое положительное число д будем называть мощностью алфавита.

Множество шп матриц с элементами из алфавита бу-

дем обозначать через Ма1 (д).

Пусть Р - поле. Известно? что план вксперимента и =1) является решением задачи поиска ,В) тогда и толь-

ко тогда, когда матрица плана эксперимента ЛЕ является йене Еыровде иной.

В § 1.2 рассматривается линейная модель задачи поиска. Пусть для решения задачи поиска (6) имеется план V и вектор отклика уЕ(х). Тогда решение задачи Ц> можно рассматривать как решение системы

(6)

{

Аях = УцЮ

(?)

и>(х) £ а ,

где а^еЛ(д), 1=1.....яг, /=1,...,?г, ш=|{/я|.

Положим для 2^п

д[0) = к + 1о0(?(д . (8)

Величина т(0) задает границу существования й-невырожденной матрицы из множества и является обобщением границы

(4) для д-ичных матриц.

Отметим, что проверочная матрица линейного кода над <?Р(р), где р - простое число, является и матрицей соответствующего плана эксперимента, так как является (сМ )-невырожденной матрицей и над полем К, где параметр <1 есть минимальное расстояние соответствующего линейного кода. Введем величину

к-1 {=0

Величина называется границей Варишова-Гилберт для линейной модели при й=2з. В теории кодирования доказано6, что существуют линейные кода, достигающие границы Для

простых д граница т11) рассматривается как граница существования й-невкрожденной шп матрицы, для других д - как формальное выражение.

Предложение 1.2.1. Илеш лесто свойства:

(I) й<1) < т10) ,

(II) тп) ~ т(°[пря к-*сс, й=о(п).

Таким образом, границы т(0) и т(1) эквивалентны при к-хх>, й=о(п) и обе задают границу сверху для оптимального плана эксперимента в линейной модели с учетом ограничений на мощность алфавита д.

бПитерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976. 594 с.

В случае бесконечного поля F задача

Ц> = (fl,JFr' ,D) (10)

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

Вещественные числа 9,...,8 называют неаоизлеримнжи

над множеством h'-Z, если из . .+7^6^=0, где ?уЕЛ, следует Я,9д=0, J=1

Будем говорить, что матрица ...|ип) удовлетворяет

свойству Рт, где !=£{,,...,£ }, «п, если для лю-

J. ISIS

бого индекса J/I система столбцов iv .....v, ,vА линейно

1 а

независима. Матрица со свойствам ?х обладает свойством разделения только для одного, совпадающего с I, набора существенных компонент вектора х, значения которых выбираются из некоторого абсолютно непрерывного распределения2, к может быть применена при случайном поиске в случае несоизмеримости4 компонент вектора х над множеством 1. Положим

mQ = s + logq(n-s+1). (11)

Величина mQ задает границу существования матрицы из множества Mat {q) со свойством Рт и является обобщением границы

77ЦСТХ -L

(3) для q-ичных матриц.

Будем говорить, что матрица А удовлетворяет условию

Pjk), если всякая ее подматрица AJf состоящая из столбцов

матрицы А с номерами из множества J, где и \J\=k, имеет линейно независимую систему столбцов.

Возможность решения задачи поиска (10) с помощью матри-

цы плана со свойством вытекает из несоизмеримости координат вектора х в (7) над некоторым конечным множеством целых чисел7.

В § 1,3 рассматриваются основные свойства линейных комбинаций векторов с компонентами из конечного алфавита.

Алгебраические свойства матриц планов отсеивакщих экспериментов связаны с линейной независимостью векторов-столбцов матриц планов. Особенностью линейных комбинаций таких векторов является принадлежность компонент векторов фиксированному конечному целочисленному множеству.

Множество гя-мерных векторов с координатами из множества si(q) обозначим через F (q).

Пусть задана система из к векторов размерности т, принадлежащих множеству 7 (q). Рассмотрим событие X . состоя-

TU Hl« А

ящее в том, что при случайном выборе вектора veVm(q) полученный вектор есть линейная комбинация заданных векторов. Вероятность события й определяется количеством .линейных комбинаций вида

С1У1+.,.+GkVh=V, (12)

где с{€®, о ,иеУ (д>. Следующее предложение показывает, что вероятность ?{Хп есть функция от матрицы, образованной к векторами-столбцами v,

Предложение 1.3.1. Млеет лесяпо неравенство

»+1 )q"® i PCX Л С q~v*h , Ш-1.

^ m» r л

В § 2.1 рассматривается уравнение

а,£„+...+а х = Ь , (13)

11 п п

где a{,ö ( Z, afО, a xl(M(q), 1=1,...,п идй есть фиксированное целое полонительное число.

7Олинько A.M. Дефекты матриц планов экспериментов / Статистические модели и методы. Сб.трудов. М.:ВНЖЖ. 1984, вып. 1. С. 93-102.

Необходамость изучения уравнений вида (13) вызвана тем, что существование линейной комбинации векторов вида (12) с компонентами из ,#(<?) влечет существование решений уравнений (13).

Обозначим через 1п ^(а^,...,о-п,Ь) число решений уравнения (13). Положим

ша* ¿«.¿Ъ.....•

а1,ьег

Нас будет интересовать асимптотика величины Лп при п-*<и, д=сог^, а также невсимптотическая оценка сверху. Получена следующая асимптотика максимального числа решений уравнения (13).

Теорема 2.1.2. Пусть д=сопзг. Тогда при л.-**»

j „ /—э--:— .

/ тПГ

Оценка сверху для максимального числа решений уравнения (13) имеет следующий вид.

Теорема 2.1.3. Для мхка целых rte 1, q$2.

J < qn/-/rT .

п. q ^

В § 2.2 рассматривается ряд лемм, необходимых для получения основных результатов.

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

Пусть задано множество матриц Mat^^q), где п>т, с введенным на нем равномерным вероятностным распределением. Обозначим через 7<я!,п,2г) вероятность получения fe-невыровденной матрицы при случайном выборе матрицы А из Mat (q), через

"\х{т,п,8) - вероятность получения матрицы со свойством ?1 и через т1(тгп,8,к) - вероятность получения матрицы со свойством при случайном выборе матрицы А из множества Маггахг(д) для некоторого фиксированного 1<=п,...,п), \1\=з.

Теореиа 2.3.2. Для любого 0<а<1 существует й0=й0(д,а), такое, то при

7х(т,тг,з,й) > 1 - (Дй"1^ _ (14)

Полученная оценка улучшает соответствующую оценку7

тх{п,п,3,к) > 1 -[1 + Ц:®]]*?-*1^-1

с учетом ограничений на параметры й и в.

При й=з+1 из (14) получается оценка для 71(и,п,з), а

при з=0 - оценка для у(т,п,к), которая улучшает оценку (5).

Далее рассматривается один конструктивный способ построения планов со свойством Рх и минимальной относительной трудоемкостью, под которой пониматся отношение числа строк к числу столбцов матрицы плана эксперимента.

Теорема 2.3.3. Пусть задано Для, любого 1сС1,...,п),

\1]=з, существует (0,1 )-лащлща со свойство* Рх и паражт-рали

т=з+1, п=20+1-1. (15)

Отметим, что матрица, построенная в теоремб 2.3.3, является вещественным аналогом проверочной матрицы кода Хэмминга над £Р(2) с параметрами (2да-1,2та~я-1) и потому имеет конструктивное представление. Матрица со свойством Рх,

имеющая параметры (15), является оптимальной и обеспечивает относительную трудоемкость приблизительно в два раза меньшую по сравнению с соответствующей трудоемкостью матрицы, достигающей границы т0, определенной в (11).

В § 2.4 рассматриваются асимптотические свойства матриц планов отсеивающих экспериментов. Основные результаты этого параграфа состоят в том, что для всех введенных в § 1.2 границ ml0), m(1), mQ (см.(8),(9),(11)) доля соответствующих матриц в множестве Mat (д) стремится к 1 при возрастании

7n,n,s и определенных ограничениях на параметры планов.

Дополнительно рассматриваются асимптотические оценки мощности оптимальных планов экспериментов, соответствукщих ^-невырожденным т*п матрицам при фиксированном отношении РУп и п-х». Данная асимптотика является наименее изученной и соответствует асимптотике наилучших известных кодов.

Теорема 2.4.1. Пусть задано фиксированное а>0 и т, п, s связаны, соотношениями smiog^n, v&mQ. Тогда

Ilm 7х(т,п,в) = 1.

1Л,,П,вХ»

Теорема 2.4.2. Пусть задано С«к1 и я, п, й связаны соситошенияли: &öcт, - Тогда

lire 7(m,n,k) = 1.

m,n,Äx»

В теореме 2.4.4- выполняется уточнение границы т<-0) для случая &/n=const. Доля й-невкрождвннях матриц во множества MatTOsn(g) также будет стремится к 1 цри п-*» и для уточненной границы.

Введем следущее обозначение функции двоичной энтропии:

h(x) = -slogan - d-xjlo^d-i), , h(0)=ft(1)=1. Определим функцию

Теорема 2.4.4. Путь задано 0<а<1. Для любого Cke<ßq(a) при ö=l+ßq(a)-s, и&Ь~1т(0)

Ilm у(т,п,ап) = 1.

т,тъх»

Непосредственнш следствием полученного результата является существование ^-невырожденных матриц при и достаточно больших п, а значит, имеется асимптотическая оценка мощности оптимального плана при й/п=сопвг.

Следствие. Пусть задано 0<а<1. Тогда Зля любого

0<8<{3 (а) при п~*<х> и й/п=а илет лвсто оценки.

(1) N $ (1+рч(а)-е)-1я(0);

(И) Ж $ (1+Рд(а)-ЕГ'1 (а+П(а)1овч2)п(1+с(1)).

Таким образом, выполнэно асимптотическое улучшение границы стС0) при фиксированном й/г<,.

При больших ограничениях на параметр а возможно дальнейшее улучшение асимптотической границы мощности оптимального плана эксперимента.

Пусть а(0) - положительный корень уравнения

х1о^д - Щ.т) = 0. Положим а0=®1п{а10),1/2}.

Теорема 2.4.5. Для любого 0<а<ао при и к/п=а

где

N ^ тЛ(а)108 2(1+0(1)). Следствие. При 0 <а<ап, £Уп=а и г?-*» N * (1+5(а,д))-1тп)(1+о(1)),

Л(а)

Следует отметить, что улучшение границы ' происходит только для недвоичных алфавитов, так как я(а,2)=0.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1) Получены новые оценки параметров матриц планов экспериментов для линейной модели задачи поиска.

2) Исследовано одно линейное целочисленное уравнение, которое связано с существованием линейных комбинаций векторов с компонентами из конечного алфавита. Получена асимптотика максимального числа решений такого уравнения и неасимптотическая оценка сверху.

3) Рассмотрено одно конструктивное представление матрицы плана эксперимента, обладающей свойством разделения одного набора индексов коэффициентов линейной функции в случае несоизмеримости искомых коэффициентов над множеством целых

чисел.

4) Получены новые асимптотические оценки мощности оптимальных планов экспериментов в линейной модели при фиксированном отношении числа линейно независимых столбцов матрицы плана эксперимента к числу всех столбцов этой матрицы.

Публикации, содержащие основные результата диссертации:

1. Илларионов В.В. О случайных 0,1-матрицах сверхнасыщенных поисковых планов экспериментов / В сб.: Ш Всесоюзная школа-семинар "Программно-алгоритмическое обеспечение многомерного статистического анализа". Часть I. Москва. 1987. С. 107.

2. Илларионов В.В. Об оценках числа решений одного целочисленного уравнения / Труды международной конференции "Современные проблемы теории чисел". Тезисы докладов. Тула. 1993. С. 65.

3. Илларионов В.В. Об оценках числа решений одного целочисленного уравнения // Мат. заметки. 1993. Т.54, вып. 5. С. 57-64.

4. Илларионов В.В. О некоторых свойствах матриц планов отсеивающих экспериментов / Балашовский гос. пед. институт. Балашов, 1994. 26 с. Деп. в ВИНИТИ. 27.12.94. ü 3045-В94.