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

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

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

(A+E)x=b+f, (16.12)
где
|?В/Г<(3и2 +41л)т? Mljr+Ofr3), (16.13)
ll/ll<(3«2 +40и)17 1Ш + 0(Т72). (16.14)
Эта теорема - просто специальный случай теоремы 16.1, так что оценки (16.13) и (16.14) получаются при п-т из оценок (16.3) и (16.4). Мы сформулировали теорему 16.11 как отдельное утверждение, поскольку квадратный невырожденный случай часто представляет самостоятельный интерес.
Поучительно сравнить теорему 16.11 с аналогичной теоремой о погреш-> ностях для гауссова исключения с выбором главного элемента [11]. В по следнем случае выполняется неравенство
H?IL< 1,01(и3 +3и2) Ш.чр,,. (16.15)
Здесь символ 11 • 1„ обозначает норму (максимальную строчную сумму) определяемую для произвольной т X и-матрицы В формулой
Ш„ =max{ Z |*«|:1</<т}. /-1
70
Величина р„ является мерой относительного роста элементов в ходе гауссова исключения [11]. Если производится частичный выбор главного элемента, то имеет место оценка
р„< 2"-'. (16.16)
Если используется полный выбор главного элемента, то
р„< l,8,i(togn>/4. (16.17)
Обычные реализации гауссова исключения опираются на стратегию частичного выбора. Поэтому оценка (16.15) для нормы матрицы ? растет экспоненциально с ростом п.
При использовании алгоритмов Хаусхолдера, например алгоритма HFTI (см. 14.9), ситуация значительно более удовлетворительная и надежная. В этом случае в оценке (16.13) вообще нет коэффициента роста р„. В [7] также отмечается этот факт, но указывается на то, что в алгоритме Хаусхолдера требуется примерно вдвое больше операций, чем в гауссовом исключении с частичным выбором. Кроме того, величину р„ легко вычислить в гауссовом алгоритме, и, согласно утверждению Уилкинсона, на практике она редко превышает 4, 8 или 16. Аналогичные замечания справедливы в отношении теоремы 17.15, где в некоторых узлах алгоритма Хаусхолдера используется повышенная точность.
В теоремах 16.1 и 16.11 было показано, что вычисленное решение является точным решением возмущенной задачи. В отличие от этого теоремы 16.18 и 16.36 утверждают, что вычисленное решение близко к нормальному решению возмущенной задачи. Эта более сложная формулировка связана с тем, что теоремы 16.18 и 16.36 относятся к задачам, решения которых были бы неединственны без требования минимальности длины.
Теорема 16.18 (нормальное решение переопределенной задачи полного ранга). Пусть А - mXп-матрица псевдоранга m,a b — некоторый тп-вектор. Если машинная арифметика имеет относительную точность щ, ах— решение задачи Ах = Ь, вычисленное посредством алгоритмов НВТ (см. 13.8) и HS2 (см. 13.9), то х близко к точному решению возмущенной задачи в следующем смысле: существуют матрица Е и вектор х такие, что х есть нормальное решение задачи
(А+Е)х = Ь, (16.19)
причем
Ш/г<(6и-Зт+41)тг/ \А iF + 0(г)2), (16.20)
Их -xl< (6и -Зт +40)mrj Ixl + 0(г/2). (16.21)
Доказательство. Краткая математическая формулировка алгоритма гл. 13 такова:
AQ= [R :0], > (16.22)
Ry = b, * (16.23)
(16.24) 71
Вместо (16.22) вычисленная нижняя треугольная матрица R будете удовлетворять соотношению
(А + G) Q = [R : 0], (16.25)
где Qортогональная и, согласно (15.40),
«G«F<(6« -Ът +40),ит7 \А\F + 0(г?2). (16.26)
Далее из (15.45) и (15.46) следует, что вместо (16.23) вычисленный вектор у будет точным решением системы
(R + S) у = Ь, (16.27)
причем
Ш< дат? ВЛ llF +0(172) = ,И17 Ы lF + 0(т?2). - (16.28)
Вместо (16.24) вычисленный вектор * о предедяетс* формулой
* = С +Л , (16.29>
в которой, согласно (15.41)-(15.43),
Ш<(6н - Зт +40)гит) lljll + 0(tj2). (16.30У
Ортогональная матрица Q в (16.29) та же, что и в (16.25), как указана в замечаниях, сопровождающих формулы (15.41) — (15.43). Переписывая (16.27) в виде
[R +5 : 0] | ^ \ = Ь, (16.31)
затем в виде
...
[R +S О] QTQ j = ft (16.32)
и,наконец, используя (16.25) и (16.29), получаем
U +G+ [S :0] QT) (x-Qh) =Ь. (16.33)
Положим
? = G+ [5 :0] QT, (16.34)
x = x-Qh = Q I Q j • (16.35)
Исходя из неравенств (15.47), можно предполагать матрицу R +S в (16.32) невырожденной. Поэтому пространство строк матрицы А+Е = = [R + S : 0] QT совпадает с оболочкой первых т столбцов матрицы Q.
Согласно (16.33)-(16.35), х удовлетворяет уравнению (16.19); в то же время (16.35) показывает, что х принадлежит оболочке первых т столбцов Q. Тем самым х является единственным нормальным решением (16.19).
72
л
для матрицы Е и вектора х — х справедливы оценки lElF< lGlF + lSlF<
< (6n-3m+41),и17 lAlF+0(rt2),
Их — icВ = Ш< (6и -3m + 40) mi? I Jl + 0(1?*) =
= (6и -3m +40)/ит? ВЗё1+0(172),
которые совпадают соответственно с (16.20) н (16.21). Теорема 16.18 доказана.
Теорема 16.36 (задача НК неполного ранга). Пусть А - m X п-матрица, b — m-вектор. Пусть машинная арифметика имеет относительную точность г) и х - решение задачи Ах^ Ъ, вычисленное посредством алгоритма HFTI (см. 14.9). Пусть к - значение псевдоранга, определенное алгоритмом, a R 22— вычисленная матрица, соответствующая матрице R22 из (14.1). Тогда х близко к точному решению возмущенной задачи в следующем смысле: существуют матрица Е и векторы f их такие, что х является нормальным псевдорешением задачи
Предыдущая << 1 .. 20 21 22 23 24 25 < 26 > 27 28 29 30 31 32 .. 88 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed