Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
ГЛАВА 19
ДРУГИЕ МЕТОДЫ ДЛЯ ЗАДАЧИ НАИМЕНЬШИХ КВАДРАТОВ
В качестве вычислительного аппарата для решения задач теории наименьших квадратов мы выделили ортогональные преобразования Хаусхолдера. При таком подходе численная устойчивость, характерная для ортогональных преобразований (см. гл. 15-17), сочетается с гибкостью, позволяющей легко приспосабливаться к специальным ситуациям, например последовательному накапливанию данных (гл. 27). Мы предложили также использовать сингулярное разложение как средство достигнуть лучшего понимания плохо обусловленных задач (гл. 18, 25).
В этой главе будут описаны некоторые другие численные методы для задачи наименьших квадратов. В табл. 19.1 приведены старшие члены формул для числа операций при решении задачи Ат^пх = h, т >п, различными методами.
Мы обсудим, в частности, методы, основанные на математической эквивалентности задачи наименьших квадратов Ах s J н системы линейных уравнений {АТА)х = (АТЬ). Эту систему называют системой нормальных уравнений исходной задачи. Методы, предполагающие формирование и решение нормальных уравнений, требуют обычно примерно вдвое меньше операций, чем алгоритм Хаусхолдера. Однако, чтобы получить этими методами решения того же качества, что в алгоритме Хаусхолдера при относительной точности г/, здесь требуется работать с точностью tj2 .
В большинстве специальных ситуаций, например в случае последовательного накапливания данных (см. гл. 27), можно организовать оба метода -алгоритм нормальных уравнений и алгоритм Хаусхолдера - так, что потребуется примерно одно и то же число единиц хранения. Заметим, однако, что если в качестве единицы хранения принимается машинное слово одинаковой для обоих методов длины, то алгоритм Хаусхолдера сможет обрабатывать более широкий класс задач, чем алгоритм нормальных уравнений.
Второй метод, обсуждаемый в данной главе, - это модифицированная ортогонализация Грама-Шмидта (MGS)*). Численные свойства этого метода очень сходны со свойствами алгоритма Хаусхолдера. Факторизо-ванное представление матрицы Q, используемое в алгоритме Хаусхолдера, требует приблизительно на п2/2 меньше ячеек памяти, чем явное представление, используемое в MGS. Как показывает наш опыт, именно по этой причине алгоритм Хаусхолдера легче, чем MGS, адаптируется к различным специальным приложениям.4'
*) MGS - сокращение английского гпиттщиия Modified Gram - SckmkK Ortho-
gonalization. (Примеч. пер.)
92
Таблица 19.1
Количество операций для различных численных методов ' i решения задачи наименьших квадратов
Метод
Приведение к треугольному виду методом
Хаусхолдера Сингулярное разложение:
прямое применение к А приведение А к треугольной матрице R методом Хаусхолдера в сингулярное разложение R Формирование нормальных уравнений Решение нормальных уравнений методом
Холесского '
Решение нормальных уравнений методом '' '
Гаусса-Жордана (для пошаговой регрессии) Спектральный анализ нормальных уравнений Метод Грама-Шмидта (классический или модифицированный)
Асимптотическое число операций •)
тп1 -п'/г 2тп' + а(п)
тп1 + 5л'/3 тп2/2
**)
лэ/6
-я
о а я
*) Под операцией понимается пара "умножить (или разделить) и сложить". •*)Член а(л) учитывает итерационную фазу в вычислении сингулярных чисел или собственных значений. Если считать, что для сходимости QR -алгоритма нужно примерно 2л шагов, то о(п) равно приблизительно 4пэ.
В качестве конкретного примера этой особенности компактного хранения заметим, что с помощью преобразований Хаусхолдера можно вычислить решение х задачи Ах a? b и вектор невязки г = b - Ах, используя т(п + 1) + 2л + т ячеек памяти. Как в алгоритме нормальных уравнений, так и в алгоритме MGS требуются дополнительные п(п + 1)/2 ячеек. При этом, как отмечалось выше, оценка запросов к памяти должна принимать во внимание, что метод нормальных уравнений требует т?2 -разрядности для обработки того же класса задач, который обрабатывается алгоритмами Хаусхолдера и MGS в арифметике с относительной точностью ц.
§ 1. Нормальные уравнения и разложение Холесского
В книгах, ограничивающихся кратким раэбором задачи наименьших квадратов, чаще всего рекомендуют именно метод нормальных уравнений. Обе части исходной задачи Ат^„х a b умножают слева на матрицу АТ. В результате получается система
Л|Хя*=<*яхь ..¦» (19-1)
называемая системой нормальных уравнений для тШШШЩШ. Здесь
Р = АТА, L / , '.„„,, (19-2)
d = ATb. ~" (V (19-3>
93
Уравнение (19.1) можно было бы вывести непосредственно из условия, что для искомого решения вектор невязкн Ь - Ах должен быть ортогонален к пространству столбцов матрицы А. Это условие записывается уравнением
Атф-Ах) = 0, (19.4)
которое, как видно из (19.2) и (19.3), эквивалентно уравнению (19.1).
Хотя Р имеет тот же ранг, что и А, и, следовательно, может быть вырождена, уравнение (19.1) всегда совместно. Чтобы убедиться в этом, заметим, что, согласно (19.3), вектор d принадлежит пространству строк А. Но, как показывает (19.2), пространство строке совпадаете пространством столбцов Р.
