Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
19.38 (142]. Предположим, что rank/4mx п~ " и m > п. Посредством гауссова исключения (с частичным выбором главного элемента) можно получить разложение А = PLR, где ?тх п - нижняя треугольная матрица с единичными диагональными элементами, Rn х п - верхняя треугольная, а Р - матрица перестановки, учитывающая перемещения строк.
a) Подсчитать количество операций при вычислении этого разложения.
b) Задачу НК можно решить, применяя метод Холесского к системе L Ly = = LTP Tb, а затем определяя х из системы Rx -у. Подсчитать количество операций при
формировании L L и при вычислении факторизации Холесского этой матрицы.
c) Показать, что общее количество операций в этом методе такое же, что и в методе Хаусхолдера (см. табл. 19.1). (Достаточно определить лишь коэффициенты при m ла и л3 в формулах для числа операций.)
19 39 Пусть A- m X л-матрица ранга п, и пусть А = QR - разложение матрицы А, полученное применением к ней (в точной арифметике) модифицированного алгоритма Г рама-Шмидта. Предположим, что Q и R нормированы так, чтобы столбцы Q имели единичную евклидову длину. Пусть
'с ]
>m X п J
есть матрица, полученная (в точной арифметике) применением к (m + л) X л-матрице 0„ х л 1
.Атх пJ
алгоритма HFT (см. 11.4). Показать, что В совпадает с R с точностью до знаков строк, а С совпадает с Qc точностью до знаков столбцов *).
11
102
*) Нужно учесть только, что столбцы С не нормированы. (Примеч. пер.)
19.40 (метод Холесского без квадратных корней). Вместо (19.S) рассмотрим разложение WTDW = Р, где W - верхняя треугольная с единичными диагональными элементами матрица, a D - диагональная матрица. Вывести формулы, аналогичные (19.12)- (19.14), для вычисления диагональных элементов D и наддиагональных элементов W, Показать, что, используя такое разложение матрицы Р из (19.S), задачу (19.1) можно решить без вычисления квадратных корней.
ГЛАВА 20
ЛИНЕЙНЫЕ ЗАДАЧИ НАИМЕНЬШИХ КВАДРАТОВ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ-РАВЕНСТВАМИ: РЕШЕНИЕ С ПОМОЩЬЮ БАЗИСА НУЛЬ-ПРОСТРАНСТВА
В этой главе мы начинаем изучение задач наименьших квадратов, в которых переменные должны удовлетворять некоторым ограничениям в форме линейных уравнений или неравенств. Такие задачи возникают во многих приложениях. Например, при вычерчивании кривой по точкам ограничения-равенства могут возникать из необходимости интерполировать часть данных или из требования непрерывности кривой, а может быть, и ее производных в некоторых точках. Ограничения-неравенства возникают из таких условий, как положительность, монотонность и выпуклость.
Мы будем кратко обозначать линейную задачу наименьших квадратов с линейными ограничениями-уравнениями как задачу НКУ. Задачу с линейными ограничениями-н-равенствами (в которой могут быть и ограничения-уравнения) будем называть задачей НКН. В этой и двух последующих главах изложены три различных алгоритма решения задачи НКУ, Задача НКН будет рассмотрена в гл. 23.
Чтобы зафиксировать обозначения, дадим развернутую формулировку задачи НКУ.
Задача НКУ 20.1 (наименьшие квадраты с ограничениями-уравнениями). Пусть даны nti X п-матрица С ранга fc,, т^-вектор d, m2 Хп-мат-рицаЕи тг-вектор f. Среди всех п-векторов худовлетворяющих системе
Сх = d, (20.2)
найти вектор, который минимизирует величину
(20.3)
Очевидно, что задача НКУ имеет решение тогда и только тогда, когда система (20.2) совместна. Мы будем предполагать совместность (20.2) на протяжении гл. 20—23. В обычных для практики вариантах этой задачи выполняются условия п > m i = ki, обеспечивающие совместность системы (20.2) и существование более чем одного решения.
В дальнейшем будет показано, что если решение задачи НКУ существует, то оно единственно тогда и только тогда, когда расширенная мат-
рица j ^ I имеет ранг л. В случае неединственности имеется единственное решение минимальной длины. '
Ясно, что задачу НКУ можно обобщить на тот случай, когда система (20.2) несовместна и интерпретируется в смысле наименьших квадратов. Нам не встречались практические ситуации такого рода; однако наше обсуждение задачи НКУ переносится с точностью до небольших модификаций и на этот случай.
Все три алгоритма для задачи НКУ компактны в том смысле, что не требуется двумерных массивов машинной памяти, за исключением тех, что хранят исходные данные задачи. Каждый из методов можно разделить на три этапа:
1. Сведение исходной задачи к безусловной задаче наименьших квадратов меньшей размерности.
2. Решение редуцированной задачи.
3. Преобразование решения редуцированной задачи в решение исходной задачи с ограничениями.
В первом методе [90], который будет описан в этой главе, используется ортогональный базис ядра матрицы ограничений. К исходной
матрице ^ | применяются левые и правые ортогональные преобразования.
По отношению к задачам с неединственным решением метод обладает таким свойством: (единственное) нормальное решение редуцированной безусловной задачи порождает (единственное) решение минимальной длины для исходной задачи с ограничениями. Поэтому метод рекомендуется в ситуации, когда задача вполне может иметь недостаточный ранг, и приходится использовать методы стабилизации (см. гл. 25), основанные на идее ограничения длины вектора решения.
