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

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

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

RTRS = ATh, откуда
||6 || ? к\А)\\г\\ п/М ||,
т.е. практически то же самое, что ив (19).
Итак, для сильно несовместных систем описанные выше приемы итерационного уточнения работают неудовлетворительно. В работах Бьорка [14*, 17*] развит другой подход, использующий эквивалентность задачи Ах а Ь и системы линейных уравнений
где г = b - Ах - оптимальная невязка. Матрица В системы (21) квадратная, а если rank А - п, что в дальнейшем предполагается, то и невырожденная. Поэтому к (21) применим обычный процесс итерационного уточнения. Приводим его описание, следуя [14*].
Полагаем г*0* 88 0, х*°* = 0. Итерация с номером s состоит из трех шагов:
1. Вычислить невязки
сип-ига
На этом шаге операции проводятся с удвоенной точностью.
202
2. Определить поправки Ьг (*), Ьх (*), решая систему
L оГЫчН- " (23)
3. Найти новые приближения г(*+1) «• г(,) + 5г(*\ = xw +6дс(,). Процедура Голуба получается, если в этом описании положить Л1* =0
для всех s. Это означает, что в случае совместной системы асимптотическое поведение методов должно быть одинаковым, и также отчасти объясняет, почему при больших невязках процесс Голуба дает неудовлетворительные результаты.
Как решать систему (23)? Заметим, что при s = 0 из формулы (22) следует, что /(0) = Ь, ?(0) = 0, а тогда (23) превращается в (21). Таким образом, первая итерация есть попросту первоначальное решение исходной задачи Ах ^ Ь. Предположим, что для этого (методом HFT или модифицированным методом Грама - Шмидта (MGS) из гл. 19) вычислено ортогонально-треугольное разложение А (мы рассматриваем пока случай точных вычислений):
-IT •
L 0 Л)т-п
QA=\ |^ . (24)
Опуская в (23) верхний индекс, подставим в оба соотношения системы формулу (24), а затем умножим первое из них слева на Q. Тогда получим
Qbr + to ]** = Qft (25)
[RT : 0] Qbr = g. (26)
Представим вектор d = Qf в i
Ld2 J} m - и
Из (26) следует, что верхние п компонент m-вектора Qbr образуют вектор» я = (RT)'lg, а из (25) видно, что нижние т — п компонент Qbr составляв ют вектор d 2. Значит,
br = Q
Вектор Ьх определяем, приравнивая верхние компоненты в соотношении (25) :
6х=/*-»(<*, - я).
Итак, решение системы (23) требует: 1) вычисления вектора d^ = -Qf^\ 2) решения треугольной системы RTh^ =g^\ 3) вычисления
14* 203
вектора
4) решения треугольной системы R5x<s) = d? - я(,). Для каждого из этих действий достаточно 0(тп) или 0(п2) операций, что значительно меньше стоимости ортогонально-треугольного разложения А. Это же можно сказать об итерации процесса (шаги 1) -3)) в целом.
В первой части работы [14*] проведен очень тщательный анализ описанной процедуры итерационного уточнения для двух способов ортогонально-треугольного разложения: метода отражений и метода MGS. Главный вывод этого анализа: для не слишком плохо обусловленных задач процесс сходится в обоих случаях; сходимость линейная, и ее замедление при ухудшении обусловленности А пропорционально первой степени числа обусловленности. Это утверждение имеет место независимо от того, мала или нет оптимальная невязка. Для величины lim ( И х — II/ В х II)
J —? во
можно дать верхнюю оценку, в которой главным членом является произведение
f(m,n)K2 ir Ht}2/( IIА Их В).
По сравнению с (19), (20) здесь прибавился множитель п. Поэтому, если выполнено (20), то процесс Бьорка приводит к результату, мало отличающемуся от округленного вектора х. Для случая, когда ортогонально-треугольное разложение вычисляется методом отражений, алгольная программа процесса дана в [17*].
При решении больших разреженных задач стараются избежать хранения ортогонального сомножителя в разложении матрицы А. Две модификации процесса Бьорка для таких задач описаны в [33*, 29*]. В первой из этих работ выводится следствие из (23), позволяющее вычислять 5х^\ не используя Q. Именно
Адх^ = /<*> - 6/•<*>, (27)
откуда, умножая обе части на АТ и используя равенство Атд№ = получаем
ATA8x^=ATf^ -gW.
Но A A = R R, поэтому окончательно находим ¦ -
RTRdx(s) = ATfW-gM. { (28)
Вычислив дх^ (т.е., согласно (28), построив проиеведвИИвЛ7/"^ И решив две треугольные системы), найдем 6г^ из (27) :
5rU)=fW-A6x(t\
Шаги 1, 3 те же, что в методе Бьорка.
В качестве начального приближения этого процесса можно брать пару (х*°) ,г*0)), где х*°* - приближенное решение, вычисленное методом отражений; г*0) - отвечающая ему невязка. Но, как отмечено в [15*],
204
можно взять ихк ' =гк > = 0. В этом случае Q не используется даже для формирования начального приближения, что является достоинством при необходимости решать серию задач с одной и той же матрицей А и разными правыми частями.
В [15*] показано, что скорость сходимости этой модификации по-прежнему (как и в методе Бьорка) зависит от первой степени числа обусловленности А. Иначе обстоит дело во второй модификации [29 *], где в качестве матрицы R в (28) предлагается брать вычисленный методом Холесского треугольный множитель матрицы АТА. Здесь (см. [15*]) с ростом числа обусловленности к скорость сходимости падает пропорционально к2.
Предыдущая << 1 .. 69 70 71 72 73 74 < 75 > 76 77 78 79 80 81 .. 88 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed