Расширение возможностей компьютерно-алгебраической системы Maple для решения линейных задач метода наименьших квадратов

• Автор: Матин Фар Машалла Набиолла
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Москва
• Количество страниц: 107 с. : ил.

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

1.1. Рациональные алгоритмы

1.1.1. Скелетное разложение

1.1.2. Метод Эрмита

1.1.3. Метод Гревилля

1.2. Вычисление псевдообратной матрицы в системе Maple

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

Глава 2. Задачи наименьших квадратов с линейными ограничениями

2.1. Ограничения в виде линейных уравнений

2.1.1. Постановка задачи HKY

2.1.2. Рациональные алгоритмы

2.1.3. Тестовые задачи
2.1.4. Результаты численных экспериментов
2.2. Ограничения в виде линейных неравенств
2.2.1. Постановка задачи НКН
2.2.2. Алгоритм NNLS
2.2.3. Тестовые задачи
2.2.4. Результаты численных экстриментов
2.2.5. Преобразование задачи НКН в задачу LDP
2.2.6. От задачи LDP к задаче NNLS
2.2.7. Результаты численных экспериментов
Глава 3. Пересчёт псевдообратных матриц и нормальных псевдорешений при одноранговых модификациях задачи
3.1. Безусловная ЗНК
3.1.1. Постановка задачи
3.1.2. Формулы пересчёта
3.1.3. Результаты численных экспериментов
3.2. Задача НКУ
3.2.1. Постановка задачи
3.2.2. Модифицированные формулы Гревилля
3.2.3. Детали реализации и численные эксперименты
Приложение
П1.1. Обращение вырожденной матрицы по Дрейзину
П1.1.1. Постановка задачи
П1.1.2. Алгоритм Кэмпбелла—Мейера
П1.1.3. Обращение по Дрейзину посредством
псевдообращения
П1.1.4. Метод последовательной редукции
П1.1.5. Тестовые задачи
П1.1.6. Результаты численных экспериментов
П1.2. Проверка матричного свойства К—коположительности
Приложение 2. Таблицы
Заключение
Литература
Напомним постановку линейной задачи наименьших квадратов (ЗНК): для заданных матрицы А размера (тхп) и т-мерного вектора Ь найти вектор х размерности п, минимизирующий величину
/(ж) = \Ах - ь\2. (0.1)
Всякий такой вектор х называется решением системы
Ах = Ъ (0.2)
в смысле наименьших квадратов или, более коротко, псевдорешением этой системы. Если система (0.2) совместна, то ее псевдорешения совпадают с решениями в обычном смысле.
Пусть г — ранг матрицы А. При г < п множество псевдорешений представляет собой линейное многообразие размерности п. Иногда наличие бесконечного множества псевдорешений обременительно, и тогда в этом множестве выбирают наиболее желательный в том или ином смысле вектор х.
В методе наименьших квадратов наиболее желательный вектор — это вектор х с наименьшей 2-нормой. Он называется нормальным псевдорешением системы (0.2) и существует для всякой системы линейных уравнений. Если система однозначно разрешима, то нормальное псевдорешение этой системы совпадает с ее единственным решением в обычном смысле.
В библиотеках и пакетах программ по численному анализу для решения системы (0.2) в смысле наименьших квадратов применяется следующий стандартный подход:
1. Для матрицы А находим то или иное ортогональное (или унитарное) разложение, т.е. представление типа
А = НИК*, (0.3)

Случай 3: и — 0, /3 ф 0. Положим
Р1 = -(—V + к), дг = -{Ш-к*А+ + />*), (3.11)
^ = М21М12 + Н2. (3-12)
Тогда
(А + «Г)+ = А+ + ь{к*А+) - £-р1д{. (3.13)
Р <*
Случай 4- и ф 0, г = О, (3 — 0. Имеем
(А + сс1*)+ = А+- (Л+(/Т)+)Л* - ки+. (3.14)
Случай 5: V = 0, 0 ф 0. Положим
Р2 = ~{^-^-А+к + к), д2 = и* +
а2 = И2|Н|2 + |/3|2.
Тогда
(.А + с(Г)+ = А+ + •=(А+К)и* - —Р2Я2- (3.15)
Р °2
Случай 6: и = О, V = О, {3 — 0. Полагая
Г = к+А+,
имеем
(А + ссГ)+ = Л+ - Ы* - [А+(/Т)+ - {1*(Н*)+)кк*. (3.16)
Как видно из формул (3.9), (3.10), (3.13) и (3.14)—(3.16), в общем случае,
" новая "псевдообратная матрица получается из старой добавлением двух (а не одной, как в (3.5)) матриц ранга 1. Однако формула (3.5) содержится как частный случай в (3.13) и (3.15). Действительно, для невырожденной матрицы А равны нулю оба вектора и и и. Рассматривая, для определенности, формулы (3.11) и (3.12), получаем
Р = -к, ях = —/г*, ах =| /3 |2