Научная литература
booksshare.net -> Добавить материал -> Математика -> Лоуcон Ч. -> "Численное решение задач метода наименьших квадратов" -> 32

Численное решение задач метода наименьших квадратов - Лоуcон Ч.

Лоуcон Ч., Хенсон P. Численное решение задач метода наименьших квадратов: учебное пособие. Под редакцией Тыртышникова Е.Е. — М.: Наука, 1986. — 232 c.
Скачать (прямая ссылка): louson_h_chisl_resh_zmnk.djvu
Предыдущая << 1 .. 26 27 28 29 30 31 < 32 > 33 34 35 36 37 38 .. 88 >> Следующая

Y=VTYV. (18.28)
В описываемом же алгоритме Y находится в факторизованной форме В В,
где В — двухдиагональная матрица. Матрицу Y также нужно построить в
факторизованной форме: Y -ВТВ. Следовательно,/? должна быть матрицей
вида В - UTBV, где V - та же ортогональная матрица, что и в (18.28), и U - также ортогональная матрица.
Переходя теперь к вычислению вращений Rt и Tt из формул (18.26) и (18.27), заметим, что первый столбец матрицы ВТВ - о/ имеет вид
4-1*2
О . (18.29)
где о вычисляется в соответствии с (18.22). Первое вращение R t определяется требованием, чтобы второй элемент первого столбца матрицы RT(BTB - о/) был нулем.
Остальные вращения определяются в порядке TltR2, T2,...,R„-i, 7,„_1 и применяются в порядке, указываемом скобками в следующем выражении:
Т„ _,( ... Г,((7,№, ))R2)... Rn _,). (18.30)
Вращение Tt, / = 1,..., и — 1-, оперирует со строками / и / + 1 и аннулирует элемент в позиции (/' + 1, /). Вращение Rt, i = 1,..., и - 1, оперирует со столбцами / и / + 1 и при /' > 2 аннулирует элемент в позиции (/ — 1,1 + 1).
Это пример алгоритмического процесса, называемого иногда вытеснением. Рис. 18.1 показывает для и = 6 последовательность появления и исчезновения элементов во внешности двухдиагональной полосы.
Из предыдущего обсуждения очевидно, что вычисление сингулярного Разложения произвольной тп X и-матрицы можно свести к более специальной задаче сингулярного разложения невырожденной двухдиагональной
87
Рис. 18.1. Иллюстрация процесса иытесиения в одном ОД-шаге для случая л = 6
матрицы В в форме (18.7). Сейчас будет сформулирован алгоритм QRBDJ выполняющий один шаг этой основной части в вычислении сингулярного] разложения. Прежде всего алгоритм сравнивает внедиагональные элемен| ты et с заданным допуском е. Если имеются индексы /', 2 </" <и, для которых \е{\ < ?, то наибольший такой индекс помешается в ячейку /, и алгоритм прекращает работу. В противном случае выполняется присваивание / = 1; такое значение / указывает, что | et \ > е для 2 </' <и. После этого алгоритм переходит к вычислению сдвига (см. (18.22)). Далее алгоритм
вычисляет н применяет вращения Rt и Tit i = 1.....и - 1 (см. (18.30)).
Когда алгоритм заканчивает работу, элементы преобразованной матрицы
B = UTBV замещают в памяти одноименные элементы В.
В некоторых случаях, например при решении задачи НК, нужно умножать некоторые другие векторы или матрицы на матрицы UT и V. Алгоритм QRBD предоставляет пользователю возможность задать к X «-матрицу W= {wtj) и и X р-матрицу G ~{gtj) , которые будут заменены произведениями WV и UTG соответственно.
Алгоритм 18.31. QRBD (q, е, п, е, I, W, к, G, р):
1. Комментарий. Шаги 2 и 3 предназначены для выявления малых вне-диагональных элементов.
2. Для i := и, и - 1,. . ., 2 выполнить шаг 3.
3. Если |е, |<е, положить l:=i и перейти к шагу 14.
4. Положить / := 1 и вычислить о в соответствии с формулами (18! 16) —, (18.22). 4 1
5. Положить i =2. '
6. Положить <?i :=<7i - ojqx и z :=<?2 (см. (18.29)).
7. Выполнить алгоритмGl(e;_,, z, с, s, e/_i).
8. Выполнить алгоритм G2(c, s, qt_v et) и для / := 1,...,к выполнить алгоритм G2(c\ s, w;.,, wfj).
9. Положить z : = sqt, qt .^cq^ c,;
10. Выполнить алгоритм Gl(ql_l, z, c, s, q,_i).
11. Выполнить алгоритм G2(c, s, et,qt) и для / := 1,.,., p выполнить алгоритм G2(c, s,gi_l /;gtj).
88 \
12. Если i = и, перейти к шагу 14.
13. Положить z := sei+I, ei+i := cel+I, i := i + 1 и перейти к шагу 7.
14. Комментарий. Если / = 1, то был выполнен один полный Qfl-шаг для двухдиагональной матрицы. Если / > 1, то элемент ех мал, и матрицу можно расщепить в этом месте.
Повторным применением алгоритма QRBD к невырожденной верхней
двухдиагональной матрице В строится последовательность двухдиагональ-
D (fc) (*)
ных матриц Вк с диагональными элементами cjj , .. ¦, q„ и наддиаго-
(1с) (к)
нальными элементами ег ...., еп . Согласно теореме 18.5, произведение
е„*' ч*„** квадратично сходится к нулю при А: Из предположения о
невырожденности В вытекает, что последовательность (ч*п**} отделена от
нуля. Следовательно, последовательность квадратично сходится
к нулю. На практике итерации прекращают, когда | | < е.
После того как величина I еп I признана достаточно малой, переходят к вычислению сингулярного разложения для двухдиагональной матрицы (или нескольких таких матриц) порядка и - 1 (или меньшего); зто делается так же, как и выше, с заменой и на и - 1. Так происходит, пока не будет и = 1. Не более чем л — 1 повторений описанной процедуры приводят
к разложению В = USVT.
Практика показывает, что при значениях параметра точности 17 в пределах примерно от Ю~18 до Ю-8 и при б = т)||?|| обычно бывает достаточно около 2л повторений алгоритма QRBD, чтобы все внедиагональные элементы стали по модулю меньше е.
Диагональные элементы 5 в общем случае не являются неотрицательными или невоэрастающими. Чтобы поправить этот недостаток, возьмем диагональную матрицу D, на диагонали которой стоят плюс и минус единицы, выбранные так, что у матрицы
Предыдущая << 1 .. 26 27 28 29 30 31 < 32 > 33 34 35 36 37 38 .. 88 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed