Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
Удаление вектора. Снова предположим, что &к определяет текущий базис. Пусть из базиса нужно удалить столбец р/, 1 </' < к. Для / =/ + 1,'..., к построим вращение Гивенса Gt, оперирующее со строками /'- 1 и / и аннулирующее элемент W в позиции (/, pt). Умножим на G( слева весь массив W.
Образуем новое индексное множество &к-1» полагая Pi: =р,, /' = 1,... ...,/'- 1, кр(: =Pt+\, »=/',..., к - 1. В этом методе требуется лишь т X (и+ 1) -массив W, содержащий поначалу исходные данные [/1:6]. Если на последующих этапах вычислений потребуются копии этих данных, то для их хранения должен быть выделен дополнительный массив.
ГЛАВА 25
ПРАКТИЧЕСКИЙ АНАЛИЗ ЗАДАЧ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ
§ 1. Общие соображения
В этой главе мы обсудим стратегию планирования и интерпретации при практическом решении задач метода наименьших квадратов. Мы будем рассматривать случай т>п, который является центральным для нашей книги.
Пользователь, от которого исходит задача наименьших квадратов (именуемый в дальнейшем хозяином задачи), должен обзавестись начальными
*>См. примечание на стр. 134 (Примеч. пер.)
137
данными и построить или выбрать математическую модель, а часто также и модель статистическую. В какой-то момент своей работы он достигает этапа, когда у него имеются матрица А и вектор Ь, и нужно найти вектор х, который минимизировал бы евклидову норму вектора невязки
г = Ъ-Ах. (25.1)
Хозяин задачи должен еще иметь информацию о неопределенности в задании коэффициентов матрицы А и вектора Ь. Зачастую у него есть и априорная информация относительно решения задачи. Она может состоять в примерном предварительном знании области разумных значений для некоторых или всех компонент решения. Другой возможный вариант предварительной информации - требование, чтобы все или часть компонент были неотрицательны.
С очень общей точки зрения имеются два главных соображения, которые нужно учитывать при численном решении задачи. Важно разделить их.
1. Вычислительная погрешность может быть снижена до уровня, когда она является пренебрежимо малой в сравнении с неопределенностью решения, вызванной неопределенностью во входных данных задачи.
2. Комбинированный эффект априорной неопределенности в А и Ь и обусловленности матрицы А может привести к ситуации, когда имеется ряд существенно различающихся векторов х, которые дают для нормы невязки г приемлемо малое значение. Мы обсудим приемы, позволяющие обнаружить такую ситуацию, и некоторые методы управления выбором конкретного решения из множества решений-кандидатов.
Остановимся более подробно на соображении 1. Предположим, что имеющаяся информация о неопределенности в А и Ъ может быть выражена следующим утверждением. Известны числа ч> и ф такие, что всякая матрица вида А +Е, где
В?В ' 1 . (25.2)
и всякий вектор вида b + db, где
idbi< ф, (25.3)
приемлемы для хозяина задачи в качестве замены наличных входных данных А иЬ.
Для сопоставления с этими параметрами ч> и ф неустранимой погрешности введем, пользуясь оценками (16.3) и (16.4), следующие две функции от п:
^'(Т7) = (6т-3л+41)л3/2 Min, (25.4)
uV(i?) = (6т - Зл + 40) п IЬВ п. (25.5)
Мы заменили в (16.3) величину $AiF ее верхней оценкой л1'2 1А В.
Игнорируя в (16.3) и (16.4) члены 0(г?2), мы извлекаем из теоремы 16.1 такой вывод: если п выбрано настолько малым, чтобы
*'(Ч)<* . ~ (25-6)
*'(Ч)<*, (25.7)
то решение, вычисленное в арифметику с {КОДЯНВОЙ точиостью г?, явля-
138
я
ется точным для некоторой задачи, исходные данные которой отличаются от заданных А и Ь возмущениями, удовлетворяющими оценкам (25.2) и (25.3).
Аналогично в случае вычислений со смешанной точностью для выбора rj и cj(<t}2) мы можем с помощью (17.13) и (17.14) определить функции
/(Ч)-30п*аШч, Хч (25.8)
*"(Ч)-29и Ifclrj. _ , ',iJR (25.9)
Возьмем т? такое, чтобы
/(Ч)<Л ¦< - ¦ (25.10)
*"(т?)<*. ' " - (25.11)
При этом выборе 17 и cj< г?1 мы заключаем по теореме 17.11, что вычисленное решение является точным для возмущенной задачи, причем возмущения будут меньше, чем априорная неопределенность, описываемая оценками (25.2) и (25.3).
Напомним, что множители перед произведениями И А И 17 и II6II т? в формулах (25.4), (25.5), (25.8) и (25.9) были получены в предположении о наихудшем накоплении погрешностей округлений. Как показывает практика, замена этих множителей квадратными корнями из них дает обычно более реалистическое представление о величине возмущений, эквивалентных вычислительным погрешностям.
Перейдем теперь к соображению 2. Полезно формализовать понятие "приемлемо малого" вектора невязки. Предположим, что мы готовы принять невязки с нормами, не превосходящими некоторого числа р. Тогда можно определить множество приемлемых решений так:
Х = {х: ЦА + Е)х-(b+db)1l<p, Ш<<а 1</ДК<Н. (25.12)
Важно отметить, что определение множества X опирается на три допуска Я>, Ф и р, которые следует выбирать, исходя из имеющейся информации о задаче и ее входных данных.
Формулируя (25.12), мы ставим своей целью не столько утвердить именно это определение, сколько придать некоторую степень конкретности общей идее множества приемлемых решений, а также указать величины, от которых зависит "размер" этого множества.
