Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Пауэлл и Рид получили удовлетворительные результаты для таких задач, когда дополнили алгоритм стратегией перестановок строк; она будет описана перед формулировкой теоремы 17.37.
Ниже будут сформулированы три теоремы [146], которые позволяют понять поведение алгоритма Хаусхолдера для задач с сильно различающимися весами.
Будет удобно считать, что столбцы А упорядочены заранее, так что при выполнении алгоритма HFTI перестановок столбцов не происходит. Положим [А<1> : Б"*1)] = [А:Ь], и пусть [А<1+1> :b(i+V] обозначает вычисленный результат применения /-го преобразования Хаусхолдера
к матрице [AW :b ('>], /= 1.....и.
Введем обозначение
• *
T^maxlajL**!, /=1,...,т, > »; (17.28)
где а^р - элемент (/, /) матрицы А^кК
Пусть q(k) — точная Ортогональная матрица Хаусхолдера, определяемая условием, чтобы элементы в позициях (/,*), i = Jfc + 1, ..., m, матричного произведения q<*М С*) были нулями.
Теорема 17.29 [146]. Пусть А - т X п-матрица псевдоранга п. Пусть используется арифметика со смешанной точностью, характеризуемая параметрами т? и со< г/2, и пусть А приведена к верхней треугольной mXn-матрице Л"(л+,) посредством алгоритма HFTI (см. 14.9). Toida
Л"("+1> =qW ...q«'(a +?), (17.30)
причем элементы etj матрицы Еудовлетворяют оценкам
|е//|<(20и2 - 17п + 44)-у,.г} + 0(172). "(17.31)
79
Чтобы сформулировать теорему 17.32, нам потребуются дополнительные определения, учитывающие то обстоятельство, что правая часть Ъ не может участвовать в перестановках столбцов:
А1/ = тах |*/к)|, 1 = 1.....т,
т т
i = к i- к
p = ггаХ[max—, max -J.
\ ' 7i * ok J
Отметим, что из наших предположений об априорном упорядочении
столбцов А следует
т
ок= max ( Z [а^]2)Ч2, к=\,...,п.
к < j < п 1 = к '
Теорема 17.32 [146]. Пусть А - тХ п-штрица псевдоранга п,а b -некоторый m-вектор. Пусть используется арифметика со смешанной точностью, характеризуемая параметрами т? и cj< 172, и пусть х - решение задачи Ах^Ь, вычисленное посредством алгоритма HFTI (см. 14.9). Тогда х является решением задачи
(A+E)x~b+f, , (17.33)
причем выполняются следующие оценки дЛЯ мемеыТОв ец матрицы Е
и элементов /, вектора /:
\ец\<(20п2 - 15и +44)7,17 + 0(г?2), (17.34)
|/}|<(20и2 +20и+44)р7,т)+О(172). (17.35)
Используя неравенство \ец\ <ИЕ11/г,из (17.13) можно вывести
\ev\< ЗОи 11/411^17+О(172). (17.36)
Сравнивая неравенства (17.34) и (17.36), видим, что оценка (17.34) будет наиболее полезна в тех случаях, когда 7,- существенно меньше, чем IIЛ Аналогичные замечания справедливы в отношении оценок (17.14) и (17.35).
Напомним, что у, обозначает величину наибольшего элемента в /-х строках всех матриц А^1\ Л(п+|). Поэтому, чтобы 7,- была мала (относительно MIIF), нужно, чтобы были малы элементы в i-й строке исходной матрицы А О =А и чтобы элементы z'-x строк последующих матриц Л не возрастали сколько-нибудь значительно.
Пауэлл и Рид привели пример, показывающий, что если не накладывать ограничений на упорядочение строк А, то рост поначалу малых элементов в некоторых строках может быть очень большим. Они рекомендуют следующую стратегию перестановок строк. Предположим, что перед выполнением k-то преобразования Хаусхолдера ведущий столбец выбран и переведен в к-й столбец'хранящего массива. Определим строчный индекс / такой, что
|д/л|=тах{|д,*|: *< /< т).
80
Переставим строки / и к. Теперь к-е преобразование Хаусхолдера строится и применяется обычным образом. Этот процесс выполняется для * = 1.....и-
Теорема 17.37 [146]. Если используется только что описанная стратегия перестановок столбцов и строк, то величины у,, определенные в (П.28) удовлетворяют оценке
для 1 < / < m.
Пауэлл и Рид сообщают, что, применяя эту комбинированную стратегию перестановок столбцов и строк, они получили удовлетворительные решения для некоторых задач с сильно различающимися весами. Для тех же задач результаты были неудовлетворительны, когда допускалось использование строк с малыми элементами в качестве ведущих строк.
ГЛАВА 18
ВЫЧИСЛЕНИЕ СИНГУЛЯРНОГО РАЗЛОЖЕНИЯ И РЕШЕНИЕ ЗАДАЧИ НК
§ 1. Введение
Сингулярное разложение матрицы было темой основополагающей работы [73]. В этой работе содержалась библиография, относящаяся к приложениям и алгоритмам, и была начата разработка нового метода, законченная в основном публикацией [34]. В книге [8] помещена усовершенствованная версия этого метода. Она представляет собой специальную адаптацию QR-алгоритма [59] для вычисления собственных значений и собственных векторов симметричной матрицы.
В этой главе будут описаны -алгоритм для симметричных матриц и (несколько модифицированный) алгоритм Голуба и Райнша для вычисления сингулярного разложения
Будет разобран также вопрос об использовании сингулярного разложения для анализа и решения задачи НК.
Чтобы не менять обозначений, а также потому, что применение сингулярного анализа в этом случае наиболее вероятно, мы предполагаем на протяжении всей главы, что тп > п. Случай ш<п можно свести к предыдущему, приписывая п - тп нулевых строк к матрице А или в случае задачи НК к расширенной матрице коэффициентов [А : Ь). Машинная программа может выполнять окаймление нулями неявно, так что не потребуется реального хранения нулевых строк или арифметических операций с нулевыми элементами.
