Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
С,С,=С,. (23.45)
После этого находят вектор хг как решение следующей задачи НКН: Минимизировать
ЪЁ2х2 - ~f\ " (23.46)
приусловии (Gt-eiC2) х% >h - G,<?.
130
Наконец, решая верхним» треугольну» систему
С,х, =d-C2x\, вычисляют вектор jc, .
(23.47)
§ 7. Пример выравнивания при наличии ограничений
В качестве примера, который иллюстрирует ряд приемов, описанных в этой главе, рассмотрим задачу выравнивания экспериментальных данных при некоторых ограничениях на аппроксимирующую прямую.
В следующей таблице приведены исходные данные задачи:
г w I 1 W
0,25 0,5 0,50 0,7
0,50 0,6 и , ! ч ^ .,;Htii 0,80 ¦ • ; *>* 1.2
Мы хотим найти прямую /(г) =х,г+дг2,
(23.48)
которая аппроксимирует эти данные Щ ОИИОЯе МфВада наименьших квадратов при следующих ограничениях:
П0>0,
/(0) > 0,
/(1)<1.
Эту задачу выравнива Минимизировать
lEx-fl при условии Gx>h, где
"0,25 I-
0,50 1 0,6
0,50 1 0,7
_ 0,80 1 _ -1,2_
' (23.49) (23.5Х)) (23.51)
в форме afjjrm НКН: (23.52)
Чтобы (как это описано в § 5) свести задачу НКН к задаче LDP, вычислим ортогональное разложение матрицы Е. Годятся и сингулярное разложение Е, и ДО-разложение Е. Проиллюстрируем применение сингуляр-
9»
131
иого разложения
•^2X2
Е
..Г2'255
L о,о
h
0,0 I Г-о,
0,346.1 1-0,!
-0,467 ,884
0,884 -0.467
-1,536 0,384 -0,054 L 0.174J
Выполним замену переменных z=SVTx-fl.
Теперь нужно решить следующую задачу LDP? Минимизировать
11 -г II
(23.53)
(23.54)
при условии Gz > И, где
Г-0,207 2,558
G = GKS_,= -0,392 -1,351
0,599 -1,206 J
|-l,300l h = h-Gft = -0,084 L 0,384 J
Графическая интерпретация этой задачи дана на рис. 23.1. Каждая строка расширенной матрицы [G: h ] определяет граничную прямую области
2,
Ограничение!
Область допустимых значений
Рис. 23.1. Графическая интерпретация иллюстративной задачи LDP (23.54)
допустимых значений. Решение х есть точка этой области, ближайшая К началу координат. Вычисления по алгоритму LDP дают
Р н с. 23.2. График выравнивающей прямой для иллюстративной задачи (2348)-(23.51)
х = VS'l(z+f
Невязка для решения х имеет
вид
г=/-Ех =
Иг 1 = 0,338.
-1- г'\ ¦ у. —1— —1-1-
1.2
Л' '
¦
as ' '. 8
¦1Ч.,)»1.
1 .и 1 1 „ I
О 0,25 0,50 0,8 1,0
На рис. 23.2 показаны заданные точки(г,-, и>,),| = 1,... ,4,ивырав-
ниваюшая прямая f(t) =0,621/ + 0,379. Отметим, что третье ограничение /(1) < 1 оказывается активным и влияет на точность аппроксимации заданных точек.
Числовые значения, указанные в разборе данного примера, были получены на машине UNIVAC 1108. Когда та же фортранная программа выполнялась на IBM 360/67, то промежуточные величины K,/i,G,z были вычислены с противоположными знаками. Это является следствием того обстоятельства, что знаки столбцов матрицы V из сингулярного разложения не определены однозначно. Разное число итераций, потребовавшееся при вычислении сингулярного разложения матрицы Е на двух машинах с различной длиной слова, привело к разному приписыванию знаков матрицам U и V.
Упражнения
23.55. Доказать, что если задача НКУ имеет единственное решение без ограничений-неравенств, то она имеет единственное решение и при наличии таких ограничений*).
23.56. Показать,что задача минимизации квадратичной функции /(х) =л Вх/2+e х, где В — положительно определенная матрица, заменой переменных w=Fx-g и подходящим выбором невырожденной матрицы F и вектора g сводится к задаче минимизации I w II1 /2.
23.57. Если функцию f (х) из упражнения 23.56 нужно минимизировать при наличии ограничений Cx = d и Gx>li, то каковы будут соответствующие ограничения в эквивалентной задаче минимизации II wt '/2?
*) Разумеется, > случае совмесгностя с дополнительным* вгришШжкШшТЩримеч.
пер.) ч ¦ "
.-•<»»» -
133
глава 24
МОДИФИКАЦИЯ (?Л-РАЗЛОЖЕНИЯ МАТРИЦЫ ПРИ ДОБАВЛЕНИИ ИЛИ УДАЛЕНИИ СТОЛБЦОВ
Эффективность алгоритма гл. 23 для задачи НКН связана с возможностью эффективно решать, последовательность задач наименьших квадратов. Мы видели, что в алгоритме NNLS (см. 23.10) матрица коэффициентов на каждом шаге получается из предыдущей добавлением или удалением столбца (не являющегося линейной комбинацией остальных).
Поэтому мы обсудим такую задачу. Пусть и> 0 и ai.....а„ — система
m-векторов. Рассмотрим матрицу
Л* = [«i ...««¦] " , " 1 (24.1)
и ДО-разложение этой матрицы ( :
QAk = И* , ' i (24.2)
где Rk - порядка к невырожденная верхняя треугольная матрица*), a Q -ортогональная матрица. Как только Q и Rk вычислены, решение задачи
Акх<*Ъ (24.3)
можно найти по формуле
*= [Ril:0] Qb= A\b, (24.4)
требующей лишь очень небольшой дополнительной работы. } _
Рассмотрим задачу о вычислении ДО-разложения матрицы, полученной из Ак удалением или приписыванием столбца, и постараемся извлечь выгоду из имеющегося 0/?-разложения матрицы Ак. Опишем три полезных метода модификации ДО-разложения. Как показывает (24.4), модификация Q и R, по существу, дает способ модификации матрицы А*к.
