Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
значит, что w Gi О О ± 1 l& О Положим
Q
.77 т _
= av
т _.
. Поэтому (27.39) можно переписать в виде
L о
Q =
[ Q.2
(27.40)
(27.41)
Матрица Q - ортогональная матрица порядка m - 1, R - верхняя треугольная к X n-матрица и
ос
¦\:\
(27.42)
Тем самым Q и R удовлетворяют требованиям, предъявляемым к матрицам Q и R (см (27.35) и (27.36)).
Каков ранг R (к или А: - 1), зависит от того, равно или нет нулю число а в (27.38). По предположению все к диагональных элементов R ненулевые. Если а Ф 0, то, исследуя структуру и действие матриц Гивенса, участвующих в переходе от (27.38) к (27.40), легко убеждаемся, что все А: диагональных элементов R также будут ненулевыми.
Пусть, напротив, а = 0. Тогда llpll = 1, и, следовательно, некоторые компоненты вектора р отличны от нуля. Пусть р, — последняя ненулевая компонента р, т.е. р, Ф0,и если / Ф к, то р{ = 0 для К i<k. Учитывая порядок, в котором применяются матрицы Gtj при переходе от (27.38) к (27.40), видим, что G,k+l будет первой матрицей, не совпадающей с единичной. Эта матрица G,ik+i (с точностью до знака) является матрицей перестановки строк / и к + 1, возможно, с изменением знака одной из этих строк. В частности, ее действие на R состоит в замене строки / строкой нулевых элементов. Последующие преобразования не меняют эту строку. Следовательно, в (27.40) 1-я строка R нулевая.
Итак, в этом случае rank/! будет меньше, чем А:. С другой стороны, rank R не может быть меньше к - 1, так как rank R = rank С > rank С — 1 = = * - 1.
2. Удаление строки. В задаче, где m очень велико или используется последовательное накапливание, матрицу Q из (27.32) обычно не сохраняют. В этом случае метод 1 нельзя применить непосредственно. Однако все, что нужно от Q при определении матрицы R в методе 1, - это вектор р из (27.37) и (27,38) и число а из (27.38). Мы увидим, что эти величины р и а можно вычислить по R и v. Перепишем (27.32) в виде
С =QT
(27.43)
Используя блочное представление (27.37), находим vT=pTR
(27.44)
или, что то же самое,
(27.45)
Если R имеет ранг п, то (27.45) - это невырожденная треугольная система, которую можно разрешить относительно р.
Если к = rank R < и, то система (27.45) все же совместна и имеет единственное fc-мерное решение р. По предположению первые к строк R т составляют треугольную к X Л-подматрицу с ненулевыми диагональными элементами. Эта подматрица вместе с первыми к компонентами вектора v определяет систему уравнений, которую можно разрешить относительно р.
Определив р, можно вычислить число а по формуле
Эта формула является следствием того, что в (27.38) евклидова длина столбца (р г, а, 0) г равна единице. Величина а имеет произвольный знак и может быть взята неотрицательной, что и сделано в (27.46).
После того как р и а вычислены, матрицу R можно построить с помощью к преобразований Гивенса, как это объяснено в изложении метода 1 вслед за формулой (27.38). Эту часть процесса можно описать равенством
Следует ожидать, что метод 2 будет несколько менее точной численной процедурой, чем метод 1, из-за необходимости вычислять р н а по формулам (27.45) н (27.46). На точность, с которой определяется вектор р, влияет число обусловленности R; оно, разумеется, равно числу обусловленности С.
Это ограничение на точность является, по-видимому, неизбежным в любом методе модификации множителя Холесского R при удалении данных, который не использует дополнительных хранимых матриц типа Q или С. Можно ожидать, что при заданной точности машинной арифметики методы модификации, оперирующие непосредственно с матрицей (АТА)~1, будут значительно менее надежными, чем метод 2.
3. Удаление строки. Этот метод интересен тем, что требует меньше операций, чем метод 2, и алгоритмически очень схож с одним нз методов, используемых при введении дополнительных данных. Это позволяет построить очень компактную программу, выполняющую и введение, и удаление информации. Сравнительная численная надежность методов 2 н 3 не исследовалась.
Метод 3 рассматривался в [37, 65,66,71]. Следуя примеру авторов этих работ, мы ограничимся обсуждением случая, когда rank С = rank С = к = и. Свойства более общего случая выясняются в упражнениях.
Пусть I обозначает мнимую единицу, т.е. i2 = - 1. Равенство (27.36) можно переписать в виде
а = (1 - Hp II2)
гл\/2
(27.46)
(27.47)
(27.48)
12.4. Лоусон
177
Формально используя соотношения Гивенса (3.5), (3.8) и (3.9), можем построить матрицы F*'\ которые приводят к треугольному виду матри-Г R 1
ну j т I . Это достигается следующим процессом:
ГЛ<'> 1 ... Г д<»-«> 1
[iv<nrrF In/'-'H' /в1*• (2750)
[о ] = [ п/*>г]
(27.51)
Здесь матрица F*'* отличается от единичной только элементами, стоящими на пересечении строк / и А: + 1 со столбцами / и к + 1. В этих четырех позициях находится подматрица
Г о<'> МО! I-/><'> о<'> J '
(27.52)
где
«ЮЧг,?-0]*-^-0]8. (27-53)
p(/) = [5(/)ji/2 - (27 54)
0(')=Г/('-«)/р(/) (2755)
r(') = u/'-,)/p('). (27.56)
Из нашего предположения о полноте ранга обеих матриц С и С можно вы-
