Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
ГЛАВА 13
ВЫЧИСЛЕНИЕ РЕШЕНИЯ НЕДООПРЕДЕЛЕННОЙ ЗАДАЧИ ПОЛНОГО РАНГА
Рассмотрим теперь задачу НК Ах = Ь, где m < и, rank А = m (случай За на рис. 1.1). Алгоритм ее решения может быть разбит на следующие шаги:
Av/^SjUf, откуда
(12.20)
IIA vt II = Sj.
(12.21)
AQ= [R. 0];
^2 - произвольный в tump;
(13.1) (13.2) (13.3)
(13.4)
57
Алгоритм вычислит ортогональную матрицу Q из (13.1), при этом R будет невырожденной нижней треугольной матрицей. Существование обеих матриц было установлено путем транспонирования основного разложения теоремы 3.11.
В (13.2) m-вектор yt определен однозначно. При любом и - т-векторе Уг (см. (13.3)) вектор х из (13.4) удовлетворяет уравнению Ах = Ь. Решение минимальной длины (нормальное решение) получается в соответствии с теоремой 2.3 приу2 = 0.
Существуют ситуации, когда недоопределенная задача Ах = Ь является частью большей оптимизационной задачи: при этом у2 оказывается ненулевым вектором. Такова, в частности, задача минимизации \Ex — f\ при наличии дополнительных линейных ограничений Ах - Ь (которые не определяют х однозначно). Эта задача, которую мы называем НКУ *), будет рассмотрена в гл. 20-22.
Матрица Q из (13.1) строится как произведение
6 = 0» -Qm, (13.5)
где каждая Q/ имеет вид
Qt = IH+b-,luMu<nt, /=1.....т. (13.6)
Величина Ь/, участвующая в (13.6), перевычисляется всякий раз, как она
нужна, по формуле (10.10). Вводя индексы, можем написать
б/^/и)0, /=1,...,т. (13.7)
Каждая величина х/ - это /-й диагональный элемент матрицы R и будет храниться как таковой. Описываемый алгоритм будем называть НВТ (m,n,A,g). Входная информация алгоритма НВТ состоит из целых чисел т и и и т X п-матрицы А ранга т. На выходе будет получена нижняя треугольная матрица R, хранимая в нижней треугольной части массива с именем А. Величины будут находиться во вспомогательном массиве переменных с именами g,J = 1,... ,т. Остальные ненулевые компоненты
вектора и * хранятся в наддиагональной части /-й строки массива А. Алгоритм 13.8. НВТ (т, n, A, g):
1. Для /: = 1.....т выполнить алгоритм HI (/, / + 1, и, д;-, ,gj,aj+l 1(
m-j) (см. (10.22)).
2. Комментарий. Приведение к (нижнему) треугольному виду закончено.
По поводу шага 1 следует отметить, что а,-1 указывает начало в памяти вектор-строки, а д/+1д - начало подматрицы, образованной т-/ строками, к которым применяется преобразование.
Приводимый ниже алгоритм выполняет вычисления в соответствии с формулами (13.2)—(13.4). Входная информация этого алгоритма состоит из целых чисел и или массивов с именами A ngB том виде, как они получены на выходе алгоритма НВТ (см. 13.8). Решение будет помешено в массив с именем х. Вектор b будет замещен в памяти вектором ух (см. (13.2)).
Алгоритм 13.9. HS2(m, и, A, g, Ъ, х):
1. Положить bt: = fti/ei,.
*) В оригинале - LSE (Least Squares with Equality constraint!). (Примеч. нер.)
58
2 Для i: = 2, ... ,тположить b, = — (bt - 2 йцЫ)
an /= i
3. Комментарий. Здесь следует задать вектор у2. Если требуется нормальное решение, нужно положить у2: = 0.
. 5. Для/: =m,m- 1,.... 1 выполнить алгоритмы 2 (/,/ + 1, и, д,, 1).
6. Комментарий. Массив с именем х содержит теперь частное решение системы Ах = Ь. Если на шаге 4 в качестве у2 был взят нулевой вектор, то полученное решение является нормальным (т.е. имеет минимальную длину).
ГЛАВА 14
ВЫЧИСЛЕНИЕ РЕШЕНИЯ ЗАДАЧИ НК, ВОЗМОЖНО, НЕПОЛНОГО ПСЕВДОРАНГА
Алгоритмы гл. 11-13 для задач полного ранга ориентированы на те случаи, когда матрица А предполагается достаточно хорошо обусловленной, т.е. исключена возможность, что неопределенность входных данных или возмущение А, эквивалентное округлениям в процессе вычислений, приведут к замене А матрицей неполного ранга. Оценки для возмущений второго типа будут получены в гл. 15—17.
Есть, однако, и другие случаи, когда желательно иметь алгоритм, определяющий, насколько близка данная матрица к матрице неполного ранга. Если выяснилось, что при изменениях коэффициентов исходной матрицы, имеющих порядок неопределенности ее задания, может получиться матрица неполного ранга, то алгоритм должен принять соответствующие меры.
Алгоритм должен по меньшей мере известить пользователя при обнаружении такой ситуации неполного (в указанном смысле) ранга. Вдобавок пользователь может пожелать, чтобы решение было вычислено посредством процедуры, свободной от произвольных возмущений, сопутствующих вычислениям, в которых очень плохо обусловленная задача обрабатывается как задача полного ранга.
Один из методов стабилизации такой задачи состоит в замене А близкой матрицей неполного ранга (назовем ее А ) и последующем вычислении нормального псевдорешения задачи Ах^Ь. Эта замена обычно производится неявно как часть численного алгоритма. Алгоритм HFTI, описываемый в Данной главе, принадлежит к алгоритмам этого типа. Пример, иллюстрирующий использование алгоритма HFTI и некоторых других методов стабилизации, приведен в гл. 26. В гл. 25 описаны другие методы стабилизации.
Определим псевдоранг к матрицы А как ранг матрицы А, заменяющей А в результате выполнения конкретного вычислительного алгоритма. Заметим, что псевдоранг не является функцией одной лишь матрицы А, но зависит также от других факторов: деталей численного алгоритма; значений Допусков, используемых в вычислениях; влияния округлений и т.д.
