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

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

Волков Владимир Викторович

Восстановление линейных зависимостей по неточной информации

05.13.17 - Теоретические основы информатики

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

2 ИЮН 2011

Москва - 2011

4848762

Работа выполнена на кафедре прикладной математики и информатики физико-математического факультета ГОУ ВПО «Борисоглебский государственный педагогический институт»

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

доцент

Ерохин Владимир Иванович

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

доцент

Воронцов Константин Вячеславович

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

Кузнецов Олег Анатольевич

Ведущая организация: Московский государственный университет

им. М. В. Ломоносова

Защита состоится 20 июня 2011 года в 16 часов 00 минут на заседании диссертационного совета Д 212.154.32 при Московском педагогическом государственном университете по адресу: 107140, г. Москва, ул. Краснопрудная, д. 14, математический факультет МПГУ, ауд. 301.

С диссертацией можно ознакомиться в библиотеке Московского педагогиче ского государственного университета по адресу: 119991, г. Москва, ул. Малая Пи роговская, д. 1.

Автореферат разослан «/¡и л мая 2011 г.

Ученый секретарь диссертационного совета

Муравьева О. В.

Общая характеристика работы

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

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

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

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

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

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

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

Дальнейшим развитием этого подхода стал так называемый обобщенный метод наименьших квадратов — 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-Ю].

Публикации. Материалы, составляющие основное содержание диссертации, опубликованы в 17 печатных работах, из них 3 статьи в изданиях, включенных в

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

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

Содержание работы

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

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

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

Задача Po(ß, S): Пусть существует точная совместная конечномерная СЛАУ

= &о> (1)

где Ло G Жт*п, 60 G Ьо ф 0, соотношения между размерами Ло и ее рангом не оговариваются, xq € К" — решение системы (1) с минимальной евклидовой нормой (нормальное решение). Численные значения Aq и 6о неизвестны, а вместо них заданы приближенные матрица А € Rmxn и вектор 6 € Rm, 6^0, такие, что выполняются условия ||j40 - Л|| ^ р, ||Ьо — Ь|| ^ 5 < ||Ь||, где/х^0и5^0 — известные параметры. Полнота ранга матрицы А и совместность системы Ах = 6 в общем случае не предполагаются.

Требуется найти Аг е Rmxn, 6i е Rm, хх е R" тате, что ||А - ^ р, ||6 - &i|| < <5, Axxi = Ьг, HsiH min.

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

Задача Pi(д, ¿): ЦхЦ min

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

Задача Рг: Фа(ж, А, Ь) min, где

Фа(х, А, Ь) = ||6 - Ах\^ + а||а:||2. 6

Вводится обозначение za для решения задачи Р2. Известно, что при любом а > 0 существует единственный вектор za. При соответствующем а > 0 вектор za является устойчивым приближением к вектору хо, то есть служит решением задачи Р0 при /i, ô —» 0.

Вводится обозначение ха для нормального решения системы

(.АТА + aln)x = АТЪ (3)

при любом фиксированном a G К, 1„ — единичная матрица порядка п ■

Известно, что для любого а > 0 вектор za совпадает с .та.

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

Теорема 1.2.1. Пусть матрица Ао и вектор Ьо удовлетворяют условиям, обеспечивающим совместность системы (1), жо — нормальное решение этой системы, ||Ло—Л|| < /х, ¡|&о_Ml ^ à, иа(/л, 6) — какие-либо возрастающие

функции fj, и ö, стремящиеся к нулю при ß-*0uö—*0u такие, что ßö ^ е(м, 6)а(ц, ö).

Тогда для любого е > 0 найдутся положительные числа Sq = âo(e, ||яо||) и (¿о = /М)(е, 1Ы1) такие, что S < 6о{е, ||а-о||) и р < цо{е, ||.то||) и при а, удовлетворяющем условию ^ а < a(fi, ô), элемент ха, доставляющий минимум функционалу (2), удовлетворяет неравенству \\ха — хо\\ ^ е.

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

Указанная модификация задачи Р\ имеет вид:

||Ь -Ах- Äx\\ = /ip|| + 6, ||х|| min, II b -Äx- Äx\\ > ô. (4)

Здесь А = [Л Л], где Л 6 JRmxft — фиксированный блок матрицы А, содержащий п столбцов, заданных точно, Л € Rmx™ — блок матрицы А из п столбцов с неточно заданными коэффициентами, п = п + п,х=[х ¿г] , где х € R", х € R".

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

Ztotai(A, Ь) : || [Я -h] ||£ - WA Ь) : № - ^Ы^. (5)

Приведены условия существования решения для указанных задач.

7

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

Во второй главе сформулирована, и доказана теорема, определяющая условия, при выполнении которых задача математического программирования Р\ сводится либо к классической регуляризации, либо к методу наименьших квадратов, либо к матричной коррекции. Здесь и далее х = А+Ь — нормальное псевдорешение приближенной системы Ах = Ь (решение системы по методу наименьших квадратов).

Теорема 2.1.1. Если задача Р\{ц,, 5) имеет решение х^, то возможны случаи:

1. Если выполняется условие ||Ь - Ах|| < /¿||х|| + 6, то вектор х^ является единственным решением задачи Р\{^,5) и совпадает с единственной точкой минимума функционала (2) при некотором а > 0 (решение задачи Р\ совпадает с решением задачи Р-г).

2. Если выполняется условие ||6 — Ах\\ = ц\\х|| + 6, то вектор х = х^ является единственным решением задачи Рг(ц, 5) и точкой минимума функционала (2) при а — 0.

3. Если выполняется условие ||Ь - Ах|| > /¿||ж|| + 5, то вектор х^ является решением задачи Р^р, б), а также стационарной точкой функционала (2) при а < 0. При этом, если матрица А имеет полный столбцевой ранг, то а < 0 (т.е. решение задачи р1(ц,§) совпадает с решением некоторой задачи минимальной матричной коррекции) и вектор х^ является единственным решением задачи Рг(ц, 6). В противном случае а = 0, решение не единственно и имеет вид: х^ = х + Дя, где Да; — произвольный вектор, такой, что ААх = 0, \\Ь-Ах\\ = ц\\х + Ах\\ + 6.

Приводятся численные примеры, иллюстрирующие результаты теоремы.

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

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

априорную информацию при ее наличии.

При использовании взвешивания с произвольными положительными весами задачи (5) можно переформулировать в виде:

&(A,b):\\Wo[H -Л]||в =

т п+1

У У (Wijhij)2 —> inf ,

т п

> > (Wijhij)2 inf 1=1 j=l

Здесь W = (wij > 0) — весовая матрица с размерами тп х (n + 1), как у матрицы [Я —Л], или с размерами их п, как у матрицы Н, знак «о» означает умножение матриц по Адамару.

Исходные задачи сводятся к безусловной минимизации дифференцируемой функции: f(x) = гг(х)Х+Т(х)Х+(х)г(х), где r(x) = [ri(a;) • • • гт(х)]Т = Ь — Ах — вектор невязок системы Ах = Ь при фиксированном векторе х, Х(х) = X(x)-W, W = (diag(u))~l, а Х(х) — матрица, специальным образом сконструированная из элементов вектора х.

С использованием аналитического представления производных функции f(x) для указанной задачи становится возможным применение методов безусловной минимизации Ньютона и Марквардта.

Аналогичный прием применяется и к системам, матрица коэффициентов которых имеет специальный вид. Рассматривается система вида Л(а).т = 6. Матрица А(а) = (ay) € Rmxn имеет специальную структуру: является параметрической и может быть задана вектором а = (a¡) € RN. Задача матричной коррекции такой системы также может быть сведена к безусловной минимизации аналитически дифференцируемой функции f(x) = гт{х) • Х+т(х)Х+(х) ■ г(х). При этом значения производных этой функции находятся с учетом специальной структуры исходной системы и весовой матрицы.

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

Теорема 3.2.1. Пусть А 6 Rmxn — произвольная матрица; .то € R" \ха ф 0; Хц ф 0 \А+Axß = xß; а > 0; А0 = А + (bo - Ах0).tJ + Z; b0 = Axß + aA+Txß + Ab; ЛЬ e Rm \{ATAb = 0, ||аЛ+т.Тф + ДЬ|| = ß\\xß\\); rank A0 = n; и матрица Z e Rn,xn I (fe^f + \\z\\* = Zxо = o) .

Тогда система Aqx = bo совместна, xo — ее нормальное решение, xß — единственное решение задачи Pi(/i, 0), СЛАУ Aqx = Ьо и Ах = bo являются

соответственно точной и приближенной системами, отвечающими условиям задачи Ро{ц, 0).

Теорема 3.2.2. Пусть А е Мтхп |гапк А = п; х^ € К" — произвольный вектор; Ь0 = Ахц+аА^х^+АЬ; х0 е К" \хйф 0; Ао = A+{bn-Axй)x^JrZ; гапк Л0 = п; АЬ € Мт |(ЛТДЬ = 0, \\аА+Тх„ + Д6|| = фЙ\\, ||ДЬ|| > ц\\хц + аА+А+тх„\));

а< 0; г е 1ГХ" | + Ш? = Яг0 = о) .

Тогда система Лоя = Ьо совместна, хо — ее нормальное решение, хм — единственное решение задачи СЛАУ Аох = &о и Ах — Ьо являются

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

Теорема 3.2.3. Пусть А е Етхп |гапк А < п; х Ф 01А+Ах = х; х^ = х + Ах; Ьо = Ах+АЬ; а?0 € К" |ж0 ф 0; Ао = Л + (Ь0-Ах0)хо +2; гапкЛ0 = п; ААх = 0; АТАЬ = 0; ||ДЬ|| = ф+Ах\\ > ф\\; г £ Е"*™ | + ||£||2 = ^ = о)

Тогда система Ацх = Ьо совместна, хо — ее нормальное решение, хц принадлежит множеству решений задачи 0), которое содержит более одного решения, СЛАУ Аох — Ьо и Ах = Ьо являются соответственно точной и приближенной системами, отвечающими условиям задачи Ро(ц,0).

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

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

Теорема 3.2.4. Если существует решение задачи Р\{ц, 6), причем Цж^Ц < ||£'||, то существует единственный параметр а*, такой, что

Г 0 < а < а* => ||6 - Ага|| < ц\\ха\\ + 6, \ а > а* => ||Ь - Аха|| > д||:Га|| +

При этом х^ = ха-, вектор ха> единственным образом определяется условием (3).

Следствие. Для нахождения х^ можно использовать алгоритм, включающий в себя решение системы (3) и дихотомию по параметру а. Экспериментальные исследования показали, что для поиска а* наиболее предпочтителен именно метод дихотомии. Другие численные методы (например, метод хорд) на практике работают медленнее, что обусловлено особенностями функции /(а) = ||Ь—Аха\\ — Н|яа|| - 5.

Указанное следствие из теоремы фактически формулирует численный метод решения задачи 5), в котором задача минимизации заменяется задачами решения СЛАУ и поиска корня нелинейного уравнения методом дихотомии.

Данный алгоритм допускает модификацию для задачи с фиксированным блоком. Для этого достаточно изменить вид матрично-векторных объектов с учетом структуры исходной матрицы коэффициентов: система (3) преобразуется к

виду ^АТА + а \\b- Äx~ Äx\\

/ О О О

= АТЬ, а целевая функция принимает вид /(а) =

Второй алгоритм решения задачи Pi основан на использовании метода наискорейшего спуска, применяемого к минимаксной задаче. Приведем этот алгоритм.

Целевая функция: f{x) = тах{ЦЬ - Аг||,/х||а;|| + ¿}.

Вспомогательные функции: fi(x) = ||Ь - Ах\\, /2(2:) = р\\х\\ + 6.

На входе: А,Ь,р,8 — параметры задачи Р\{ц, 5), х° — начальное приближение для решения.

На выходе: вектор х*, являющийся решением задачи P\{ß, Ö).

Шаг 1. Вычислить градиенты функций хг) и /2(2.''): gi{xl) = Vfi{xl) = -AT(b - Аз*)/\\Ъ - Ах{||, ф*) = У/2(г<) = цх'/\\х%.

Шаг 2. Найти вектор градиента д как линейную комбинацию градиентов и зг(^): д = 7*9\W) + (1 - 7*Ыя')-

Параметр 7* может быть найден следующим образом:

7 =

1, если ЛИ > f2{x% О, если h(xl) < ¡2{хг),

, _ 92(xi)T9A?)-Ji(x<)TS2(f) спнп!т{)= Mr*)

Шаг 3. Найти новое значение вектора х1+х по формуле: .тг+1 = х1 - А*д.

Для поиска А* решить вспомогательную задачу: /(хг+1) = {{х1 — Ад) —> ппп.

Если рассматривать ¡\{х' - Ад) и /2(а;! - Ад) как функции от А, легко показать, что каждая из них имеет по единственной точке глобального минимума. Эти точки могут быть найдены аналитически в следующем виде (для ^(х1 — Xд) и Ш ~ Ад) соответственно): А> = А§ =

Если функции /^х'—Хд) и ¡2{х1—Хд) не имеют точек пересечения, то искомое значение А* может быть найдено по формуле:

Д» _ / ло> если /\(х' - АЪд) ^ /2(х* - А¡д), \ Ац, если ¡г{хг - А\д) < /2(.т* - \20д).

В противном случае, искомое значение А* можно найти, применив метод дихотомии к функции ф(А) = /1(хг-Хд)-/2{хг-Хд) на отрезке [тт(А^, Ад); тах(А^, Ад)].

Шаг 4. Если д ф 0, то положить г = г + 1 и вернуться к шагу 1, иначе — конец алгоритма и я* = х1+1 — искомое решение.

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

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

На все алгоритмы получены свидетельства об отраслевой регистрации разработки ОФАП или свидетельства о регистрации электронного ресурса ОФЭРНиО [7-10].

Четвертая глава посвящена исследованию погрешностей решения задачи РМНК различными методами.

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

Теорема 4.1.1 .При решении задачи Pi(fi,0) для случая ||&о - < rank Л = п, ц < cTmin, максимальное значение относительной погрешности (где Ах = хо — Хц) будет не меньше, чем величина: £\ —

Теорема 4.1.2. При решении задачи Pi(n,0) для случая ||6о - АхЦ > /хр||, rank Л = п, /и < <7mmi максимальное значение относительной погрешности (где Ах = хо — xMJ будет не меньше, чем величина: £2 — рг^г-

Теорема 4.1.3. При решении задачи Ро(ц,0) для случая ||&о — Ах|| = fi\ f||, rank Л = тг, ц < <7mm максимальное значение относительной погрешности ^^ (где Ах = хо - xJ будет не меньше, чем величина: £3 = ffi а.

miri 'г*

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

Указанные теоретические результаты проиллюстрированы численными примерами.

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

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

Основным содержанием задачи позиционирования в СРНС является определение пространственно-временных координат потребителя: координат {xT,yr,zT) и временной поправки 6т шкалы времени потребителя относительно системной шкалы времени.

Пусть te — время излучения сигнала спутником, tr — время получения сигнала приемником, с — скорость света. Время распространения сигнала от спутника до потребителя tr — te может быть получено из измерений. Тогда для каждого г-го из п видимых спутников может быть измерена так называемая псевдодальность:

Ri = ЛА - хт? + (vi - Ут? + - zry + órc.

(6)

В этих уравнениях четыре неизвестных: координаты приемника (хГ} уг, гт) и поправка часов 6т. Поэтому для определения искомых навигационных параметров необходимо как минимум четыре уравнения (тшп = 4), то есть данные как минимум с четырех спутников.

Линеаризованные функции (б) будут иметь вид Щ =

^Аг + Ы, где г = \,..,п,А1= сбт, Ог = у/{х\ - а;°)2 + {у\ - у°)2 + (а* - гг°)2, — некоторая точка, которая является начальным (известным или приближенно заданным) положением потребителя.

Введем обозначения: дх, =

бгг = г = 1 ,..,п.

д. I "Уг — д>

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

дх\ 5у1 1" 6X2 ¡Уг ¿22 1

- 6хп <5уп 5гп 1 -

Дх А у Дг Дг

Д1

(7)

В экспериментах исследовалось применение для решения задачи позиционирования (фактически, системы (7)) подхода А. Н. Тихонова (задача в сравнении с традиционными методами. Некоторые результаты представлены на графиках (рис. 1-6).

Исходные данные о положении спутников ГЛОНАСС были получены из архива Информационно-аналитического центра Федерального космического агентства.

В ходе экспериментов для пользователя задавалось смещение по координатам (Да;, Ау, Дг) и поправка по времени и исследовались результаты определения изменившегося местоположения и поправок часов при различных уровнях погрешности с помощью метода Монте-Карло. При этом сравнивались два метода решения — с использованием метода наименьших квадратов (или поиск нормаль-

хкГ®

хю-* ИМ! „о-1 |

|

Рис. 3. Области для норм погрешностей реше- Рис. 4. Области для норм погрешностей решения по МНК и РМНК в примере 5.1.3 ния по МНК и РМНК в примере 5.1.4

ного решения для системы из четырех уравнений) и с помощью решения задачи | Р\ (РМНК).

Для решения задачи РМНК могут быть применены алгоритмы [7, 8], описанные во втором разделе третьей главы. При сравнении алгоритмов [7] и [8] на прак- I тике, оказалось, что быстрее работает алгоритм [8], поэтому в вычислительных | экспериментах данного раздела использовался именно он, с учетом модификации

для блочной матрицы.

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

Для каждого из четырех случаев производилось 200000 запусков со случайными погрешностями для вектора Ь, равномерно распределенными по норме в 1 диапазоне от 0 до 2е. Величина е была задана в 1% от нормы вектора Ь.

На графиках (рис. 1-4) показаны области, в которые попали значения нормы погрешности решения в зависимости от нормы погрешности исходных данных. Темные области на графиках — погрешности решения задачи в постановке А. Н. Тихонова (РМНК), светлые — метода наименьших квадратов (или нормаль- \ ного решения).

Пример 5.1.1. Поправка на неточность часов приемника значительно больше I смещения пользователя по координатам. Используются данные с четырех спутников.

Пример 5.1.2. Поправка на неточность часов приемника значительно больше смещения пользователя по координатам. Используются данные с пяти спутников.

Пример 5.1.3. Поправка на неточность часов приемника одного порядка со смещением пользователя по координатам. Используются данные с четырех спутников.

Пример 5.1.4- Поправка на неточность часов приемника одного порядка со

Рис, 5. Пример 5.1.1. Распределение нормы по- Рис. 6. Пример 5.1.1. Распределение нормы погрешности решения по МНК грешности решения по РМНК

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

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

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

Рассмотрена задача поиска решения интегрального уравнения Фредгольма I

рода

ъ

К(в,Ш)<й = д(8),

где заданы функции К(э, г) — ядро и — правая часть. Требуется определить неизвестную функцию

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

6

тором интеграл аппроксимируется взвешенной суммой: \ К(зЛ)}{1)<И « /п(г) =

а

п

£ щК{в, г?)/(7}), где щ = {Ь - а)/п, Ц = (; - |)(Ь - а)/п, з = 1,..., п.

г=1

С другой стороны, = д(вг), i = 1,...,п. Таким образом, получаем

систему вида Ах = 6, где матрица А и вектор Ь заданы лишь приближенно, что обусловлено погрешностями дискретизации.

Для данной задачи также было проведено несколько вычислительных экспе-

Рис. 7. Сравнение истинного решения инте- Рис. 8. Сравнение прогнозирования солнеч-грального уравнения с найденным ной активности разными методами

риментов, которые продемонстрировали применимость исследованных в работе методов. Вычисления производились при помощи алгоритмов [7, 8], описанных во втором разделе третьей главы. На рис. 7 представлены результаты одного из экспериментов.

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

Дан вектор у = [3/1 г/2 ••• Улг]Т £ компоненты которого являются

снятыми через промежутки времени значениями непрерывного сигнала ви- ( р

да у{{) = у*(Ь) 4- <$(£) = X] аце™ сов(ш$ + </?,) + <5(г), где у*({) — полезный сигнал,

¿=1 I

параметры р, а^А,,^,^ которого неизвестны, <5(£) — шум. Требуется оценить | неизвестные параметры полезного сигнала.

Интересующие нас СЛАУ возникают при поиске значений коэффициентов \ Для их определения можно воспользоваться приведенными ниже рассуждениями. Функция f{t) = у*{Ь) является решением уравнения вида + + I

Дг) + с2/(* + Ш) + ... + Ср/О + рАЬ) = 0.

Тогда для определения каждой из величин & = сце*'* + получаем

алгебраическое уравнение: со + сг£ + сг£2 + • ■ ■ + ср£р = 0.

Для нахождения коэффициентов с* придется решать следующую систему линейных алгебраических уравнений с матрицей Ганкеля (коэффициент Ср норми-

рован к 1):

Vi Уг ... Ур УР+1 У2 Уз - Vp+1 Vp+2

Со Cl

= 0. (8)

Ур Ур+1 - lttp-1 Vip J Cp-i

L i .

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

Для решения этой задачи могут быть применены алгоритмы [9, 10], описанные в первом разделе третьей главы. Т.к. в данном случае матрица системы имеет специальный вид, то использовался алгоритм [10].

Приводятся вычислительные эксперименты, показывающие адекватный характер построенной модели. На рис. 8 представлено сравнение прогнозирования солнечной активности с помощью этой модели с прогнозом NASA и с действительными данными для 23-го солнечного цикла.

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

Основные выводы:

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

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

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

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

Основное содержание диссертации отражено в работах

1. Волков В. В., Ерохин В. И. О тихоновских решениях приближенных систем линейных алгебраических уравнений при конечных возмущениях их матриц // Журнал вычислительной математики и математической физики. 2010. Т. 50, JV® 4. С. 618-635. (авторский вклад

- 50%).

2. Ерохин В. И., Волков В. В. Методы и модели восстановления линейных зависимостей по неточной информации // Известия Санкт-Петербургского государственного технологического института (технического университета). 2011. № 10. С. 53-58. (авторский вклад

- 50%).

3. Ерохин В. И., Волков В. В. Приближенные линейные модели в задачах позиционирования с использованием глобальных спутниковых навигационных систем // Системы управления и информационные технологии. 2010. № 4.1(42). С. 145-149. (авторский вклад — 50%).

4. Ерохин В. И., Волков В. В. Построение модельных приближенных систем линейных алгебраических уравнений с известными тихоновскими решениями // Сибирские электронные математические известия. 2010. Т. 7. С. 207-218. Труды первой Международной молодежной школы-конференции «Теория и численные методы решения обратных и некорректных задач». Часть I. URL: http://semr.math.nsc.ru/v7/l-394.pdf (дата обращения: 4.01.2011). (авторский вклад — 50%).

5. Волков В. В. Методы решения приближенных систем линейных алгебраических уравнений в задачах позиционирования с использованием глобальных спутниковых навигационных систем // Научная жизнь. 2010. № 6. С. 64-69.

6. Волков В. В. О возможной погрешности решения регуляризованной по Тихонову СЛАУ с возмущенной матрицей и точной правой частью // Информационные и коммуникационные технологии в образовании. Сборник материалов

X Международной научно-практической конференции в 2-х томах. Т. 2. Во-рисоглебск: ГОУ ВПО БГПИ, 2009. С. 175-179.

7. Волков В. В. Минимаксный алгоритм регуляризованного по Тихонову решения приближенной СЛАУ с учетом априорной информации о погрешности матрицы коэффициентов и правой части. Объединенный фонд электронных ресурсов «Наука и образование». Свидетельство о регистрации №15165. 28 декабря 2009 г.

8. Ерохин В. И., Волков В. В. Алгоритм регуляризованного по Тихонову решения приближенной СЛАУ с учетом априорной информации о погрешностях расширенной матрицы коэффициентов. Объединенный фонд электронных ресурсов «Наука и образование». Свидетельство о регистрации №16064. 10 августа 2010 г. (авторский вклад — 50%).

9. Ерохин В. И., Волков В. В., Красников А. С. Матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму взвешенной с индивидуальными весами евклидовой нормы. Отраслевой фонд алгоритмов и программ. Свидетельство о регистрации №5806. 09 марта 2006 г. (авторский вклад — 33%).

10. Ерохин В. И., Красников А. С., Волков В. В. Метод Ньютона для матричной коррекции однородных несовместных систем линейных алгебраических уравнений с матрицами Теплица по минимуму взвешенной с индивидуальными весами евклидовой нормы. Отраслевой фонд алгоритмов и программ. Свидетельство о регистрации №5798. 02 марта 2006 г. (авторский вклад — 33%).

11. Ерохин В. И., Волков В. В. Применение методов анализа временных рядов к задаче прогнозирования солнечной активности // Совершенствование преподавания физико-математических и общетехнических дисциплин в педвузе и школе. Сборник научных трудов Борисоглебского государственного педагогического института / ГОУ ВПО БГПИ. Борисоглебск, 2006. С. 6-11. (авторский вклад — 50%).

12. Ерохин В. И., Волков В. В. Применение регуляризации по А. Н. Тихонову к решению интегральных уравнений Фредгольма первого рода // Совершенствование преподавания физико-математических и общетехнических дисциплин в педвузе и школе. Сборник научных трудов Борисоглебского государственного педагогического института / ГОУ ВПО БГПИ. Борисоглебск, 2007. С. 71-75. (авторский вклад — 50%).

13. Ерохин В. И., Волков В. В. Тихоновская задача для приближенной системы линейных алгебраических уравнений с фиксированным блоком матрицы коэффициентов // Информационные и коммуникационные технологии в образовании. Сборник материалов XI Международной научно-практической конференции. Борисоглебск: ГОУ ВПО БГПИ, 2010. С. 252-255. (авторский вклад - 50%).

14. Ерохин В. И., Волков В. В. О некоторых взаимосвязях методов регуляризации и матричной коррекции при нахождении устойчивого решения приближенной системы линейных алгебраических уравнений // Обратные и некор-

ректные задачи математической физики: Труды международной конференции, посвященной 75-летию академика М. М. Лаврентьева / СО РАН. Новосибирск, 2007. и ГШ http://www.math.nsc.ru/conference/ipmp07/abstracts/ SectionЗ/ErohinVIVolkovW.pdf (дата обращения: 03.04.2010). (авторский вклад — 50%).

15. Ерохин В. И., Волков В. В. Устойчивые методы решения приближенных систем линейных алгебраических уравнений // Материалы ежегодной научной конференции преподавателей и студентов БГПИ по итогам НИР за 2006 год / ГОУ ВПО БГПИ. Борисоглебск, 2007. С. 24-27. (авторский вклад - 50%).

16. Волков В. В., Ерохин В. И. Некоторые свойства решений по А. Н. Тихонову приближенных систем линейных алгебраических уравнений // Проблемы теоретической и прикладной математики: Труды 38-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2007. С. 90-94. (авторский вклад — 50%).

17. Ерохин В. И., Волков В. В. Использование подхода А. Н. Тихонова для решения приближенных систем уравнений специального вида // Информационные и коммуникационные технологии в образовании. Сборник материалов VII Всероссийской научно-практической конференции. Борисоглебск: ГОУ ВПО БГПИ, 2006. С. 107-110. (авторский вклад - 50%).

18. Красников А. С., Волков В. В., Ерохин В. И. Алгоритм матричной коррекции несовместных однородных систем линейных алгебраических уравнений с матрицами Теплица по минимуму евклидовой нормы // Проблемы теоретической и прикладной математики: Труды 37-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2006. С. 127-131. (авторский вклад - 33%).

19. Волков В. В., Ерохин В. И., Красников А. С. Использование матричной коррекции систем линейных алгебраических уравнений специального вида в задаче прогнозирования солнечной активности // Проблемы теоретической и прикладной математики: Труды 37-й Региональной молодежной конференции. Екатеринбург: УрО РАН, 2006. С. 122-126. (авторский вклад - 33%).

20. Ерохин В. И., Волков В. В., Красников А. С. Матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы, взвешенной с произвольными положительными весами // Информаг ционные и коммуникационные технологии в образовании. Сборник материалов VI Всероссийской научно-практической конференции. Борисоглебск: ГОУ ВПО БГПИ, 2005. С. 90-95. (авторский вклад - 33%).

21. Ерохин В. И., Красников А. С., Волков В. В. Метод Ньютона для матричной коррекции несовместных систем линейных алгебраических уравнений со специальной структурой по минимуму взвешенной евклидовой нормы // Информационные и коммуникационные технологии в образовании. Сборник материалов VI Всероссийской научно-практической конференции. Борисоглебск: ГОУ ВПО БГПИ, 2005. С. 95-102. (авторский вклад - 33%).

Подп. к печ. 05.05.2011 Объем 1,25 пл. Зак. № 59 Тир, 100 экз.

Типография МПГУ

Введение

Список используемых обозначений

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

1.1. СЛАУ с приближенной правой частью и классический метод наименьших квадратов.

1.2. Регуляризованный метод наименьших квадратов А. Н. Тихонова

1.2.1. Формализация регуляризованного метода наименьших квадратов.

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

1.2.3. Сведение РМНК к задаче математического программирования

1.2.4. РМНК для приближенной системы линейных алгебраических уравнений с фиксированным блоком матрицы коэффициентов.

1.3. Матричная коррекция приближенных несовместных СЛАУ

1.3.1. Постановки задач матричной коррекции приближенных несовместных СЛАУ

1.3.2. Условия существования решения задач матричной коррекции и вид множеств решений скорректированных систем.

1.3.3.

Задачи матричной коррекции несовместных СЛАУ специального вида с матрицами Теплица (Ганкеля)

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

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

2.2. Вспомогательные леммы.

2.3. Доказательство теоремы и численные примеры.

Глава 3. Вычислительные алгоритмы восстановления линейных зависимостей, формализованных приближенными « СЛАУ

3.1. Алгоритмы матричной коррекции приближенных СЛАУ

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

3.1.2. Матричная коррекция несовместных СЛАУ со специальной структурой по минимуму взвешенной евклидовой нормы.

3.1.3. Вычислительные эксперименты.

3.2. Алгоритмы РМНК.

3.2.1. Методы построения модельных приближенных СЛАУ

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

3.2.3. Минимаксный алгоритм РМНК.

Глава 4. Оценка близости решения РМНК-решения приближенной системы к гипотетическому решению точной системы при точной правой части и приближенной матрице коэффициентов

4.1. Априорные нижние оценки максимальной относительной погрешности решения задачи РМНК.

4.2. Вычислительные эксперименты.

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

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

5.1.1. Общие сведения о системах глобального позиционирования

5.1.2. Математическая модель систем глобального позиционирования

5.2. Восстановление линейных зависимостей, формализованных интегральными уравнениями Фредгольма первого рода.

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

Актуальность работы.

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

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

Одним из принципиально новых методов моделирования является алгебраический подход к распознаванию образов с использованием эвристических информационных моделей, предложенный и исследованный академиком РАН Ю. И. Журавлевым и его учениками и коллегами академиком РАН В. Л. Мат-росовым (статистическое обоснование алгебраического подхода), членом-корреспондентом РАН К. В. Рудаковым (общая теория проблемно-ориентированного алгебраического синтеза корректных алгоритмов), К. В. Воронцовым, В. В. Рязановым и другими [23, 24, 70-72, 88-90]. Учеными этой научной школы активно исследуется статистическая теория Вапника-Червоненкиса [5, 6], в частности, рассматривается статистическая оценка качества алгоритмов обучения распознаванию [25, 26].

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

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

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

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

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

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

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

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

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

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

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

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

Также большой вклад в эту область внесли А. С. Апарцин, А. Б. Баку-шинский, Ф. П. Васильев, В. В. Васин, Ю. Е. Воскобойников, С. И. Кабани-хин, А. С. Леонов, В. И. Цурков и многие другие [2, 3, 7-10, 27-30, 103, 104, 106, 125].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Получены 4 свидетельства о регистрации алгоритмов [16, 60, 66, 68].

Публикации. Материалы, составляющие основное содержание диссертации, опубликованы в 17 печатных работах, из них 3 статьи в изданиях, включенных в перечень ВАК РФ [20, 62, 64], 2 статьи в журналах [18, 61], 12 — в сборниках и трудах конференций [17, 19, 21, 54-58, 63, 65, 67, 75].

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

Основные выводы:

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

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

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

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

Заключение

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

1. Алберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. М.: Наука, 1977. 224 с.

2. Апарцин А. С., Тен Мен Ян. О неулучшаемых оценках решений некоторых интегральных неравенств // Сиб. матем. журн. 1979. Т. 20, № 1. С. 192-195.

3. Бакушинский А. Б., Апарцин А. С. Методы типа стохастической аппроксимации для решения линейных некорректных задач // Сиб. матем. журн. 1975. Т. 16, № 1. С. 12-18.

4. Бакушинский А. Б., Гончарский А. В. Некорректные задачи. Численные методы и приложения. М.: Изд-во Моск. ун-та, 1989. 199 с.

5. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. М.: Наука, 1979. 448 с.

6. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов (статистические проблемы обучения). М.: Наука, 1974. 416 с.

7. Васильев Ф. П. О регуляризации некорректных задач минимизации на множествах, заданных приближенно // Журнал вычислительной математики и математической физики. 1980. Т. 20, № 1. С. 38-50.

8. Васильев Ф. П. К вопросу устойчивости методов регуляризации в линейном программировании // Вестник Московск. ун-та. Сер. 15. Вычислит, матем. и киберн. 1998. № 3. С. 19-23.

9. Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. М.: Факториал Пресс, 2003. 352 с.

10. Васильев Ф. П., Иваницкий А. Ю., Морозов В. Оценка скорости сходимости метода невязки для задач линейного программирования с приближенными данными // Журнал вычислительной математики и математической физики. 1990.- Т. 30, № 8. С. 1257-1262.

11. Ватолин А. А. Аппроксимация несобственных задач линейного программирования по критерию евклидовой нормы // Журнал вычислительнойматематики и математической физики. 1984. Т. 24, № 12. С. 1907-1908.

12. Ватолин А. А. О коррекции расширенной матрицы несовместной системы линейных не-равенств и уравнений // Комбинаторные, алгебраические и вероятностные методы дискретного анализа. Горький, 1989. С. 40-54.

13. Верлань А. Ф., Сизиков В. С. Интегральные уравнения: методы, алгоритмы, программы. Киев: Наукова думка, 1986. 544 с.

14. Витинский Ю. И. Цикличность и прогнозы солнечной активности. Л.: Наука, 1973. 258 с.

15. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. М.: Наука, 1984. 320 с.

16. Волков В. В. Методы решения приближенных систем линейных алгебраических уравнений в задачах позиционирования с использованием глобальных спутниковых навигационных систем // Научная жизнь. 2010. № 6. С. 64-69.

17. Волков В. В., Ерохин В. И. О тихоновских решениях приближенных систем линейных алгебраических уравнений при конечных возмущениях их матриц // Журнал вычислительной математики и математической физики. 2010. Т. 50, № 4. С. 618-635.

18. Воронцов К. В. Качество восстановления зависимостей по эмпирическим данным // Математические методы распознавания образов: 7-ая Всерос. конф. Тезисы докладов. Пущино: 1995. С. 24-26.

19. Воронцов К. В. Оптимизационные методы линейной и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Журнал вычислительной математики и математической физики. 2000. Т. 40, № 1. С. 166-176.

20. Воронцов К. В. Комбинаторные обоснования обучаемых алгоритмов // Журнал вычислительной математики и математической физики. 2004. Т. 44, № И. С. 2099-2112.

21. Воронцов К. В. Комбинаторные оценки качества обучения по прецедентам // Доклады РАН. 2004. Т. 394, № 2. С. 175-178.

22. Воронцов К. В. Комбинаторный подход к оценке качества обучаемых алгоритмов // Математические вопросы кибернетики. 2004. Т. 13. С. 5-36.

23. Воскобойников Ю. Е. Численная реализация и сравнение четырех способов выбора параметра регуляризации в устойчивых алгоритмах декон-волюции // Научный вестник НГТУ. 2004. Т. 17, № 2. С. 27-44.

24. Воскобойников Ю. Е. Устойчивые методы и алгоритмы параметрической идентификации. Новосибирск: Изд-во НГАСУ, 2006. 186 с.

25. Воскобойников Ю. Е., Преображенский Н. Г. Выбор параметра регуляризации при решении обратных измерительных задач // Автометрия. 1984. № 2. С. 31-38.

26. Глобальная навигационная спутниковая система ГЛОНАСС. Интерфейсный контрольный документ (редакция 5.1). М., 2008. 74 с.

27. Глобальная спутниковая радионавигационная система ГЛОНАСС, Под ред. В. Н. Харисова, А. И. Перова, В. А. Болдина. М.: ИПРЖР, 1998. 400 с.

28. Голуб Д., Лоун Ч. В. Матричные вычисления. М.: Мир, 1999. 548 с.

29. Горелик В. А. Матричная коррекция задачи линейного программирования с несовместной системой ограничений // Журнал вычислительной математики и математической физики. 2001. Т. 41, № 11. С. 1697-1705.

30. Горелик В. А., Ерохин В. И. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений по минимуму евклидовой нормы. М.: ВЦ РАН, 2004. 193 с.

31. Горелик В. А., Ерохин В. И., Печенкин Р. В. Матричная коррекция несовместных линейных систем с матрицами Теплица (Ганкеля) // Моделирование, декомпозиция и оптимизация сложных динамических процессов / ВЦ РАН. М., 2003. С. 41-73.

32. Горелик В. А., Ерохин В. И., Печенкин Р. В. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений с блочными матрицами коэффициентов // Дискрет, анализ и исслед. операций. Серия 2. 2005. Т. 12, № 2. С. 3-22.

33. Горелик В. А., Ерохин В. И., Печенкин Р. В. Численные методы коррекции несобственных задач линейного программирования и структурных систем уравнений. М.: ВЦ РАН, 2006. 153 с.

34. Горелик В. А., Кондратьева В. А. Параметрическое программирование и несобственные задачи линейной оптимизации // Моделирование, декомпозиция и оптимизация сложных динамических процессов / ВЦ РАН. М., 1999. С. 57-82.

35. Горелик В. А., Муравьева О. В. Задача аппроксимации с коррекцией всех данных // Моделирование, декомпозиция и оптимизация сложных динамических процессов / ВЦ РАН. М., 2000. С. 21-32.

36. Горелик В. А., Муравьева О. В. Коррекция несовместной системы линейных уравнений с дополнительными ограничениями // Декомпозиционные методы в математическом моделировании. Тез. докл. 1-й Московской конференции. М.: ВЦ РАН, 2001. С. 36-37.

37. Горелик В. А., Муравьева О. В. Методы коррекции данных в задаче распознавания образов // Декомпозиционные методы в математическом моделировании. Тез. докл. 2-й Московской конференции. М.: ВЦ РАН, 2004. С. 39.

38. Горелик В. А., Муравьева О. В. Матричная коррекция данных в задачах оптимизации и классификации // Моделирование, декомпозиция и оптимизация сложных динамических процессов / ВЦ РАН. М., 2004. С. 94-120.

39. Демьянов В. Ф., Малоземов В. Н. Введение в минимакс. М.: Наука, 1972. 368 с.

40. Демьянов В. Ф., Рубинов А. М. Приближенные методы решения экстремальных задач. Л.: Изд-во Ленинградского университета, 1968. 181 с.

41. Еремин И. И. Противоречивые модели оптимального планирования. М.: Наука, 1988. 160 с.

42. Еремин И. И., Ватолин А. А. Двойственность для несобственных бесконечномерных задач линейного и выпуклого программирования // Методы аппроксимации несобственной задачи линейного программирования, УНЦ АН СССР. Свердловск, 1984. С. 3-20.

43. Еремин И. И., Мазуров В. Д., Астафьев Н. Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.

44. Ерохин В. И. Оптимальная матричная коррекция несовместных систем линейных алгебраических уравнений и несобственных задач линейного программирования: Дисс. . д-ра физ.-мат. наук: 05.13.17. М., 2005.

45. Ерохин В. И., Волков В. В. Приближенные линейные модели в задачахпозиционирования с использованием глобальных спутниковых навигационных систем // Системы управления и информационные технологии. 2010. № 4.1(42). С. 145-149.

46. Ерохин В. И., Волков В. В. Методы и модели восстановления линейных зависимостей по неточной информации // Известия Санкт-Петербургского государственного технологического института (технического университета). 2011. № 10. С. 53-58.

47. Ерохин В. И., Печенкин Р. В. Идентификация сигнала в виде суммы экспонент с помощью метода ТЬК // Математическое программирование и приложения: Тез. докл. 12-й Всероссийской конференции. Екатеринбург: УрО РАН, 2003. С. 105-106.

48. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики / Наука. М., 1987. 33. С. 5-68.

49. Журавлев Ю. И., Рудаков К. В. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. 1987. С. 187-198.

50. Журавлев Ю. И., Рязанов В. В., Сенько О. В. Распознавание. Математические методы. Программная система. Практические применения. М.: Фазис, 2005. 159 с.

51. Иванов В. К., Васин В. В., Танана В. П. Теория линейных некорректных задач и ее приложения. М.: Наука, 1978. 206 с.

52. Информационно-аналитический центр Федерального космического агентства. Архив данных. 1ЖЬ: ftp://ftp.glonass-iac.ru/MCC (дата обращения: 01.09.2010).

53. Лаврентьев М. М. О некоторых некорректных задачах математической физики. Новосибирск: СО АН СССР, 1962. 96 с.

54. Ланцош К. Практические методы прикладного анализа. М.: Физматгиз, 1961. 524 с.

55. Лоусон Ч., Хенсон Р. Численное решение задач метода наименьших квадратов. М.: Наука, 1986. 232 с.

56. Льюнг Л. Идентификация систем. Теория для пользователя. М.: Наука, 1991. 432 с.

57. Мазуров В. Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. 248 с.

58. Марпл-мл. С. Л. Цифровой спектральный анализ и его приложения. М.: Мир, 1990. 584 с.

59. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990. 488 с.

60. Муравьева О. В. Матричная коррекция данных для несовместных систем линейных уравнений и ее применение в задачах оптимизации и классификации: Дисс. . канд. физ.-мат. наук: 05.13.17. М., 2002.

61. Насыров И: А. Введение в современные спутниковые радионавигационные системы. Казань: КГУ, 2005. 43 с.

62. Одуан К., Гино Б. Измерение времени. Основы GPS. М.: Техносфера, 2002. 400 с.

63. Печенкин Р. В. Задача идентификации сигнала с использованием регу-ляризованного алгоритма SNTLN // Алгоритмический анализ неустойчивых задач. Тез. докл. Всеросс. конференции. Екатеринбург: Изд-во Урал, ун-та, 2004. С. 362-363.

64. Рудаков К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания: Дисс. . д-ра физ.-мат. наук. 1992.

65. Рудаков К. В., Воронцов К. В. О методах оптимизации и монотонной коррекции в алгебраическом подходе к проблеме распознавания // Доклады РАН. 1999. Т. 367, № 3. С. 314-317.

66. Рязанов В. В. Логические закономерности в задачах распознавания (параметрический подход) // Журнал вычислительной математики и математической физики. 2007. Т. 47, № 10. С. 1793-1808.

67. Сизиков В. С. Устойчивые методы обработки результатов измерений. СПб.: СпецЛит, 1999. 240 с.

68. Тихонов А. Н. Об устойчивости обратных задач // Доклады АН СССР. 1943. Т. 39, № 4. С. 195-198.

69. Тихонов А. Н. О регуляризации некорректно поставленных задач // Доклады АН СССР. 1963. Т. 153, № 1. С. 49-52.

70. Тихонов А. Н. О решении некорректно поставленных задач и методе регуляризации // Доклады АН СССР. 1963. Т. 151, № 1. С. 501—504.

71. Тихонов А. Н. О некорректных задачах линейной алгебры и устойчивом методе их решения // Доклады АН СССР. 1965. Т. 163, № 3. С. 591-594.

72. Тихонов А. Н. О нормальных решениях приближенных систем линейных алгебраических уравнений // Доклады АН СССР. 1980. Т. 254, № 3. С. 549-554.

73. Тихонов А. Н. О приближенных системах линейных алгебраических уравнений // Журнал вычислительной математики и математической физики. 1980. Т. 20, № 6. С. 1373-1383.

74. Тихонов А. Н. О методах автоматизации обработки наблюдений // Вестник АН СССР. 1983. № 1. С. 14-25.

75. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1986. 288 с.

76. Тихонов А. Н., Гончарский А. В., Степанов В. В., Ягола А. Г. Численные методы решения некорректных задач. М.: Наука, 1990. 229 с.

77. Химмельблау Д. Анализ процессов статистическими методами. М.: Мир, 1993. 956 с.

78. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989. 655 с.

79. Цурков В. И. Декомпозиция в задачах большой размерности. М.: Наука, 1981. 352 с.

80. Цурков В. И. Динамические задачи большой размерности. М.: Наука, 1988. 287 с.

81. Яценков В. С. Основы спутниковой навигации. Системы GPS NAVSTAR и ГЛОНАСС. М.: Горячая линия-Телеком, 2005. 272 с.

82. Apartsin A. S. Some ill-posed problems and their applications in energy research // Sov. Tech. Rev. A. Energy. 1992. Vol. 6, no. 1. Pp. 65-125.

83. Branham R. J. Astronomical data reduction with total least squares // New

84. Astronomy Reviews. 2001. Vol. 45. Pp. 649-661.

85. De Groen P. An introduction to total least squares // Niew Archief voor Wiskunde. 1996. Vol. 14, no. 2. Pp. 237-254.

86. Gauss C. F. Theoria motus corporum coelestium in sectionibus conicis solem ambientium. Hamburgi: F. Perthes et I. H. Besser, 2003.

87. Golub G. H., Hansen P. C., O'Leary D. P. Tikhonov regularization and total least squares // SIAM Journal on Matrix Analysis and Applications. 1999. Vol. 21, no. 1. Pp. 185-194.

88. Golub G. H., Van Loan C. F. An analysis of the total least squares problem // SIAM J. Numer. Anal. 1980. Vol. 17, no. 3. Pp. 883-893.

89. Gorelik V. A., Pechenkin R. V. Decomposition approach for solving signal identification problem // Декомпозиционные методы в математическом моделировании и информатике. Тез. докл. 2-й Московской конференции. М.: ВЦ РАН, 2004. С. 41-42.

90. Hansen С. Regularization Tools. A Matlab Package for Analysis and Solution of Discrete Ill-Posed Problems // Numerical Algorithms. 2007. Vol. 46. Pp. 189-194.

91. Hansen C. Regularization Tools. A Matlab Package for Analysis and Solution of Discrete Ill-Posed Problems. The accompanying manual, 2008. URL: http://www2.imm.dtu.dk/~pch/Regutools/RTv4manual.pdf (дата обращения: 01.09.2010).

92. Legendre A. M. Nouvelles methodes pour la determination des orbites des cometes. Paris: Courcier, 1806.

93. Louis A. K. A mollifier method for linear operator equations of the first kind // Inverse Problems. 1990. Vol. 6. Pp. 427-440.

94. Marquardt D. W. An algorithm for least squares estimation of nonlinear parameters // J. Soc. Indust. Appl. Math. 1963. Vol. 11, no. 2. Pp. 431-441.

95. Mazurov V. D., Khachai M. U., Rybin A. I. Committee Constructions for Solving Problems of Selection, Diagnostics and Prediction // Proceedings of Steklov Inst, of Math. Suppl. 2002. № 1. C. 67-101.

96. Morrison D. D. Methods for nonlinear least squares problems and convergence proofs // Proc. Seminar Tracking Programs and Orbit Determination. Calif., Pasadena, Jet Propulsion Lab. 1960. Pp. 1-9.

97. National Geophysical Data Center. Solar Data. URL: ftp://ftp.ngdc. noaa.gov/STP/SOLARDATA/ (дата обращения: 01.09.2010).

98. Nievergelt Y. A tutorial history of least squares with applications to astronomy and geodesy // Journal of Computational and Applied Mathematics. 2000. Vol. 121, no. 1-2. Pp. 37-72.

99. Prasad R., Ruggieri M. Applied satellite navigation using GPS, GALILEO, and augmentation systems. Artech: House mobile communications series, 2005. 309 pp.

100. Rosen J. В., Park H., Glick J. Total least norm formulation and solution for structured problems // SIAM Journal on Matrix Anal. Appl. 1996. Vol. 17, no. 1. Pp. 110-128.

101. Stewart G. W. On the early history of the singular value decomposition // SIAM Rev. 1993. Vol. 35, no. 4. Pp. 551-566.

102. Tkurkov V. I. Large-scale Optimization Problems and Methods. Dordrecht: Kluwer Academic Publishers, 2001. 320 pp.

103. Van Huffel S., Vandewalle J. The total least squares problem: computational aspects and analysis // Frontiers in applied mathematics. Philadelphia: SIAM. 1991. Vol. 9.

104. Vapnik V. Estimation of Dependencies Based on Empirical Data. New York: Springer-Verlag, 1982.

105. Varah J. M. Pitfalls in the numerical solution of linear ill-posted problems // SIAM J. Sci. Stat. Comput. 1983. Vol. 4. Pp. 164-176.

106. Watson G. A. Data fitting problems with bounded uncertainties in the data // SIAM J. Matrix Anal. Appl. 2001. Vol. 22, no. 4. Pp. 1274-1293.

107. Xu G. GPS: Theory, Algorithms and Applications. Potsdam, 2007. 353 c.