Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Вместе с численно устойчивыми приемами модификации метод может быть применен к решению последовательности задач НКУ, в которой очередная матрица С получается из предыдущей добавлением или удалением строк. Именно таким образом метод использован в [174] для построения алгоритма, решающего задачу НКН.
Кроме всего прочего метод представляет и теоретический интерес. С его помощью в теореме 20.31 показано существование безусловной задачи наименьших квадратов, эквивалентной задаче НКУ в том смысле, что обе имеют одно и то же множество решений для любых правых частей d и f. Это позволяет применять к задаче НКУ такие численные процедуры, как, например, сингулярное разложение.
Второй метод, описываемый в гл. 21, основан на прямом исключении и использует как ортогональные, так и неортогональные левые преобразования.
Каждый из этих двух методов можно использовать для удаления ограничений-равенств (если таковые имеются) в качестве первого шага в решении задачи НКН. Кроме того, оба метода адаптируются к последовательной обработке данных, когда после триангуляризации исходной матрицы добавляются новые строки к системе ограничений [C:d] или системе наименьших квадратов [Е: /],
Третий метод для задачи НКУ, изложенный в гл. 22, освещает некоторые важные свойства преобразования Хаусхолдера в применении к задаче наи-
104
меньших квадратов с сильно различающимися весами. С практической точки зрения главное достоинство этого метода состоит в следующем: он дает возможность решать задачу НКУ в случае, когда пользователь имеет доступ к подпрограмме метода Хаусхолдера для безусловной задачи наименьших квадратов, но не имеет и ие хочет составлять сам программу одного из алгоритмов, специально рассчитанных на задачу НКУ.
Перейдем теперь к описанию нашего первого метода для задачи НКУ. В методе используется явное параметрическое представление элементов линейного многообразия
X = {х. Сх = d). (20.4)
Если , , v ,
С = HRKT x^-t'.'v (20.5)
есть произвольное ортогональное разложение (определение см. в гл. 2)
матрицы С, л К представлена в виде
* = [*,: Кг ]}и, (20.6)
. t -
*. п - к,
то (см. теорему 2.3, равенство (2.8)) южш представить как (
X ={х: х=х+К2у2), |. .м*Ч,}, (20-7>
где ч „, ^ г , г .-^у
х = C*d, llf (20-8)
а у 2 пробегает пространство всех векторов размерности п — к%.
Теорема 20.9. Если система (20.2) совместна, то задача НКУ имеет единственное решение минимальной длины, задаваемое формулой
х = C*d + (EZ)\f- EC+d ), (20.10)
где
z = г„-с+с, .; *¦*
или .что эквивалентно, > < —,
х = C*d + K2(EK2)\f-EC*d). - (20.11)
Матрица К2 определена в (20.6).
Вектор х является единственным решением задачи НКУ тогда и только
С]
тогда, когда система (20.2) совместна и ранг матрицы
^ j равен п.
До казательство. Установим эквивалентность выражений (20.10)" и (20.11). Заметим прежде всего, что Z = 1„ - С*С = ККТ - KR*RKT ш
КК1
Г7*, о L 0 0
Кт = ККТ - КХК\ = К2К{. Поэтому EZ *
105
Равенство (ЕК2К^)* = К2(ЕК2)* можно проверить прямой подстановкой в условия Пенроуза (теорема 7.9), учитывая, что К2К2 = /„_ k . Таким образом, (20.10) и (20.11) эквивалентны.
Представление (20.7) показывает, что задача минимизации величины (20.3) по всем х € X эквивалентна отысканию такого п — k i-вектора уг, который минимизирует величину ||?(х + К2у2) — /||, или, что то же самое,
\\(EK2)y2-(f-Ex)\\. (20.12)
Согласно (7.5), единственное нормальное решение этой задачи выражается формулой
Рг*(ЕКг)\Г-Ех). (20.13)
В соответствии с (20.7) решение задачи НКУ запишется как
х = х + К2у2 , (20.14)
что эквивалентно (20.11), а также (20.10).
Поскольку столбцы К2 попарно ортогональны *) и все вместе ортогональны к х, то для нормы любого вектора х& X
\\х\\2 = ||5ё|[2 + \\у2 Н2-. (20.15)
Если вектор у2 Ф у2 также минимизирует (20.12), то \\у2 II >ll>'2ll-
Следовательно, х = х + К2у2 является решением задачи НКУ; при этом
II * II2 = II х ||2 + || yt ||2 > || х ||2 + || у2 ||2 = || * ||2. (20.16)
Тем самым х - единственное решение минимальной длины для задачи НКУ.
Остается связать единственность решения задачи НКУ со значением к:
к = rank
Ясно, что при А: < и существует n-вектор w Ф 0, для которого
|?| w = 0, (20.17)
и если х — решение задачи НКУ, то х + w — также решение. Пусть, с другой стороны, к = п. Рассмотрим (т, + т2) Хп-матрицу [С] ГС*! СК2Л ) т,
Af= \ \К = , , (20.18)
L Е J L EKt ЕК21 ) т2
п - Ас,
ранг которой также равен п. Так как у этой матрицы и столбцов, они
*) И нормированы. (Примеч. пер.) 106
должны быть линейно независимыми. Поскольку СК2 - О, rank ЕК2 непременно равен и — А.1. Поэтому у из (20.13) - единственный вектор, минимизирующий (20.12), а х из (20.14) - единственное решение задачи НКУ. Теорема 20.9 доказана.
Вычислительную процедуру можно построить на базе формулы (20.11). Будем считать, что k{ = т,, так как это — обычный для практики случай. Тогда в качестве матрицы Я в (20.5) можно взять единичную матрицу.
Пусть К - ортогональная и X л-матрица, которая, будучи умножена на С слева, преобразует С к нижней треугольной матрице. Умножим С и Е справа на К; тогда
