Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Теоретические основы информатики

Диссертационная работа:

Волков, Владимир Викторович. Восстановление линейных зависимостей по неточной информации : диссертация ... кандидата физико-математических наук : 05.13.17 / Волков Владимир Викторович; [Место защиты: Моск. пед. гос. ун-т].- Борисоглебск, 2011.- 135 с.: ил. РГБ ОД, 61 11-1/823

смотреть введение
Введение к работе:

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

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

Одним из принципиально новых методов моделирования является алгебраический подход к распознаванию образов с использованием эвристических информационных моделей, предложенный и исследованный академиком РАН Ю. И. Журавлевым и его учениками и коллегами академиком РАН В. Л. Матросовым (статистическое обоснование алгебраического подхода), членом-корреспондентом РАН К. В. Рудаковым (общая теория проблемно-ориентированного алгебраического синтеза корректных алгоритмов), К. В. Воронцовым, В. В. Рязановым и другими.

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

Указанные выше подходы наиболее перспективны для решения прикладных задач в тех предметных областях, для которых нет адекватных математических моделей.

В контексте настоящего исследования наиболее интересен случай, когда в описанных приложениях распознавания зависимостей и обработки данных возникают приближенные системы линейных алгебраических уравнений (СЛАУ). Для решения таких СЛАУ, как правило, используются два альтернативных подхода.

Первый подход представляет метод наименьших квадратов (МНК), предложенный для решения приближенных СЛАУ еще Лежандром и Гауссом. В традиционной формулировке МНК заключается в поиске вектора решения, минимизирующего норму невязки системы. Однако классический МНК можно также сформулировать как задачу поиска такого вектора поправок к правой части, который делает приближенную систему совместной и имеет минимальную норму.

Дальнейшим развитием этого подхода стал так называемый обобщенный метод наименьших квадратов — Total Least Squares (TLS). TLS обобщает подход МНК, распространяя поправки не только на правую часть, но и на матрицу коэффициентов системы. При использовании этого метода ставится задача найти

такую минимальную по норме матрицу коррекции, что при ее добавлении к приближенной матрице исследуемая приближенная СЛАУ становится совместной.

За рубежом интенсивные исследования метода TLS и его модификаций, а также его активное использование при решении прикладных задач начались в конце 80-х годов XX века после появления работ бельгийского математика S. Van Haffel. Также заметный вклад внесли J. Vandewalle, J. В. Rosen, G. Н. Golub и другие.

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

Исследования в этом направлении велись параллельно с зарубежными учеными. Первые результаты, связанные с матричной коррекцией систем линейных алгебраических уравнений и несобственных задач математического программирования получены научной школой Института математики и механики УрО РАН под руководством академика РАН И. И. Еремина. Так, матричная коррекция СЛАУ впервые была рассмотрена в работах ученика академика И. И. Еремина А. А. Ватолина в середине 80-х годов XX в.

Исследования И. И. Еремина и А. А. Ватолина в конце 90-х годов XX в. были продолжены (и продолжаются в настоящее время) в ВЦ им. А. А. Дородницына РАН В. А. Гореликом и его коллегами и учениками: В. И. Ерохиным, Р. Р. Иба-туллиным, В. А. Кондратьевой, О. В. Муравьевой, Р. В. Печенкиным и другими.

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

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

Основополагающие подходы для теории некорректных задач связаны с именами А. Н. Тихонова, В. К. Иванова, М. М. Лаврентьева. Монографии А. И. Тихонова, В. Я. Арсенина и В. К. Иванова, В. В. Васина, В. П. Тананы являются ключевыми для теории линейных некорректных задач.

Также большой вклад в эту область внесли А. С. Апарцин, А. Б. Баку-шинский, Ф. П. Васильев, В. В. Васин, Ю. Е. Воскобойников, С. И. Кабанихин, А. С. Леонов, В. И. Цурков и многие другие.

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

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

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

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

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

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

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

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

Цель диссертационной работы состоит в развитии математического аппарата оптимальной матричной коррекции несовместных СЛАУ (А. А. Ватолин, В. А. Горелик, В. И. Ерохин и др.) и математического аппарата построения регуля-ризованных решений приближенных СЛАУ (А. Н. Тихонов) на случай конечных по величине погрешностей в матрице коэффициентов приближенной системы и

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

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

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

  1. Получить необходимые и достаточные условия эквивалентности задачи решения приближенной СЛАУ в постановке А. Н. Тихонова (РМНК) задаче минимизации сглаживающего функционала, методу наименьших квадратов, либо задаче минимальной матричной коррекции.

  2. Оценить максимальное по евклидовой норме относительное отклонение решения приближенной СЛАУ от нормального решения гипотетической точной СЛАУ.

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

  4. Рассмотреть приложения разработанной теории и методов решения приближенных СЛАУ и анализа приближенных линейных моделей к решению практических задач восстановления линейных зависимостей по неточной информации.

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

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

методов решения для проблемы поиска решения приближенной СЛАУ с фиксированными столбцами матрицы коэффициентов.

Практическая значимость результатов. Предложенные в работе методы и алгоритмы построения и анализа решений приближенных СЛАУ могут быть использованы в задачах обработки зашумленных данных, прогнозирования и управления, относящихся к области исследования специальности 05.13.17 — теоретические основы информатики:

разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях;

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

Основные положения, выносимые на защиту:

необходимые и достаточные условия эквивалентности проблемы решения приближенной СЛАУ по А. Н. Тихонову (РМНК) одной из трех задач: задаче минимизации сглаживающего функционала, методу наименьших квадратов или задаче минимальной матричной коррекции;

априорные нижние оценки максимальной относительной погрешности решения приближенной СЛАУ для случая, когда правая часть системы свободна от погрешности;

алгоритмы решения приближенной СЛАУ по А. Н. Тихонову (РМНК) для общего случая и для частных случаев: специального вида матрицы коэффициентов СЛАУ и запрета на модификацию отдельных столбцов матрицы СЛАУ. Апробация работы. Результаты работы докладывались и обсуждались на российских и международных конференциях: Всероссийской молодежной конференции «Проблемы теоретической и прикладной математики» (Екатеринбург, 2005, 2006, 2007 гг.), Международной конференции «Информационные и коммуникационные технологии в образовании» (Борисоглебск, 2006, 2009, 2010 гг.), Международной конференции «Обратные и некорректные задачи математической физики» (Новосибирск, 2007 г.), Молодежной международной научной школе-конференции «Теория и численные методы решения обратных и некорректных задач» (Новосибирск, 2009 г.), научных семинарах кафедры прикладной математики и информатики физико-математического факультета Борисоглебского государственного педагогического института, кафедры оптимального управления факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова, отдела интеллектуальных систем Вычислительного центра РАН имени А. А. Дородницына и кафедры ресурсосберегающих технологий Санкт-Петербургского государственного технологического института (технического университета).

Получены 4 свидетельства о регистрации алгоритмов [7-10]. Публикации. Материалы, составляющие основное содержание диссертации, опубликованы в 17 печатных работах, из них 3 статьи в изданиях, включенных в

перечень ВАК РФ [1-3], 2 статьи в журналах [4, 5], 12 — в сборниках и трудах конференций [6, 11-21].

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы, содержащего 130 источников. Объем диссертации составляет 135 страниц.


© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net