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

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

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

Число 17 характеризует относительную точность машинной арифметики с плавающей запятой и нормализацией. Следуя Уилкинсону, мы используем обозначение
z = П(х+у)
для указания на то, что Г есть машинное число, полученное в результате машинной операции сложения машинных чисел хну. Если z = х + у, то даже при выполнении условий L <l z | < U часто оказывается, что Г - z Ф 0. Удобно называть эту разность погрешностью округления независимо от того, действительно ли округляет данная машина или же оно просто производит усечение *).
Число г) — это наименьшее положительное число с таким свойством: если точный результат z одной из пяти операций - сложить, вычесть, умножить, разделить, извлечь квадратный корень — равен нулю или удовлетворяет неравенствам L <| z | <(/, то найдутся числа et, ограниченные по абсолютной величине числом 17, для которых выполняется одно из следующих пяти уравнений:
А(дс+^) = дс(1+е,)+ Я1+е2)=+ (15.1)
1 + е3 1 + е4 !
(если* и у имеют одинаковые знаки, то et = ег и е2 = f*): i
fl(x->0=x(l+e5)-,Kl+e6) = -^--<15.J
1 +e7 1 +e8
*) В оригинале - truncation. (Примеч. пер.)
«4
(если* и у имеют противоположные знаки, то es = еб и еп = е8);
П(ху) = ху(1 + е9) = —^— ; (15.3)
1 +ею
<4;Hf>
1 + e,i)= ~т—"ч: <154>
х1/2
Я(х,/2) = х,/2(1 + е»з)=-- . (15.5)
1 + 6,4
Общий подход к анализу алгоритмов линейной алгебры на основе предположений этого типа хорошо отражен в литературе [7, 11, 23, 24, 190]. При этом использовались различные приемы, позволяющие учесть неизбежно возникающие члены второго и более высоких порядков по г\. Так как в оценках наиболее полезную информацию дает коэффициент при % то только он и будет определяться в последующем анализе.
Вследствие группировки членов порядка г)2 в единое слагаемое 0(rj2) "оценки", которые будут получены в гл. 15—17, не являются вполне вычислимыми. Однако для значений % соответствующих реальным машинам, этим слагаемым можно пренебречь. Так как повсюду в анализе предполагается максимальное накопление погрешностей, то выводимые нами оценки существенно превышают реальные погрешности. Основное практическое назначение этих оценок - показать зависимость погрешностей от параметров т, и, г? и установить численную устойчивость алгоритмов нз гл. 11, 13, 14.
Вначале мы проанализируем погрешности округлений в алгоритме HI (см. 10.22). Будем считать, что алгоритм строит т X /и-преобразование Хаусхолдера, которое аннулирует все элементы данного m-вектора v, кроме первого. Математически алгоритм определяется следующими формулами:
и = max | v/1, (15.6)
i
",!,(7)'; <'">
s =-(sgnUl)fl>V (15.8)
"i=ui-s, (15.9)
«, = u,, j=2.....m, (15.10)
* = su,, (15.11)
Q = I,„ + b-luuT. (15.12)
В алгоритм включено масштабирование, имеющее целью избежать машинных нулей. Условимся черточкой сверху отмечать величины, являющиеся машинными числами или составленные из таких чисел. Величины, реально
5 Ч. Лоусон 65
вычисленные алгоритмом, можно представить формулами
ц = max | о, |, (15.13|
r4?,(f)1* (15Л«
s = -fl[(sgn(y,)XO,/2*i], (15.15)
u = fl(v, -J), (15.16)
u, = Vi, /' = 2, ...,m, (15.17)
?=fl(7u,), (15.18)
б = fl(/m+ *>"№). (15.19)
Вычисленные величины, выражаемые формулами (15.14)—(15.19), связаны с одноименными точными величинами из формул (15.7)-(15.12) следующим образом:
г = г(1 +т), |г|<(т+2)т> + 0(т>2), (15.20)
(т + 6)17 T = s(l + o), |о|<--— +0(т?2), 2 (15.21)
(m + 8)17 17, =и,(1+к), | к |< --— +0(tj2), 2 (15.22)
"/ = и,, i = 2,... ,m, (15.23)
F = ft(l+0), IUI<(m + 8)Tj + 0(T72), (15.24)
Jfl-C lF<4* + 2|J + 0(i72)<(4m + 32)т?+0(i72). (15.25)
Мы опускаем громоздкий вывод этих оценок, поскольку он очень схож
с выводом оценок книги [7]. Заметим, однако, что наши оценки отличаются от оценок Уилкинсона. Главная причина различия следующая: мы предполагаем, что вся арифметика выполняется с точностью 17, а Уилкинсон считает, что некоторые операции выполняются с точностью 172. Мы отложим обсуждение такой арифметики со смешанной точностью до гл. 17.
Сейчас мы рассмотрим применение преобразования Хаусхолдера к, т X n-матрице С посредством алгоритма Н2 или второй (необязательной! части алгоритма HI (см. 10.22). С математической точки зрения нужн<| вычислить произведение
B=QC. (15.26)
При реальных вычислениях, однако, мы имеем лишь Q~ вместо Q, поэтому будет вычислена матрица
B = fl(QC), (15.27)
lB-BiF=Hn(QC)-QC] +(QC-QC) ИF<
<ifl(5c)-eciF + ifi-eiFiciFs
= I?IF+Ifi-QIFICIF. (15.28)
M
Подобно тому как это сделано в книге [7], можно показать, что
НЕ lF<(2m +5) IС tFv + Oft2). (15.29)
Теперь из (15.25), (15.28) и (15.29) получаем
IB-BIF <(6m+37) iCl^tj + Ofo2). (15.30)
Мы должны теперь исследовать погрешность, связанную с применением к тХ n-матрице А к последовательных преобразований Хаусхолдера. Точный математический процесс описывается формулами
At=A, (15.31)
A, + i=QiAi, i = l.....к, (15.32)
Л
где матрица Хаусхолдера Qi аннулирует элементы i + 1,..., т столбца i матрицы QiAt. Эта последовательность умножений лежит И основе различных алгоритмов, которые мы рассматриваем. - >. ^ Будут вычислены величины
Предыдущая << 1 .. 18 19 20 21 22 23 < 24 > 25 26 27 28 29 30 .. 88 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed