Нелинейный метод наименьших квадратов Постановка задачи




Скачать 177.72 Kb.
НазваниеНелинейный метод наименьших квадратов Постановка задачи
страница3/3
Дата публикации01.06.2014
Размер177.72 Kb.
ТипДокументы
literature-edu.ru > Информатика > Документы
1   2   3

Метод Гаусса-Ньютона. От второго (а частично и от первого) из указанных недостатков метода Ньютона свободен учитывающий специфику (3) метод Гаусса-Ньютона. Пусть ei = ei ( ) = yi h(xi ; ) . Тогда Q( ) = , и мы имеем



H = + (15)

Если остатки ei малы, то можно пренебречь первым слагаемым в H и рассматривать приближение

H G = (16)

Пусть матрица XRn x k и имеет элементы Xij = , причём вектор берётся в точке (l) . Тогда имеем в матричной форме

g = – 2 XT e , G = 2 XTX ,

и в указанном приближении вместо (14) будем иметь
(l+1) = (l) G l -1 gl = (l) + (XTX )-1 XT e (l) (17)

в качестве шага метода Гаусса-Ньютона. Очевидно, что G0 (матрица Грама) при всех , и для её вычисления нужны лишь первые производные по параметрам. Недостатки метода: (а) сходимость несколько медленная, чем в методе Ньютона; (б) по-прежнему не гарантировано условие допустимости G > 0 вдали от *.

Иначе метод Гаусса-Ньютона называют ещё методом линеаризации. Действительно, в матричном виде h( )  h ( (l)) + X ( (l)) . Тогда e = y h( )  y h( (l)) X( (l)) = e (l) X  . Задача минимизации НК с Q( ) = ||e|| 2  ||e(l) – –X  || 2 является задачей линейного МНК относительно  и даёт решение

 (l) = (XTX ) -1 XT e (l) , (17’)

что совпадает с (17). Итак, в методе Гаусса-Ньютона R l = G l -1, l = 1.

Метод Левенберга-Марквардта. Чтобы гарантировать нам в матрице Rl положительную определённость, воспользуемся следующим результатом:

Лемма 4.1. Пусть A = A T R k x k , а PR k x k и P > 0 . Тогда существует такое > 0, что A + P > 0 при > .

Доказательство. Так как A = A T и P = P T , то симметричность матрицы A + P при любом очевидна. Для доказательства положительной определённости осталось показать, что если z R k – произвольный ненулевой вектор, || z || > 0 , || A||  спектральная норма матрицы A, а dk > 0  наименьшее с.з. матрицы P , то при > = || A|| / dk будет выполнено неравенство z T(A + P ) z = z TA z + z TP z > 0. По неравенству Коши-Шварца для произвольных векторов a , b Rk

- 1 +1,

и, в частности, при a = z , b = A z получим z TA z – || z || || A z || || z || || A || || z || = || A || || z || 2 . Так как матрица P > 0, то по формуле (15) гл.1 она имеет спектральное разложение P = V D V T, где диагональная матрица D – матрица упорядоченных по убыванию собственных значений d1 d2 ... dk > 0, а V – ортогональная матрица, VRk x k , то

z TP z = z T V D V T z = w T D w = dk  || w || 2 = dk  || z || 2,

где w = V T z , и || w || = || z || из-за ортогональности V . Следовательно, при > = || A|| / dk будет z T(A + P ) z > 0.
Основываясь на этом результате, Левенберг предложил заменить в (17) матрицу (XTX )-1 на ( XTX + I k ) –1, > 0. При достаточно большом матрица (XTX + I k)-1 > 0 , что делает шаг допустимым. Однако добавление к диагонали матрицы XTX значения имеет разный эффект в зависимости от величины (XTX) jj : если этот элемент, скажем, порядка 104  105, то добавление сравнительно малого (вблизи минимума  10-4  10-5) не изменит значения (XTX) jj + (при точности 10-7 компьютеров типа IBM PC). Если же (XTX) jj близка к 0 (скажем, порядка 10-6), то вклад в диагональную компоненту (XTX+Ik)jj будет преобладающим.

Поэтому Марквардт предложил добавлять к XTX умноженную на матрицу P = diag{XTX}. Если только какой-либо столбец X не равен 0 , то P > 0. Если вернуться к интерпретации метода Гаусса-Ньютона как метода линеаризации модельной функции, то шаг метода Левенберга-Марквардта получится из минимизации целевой функции

Q ( ) = || e(l) X  || 2 + ( )T P  . (18)

Введём матрицу V = P 1/2 = diag{P11 1/2, ..., Pkk 1/2} = VT. Тогда (18) перепишется в виде

Q ( ) = || e(l) X  || 2 + ( )TV TV  = || e(l) X z || 2 + || z || 2,

где z = V  , X  = X V -1. Последнее выражение тождественно целевой функции в гребневой регрессии (её нетрудно получить из формулы (8) гл.3).

Значение изменяется с итерациями: на первых, вдали от *, велико, так что член P преобладающий, и итерация (в варианте Левенберга) близка к итерации метода наискорейшего спуска (по антиградиенту), что обеспечивает допустимость шага и быстрое уменьшение значений Q( ). С приближением к * значения уменьшаются, и метод Левенберга-Марквардта близок к методу Гаусса-Ньютона, что обеспечивает его эффективность на последних итерациях.

Марквардт предложил следующий алгоритм итераций:

  1. Пусть (1)  начальное приближение, l = 1. Положим = 0.01.

  2. Изменяем := / 10.

  3. Вычисляем пробное значение (l+1) для (l+1).

  4. Проверяем допустимость шага, т.е. что Q ( (l+1)) < Q ( (l)). Если шаг допустимый, то идём на шаг 6 алгоритма, иначе на шаг 5.

  5. Если шаг (l+1) не является допустимым, изменяем := 10 и идём на шаг 3.

  6. Полагаем (l+1) = (l+1). Проверяем условия останова. Если они выполнены, то *:= (l+1) , и идём на шаг 8.

  7. Если условия останова не выполнены, то обновляем значения (l) := (l+1), l:= l + 1 и идём на шаг 2.

  8. Стоп.

Казалось бы, метод Левенберга-Марквардта – всё, чего можно пожелать: он обеспечивает допустимость градиентного метода (R > 0 при всех l ), и в то же время объём работы обычно не намного больше, чем в методе Гаусса-Ньютона. Однако практики всегда чем-то недовольны !

В частности, мы рассматривали до сих пор дело так, будто модельная функция h(x;) задана аналитически, и её производные относительно легко вычислить. Между тем это не единственно возможный способ задания h. В частности, в задачах физической или химической кинетики функция h(x;) определяется из системы ДУ 1-го порядка:

, (19)

где f( . ) – известного вида (нелинейная) функция, x – аргумент (в таких задачах аргументом обычно является время, x = t ), Rk неизвестные параметры системы ДУ, – точное решение: R n , = h(x;). Обычно для нелинейных ДУ решение находят численно, так что вычисление модельной функции – довольно дорогое дело. Но мало того: чтобы применять метод Гаусса-Ньютона или Левенберга-Марквардта в задаче минимизации

Q ( ) = || y || 2 (2’)

(где y = (y1 , …, yn ) T измеренные с ошибкой компоненты решения ), нужны ещё производные , j = 1, …, k. Так как аналитическое выражение для h неизвестно, то рассматривают конечно-разностные аналоги

= , (20) т.е. приходится решать (19) при значении j-го параметра в точке j  j , т.е. для вычисления k производных систему (19) нужно решать k раз ! и так – на каждой итерации. В результате применение градиентных методов в таких задачах очень дорого.

В 1978 г. Рэлстон и Дженнрич (Ralston, M.L., and Jennrich, R.J. (1978) Dud a derivative-free algorithm for nonlinear least squares // Technomenrics. V.20, No 1. P.7) предложили алгоритм DUD (Doesn’t Using Derivatives), в котором приближения к поверхности целевой функции Q ( ) находятся на основе не касательных, а секущих плоскостей. При этом, в отличие от (20), на каждом итерационном шаге систему (19) нужно решать не k раз, а только один. Этот метод эффективен и для других задач, где вычисление производных модельной функции очень трудоёмко.

Я не имею времени для изложения этого метода. В литературе на русском языке его идея достаточно подробно изложена в книге Е.З.Демиденко “Оптимизация и регрессия”, 1989. Начиная с 1978 г., программная реализация DUD вошла в состав статистического пакета BNDP, в том числе и в версию для IBM PC.



1   2   3

Похожие:

Нелинейный метод наименьших квадратов Постановка задачи iconПостановка задачи
Роботы — это физические агенты, которые выполняют поставленные перед ними задачи, проводя манипуляции в физическом мире. Управление...

Нелинейный метод наименьших квадратов Постановка задачи iconМатематические модели cae систем
Описание и постановка прикладной задачи, реализованной в качестве дипломной работы. 33

Нелинейный метод наименьших квадратов Постановка задачи iconМатематические модели cae систем
Описание и постановка прикладной задачи, реализованной в качестве дипломной работы. 33

Нелинейный метод наименьших квадратов Постановка задачи iconОпределение ориентации неподвижного объекта с помощью спутниковых радионавигационных систем
В статье рассматривается постановка задачи определения ориентации. Описана модель, используемая для решения задачи. Приведен алгоритм...

Нелинейный метод наименьших квадратов Постановка задачи iconI. Обзор предметной области 1 Цель работы 6 Постановка задачи 6 Глава
...

Нелинейный метод наименьших квадратов Постановка задачи iconОтчет по лабораторной работе должен содержать следующие материалы...
Аналитическое решение тестового примера и результат вычислительного эксперимента по тесту

Нелинейный метод наименьших квадратов Постановка задачи iconПрограмма по курсу: практикум по программированию в ядре
Постановка задачи на драйвер kLogger. Базовая структура драйвера. Работа с файлами из режима ядра. Инициализация и выгрузка драйвера....

Нелинейный метод наименьших квадратов Постановка задачи iconОтчет должны содержать следующие: заголовок или титульный лист, введение,...
Спешу вам сообщить, что мы чуть не упустили такую замечательную вещь как курсовая работа

Нелинейный метод наименьших квадратов Постановка задачи iconД. Е. Кочкин в статье рассматривается постановка задачи относительного...
Применение математической модели вторых разностей фазовых измерений gps в задаче относительного местоопределения

Нелинейный метод наименьших квадратов Постановка задачи iconРобоча програма по дисципліні Чисельні методи
Численные методы решения систем линейных алгебраических уравнений. Правило Крамера, метод обращения матрицы, метод Гаусса

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции