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

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

Лоуcон Ч., Хенсон P. Численное решение задач метода наименьших квадратов: учебное пособие. Под редакцией Тыртышникова Е.Е. — М.: Наука, 1986. — 232 c.
Скачать (прямая ссылка): louson_h_chisl_resh_zmnk.djvu
Предыдущая << 1 .. 70 71 72 73 74 75 < 76 > 77 78 79 80 81 82 .. 88 >> Следующая

Итерационное уточнение для задачи неполного ранга анализируется в [2*]. Для этого же случая во второй части работы [14*] дана алгольная процедура.
Г л а в а 18. Алгоритм Голуба-Бизингера-Райнша пришел на смену более раннему алгоритму сингулярного разложения, так называемому методу односторонней ортогоналиэации. Идея этого метода независимо высказана рядом авторов (см., например, [4*]). Наиболее ранняя публикация принадлежит, по-видимому, Хестенсу [37*], почему н говорят обычно об алгоритме Хестенса. В последние годы интерес к этому методу, одно время совершенно вытесненному из практики алгоритмом SVD, снова оживился в связи с удобством его реализации как на мини-ЭВМ, так и на мощных компьютерах четвертого поколения [46*, 48*].
Нужно отметить, что почти одновременно с Бизингером и Голубом и независимо от них алгоритм сингулярного разложения, очень схожий с алгоритмом SVD, построил В.В. Воеводин [1 *]. Основное различие обоих методов состоит в том, что шаг итерационной фазы в алгоритме Воеводина эквивалентен шагу @К-алгоритма без сдвигов для соответствующей трехдиагональной матрицы.
Высказанная в начале § 5 идея о том, что при больших размерах задачи и m > л целесообразно вначале привести матрицу к верхней треугольной форме последовательностью левых отражений, подробно развита в [19*] Этот вариант алгоритма сингулярного разложения становится эффективней стандартной процедуры уже при р = ш/п > 2. Для р * 10 экономия машинного времени может достигать 50%. Интересно и следующее наблюдение. Если для m = л любой вариант сингулярного разложения требует много большей работы в сравнении с нормализованным процессом, то уже при р * 3 соотношение числа операций для модифицированного SVD н нормализованного процесса равно приблизительно 3. Это соотношение может оказаться вполне приемлемым, если учесть, что SVD дает значительно больше информации о задаче.
Там же, в [19*], указана другая возможность экономии вычислений, правда, ценой введения дополнительного л X л-массива. Если пользователю нужна матрица U левых сингулярных векторов, то обычно она вычисляется следующим образом. После завершения двухдиагонализации строится в явном виде произведение Q отражений Q„ . ¦ .Q\ (точнее, первые л столбцов 0; до этого каждая из матриц Qi хранилась в компактной форме (т.е. фактически хранился соответствующий вектор и,) в нижней части массива А. Итак, Q — т X л-матрица. В последующем каждое левое вращение 7} (по стандартной оценке в QR-процессе их * 2л2) применяется
205
к столбцам Q, требуя 4т операций умножения (при обычной, "не быстрой" форме вращений). Более экономный способ состоит в накапливании произведения вращений 7} в виде л X л-матрицы Т в выделенном для этой цели дополнительном массиве. Лишь по окончании итерационной фазы алгоритма производится перемножение Q и 7Л
В [24*] предлагается вообще отказаться от формирования в явном виде ортогональных сомножителей разложения; хранятся лишь порождающие векторы отражений и информация о вращениях. Если опорная пара индексов вращения известна, то для устойчивого восстановления с и $ достаточно хранить одно число (см., например, [9*, с. 110]). В QR-процессе вращения следуют одно за другим циклами (1,2) ,(2,3),..., (n- 1,л), пока матрица не будет расщеплена вследствие появления малого внедиагонального элемента. Показано, что информация о расщеплениях и, следовательно, полная информация об опорных индексах вращений может быть упакована в целом массиве длины п. Общие требования к памяти при таком методе хранения возрастают приблизительно в полтора раза, но и время вычисления сингулярного разложения сокращается по меньшей мере вдвое.
Отметим, что алгольная программа алгоритма сингулярного разложения имеется в справочнике [10*], а фортрэнная, как уже говорилось в предисловии, - в книге [12*].
Г л а в а 19. Метод Питерса—Уипкинсона, описанный в упражнении 19.38, привлек к себе внимание многих алгебраистов. Первые отклики [20*,56*] представляли собой попытки усовершенствовать метод (в сторону уменьшения числа операций) в случае слабо переопределенных систем. Пусть L -нижняя треугольная m X л-матрица, полученная на первом этапе метода Питерса—Уилкинсона. Для искомого решениях справедлива формула
х = /Г' (LTLflLTPTb. (29)
Применим к L последовательность левых отражений Q„,..., Qt, определяемых следующим образом. Отражение Qn действует на строки L с номера-ми л, л + 1,. .., m и аннулирует элементы (л + 1, л).... , (т, л); Q„_, действует на строки Q„L с номерами л-1,л+1,...,т и аннулирует элементы (л + 1, л - 1)...., (т,и - 1); наконец, б, действует на строки Q.2... Q„L с номерами 1, л + 1,..., m и аннулирует элементы (л + 1, 1),... ..., (л>, 1). Хранить порождающие векторы отражений можно в освобождающихся позициях m X и-масс ива, первоначально содержащего матрицу L. Результатом описанного процесса будет нижняя треугольная п X л-матрица L. Полагая б = Qi • • • @н> имеем
Подставляя (30) в (29), получим
x=R-lL~l (In:Q)QPTb.
Это значит, что для вычисления х нужно найти первые л компонент вектора QPTb = Q\ ... Q„PTb, а затем решить две треугольные системы с матрицами L и R. Главный член числа операций умножения в изложенном методе равен Зтл2/2 — 7л3/6. Это меньше, чем в исходном методе Питерса—Уил-
Предыдущая << 1 .. 70 71 72 73 74 75 < 76 > 77 78 79 80 81 82 .. 88 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed