Скачать 177.72 Kb.
|
Метод Гаусса-Ньютона. От второго (а частично и от первого) из указанных недостатков метода Ньютона свободен учитывающий специфику (3) метод Гаусса-Ньютона. Пусть ei = ei ( ) = yi – h(xi ; ) . Тогда Q( ) = , и мы имеем H = + (15) Если остатки ei малы, то можно пренебречь первым слагаемым в H и рассматривать приближение H G = (16) Пусть матрица X Rn 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) в качестве шага метода Гаусса-Ньютона. Очевидно, что G 0 (матрица Грама) при всех , и для её вычисления нужны лишь первые производные по параметрам. Недостатки метода: (а) сходимость несколько медленная, чем в методе Ньютона; (б) по-прежнему не гарантировано условие допустимости 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 , а P R 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 – ортогональная матрица, V Rk 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( ). С приближением к * значения уменьшаются, и метод Левенберга-Марквардта близок к методу Гаусса-Ньютона, что обеспечивает его эффективность на последних итерациях. Марквардт предложил следующий алгоритм итераций:
Казалось бы, метод Левенберга-Марквардта – всё, чего можно пожелать: он обеспечивает допустимость градиентного метода (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. |
Постановка задачи Роботы — это физические агенты, которые выполняют поставленные перед ними задачи, проводя манипуляции в физическом мире. Управление... |
Математические модели cae систем Описание и постановка прикладной задачи, реализованной в качестве дипломной работы. 33 |
||
Математические модели cae систем Описание и постановка прикладной задачи, реализованной в качестве дипломной работы. 33 |
Определение ориентации неподвижного объекта с помощью спутниковых радионавигационных систем В статье рассматривается постановка задачи определения ориентации. Описана модель, используемая для решения задачи. Приведен алгоритм... |
||
I. Обзор предметной области 1 Цель работы 6 Постановка задачи 6 Глава ... |
Отчет по лабораторной работе должен содержать следующие материалы... Аналитическое решение тестового примера и результат вычислительного эксперимента по тесту |
||
Программа по курсу: практикум по программированию в ядре Постановка задачи на драйвер kLogger. Базовая структура драйвера. Работа с файлами из режима ядра. Инициализация и выгрузка драйвера.... |
Отчет должны содержать следующие: заголовок или титульный лист, введение,... Спешу вам сообщить, что мы чуть не упустили такую замечательную вещь как курсовая работа |
||
Д. Е. Кочкин в статье рассматривается постановка задачи относительного... Применение математической модели вторых разностей фазовых измерений gps в задаче относительного местоопределения |
Робоча програма по дисципліні Чисельні методи Численные методы решения систем линейных алгебраических уравнений. Правило Крамера, метод обращения матрицы, метод Гаусса |
Поиск на сайте Главная страница Литература Доклады Рефераты Курсовая работа Лекции |