Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
206
кинсона или в методе отражений, если т <5п/3, и даже меньше, чем в обычном методе нормальных уравнений, когда т < 4и/3.
Рассмотренный нами метод Клайна [20*] отличается от метода Пнтерса-Уилкинсона тем, что задача наименьших квадратов Ly=iPTb решается (вместо перехода к нормальным уравнениям) своеобразным вариантом метода отражений, учитывающим форму матрицы L. В [56*] предлагается на этом этапе вместо отражений использовать модифицированный процесс Грама—Шмидта.
Главная идея метода Питерса—Уилкинсона состоит в том, чтобы заменить решение "плохо обусловленной" системы нормальных уравнений
АТАх=АТЬ
решением "хорошо обусловленной" системы " } " *н н '
LTLy - LTPTb. ' (31)
Надежда на хорошую обусловленность системы (31) опирается на то, что все элементы матрицы L по абсолютной величине не превосходят единицу - зто обеспечивается матрицей перестановок Р. Практика метода свидетельствует, что зта надежда обычно оправдывается (хотя с точки зрения теории существуют треугольные матрицы, ненулевые элементы которых равны 1 или -1, с числом обусловленности порядка 2"; такова, например, первая матрица Кахана из гл. 6). Так как, однако, число операций в методе Питерса-Уилкинсона (в главном члене) такое же, что и в методе отражений, где нет проблем с обусловленностью, то для задач с хранимыми матрицами первый метод не обладает никакими преимуществами. Современный интерес к нему связан с тем, что для больших систем разреженность обычно удается сохранить лучше при неортогональных преобразованиях. "Разреженная" трактовка метода Питерса-Уилкинсона дана в [16 *].
Глава 20. Оценки возмущения для решения линейной задачи наименьших квадратов с линейными ограничениями-равенствами получены в [27 * ]. Эти оценки обобщают выведенные в гл. 8, 9 оценки возмущения для решения обычной задачи НК.
Пусть система Сх = d совместна, и пусть х — решение задачи
min || Ex-/||, F = {x|Cx=d}. ,4*2)
F
Составляя функцию Лагранжа
Ф(х,Х) = ||?х-/||2 +(Х, Cx-d),
где X - mi-вектор множителей Лагранжа, и приракШвНяУ nynio^lad х Ф,
получим
ET(Ex-f) + CT\ = 0. (33)
Вводя вектор невязки г, отвечающий решению х:
r = Ex-f, ' (34)
перепишем (33) в виде
СГХ + Етг = 0. > (35)
207
Вместе с уравнением связи Сх ¦ d соотношения (34), (35) означают, что
вектор
и =
Г X г
L х J
является решением системы
¦ 0 0 С " ' d '
Ди = 0 -7 Е и = f
-Ст Ет 0 - - 0 -
= л.
(36)
Это решение единственно, если ker С Л ker Е = {0}. Заметим, что матрица В квадратная н в случае единственного решения будет не вырождена.
Будем считать, что С — матрица полного строчного ранга: rank С = т,. Наряду с задачей (32) рассмотрим задачу
min || Ex
F
/II, F = ix\Cx=d),
(37)
где? = ? + еЕЯЕ, С=С+есЯс, /=/ + е/Я/, d = d+edhd,\\HE\\ =¦ = НЯС|| = ЦЛ/И = \\hd\\ = 1; eE, ec, e/; ed > 0. Предполагаем, что
rank С = m,, и обе задачи (32), (37) имеют единственное решение: х н = х + соответственно. Построенный по х вектор и будет решением системы с матрицей В, аналогичной системе (36). Положим ""
0
Но = в - В =
о о
еснс
€сНс ~>
Малость возмущения будет определяться требованием \\В~1НВ || < 1. Введем обозначения:
кс(Е) = \\Е\\\\(ЕРс)*\\, РС=1-С*С, кЕ(С) = ||С|| || С/Е ||
(по поводу обозначения С) Е см. комментарий,к гл. 7), -
II С ||
и(Е,С) = ||?С/Е
II ?11'
Ре
Уе 208
|?|l II х II 11/11
Оценки Элдена [27*] имеют вид
II dx || < || (ЕРСУ ||2(ес || X || + еЕ || г || ) + + (eclic;>?|| + e?|| (?/»с)*||)||лс|| + + е</ Н С/ Е\\ +6,11 (?/>сЛ|+0(е2),
И«/*||
-<к.
^e{v(E, С)-^~ + —W
A IIсо IIяII/
+ к,
>(?)(— + —^?аЛ + МС)(— +——) + 0(е2). ' VIIII 11/11 */ Е '\ IIС|| ||d||/
Коэффициенты кс(?), кЕ(С) Элдеи назьшает числами обусловленности задачи (32). Он отмечает, что эти числа могут быть невелики даже при плохо обусловленной Е. Тем самым задача (32) может оказаться хорошо обусловленной, хотя соответствующая задача без ограничений m i п || Ex — /|| обусловлена плохо (разумеется, может быть и наоборот).
х
Поэтому вряд ли стоит начинать решение задачи (32) с преобразования матрицы Е. Тот же вывод, впрочем, содержится в более ранней работе J43 * ].
Анализ чувствительности решения задачи (32) к возмущениям исходных данных проводится и в [57 * ]; при этом применяются только обычные псевдообратные матрицы.
Представление (36) используется в [17*] для построения алгоритма итерационного уточнения решения задачи (32). Полагая и*0* = 0, можем описать процесс формулами (s = 0,1,... ):
а) v<^> = л -Ви^;
б) 6и<*> =B-»u(J);
в) и<1+,) =ы(,) +бы<*>. При s > 0 в векторе
r</w
L gis) J
подвектор g О не будет нулевым. Заменяя в векторе л нулевой подвек-тор вектором g, укажем, следуя [17], метод решения системы (36). При этом считаем, что rank С = m i икег СПker Е = {0}.
Предположим (переставляя в случае необходимости столбцы С), что в представлении С = [С,, : С\ 2] подматрица Ci i квадратная и невырожденная. Пусть Qt 1 - ортогональная матрица порядка т, такая, что в матрице
Си С = [Ri\ -Я\г] (38)
209
R11 верхняя треугольная. Разбивая Е янапо:
