Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Доказательство. Математическое описание алгоритма дано формулами (14.1) —(14.6). Напомним, что матрица Q в (14.1) является произведением п преобразований Хаусхолдера: Q-Qn ¦ Qi- Заметим, что матрицы Ru и Лц из (14.1) и вектор Ci из (14.2) полностью определяются первыми к нз этих преобразований. Пусть
(A +f) X5<b+f,
(16.37)
причем
IEIF < Ы22 lF +(6m + 6и - 6к - Зц + 84) ЦП 1л\р +0(я*),
/u = min(m, и),
1/1<(6/и -Зк +40)*г/ Ш + 0(г/а), Их -х11<(6и-6к+43)*17 ПхП + 0(172).
(16.38) (16.39) (16.40)
Тогда
(16.41)
(16.42)
(16.43)
причем
S % F — Н R22 di= lc2ll.
22 "/Ti
(16.44) (16.45)
73
Вместо (16.42) вычисленные матрицы R ц, R i2, 5 удовлетворяют соотношению
1о 5"} il6MJ
Q{A + G)P =
Согласно результатам гл. 15, ? — точно ортогональная матрица н
iGlF<( I am+I_,)МlF+0(t}2), (16.47)
/= i
H5iF< I am+,_/)l/l»/r+0(t?2).
/ = * + i
Величина ay определяется формулой (15.37); /u = min(m, и), как н в гл. 14, а/?2 2 обозначает вычисленную матрицу, соответствующую R22 в (14.1). ^
Из (16.46) можно вывести формулу
То О J'
(2(Л+#)Р=| |, (16.48)
где _м
1Я1К< 151,. + IGIF< 1ЛИ 1/г + ( 2 am+i_,) M»F+0(172)<
< 1Л» И/г + (6т - З/i +40)дл7 U \р + 0(т?2). (16.49)
Вместо (14.3) вычисленная матрица IV удовлетворяет равенству ([Л„ :Л12] +М)к= [W: 0], (16.50)
Л
где /С - ортогональная матрица.
Оценка для \\M4F несколько отличается от оценки (15.40). Дело в том, что каждое из к преобразований Хаусхолдера, чье произведение образует матрицу К, отличается от единичной матрицы только п - к + I столбцами. Поэтому
IAflF< «„-^.ЛтгНЛ,, :R12]tF+0(r}2) =
= (6M-6jfc+43)Jfct? iAlF+0(n2). (16.51)
где а/ определены формулой (15.37). _
Вместо (16.43) вычисленные векторы сi и d удовлетворяют соотношению
Q(b + /) =1 V I, (16.52)
где Q - та же матрица, что и в (16.46), а
1/1 < (6т - Зк+ 40) *tjH ft II + 0(т)2); (16i3)
это и есть оценка (16.39) теоремы 16.36.
74
Что касается (14.4), то вычисленный вектор .у, будет решением системы
(W + Z)yl=cl (16.54)
с невырожденной матрицей W + Z; при этом •
BZBF< *г/ BJPBF+0(r)2)< кг) \AlF +0(712). (16.55)
В (14.5) мы рассмотрим только случай у2 = 0. Вмело (14.6) вычисленный вектор х удовлетворяет равенству
-'ft]
+ й, (16.56)
где * j
Irtl<(6n-6fc + 43)fci7 Ij,ItC>(t}2). Я1 (16.57)
Оценка (16.57) выводится таким же образом, как и (16.51).Положим
5=/>^[о J (1658)
Тогда из (16.56)-(16.58) следует -¦' ^
¦ Зс -*В<(6и-6к +43)*г/ Вх И + 0(т}2), (16.59)
т.е. оценка (16.40).
Аналогично доказательству теоремы 16.18 из (16.54), (1638) выводится, что х есть нормальное решение задачи
[W + Z : 0] КтРтх = Сх. (16.60)
Согласно (16.50) (
[W + Z : 0] Кт= [Rn :R12] + X, (16.61)
где
Х = М + [Z : 0] Кт; „.,.„(16.62) при этом из (16.51) и (16.55) следует
\X\F< \M\F + ВZIIF<(6w-6fc+ 44)Attj ВЛBF +0(г)2). (16.63)
Подставляя (16.61) в (16.60) и окаймляя систему дополнительными строками, видим, что х является нормальным псевдорешением задачи
i: :н:])'- а
(16.64)
Умножая (16.64) слева на Q и используя (16.46), заключаем, что х есть нормальное псевдорешение задачи (16.37), где
(16.65) 75
Следовательно,
\\E\\F<\\H\\F+ 11^11^..
(16.66)
Из (16.49) и (16.63), где к для простоты заменено числом ц(ц> к), тин лучаем окончательное выражение
Вместе с (16.53) и (16.59) оно доказывает теорему 16.36. ГЛАВА 17
АНАЛИЗ ПОГРЕШНОСТЕЙ ОКРУГЛЕНИЙ ДЛЯ ЗАДАЧИ НК . В АРИФМЕТИКЕ СО СМЕШАННОЙ ТОЧНОСТЬЮ
В анализе погрешностей округлений мы предполагали до сих пор, что вся арифметика выполняется с одной и той же точностью, характеризуемой параметром т). Если в данной вычислительной машине эффективно реализована арифметика повышенной точности (характеризуемая параметром со, oj<tj) и имеются эффективные машинные команды для перевода чисел из одной разрядности в другую, то можно использовать эту повышенную точность в отдельных узлах численного процесса. Это позволяет улучшить точность результатов с очень малыми издержками по времени и, по существу, без дополнительных требований к памяти.
Если не решено перейти полностью с т/-точности на cj-точность, то обычно использование арифметики с со-точностью ограничивают теми частями алгоритма, где требуется лишь небольшое фиксированное (т.е. не зависящее от размерностей задачи тип) число ячеек с со-разрядностью.
Уилкинсон провел подробный анализ погрешностей округлений для алгоритмов линейной алгебры в случае конкретного варианта арифметики со смешанной точностью, а именно cj = 172 (см. [7]). Мы воспользуемся сходными методами, чтобы вывести для алгоритмов, уже проанализированных в предыдущей главе, оценки в той же специальной арифметике со смешанной точностью.
При вычислении преобразования Хаусхолдера мы модифицируем процесс (15.13) — (15.19) следующим образом. Вычисления по формуле (15.14) будут выполняться в арифметике с со-точностью, а конечный результат будет представлен так, что Т - число 17-разрядности. Выражения для по-грешностейв (15.20) —(15.25) примут вид
+ (6те +6н -6к - Ъц + 84)^77 \\А \\F +0(rf).
(16.67),
7 = г(1+т), |r|<r? +0(т?2), T = s(l +о), |о|< 517/2 +«9(i72), ^ й,=и,(1+к), |к| < 717/2 + 0(тг»Х', Ь=Ь(1+р), I0l< 7Tf + 0(r?2), Иб-б»/г< 28т>+0(т?2).
