Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Метод 1. Предположим, что Q хранится как явно вычисленная**) ортогональная т X m-матрица, a R — как верхняя треугольная к X Л-матрица.
Приписывание вектора. Пусть ак + х — вектор, не являющийся линейной комбинацией столбцов Ак. Составим расширенную матрицу
Ак+1 = [Ак :ак+1). (24.5)
Вычислим произведение bk+l = Qak+l, где Q - матрица из (24.2). Построим матрицу Хаусхолдера 6*+i так, чтобы вектор rk+x =Qk+ibk+1 имел нулевые компоненты в позициях А:+ 2, ...,т***).ТогдаДО-разложение матрицы Ak+i дает формула
а*..-[;].
*)Система в,,... ,«„ считаетси линейно независимой. (Примеч. пер.)
**)а не факториэованная, как в методе 2. (Примеч. пер.)
***)Сохранив неизменными компоненты с номерами 1,..., к. (Примеч. пер.)
134
где
fl "**'"• Ш[о]"4
Удаление вектора. Пусть матрица А к из (24.1) модафащвруется
удалением столбца Ду, в результате чего получается матрица ' ¦
Л*_, = [д, ... Д/_, а1+, ... ак). (24.6) Если положить
QAk-1 = [г, .. . г/_, г/+, ... гк), (24.7)
то каждый вектор г, имеет нули в позициях / + 1, ..., m (см. [76, 174]). Введем матрицу
(? = G*_i ... G/Q, (24.8) где Gj - вращения Гивенса, ШЫврШШШМ Так;'
¦¦¦И
&4fc_,= , (24.9)
была верхней треугольной. Матрица Gt оперирует со строками i и i + 1 и позволяет получить нуль в позиции (i + 1, i) произведения С,... G/QAk_ j.
Метод 1 требует т2 машинных слов для хранения Q и /(/ + 1)/2 слов для хранения R. Здесь /, Km, — наибольшее число векторов as, используемых одновременно.
Метод 2. Вместо явного хранения матрицы Q, как в методе 1, мы будем теперь считать, что Q задана как произведение к преобразований Хаусхолдера
G = &..•(?.. "-НЧЧУ"С . (24.10)
Для каждой матрицы
<?#¦=/« +*71и#и7 ' ' (24.11)
хранятся лишь ненулевые элементы вектора щ, а также используется еще одна ячейка. Матрица R по-прежнему хранится как верхняя треугольная к X fc-матрица.
Приписывание вектора. Пусть система столбцов (24.1) расширена с сохранением свойства линейной независимости до системы [a i ... ... д*+1]. Вычислим произведение bk+i =Qk .. .Qiak+i. Построим преобразование Хаусхолдера 6*+i так, чтобы вектор =r*+i имел нули в позициях к + 2,..., т *). Тогда формула
б*+1(б*...б.)И* =[[о]:Г*+1] (24Л2*
дает с?/?-разложение расширенной матрицы.
*)См. примечание на стр. 134 {Примеч. пер.)
135
Удаление вектора. Снова рассмотрим матрицу Ак-j из (24.6). Запишем более подробно формулу, определяющую ДО-разложение матрицы .4*:
Qk-. QxAk = = 0 Л22 \) • (24.13),
Представим искомое ДО-разложение Ак-\ в виде
ал... .[*].
В матрицу Л в качестве ведущей главной подматрицы порядка / — 1 входит та же, что и в (24.13), матрица Л п. Поэтому нужно найти только последние к — j столбцов R.
Одна из возможностей состоит в том, чтобы на место подматрицы
Л 12 R 22
_о J
записать систему 1 ... ак]. Далее вычисляем произведение
(?/_!...(?, ...я*] =Smx (*-/)• '] С?4.14>
Наконец, строим новые преобразования Хаусхолдера-fij так, чтобы
к-1
;s = д22 >*-/ ,
.0 + 1
Qk-i.--Q}
где 7?22 - верхняя треугольная матрица.
ДО-разложение матрицы i теперь имеет вид
[Л„ Л12 о д22 о о
Иначе матрицу 5 из (24.14) можно построить по формуле' Rl2
QjQj
Qk
l22
~ [Oj- S], Of = С/ _ 1 . . .
(24.15)
где 7?',j и /?22 определены в (24.13).
Метод 2 требует (m+ 1) / машинных слов для хранения информации, определяющей Q и R. Здесь I, Km, - наибольшее число векторов as, используемых одновременно. Вариант метода 2, опирающийся на формулу (24.14), требует дополнительного mXn-массива для хранения копий векторов alt . ... а„, с тем чтобы при необходимости использовать их в вычислениях по этой формуле.
Во втором варианте метода 2, использующем соотношение (24.15), устраняется необходимость в хранении копий векторов а/, а/+1, ..., а„. Поэтому вся информация о ДО-разложении матрицы Ак и векторы at, 136
не включаемые в данный момент в число столбцов Ак, могут быть (с точностью до дополнительных Зт ячеек) хранимы единым т X п-массивом.
Метод 3. В этом методе все содержимое массива ^mX(n+i), который поначалу хранит исходные данные задачи [Атх„ : ftmX 1], модифицируется каждый раз, когда приписывается или удаляется из базиса очередной вектор. Столбцы верхней треугольной матрицы Rk из (24.2) занимают некоторые к столбцов массива W. Матрица Q из этой формулы не хранится.
Пусть ={pi, ..., Рк) - подмножество в (1, ..., и), определяющее столбцы А, введенные в базис. Порядок чисел р, в множестве &к важен. Пусть Ак - тХ А;-матрица, образованная столбцами А, которые индексированы множеством 03 в порядке Pi, ..., рк. Пусть Q — ортогональная матрица из формулы (24.2). Тогда в массиве W находится тХ (и + 1)-матрица Q[A :Ь). Это значит, что /-й столбец Rk хранится в столбце р/ массива W. В рассматриваемом методе может оказаться удобным явное хранение нулевых элементов, полученных преобразованиями Хаусхолдера или Гивенса.
Приписывание вектора. Пусть pk+i - индекс столбца А, приписываемого к базису. Составим новое индексное множество ?lbk+i, присоединяя к 9s к индек р& +1. Построим преобразование Хаусхолдера Н, которое в столбце рк+х массива W аннулирует элементы, находящиеся ниже строки к + 1 *). Умножим на Я слева весь массив W.
