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

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

Лоуcон Ч., Хенсон P. Численное решение задач метода наименьших квадратов: учебное пособие. Под редакцией Тыртышникова Е.Е. — М.: Наука, 1986. — 232 c.
Скачать (прямая ссылка): louson_h_chisl_resh_zmnk.djvu
Предыдущая << 1 .. 54 55 56 57 58 59 < 60 > 61 62 63 64 65 66 .. 88 >> Следующая

будем обозначать элемент (/,/') массива W. Символ р указывает отдельную ячейку памяти.
1*2 ., •
Алгоритм 27.10. SEQHT (последовательная триангуляризация Хаусхолдера):
1. Положить / := 0.
2. Для t := 1,..., q выполнить шахи 3-6.
3. Положить р :=/ + mt.
4. Положить W(l + 1 : р, 1 : и + 1) := [А,: Ь,] (см. (27.2) и (27.3)).
5. Для / := 1, ..., min (л + \,р - 1) выполнить алгоритм Н1(/, max(i + l, /+ l),p, W(\,i),p, W(\, / + 1), и - / + 1).
6. Положить / := min(n + 1, р).
7. Замечание. Матрица [А : Ь] приведена к верхней треугольной форме (27.6).
Отметим, что для шага 4 нужно единовременно вводить в память машины лишь подматрицу [А, : Ь,]. Вся информация может быть обработана в рабочем массиве W размера и X (и + 1). Усложняя программирование, можно еще больше сократить запросы к памяти, используя то обстоятельство, что матрица [Rj: dj] верхняя треугольная.
Для последующего обсуждения числа операций обозначим через а сложение или вычитание, а через ц умножение или деление. Положим
тп2 - и3/3
В табл. 19.1 было указано, что число операций при триангуляризации т X п-матрицы (т > п) посредством преобразований Хаусхолдера равно приблизительно v(2a + 2ц), если игнорировать при подсчете константы и члены, линейные или квадратичные по га и л. Если алгоритм Хаусхолдера применяется последовательно в q этапов, как в алгоритме SEQHT (см. 27.10), то число операций возрастает примерно до и (2а + 2ц) (т + q)jm. Если вводимые блоки данных состоят каждый из к строк (kq =т),то число операций можно записать формулой и(2а + 2ц) (к + 1)/к.
Таким образом, стоимость последовательного накапливания в методе Хаусхолдера возрастает по мере уменьшения размера блока. В предельном случае к = 1 число операций приблизительно удваивается по сравнению с обычным алгоритмом Хаусхолдера.
При малых размерах блоков может оказаться более экономичной замена преобразований Хаусхолдера иа шаге 5 алгоритма SEQHT (см. 27.10) каким-либо методом, основанным на двумерных вращениях или отражениях. Число операций в этих последних методах не зависит от размера блока. Если для триангуляризации используется метод Гивенса (алгоритмы G1 (см. 10.25) и G2 (см. 10.26)), то число операций составит р(2а + 4ц). Для хаусхолдеровых 2 X 2-преобразований, записанных в виде (10.27), число операций равно v(3a + 3ju).
Если метод Гивенса применяется в модификации Джентльмена (см. гл. 10), то число операций снижается до v(2a + 2ц). Следовательно, этот метод может составить конкуренцию обычному (непоследовательному) методу Хаусхолдера и требует меньше арифметических операций, чем модификация метода Хаусхолдера для последовательной обработки.
На практике соотношение характеристик программ, реализующих зти методы, сильно зависит от деталей программирования. л..<*».;. -.*•> с > •
И*
ЛоТяТТОТи Как алгоритм авдш (см. 27.10) закончил работу, можно вычислить (если матрица R в (27.6) не вырождена) решение х из системы
Rx=d. (27.11)
Для числа е из (27.6)
\е \ = \\Ах-Ь\\. (27.12)
Во многих приложениях нужна нешкалированная матрица ковариации (см. (12.1))
С = (АГА)1 =R-1(R->)T. (27.13)
Вычисление /?"' можно осуществить на том месте, которое занимает R, а затем на том же месте можно вычислить (верхнюю треугольную часть) R~l(R~l)T. Тем самым матрица С из (27.13) может быть вычислена, по существу, без использования дополнительной памяти. Более подробно организация этих вычислений обсуждается в гл. 12. Кроме того можно вычислить величину (см. (12.2))
т - п
где число е определено в (27.6).
Для определенности алгоритм SEQHT был оформлен в виде цикла, выполняемого при / = 1.....q.B реальных приложениях этой последовательной обработки более вероятно, что шаги 3—6 алгоритма будут реализованы как подпрограмма. Число q и весь массив данных, образующий матрицу [А : Ь], могут быть поначалу неизвестны. Чтобы найти решение, опирающееся на накопленную до сих пор информацию, вызывающая программа может использовать текущую треугольную матрицу R на любом этапе, где R не вырождена. Если имеется дополнительный массив в и (л + 1)/2 машинных слов, то вызывающая программа может вычислить и верхнюю треугольную часть нешкалированной матрицы ковариации Л "'(/?"' )Т, опять же в предположении, что Rt не вырождена. Таким образом, шагиЗ-6 алгоритма SEQHT составляют его ядро, на основе которого можно строить программы последовательного оценивания.
§ 2. Последовательное накапливание ленточных матриц
В некоторых задачах матрица исходных данных [А : Ь) имеет или после предварительной перестановки строк и столбцов приобретает следующую ленточную структуру. Существуют целое число пь, пь <п, и неубывающая последовательность целых чисел j\,... ,jq, такие, что все ненулевые элементы подматрицы А, сосредоточены в столбцах ...,/', + пь - 1. Таким образом, А, имеет вид
At = [ J>_ iCtj О , ]} mu (27.14)
it"1 "b "-"ft-/f + >
Число nb мы будем называть шириной ленты матрицы А.
Легко проверить, что все ненулевые элементы /-й строки верхней треугольной матрицы R из (27.6) находятся в столбцах i.....i + nb-l.
Предыдущая << 1 .. 54 55 56 57 58 59 < 60 > 61 62 63 64 65 66 .. 88 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed