автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Моделирование процессов дискретизации многомерных неизотропных данных методами теории квантизации

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

Захаров Андрей Владимирович

МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ДИСКРЕТИЗАЦИИ МНОГОМЕРНЫХ НЕИЗОТРОПНЫХ ДАННЫХ МЕТОДАМИ ТЕОРИИ КВАНТИЗАЦИИ

05 13.18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ

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

Уфа 2004

Работа выполнена на кафедре математики Уфимского Государственного Авиационного Технического Университета

Научный руководитель: доктор физико-математических наук,

профессор Н.К.Вакиров

Официальные оппоненты: доктор физико-математических наук,

профессор Е.М.Бронштейн,

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

В.Х.Багманов

Ведущая организация: Институт вычислительной математики

и математической геофизики СО РАН

Защита состоится декабря 2004 года в часов минут на заседании диссертационного совета КР-212.288 26 при Уфимском Государственном Авиационном Техническом Университете по адресу: 450000, г.Уфа, ул.К.Маркса, 12.

С диссертацией можно ознакомится в библиотеке Уфимского Государственного Авиационного Технического Университета.

Автореферат разослан ноября 2004 года.

Ученый секретарь диссертационного собета доктор физико-математических наук, профессор

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

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

Общая задача квантизации в йп формулируется следующим образом. Пусть Т - некоторое связное подмножество Д". Пусть {^¡¿^ - набор N точек из Т. Каждая точка множества Т кодируется какой-нибудь одной точкой из этого набора. Ошибка кодирования точки Ь £ Т точкой измеряется некоторой неотрицательной функцией действующей из ТХ Т в Я1.

Пусть Д* - множество точек из Т, которые кодируются точкой к = Так как кодируются все точки Т, набор множеств об-

разует разбиение Т. Ошибка кодирования точкой измеряется интегралом / />(£,£ к — 1,. .. Общая ошибка кодирования множества Г точками

измеряется суммой

е*СП= £ I ры<и.

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

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

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

источника и последующего применения этого

модели-

КНМИОТЕКЛ I СйтЛЯКА" 1

о» т,Ушу ^

рования процессов адаптивной дискретизации основных типов непрерывных данных.

Задачи.

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

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

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

4) Построить иерархию моделей для различных частных случаев многомерных неизотропных данных.

5) Провести численные эксперименты моделирования показательных частных видов двумерных неизотропных данных, сравнить полученные результаты с результатами кластеризационного алгоритма Маккуина.

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

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

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

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

На защиту выносятся:

- квантизационная модель с функцией ошибки, локально приближаемой степенью выпуклой метрики, описывающая процесс дискретизации неизотропных данных с оценкой потерь информации;

- методы моделирования адаптивной дискретизации неизотропных данных в различных условиях:

- оценки потерь информации при дискретизации неизотропных данных в различных условиях;

- иерархия моделей для различных частных случаев многомерных неизотропных данных;

- результаты численных экспериментов моделирования частных видов двумерных неизотропных данных.

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

1. На международном конгрессе по кубатурным формулам (Уфа. 2001).

2. На международной конференции по кубатурным формулам (Красноярск, 2003).

3. На семинаре по теории вероятностей и математической статистике кафедры математики УГАТУ, руководитель проф.Ф.С.Насыров.

4 На городском семинаре по кубатурным формулам, руководители проф.М Д.Рамазанов, проф.Р.Р.Асадуллин.

5 На методическом семинаре Института математики с вычислительным центром УНЦ РАН, руководитель проф.Н.К.Бакиров.

Публикации. Основные результаты диссертации изложены в шести публикациях, среди которых одна монография ([1]) и пять статей ([2]-[6]). Работа [4] выполнена совместно с К.В.Симоновым и САПеретокиным. Из

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

Структура и объем диссертации. Диссертация включает в себя список основных обозначений, введение, пять глав, содержащих в совокупности 22 параграфа, заключение, список литературы, содержащий 147 наименований, в том числе ссылки на работы автора, помещенные в конце списка, а также два приложения. Общий объем диссертации 137 страниц.

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

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

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

Приведем определение асимптотически оптимальной квантизации.

Определение. Последовательность наборов {t*kN, с ошибкой

еМП N— 1,2,..., называется асимптотически оптимальной, если для любой другой последовательности ошибкой £лг[Т], N = 1,2,..., выполняется неравенство

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

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

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

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

Рис. 1. Метрика, порожденная выпуклым множеством

Пусть С - связное выпуклое множество в й", симметричное относительно какой-нибудь своей внутренней точки О. Пусть в и £ - произвольные точки К". При помощи параллельного переноса переместим множество С так, чтобы его точка симметрии О совпала с точкой 5 (рис.1). Пусть луч, выходящий из точки и проходящий через точку пересекает границу этого выпуклого множества в точке V. Определим расстояние между в и £ следующим образом:

\\t~sh

\\V-S\l2

где Ц.Ц2 - евклидова метрика (¿2)- То есть в качестве в) мы возьмем коэффициент, с которым мы должны увеличить множество С гомотетично относительно точки в, чтобы его граница прошла через точку

Расстояние полностью определяемое выпуклым множеством С,

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

Поместим начало координат в точку О, совпадающую с точкой я (рис.1). Для любого £ € Яп (кроме £ = в) направление от 5к( (по прямой) можно задать при помощи набора П — 1 углов ¡р = ((/З), </>2,..., ^п-0- Например, это могут быть углы обобщенных сферических координат (с центром в точке б). В любом случае мы будем предполагать, что эти углы (точнее, вектор Iр, состоящий из набора углов) зависят от точки £ непрерывно. Например, если один из этих углов, скажем <р1, изменяется на отрезке [0.27г]. и при движении точки ( 6 й" у го лпереходит из области [2я" — д, 27т] в область мы будем считать, тем не менее, зависимость от непре-

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

В дальнейшем направление от фиксированной точки к произвольной точке t (по прямой) будем обозначать переменной ¡р, соответствующей П — 1-мерному вектору, полагая, что ¡р зависит от точки £ непрерывно. Приведем теперь основное условие на функцию

A. p{t,s) = (<V,i||i-5Ц2Г + °s ((||i - ^Цг)0) при i-»sno прямой с направления, задаваемого набором П - 1 углов (/?, где - положительный коэффициент, зависящий только от tp и от S, причем от обеих переменных зависящий непрерывно, ограниченный сверху и снизу положительным числом, и такой, что при фиксированном i уравнение — йЦг = 1, t € Л", задает поверхность (линию), ограничивающую выпуклое множество, Ос - положительная константа.

Из вышеизложенного следует, что при фиксированном S функция = - метрика, порожденная выпуклым множеством. Условие

А требует, чтобы при фиксированном S функция p(t,s) могла быть приближена степенью метрики, порожденной выпуклым множеством. Показатель степени при этом отражает порядок малости функции при

Предположение о независимости О: от <£ и от S (от t) в условии А является достаточно естественным.

Определение. При фиксированной точке S поверхность (линия) p°{t,s) = C^sllf — йЦг = 1, t € Rn, вместе с показателем а называется (локальным) вариационным профилем функции в точке

Известным примером метрики, порожденной выпуклым множеством, является метрика Lp, 1 < р < 00. Из остальных метрик, порожденных выпуклым множеством, для теории квантизации важными являются также метрики, порожденные выпуклым множеством, из которого можно составить разбиение (или, по-другому, плотную упаковку, паркет) пространства

Приведем второе условие на функцию />(/,s).

B. Для любого 6 > 0 ^ inf > 0.

Оно дает возможность рассматривать в качестве асимптотически оптимальной квантизации лишь те последовательности {t^, N — 1,2,..., для которых ^ niax^ diam Д]^ —»0 при N —> оо.

Определение. Пусть - набор точек в Т. Для каждой точки

tk множеством Вороного в Г относительно метрики называется мно-

жество Ак = {f е Т : p°(t,tk) < p°(t,t}),j = I,..., к- l,k + l,...,N}, то

есть множество точек из Т, расстояние от которых до ijt не больше, чем до остальных точек набора

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

В третьей главе рассматривается случай, когда функция p(t,s) имеет один и тот же вариационный профиль на всем множестве Т (выполняется условие Л, и вид функции p°(i,s) не зависит от точки S). В этом случае коэффициент в условии А не зависит от S. Каждой теореме посвящен

отдельный пункт главы.

Теорема 1. Пусть дляфункции p[t,s) выполнены условия А и В (или же вместо условия В условие ^ мах^ diam Д^ —► 0 при N оо), причем вариационный профиль функциир(Ь, s) одинаков для всех s € Т. Пусть также границамножества Ткусочно-гладкая. Тогда в классерешетчатыхраспо-ложений точек {¿k}kLi (N — 1,2, ...) задача асимптотически оптимальной квантизации сводится к следующей задаче, которая имеет по крайней мере одно решение.

Задача. Найти параллелепипедР, для которого значение

минимально, где U,i =1,2,..., - точкирешетки, порожденной параллелепипедом Р, Д„г = 1,2,..., - соответствующие им множества Вороного в метрике pa(t,s) = — s||.

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

1) Заполнить по возможности множество Т параллелепипедами

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

2)Расположитъ точки в вершинах параллелепипедов внутри Т, оставшиеся точки расположить произвольно вдоль границыТ.

3) В качестве множеств {Д^}^ взять любой из вариантов разбиения Вороного множества относительно точек

Для ошибки асимптотически оптимальной квантизации верно равенство

(13)

Г-,*,- "Реш!

где Среш — inf Oj (Р) - константа, которая зависит, от поверхности (линии) вариационного профиля (как функции от обобщенного угла пространства функций с равномерной метрикой) непрерывно.

Определение. Паркетом называется разбиение пространства Л" на множества, которые могут быть получены друг из друга при помощи параллельного переноса.

Определение. Паркетом в Т С Я" назовем пересечение какого-нибудь паркета в Я™ и множества Т.

Теорема 2. Пусть дляфункции p{t,s) выполнены условия А и В (или

при причем

же вместо условия В условие

вариационный профиль функции р(1,з) одинаков для всех 5 € Т, и из выпуклого множества А*, которое порождает соответствующую метрику р°(/, б'), можно составить паркет в йп. Пусть также граница множества Т кусочно-гладкая. Тогда для построения асимптотически оптимальной квантизации достаточно в качестве множеств {Д^}^ взять плотную укладку копий множества в множестве Т (заисключе-

нием граничных множеств, в качестве которых можно взять произвольные множества с диаметром стремящемся к нулю при N —у 00), а в качестве точек точки симметрииэтихмножеств, соответствующие точке симметрии Д*, относительно которой строилась поверхность (линия) вариационного профиля.

Для ошибки асимптотически оптимальной квантизации верно равенство

точка симметрии Д* ¡относи-

тельно которой строилась поверхность (линия) вариационного профиля. Константа С0 зависит от поверхности (линии) вариационного профиля (как функции от угла пространства функций с равномерной метрикой) непрерывно.

Теорема 3. Пусть для функции p{t,s) выполнены условия Л и В (или же вместо условия В условие ^ max^diam Д^ —► 0 при N —> ooj, причемва-

риационный профиль функции p(t,s) одинаков для всех S £ Т. Пусть также граница множества Ткусочно-гладкая. Тогда существует вариант асимптотически оптимальной квантизации (t^, N = 1,2,..., для которого множества {Д^}^] являются множествами Вороного относительно точек

Для ошибки асимптотически оптимальной квантизации верноравен-

ство

ЫжМа/пен[Т} = С°\Т\а/п+\

где

С°> I ■ Ды*)Л, А')" '

Д* - выпуклое множество, порождающее метрику р(1,$),1' - точка симметрии этого выпуклого множества, соответствующая точке построе-

. С

ния метрики

■ (№)">)

- гомотети чное преобразованиемножества

Д* относительно точки V с коэффициентом ^ д)|д.| ^

Для формулировки следующей теоремы, введем дополнительный класс расположений точек квантизации. Его определение основано на следующем хорошо известном утверждении: в метрике, порожденной выпуклым множеством с гладкой границей, для любых трех не лежащих ьа одной прямой точек бисектор существует и состоит из одной точки. Это утверждение может быть переформулировано так: для любого невырожденного треугольника существует описанная вокруг него окружность в мегрике з), причем только одна. Заметим, что условие гладкости границы порождающего метрику множества существенно, так как существуют примеры метрик, порожденных выпуклым множеством с кусочно-гладкой границей, в которых бисектор трех точек не всегда существует.

Определим класс С(р ) расположений

л я метрики

р°(£, в), порожденной выпуклым множеством с гладкой границей, следующим образом. Будем говорить, что расположение точек С Яп принадле-

жит классу если существует триангуляция, построенная по этим точ-

кам, все треугольники которой содержат центр описанной вокруг них окружности в метрике /5°(?,5).

Если три точки образуют некоторый треугольник Б, содержащий центр описанной вокруг него окружности в метрике будем использовать

запись $ е С[р°).

Теорема 4. Пусть выполнены условия А и В (или же вместо условия В условие ^Юах^сНат Д^ —> 0 при N —> ОС), причем вариационный профиль

функции в) одинаков для всех Э € Т, имеет гладкую линию вариационного профиля. Пусть также граница множества Т С Н.' кусочно-гладкая. Тогда задача построения асимптотически оптимальной аппроксимации в классе расположений точек сводится к следующей задаче, которая

имеет по крайней мере два решения: найти треугольник Б, содержащий центр описанной вокруг него окружности в метрике 5), для которого значение е0м[О/\О\Х'2} = 1/|0|1+а/2^[0] = 1/|£|На/2 £ /рв(и,)А минимально, где ¿,,2 = 1,2,3, - вершины, треугольника О, Д,,? - 1,2,3, -соответствующие им множества Вороного в D относительно метрики

Ро(м).

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

1) Отразить И* симметрично относительно какой-либо точки, получить симметричный треугольник

2) Заполнить по возможности множество Т треугольниками \j24\D'\ В* и (этом некоторые треугольники могут выходить за границу Т, и некоторые приграничные области могут остаться непокрытыми треугольниками).

3)Расположить точки {t^}в вершинах треугольников внутриТ. оставшиеся точки расположить произвольно вдоль границыТ.

4)В качестве множеств { Д^'взять любой из вариантов разбиения Вороного множества Т относительно точек

Для ошибки асимптотически оптимальной квантизации верно равенство

г С° = 2 inf e%[D/\D\4*\ станта, которая зависит о т линии

вариационного профиля (как функции от обобщенного угла пространства функций с равномерной метрикой) непрерывно.

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

Пусть m(N) - положительная целочисленная функция от N, удовлетворяющая следующему условию.

Например, в качестве m(N) можно взять целую часть от y/N, На каждом шаге N разобьем Т на m[N) непересекающихся подмножеств .. с кусочно-гладкими границами:

таких, что ^ max^ diam щ —» 0 при N —♦ ОО, и среди множеств к — 1,..., m(N), не существует двух множеств T^^j, для которых

Теорема 5. Пусть для функции p{t,s) выполнены условия А и В (или же вместо условия В условие ^ шах^ diam Д^ —> 0 при N —> ос). Пусть

также поверхность (линия) локального вариационного профиля функции p(t, s) непрерывно зависит от точки S S Т (коэффициент cS:i, в условии А при любом фиксированном if непрерывно зависит от S ЕТ). Предположим

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

1. Построим разбиение множестШ наподмножестваТ^т^у к = 1,... .ш(Л^), согласноприведеннойвышесхеме.

2. В каждом измножеств Т/цд^, к = 1,... выберем,поодной точке^, к = 1,... ,т(И).По вариационномупрофилю в каждой из точек

вычислим значение

3. Введем функцию плотности

ш =

(С(0)

1/(1+«/«)

1Ш)

Т

1/(1 + о/л)

й

Пусть

приближение этой функции построенное по произвольным точкам 6 дг), <? которых было вычислено значение функциис(£) = С°(¿), £ 6 Т. 4. В каждом множестве расположим 72^,у =

точек оптимальным образом, как для оптимальной квантизации с равномерным источником для вариационного профиля, совпадающего с вариационным профилем функции р{1, в) в точке Здесь [.] - целая часть числа,

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

1ш л'а/п4[т] = / -4^-л.

1/-.00 1 ) „й/"м

Ы-мх

#"(0

Теперь рассмотрим случай квантизации неравномерного источника, при котором поверхность (линия) вариационного профиля в различных точках одной формы, но разного размера. В этом случае

(2)

где функция С~ определяет форму поверхности вариационного профиля, а функция С1 - ее размер в зависимости от точки Я. Везде в этом пункте предполагается, что функция непрерывна. Таким образом, множество можно разбить на достаточно мелкие подмножества, в каждом из котором можно приближенно считать источник квантизации равномерным. Разбиение Т на

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

Наряду сфункцией 5), удовлетворяющей(2).будемрассматривать функцию = — £¡¡2, которая задает вариационный профиль равно-

мерного источника. По определению — й).

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

Теорема 6. Пусть для функции , 5) выполнены условия А и В (или же вместо условия В условие ^ П1ах^ сЛат А^ —> 0 при N —► оо/, и пустъ

выполнено условие (2), где функция Сх ), I € Т, непрерывна, а функция с2(у) - непрерывная ограниченная положительная функция набораП—1 углов <р, задающая в обобщенных сферических координатах выпуклое множество. Пусть также граница множества Т - кусочно-гладкая. Тогда один из вариантов асимптотически оптимальной квантизации может быть построен следующим образом.

1. Найдем асимптотически оптимальную квантизацию на множестве Т' (достаточно большом, чтобы на нем умещалось любое множество И-3 ^ с ошибкой

где - разбиение множества на подмножеств, а

набор точек квантизации, соответствующий этому набору.

Пусть Д/^}^!, Л'1 — 1.2,..., - эта оптимальная квантизация, для которой, согласно теореме 3, верно равенство

2. Построим разбиение множества Т на подмножества к — 1,..., т(М), согласно приведенной выше схеме.

3 В каждом из множеств к — 1.... ,т{М), выберем по одной

точке к — 1,...,т(ЛГ).

4. Введем функцию плотности

Разместим теперь каждое множество в множестве Т' та-

ким образом и подберем номер такой, чтобы в множество его-

дило — \NgtjЩ|] точек из набора - Соберем из мно-

жеств Т^^щ множество Т, сохранив при этом расположение точек.

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

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

Для двумерного случая процесс дискретизации был численно промоделирован для общего типа метрик вида:

£(з,"е, ), в(х3)уа), порожденных ромбом с отношением горизонтальной и вертикальной диагоналей, равным

Для примера приведем асимптотически оптимальное (в соответствии с теоремой 2) расположение 35 точек квантизации для А = 3 (рис.2). Ошибка квантизации для данного расположения равна 0.146 ± 0.001. Асимптотическая оценка ошибки равна 0.138:Ъ0.001. Число выполненных вычислительных операций равно 175+7 (пять операций на каждую точку плюс семь операций для вычисления параметров сетки).

09 оа

ов

95 )«

аэ

33

О 01 04 ОС 0В I

Рис. 2. Асимптотически оптимальная квантизация

Рис 3 Алгоритм Макк\ина- 3500 итераций

Рис 4. Алгоритм Маккуина - 35 млн итераций

Для сравнения приведены результаты применения алгоритма Маккуина, широко применяющемся для задач квантизации с нестандартными метриками. Каждая итерация алгоритма Маккуина даже в самом лучшем (оптимизированном) варианте выполняется не менее чем за пять вычислительных операций. После выполнении 350 итераций (10 итераций и не менее 50 вычислительных операций на одну точку) ошибка квантизации оказалась равна 0 158 0.001. После 3500 итераций (100 итераций и не менее 500 вычислительных операций на одну точку) ошибка сравнялась с ошибкой асимптотически оптимальной квантизации во втором знаке: 0.148 ±0.001 (рис.3). После 35000 итераций (1000 итераций и не менее 5000 вычислительных операций на одну точку) - в третьем знаке: 0.146 ¿0.001. И только после 35 миллионов итераций (1 млн. итераций и не менее 5 млн. вычислительных операций на каждую точку) ошибка квантизации стала различимо меньше ошибки асимптотически оптимальной квантизации: 0.144 0.001 (рис.4).

В заключении подведены итоги проведенного исследования. После списка литературы добавлены два приложения. В приложении 1 (библиографические замечания) дан краткий библиографический обзор основных работ по теории дискретизации данных (сигнала). В приложении 2 приведено описание алгоритмов Ллойда и Маккуина построения адаптивной дискретизации.

Результаты работы:

1) Построена квантизационная модель с функцией ошибки, локально

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

2) Разработаны методы моделирования адаптивной дискретизации неизотропных данных в различных условиях. Во всех случаях задача оптимальной дискретизации сведена к простым задачам вычислительной геометрии.

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

4) Построена иерархия моделей для различных частных случаев многомерных неизотропных данных. Были рассмотрены как случайные, так и неслучайные данные.

5) Были проведены численные эксперименты для моделирования частных видов двумерных неизотропных данных, произведено сравнение полученных результатов с результатами применения кластеризационного алгоритма Маккуина.

Благодарности: Автор благодарит своего научного руководителя проф.Н.К.Бакирова (Институт математики с ВЦ. Уфа) за постановки задач и помощь в написании диссертации, проф. О.В.Селезнева (МГУ, University of Umea, Швеция) за помощь в поиске информации по теме диссертации, проф. Peter M. Gruber (Technische Universität Wien, Австрия) и проф. Qiang Du (Penn State University, США) за присланные работы по теме диссертации. Автор благодарен профессору I.Sloan (The University of New South Wales. Австралия) и В.В.Дмитриеву за полезные замечания по тексту работы, а также И.Х.Махмутову за помощь в распечатке текстов.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Захаров А.В. Одно обобщение теории квантизации и его применение в задачах оценивания полей по значениям в точках. - Уфа: Гилем, 2003. 108 с.

2. Захаров А.В. Обобщение теории квантизации и его применение в задачах оценивания полей по значениям в точках // Вестник УГАТУ. - 2003. Т.4. №2. - С.187-191.

3. Захаров А.В. Что умеют специалисты по теории квантизации // Труды Международной конференции по вычислительной математике (МКВМ-2004). - Новосибирск: Изд-во ИВМиМГ СО РАН, 2004. - С. 104-109.

4. Захаров А.В., Симонов К.В., Перетокин С.А. Некоторые подходы к решению аппроксимационных задач при интерпретации данных геомониторинга // Труды Международной конференции по вычислительной математике (МКВМ-2004). - Новосибирск: Изд-во ИВМиМГ СО РАН, 2004. -С.110-115.

5. Захаров А.В. Оптимальное моделирование полей при помощи алгоритмов Ллойда и Маккуина // Актуальные проблемы математики. Математические модели современного естествознания. Межвуз.научн.сб. - Уфа: РИК УГАТУ. 2004. - С.147-154.

6. Захаров А.В. Ступенчатая аппроксимация и кубатурные формулы на классах функций Липшица // Актуальные проблемы математики. Математические модели современного естествознания. Межвуз.научн.сб. - Уфа: РИК УГАТУ. 2004. - С.154-166.

Захаров Андрей Владимирович

МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ДИСКРЕТИЗАЦИИ МНОГОМЕРНЫХ НЕИЗОТРОПНЫХ ДАННЫХ МЕТОДАМИ ТЕОРИИ КВАНТИЗАЦИИ

05 13.18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ диссертации на соискание ученой сгепени кандидата физико-математических наук

Подписано к печати 18 ноября 2004 г. Формат 60x84/16. Бумага офсетная. Печать плоская. Гарнитура Times New Roman. Усл печ л 1,0. Усл кр.отт. 0,9. Уч.-изд л 0,9. Тираж 100 экз Заказ № 647. Бесплатно. Уфимский государственный авиационный технический университет Центр оперативной полиграфии 45000, Уфа-центр, ул К Маркса, 12.

»--110

Основные обозначения

Введение

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

1.1. Аналого-цифровое преобразование. Дискретизация данных

1.2. Постановка задачи оптимальной квантизации

1.3. Учет неизотропности данных

1.4. Разбиение Вороного. Бисекторы

1.5. Оптимизация фотоприемной матрицы прибора с зарядовой связью

1.6. Оптимизация геофизических съемок

Глава 2. Вспомогательные утверждения.

Глава 3. Квантизация равномерного источника.

3.1. Теорема о решетчатой квантизации в Rn

3.2. Теорема о паркете

3.3. Теорема о квантизации в Яп, неконструктивный результат

3.4. Теорема о квантизации в R

Глава 4. Квантизация неравномерного источника.

4.1. Теорема о квантизации неравномерного источника с непрерывно меняющейся поверхностью (линией) вариационного профиля

4.2. Теорема о квантизации неравномерного источника с гомотетичной поверхностью (линией) вариационного профиля

Глава 5. Дискретизация различных типов многомерных неизотропных данных.

5.1. Оптимальная дискретизация фиксированных многомерных данных.

5.2. Оптимальная дискретизация случайных многомерных данных с известным распределением

5.3. Оптимальная дискретизация локально-однородных случайных данных с нулевым средним

5.4. Оптимальная дискретизация многомерных случайных данных с независимыми приращениями с нулевым средним.

5.5. Оптимальная дискретизация случайных данных с ненулевым средним

5.6. Дискретизация суммируемых случайных данных.

5.6.1. Аппроксимация интеграла

5.6.2. Оптимальность простейшей кубатурной формулы для интеграла по случайному полю с независимыми приращениями.

5.7. Оптимальная дискретизация на классах данных, описываемых функциями, удовлетворяющих общему условию Липшица

5.8. Оптимальная дискретизация на классах суммируемых данных, описываемых функциями, удовлетворяющих общему условию Липшица

5.9. Численные эксперименты для одного класса метрик

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

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

Процедура дискретизации сигнала в общем случае предполагает замену исходного значения сигнала в произвольной точке/; его значением в точке tk некоторого набора точек области определения Т. Ошибку такой замены запишем в виде p(t,tk), где p(t,s) - некоторая функция. Значением сигнала в точке tь заменяются значения функции из целого множества (как правило ближайших) точек Д^. Так как кодируются все точки Т, набор множеств {Дь})^ образует разбиение Т. Ошибка кодирования точкой tk измеряется интегралом

J p(t,tk)dt, к = 1,., N. Общая ошибка кодирования множества Т точками {tk}^ измеряется суммой n[T\ = £ / P(t,tk)dt. k=ll

Таким образом, рассматривая задачу оптимальной дискретизации сигнала аналого-цифровым преобразователем, мы приходим к задаче квантизации, которая в общей постановке описывается следующим образом ([80], [87]).

Все точки односвязного множества Т С Rn кодируются конечным набором точек С Rn. Для этого множество Т разбивается на N подмножеств {Д*}^, каждое из которых кодируется соответствующей точкой набора {tk}k=i- Общая ошибка кодирования определяется суммой интегралов n j P(t,h)dt. k=lAk

Здесь /?(£, s) - некоторая функция, определяющая ошибку кодирования точки t точкой s (подробнее - в первой главе). Задача квантизации состоит в минимизации ошибки £ по разбиению {Д/с}^ и набору точек {U}fcLi- Отметим, что под термином квантизация понимается как сам процесс кодирования информации, так и набор Д^}^, определяющий способ кодирования. Набор {tk,Ak}k=доставляющий минимум ошибке £, называется оптимальной (наилучшей) квантизацией. За исключением некоторых очень частных случаев, получить теоретическими методами наилучшую квантизацию для конечного числа точек N практически невозможно. Поэтому практически всегда используется асимптотический подход. Точное определение асимптотически оптимальной квантизации приведено в первой главе.

Первоначально задача оптимальной квантизации рассматривалась для одномерного случая (п = 1) с функцией p(t,s), являющейся евклидовой метрикой. В таком виде она впервые была поставлена Шенноном в 1948 году для проблемы кодирования аналогового сигнала с целью обеспечить максимальную помехоустойчивость. Основные имеющиеся результаты теории квантизации касаются одномерного (п — 1) случая, когда функция p{t,s) есть евклидова метрика, или же локально может быть приближена этой метрикой с некоторым коэффициентом (неоднородный случай). Теория оптимальной квантизации достаточно подробно разработана в случае двумерной области Т, как для метрики L2, так и для метрики L\, начиная с [130], в [81], [126], [128]. Также разрабатывался асимптотический подход прип —> оо в случае, когда p(t, s) есть Ь2-метрика ([81], [95], [139]).

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

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

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

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

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

Цель работы. Целью настоящей работы является обобщение основных результатов асимптотической теории квантизации на случай неизотропного источника и последующего применения этого обобщения к задачам дискретизации основных типов непрерывных данных. Для того, чтобы учесть неизотропность источника, в качестве ошибки квантизации была рассмотрена функция p(t,s), которая может быть локально приближена степенью метрики, порожденной выпуклым множеством.

Методы исследования. В работе используются следующие известные методы и конструкции. Метрика, порожденная выпуклым множеством, и теория множеств Вороного относительно этой метрики, разработанная в работах [72], [73], [91], [98]. Методы классической теории квантизации, в частности, те простейшие утверждения, что оптимальным разбиением {Ak}k=i будет разбиение на множества Вороного относительно точек {tk}'k=i (лемма 8), а также, что минимум погрешности по множеству Ak относительно точки tk при фиксированной площади А^ достигается, когда А^ есть окружность в метрике p{t,s) (лемма 5). Метод сведения задач оптимальной ступенчатой аппроксимации случайного поля к задаче оптимальной квантизации ([127]). Метод сведения задач оптимальной аппроксимации и оптимальной кубатурной формулы на классах функций Липшица к задаче квантизации ([89], в неявном виде это метод получен также в работе [45]). Метод построения асимптотически оптимальной квантизации и асимптотического оценивания ошибки ее погрешности в случае неоднородной функции p(t,s), состоящий в разбиении области Т на бесконечно малые подмножества, на которых функция p(t, s) считается однородной. Последний метод разработан в работах [81], [126]-[128], [130] и предполагает введение функции плотности расположения точек, вид которой автор взял из работы [95]. Определение асимптотической оптимальности ([117], [127]), которое введено по отношению к задачам оптимального расположения точек впервые, по видимости, в [117].

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

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

Помимо основных результатов, принципиально новыми моментами в данной работе являются: рассмотрение общей задачи квантизации с функцией p(t,s), приближаемой метрикой, порожденной выпуклым множеством; введение понятия вариационного профиля, которое, как оказалось, является ключевым в обобщенной теории квантизации; рассмотрение в случае п > 3 параллелограмов двойственного разбиения, а в случае п = 2 - треугольников Делоне в качестве обьекта по которому минимизируется ошибка; строгие доказательства утверждений лемм 2 и 7, которые в других работах предполагаются выполнеными по условию.

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

На защиту выносятся: квантизационная модель с функцией ошибки, локально приближаемой степенью выпуклой метрики, описывающая процесс дискретизации неизотропных данных с оценкой потерь информации;

- методы моделирования адаптивной дискретизации неизотропных данных в различных условиях;

- оценки потерь информации при дискретизации неизотропных данных в различных условиях;

- иерархия моделей для различных частных случаев многомерных неизотропных данных;

- результаты численных экспериментов моделирования частных видов двумерных неизотропных данных.

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

1. На международном конгрессе по кубатурным формулам (Уфа,

2001).

2. На международной конференции по кубатурным формулам (Красноярск, 2003).

3. На семинаре по теории вероятностей и математической статистике кафедры математики УГАТУ, руководитель проф.Ф.С.Насыров.

4. На городском семинаре по кубатурным формулам, руководители проф.М.Д.Рамазанов, проф.Р.Р.Асадуллин.

5. На методическом семинаре Института математики с вычислительным центром УНЦ РАН, руководитель проф.Н.К.Бакиров.

Публикации. Основные результаты диссертации изложены в восьми публикациях, среди которых одна монография ([141]), пять статей ([144]-[147]) и две публикации тезисов докладов ([140], [142]). Работа [145] выполнена совместно с К.В.Симоновым и С.А.Перетокиным. Из результатов этой работы в диссертацию автором включены только результаты полученные им лично.

Аннотация диссертационной работы по главам. В первой главе дается общая постановка задачи оптимальной квантизации, и конкретизируются основные условия, в которых она решается. При этом даются предварительные сведения о конструкциях используемых в дальнейшем. Во второй главе собраны основные леммы, представляющие из себя не только вспомогательные результаты, но также и самостоятельные утверждения, которые могут использоватся при разработке численных методов решения задачи. Третья глава посвящена разработке методов решения задачи для случая функции p{t,s), которая может быть приближена однородной функцией. Четвертая глава содержит результаты, полученные для случая неоднородной функции p(£,s). Пятая глава содержит применения построенной модели квантизации к задачам дискретизации данных для различных моделей данных. В этой главе каждый пункт построен следующим образом: сначала приводится постановка задачи, затем поставленная задача сводится к задаче квантизации, и приводится вид соответствующей данной задаче функции p(t, s). При этом основным результатом каждого пункта является возможность сведения поставленной задачи к задаче квантизации с соответствующим видом функции p(t,s). Также приведены результаты численных экспериментов для одного класса выпуклых метрик. В заключении подводятся итоги проведенного исследования. После списка литературы приведены приложения, в которых приведено описание обобщенного алгоритма Ллойда и алгоритма Маккуина, позволяющих минимизировать ошибку квантизации в общем случае, а также приведены библиографические замечания к списку литературы.

Несколько слов об одномерном случае. В данном случае проблема неизотропности источника снимается, и для решения аналогичных задач могут быть применены уже хорошо разработанные методы теории квантизации. Более того, для решения задачи дискретизации одномерного случайного сигнала существует более совершенный метод, который позволяет найти наилучшую линейную несмещенную оценку (так называемую BLUE-оценку, BLUE - best linear unbiased estimator). Он заключается в следующем. Для конкретного расположения точек {tk}k=\ наилучшая оценка функции, зависящая линейно от значений в этих точках, может быть найдена методом ортогональной проекции. Оптимизация расположения же самих точек может быть произведена различными методами. Например, для случайных процессов с независимыми приращениями - это метод сведения задачи к минимизации среднего отклонения от нуля набора броуновских независимых мостов с концами в точках {tk}k=i> использующийся в [110], [111], [131], также частично в [103]-[108]. Тот же метод может быть применен для нахождения оптимального приближения суммируемых случайных данных данных (интеграла от случайного процесса, см. [111], [110]). По этой причине в данной работе одномерный случай не рассматривается.

Основные результаты работы.

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

2) Разработаны методы моделирования адаптивной дискретизации неизотропных данных в различных условиях. Во всех случаях задача оптимальной дискретизации сведена к простым задачам вычислительной геометрии.

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

4) Построена иерархия моделей для различных частных случаев многомерных неизотропных данных. Были рассмотрены как случайные, так и не случайные данные.

5) Были проведены численные эксперименты для моделирования частных видов двумерных неизотропных данных, произведено сравнение полученных результатов с кластеризационным алгоритмом Маккуина.

ЗАКЛЮЧЕНИЕ

1. Анищенко B.C., Вадивасова Т.Е. Лекции по статистической радиофизике. Часть 1. Саратов: Изд-во СГУ, 1992.

2. Анищенко B.C. Введение в статистическую радиофизику. Часть 1.- Саратов: Изд-во СГУ, 1979.

3. Ахманов С.А., Дьяков Ю.Е., Чиркин А.С. Введение в статистическую радиофизику и оптику. М.: Наука, 1981.

4. Баранов Ю. Б., Берлянт А. М., Капралов Е. Г., Кошкарев А. В., Серапинас Б. Б., Филиппов Ю. А. Геоинформатика. Толковый словарь основных терминов. М.: ГИС-Ассоциация, 1999.

5. Бримкулов У.Н., Круг Г.К., Саванов В. Л. Планирование экспериментов при исследовании случайных полей и процессов. М.: Наука, 1986.

6. Бусленко Н.П., Голенко Д.И., Соболь И.Н., Срагович В.Г., Шрейдер Ю.А. Метод статистических испытаний (метод Монте Карло).- М.: Физматгиз, 1962.

7. Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний Монте Карло и его реализация в цифровых машинах. М.: Физматгиз, 1961.

8. Быков В. В. Цифровое моделирование в статистической радиотехнике. М.: Советское радио, 1971.

9. Васильев К.К. Крашенинников В.Р. Методы фильтрации многомерных случайных полей. Саратов: Изд. Саратовского университета, 1990.

10. Воробьев О.Ю. Среднемерное моделирование. М.: Наука, 1984.

11. Гандин Л.С., Каган Р.Л. Статистические методы интерпретации метеорологических данных. Л.: Гидрометеоиздат, 1976.

12. Гардинер К.В. Стохастические методы в естественных науках.1. М., Мир, 1986.

13. Горский В.Г., Адлер Ю.П., Талалай A.M. Планирование промышленных экспериментов (модели динамики). М.: Металлургия, 1987.

14. Гихман И.И., Скороход А.В. Введение в теорию случайных процессов. М.: Наука, 1977.

15. Ермаков С.Н. Метод Монте Карло и смежные вопросы. М.: Наука. 1971.

16. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. -М.: Наука, 1982.

17. Климов А.С. Форматы графических файлов. М.: НИПФ «ДиаСофт Лтд», 1995.

18. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. В 2 т. М.: Мир. - 1990. - Т. 1-2.

19. Купер Дж., Макгиллем К. Вероятностные методы анализа сигналов и систем. М.: Мир, 1989.

20. Левин Б.Р. Теоретические основы статистической радиотехники.- М.: Радио и связь, 1989.

21. Люстерник Л.А. Выпуклые фигуры и многогранники. М.: Гос. изд-во научно-технич. лит. - 1956.

22. Михайлов Г.А. Оптимизация весовых методов Монте-Карло. М.: Наука, 1987.

23. Михайлов Г.А. Приближенные модели случайных процессов и полей // Журнал вычисл. математики и матем. физики. Т.23, №3. С.558-566.

24. Михайлов Г.А. Численное построение случайного поля с заданной спектральной плотностью // Докл. АН СССР. 1978. Т.238, №4, С.793-795.

25. Николаев А.В., Верещагина Г.М. Об инициировании землетрясений землетрясениями // Доклады АН СССР, 1991, том 318, N2.- С. 320-324

26. Николаев А.В., Верещагина Г.М. Об инициировании землетрясений подземными ядерными взрывами // Доклады АН СССР, 1991, том 319, N2. С. 333-336

27. Пиранашвили З.А. Некоторые вопросы статистико-вероятностного моделирования случайных процессов / / Вопросы исследования операций. Тбилиси: Мецниереба, 1966. С.53-91.

28. Полляк Ю.Г. Вероятностное моделирование на электронных вычислительных машинах. М.: Сов. радио, 1971.

29. Препарата Ф., Шаймос М., Вычислительная геометрия: введение.- М.: Мир, 1989, 478 с.

30. Приборы с зарядовой связью // Под ред. М. Хуанга, Д. Моргана.- М: Советское радио, 1976.

31. Приборы с зарядовой связью // Под ред. Д.Ф. Барба. М: Мир,1982.

32. Пригарин С.М. Введение в численное моделирование случайных процессов и полей. Учебное пособие. Часть 1,2.- Новосибирск: НГУ, 1999.

33. Пугачев B.C. Теория случайных функций. М.: Физматгиз, 1962.

34. Расщепляев Ю.С., Фандиенко В.Н. Синтез моделей случайных процессов для исследования автоматических систем управления. М.: Энергия, 1981.

35. Рикитаке Т. Предсказание землятресений. Пер. с англ. М.: Мир,1979.

36. Роджерс К. Укладки и покрытия. М.: Мир. - 1968.

37. Родионов Д.А., Коган Р.И., Голубева В.А. и др. Справочник по математическим методам в геологии. М.: Недра, 1987.

38. Розанов Ю. А. Стационарные случайные процессы. М.: Наука,1990.

39. Рытов С.М. Введение в статистическую радиофизику. М., Наука,1976.

40. Сальтелли А., Соболь И.М. Анализ чувствительности нелинейныхматематических моделей: численные опыты / / Математическое моделирование. 1995.- т.7, №11. С. 16-28.

41. Свешников А.А. Прикладные методы теории случайных функций.- М.: Наука, 1968.

42. Секен К., Томпсет М. Приборы с переносом заряда. М: Мир,1978.

43. Сизова А.Ф., Товстик Т.М. Моделирование случайного поля на сфере // Вестн. ЛГУ. 1984. т. С.118-120.

44. Скороход А.В. Случайные процессы с независимыми приращениями. М.: Наука, 1986.

45. Соболь И.М. Многомерные квадратурные формулы и функции Хаара. М.: Наука, 1969.

46. Соболь И.М. Рэйндж количественная мера неравномерности распределения // Матем. моделирование. - 2002.- т.14, N.6. - С.119-27.

47. Соболь И.М. Численные методы Монте Карло. М.:Наука. 1973.

48. Соболь И.М. Метод Монте-Карло. М.: Наука, 1985.

49. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. М.: Наука, 1981.

50. Сульдин А.В. Мера Винера и ее приложения к приближенным методам. I. Изв.ВУЗов.Сер.Матем., 1959. № 6. С. 145-158.

51. Сульдин А.В. Мера Винера и ее приложения к приближенным методам. II. Изв.ВУЗов.Сер.Матем., 1960. № 5. С.165-179.

52. Тихонов В.И. Статистическая радиотехника. М.: Радио и связь,1982.

53. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве.- М.: ГИФМЛ. 1958.

54. Хамитов Г.П. Имитация случайных процессов. Иркутск: Изд-во Иркутского университета, 1983.

55. Хартман К., Лецкий Э., Шефер В., и др. Планирование эксперимента в исследовании технологических процессов. М.: Мир, 1977.

56. Шалыгин А.С., Палагин Ю.И. Прикладные методы статистического моделирования. JL: Машиностроение, 1986.

57. Яглом A.M. Некоторые классы случайных полей в п-мерном пространстве, родственные стационарным случайным процессам // Теория вероятностей и ее применения. 1957. Т.2, №3. С.292-337.

58. Abut Н. Vector Quantization. IEEE Reprint Collection. IEEE Press. Piscataway, NJ, 1990.

59. Adler R.J. The geometry of random fields. Wiley, New York, 1981.

60. Okabe A., Boots В., Sugihara K. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley, John and Sons, Incorporated, 1992.

61. Aurenhammer F. Voronoi diagrams survey of a fundamental geometric data stucture // ACM Compuing Surveys. 1991. 23. P. 345-405.

62. Barnes E.S., Sloane N.J.A. The optimal lattice quantizer in three dimensions // SIAM J. Alg. Discrete Methods. 1983. March, 4. P. 30-41.

63. Benhenni K., Cambanis S. Sampling designs for estimating integrals of stochastic processes // Ann. (Math.) Statist. 1992. 20. P.161-194.

64. Benhenni K., Cambanis S. Sampling designs for estimating integrals of stochastic processes using quadratic mean derivatives // Approximation theory, ed. G. A. Anastassiou. Dekker. New York, 1992. P. 93-123.

65. Benhenni K., Cambanis S. The effect of quantization on the performance of sampling design. Tech. Report. 481 (1996). Dept. of Statistics. University of North Carolina, 1996.

66. Bucklew J.A. Companding and random quantization in several dimensions // IEEE Trans. Inform. Theory. 1981. March, 27. P. 207-211.

67. Bucklew J.A. Two results on the asymptotic performance of quantizers // IEEE Trans. Inform. Theory. 1984. March, IT-30. P. 341-348.

68. Bucklew J.A., Wise G.L. Multidimensional asymptotic quantization theory with r-th power distortion measures // IEEE Trans. Inform. Theory. 1982. March, 28. P. 239-247.

69. Boissonnat J.-D., Sharir M., Tagansky В., Yvinec M. Voronoi diagrams in higher dimensions under certain polyhedra distance function // Proc. 11-th Annual ACM Symp. Comput. Geom. 1995. P.79-88.

70. Cambanis S. Sampling designs for time series // Hannan E. J., Krish-naiah P. R., Rao M. M.(eds) Handbook of Statistics. V.5: Time Series in Time Domain. Amsterdam: North-Holland, 1985. P. 337-362.

71. Cambanis S., Gerr N. A simple class of asymptotically optimal quantizers // IEEE Trans. Inform. Theory. 1983. Sept., 29. P. 664-676.

72. Chew L.P., Drysdale R.L.S. Voronoi diagrams based on convex distance functions // Proc. 1-st Ann. Symp. Сотр. Geom. 1985. P. 235-244.

73. Chew L.P., Drysdale R.L.S. Voronoi diagrams based on convex distance functions. Preprint. Dartmouth PCS-TR86-132. Dartmouth, 1986.

74. Christakos G. Random fields models in earth sciences. Academic press. San Diego, CA, USA, 1992.

75. Cressie N., Gotway C.A., Grondona M.O. Spatial prediction from networks // Chemometrics Intelligent Laboratory Systems. 1990. 7. P.251-271.

76. Du Q., Faber V., Gunzburger M. Centroidal Voronoi tesselations: applications and algorithms // SIAM Review. 2003. 41(4). P.637-676.

77. Fejes Toth L. Lagerungen in der Ebene, auf der Kugel und in Raum. 2-nd ed. Springer-Verlag, 1972.

78. Fedorov V.V, Hackl P. Optimal experimental design: spatial sampling // Calcutta Statistical Association Bulletin. 1994. 44. P.173-174.

79. Fortune S. Voronoi diagrams and Delaunay triangulations // Computing in Euclidean Geometry. Lecture Notes Series in Computing, 4. World Scientific. Singapore, 1995. P.225-265.

80. Gersho A. Principles of Quantization // IEEE Trans. Circuits Syst. 1978. July, 25. P. 427-436.

81. Gersho A. Asymptotically optimal block quantization // IEEE Trans. Inform. Theory. 1979. July, IT-25(4). P. 373-380.

82. Gersho A., Gray R.M. Vector Quantization and Signal Compression. Kluwer Academic Publishers. Boston, 1992.

83. Gray R.M. Vector Quantization I j IEEE ASSP Magazine. 1984. April, 1. P. 4-29.

84. Gray R. M., Gray, Jr.A.H. Asymptotically optimal quantizers // IEEE Trans. Info. Theory. 1977. Feb., IT-23. P. 143-144.

85. Gray R.M., Kieffer J.C., Linde Y. Locally optimal block quantizer design // Information and Control. 1980. May, 45. P. 178-198.

86. Gray R.M. Multivariate quantization // Multivariate Analysis-VI, Krishnaiah P.R., Ed., North-Holland, 1985.

87. Gray R.M., Neuhoff D.L. Quantization // IEEE Transactions on information theory (Commemorative Issue, 1948-1998). 1998. October, 44(6). P.2325-2384.

88. Gruber P.M. A short analytic proof of Fejes Toth's theorem on sums of moments // Aequationes Mathematicae. 1999. 58 (Issue 3). P. 291-295.

89. Gruber P.M. Optimal arrangements of finite point sets in Riemannian 2-manifolds. Тр.матем.инст.им.Стеклова, 1999. - т. 225. - С. 148-155.

90. Journel A.G., Huijbregts C.J. Mining geostatistics. Academic press. New York, 1978.

91. Klein R. Concrete and abstract Voronoi diagrams. Lect. Notes in Computer Science. Vol. 400. Springer-Verlag, 1989.

92. Kuhlmann F., Bucklew J. A. Piecewise uniform vector quantizers // IEEE Trans. Inform. Theory. 1988. Sept., 34(5). Pt.2. P. 1259-1263.

93. Lee D.T. Two-dimensional Voronoi diagrams in the Lp metric // Jurnal of ACM. 1980. 27(4). P.604-618.

94. Lee D.T., Wang C.K. Voronoi diagrams in L\ (Loo) metrics with two dimensional storage application // SIAM J. Comput. 1980. 9. P. 200-211.

95. Li J., Chaddha N., Gray R.M. Asymptotic performance of vector quantizers with a perceptual distortion measure // IEEE Int'l Symp. Inform. Theory. June. Ulm, Germany, 1997.

96. Linder T. On asymptotically optimal companding quantization // Problems of Control and Inform. Theory. 1991. 20(6). P. 465-484.

97. Lookabaugh T.D., Gray R.M. High-resolution quantization theory and the vector quantizer advantage // IEEE Trans. Inform. Theory. 1989. Sep., 35. P. 1020-1033.

98. Ma L. Bisectors and Voronoi Diagrams for Convex Distance Functions. Dissertation zur Erlangung des akademischen Grades eines Doktors der Naturwissenschaften (Dr. rer. nat.) von Dipl.-Math. Erlangen, 2000.

99. Mathe P. Asimptotically optimal weighted numerical integration. Erlangen-Niirnberg University, 1997.

100. Mathews V.J. Vector quantization of images using theZ/oo distortion measure // Proc. Int'l Conf. Image Processing. 1995. Oct., 1. Washington, DC. P. 109-112.

101. Mathews V.J. Vector quantization using the L^ distortion measure // IEEE Signal Processing Letters. 1997. 4. P. 33-35.

102. Moo P.W., Neuhoff D.L. An asymptotic analysis of fixed rate lattice vector quantization // Proc. Intern'l Symp. Inform. Thy. and Its Applications. Victoria, B.C., Sept. 1996. P. 409-412.

103. Miiller-Gronbach T. Optimal designs for approximating the path of a stochastic process. Preprint A-93-14. Fachbereich Mathematik, Freie Univer-sitat Berlin, 1993.

104. Miiller-Gronbach T. Optimal designs for approximating the path of a stochastic process // J. Statist. Planning Inference. 1996. 49. P. 371-385.

105. Miiller-Gronbach T. Optimal designs for approximating the path of a stochastic process with respect to a minimax criterion // Statistics. 1996. 27. P. 279-296.

106. Miiller-Gronbach T. Asymptotically optimal designs for approximating the path of a stochastic process with respect to Loo-norm // Tatra Mountains Math. Publ. 1996. 7. P. 87-95.

107. Miiller-Gronbach Т., Ritter K. Uniform reconstruction of Gaussian processes // Stochastic Processes Appl. 1997. 69. P. 55-70.

108. Miiller-Gronbach Т., Schwabe R. On optimal allocations for estimating the surface of random field // Metrica. 1996. 44. P. 239-258.

109. Newman D.J. The hexagon theorem // IEEE Trans. Inform. Theory. 1982. 28. P. 137-139.

110. Ritter K. Asymptotic optimality of regular sequence designs // Ann. (Math.) Statist. 1996. 24. P. 2081-2096

111. Ritter K. Average case analysis of numerical problems. Habilitation-sschrift, 1996.

112. Ritter K. Average-case analisys of numerical problems. Lecture Notes in Mathematics. 1733. Springer, Berlin, 2000.

113. Ritter K., Wasilkowsky G.W., Wozniakowsky H. Multivariate integration and approximation for random fields satisfying Sacks-Ylvisaker conditions // Ann. Appl. Probab. 1995. 5(2). P. 518-540.

114. Ritter K.,Wasilkowsky G.W., Wozniakowsky H. On multivariate integration for stochastic process // Brass H., Hammerlin G., eds. Numerical Integration IV, ISNM 112. Birkhauser, Basel, 1993. P. 331-347.

115. Sacks J., Schiller S.B., Welch W.J. Designs for computer experiments. // Technometrics. 1989. 31(1). P. 41-47.

116. Sacks J., Welch W. J., Mitchell T. J., Wynn H. P. Designs and analysis of computer experiments // Statistical Sci. 1989. 4. P. 409-435.

117. Sacks J., Ylvisaker D. Designs for regression with correlated errors // Ann. Math. Statist. 1966. 37. P. 68-89.

118. Sacks J., Ylvisaker D. Designs for regression problems with correlated errors; many parameters // Ann. Math. Statist. 1968. 39. P. 49-69.

119. Sacks J., Ylvisaker, D. Designs for regression problems with correlated errors III // Ann. Math. Statist. 1970. 41. P. 2057-2074.

120. Sacks J., Ylvisaker D. Statistical design and integral approximation // Proc.l2th Bienn. Semin. Can. Math. Congr., ed. Руке R., Can. Math. Soc. Montreal, 1970. P. 115-136.

121. Stein M.L. Asymptotically efficient prediction of a random field with a mis-specified covariance function // Annals of Statistics. 1988. 16. P. 55-63.

122. Stein M. Locally lattice sampling designs for isotropic random fields // Ann. Statist. 1995. 23 (6). P. 1991-2012.

123. Stein M. L. Predicting integrals of stochastic processes // Ann. Appl. Probab. 1995. 5. P. 158-170.

124. Stein M. L. Correction Note: Locally lattice sampling designs for isotropic random fields // Ann. Statist. 1999. 27. P. 1440.

125. Stein M.L. Predicting random fields with increasingly dense observation // Ann. Appl. Probab. 1999. 9. P. 242-273.

126. Su Y. Asymptotically optimal representative points of bivariate random vectors // Statistica Sinica. 2000. 10. P. 559-575.

127. Su Y. Estimation of random fields by piecewise constant estimators // Stoch. Proc. Appl. 1997. 71. P. 145-163.

128. Su Y.C. On the asymptotics of quantizers in two dimension // J. Multivariate Anal. 1997. 61(1). P. 67-85.

129. Su Y.C., Cambanis S. Sampling designs for estimation of a random process // Stochastic Processes Appl. 1993. 46. P. 47-89.

130. Toth L.F. Sur la presentation d'une population infinite par un nom-bre fini d'elements // Acta Math. Acad. Scient. Hungary. 1959. 10. P. 299-304 (76-81).

131. Traub J.F., Wasilkowsky G.W., Wozniakowsky H. Information based complexity. Academic Press, San Diego, 1988,

132. Wasilkowski G. Average case complexity of multivariate integration and function approximation an overview // J. Complexity. 1996. 12(4). P. 257-272.

133. Wozniakowski H. Average case complexity of multivariate integration // Bull. Amer. Math. Soc. 1991. 24. P. 185-194

134. Yaglom A.M. Correlation theory of stationary and related random function. Volume I: Basic results. Springer, Berlin, 1987.

135. Yaglom A.M. Correlation theory of stationary and related random functions. Volume II: Supplementary notes and references. Springer-Verlag,1. New York, 1987.

136. Yamada Y., Tazaki S., Gray R. M. Asymptotic Performance of Block Quantizers with Difference Distortion Measures // IEEE Trans. Inform. Theory. 1980. Jan., IT-26(4). P. 6-14.

137. Zador P.L. Topics in the asymptotic quantization of continuous random variables. Bell Laboratories Memorandum. 1963.

138. Zador P.L. Development and evaluation of procedures for quantizing multivariate distributions. Ph.D. Dissertation. Stanford University, 1963.

139. Zador P.L. Asymptotic quantization error of continuous signals and their quantization dimension // Transactions on Inform. Theory. 1982. March, 28. P. 139-149.

140. Работы, опубликованные соискателем

141. Захаров А.В. Пример оптимальной аппроксимации ступенчатыми функциями из С0,1.2 // Третий сибирский конгресс по прикладной и индустриальной математике. Тезисы докладов, часть I. Новосибирск: Издательство Института математики СО РАН, 1998. -С.70-71.

142. Захаров А.В. Одно обобщение теории квантизации и его применение в задачах оценивания полей по значениям в точках. Уфа: Гилем, 2003. - 108 с.

143. Захаров А.В. Современная теория квантизации (квантования) и ее применения к аппроксимационным задачам // Кубатурные формулы и их прилолжения (тезисы докладов). Красноярск: Изд-во КГТУ, 2003. -С.65-66.

144. Захаров А.В. Обобщение теории квантизации и его применение в задачах оценивания полей по значениям в точках // Вестник УГАТУ. -2003. Т.4. т. С.187-191.

145. Захаров А.В. Что умеют специалисты по теории квантизации // Труды Международной конференции по вычислительной математике

146. МКВМ-2004). Новосибирск: Изд-во ИВМиМГ СО РАН, 2004. - С.104-109.

147. Захаров А.В. Оптимальное моделирование полей при помощи алгоритмов Ллойда и Маккуина // Актуальные проблемы математики. Математические модели современного естествознания. Межвуз.научн.сб. -Уфа: РИК УГАТУ, 2004. С.147-154.

148. Захаров А. В. Ступенчатая аппроксимация и кубатурные формулы на классах функций Липшица // Актуальные проблемы математики. Математические модели современного естествознания. Межвуз.научн.сб. Уфа: РИК УГАТУ, 2004. - СЛ54-166.