Содержание к диссертации
Введение
Глава 1. Приближенные СЛАУ как инструмент восстановления линейных зависимостей по неточной информации: формальное описание и методы решения 18
1.1. СЛАУ с приближенной правой частью и классический метод наименьших квадратов 18
1.2. Регуляризованный метод наименьших квадратов А. Н. Тихонова 22
1.2.1. Формализация регуляризованного метода наименьших квадратов 22
1.2.2. Обобщение теоремы Тихонова об устойчивом приближении РМНК-решения к нормальному решению точной системы на случай неодинаковых погрешностей матрицы коэффициентов и правой части приближенной СЛАУ 24
1.2.3. Сведение РМНК к задаче математического программирования 28
1.2.4. РМНК для приближенной системы линейных алгебраических уравнений с фиксированным блоком матрицы коэффициентов 29
1.3. Матричная коррекция приближенных несовместных СЛАУ 33
1.3.1. Постановки задач матричной коррекции приближенных несовместных СЛАУ 33
1.3.2. Условия существования решения задач матричной коррекции и вид множеств решений скорректированных систем 35
1.3.3. Задачи матричной коррекции несовместных СЛАУ специального вида с матрицами Теплица (Ганкеля) 36
Глава 2. Исследование взаимосвязи методов регуляризации и матричной коррекции при нахождении устойчивых решений приближенных СЛАУ 42
2.1. Теорема об условиях эквивалентности задачи РМНК задаче минимизации сглаживающего функционала, методу наименьших квадратов и матричной коррекции 42
2.2. Вспомогательные леммы 43
2.3. Доказательство теоремы и численные примеры 50
Глава 3. Вычислительные алгоритмы восстановления линейных зависимостей, формализованных приближенными « СЛАУ » 57
3.1. Алгоритмы матричной коррекции приближенных СЛАУ 57
3.1.1. Матричная коррекция несовместных СЛАУ по минимуму евклидовой нормы, взвешенной с произвольными положительными весами 57
3.1.2. Матричная коррекция несовместных СЛАУ со специальной структурой по минимуму взвешенной евклидовой нормы 60
3.1.3. Вычислительные эксперименты 65
3.2. Алгоритмы РМНК 69
3.2.1. Методы построения модельных приближенных СЛАУ 70
3.2.2. Алгоритм РМНК основанный на использовании условий Лагранжа и его модификация на случай набора точных столбцов в приближенной матрице коэффициентов исследуемой СЛАУ 73
3.2.3. Минимаксный алгоритм РМНК 76
Глава 4. Оценка близости репіения РМНК-решения прибли женной системы к гипотетическому решению точной системы при точной правой части и приближенной матрице коэффициентов 83
4.1. Априорные нижние оценки максимальной относительной погрешности решения задачи РМНК 83
4.2. Вычислительные эксперименты 90
Глава 5. Примеры использования аппарата приближенных СЛАУ для решения практических задач восстановления ли нейных зависимостей по неточной информации 97
5.1. «Очистка» измерительных данных приближенной линейной модели от шума на примере задачи позиционирования объекта с использованием глобальных спутниковых навигационных систем 97
5.1.1. Общие сведения о системах глобального позиционирования 97
5.1.2. Математическая модель систем глобального позиционирования 101
5.2. Восстановление линейных зависимостей, формализованных интегральными уравнениями Фредгольма первого рода 109
5.3. Параметрическая идентификация сигнала, являющегося решением системы линейных разностных уравнений на примере задачи прогнозирования солнечной активности 112
Заключение 120
Литература 122
- Регуляризованный метод наименьших квадратов А. Н. Тихонова
- Постановки задач матричной коррекции приближенных несовместных СЛАУ
- Матричная коррекция несовместных СЛАУ со специальной структурой по минимуму взвешенной евклидовой нормы
- Восстановление линейных зависимостей, формализованных интегральными уравнениями Фредгольма первого рода
Введение к работе
Актуальность работы. Задачи восстановления линейных зависимостей по неточной информации весьма широко распространены и часто возникают в приложениях, связанных с обработкой подверженной погрешностям экспериментальной информации. Примерами подобных прикладных задач являются проблемы распознавания зависимостей, анализа временных рядов, обработки наблюдений, очистки данных от шума, параметрической идентификации линейных зависимостей по экспериментальным данным, обратные задачи математической физики, встречающиеся в различных областях науки и техники.
В зависимости от специфики прикладной проблемы могут возникать различные классы задач, сводящиеся как к системам уравнений и неравенств, так и требующие более сложных моделей. Часто подобные модели приводят к задачам распознавания образов и классификации.
Одним из принципиально новых методов моделирования является алгебраический подход к распознаванию образов с использованием эвристических информационных моделей, предложенный и исследованный академиком РАН Ю. И. Журавлевым и его учениками и коллегами академиком РАН В. Л. Матросовым (статистическое обоснование алгебраического подхода), членом-корреспондентом РАН К. В. Рудаковым (общая теория проблемно-ориентированного алгебраического синтеза корректных алгоритмов), К. В. Воронцовым, В. В. Рязановым и другими.
Оригинальной методикой решения задачи обучения распознаванию образов является теория комитетов, тесно связанная с упомянутым алгебраическим подходом к распознаванию образов. Первые исследования в этом направлении принадлежат научной школе академика И. И. Еремина.
Указанные выше подходы наиболее перспективны для решения прикладных задач в тех предметных областях, для которых нет адекватных математических моделей.
В контексте настоящего исследования наиболее интересен случай, когда в описанных приложениях распознавания зависимостей и обработки данных возникают приближенные системы линейных алгебраических уравнений (СЛАУ). Для решения таких СЛАУ, как правило, используются два альтернативных подхода.
Первый подход представляет метод наименьших квадратов (МНК), предложенный для решения приближенных СЛАУ еще Лежандром и Гауссом. В традиционной формулировке МНК заключается в поиске вектора решения, минимизирующего норму невязки системы. Однако классический МНК можно также сформулировать как задачу поиска такого вектора поправок к правой части, который делает приближенную систему совместной и имеет минимальную норму.
Дальнейшим развитием этого подхода стал так называемый обобщенный метод наименьших квадратов — Total Least Squares (TLS). TLS обобщает подход МНК, распространяя поправки не только на правую часть, но и на матрицу коэффициентов системы. При использовании этого метода ставится задача найти
такую минимальную по норме матрицу коррекции, что при ее добавлении к приближенной матрице исследуемая приближенная СЛАУ становится совместной.
За рубежом интенсивные исследования метода TLS и его модификаций, а также его активное использование при решении прикладных задач начались в конце 80-х годов XX века после появления работ бельгийского математика S. Van Haffel. Также заметный вклад внесли J. Vandewalle, J. В. Rosen, G. Н. Golub и другие.
В отечественных научных работах методы, основанные на обобщении и модификации классического метода наименьших квадратов, получили название матричной коррекции.
Исследования в этом направлении велись параллельно с зарубежными учеными. Первые результаты, связанные с матричной коррекцией систем линейных алгебраических уравнений и несобственных задач математического программирования получены научной школой Института математики и механики УрО РАН под руководством академика РАН И. И. Еремина. Так, матричная коррекция СЛАУ впервые была рассмотрена в работах ученика академика И. И. Еремина А. А. Ватолина в середине 80-х годов XX в.
Исследования И. И. Еремина и А. А. Ватолина в конце 90-х годов XX в. были продолжены (и продолжаются в настоящее время) в ВЦ им. А. А. Дородницына РАН В. А. Гореликом и его коллегами и учениками: В. И. Ерохиным, Р. Р. Иба-туллиным, В. А. Кондратьевой, О. В. Муравьевой, Р. В. Печенкиным и другими.
Одна из наиболее существенных проблем МНК, а также его модификаций и обобщений, заключается в том, что минимизация нормы соответствующих поправок происходит без учета информации о погрешностях исходных данных и является безусловной. Как следствие, нормы поправок могут оказаться существенно меньше истинных значений погрешностей, в силу чего шум интерпретируется как полезный сигнал и соответствующее решение оказывается далеко от истинного решения точной системы.
Альтернативный подход к решению приближенных СЛАУ, предложенный академиком А. Н. Тихоновым, заключается в построении для заданной приближенной СЛАУ регуляризующего алгоритма, который при определенном выборе регуляризующего параметра позволяет получить устойчивое решение этой системы. Тихоновым же предложен способ поиска регуляризованного решения с помощью минимизации сглаживающего функционала. Аппарат регуляризации открыл новое направление в решении некорректных задач.
Основополагающие подходы для теории некорректных задач связаны с именами А. Н. Тихонова, В. К. Иванова, М. М. Лаврентьева. Монографии А. И. Тихонова, В. Я. Арсенина и В. К. Иванова, В. В. Васина, В. П. Тананы являются ключевыми для теории линейных некорректных задач.
Также большой вклад в эту область внесли А. С. Апарцин, А. Б. Баку-шинский, Ф. П. Васильев, В. В. Васин, Ю. Е. Воскобойников, С. И. Кабанихин, А. С. Леонов, В. И. Цурков и многие другие.
Однако и в данном подходе существуют проблемы, связанные с тем, что в классическом случае при минимизации сглаживающего функционала также не
привлекается информация об истинных погрешностях матрицы коэффициентов и правой части приближенной системы. Поэтому существует опасность «заглаживания» решения, также уводящая его от истинного решения точной системы.
В 80-х годах XX в. А. Н. Тихоновым был предложен подход к регуляризации (позже названный им регуляризованным методом наименьших квадратов — РМНК), привлекающий для решения исходной приближенной системы априорную информацию — сведения о величине ошибок, накладывающихся на матрицу коэффициентов и правую часть. Такой подход позволяет избежать недостатков, присущих перечисленным выше методам, но накладывает повышенные требования на исходные данные (необходимо привлекать априорные сведения о погрешностях). Кроме того, проблемами данного метода являются плохая численная обусловленность задачи, отсутствие эффективных алгоритмов решения, неизученность поведения решений при конечных значениях погрешностей исходных данных.
Отметим, что до настоящего времени методы матричной коррекции и регуляризации приближенных линейных моделей не рассматривались во взаимосвязи и с единых позиций.
Не до конца исследован вопрос об условиях существования решений, получаемых указанными методами, не известны априорные оценки максимальных возможных погрешностей этих решений. И, наконец, весьма актуальной проблемой является разработка эффективных вычислительных процедур решения практических задач с использованием упомянутых подходов. До сих пор ощущается нехватка готовых алгоритмов, которые могли бы быть использованы при анализе приближенных линейных моделей и обработке неточной информации. Необходимы также и исследования приближенных линейных моделей специального вида (с матрицами специальной структуры), встречающихся на практике.
Таким образом, развитие методов и алгоритмов решения приближенных СЛАУ и восстановления линейных зависимостей является актуальной научной проблемой.
Объектом исследования служат задачи восстановления линейных зависимостей, встречающиеся в приложениях, связанных с обработкой зашум ленных или подверженных погрешностям данных.
Предмет исследования составляют методы и алгоритмы построения решений приближенных систем линейных алгебраических уравнений и задач восстановления линейных зависимостей, а также свойства указанных решений: существование, единственность, чувствительность к погрешностям исходных данных, близость к решениям гипотетических точных систем линейных алгебраических уравнений.
Цель диссертационной работы состоит в развитии математического аппарата оптимальной матричной коррекции несовместных СЛАУ (А. А. Ватолин, В. А. Горелик, В. И. Ерохин и др.) и математического аппарата построения регуля-ризованных решений приближенных СЛАУ (А. Н. Тихонов) на случай конечных по величине погрешностей в матрице коэффициентов приближенной системы и
векторе ее правой части, а также в построении соответствующих вычислительных алгоритмов.
В основу исследования положена гипотеза о том, что любая приближенная линейная модель, возникающая в задаче восстановления линейных зависимостей, формализованная в виде приближенной СЛАУ, может быть сопоставлена с некоторой гипотетической точной линейной моделью, формализованной в виде совместной СЛАУ, нормальное решение, матрица коэффициентов и правая часть которой считаются точными. При этом существуют математические методы и вычислительные алгоритмы, позволяющие на основе априорной информации о мере близости приближенной линейной модели к точной вычислять асимптотически устойчивое решение приближенной системы и оценивать меру близости этого решения к нормальному решению точной системы при конечных ненулевых погрешностях, и, как следствие, получать восстановленные линейные зависимости.
Для достижения поставленной цели и проверки правильности выдвинутой гипотезы требуется решить следующие задачи:
Получить необходимые и достаточные условия эквивалентности задачи решения приближенной СЛАУ в постановке А. Н. Тихонова (РМНК) задаче минимизации сглаживающего функционала, методу наименьших квадратов, либо задаче минимальной матричной коррекции.
Оценить максимальное по евклидовой норме относительное отклонение решения приближенной СЛАУ от нормального решения гипотетической точной СЛАУ.
Разработать, теоретически обосновать и проверить в вычислительных экспериментах алгоритмы решения приближенных СЛАУ при различных условиях, а также некоторых, важных для практических приложений, дополнительных модификациях задачи, таких как специальный вид матрицы коэффициентов СЛАУ или запрет на коррекцию отдельных столбцов матрицы коэффициентов исследуемой линейной модели.
Рассмотреть приложения разработанной теории и методов решения приближенных СЛАУ и анализа приближенных линейных моделей к решению практических задач восстановления линейных зависимостей по неточной информации.
Методологическую основу работы составляют методы классической и вычислительной линейной алгебры, матричного анализа, математического программирования.
Научная новизна диссертации заключается в том, что впервые исследована взаимосвязь методов минимальной матричной коррекции, минимизации сглаживающего функционала и метода наименьших квадратов в задаче решения приближенной СЛАУ и построены априорные оценки максимального отклонения между решениями точной и приближенной СЛАУ при конечных ненулевых погрешностях в матрице коэффициентов приближенной линейной модели. Элементы новизны содержатся в разработанных вычислительных алгоритмах решения приближенных СЛАУ. Новой является постановка задачи и теоретическое обоснование
методов решения для проблемы поиска решения приближенной СЛАУ с фиксированными столбцами матрицы коэффициентов.
Практическая значимость результатов. Предложенные в работе методы и алгоритмы построения и анализа решений приближенных СЛАУ могут быть использованы в задачах обработки зашумленных данных, прогнозирования и управления, относящихся к области исследования специальности 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 страниц.
Регуляризованный метод наименьших квадратов А. Н. Тихонова
В настоящем разделе и далее в диссертации под решением по А. Н. Тихонову приближенной СЛАУ будем понимать метод, предложенный А. Н. Тихоновым в работах [96, 97] и позже названный им регуляризованным методом наименьших квадратов (РМНК) [98]. Следуя работам А. Н. Тихонова [96, 97], будем проблему отыскания устойчивого решения приближенных СЛАУ рассматривать в следующей постановке: Задача PQ(/I,6): Пусть существует точная совместная конечномерная СЛАУ где Ао Є K.mxn, бо Є Ж171, бо ф 0, соотношения между размерами AQ и ее рангом не оговариваются, хо Є Шп — решение системы (1.12) с минимальной евклидовой нормой (нормальное решение). Численные значения Ао и &о неизвестны, а вместо них заданы приближенные матрица А Є ЖтХ7г и вектор Ь Є Ш"1, Ъ т 0, такие, что выполняются условия где д 0 и 5 0 — известные параметры. Полнота ранга матрицы А и совместность системы Ах = 6 в общем случае не предполагаются. Требуется найти Ах є Rmxn, bi Є Шт, хі Є W1 такие, что \\А - Аг\\ \х, 6 — 6іП 6, АіХі = 6ь #і — min. Возможны и другие постановки задачи отыскания устойчивого решения приближенной СЛАУ (см., например, [129]), но в настоящей работе они не рассматриваются. Как было показано в работах [96, 97], вектор х± является устойчивым приближением к вектору х о, т.е. lim х\ = XQ. Традиционно [73, 99, 100] задачу Po([i,5) принято сводить к задаче безусловной минимизации сглаживающего функционала Задача Р2: Фа(х, А, Ь) — min. X Будем обозначать через za решение задачи Р2. Известно (см., например, [15]), что при любом а 0 существует единственный вектор za.
Кроме того, при соответствующем а 0 вектор za является устойчивым приближением к вектору хо, то есть служит решением задачи Р0 при [л,6- 0 [73, 99, 100]. Пусть ха — в общем случае нормальное решение системы где 1п — единичная матрица порядка п при любом фиксированном а Є R. Тогда ха+ — решение системы (1.16) при а 0; а;а_ — решение системы (1.16) при а 0. Здесь также необходимо сделать некоторые замечания относительно параметра о;, системы (1.16) и вектора ха: Замечание 1. Если а = О, то вектор ха+ найдется в виде ха+ = х + Ах, где Ах — произвольный вектор, ортогональный строкам матрицы А. Если при этом rank Л = п, то Ах = 0, и решение системы (1.16) ха+ = х единственно. В противном случае система (1.16) имеет бесконечное множество решений, среди которых решение ха+ = х является единственным решением с минимальной евклидовой нормой [15]. Замечание 2. Для любого а 0 вектор za совпадает с ха+ и является единственным решением системы (1.16) [15]. При а О система (1.16) может оказаться несовместной (ха- может не существовать). Замечание 3. х+ = для любого вектора х 0. В справедливости указанного соотношения несложно убедиться с помощью уравнений Пенроуза (1.7), рассматривая х как матрицу, состоящую из одного столбца, а х+ — как матрицу, состоящую из одной строки. Следующая теорема, являющаяся обобщением результатов работы [95] на случай неодинаковой точности задания левой и правой части исследуемой приближенной системы, показывает, что вектор ха дает устойчивое приближение к нормальному решению совместной системы (1.12). вимых в виде U — Ах, где х = х\ хп — произвольный элемент пространства Еп. Очевидно, что подмножество {UA} представляет собой линейное пространство и поэтому является подпространством Ет. Обозначим через {VА] ортогональное дополнение {UA} (ДО всего Ет) и разложим Ет в прямую сумму подпространств {UA} И {УД}. Пусть ЪА обозначает проекцию столбца Ъ на подпространство {UA}, так что Ъ = ЪА + (Ь — ЬА), где (Ь — ЪА) — элемент {Уд}. Тогда, поскольку для любого элемента х пространства Еп столбец Ах является элементом {UА}, получим следующее разложение: в котором элементы (Ах — ЬА) И (ЬА — Ь) ортогональны друг другу и принадлежат соответственно {UА} И {УД}.
Постановки задач матричной коррекции приближенных несовместных СЛАУ
Рассмотрим еще один, помимо регуляризации, интересный в контексте данного исследования класс задач: задачи минимальной матричной коррекции, возникающие при исследовании приближенных несовместных СЛАУ (см., например, [11, 35, 111, 126]). Краткая история исследования задач матричной коррекции приведена во введении, здесь же введем постановки наиболее распространенных задач и сделаем общие замечания о свойствах решений этих задач. Как уже было отмечено, на практике задачи минимальной матричной коррекции несовместных СЛАУ, как правило, выступают в роли обобщений метода наименьших квадратов. В настоящее время их не принято рассматривать в качестве инструментов для получения устойчивых решений приближенных СЛАУ. В определенных случаях, простейшим из которых является неполнота столбцевого ранга матрицы А, задачи матричной коррекции не имеют решения [11, 35]. Однако, при обработке экспериментальных данных с низким уровнем погрешностей в исследуемых переопределенных системах с полноранговыми матрицами, скорректированные системы оказываются близки к точным, а их нормальные решения — к вектору хо- Существенной особенностью задач матричной коррекции является тот факт, что их решения могут быть найдены из системы (1.16) при а 0 [35].
Подробному исследованию указанных задач посвящена работа [53], здесь же ограничимся лишь краткими, необходимыми для дальнейшего изложения, сведениями. Рассмотрим систему линейных алгебраических уравнений (1.1). Введя в рассмотрение матрицу Н Є Mm n и вектор h Є Ш"1 и используя запись для обозначения евклидовой матричной нормы, можно рассмотреть задачу которую назовем задачей коррекции расширенной матрицы коэффициентов системы (1.1) по минимуму евклидовой нормы. При этом Ztotai{Aib) — чис- ленное значение нижней грани евклидовой нормы матрицы даче Ztotal(A,b). Если нижняя грань целевой функции в задаче Ztotai(A,b) достигается, будем говорить, что задача Ztotai{A b) имеет решение, которое Как уже было отмечено выше, задача Ztotai{A, b) мо- Достаточно очевидно, что задача матричной коррекции несовместной системы (1.1) в постановке (1.30) не может быть универсальным ответом для всего многообразия проблем, возникающих в практических приложениях и связанных с несовместностью систем линейных алгебраических уравнений. Поэтому возможны различные модификации задачи Ztotai{A,b) [53]. Отметим, что, для решения подобных модификаций могут быть использованы сходные вычислительные алгоритмы. Одно из направлений модификации задачи Ztotai{A, b) — фиксированные (не подверженные коррекции) строки и столбцы в расширенной матрице системы (1.1). Особую роль в этом классе задач играет задача с фиксированной правой частью: Норму решения такой задачи будем обозначать Zfix (A,b). Здесь приведем без доказательств теоремы об условиях существования решений рассматриваемых задач матричной коррекции. Подробное обоснование указанных результатов приведено в работе [53]. Теорема 1.3.1 (О существовании и виде решения задачи Ztotai(A, &)). Пусть дана система линейных алгебраических уравнений вида (1.1)—(1.2). Тогда для оптимального значения целевой функции в задаче Ztotai(A, b) справедлива формула Данный раздел посвящен оптимальной матричной коррекции несовместных линейных систем специального вида с матрицами (расширенными матрицами) Теплица или Гапкеля.
Указанные линейные системы достаточно распространены. Они возникают, например, при анализе и параметрической идентификации линейных динамических систем с одним входом и одним выходом, когда соответствующие непрерывные входные и выходные сигналы заменяются дискретными наборами значений, а соответствующие системы линейных дифференциальных уравнений первого порядка, описывающие поведение исследуемых систем, превращаются в системы линейных разностных уравнений специального вида [77, 79, 81, 101]. Пример практической задачи, приводящей с подобным системам, описывается в третьем разделе пятой главы. Несмотря на свою распространенность, матрицы Теплица определяются в литературе неоднозначно — с точностью до перестановки строк. В настоящей работе матрицей Теплица будем называть прямоугольную матрицу Т{у) Є к.(ЛГ-7г+1)хгг) параметризованную вектором у Є M.N, и имеющую вид
Матричная коррекция несовместных СЛАУ со специальной структурой по минимуму взвешенной евклидовой нормы
Предлагаемые вычислительные алгоритмы предназначены для нахождения устойчивого решения приближенных систем линейных алгебраических уравнений в постановке А. Н. Тихонова. Исходная задача Ро заменяется на задачу Рі (/І, 5). Для работы алгоритмам необходима априорная информация в виде данных о погрешностях матрицы коэффициентов и правой части систем, задаваемых параметрами /л 0, 6 0. Сначала рассмотрим вспомогательную задачу. Приведенные ниже теоремы 3.2.1, 3.2.2 и 3.2.3 описывают способ построения модельных возмущенных и невозмущенных СЛАУ с известными решениями задач Ро(/х, 0) и РІ(ДІ, 0). Докажем ряд лемм. Лемма 3.2.1. Вектор х ф 0 является единственным решением задачи РІ(/І, 0) с параметрами &о = Ахц + aA+Txfl + Ab, АТАЬ = 0, ЦаА4"7 + ДЬ=/ф;Д а 0. Доказательство. Для задачи Pi (/л, 0) запишем условия Лагранжа (см. доказательство леммы 2.2.4) и убедимся, что при подстановке в них жм, А, &о, а, соответствующих условиям леммы, они обращаются в тождества. Следовательно, в силу леммы 2.2.9, вектор х является решением задачи Pi(/x, 0), причем единственным. Лемма 3.2.2. Вектор х ф 0 является единственным решением задачи Рі(д, 0) с параметрами &о = Ахц + аА+ТХц + АЬ, АГД6 = 0, ЦаЛ4"7 4-АЬ\\ = НЫ1, а 0, Ьо - Ах\\ fi\\x\\, rank А = п. Доказательство. Убеждаемся в выполнении условий Лагранжа для задачи РІ(/І, 0) при подстановке в них х А, &о, а, соответствующих условиями лем мы. Учитываем, что выполняется условие &о — Ах\\ ц\\х\\ и матрица А имеет полный столбцевой ранг. В силу вышеперечисленного и с учетом лемм 2.2.5, 2.2.9 и 2.2.10 вектор Хц является решением задачи Рі (/і, 0), причем един ственным. D Лемма 3.2.3. Вектор Хц = х + Ах, где х Ф 0 А+А = х, Ах — произвольный вектор, такой что ААх = 0, &о — Ах\\ = /л\\х + Ах\\, принадлежит множеству решений задачи Рі(/л,0) с параметрами &о = Ах + АЬ, АТАЬ = 0, ЦД&Ц = //.тД 60 Ах\\ fjt\\x\\, rank А п.
Доказательство. Убеждаемся в выполнении условий Лагранжа для задачи РІ(/І, 0) при подстановке в них х А, &о, соответствующих условиями леммы. Учитывая, что выполняется условие бо — Ах\\ р\\х\\ и матрица А имеет неполный столбцевой ранг, по аналогии с соответствующими выкладками, приведенными в доказательстве теоремы 2.1.1, убеждаемся, что других ре шений кроме Хц задача Р\ (/І, 0) не имеет. Лемма 3.2.4. Матрица AQ Є Rmxn и векторы XQ Є W1, XQ Ф 0, бо Є №т, где Ао = А + (б0 - Ах0)х + Z, гапкЛ0 = п, Z Є Rmxn ( й;Л2 + ll ll2 = Л ZXQ = 0 J , могут считаться элементами точной СЛАУ, отвечающей условиям задачи Ро([л,0), а матрица А и вектор bo могут считаться элементами соответствующей приблиоюенной СЛАУ. Доказательство. 1. Покажем, что вектор XQ является нормальным решением СЛАУ AQX = бо- По условию леммы AQ = А + (бо — AXQ)XQ + Z, Zxo = 0. Умножим справа обе части первого равенства на XQ: AQXQ = AXQ + (бо — AXQ)XQXQ + Zxo Ф AQXQ = bo. Таким образом, система AQX = бо совместна, а в силу условия rank AQ = п вектор XQ является ее единственным решением, которое можно считать нормальным. 2. Оценим величину \\AQ — А\\. Используя выражение для AQ, получим: \\А0 - А\\ = \\(Ь0 - Ах0)х + Z\\, \\Ao-Af = \\(b0-Ax0)xt+Z\\2 = \\(bo-Ax0)xtf+\\Z\f = J! jliM!-bZ2. Учтем, что по условию леммы выполняется равенство Таким образом, система AQX = bo совместна, XQ является ее решением и выполняется условие Ло — А\\ — \х. П Теперь сформулируем и докажем теоремы, позволяющие конструировать модельные приближенные и точные системы с известными решениями.
Теорема 3.2.1. Пусть А Є Rmxn — произвольная матрица; х ф О {А+Ахц = Хц; Тогда система AQX — бо совместна, XQ — ее нормальное решение, Хц — единственное решение задачи РІ(/І, 0); СЛЛУ Ло& = Ьо и Ах = 6о лвлл- ются соответственно точной и приближенной системами, отвечающими условиям задачи Ро(м, 0). Доказательство. Так как выполняются условия Ло = Л + (&о — AXQ)X.Q 4- Z, rank Л = п, lboj ola + II Z\\2 = /і2 и Za,-0 = 0, то, согласно лемме 3.2.4, СЛАУ AQX = бо и Ах = Ьо являются соответственно точной и приближенной систе мами, отвечающими условиям задачи PQ(/I,0). Кроме того, так как выполня ются условия Ьо = Лям 4- aA+TXfj. + Ab, \\аА+ТХц + А6 = / Цж Ц, АТАЬ = 0 и а 0, то из леммы 3.2.1 следует, что вектор Хц является единственным решением соответствующей задачи Р\(/л, 0). Тогда система AQX — bo совместна, xo — ее нормальное решение, x — единственное решение задачи Р\(ц, 0), СЛАУ Аох — Ьо и Ах = &о явля ются соответственно точной и приближенной системами, отвечающими условиям задачи Po(/J , 0). Доказательство. Из леммы 3.2.4 следует, что СЛАУ Аох = Ьо и Ах = Ьо являются соответственно точной и приближенной системами, отвечающими условиям задачи Ро(м, 0)- Согласно условию теоремы, выполняется неравенство А6 р\\хц - а А+А+ТХц\\. Учтем, что 60 = Лссм - \а\А+тх + Ab. Тогда х = A+bo = хм — \а\ А+А+тх1Х. Следовательно, выполняется неравенство &о — - 4# д- Кроме того, согласно условию теоремы, выполняются равенства &о = Ах -\-аА+тх +АЬ, АТАЪ = 0, ЦаЛ+ + АбЦ = джм. Тогда из леммы 3.2.2 следует, что вектор Хц является единственным решением соответствующей задачи Рі(/х, 0).
Восстановление линейных зависимостей, формализованных интегральными уравнениями Фредгольма первого рода
В третьей главе приводятся алгоритмы, разработанные для решения задач матричной коррекции и задачи математического программирования, к которой сводится задача поиска решения приближенной СЛАУ в постановке А. Н. Тихонова (РМНК). Алгоритмы матричной коррекции основаны сведении исходной задачи к задаче безусловной минимизации специальным образом сконструирован- ной функции (для решения которой можно использовать методы Ньютона и Марквардта) и предназначены для решения двух классов задач: задачи со взвешенными с произвольными положительными весами элементами расширенной матрицы коррекции для систем произвольного вида , и задачи с матрицей коэффициентов, имеющей специальную структуру (представляющей собой, например, матрицу Теплица или Ганкеля), матрица коррекции которой также имеет специальную структуру, но как и для первого алгоритма допускает взвешивание с произвольными положительными весами. В третьей главе приводятся и обосновываются процедуры, позволяющие строить системы тихоновского типа с заданными свойствами для частного случая, когда правая часть системы свободна от погрешности. Указанные процедуры могут быть полезны для построения модельных примеров, а обосновывающие их теоремы могут быть использованы для теоретического исследования указанного частного случая. Алгоритмы, предназначенные для нахождения устойчивого решения приближенной системы линейных алгебраических уравнений, реализуют подход А. Н. Тихонова к решению задачи регуляризации, заключающийся в переходе к специальным образом построенной задаче математического программирования (о чем подробно говорилось в первой главе). Указанные алгоритмы могут быть применены и к модифицированной задаче с свободными от погрешности столбцами матрицы коэффициентов. Для всех алгоритмов приведены численные примеры, иллюстрирующие их работу. На все представленные в третьей главе алгоритмы получены свидетельства об отраслевой регистрации разработки ОФАП или свидетельства о регистрации электронного ресурса ОФЭРНиО. Априорная оценка погрешности решения приближенной СЛАУ является важной практической задачей.
Подобные оценки погрешностей для классического метода наименьших квадратов хорошо известны [15, 78]. Однако, до настоящего момента, вопрос о нахождении априорных оценок погрешности для методов регуляризации и матричной коррекции оставался открытым. Задача настоящего раздела: определить условия, которым должны отвечать параметры задачи Рі (/І, 6), чтобы погрешность найденного решения была максимальной: є = жо - х\\\ — \\х0 - x W - max. Ввиду сложности поставленной задачи, ограничимся случаем, когда правая часть системы свободна от погрешности, т.е. 6 = 0. Ниже будем исследовать свойства решений задачи P\(fi, 0). Решение данной задачи будем обозначать Хц. С практической точки зрения наиболее интересен случай, когда погрешность системы меньше минимального сингулярного числа матрицы А, т.е. М tfmin- Поэтому рассмотрим именно этот случай. Следующие теоремы дают априорные нижние оценки максимальной относительной погрешности решения задачи Рі(/л,0) для различных случаев. Теорема 4.1.1. При решении задачи РІ(/І, 0) для случая 6о — Лт ц\\х\\, rank Л = п, (л amin, максимальное значение относительной погрешности 4 (где Ах = XQ — х ) будет не меньше, чем величина: Доказательство.
Покажем, что существуют удовлетворяющие условиям теоремы точная и соответствующая ей приближенная СЛАУ, для которых оценка (4.1) достигается. Пусть А Є Штхп, rank А = п (следовательно, crmin 0), тм Ф 0 — собственный вектор матрицы АТА, соответствующий ее минимальному собственному значению Хт[П(АтА) = cr in, 0 /х crmin, параметры точной системы рассчитываются следующим образом: 1) Убедимся в существовании объектов, задаваемых приведенными выше формулами. Скаляр а и векторы то, % и &о очевидно, существуют, причем из условия Хц ф 0 следует условие .то ф 0, достаточное для существования матрицы AQ. Покажем, что Лот = 6о и Ах = &о — действительно точная и соответствующая ей приближенная СЛАУ, отвечающие условиям задачи Ро(м, 0), причем то — нормальное решение СЛАУ Лот = bo. Для этого убедимся в выполнении условий теоремы 3.2.1. Поскольку rank Л = п, справедливо условие А+Ахц = Хц [15, 78]. Очевидно, что а 0. В то же время, учитывая связь псевдообратной матрицы с ее сингулярным разложением [78, 102], несложно показать, что а = ІГ +ГД И Теперь легко проверить, что bo отвечает условиям теоремы 3.2.1 при Д6 = 0, причем действительно АТАЬ = 0, \\аА+тх, + Щ = \\х,\\. Покажем, что Ло отвечает условиям теоремы 3.2.1 при Z = 0. Очевидно, что ZXQ = 0. Покажем, что Убедимся, что rank AQ = п. Из приведенных выше выкладок следует, что AQ — А\\ = /J, (см. доказательство леммы 3.2.4). В то же время, по условиям теоремы, rank Л = п, /J, Jmm- Совокупность указанных условий позволяет утверждать, что rank Д) = п [102].
Таким образом, все условия теоремы, накладываемые на векторы а;о, х , Ьо и матрицы A, AQ, выполнены, указанные объекты существуют, в силу чего СЛАУ AQX = бо и Ах = Ьо действительно являются соответственно точной и приближенной системами, отвечающими условиям задачи Ро(/ 0)- 2) Покажем, что и "у = 2/і, . Действительно,
