Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
0,4087 0,1593
0,4302 е 0,3516 е
0,6246 е 0,3384 е
Задача (22.39) решалась на машине UNIVAC1108 посредством подпрограммы HFTI для 40 значений е (е= 10~г,г = 1,... ,40); при этом использовался режим смешанной точности с характеристиками 17 = 2~2 7 «Ю-8,1 hcj=2"S8 *10_,7,s.
¦ V 1 "0,1376 "
¦М 1 V* 1 0,6593 е (22.39)
- . л2 J - 0,9666 е
*)х (е) =*(р), где р = е(1 - ег) 1/2. (Примеч. пер.)
120
Таблица 22.1
г 6(0 I г
1 3,7 X 10» 10
2 3,7 X 10"4
3 3,6 х 10« 36
4 6,3 х 10"* 37
5 2,6 х Ю"7 38
6 9,1 X 10"* 39
7 9,1 X 10-' 40
8 1,2 X 10"'
9 4,5 X 10'*
5,8 X 10"*
8,7 X 10"* 3,6 X 10"»
е — слишком мало; числа, умноженные на t, превращаются в машинные нули
"Подлинное" решение х было вычислено методом гл. 20; во всех вычислениях использовалась арифметика с удвоенной точностью (10~18). С округлением до 12 разрядов этот вектор имеет вид
Г -1,17749898217 [ 3,88476983058
Относительная точность кяжЧйно ЙраЙгижениого решения х^ вычислялась'
по формуле
5С-) =
1* I
Некоторые значения 6приведены в табл. 22.1.
Из этой таблицы видно, что любое значение е в интервале от 10~* до 10~37 дает приемлемое для режима обыкновенной точности (т? * 10~8,1) согласие с "подлинным" решением х.
Упражнение
22.40. Пусть в (22.1) матрица С имеет размеры т, Хл, матрица Е - размеры >л, Хл и m.-m, +т2. Обозначим через Не первую матрицу Хаусхолдера, которая
была бы построена при приведении к треугольному виду матрицы | |. Положим J.
г 1
1° «4J
Показать, что существует lim J е~' Ht Jt ж Н. Вывести формулы, позволяющие е-0
вычислить векторы и, и и, с размерностями /я, и т, соответственно и скаляр Ь/ (как функции первой строки матрицы [Ст: ЕТ ]) такие, что
Доказать, что в произведении Н ? ^ J поддиагональные элементы первого столбца
равны нулю. Доказать также, что соответствующую последовательность из т, матриц типа Н можно использовать для аннулирования всех поддиагональньгх элементов в первых т, столбцах матрицы ? ^ J. Показать, что эта последовательность операций дает тот же результат, что и формулы (21.11)-(21.14). , , . ,.
ttt
ГТГА В А 13
ЛИНЕЙНЫЕ ЗАДАЧИ НАИМЕНЬШИХ КВАДРАТОВ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ-НЕРАВЕНСТВАМИ
§ 1. Введение
Существует много приложений теории наименьших квадратов в математике, физике, статистике, математическом программировании, экономике, теории управления, общественных науках и других областях, где обычную задачу НК приходится переформулировать, включив в нее некоторые ограничения в форме неравенств. В этих ограничениях заключена дополнительная информация о задаче.
Мы будем рассматривать только случай линейных неравенств. Для этой задачи в литературе предложено большое число методов. Особо отметим работы [67, 76,174], в которых серьезное внимание уделено численной устойчивости.
Рассмотрение задач наименьших квадратов с линейными ограничениями-неравенствами позволит нам, в частности, допускать такие ограничения на решение, как неотрицательность, или независимые верхние и нижние границы для отдельных переменных, или оценки для суммы всех переменных, или (в случае сглаживания) требование, чтобы кривая была монотонной или выпуклой.
Пусть E,f, G, л - соответственно тг X л-матрица, т2-вектор, т X л-матрица, m-вектор. Тогда задачу наименьших квадратов с линейными ограничениями-неравенствами можно сформулировать следующим образом.
Задача НКН 23.1. Минимизировать Ых-f i при условии Gx>И.
Будут подробно рассмотрены и важные частные случаи задачи НКН.
Задача NNLS*) (наименьшие квадраты с условием неотрицательности) . Минимизировать И Ex - f И при условии х > 0.
Задача L D Р **) (вычисление наименьшего расстояния). Минимизировать Wx It при условии Gx> л.
Условия, характеризующие решение задачи НКН, дает теорема Куна— Таккера. Эта теорема формулируется и обсуждается в § 2 данной главы.
В § 3 исследуется задача NNLS. Представлен алгоритм ее решения, называемый NNLS. Он очень важен для последующих алгоритмов главы.
В § 4 показано, что наличие алгоритма для задачи NNLS позволяет предложить элегантное и простое решение задачи LDP.
Задача установления, совместна или нет заданная система линейных неравенств СХ> й, и отыскания в случае совместности какого-либо допустимого вектора возникает в различных контекстах. Разумеется, к ней можно применить алгоритм LDP. Для некоторых задач, связанных с совместностью и допустимостью, этот метод может оказаться особенно полезным ввиду отсутствия в нем ограничений на ранг и соотношение строчной и столбцовой размерностей G.
*) NNLS - Nonnegative Least Squares. (Примеч. пер.) **) LDP - Least Distance Programming. (Примеч. пер.)
122
В § 5 общая задача НКН с полным столбцовым рангом преобразуется в задачу LDP. Задача НКН с дополнительными ограничениями-уравнениями рассматривается в § 6.
Наконец, в качестве приложения методов, развитых для задач с ограничениями, в § 7 разобран численный пример - сглаживание при наличии ограничений-неравенств.
§ 2. Характеризация решения
Следующая теорема характеризует вектор, решающий задачу НКН.
