Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
В [51 *] указаны численно устойчивые и эффективные алгоритмы перестройки решения задачи (48) при удалении столбца из матрицы или, наоборот, введении нового столбца. В [42*] анализируются статистические свойства формулировки (48) и устанавливается связь этого подхода с предложенным Рао методом обобщенного обращения фундаментальной матрицы
С А Ат О
Обзор методов численного решения задачи (48) дан в [36].
Упомянутая в конце § 4 задача о выборе X из условия, чтобы норма решения либо норма невязки имела заранее предписанное значение, в более общей постановке рассматривается в [31]: для заданных m X «-матрицы /1, р X п-матрицы С, m-вектора Ь, р-вектора d и положительного числа а найти вектор х, минимизирующий \\Ах - Ь\\ при условии ||Сх - d\\= а. Будем называть эту задачу задачей наименьших квадратов с квадратичным ограничением (сокращенно ЗНККО). Предполагается, что множество {х | || Сх - d || = а} непусто и
а > min || Сх - d \\.
Это условие обеспечивает разрешимость ЗНККО. Чтобы число решений было конечным, потребуем, чтобы ker А Пкег С = (0).
Метод Лагранжа, примененный к ЗНККО, дает следующие нормальные уравнения:
(АтА+\СтС)х = ATb + \CTd, ||Сх-сМ|2 = о2.
Среди решений (X, х(Х)) системы нормальных уравнений решение ЗНККО дает пара (X 0, х(Х0))с наибольшим значением X. Если, в частности, имеется пара с положительным X, то такая пара будет ровно одна, и соответствующий единственный вектор х(Х) решает ЗНККО. Если же все X отрицательны, то решение ЗНККО может оказаться неединственным. Так
будет, если X 0 - собственное значение пучка А ТА + ХСГС.
Интересно отметить, что исследование системы нормальных уравнений проводится в [31] посредством обобщенного сингулярного разложения пары (4, С).
Частными случаями ЗНККО являются задачи:
минимизировать \\Ах — Ь\\ (55)
21*
при условии || х || в а
(эта задача рассматривалась еще в [30]) и
минимизировать || х || (56)
при условии || Сх~ d\\ = а.
Последняя интерпретируется геометрически как определение точки гиперэллипсоида, ближайшей к началу координат. К ЗНККО тесно примыкает задача
минимизировать
¦ \\Ах-Ъ\\
при условии || Сх - d || < а. (57)
В самом деле, либо \\Сх — d\\< а для некоторого псевдорешения х^зада-
чи Ах s Ь, и в этом случае одним из решений (57) будет х, либо минимум достигается на границе, и мы приходим к соответствующей ЗНККО.
В [28] рассмотрены задачи, получающиеся из (55) либо (56) заменой ограничения-уравнения ограничением-неравенством и заменой евклидовой длины в целевой функции либо в левой части ограничения на эллипсоидальную полунорму.
Некоторый метод выбора гребневого параметра X в задаче (25,31) предложен в § 12.1 книги [34]. Там же на стр. 418 описан следующий алгоритм выбора подмножества (см. § 5):
1. Вычисляется сингулярное разложение матрицы А :
UTAV = diag(o,.....о„).
Матрица V должна быть сохранена.
2. Определяется значение к псевдоранга, после чего f раяЯияняНШ
в соответствии с к:
V =
Ум У12
У22
к л - *
3. К матрице [И,г, : V\rl ] применяется алгоритм* HFTI из гл. 14:
Q[ Ум ¦ УгТ1 \Р = [Д.. ];
здесь Р - матрица, описывающая произведенные перестановки столбцов.
4. Положим АР = [Bi : В2 ]. Решается задача наименьших квадратов
* я - *
Bxz as Ь. (58)
Таким образом, мощность выбираемого подмножества определяется на этапе 2, а само это подмножество столбцов указывает матрица Р. На этапе 4 решается редуцированная задача (58).
15.4. Лоусон
»7
Насколько велика невязка задачи (58) по сравнению с невязкой исходной задачи Ах as Ы Если z, х — решения обеих задач, гz, гх — отвечающие им невязки, то
H'w*ll < WRl\ 1111*11- / ; (»)
Сингулярные числа о,, о„ предполагаются упорядоченными по убыванию. Понятно, что \\rz || > \\гх ||.
Оценка (59) объясняет, почему для выбора подмножества был применен алгоритм HFTI: он позволяет определить в достаточной степени невырожденную подматрицу порядка к в первых к столбцах V, т.е. по возможности уменьшить значение \\R~t\ II • Есть и другая причина: необходимость обеспечить линейную независимость столбцов В\. Справедливы неравенства
°к
——7Т ** °min(?i) < ок. - , > . ,к
'"Ml 11 • - .'( • .rii..;; ¦ .. ,;!. , .,
Чем меньше тем большим ^IjpMii* ilMlltoil wmwmMintn
обладают столбцы Д1.
СПИСОК ЛИТЕРАТУРЫ
1. А л б е р т А. Регрессия, псевдоинверсия и рекуррентное оценивание. - М.: Наука, 1977.
2. Гордонова В.И- Оценки ошибок округления при решении системы условных уравнений. - ЖВМ и МФ, 1969, 9, № 4, с. 775-782.
3. Г э й л Д. Теория линейных экономических моделей. - М.: ИЛ, 1963.
4. Д р е й п е р Н„ С м и т Г. Прикладной регрессионный анализ. - М.: Статистика, 1973.
5. О р тег а Дж., РейнболдтВ. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. - М.: Мир, 1975.
6. Тихонов А.Н., Г л а с к о В.Б. О приближенном решении интегральных уравнений Фредгольма 1 рода. - ЖВМ и МФ, 1964,4, № 3, с. 564-574-.
7.Уилкинсон Дж. Алгебраическая проблема собственных значений. - М.: Наука, 1970.
8. Уилкинсан Дж., р а й н ш К. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра. - М.: Машиностроение, 1976.
