Книги по разным темам Pages:     | 1 | 2 | Электронный журнал ИССЛЕДОВАНО В РОССИИ 641 Метод наименьших квадратов как управляемая динамическая система Ю.И. Неймарк, Л.Г. Теклина (neymark@pmk.unn.runnet.ru) Научно-исследовательский институт прикладной математики и кибернетики Нижегородского государственного университета МНК - это метод оценивания неизвестных параметров теоретических моделей по косвенным измерениям при параметрическом анализе данных. Истоки МНК восходят к концу XVIII и началу XIX веков, к трудам К. Гаусса и А. Лежандра. Дальнейшее развитие этот метод получил в работах многих известных математиков: Лапласа, Чебышева, Неймана, Рао, Маркова, Колмогорова и др. Главные достоинства решения задачи оценивания с использованием МНК связаны с ее априорной разрешимостью и такими замечательными свойствами получаемых оценок, как несмещенность, эффективность и состоятельность, что сделало МНК одним из наиболее широко известных и многообразно используемых математических методов обработки наблюдений и экспериментальных данных. МНК позволяет на основе принимаемых гипотез и математических моделей определять неизвестные параметры и закономерности не только в задачах прямой обработки данных, но и в задачах фильтрации, идентификации, распознавания образов, сжатия описания (кодирования), автокорреляционного анализа и др.

В основе МНК лежит минимизация квадратичного функционала 2 N m j J (a1,a2,...,am ) = i (x ) - b (1) ai j j =1i=1 при линейных ограничениях m ai - ck = 0 (k = 1,2,..., L) (2) gki i=1 по искомым значениям параметров a1,a2,...,am на основе используемых данных из N j наблюдений {(bj,x )/ j = 1,2,..., N}, где bj - характеристика j- го объекта, а j x = (x1j,..., xnj)- его описание в n-мерном евклидовом пространстве. Предположение о m наличии зависимости вида b = aii (x), которая может быть точным или i =1 принимаемым приближением, определяется выбранными базисными функциями 1(x),2 (x),...,m (x) и линейными ограничениями (2), и вместе они составляют модель, положенную в основу конкретного применения МНК.

Если ввести матричные обозначения (индексы в скобках определяют значения элементов матриц, а индексы вне скобок - и значения элементов, и порядок матриц):

am(N, L) = ai,i = 1,2,..., m - (m 1) - матрица искомых параметров ai ;

b = b, j = 1,2,..., N - (N 1) - матрица значений bj ;

j N Электронный журнал ИССЛЕДОВАНО В РОССИИ 642 j FN,m = i(x ) j = 1,2,..., N;i = 1,2,...,m - (N m) - матрица значений функций 1(x),...,m(x), на векторах x1,...,xN (в матрице FN,m столбцы i представляют собой значения функции i(x) в точках x1,...,xN, а строки f - это значения функций j j 1(x),...,m(x) при x = x ) то функционал (1) примет вид J (am(N,L) ) = (FN,mam(N,L) - b )T (FN,mam(N,L) - b ).

N N При минимизации функционала (1) в условиях наличия L линейных ограничений вида (2) G am(N,L) = cL методами линейной алгебры и оптимизации (метод L,m множителей Лагранжа для условной оптимизации) можно найти оптимальные значения параметров в виде явных формул [1]:

- T am(N,L) = (Pm1N - Dm(N,L) )FN,mb N + ST,m(N cL ( ) L ) (3) T L( L(N,m) = SL,m(N )FN,mb N - Q-1N,m)cL T где Pm(N ) = FN,mFN,m - информационная матрица размерности m m, L(N,m) - вектор коэффициентов Лагранжа размерности L 1, QL(m,N ) = GL,mPm1N )GT,m - матрица размерности L L, ( L - Dm(N,L) = Pm1N )GT,mQ-1N,m)GL,mPm1N ) - матрица размерности m m, ранг которой ( L L( ( rangD L m, SL,m(N) = Q-1N,m)GL,mPm1N ) - матрица размерности L m.

L( ( Решение (3) имеет место при условии невырожденности матриц Pm(N ) и QL(N,m), когда ранги матриц Pm(N ) и QL(N,m) максимальны и равны m и L соответственно.

-Для удобства записи в дальнейшем введем матрицу m(N,L) = Pm(N) - Dm(N,L), -при L = 0 m(N,0) = Pm(N).

Это - МНК в своей исходной классической форме.

МНК A R B C Рис.Преобразование, определяемое МНК, от входных данных и управляющих команд исследователя к выходным результатам можно представить схематически как показано на рис.1. Прямоугольник символизирует вычислительную процедуру МНК, А,В и С - входы для данных, необходимых для вычислений (А - исходные данные, В - базисные Электронный журнал ИССЛЕДОВАНО В РОССИИ 643 функции, С - линейные ограничения), R - выход, дающий значения искомых параметров и величину функционала качества решения. Классическая форма МНК предполагает, что сначала поступают все входные данные, а затем выполняются вычисления и выдаются требуемые выходные данные.

Но существуют две трудности применения классического МНК. Первая связана с обращением матрицы, подчас большой размерности, без уверенности в ее корректности.

Вторая трудность вызвана тем, что задача анализа данных, осуществляющая преобразование от Уисходных данныхФ к УрезультатуФ, обычно требует изменений в выборке данных и в принимаемых гипотезах в отношении изучаемых процессов и явлений. МНК в своей канонической форме при любых изменениях используемых данных, принимаемых моделей и гипотез требует полного повторения всех вычислений.

Именно поэтому уже в 1821г. Гаусс предложил рекуррентный вариант процедуры, позволяющий корректировать ранее вычисленную оценку с учетом вновь поступивших дополнительных измерений без необходимости повторять все предшествующие вычисления, для случая, когда наблюдение представляется скаляром [2]. В 1950 г.

Плакетт обобщил эту идею на случай векторной величины [3]. Рекуррентная форма МНК получила очень широкое распространение, особенно в теории идентификации, адаптивного управления и современной теории фильтрации. Вычисление оптимальных значений параметров с использованием рекуррентной формулы Плакетта представляет собой итерационный процесс, результат которого зависит от задания начальных значений для вектора искомых параметров и обратной информационной матрицы, а также от объема выборки данных. Дальнейшее расширение рекуррентной формы МНК для случая поиска единственного решения с минимальной нормой путем псевдообращения матрицы данных осуществлено в работах А.Алберта [4]. Но получаемый при этом набор операций итеративного изменения используемых данных и модели - базовых функций и линейных ограничений на искомые параметры - не полный. Доведение его до полного набора привело к универсальной рекуррентной форме МНК, полученной авторами данной работы [5-7]. Универсальность введенных рекуррентных процедур заключается, во-первых, в общности формул как для случая наличия линейных ограничений на оцениваемые параметры, так и при отсутствии таких ограничений и, во-вторых, в наличии рекуррентных процедур МНК и по числу данных в выборке, и по определяемым параметрам, и по количеству ограничений на параметры, причем возможные изменения включают в себя как увеличение, так и сокращение и выборки, и описания, и ограничений. Полнота введенных операций открывает новые более широкие возможности приложений и использования МНК.

Процесс обработки данных с использованием рекуррентного МНК - динамический процесс: все время на входы А, В и С могут подаваться извне данные или исключаться старые и в соответствии с ними выход R выдает соответствующие им значения искомых параметров, и происходит это не путем многократного повторения вычислительной процедуры МНК, а рекуррентно на основе состояния динамической системы, или точнее: управляемой динамической системы обработки и анализа данных на основе метода наименьших квадратов.

Оператор этой динамической системы задается универсальной рекуррентной формой МНК, включающей в себя шесть наборов рекуррентных процедур. Реализация оператора управляемой динамической системы не требует обращения матриц, а только их сложения и умножения. Управление системой состоит в выборе на каждом шаге необходимой рекуррентной процедуры и текущего входного воздействия для перехода системы в новое состояние. Выбор управления определяется результатами анализа Электронный журнал ИССЛЕДОВАНО В РОССИИ 644 информации с помощью МНК, числовыми показателями качества решения - значения функционала J - и данными, поступающими на вход системы.

Состояние системы описывается пятью (a,,Q-1,S, - при наличии ограничений на параметры) или двумя (a, - при отсутствии ограничений на параметры) матрицами, включая и вектор определяемых параметров. При этом k+1 = T (uk+1)k, k +где k и k+1 - состояния на k-ом и следующем k+1-ом тактах вычислений, u вектор входа используемых данных и управляющих воздействий исследователя, поступающих после k-го шага. Выход системы содержит как выбранный базис и соответствующий ему вектор оптимальных параметров, так и числовые показатели качества решения поставленной задачи, а при необходимости и матрицу введенных линейных ограничений.

k +Вектор u представляет собой одно из следующих шести возможных входных воздействий I-VI, определяемых ниже.

I. Введение новых входных данных ( xN +1,bN +1).

Вектору xN +1 соответствует вектор значений базисных функций fN +1. При поступлении новых данных новое состояние системы и оптимальное значение функционала определяются рекуррентными процедурами:

T m(N,L)fN +am(N +1,L) = am(N, L) + (bN +1 - fN +1am(N,L) ), (4) T 1+ fN +1m(N,L)fN +T m(N,L)fN +1fN +1m(N,L) m(N +1,L) = m(N,L) -. (5) T 1+ fN +1m(N,L)fN +T SL,m(N )fN +1fN +1ST ) L,m(N Q-1N +1,m) = Q-1N,m) +, (6) L( L( T 1 + fN +1m(N,L)fN +T SL,m(N )fN +1fN +1m(N,L) SL,m(N +1) = SL,m(N ) -, (7) T 1+ fN +1m(N,L)fN +T SL,m(N )fN +L(N +1,m) = L(N,m) + (bN +1 - fN +1am(N,L)). (8) T 1 + fN +1m(N,L)fN +(bN +1 - fN +1am(N,L))J (am(N +1,L)) = J (am(N,L)) + (9) T 1 + fN +1m(N,L)fN +II. Исключение старых данных ( xN,bN ).

Вектору xN соответствует вектор значений базисных функций fN. При исключении из выборки этого вектора система переходит в новое состояние, определяемое следующими рекуррентными формулами:

T m(N, L)fN am(N -1, L) = am(N,L) - (bN - fN am(N, L) ), (10) T 1- fN m(N, L)fN Электронный журнал ИССЛЕДОВАНО В РОССИИ 645 T m(N,L)fN fN m(N, L) m(N -1, L) = m(N,L) +. (11) T 1- fN m(N,L)fN T SL,m(N )f fN ST,m(N ) N L Q-1N -1,m) = Q-1N,m) -, (12) L( L( T 1- fN m(N,L)fN T SL,m(N )fN fN m(N, L) SL,m(N -1) = SL,m(N ) +, (13) T 1- fN m(N, L)fN T SL,m(N )fN L(N -1,m) = L(N,m) - (bN - fN am(N,L) ). (14) T 1- fN m(N,L)fN (bN - fN am(N,L) )J (am(N -1,L) ) = J (am(N, L) ) - (15) T 1- fN m(N, L)fN III. Введение новой функции m+1(x) с соответствующим введением нового параметра am+1.

При вводе новой базисной функции матрица FN,m пополняется новым столбцом m+1, а матрица G - столбцом m+1, но вид ограничений для старых параметров L,m остается неизменным. Необходима и дополнительная информация о связи новой функции с уже сформированным базисом. Эта информация представляется вектором zm+1 = T FN,m, который является строкой матрицы PM (N ), M m, рекуррентно m+формируемой в процессе ввода статистических данных (увеличения N ) согласно T формуле PM (N +1) = PM (N ) + fN +1fN +1. Новое состояние системы и оптимальное значение функционала определяются в соответствии с рекуррентными процедурами:

-1 T am(N, L) - w (T b - z am(N, L) - m +1L(N,m) ) m +1 m +1 m +1 N m +am +1(N, L) =, (16) -1 T (T b - z am(N, L) - m +1L(N,m) ) m +1 m +1 N m +T L(N,m+1) = L(N,m) - -1 vm+1(T b - zm+1am(N, L) -m+1L(N,m) ), (17) m+1 m+1 N -m(N, L) + -1 w wT - w m +1 m +1 m +1 m +1 m +m +1(N, L) =, (18) -- wT -m +1 m +1 m +Q-1N,m+1) = Q-1N,m) - -1 vm+1vT, (19) m+1 m+L( L( ST ) + -1 w vT m +1 m +1 m +L,m(N ST =, (20) L,m +1(N ) -- vT m +1 m +T J (am+1(N, L) ) = J (am(N,L) ) - -1 (T b - z am(N, L) -m +1L(N,m)) (21) m +1 m +1 N m +где w = m(N,L)zT + ST,m(N )m+1 и vm+1 = S zT - Q-1N,m)m+1, m+1 L,m(N ) m+1 L m+1 L( Электронный журнал ИССЛЕДОВАНО В РОССИИ 646 T m+1 = T m+1 - zm+1m(N.L)zT - zm+1ST,m(N )m+1 -m+1SL,m(N )zT + m+m+1 m+1 L T +m+1Q-1N,m)m+1 = T m+1 - zm+1Pm1N )zT + m+1 m+L( ( - T + (zm+1Pm1N )GT,m -m+1)Q-1N,m) (G Pm1N )zT -m+1) = L L,m ( L( ( m+- = H + (G Pm1N )zT -m+1)T Q-1N,m) (G Pm1N )zT -m+1). (22) m+1 L,m L,m ( m+1 L( ( m+IV. Исключение из базиса некоторой функции (x) и соответствующего ей параметра a.

Если из рассмотрения исключается -ый параметр, < m, то удобнее предварительно изменить порядок следования функций в базисе на 1(x),..., -1(x), +1(x),...,m (x), (x) с соответствующей перестановкой строк и столбцов в тех рассматриваемых матрицах и векторах, порядок элементов в которых определяется упорядоченностью базиса: am(N, L),m(N, L),SL,m(N ), Pm(N ), после чего воспользоваться рекуррентными формулами для определения нового состояния системы после исключения m-ого параметра:

-am-1(N, L) = am(N,L) - mm am, (23).m -L(N,m-1) = L(N,m) - s.mam, (24) mm -1 T m-1(N, L) = m(N,L) -, (25) mm.m.m -Q-1N,m-1) = Q-1N,m) + s.msT, (26) mm.m L( L( -1 T SL,m-1(N ) = SL,m - s.m, (27) mm.m 2 -J (am-1(N,L) ) = J (am(N,L) ) + am (28) mm где A,,S - подматрицы (порядка m-1) соответствующих матриц, - элемент mm матрицы m(N,L), - m-ый столбец матрицы m(N,L) (без ), s.m - m-ый столбец в.m mm матрице S, am - m-ый элемент в векторе am(N,L).

L,m(N ) V. Добавление нового линейного ограничения на оцениваемые параметры.

Если к L 0 (подчеркнем, что допускается и L = 0 ) известным соотношениям добавляется новое, определяемое вектором коэффициентов gL+1 и величиной cL+1, то система переходит в новое состояние, определяемое следующими рекуррентными формулами:

m(N, L)gT L+am(N, L+1) = am(N,L) + (cL+1 - g am(N, L) ), (29) L+gL+1m(N, L)gT L+m(N,L)gT g m(N,L) L+L+m(N,L+1) = m(N,L) -, (30) g m(N,L)gT L+L+-1 - Q + hL1 S gT g ST ) - hL1 S gT +1 L,m(N ) L +1 L +1 +1 L,m(N ) L +L(N,m) L,m(N -Q =, (31) L+1(N,m) - - hL1 g ST ) hL+1 L +1 +L,m(N Электронный журнал ИССЛЕДОВАНО В РОССИИ 647 S - hL1 S gT g m(N,L L,m(N ) +1 L,m(N ) L +1 L +1 ) S =, (32) L +1,m(N ) hL1 g m(N, L) +1 L +L(N,m) + hL1 S gT (cL - g am(N,L ) +1 L,m(N ) L +1 +1 L +1 ) L +1(N,m) =, (33) - hL1 (cL +1 - g am(N, L) ) +1 L +(cL+1 - gL+1am(N,L) )J (am(N,L+1) ) = J (am(N,L) ) + (34) g m(N,L)gT L+L+где hL+1 = gL+1m( N,L)gT.

L+VI. Исключение введенного ранее линейного ограничения.

Если из рассмотрения исключается -ое ограничение,

Q-1N,m),SL,m(N ),L(N,m). После этого новое состояние системы определяется в L( соответствии с рекуррентными процедурами по исключению L -ого ограничения:

-am(N, L-1) = am(N,L) + qLLsT.L, (35) L -L-1(N,m) = L(N,m) - qLLq.LL, (36) -m(N,L-1) = m(N,L) + qLLsT.s, (37) L.

Pages:     | 1 | 2 |    Книги по разным темам