Численное решение задач метода наименьших квадратов - Лоуcон Ч.
Скачать (прямая ссылка):
ГЛАВА 21
ЛИНЕЙНЫЕ ЗАДАЧИ НАИМЕНЬШИХ КВАДРАТОВ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ-РАВЕНСТВАМИ: РЕШЕНИЕ ПОСРЕДСТВОМ ПРЯМОГО ИСКЛЮЧЕНИЯ
К введенной в предыдущей главе задаче НКУ здесь будет применен метод прямого исключения. Будем считать, что ранг *i матрицы С равен ти
но теореме 20.9, что задача НКУ имеет единственное решение для любых правых частей d и /.
\с 1
Мы предположим еще, что столбцы матрицы I ^ I упорядочены так,
чтобы первые тх столбцов С были линейно независимы. Перестановки столбцов, обеспечивающие такое упорядочение, составляют обязательную часть любой вычислительной процедуры того типа, какой обсуждается в данной главе.
Воспользуемся представлениями
л
а ранг матрицы
равен и. Эти предположения гарантируют, соглас-
} т, } тг
лги)
m!n-m,
}m,
} n-m,
(21.2)
ttl
"Систему ограничения Сх = d можно разрешить относительно х t: дг, =Cfl(d-С2х2). Подставляя это выражение для Xi в I Ex - f И, получаем IIEx - f И = I ?,Cf1 (d - C2x2) + ?2*2 -/II =
= II (?2 -ЕхС?Сг)Хг -(f-EtC^d) 11= tE2x2 -f I (21.3)
Вектор x2 определяется из условия минимума згой величины.
С принципиальной точки зрения процедура решения состоит из следующих этапов. Вычисляем матрицу
Ег = Е2-Е1С1-1Сг (21.4) и вектор
f=f-ExC?d. ' (21.5)
Решаем задачу наименьших квадратов
ЕгХг^Г (21.6)
н, наконец, вычисляем
х, = Cll(d-C2x2). (21.7)
Эти этапы можно организовать многими различными способами. Например [25], предположим, что вычислено (^-разложение матрицы СХ:
Сх = Ql С i, (21.8)
где Qi — ортогональная матрица, а Сх - правая треугольная матрица. Тогда равенства (21.4), (21.5) можно записать в виде
Ег= Е2 - (?, СГ1) GiС2 = Е2 - Et С2, (21.9)
/ = /- (?iC~rlX6id)=f-ЁЛ (21.10)
В результате получается следующий алгоритм. Вычисляются преобразования Хаусхолдера, которые приводят С. к треугольному виду: эти же преобразования применяются к С2 и d:
0.[С, С2 .«/] =[C,:Ca:d]. (21.11)
Далее вычисляют т2 Xwti-матрицу ЕХ как решение треугольных систем ?,С, =?,. (21.12)
Затем вычисляют матрицу
Ё2 = Е2-ЁХС2 ., „ (21.13)
и вектор
/ = /-?,? , (21.14)
Потом матрицу Е2 посредством преобразований Хаусхолдера приводят
I
к треугольному виду; эти же преобразования примпигонв к /:
[Ej-\)n-mx О ч> } 1 (21.1J
О 0 \imx +тг -н- I Наконец, из треугольной системы
[?*] [:;]=[Л
определяется решение
А
В описанном алгоритме не требуется двумерных массивов машинно памяти, за исключением тех, что нужны для хранения исходных данны задачи. При этом величины, помеченные знаком ~, следует записыват на место одноименных непомеченных величин, а величины со знаком л на место одноименных величин со знаком ~ .
Подпрограмма этого алгоритма может быть очень компактной, кэд показывает алгольная процедура decompose, приведенная в работе [25]
Предположим, что матрица исходных данных I хранитсявтХл-масси
[I)
I <п
ве А, где т = т, + т2, а вектор исходных данных! I хранится в массив
Ъ длины т. Шаги (21.11) и (21.15) может выполнять одна и та же подпрог рамма, реализующая, по существу, шаги 2-12 алгоритма HFTI (см. 14.9) На этапе (21.11) арифметические операции выполняются лишь с первым! те, строками матрицы [А:Ь], но любые необходимые перестановки столб цов должны производиться над полными m-мерными столбцами А.
Шаги (21.12)-(21.14), которые можно интерпретировать как гауссовс исключение, реализуются следующими операциями:
ап
.-¦•.< ' ¦ • -,' «*' ¦/•¦'ньи ' , • rtsi-i >• (21.17)
д11
к >- •
ац-'-—-. /: = 2...../я,, «"' ¦ ; (21.18)
= «//- S в,*вл/, /:=1Я,+1,...,и, (21.19)
* = 1
т.
= 2 /:-т,+1,... ,т. ч* (21.20)
В качестве примера для этой процедуры снова рассмотрим Задачу НКУ с исходными данными (20.25)-(20.28). Для этой задачи матрицу Qi
8.4. Лоусон 113
в (21.11) можно считать единичной матрицей порядка 1. В соответствии с формулами (21.11)-(21.16) вычисляем
глава 22
ЛИНЕЙНЫЕ ЗАДАЧИ НАИМЕНЬШИХ КВАДРАТОВ С ЛИНЕЙНЫМИ ОГРАНИЧЕНИЯМИ-РАВЕНСТВАМИ: РЕШЕНИЕ ПУТЕМ ВЗВЕШИВАНИЯ
Многие статистики и инженеры пользуются следующим эвристическим приемом. Пусть нужно решить линейную задачу наименьших квадратов, в которой желательно удовлетворить точно некоторые из уравнений. Этого можно добиться приближенно, приписывая большие веса соответствующим уравнениям и решая полученную задачу наименьших квадратов. К тому же результату можно прийти, если приписать малые веса прочим уравнениям и решить такую задачу наименьших квадратов.
В данной главе мы проведем анализ этой вычислительной процедуры решения задачи НКУ (20.1). Основная идея проста. Вычисляем решение задачи наименьших квадратов
(22.1)
(используя, например, метод Хаусхолдера) для "малого", но ненулевого значения е. Тогда решение it(e) задачи (22.1) "близко'^ (в смысле, определяемом соотношениями (2238) и (22.37)) к решению х задачи НКУ.
Такой общий подход представляет практический интерес по той причине, что некоторые существующие программы метода наименьших квадратов могут эффективно решать задачу НКУ путем решения задач вида (22.1).
Очевидным практическим изъяном этой идеи является то обстоятельство, что матрица задачи (22.1) становится как угодно плохо обусловленной (в предположении, что rank С<п) по мере уменьшения параметра е. Это обстоятельство, конечно, ограничивает практическую применимость рассматриваемого подхода, если задача (22.1) решается методом нормальных уравнений (см. (19.1)). В самом деле, нормальные уравнения для (22.1) имеют вид
