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

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

Лоуcон Ч., Хенсон P. Численное решение задач метода наименьших квадратов: учебное пособие. Под редакцией Тыртышникова Е.Е. — М.: Наука, 1986. — 232 c.
Скачать (прямая ссылка): louson_h_chisl_resh_zmnk.djvu
Предыдущая << 1 .. 13 14 15 16 17 18 < 19 > 20 21 22 23 24 25 .. 88 >> Следующая

ГЛАВА 12
ВЫЧИСЛЕНИЕ КОВАРИАЦИОННОЙ МАТРИЦЫ РЕШЕНИЯ
Симметричная, положительно определенная матрица
С = (АтАу\ гапкЛ=и, (12.1)
или ее скалярное кратное (скажем, о2С), имеет при соответствующих предположениях статистическую интерпретацию в качестве оценки ковариационной матрицы для решения задачи НК (см., например, [144]). Мы будем называть С нешкалированной ковариационной матрицей. 52
g этой главе будут представлены некоторые алгоритмы вычисления С. ^ы вЬщелим также некоторые часто встречающиеся ситуации, когда можно избежать явного вычисления С, пересматривая ее роль в последующем анализе.
Мы не станем обсуждать причину появления или интерпретацию скалярного множителя а2. Отметим только, что обычно а2 вычисляют по формуле
lAx-M
а2 = - . (12.2)
т-п
где х - решение задачи Ах^ b, am ии - соответственно число строк и число столбцов матрицы А.
Мы обсудим алгоритмы вычисления С, использующие те или иные разложения матрицы А. Эти разложения вычисляются в ходе трех различных методов решения задачи НК, детально изучаемых в данной книге, и выглядят следующим образом:
QA =?о J , Rnxn - верхняя треугольная (см. гл. 11); . (12.3)
---, .»<ЭГ.С ¦ .=5
If Rnxп -верхняя треугольная (см. гл. 14№ *" ' (12.4)
О J ' к' -".Л"
Г51
UTA V = I I , SnXn - диагональная (см. гл. 18). (12.5)
Разложения (12.3) — (12.5) вычисляются соответственно алгоритмом HFT (см. 11.4), алгоритмом HFTI (см. 14.9) и алгоритмом сингулярного разложения гл. 18. Матрица Q в (12.3) ортогональная порядка т. Обе матрицы Q и Р в (12.4) ортогональные, причем Р — матрица перестановки. Матрицы U и V в (12.5) имеют порядок тип соответственно, и обе они ортогональны.
Легко видеть, что соответственно этим трем случаям
ATA=RTR, (12.6)
АТА -PTRTRP, (12.7)
ATA = VS2VT, (12.8)
и если rank Л = п, то ооращение этих урриаянщив§г (. ; j. ,
С= (АТАУ1 =/Г1(Д~,)г, (12.9)
С=(АТАУ1 =PR~l(R-l)TPT, (12.10)
С=(АТАУ1 = VS-2VT. (12.11)
Рассмотрим вначале детали вычислений в соответствии с формулами (12.9) и (12.10). Здесь три основных шага.
1. Обращение верхней треугольной матрицы R (или R) на месте, занимаемом ею в памяти.
2. Формирование верхней треугольной части симметричной матрицы ^ l(R~1)T илиR~l(R~l)T. Она может замещать/?"1 (илиЛ"1) в памяти.
53
3. Перестановка строк и столбцов матрицы R~l(R~l)T. На каждо] шаге матрица симметрична, поэтому в хранении нуждается лишь ее вер] няя треугольная часть.
Чтобы вывести формулы обращения треугольной матрицы R, обоз» чим элементы R~l через ty. Тогда из тождества R~lR = / и того обсто! тельства, что обе матрицы R и R~l верхние треугольные, получаем ypj| нения
/ f1- i=>>
'"' 10, 1Фи
К /'< и, /< / < и.
Решая относительно Хц, находим ¦ ,
' ,-1
r„, 1 = 1,
Чтобы при вычислении элементов иметь возможность замещать им элементы Гц и заодно сократить число операций деления, эти формул следует использовать таким образом:
г« = г«!' ,= 1.....и> '
tt/ = -tjj Ztnrlh j = i + 1.....и, / = 1.....и - 1.
Счет по этим формулам требует и3/6 + 0(и2) операций, где под операцие понимается "умножить и сложить" или "поделить и сложить". Умнож ние/Г1 справа на транспонированную матрицу (см. (12.9)) также требу! п3/6 + О (/г) операций. Следовательно, алгоритм COV вычисляет элемент верхнего треугольника матрицы (АТА)~1 по элементам R за и3/3 + 0(п2 операций.
В алгоритме COV предполагается, что задаваемая на входе матрица (или R) из правой части формулы (12.6) (или (12.7)) занимает верхню треугольную часть массива с именем А. На выходе в верхней треугольно части массива А будет находиться верхняя треугольная часть матриц (АТА)~1. Массив с именем р содержит информацию (полученную, напр мер, алгоритмом HFTI (см. (14.9)), описывающую действие матрицы (из (12.10).
Алгоритм 12.12. COV (А,п,р):
1. Для i: = 1,..., и положить att; = l/art.
2. Если п= 1, перейти к шагу 8.
3. Для /: = 1, ..., и - 1 выполнить нижеследующее до шага 7 в ключ тельно.
4. Для /: = /' + 1, ..., и выполнить нижеследующее до шага 7 включ тельно.
5. Положить s: =0.
6. Для /: = 1,...,/- 1 положить i: ¦ i + а^ву.
7. Положить ац: = -вцЗ.
54
8. Для /: = 1, . •., и выполнить нижеследующее до шаха 12 включительно.
о Для /: =1, ..., п выполнить нижеследующее до шага 12 включительно.
10.Положить s: =0.
11.Для /: =/'.....и положить s: = s+a{taji.
12.Положить atl: =s.
13. Замечание. Закончено вычисление элементов верхнего треугольника матрицы {АТА)~1 для случая (12.3), где не делается перестановок при вычислении R. В случае же (12.4) нужно еще выполнить шаги 14-23, соответствующие левому умножению на Р и правому умножению на Рт (см. (12.10)). В этом случае мы предполагаем наличие массива целых чисел p{,i=\, ..., п. Смысл этих чисел такой: /-я перестановка в процессе приведения А к треугольному виду была перестановкой столбцов с номерами i и pt.
14. Для (': = и, ..., 1 выполнить нижеследующее до шага 22 включительно.
15. Если pt = I, перейти к шагу 22.
16. Положить к: =р{. Поменять местами содержимое ячеек аи и акк. Если i ~ 1, перейти к шагу 18.
Предыдущая << 1 .. 13 14 15 16 17 18 < 19 > 20 21 22 23 24 25 .. 88 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed