Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
и умножим (25.36) слева на ортогональную матрицу
(25.38)
с* ]¦
В результате получим новую задачу наименьших квадратов:
JnXn
J(m - n)Xn
х/„
(25.39)
где
. ¦ .. . (25.40)
Наконец, при Х>0 из задачи (25.39) можно исключить подматрицу XI„ посредством левого умножения на соответствующие вращения Гивенса. Так, чтобы исключить 1-й диагональный элемент XIп, умножим (25.39) иа матрицу, которая отличается от единичной матрицы порядка m + и только следующими четырьмя позициями:
Столбец/
Строка I
Столбец m + i
(j? + л2)"2
(j? + X2)1"
Строка
т+/
После того как это исключение проделано для / =•!,... ±щ вцщщщщб-
на эквивалентная задача: ,. •
лХл Г g™ 1} m
0(т-я)хл р»[ й(Х) J} и ;
146
здесь
s i
(s2 + X2)'/2 gi,
1=1,...,л
i-n + 1.....m.
ftX
(s^+X2)1'2 S<*> = diag {sfM, • •
5 я ' »
где
s<*> = (*2+Х2)"2,
I = 1,... ,n.
. При X = 0 в задаче (25.39) матрица 1^0) имеет компоненты
(25.42) (25.43)
(25.44) #, а решение
Р(.) =
list
о,
1=1,...,*,
I = * + 1,..., и.
м- ил ч
(25.45)
При Х> О для компонент решения получаем из (25.41)—(25.44) выражения
= „(0) . /=!,...,*,
Кроме того,
О,
+ х2
*2+х2 *
/' = * + 1,... ,и.
(25.46)
- Д I s2 + X2 J i-i1 Pi J Ц2+Х2 J
(25.47)
Отметим, что формулы (25.46) и (25.47) остаются справедливыми и при Х = 0.
Вектор — решение задачи (25.39) - можно преобразовать, пользуясь линейными соотношениями (25.38) и (25.35), в векторы у^ и х^ , которые решают соответственно задачи (25.36) и (25.31).
Нас интересует главным образом задача Ах^Ь. Задача (25.31) была введена лишь как техническое средство генерирования решений для конкретного семейства родственных задач. Поэтому выведем еще формулы для величины шк = ib-Ах^ П. Для Х>0 и определенного в
(25.46), имеем
(Ml =
* ' *' m * Г X2 1J т , .
/=1 ' /=*+! /=1 L J/+X2 J <=*+!
10*
(25.48) 147
Заметим, что при увеличении X происходит уменьшение llp(X) II и увеличение со\. Поэтому хозяин задачи имеет возможность выбрать X, обеспечивающее приемлемый компромисс между величиной решения р(Х) и значением нормы невязки со\.
Получаемое в описанном методе множество решений задачи (25.31) имеет важное свойство оптимальности, выражаемое следующей теоремой.
1 ео р е м а 25.49 [121, 130]. Яусгь фиксировано неотрицательное значение X параметра X, и пусть у - соответствующее решение задачи (25.36). Положим со = i b - Ау\\. Тогда со будет минимальным значением II b> - А у II на множестве векторов у, для которых II у II < II у II.
Доказательство. Предположим^противное. Тогда найдется вектор у, для которого II.у H<Jj.P~ ^ и lb-Ay И< lb-Ay II. Следовательно, II b - Ay f + X2 ly IP < II b - Ay В2 + X 2 IIУ И2, а это противоречит предположению, что у есть решение задачи (25.36) и потому минимизирует II Ъ-Ау II2 +Х~2 \у II2.
При исследовании конкретной задачи наименьших квадратов очень полезным может быть простое табличное или графическое изображение величин \р^ II исо^ из формул (25.47), (25.48). Дополнительную информацию может дать табличное или графическое изображение отдельных компонент решения (при этом нужно опираться на формулы (25.46), (25.38) и (25.35)) как функций от X. Пример анализа этого типа дан в гл. 26.
Значение X, обеспечивающее предписанную норму решения или норму невязки, можно найти, решая уравнения (25.47) или (25.48). Если для этой цели используется метод Ньютона, то могут пригодиться следующие выражения:
Г = Х2, =
'=i dt t=i s2 +t
Si
usf + 1
* , m <*(co?) * *?(u)s?
co2= 2 S g2, -L*1--2Z W,yn
x i=i i=k+\ '' du i=i usj+l
Если задача (25.36) решается непосредственно *) с помощью какого-либо алгоритма, определяющего норму р\ вектора невязки, то следует обратить внимание на соотношение
р? = со2 +Х2 Ь(Х) Л 2- (25-50)
Если нужно найти величину со^, то можно вычислить iy^ I2, а затем разрешить (25.50) относительно сох.
*) То есть без преобразования к (25.39), а затем к(25.41). (Дрнмеч. пер.)
148
§ 5. Удаление переменных
Удаление переменной из задачи эквивалентно фиксированию значения этой переменной в нуле. Если удаляется одна переменная, скажем х„, то задача
Ах (25.51)
преобразуется в
Ах^Ь, (25.52)
где А — тХ (и - 1)-матрица, образованная первыми и- 1 столбцами А, а v - п - 1-мерный вектор.
Предположим, что т> п. Согласно теореме 5.12, сингулярные числа А разделяют сингулярные числа А, откуда следует, что cond (.4) < cond (А). Повторное применение этого процесса показывает, что удаление любого собственного подмножества переменных приводит к матрице с числом обусловленности не большим, чем у исходной матрицы.
Ясно, что минимальная невязка в задаче (25.52) не меньше, чем минимальная невязка задачи (25.51).
Таким образом, удаление переменных, как и некоторые из ранее обсуждавшихся приемов, является средством снижения (или по крайней мере неувеличения) числа обусловленности матрицы ценой увеличения (или по крайней мере неуменьшения) нормы вектора невязки.
Мы сочли полезным отметить эти свойства, с тем чтобы сопоставить удаление переменных или введение дополнительных переменных с другими методами стабилизации. Тем не менее не они (свойства) обычно являются мотивировкой для процедур этого типа. Чаше к удалению или введению переменных прибегают для того, чтобы определить наименьшее число параметров, которые можно использовать в решении, сохраняя приемлемо малую норму невязки.
