Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
At =А, (15.33)
Ai+i=n(QtAi), /=1,...Д, (15.34)
где Qi — численное приближение к точной матрице^,, которая аннулирует элементы i + 1,..., m столбца / произведения QjAf. Определим матрицу погрешности
F, = QiAt-fl(Qt At)=QtAi-Ai+l, i = l,...,k. (15.35)
Из (15.30) следует оценка
IFf 1р<ат +,_,lAt lp + Otf), (15.36)
ey=(6/ + 37)tj. (ЩТ)
Из ортогональности матриц Qt прямой подстановкой выводится ,. j,
_ к
- Qk...QxA\F< Ъ am + 1_, li4,lF+0(tj2)<
<1Л|_,? <*т ¦ +0(т?2)<
Г i — i
<(6т -3*+4О)*17 + 0(172). (15.38)
Полезно ввести также другую матрицу погрешности Нк = (?, • •.
• • QkAk*i - А. Тогда
А~к + х =Qk ¦¦¦ QM +Нк) (15.39) и, согласно (15.38),
IIНк Iр < (6т - Зк + 40)*т» + 0(п*). (15.40)
5* 67
Равенство (15.39) и оценку (15.40) можно интерпретировать следующим образом: вычисленная матрица Ак + t есть точный результат ортогонального преобразования матрицы А + Нк, где IIНк Немала в сравнении с IIA
Заметим, что результат, выражаемый_соотношениями (15.39) и (15.40), не зависит от того факта, что матрицы Q, вычислялись с целью аннулировать некоторые элементы в At. Эти соотношения остаются зерными и в тех случаях, когда А (следовательно, и Ак + i) заменяется матрицей илн вектсь ром, не имеющими никакой специальной связи с матрицами Q/. J
Далее, если матрицы, вычисленные процессом (15.34), используютОр в обратном порядке и
У =fl(6, ...QkX), (15.41J где X - произвольная матрица, то
y = Qi ¦¦¦ Qk(X + K), (15.42 причем
IK \F<(6m-3k+40)kn IX Uf+0(tj2). (15.43)
Ортогональные матрицы Q, в (15.42) те же, что и в (15.39). Это замечание понадобится нам в доказательствах теорем 16.18, 16.36, 17.19 и-17.23.
Наконец, нам потребуются оценки погрешностей округления при нии треугольной системы уравнений. Пусть R - треугольная к X fc-матри а с - it-вектор. Тогда вычисленное решение х системы
Rx = c (15.44
будет удовлетворять равенству
(R+S)x=c, (15.451
где S - треугольная матрица той же конфигурации, что и R; при этом
115 »F<* ИД Ърг) + 0(г)2). (15.46)
Доказательство этого результата дано в [11]. В процессе вывода (15.46) в указанной книге показано заодно, что
\1„\<2я\гн\+0{яг), (15.47)
поэтому для разумных значений т; невырожденность R обеспечивает невьи рожденность R + S. Упражнение
15.48. Пусть G - матрица Гивенса, вычисленная алгоритмом G1 (см. 10.25) Щ точной арифметике, а С - соответствующая матрица, вычисленная в арифметикя с относительной точностью tj. Пусть z - произвольный машинно представимый 2-век1 тор. Вывести оценку вида
И fl(Cz) - Cz I < ст) lz I ' f
и определить значение константы е.
реша
триц|
68
глава 16
АНАЛИЗ ПОГРЕШНОСТЕЙ ОКРУГЛЕНИЙ ДЛЯ ЗАДАЧИ НК
В этой главе анализ погрешностей округления, проведенный в гл. 15, будет применен к выводу оценок для вычислительных погрешностей алгоритмов нз гл. 11, 13, 14. Эти алгоритмы осуществляют решение шести типов задачи НК, изображенных на рис. 1.1.
Мы предполагаем в этой главе, что вся арифметика выполняется с одной и той же точностью г). Вследствие этого оценки погрешностей будут содержать множители и2 и тп. Можно получить меньшие оценки, зависящие лишь от первой степени п и вовсе не зависящие от т, если использовать арифметику повышенной точности в некоторых критических "узлах" численного процесса. Теоремы этой главы будут переформулированы в гл. 17, для арифметики со смешанной точностью.
Теорема 16.1 (переопределенная задача наименьших квадратов полного ранга). Пусть А - тУ. п-матрица псевдоранга п,а b - некоторый m вектор. Если машинная арифметика имеет относительную точность г\, ах- решение задачи Ах^ьЬ, вычисленное посредством алгоритмов HFT (см. 11.4) и HS1 (см. 11.10) или HFTI (см. 14,.9), то х является точным решением задачи
(A+E)xasb+f, (16.2)
где
ll?'lF<(6m -Зи +41)ит) Ч1А11Р+0(г?1, (16.3)
ll/IK(6m -Зи+40)и17 Ш + 0(г)2). (16.4)
Доказательство. Математически процесс можно описать формулами
Q[A:b]=\n I, , (16.5)
Rx = c. (16.6)
Заменяя А в (1539) и (15.40) матрицей [А : Ь] из (16.5), заключаем, что существуют ортогональнаяматрица Q, матрица G и вектор / такие, что вычисленные величины R,c~ на" удовлетворяют равенству
¦и ;]¦
Q[A+G:b+f] =| л т |, (16.7) где
HGHF<(6m-3n+40),ii7 \А ЪР + 0(т?), (16.8)
И/И< (6т -Зи +40)иг/ Ш + 0(г)2). (16.9)
Вместо (16.6), машина определяет х иэ системы Rx = c~. Согласно (15.45) и (15.46), вычисленное решение х будет точно удовлетворять
69
равенству
(R + S) x = с, причем
\SlF< ит? \R\F +0(v2) = nV МП/г +0(t?J). (16.10)
Чтобы связать вычисленный вектор х с исходной задачей наименьших квадратов, определим окаймленную матрицу
rR+S с 0 1
Умножая ее слева на матрицу QT (Q - ортогональная матрица из (16.7)
получим
[*+с'4оМ-
Положим E=G+QT
Тогда х будет решением задачи (16.2). Из неравенства l?l<lGl + tSi и формул (16.8), (16.10) вытекают оценки (16.3) и (16.4). Это завершает доказательство теоремы 16.1.
Теорема 16.11 (квадратная невырожденная задача). Пусть А -п X п-матрица псевдоранга и, а Ь — некоторый п-вектор. Если машинная арифметика имеет относительную точность т},ах- решение задачи Ах-Ь, вычисленное посредством алгоритмов HFT {см. 11.4) и HS1 (см. 11.10) или HFTI (см. 14.9), то х является точным решением задачи
