Когда данные зашумлены т е полны случайных ошибок тогда аппроксимация данных простой функцией

Линейная аппроксимация комбинации линий по набору зашумленных точек

Постановка задачи

Рассмотрим задачу аппроксимации комбинации прямых линий по набору зашумленных координат точек, находящихся на данной комбинации линий (см. Рис. 1 и Рис. 2). Обычная формула линейной аппроксимации здесь не подойдет, так как точки перемешаны и результат будет некая усредненная линия между ними (см. Рис. 3).

Рис. 1 Комбинация линий и зашумленный набор координат

Рис. 2 Комбинация линий и зашумленный набор координат в увеличенном масштабе

Рис. 3 Результат линейной аппроксимации

Алгоритм

Единственный способ, который пришел в голову, это перебирать разные варианты линий. Т.е. перебираем все возможные углы, естественно на ограниченной сетке, от -90 градусов до +90 градусов (от -180 до 180 бессмысленно, т.к. линия симметрична относительно центра координат).

Таким образом, перебирая всевозможные варианты углов оцениваем тот угол наклона линии, при котором наибольшее количество точек находится на одинаковом расстоянии. Данный угол является искомым углом наклона линии, но он приблизительный, ввиду дискретности начального набора углов. Далее строим линейную аппроксимацию по полученному набору точек и получаем максимально приближенную аппроксимацию первой линии.

Для нахождения следующей линии, из рассмотрения убираются точки, использованные на предыдущем этапе. Таким образом, линия за линией, аппроксимируем все линии.

1. Набор рассматриваемых углов

На данном этапе необходимо разобраться какой набор углов будет перебираться. Зная особенности конкретной задачи можно подкорректировать данный набор углов, тем самым ускорив процесс детектирования линий. Так же можно учесть особенности угла наклона между линиями, то есть на каждом следующем шаге сужать диапазон перебираемых углов. В данной задаче будем использовать в лоб равномерный набор углов от -90 до 90 градусов с шагом 0.1 градуса.

2. Определение расстояния от точки до прямой

Для удобства перебора всевозможных вариантов линий, нам необходимо вывести формулу оценки кратчайшего расстояния от точки до линии.

Пусть уравнение линии и координаты точки, расстояние от которой измеряем, принимают следующие обозначения:

$y = kx + b, x_p, y_p$

Тогда, так как кратчайшее расстояние от точки до линии это перпендикуляр к этой линии, получаем уравнение перпендикуляра, проходящего через заданную точку следующего вида:

$y-y_p=-(x-x_p)/k =>y= -x/k+ x_p/k+y_p$

Тогда, точка пересечения этих двух прямых:

$-x/k+ x_p/k+y_p=kx+b => -x+ x_p+ky_p= k^2 x+bk$

$-bk+ x_p+ky_p= k^2 x+x => x= (x_p+ky_p-bk)/(k^2+1)$

$y= k (x_p+ky_p-bk)/(k^2+1)+b= (〖kx〗_p+k^2 y_p-bk^2+bk^2+b)/(k^2+1)=(〖kx〗_p+k^2 y_p+b)/(k^2+1)$

Получаем расстояние от интересующей точки до точки пересечения:

$dist= √((x_p- (x_p+ky_p-bk)/(k^2+1))^2+(y_p- (〖kx〗_p+k^2 y_p+b)/(k^2+1))^2 )$

3. Построение гистограммы расстояний

Если мы построим просто гистограмму расстояний, она будет малоинформативной, поэтому нам необходимо построить гистограмму по скользящему окну, таким образом она будет более плавной и результат мы получим с меньшей ошибкой (см. Рис. 4-6).

По построенной гистограмме определяем расстояние с максимальным количеством точек. По полученному набору максимального количества точек для каждого угла, строим зависимость количества точек и угла наклона линии (см. Рис. 7, 8). На Рис. 7 видно четких два пика, данные пики и есть углы наклона интересующих нас линий.

Рис. 4 Гистограмма расстояний (ошибочная линия)

Рис. 5 Гистограмма расстояний (правильная линия)

Рис. 6 Увеличенная гистограмма расстояний (правильная линия)

Рис. 7 Гистограмма распределения максимального количества равноудаленных точек в зависимости от угла наклона рассматриваемой линии (Шаг 1)

Рис. 8 Гистограмма распределения максимального количества равноудаленных точек в зависимости от угла наклона рассматриваемой линии (Шаг 2)

4. Построение линейной аппроксимации

Полученный из гистограммы угол наклона линии является неточным, так как он был получен на фиксированной сетке углов. Для получения более точного угла наклона и смещения интересующей линии, необходимо выполнить линейную аппроксимацию полученного набора точек по следующим формулам (см. Рис. 9 и Рис. 10):

$k= (N∑_1^N(xy)- ∑_1^Nx ∑_1^Ny)/(N∑_1^Nx^2 - (∑_1^Nx)^2 ); b =(∑_1^Ny-k∑_1^Nx)/N$

Рис. 9 Результат аппроксимации первой линии

Рис. 10 Результат аппроксимации второй линии

Примеры использования

Приведем примеры распознавания линий на произвольных наборах точек (см. Рис 11-13).

Рис. 11 Результат работы на произвольной выборке точек

Рис. 12 Результат работы на произвольной выборке точек

Рис. 13 Результат работы на произвольной выборке точек

Вывод

С помощью приведенного алгоритма можно детектировать прямые линии с относительно высокой скоростью и определять их параметры (наклон и смещение). Количество линий при этом может быть неограниченное количество.

Для успешного детектирования линий, желательно чтобы точки были максимально сильно разбросаны по координатной системе, так как если все точки будут рядом, то при процедуре перехода детектирования от одной линии к другой, точки новой линии будут отброшены ввиду их близости к линии с предыдущей итерации.

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

Источник

Мо1ег, 8. 1)ахи С «Хцтег1са1 МейосЬ апс1 дойч аге'» С Ргеп1г:е-На11, 1988 С С Версия для вещественной арифметики одинарной точности. С С С С С С С С С А вЂ” КЕА1 С Нижний предел интегрирования. С В КЕА1. С Верхний предел интегрирования С Выходные параметры: С КЕБ1’1 Т вЂ” КЕА1 С Приближение к ингегралу 1. С Вычисляется с помощью 15-ТОЧЕ Ч НОГО П РАВИС ЛА КРОНРОДА 1КЕЯК), полученного оптимальным С добавлением абсцисс к 7-ТОЧЕЧНОМУ ПРАВИЛУ С ГАУССА (КЕМ). С С С С С С КЕВАВБ -КЕАЕ С Приближение к интегралу 3. С КЕ8АЯС вЂ” К ЕА1. С Приближение к интегралу для АВ8(Е вЂ” 1,/(В вЂ” А)). С*»» ССЫЛКИ. Р1ЕББЕХ8 К ЕТ А1 111))АОРАСК- А 81 ВКОСЬ!Т11~Е С РАСКАС~Е РОК АЬТОМАТ1С 1ХТЕ(лКАТ1ОЧ~, С 8РК11~ОЕК, ВЕК1.1М, 1983 С ВЫЗЫВАЕМЫЕ ПОДПРОГРАММЫ: К1МАСН I’лава 5 КОНЕЦ ПРОЛОГА () К! 5 8(1ВКО()Т!ХЕ 9!Г)А(А,В,ЕРБ,К.Е,КЕ,!Н АО) НАЧАЛО ПРОЛОГА 010А Из книги: Р.

КаЬапег, С. Мо1сг, 8. Хачим «о!шпет(са! Ме!!1ойв апс! 8ойъагс» Ргспг(се-На!1, 1988 Описание параметров: А В ЕР8 (на входе) пределы интегрирования. (на входе) допустимая погрешность вычисления интеграла. чтобы получить точность до двух знаков, задайтс ЕРВ = .01, до трех знаков- ЕР8 = .001 и т.д. значение ЕР8 должно быть положительным, К (на выходе) наиболее точное из вычисленных программой 11!ПА значений вашего интеграла. Е (на выходе) оценка АВБ (интеграл вЂ” К). КЕ (на выходе) мера трудоемкости: количество вычислений вашей подынтегральной функции. КЕ всегда ке меньше ЗО.

1ЕЕА(з (на выходе) признак ошибки. Принимает значения: 0 Нормальное завершение, выполняются неравенсгва Е < ЕРВ и Е < ЕР8 е АВЯ(К). 1 Нормальное завершение, выполняются неравенства Е < ЕРБ, но Е > ЕР8~ АВБ(К). 2 Нормальное завершение, выполняются неравенства Е < ЕРБ ~ АВ8(К), но Е > ЕР8. 3 Нормальное завершение„но значение ЕР8 задано слишком малым, чтобы можно было удовлетворить требованиям абсолютной или относительной ДАТА НАПИСАНИЯ 821018 (ГГММДД) ДАТА ПЕРЕСМОТРА 870525 (ГГММДД) КАТЕГОРИЯ МО. Н2А1А1 КЛЮЧЕВЫЕ СЛОВА: адаптивная квадратура, автоматическая квадратура АВТОР: КАНА!ЧЕК О. К., 8С1ЕХТ1Г1С СОМР()Т1МСг Р1’Л81ОХ, ХВ8. НАЗНАЧЕНИЕ: 91ЭА находит приближение к одномерному интегралу для заданной пользователем подынтег ральной функции (простая в использовании программа).

ОПИСАНИЕ О10А вычисляет определенный интеграл для заданной пользователем функции одной переменной. с С с С С С С с с с с С С с с с с С с с с с С С с С С с с с С с С с с с с С С С с С С С с с Замечание. Если 1Г1.А(3 = 3, 4, 5 или 6, попробуйте вместо (~1РА воспользоваться Я11УАХ. Вы должны написать фортранную подпрограмму-функцию с именем Г, вычисляющую подынтегральную функцию. Обычно она выглядит так: ГГЧСТ1ОМ Г(Х) Е-(вычисление подынтегральной функции в точке Х) КЕТ1)КХ ЕМЭ погрешности.

4 Вычисления не завершены из-за больших ошибок округления. По-видимому, Е и К не далеки от истинных. 5 Вычисления не завершены из-за нехватки памяти. К и Е не далеки от истинных. 6 Вычисления не завершены из-за трудностей, вызванных слишком жесткими требованиями к погрешности. 7 Вычисления не завершены из-за того, что значение ЕРЯ задано с =0.0.

ИЛЛЮСТРИРУЮЩАЯ ПРОГРАММА А=00 В = 1.0 (ЗАДАНИЕ КОНЦОВ ОТРЕЗКА ИНТЕГРИРОВАНИЯ 10, Ц) ЕРЯ = 0.001 (ЗАДАНИЕ ДОПУСТИМОЙ ПОГРЕШНОСТИ) СА1.1. (~11УА (А,В,ЕРБ,К,Е,КЕ,1Г1 АС) ЕХ1:У Н1ХСТ1ОМ Г(Х) Е = 511’1(2.* Х) вЂ” Я 1КТ(Х) (НАПРИМЕР) КЕТ1)КХ Е1М1У ВЫХОДНЫЕ ДАННЫЕ ДЛЯ ЭТОГО ПРИМЕРА 0.0 1.0 .001 .041406750 .69077Е вЂ” 07 30 0 Замечание 1. Программа содержит небольшой элемент случайности. При нескольких последовательных обращениях к ней с одними и с С С с с с с С с с с с с с с с С с с С с с с с с с с С с с С С с с с с с с теми же входными параметрами результаты окажутся разными, по, как правило, близкими дру~ к другу.

Замечание 2. Программа предназначена для интегрирования по конечному отрезку. Поэтому входные параметры А и В должны быть вещественными числами из диапазона„который допустим на вашем компьютере. Если требуется произвести интегрирование по бесконечному отрезку, то задайте А или В или оба этих параметра такими, чтобы интеграл по отрезку [А, В) почти не отличался от интеграла по бесконечному отрезку. Здесь, однако, необходима осторожность. Например, чтобы проинтегрировать ЕХР( вЂ” Х*Х) по вещественной прямой, можно положить А = вЂ” 20., В = 20. или присвоить этим параметрам сходные значения, которые обеспечат хороший результат, Если вы выберете А = вЂ” 1.Е10 и В = + 1,Е10, то вы столкнетесь с двумя неприятными явлениями.

Во-первых, вы обязательно получите сообщение об ошибке из программы ЕХР, так как обращаться к ней придется при слишком малых значениях аргумента. Возможны и другие неприятности, например, произойдет исчезновение порядка. Во-вторых„даже если арифметика будет работать должным образом, О1РА, скорее всего, выдаст неверный результат, потому что по сравнению со столь большим отрезком интегрирования отрезок ( вЂ” 20., 201. который вносит основной вклад в значение интеграла.

почти «бесконечно мал», и вряд ли точки, в которых будет вычисляться подынтегральная функция, попадут в этот отрезок. Более гибкая программа О1РА представляет собой простой в использовании драйвер для другой программы (~1РАХ. (~1РАХ обладает по сравнению с О1РА дополнительными возможностями. Ссылки: нет ВЫЗЫВАЕМЫЕ ПОДПРОГРАММЫ: 01РАХ КОНЕЦ ПРОЛОГА Я1РА КЕА1 ЕСХСТ10)Х1 РСН(;1А(М.Х,Г,Р,А,В,1Е1хК) НАЧАЛО ПРОЛОГА РСНЯА ДАТА НАГ1ИСАНИЯ 870829 (ГГММДД) ДАТА ПЕРЕСМОТРА 870829 (ГГММДД) КАТЕГОРИЯ ХО. ЕЗ,Н2А2 КЛЮЧЕВЫЕ СЛОВА: простое в использовании эрмитово кубическое или сплайн-интегрирование, численное интегрирование, квадратура С*** АВТОР: КАНАХЕК 1Э К„(ХВК) С С С С С С*** НАЗНАЧЕНИЕ: РСНЯА вычисляет определенный интеграл для С кусочно-полиномиальной эрмитовой кубической С функции или сплайна по произвольному отрезку С (простая в использовании программа).

С*~* ОПИСАНИЕ 1ХТЕОЕК Х, 1ЕКК КЕА1. Х(Х), Г(Х), ЩХ), А, В С С С С С С С С С С С С С С С С С С С С С С С С С С С С С С С С С С С ЯС1ЕХТ1Г1С СОМР1)Т1ХС~ Е)171ЯОХ ХАТ10ХА1. ВБКЕАБ ОГ ЯТАХОАКОЯ КООМ А161, ТЕСНХО(.ОСУ ВШ1.ШХО ОА1ТНЕКЯВ1)КСх, МАКУ1 АМЭ, 20899 (301) 975-3808 РСНЯА: Кусочно-полиномиальное эрмитово ‘ кубическое или сплайн-интегрирование, произвольные пределы интегрирования, простота в использовании. Из книги: Р. КаЬапег, С, Мо1ег, Б.

Хаий «Хшпег)са1 МейосЬ апй Бочаге» Ргеп6се-На11, 1988 РСНЯА вычисляет по отрезку 1А, В1 определенный интеграл для кусочно-полиномиальной эрмитовой кубической функции или сплайна, заданных параметрами Х, Х, Г, В. Представляет собой простой в использовании драйвер для программы РСН1А Ф.Н. Фритча, описание которой приведено в указанной ниже работе (2). Программа обладает также другими возможностями, Обращение к подпрограмме: Ъ’А1Л.!Е = РСНЯА (Х, Х, Г, Р, А, В, 1ЕКК) Описание параметров: ЧАВ)Е-(на выходе) ЗНАЧЕНИЕ интеграла. вЂ” (на входе) число заданных точек.

(Сообщение об ошибке, если Х.1 Т.2.) -(на входе) вещественный массив значений независимой переменной. Элементы массива Х должны быть заданы в строго возрастающем порядке: Х(1 вЂ” 1) .1-Т. Х(1), 1 = 2(1) Х. (Сообщение об ошибке в противном случае.) 1ЕКК С*** ССЫЛКИ: 1. Г.Х. ГК1ТБСН, К,Е. САКЬБОХ, МОХОТОХЕ С С С С С С С С С КОНЕЦ ПРОЛОГА РСНЯА С С с С С с с с с С С С с С с С с С С С с С с с С с С с С С С С С С С с Г вЂ” (на входе) вещественный массив значений функции.

Значение Г(1) соответствует Х(1). О вЂ” (на входе) вещественный массив значений производной, Значение О(1) соответствует Х(1). А, В -(на входе) пределы интегрирования. Замечание. Здесь не требуется, чтобы отрезок (А, В) принадлежал отрезку (Х(1), Х(ХЦ. Однако если это не так, к результату нужно относиться с большой долей недоверия, вЂ” (на выходе) признак ошибки.

Нормальный выход: 1ЕКК = 0 (нет ошибок). Предупреждения: 1ЕКК = 1, если А не принадлежит отрезку (Х(1), Х(ХЦ. 1ЕКК = 2, если В не принадлежит отрезку (Х(1), Х(Х)1. 1ЕКК = 3, если выполняются оба вышеуказанных условия. (Отсюда следует, что либо отрезок [А, В | содержит отрезок (Х(1), Х(Х)3, либо эти отрезки не пересекаются.) Устранимые ошибки: 1ЕКК = вЂ” 1, если Х,ЬТ,2. 1ЕКК = вЂ” 3, если элементы массива Х заданы не в строго возрастающем порядке.

(В каждом из этих случаев интеграл не вычисляется.) Замечание, Проверка параметров осуществляется в указанном выше порядке; при обнаружении ошибки остальные параметры не проверяются. Р1ЕСЕ%1$Е С11В1С 1ХТЕКРО1.АТ1ОХ, $1АМ Я. ХБМЕК, АХА1.

17, 2 (АРК11. 1980), 238 вЂ” 24б 2. Г. Х. ГК1ТБСН, Р1ЕСЕ%1БЕ СБВ1С НЕКМ1ТЕ 1ХТЕКРОЬАТ1ОХ РАСКАБЕ, Г|ХАЬ ЯРЕС1. Г|САТ10ХБ, 1 АЮКЕХСЕ Ь|УЕКМОКЕ ХАТ1ОХА1. ЬАВОКАТОКЪ’, СОМРЬ1ТЕК РОС(3 МЕХТАТ1ОХ 13С11)-30194, А|АСЯТ 1982 ВЫЗЫВАЕМЫЕ ПОДПРОГРАММЫ: РСН1А Глава 6 Аппроксимация данных методом наименьших квадратов б.1. Введение Рассмотрим следующий эксперимент: воду прогоняют сквозь контейнер, в который добавлено некоторое количество краски. Через каждые несколько секунд измеряется концентрация ° краски в воде, вытекающей из контейнера.

Ожидается, что концентрация краски будет линейно уменьшаться со временем. Результаты измерений показаны на рис. б.!. Заметим, что точки данных не лежат на прямой линии. Это не так уж неожиданно. Измерительные приборы могут быть не совсем точными, может оказаться невозможным точно интерпретировать измерения, а смешивание может происходить не совсем так, как предсказано. Чтобы определить скорость, с которой убывает концентрация, экспериментатору следовало бы аппроксимировать данные прямой линией, которая в некотором смысле «наилучшим образом» аппроксимирует данные. На рис. б.! вычерчена одна из таких аппроксимаций. Ситуации такого типа встречаются весьма часто. Одна из причин, по которой требуется знать скорость смешивания, заключается в том, что 7.0 6.5 6.0 5.5 5.0 45 4,0 3.5 3.0 2.5 2.0 1.5 1.0 0.5 0 0 1 2 3 4 5 6 7 8 8 10 !1 12 13 Рис.

6.1. Эксперимент с изменением концентрации. мы хотим уметь предсказывать, как будут протекать другие эксперименты. При других обстоятельствах нам может потребоваться смоделировать инфляцию в экономике, распространение эпидемии или рост населения страны. Когда данные «зашумлены», т. е. полны случайных ошибок, тогда аппроксимация данных простой функцией позволяет нам изучать тренды (тенденции изменения) в данных; зто называют сглаживанием.

Возможны две качественно различные причины, по которым требуется найти линию, аппроксимируюшую данные. (1) Скорость смешивания а необходима, например, чтобы определить, не перегружено ли оборудование для инжекции краски. (2) Аппроксимирующая линия необходима, чтобы предсказать концентрацию краски в моменты времени, для которых не проводилось измерений. В этом случае нас интересуют не столько значения а и р, сколько значения приближающей функции.

Источник

Если информации
о моделируемом объекте (процессе)
недостаточно или он настолько сложен
(имеет случайный характер), что невозможно
составить его детерминированную модель,
используют стохастические модели и
соответствующие экспериментально-статистические
методы.

На
практике весьма распространенной
является задача определения функции
(аналитической зависимости), которая
должна соответствовать некоторым
данным, полученным, например, при
проведении экспериментальных исследований.
При этом можно выделить два направления
приближения функции –
процесс интерполяции,
определяющий вид функции, совпадающей
с табличными данными, а также процесс
аппроксимации,
направленный на восстановление
функциональной зависимости по данным
эксперимента, возможно содержащего
ошибки. Аппроксимация при этом должна
обеспечивать оптимальное расположение
линии (поверхности для многофакторного
эксперимента) функции среди множества
экспериментальных точек, не обязательно
совпадающей с ними.

Простейшим
случаем интерполяции является определение
вида функции f(x)
одной переменной, проходящей через
заданные точки (x_i,
y_i),
т.е. f(x_i)=y_i
, i=1,…,N
(рис.19а).

y
y

x

x

а) б)

Рис.
19. Виды аппроксимации

Говорят,
что функция f
интерполирует
данные, и в
этом случае она называется интерполянтом,
или интерполирующей
функцией.
Как видно из графика, в зависимости от
способа интерполяции можно получить
различные интерполянты. Отсюда следует:

1)
данные (x_i,
y_i)
сами по себе не могут определить
интерполянт, и для фиксированного набора
данных существует бесконечное множество
интерполянтов;

2)
интерполяция может быть полезна только
в том случае, если данные не содержат
ошибок, если же, например, y_i
содержит погрешности, данные необходимо
аппроксимировать как-то по-другому.

Наиболее
употребительным способом аппроксимации
данных, содержащих ошибки, является
метод наименьших квадратов. Он позволяет
определить вид функции с минимальной
суммой квадратов отклонений ее значений
от экспериментальных. На рис. 19б отражен
вариант такой функции при одномерной
линейной аппроксимации.

В общем случае
задача аппроксимации данных решается
для нелинейной функции многих переменных.

Так
как в реальном процессе всегда существуют
неуправляемые и неконтролируемые
переменные, результат эксперимента
есть случайная величина. Пусть, например,
требуется исследовать зависимость
y(x₁,
x₂,…x_m),
причем величины y
и Х={x₁,
x₂,…x_m}
измеряются в одних и тех же экспериментах.
Будем считать, что погрешность измерения
величин x_j
пренебрежимо мала по сравнению с
погрешностью измерения величины y,
т.е. величины x_j
измеряются точно, в то время как измерение
величины y
содержит случайные погрешности. Таким
образом, результаты эксперимента можно
рассматривать как выборочные значения
случайной величины (X),
зависящей от X
, как от параметра.

Регрессией
называют зависимость

условного математического ожидания
величины (X)
от переменной X
, т.е.
.
Задача регрессионного анализа состоит
в этом случае в восстановлении
функциональной зависимости

по результатам измерений (X_i,
y_i),
i=1,2,…,
N.
Аппроксимируем неизвестную зависимость

при помощи заданной функции уравнения
регрессии
.
Это значит, что результаты измерений
можно представить в виде
,
где

–
неизвестные параметры регрессии, _i
–
случайные величины, характеризующие
погрешности эксперимента. С учетом
разложения исследуемой зависимости в
ряд Тейлора в окрестности X₀
и использования выборочных коэффициентов

как оценок теоретических (₀=f(X₀),
₁=
f(X₀)/
x₁,…)
уравнение регрессии можно записать в
следующем общем виде [8]

,
(86)

где
b₀
– свободный член уравнения регрессии;
b_j
– линейные эффекты; b_jj
–
квадратичные эффекты; b_jk
— эффекты взаимодействия.

Коэффициенты
уравнения (86) определяются методом
наименьших квадратов из условия

,
(87)

где
N
– объем выборки.

Необходимым
условием минимума

является равенство нулю соответствующих
частных производных
,
,…
Тогда после преобразования получим

.
(88)

Система
(88) содержит столько же уравнений, сколько
неизвестных коэффициентов

входит в уравнение регрессии и называется
в математической статистике системой
нормальных уравнений.
Для решения системы (52) необходимо задать
конкретный вид функции
.

Линейная
регрессия одного параметра.
Определим по методу наименьших квадратов
коэффициенты линейного уравнения
.
Тогда с учетом

и

для системы (3) можно записать

или
.
(89)

Решая
данную систему относительно

и
,
получим при помощи определителей
следующие выражения:

, .

Коэффициент

проще найти по известному

из первого уравнения системы (53)

, где

–
средние значения x
и y
().

Для
оценки силы линейной связи вычисляется
выборочный коэффициент корреляции r^*

.
(89)

Чем
ближе r^*
к единице, тем выше линейность зависимости
между x
и y.

Параболическая
регрессия одного параметра
определяется коэффициентами параболического
уравнения
.
Тогда для параболы второго порядка
система
нормальных уравнений (88) имеет вид

(90)

Аналогично
могут быть определены коэффициенты

для параболы любого порядка.

Трансцендентная
регрессия одного параметра
определяется коэффициентами уравнений
показательного
,
дробно-степенного типа

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



Пусть и	Пусть и

Коэффициенты

или

определяются методом наименьших
квадратов, значения которых используются
для нахождения
.

Для
оценки силы (тесноты) нелинейной связи
(проведения корреляционного
анализа)
вычисляется корреляционное
отношение

,
(91)

где
f₁=N–1,
f₂=N–l
– числа степеней свободы; l
– число связей, наложенных на выборку
(для уравнения регрессии это число
определяемых коэффициентов);

–
остаточная дисперсия;

— дисперсия относительно среднего.

Чем
больше ,
тем сильнее связь (01).
При =0
однозначное отсутствие связи между
случайными величинами возможно только
для нормального распределения. В случае
линейной регрессии (l=2)
корреляционное отношение равно
коэффициенту корреляции =|r^*
|.

Множественная
регрессия
предполагает определение коэффициентов
(исследование корреляционной связи)
для многофакторного уравнения. Например,
для линейного случая уравнение
множественной регрессии имеет вид
.
Здесь, следовательно, требуется определить
не линию регрессии, а поверхность (m=2)
или гиперповерхность (m>2).

Статистический
анализ результатов (регрессионный
анализ)
проводится после определения уравнения
регрессии и включает: оценку адекватности
уравнения; проверку значимости всех
коэффициентов

в сравнении с ошибкой воспроизводимости;
расчет доверительных интервалов для
параметров модели

и выходной переменной
.

При
отсутствии параллельных опытов и,
следовательно, дисперсии воспроизводимости,
а также нормальном распределении
случайных величин y_i
качество аппроксимации (адекватность)
можно оценить по критерию
Фишера

[4]. В данном случае он показывает, во
сколько раз уменьшается рассеяние
относительно полученного уравнения
регрессии по сравнению с рассеянием
относительно среднего. Чем больше
значение F
превышает табличное

для выбранного уровня вероятности
(значимости, надежности) p
(обычно
p=0.95)
и чисел
,
тем эффективнее уравнение регрессии.

При
одинаковом числе параллельных опытов
(каждый i-й
опыт с объемом выборки N
()
проводится U
раз
)
выборочные дисперсии

должны быть однородны. Последнее
выполняется если справедливо условие
G_max<G_p^ТАБ(N,U-1),
где G_p^ТАБ(N,U–1)
– табличное значение критерия
Кохнера
при уровне значимости p;

;

–
максимальное значение выборочной
дисперсии. Для однородных выборочных
дисперсий рассчитываются дисперсия
воспроизводимости

и дисперсия адекватности
,
которые необходимы для определения
критерия Фишера
.
Если расчетное значение меньше табличного
,
то уравнение адекватно.

Оценка
значимости коэффициентов уравнения
регрессии проводится по критерию
Стьюдента
,
где

–
h-й
коэффициент уравнения;

–
среднее квадратичное отклонение h-го
коэффициента. Если

больше табличного

для выбранного уровня значимости p
и степени свободы f=N(U–1),
то коэффициент

значимо отличается от нуля. Незначимые
коэффициенты из уравнения исключаются
с последующим пересчетом оставшихся.
Чтобы не проводить повторных расчетов
модели, при отбрасывании (включении)
отдельных факторов применяют регрессионные
уравнения в форме ортогональных полиномов
(ортогональные многочлены Чебышева)
[4, 8]. Для уравнения регрессии

, .

Определив

и табличные значения величины t_
корня уравнения F_N_-2()=1–0.5,
функции распределения Стьюдента (t
– распределение) с N-2
степенями свободы можно найти доверительные
интервалы параметров модели

и доверительный коридор выходной
переменной
.
Для уравнения регрессии

получим

для
параметров

и
:

где
₀,
₁–
половина ширины доверительного интервала
для

и
;

для
определения концов доверительных
интервалов (доверительной полосы или
коридора) выходной переменной

при каждом конкретном значении

(доказано, что доверительный интервал
накрывает истинное значение

с вероятностью 1-):

;

для
определения доверительной области всей
линии регрессии соответственно нижней
(left)
и верхней (right)
границ полосы:

где

–
корень уравнения F_2,_N_-2()=1–;
F_2,_N_-2(x)
– функция распределения Фишера (F
–
распределение) с 2 и N–2
степенями свободы.

Использование
модели

за пределами исследуемого диапазона
не обосновано.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Аппроксимацией (приближением) функции называется нахождение такой функции (аппроксимирующей функции), которая была бы близка заданной. Критерии близости функций и могут быть различные.

Основная задача аппроксимации — построение приближенной (аппроксимирующей) функции, в целом наиболее близко проходящей около данных точек или около данной непрерывной функции. Такая задача возникает при наличии погрешности в исходных данных (в этом случае нецелесообразно проводить функцию точно через все точки, как в интерполяций) или при желании получить упрощенное математическое описание сложной или неизвестной зависимости.

Рис. 3.6 Метод Лагранжа

Концепция аппроксимации

Близость исходной и аппроксимирующей функций определяется числовой мерой

— критерием аппроксимации (близости). Наибольшее распространение получил квадратичный критерий, равный сумме квадратов отклонений расчетных значений от «экспериментальных» (т.е. заданных), — критерий близости в заданных точках:

Здесь у_i — заданные табличные значения функции; у_i^расч — расчетные значения по аппроксимирующей функции; b_i — весовые коэффициенты, учитывающие относительную важность i-и точки (увеличение b,. приводит при стремлении уменьшить R к уменьшению, прежде всего отклонения в i—й точке, так как это отклонение искусственно увеличено за счет относительно большого значения весового коэффициента).

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

Другим распространенным критерием близости является следующий:

Этот критерий менее распространен в связи с аналитическими и вычислительными трудностями, связанными с отсутствием гладкости функции и ее дифференцируемости.

Выделяют две основные задачи:

1) получение аппроксимирующей функции, описывающей имеющиеся данные, с погрешностью не хуже заданной;

2) получение аппроксимирующей функции заданной структуры с наилучшей возможной погрешностью.

Чаще всего первая задача сводится ко второй перебором различных аппроксимирующих функций и последующим выбором наилучшей.

Метод наименьших квадратов

Метод базируется на применении в качестве критерия близости суммы квадратов отклонений заданных и расчетных значений. При заданной структуре аппроксимирующей функции у_i^расч(х) необходимо таким образом подобрать параметры этой функции, чтобы получить наименьшее значение критерия близости, т.е. наилучшую аппроксимацию. Рассмотрим путь нахождения этих параметров на примере полиномиальной функции одной переменной:

Запишем выражение критерия аппроксимации при b_i =1 (i=1, 2,…, n) для полиномиального у_i^расч (х):

Искомые переменные а_j можно найти из необходимого условия минимума R по этим переменным, т.е. dR / dа_р = 0 (для _р =0, 1,2,…,k). Продифференцируем по а_р (р — текущий индекс):

После очевидных преобразований (сокращение на два, раскрытие скобок, изменение порядка суммирования) получим

Перепишем последние равенства

Получилась система n+1 уравнений с таким же количеством неизвестных а_j, причем линейная относительно этих переменных. Эта система называется системой нормальных уравнений. Из ее решения находятся параметры а_j аппроксимирующей функции, обеспечивающие minR, т.е. наилучшее возможное квадратичное приближение. Зная коэффициенты, можно (если нужно) вычислить и величину R (например, для сравнения различных аппроксимирующих функций). Следует помнить, что при изменении даже одного значения исходных данных (или пары значений х_i, у_i, или одного из них) все коэффициенты изменят в общем случае свои значения, так как они полностью определяются исходными данными. Поэтому при повторении аппроксимации с несколько изменившимися данными (например, вследствие погрешностей измерения, помех, влияния неучтенных факторов и т.п.) получится другая аппроксимирующая функция, отличающаяся коэффициентами. Обратим внимание на то, что коэффициенты а_j полинома находятся из решения системы уравнений, т.е. они связаны между собой. Это приводит к тому, что если какой-то коэффициент вследствие его малости захочется отбросить, придется пересчитывать заново оставшиеся. Можно рассчитать количественные оценки тесноты связи коэффициентов. Существует специальная теория планирования экспериментов, которая

позволяет обосновать и рассчитать значения х_i, используемые для аппроксимации, чтобы получить заданные свойства коэффициентов (несвязанность, минимальная дисперсия коэффициентов и т.д.) или аппроксимирующей функции (равная точность описания реальной зависимости в различных направлениях, минимальная дисперсия предсказания значения функции и т.д.).

Рис. 3.7 Влияние степени аппроксимирующего полинома М на точность аппроксимации

В случае постановки другой задачи — найти аппроксимирующую функцию, обеспечивающую погрешность не хуже заданной, — необходимо подбирать и структуру этой функции. Эта задача значительно сложнее предыдущей (найти параметры аппроксимирующей функции заданной структуры, обеспечивающей наилучшую возможную погрешность) и решается в основном путем перебора различных функций и сравнения получающихся мер близости. Для примера на рис. 3.7 приведены для визуального сравнения исходная и аппроксимирующие функции с различной степенью полинома, т.е. функции с различной структурой. Не следует забывать, что с повышением точности аппроксимации растет и сложность функции (при полиномиальных аппроксимирующих функциях), что делает ее менее удобной при использовании.

Рассмотрим решение задачи аппроксимации и интерполяции с шумом в

программе MathCAD (рисунок 3.8).

Пример 3.1. В ходе проведения эксперимента были получены данные, представленные в таблице 3.1. Необходимо способом наименьших квадратов подобрать для заданных значений x и y квадратичную функцию . Построить на одной координатной плоскости экспериментальные данные и аппроксимирующую функцию.

Таблица 3.1 Данные эксперимента

х	80,5	77,0	70,8	56,7	39,7	29,9
у	281	272	259	224	186	170

Решение. Для определения коэффициентов квадратичной функции построим дополнительную таблицу 3.2.

Таблица 3.2 Дополнительная таблица


1	80,5	6480,25	521660,13	41993640,0625	281	22620,5	1820950,25
2	77	5929	456533	35153041,0000	272	20944	1612688,00
3	70,8	5012,64	354894,91	25126559,7696	259	18337,2	1298273,76
4	56,7	3214,89	182284,26	10335517,7121	224	12700,8	720135,36
5	39,7	1576,09	62570,773	2484059,6881	186	7384,2	293152,74
6	29,9	894,01	26730,899	799253,8801	170	5083	151981,70
Σ	354,6	23106,88	1604673,972	115892072,1124	1392	87069,7	5897181,81

Строим систему уравнений

В нашем случае она будет иметь вид:

Из полученной системы уравнений находим

Искомая зависимость

Строим график экспериментальных данных и найденной зависимости.

Рис.3.8 Аппроксимация и интерполяция в задаче с помехами

Если требуется построить зависимость в виде показательной функции , то необходимо составить систему:

(3.7)

Для этого строится таблица


1
…	…	…	…	…
n
Σ

Из системы 3.7 находим коэффициенты и (необходимо выразить ).

Если требуется построить зависимость в виде степенной функции , то составляется система:

(3.8)

Для этого строится таблица


1
…	…	…	…	…
n
Σ

Из системы 3.8 находим коэффициенты и (необходимо выразить ).

Источник

Содержание

Выполнение аппроксимации
- Способ 1: линейное сглаживание
- Способ 2: экспоненциальная аппроксимация
- Способ 3: логарифмическое сглаживание
- Способ 4: полиномиальное сглаживание
- Способ 5: степенное сглаживание
Вопросы и ответы

Аппроксимация в Microsoft Excel

Среди различных методов прогнозирования нельзя не выделить аппроксимацию. С её помощью можно производить приблизительные подсчеты и вычислять планируемые показатели, путем замены исходных объектов на более простые. В Экселе тоже существует возможность использования данного метода для прогнозирования и анализа. Давайте рассмотрим, как этот метод можно применить в указанной программе встроенными инструментами.

Выполнение аппроксимации

Наименование данного метода происходит от латинского слова proxima – «ближайшая» Именно приближение путем упрощения и сглаживания известных показателей, выстраивание их в тенденцию и является его основой. Но данный метод можно использовать не только для прогнозирования, но и для исследования уже имеющихся результатов. Ведь аппроксимация является, по сути, упрощением исходных данных, а упрощенный вариант исследовать легче.

Главный инструмент, с помощью которого проводится сглаживания в Excel – это построение линии тренда. Суть состоит в том, что на основе уже имеющихся показателей достраивается график функции на будущие периоды. Основное предназначение линии тренда, как не трудно догадаться, это составление прогнозов или выявление общей тенденции.

Но она может быть построена с применением одного из пяти видов аппроксимации:

Линейной;
Экспоненциальной;
Логарифмической;
Полиномиальной;
Степенной.

Рассмотрим каждый из вариантов более подробно в отдельности.

Урок: Как построить линию тренда в Excel

Способ 1: линейное сглаживание

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

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

Для построения графика, прежде всего, выделяем столбцы «Себестоимость единицы продукции» и «Прибыль». После этого перемещаемся во вкладку «Вставка». Далее на ленте в блоке инструментов «Диаграммы» щелкаем по кнопке «Точечная». В открывшемся списке выбираем наименование «Точечная с гладкими кривыми и маркерами». Именно данный вид диаграмм наиболее подходит для работы с линией тренда, а значит, и для применения метода аппроксимации в Excel.

Построение диаграммы в Microsoft Excel

График построен.

График построен в Microsoft Excel

Для добавления линии тренда выделяем его кликом правой кнопки мыши. Появляется контекстное меню. Выбираем в нем пункт «Добавить линию тренда…».

Существует ещё один вариант её добавления. В дополнительной группе вкладок на ленте «Работа с диаграммами» перемещаемся во вкладку «Макет». Далее в блоке инструментов «Анализ» щелкаем по кнопке «Линия тренда». Открывается список. Так как нам нужно применить линейную аппроксимацию, то из представленных позиций выбираем «Линейное приближение».

Добавление линии тренда через блок инструментов на ленте в Microsoft Excel

Если же вы выбрали все-таки первый вариант действий с добавлением через контекстное меню, то откроется окно формата.
В блоке параметров «Построение линии тренда (аппроксимация и сглаживание)» устанавливаем переключатель в позицию «Линейная».
При желании можно установить галочку около позиции «Показывать уравнение на диаграмме». После этого на диаграмме будет отображаться уравнение сглаживающей функции.

Также в нашем случае для сравнения различных вариантов аппроксимации важно установить галочку около пункта «Поместить на диаграмму величину достоверной аппроксимации (R^2)». Данный показатель может варьироваться от 0 до 1. Чем он выше, тем аппроксимация качественнее (достовернее). Считается, что при величине данного показателя 0,85 и выше сглаживание можно считать достоверным, а если показатель ниже, то – нет.

После того, как провели все вышеуказанные настройки. Жмем на кнопку «Закрыть», размещенную в нижней части окна.

Включение линейной аппроксимации в Microsoft Excel

Как видим, на графике линия тренда построена. При линейной аппроксимации она обозначается черной прямой полосой. Указанный вид сглаживания можно применять в наиболее простых случаях, когда данные изменяются довольно быстро и зависимость значения функции от аргумента очевидна.

Линия тренда построена с помощью линейной аппроксимации в Microsoft Excel

Сглаживание, которое используется в данном случае, описывается следующей формулой:

y=ax+b

В конкретно нашем случае формула принимает такой вид:

y=-0,1156x+72,255

Величина достоверности аппроксимации у нас равна 0,9418, что является довольно приемлемым итогом, характеризующим сглаживание, как достоверное.

Способ 2: экспоненциальная аппроксимация

Теперь давайте рассмотрим экспоненциальный тип аппроксимации в Эксель.

Для того, чтобы изменить тип линии тренда, выделяем её кликом правой кнопки мыши и в раскрывшемся меню выбираем пункт «Формат линии тренда…».

Переход в формат лини тренда в Microsoft Excel

После этого запускается уже знакомое нам окно формата. В блоке выбора типа аппроксимации устанавливаем переключатель в положение «Экспоненциальная». Остальные настройки оставим такими же, как и в первом случае. Щелкаем по кнопке «Закрыть».

Построение экспоненциальной линии тренда в Microsoft Excel

После этого линия тренда будет построена на графике. Как видим, при использовании данного метода она имеет несколько изогнутую форму. При этом уровень достоверности равен 0,9592, что выше, чем при использовании линейной аппроксимации. Экспоненциальный метод лучше всего использовать в том случае, когда сначала значения быстро изменяются, а потом принимают сбалансированную форму.

Экспоненциальная линия тренда построена в Microsoft Excel

Общий вид функции сглаживания при этом такой:

y=be^x

где e – это основание натурального логарифма.

В конкретно нашем случае формула приняла следующую форму:

y=6282,7*e^(-0,012*x)

Способ 3: логарифмическое сглаживание

Теперь настала очередь рассмотреть метод логарифмической аппроксимации.

Тем же способом, что и в предыдущий раз через контекстное меню запускаем окно формата линии тренда. Устанавливаем переключатель в позицию «Логарифмическая» и жмем на кнопку «Закрыть».

Включение логарифмической аппроксимации в Microsoft Excel

Происходит процедура построения линии тренда с логарифмической аппроксимацией. Как и в предыдущем случае, такой вариант лучше использовать тогда, когда изначально данные быстро изменяются, а потом принимают сбалансированный вид. Как видим, уровень достоверности равен 0,946. Это выше, чем при использовании линейного метода, но ниже, чем качество линии тренда при экспоненциальном сглаживании.

Логарифмическая линия тренда построена в Microsoft Excel

В общем виде формула сглаживания выглядит так:

y=a*ln(x)+b

где ln – это величина натурального логарифма. Отсюда и наименование метода.

В нашем случае формула принимает следующий вид:

y=-62,81ln(x)+404,96

Способ 4: полиномиальное сглаживание

Настал черед рассмотреть метод полиномиального сглаживания.

Переходим в окно формата линии тренда, как уже делали не раз. В блоке «Построение линии тренда» устанавливаем переключатель в позицию «Полиномиальная». Справа от данного пункта расположено поле «Степень». При выборе значения «Полиномиальная» оно становится активным. Здесь можно указать любое степенное значение от 2 (установлено по умолчанию) до 6. Данный показатель определяет число максимумов и минимумов функции. При установке полинома второй степени описывается только один максимум, а при установке полинома шестой степени может быть описано до пяти максимумов. Для начала оставим настройки по умолчанию, то есть, укажем вторую степень. Остальные настройки оставляем такими же, какими мы выставляли их в предыдущих способах. Жмем на кнопку «Закрыть».

Включение полиномиальной аппроксимации в Microsoft Excel

Линия тренда с использованием данного метода построена. Как видим, она ещё более изогнута, чем при использовании экспоненциальной аппроксимации. Уровень достоверности выше, чем при любом из использованных ранее способов, и составляет 0,9724.

Данный метод наиболее успешно можно применять в том случае, если данные носят постоянно изменчивый характер. Функция, описывающая данный вид сглаживания, выглядит таким образом:

y=a1+a1*x+a2*x^2+…+an*x^n

В нашем случае формула приняла такой вид:

y=0,0015*x^2-1,7202*x+507,01
Теперь давайте изменим степень полиномов, чтобы увидеть, будет ли отличаться результат. Возвращаемся в окно формата. Тип аппроксимации оставляем полиномиальным, но напротив него в окне степени устанавливаем максимально возможное значение – 6.

Включение полиномиальной аппроксимации в шестой степени в Microsoft Excel

Как видим, после этого наша линия тренда приняла форму ярко выраженной кривой, у которой число максимумов равно шести. Уровень достоверности повысился ещё больше, составив 0,9844.

Полиномиальная линия тренда в шестой степени в Microsoft Excel

Формула, которая описывает данный тип сглаживания, приняла следующий вид:

y=8E-08x^6-0,0003x^5+0,3725x^4-269,33x^3+109525x^2-2E+07x+2E+09

Способ 5: степенное сглаживание

В завершении рассмотрим метод степенной аппроксимации в Excel.

Перемещаемся в окно «Формат линии тренда». Устанавливаем переключатель вида сглаживания в позицию «Степенная». Показ уравнения и уровня достоверности, как всегда, оставляем включенными. Жмем на кнопку «Закрыть».

Полиномиальная линия тренда в шестой степени в Microsoft Excel

Программа формирует линию тренда. Как видим, в нашем случае она представляет собой линию с небольшим изгибом. Уровень достоверности равен 0,9618, что является довольно высоким показателем. Из всех вышеописанных способов уровень достоверности был выше только при использовании полиномиального метода.

Степенная линия тренда построена в Microsoft Excel

Данный способ эффективно используется в случаях интенсивного изменения данных функции. Важно учесть, что этот вариант применим только при условии, что функция и аргумент не принимают отрицательных или нулевых значений.

Общая формула, описывающая данный метод имеет такой вид:

y=bx^n

В конкретно нашем случае она выглядит так:

y = 6E+18x^(-6,512)

Как видим, при использовании конкретных данных, которые мы применяли для примера, наибольший уровень достоверности показал метод полиномиальной аппроксимации с полиномом в шестой степени (0,9844), наименьший уровень достоверности у линейного метода (0,9418). Но это совсем не значит, что такая же тенденция будет при использовании других примеров. Нет, уровень эффективности у приведенных выше методов может значительно отличаться, в зависимости от конкретного вида функции, для которой будет строиться линия тренда. Поэтому, если для этой функции выбранный метод наиболее эффективен, то это совсем не означает, что он также будет оптимальным и в другой ситуации.

Если вы пока не можете сразу определить, основываясь на вышеприведенных рекомендациях, какой вид аппроксимации подойдет конкретно в вашем случае, то есть смысл попробовать все методы. После построения линии тренда и просмотра её уровня достоверности можно будет выбрать оптимальный вариант.

Источник

Построить аппроксимацию входных данных с учётом их погрешностей

04.03.2021, 02:16. Показов 687. Ответов 9

Доброго времени суток!
Имеется набор данных, условно, х и у. Все данные сняты экспериментально, поэтому имеют как инструментальную, так и случайную погрешность, которые оценочными (немного кустарными, но не суть) формулами сводятся к общему понятию «погрешность величины х» или «погрешность величины у».
Для каждой точки набора данных погрешность своя (причём и по х, и по у).

Пример такого набора , а так же график (рис.1), который, возможно, прояснит ситуацию лучше:

Matlab M

clear
clc
 
%Задаём
func = @(x) (150.*x + 20);
x = [0:1:5]';
y = func(x);
 
%Зашумляем
to_approx_x = x + (rand([size(x, 1), 1]).*(0.7 + 0.2)) + (-0.2);
to_approx_y = y + ((rand([size(y, 1), 1]).*(50 + 14)) + (-14)).*rand([size(y, 1), 1]).*5;
 
%Задаём вектор "измернной погрешности"
sigma_x = abs((rand([size(x, 1), 1]).*(0.7 + 0.2)) + (-0.2));
sigma_y = abs((rand([size(y, 1), 1]).*(50 + 14)) + (-14)).*5;
 
%Демонстрируем, что имеем с "эксперимента": 
figure
hold on
err = errorbar(to_approx_x, to_approx_y, -sigma_y, sigma_y, -sigma_x, sigma_x, '.');
h = plot(to_approx_x, to_approx_y, 'r.');
grid on
 
xlabel ('Ось данных х');
ylabel ('Ось данных y');

В данном случае, конечно, генерация данных произведена искусственно с помощью кода, а не снята ручками в лаборатории

Итак, после того, как описаны начальные условия задачи, переходим к сути вопроса.
Необходимо построить аппроксимацию данных с учётом их погрешностей.
То есть, например, известно, что данные в теории ложатся на кривую, описываемую функцией: f(x) = a/x + b. Или, например, строится калибровочная кривая при помощи полинома (рис.2). Все эти построения производятся с помощью аппроксимации заданного набора какой-то заданной функцией.

Лично я делаю это в cftool. Но, к сожалению, он делает это по МНК. А в этот метод никак (как я смог понять) нельзя передать погрешности измерений, только измерения. При этом манящий раздел параметров weights — всего лишь возможность после первой аппроксимации минимизировать сумму вида:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?sum (W(i) * (y(i) - y_{fit}(i))^2)$

Загнав во второй проход в графу weights вектор W.
(источник: https://www.mathworks.com/supp… ion&page=1)

То есть никакого обозримого учёта погрешности исходных данных нет, что влияет на выдаваемую матлабом погрешность вычисления параметров a и b или погрешность определённых по калибровочной кривой данных.

Соответственно, стоит вопрос — как учесть погрешность исходных данных при построении аппроксимационной модели?

И теперь коротко для тех, кто потерялся:
1. Есть данные x, y определённые с погрешностью.
2. Нужно построить аппроксимацию какой-то заданной функцией f(x) этих y и х.
3. Как при аппроксимации учесть погрешность исходных данных?

P.S.: Если это делается какой-то одной командой или чем-то красивым, как cftool, то будет вообще здорово

Миниатюры

Построить аппроксимацию входных данных с учётом их погрешностей

__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь

Источник

From Wikipedia, the free encyclopedia

Stochastic approximation methods are a family of iterative methods typically used for root-finding problems or for optimization problems. The recursive update rules of stochastic approximation methods can be used, among other things, for solving linear systems when the collected data is corrupted by noise, or for approximating extreme values of functions which cannot be computed directly, but only estimated via noisy observations.

In a nutshell, stochastic approximation algorithms deal with a function of the form ${textstyle f(theta )=operatorname {E} _{xi }[F(theta ,xi )]}$
which is the expected value of a function depending on a random variable ${textstyle xi }$ . The goal is to recover properties of such a function ${textstyle f}$ without evaluating it directly. Instead, stochastic approximation algorithms use random samples of ${textstyle F(theta ,xi )}$ to efficiently approximate properties of ${textstyle f}$ such as zeros or extrema.

Recently, stochastic approximations have found extensive applications in the fields of statistics and machine learning, especially in settings with big data. These applications range from stochastic optimization methods and algorithms, to online forms of the EM algorithm, reinforcement learning via temporal differences, and deep learning, and others.^[1]
Stochastic approximation algorithms have also been used in the social sciences to describe collective dynamics: fictitious play in learning theory and consensus algorithms can be studied using their theory.^[2]

The earliest, and prototypical, algorithms of this kind are the Robbins–Monro and Kiefer–Wolfowitz algorithms introduced respectively in 1951 and 1952.

Robbins–Monro algorithm[edit]

The Robbins–Monro algorithm, introduced in 1951 by Herbert Robbins and Sutton Monro,^[3] presented a methodology for solving a root finding problem, where the function is represented as an expected value. Assume that we have a function ${textstyle M(theta )}$ , and a constant ${textstyle alpha }$ , such that the equation ${textstyle M(theta )=alpha }$ has a unique root at ${textstyle theta ^{*}}$ . It is assumed that while we cannot directly observe the function ${textstyle M(theta )}$ , we can instead obtain measurements of the random variable ${textstyle N(theta )}$ where ${textstyle operatorname {E} [N(theta )]=M(theta )}$ . The structure of the algorithm is to then generate iterates of the form:

${displaystyle theta _{n+1}=theta _{n}-a_{n}(N(theta _{n})-alpha )}$

Here, $a_{1},a_{2},dots$ is a sequence of positive step sizes. Robbins and Monro proved^[3]^{, Theorem 2} that $theta_n$ converges in $L^{2}$ (and hence also in probability) to $theta^*$ , and Blum^[4] later proved the convergence is actually with probability one, provided that:

$qquad sum _{{n=0}}^{{infty }}a_{n}=infty quad {mbox{ and }}quad sum _{{n=0}}^{{infty }}a_{n}^{2}<infty quad$

A particular sequence of steps which satisfy these conditions, and was suggested by Robbins–Monro, have the form: ${textstyle a_{n}=a/n}$ , for ${textstyle a>0}$ . Other series are possible but in order to average out the noise in ${textstyle N(theta )}$ , the above condition must be met.

Complexity results[edit]

If ${textstyle f(theta )}$ is twice continuously differentiable, and strongly convex, and the minimizer of ${textstyle f(theta )}$ belongs to the interior of ${textstyle Theta }$ , then the Robbins–Monro algorithm will achieve the asymptotically optimal convergence rate, with respect to the objective function, being ${textstyle operatorname {E} [f(theta _{n})-f^{*}]=O(1/n)}$ , where ${textstyle f^{*}}$ is the minimal value of ${textstyle f(theta )}$ over ${textstyle theta in Theta }$ .^[5]^[6]
Conversely, in the general convex case, where we lack both the assumption of smoothness and strong convexity, Nemirovski and Yudin^[7] have shown that the asymptotically optimal convergence rate, with respect to the objective function values, is ${textstyle O(1/{sqrt {n}})}$ . They have also proven that this rate cannot be improved.

Subsequent developments and Polyak–Ruppert averaging[edit]

While the Robbins–Monro algorithm is theoretically able to achieve ${textstyle O(1/n)}$ under the assumption of twice continuous differentiability and strong convexity, it can perform quite poorly upon implementation. This is primarily due to the fact that the algorithm is very sensitive to the choice of the step size sequence, and the supposed asymptotically optimal step size policy can be quite harmful in the beginning.^[6]^[8]

Chung (1954)^[9] and Fabian (1968)^[10] showed that we would achieve optimal convergence rate ${textstyle O(1/{sqrt {n}})}$ with ${textstyle a_{n}=bigtriangledown ^{2}f(theta ^{*})^{-1}/n}$ (or ${textstyle a_{n}={frac {1}{(nM'(theta ^{*}))}}}$ ). Lai and Robbins^[11]^[12] designed adaptive procedures to estimate ${textstyle M'(theta ^{*})}$ such that ${textstyle theta _{n}}$ has minimal asymptotic variance. However the application of such optimal methods requires much a priori information which is hard to obtain in most situations. To overcome this shortfall, Polyak (1991)^[13] and Ruppert (1988)^[14] independently developed a new optimal algorithm based on the idea of averaging the trajectories. Polyak and Juditsky^[15] also presented a method of accelerating Robbins–Monro for linear and non-linear root-searching problems through the use of longer steps, and averaging of the iterates. The algorithm would have the following structure:

${displaystyle theta _{n+1}-theta _{n}=a_{n}(alpha -N(theta _{n})),qquad {bar {theta }}_{n}={frac {1}{n}}sum _{i=0}^{n-1}theta _{i}}$

The convergence of ${displaystyle {bar {theta }}_{n}}$ to the unique root $theta^*$ relies on the condition that the step sequence ${a_{n}}$ decreases sufficiently slowly. That is

A1)

${displaystyle a_{n}rightarrow 0,qquad {frac {a_{n}-a_{n+1}}{a_{n}}}=o(a_{n})}$

Therefore, the sequence ${textstyle a_{n}=n^{-alpha }}$ with ${textstyle 0<alpha <1}$ satisfies this restriction, but ${textstyle alpha =1}$ does not, hence the longer steps. Under the assumptions outlined in the Robbins–Monro algorithm, the resulting modification will result in the same asymptotically optimal convergence rate ${textstyle O(1/{sqrt {n}})}$ yet with a more robust step size policy.^[15] Prior to this, the idea of using longer steps and averaging the iterates had already been proposed by Nemirovski and Yudin^[16] for the cases of solving the stochastic optimization problem with continuous convex objectives and for convex-concave saddle point problems. These algorithms were observed to attain the nonasymptotic rate ${textstyle O(1/{sqrt {n}})}$ .

A more general result is given in Chapter 11 of Kushner and Yin^[17] by defining interpolated time ${textstyle t_{n}=sum _{i=0}^{n-1}a_{i}}$ , interpolated process ${textstyle theta ^{n}(cdot )}$ and interpolated normalized process ${textstyle U^{n}(cdot )}$ as

${displaystyle theta ^{n}(t)=theta _{n+i},quad U^{n}(t)=(theta _{n+i}-theta ^{*})/{sqrt {a_{n+i}}}quad {mbox{for}}quad tin [t_{n+i}-t_{n},t_{n+i+1}-t_{n}),igeq 0}$

Let the iterate average be ${displaystyle Theta _{n}={frac {a_{n}}{t}}sum _{i=n}^{n+t/a_{n}-1}theta _{i}}$ and the associate normalized error to be ${displaystyle {hat {U}}^{n}(t)={frac {sqrt {a_{n}}}{t}}sum _{i=n}^{n+t/a_{n}-1}(theta _{i}-theta ^{*})}$ .

With assumption A1) and the following A2)

A2) There is a Hurwitz matrix ${textstyle A}$ and a symmetric and positive-definite matrix ${textstyle Sigma }$ such that ${textstyle {U^{n}(cdot )}}$ converges weakly to ${textstyle U(cdot )}$ , where ${textstyle U(cdot )}$ is the statisolution to

${displaystyle dU=AU,dt+Sigma ^{1/2},dw}$

where ${textstyle w(cdot )}$ is a standard Wiener process.

satisfied, and define ${textstyle {bar {V}}=(A^{-1})'Sigma (A')^{-1}}$ . Then for each ${textstyle t}$ ,

${displaystyle {hat {U}}^{n}(t){stackrel {mathcal {D}}{longrightarrow }}{mathcal {N}}(0,V_{t}),quad {text{where}}quad V_{t}={bar {V}}/t+O(1/t^{2}).}$

The success of the averaging idea is because of the time scale separation of the original sequence ${textstyle {theta _{n}}}$ and the averaged sequence ${textstyle {Theta _{n}}}$ , with the time scale of the former one being faster.

Application in stochastic optimization[edit]

Suppose we want to solve the following stochastic optimization problem

${displaystyle g(theta ^{*})=min _{theta in Theta }operatorname {E} [Q(theta ,X)],}$

where ${textstyle g(theta )=operatorname {E} [Q(theta ,X)]}$ is differentiable and convex, then this problem is equivalent to find the root $theta^*$ of ${displaystyle nabla g(theta )=0}$ . Here ${displaystyle Q(theta ,X)}$ can be interpreted as some «observed» cost as a function of the chosen $theta$ and random effects $X$ . In practice, it might be hard to get an analytical form of ${displaystyle nabla g(theta )}$ , Robbins–Monro method manages to generate a sequence ${displaystyle (theta _{n})_{ngeq 0}}$ to approximate $theta^*$ if one can generate ${displaystyle (X_{n})_{ngeq 0}}$ , in which the conditional expectation of ${displaystyle X_{n}}$ given ${displaystyle theta _{n}}$ is exactly ${displaystyle nabla g(theta _{n})}$ , i.e. $X_{n}$ is simulated from a conditional distribution defined by

${displaystyle operatorname {E} [H(theta ,X)|theta =theta _{n}]=nabla g(theta _{n}).}$

Here ${displaystyle H(theta ,X)}$ is an unbiased estimator of ${displaystyle nabla g(theta )}$ . If $X$ depends on $theta$ , there is in general no natural way of generating a random outcome ${displaystyle H(theta ,X)}$ that is an unbiased estimator of the gradient. In some special cases when either IPA or likelihood ratio methods are applicable, then one is able to obtain an unbiased gradient estimator ${displaystyle H(theta ,X)}$ . If $X$ is viewed as some «fundamental» underlying random process that is generated independently of $theta$ , and under some regularization conditions for derivative-integral interchange operations so that ${displaystyle operatorname {E} {Big [}{frac {partial }{partial theta }}Q(theta ,X){Big ]}=nabla g(theta )}$ , then ${displaystyle H(theta ,X)={frac {partial }{partial theta }}Q(theta ,X)}$ gives the fundamental gradient unbiased estimate. However, for some applications we have to use finite-difference methods in which ${displaystyle H(theta ,X)}$ has a conditional expectation close to ${displaystyle nabla g(theta )}$ but not exactly equal to it.

We then define a recursion analogously to Newton’s Method in the deterministic algorithm:

${displaystyle theta _{n+1}=theta _{n}-varepsilon _{n}H(theta _{n},X_{n+1}).}$

Convergence of the algorithm[edit]

The following result gives sufficient conditions on ${displaystyle theta _{n}}$ for the algorithm to converge:^[18]

C1) ${displaystyle varepsilon _{n}geq 0,forall ;ngeq 0.}$

C2) ${displaystyle sum _{n=0}^{infty }varepsilon _{n}=infty }$

C3) ${displaystyle sum _{n=0}^{infty }varepsilon _{n}^{2}<infty }$

C4) ${displaystyle |X_{n}|leq B,{text{ for a fixed bound }}B.}$

C5) ${displaystyle g(theta ){text{ is strictly convex, i.e.}}}$

${displaystyle inf _{delta leq |theta -theta ^{*}|leq 1/delta }langle theta -theta ^{*},nabla g(theta )rangle >0,{text{ for every }}0<delta <1.}$

Then ${displaystyle theta _{n}}$ converges to ${displaystyle theta ^{*}}$ almost surely.

Here are some intuitive explanations about these conditions. Suppose ${displaystyle H(theta _{n},X_{n+1})}$ is a uniformly bounded random variables. If C2) is not satisfied, i.e. ${displaystyle sum _{n=0}^{infty }varepsilon _{n}<infty }$ , then

${displaystyle theta _{n}-theta _{0}=-sum _{i=0}^{n-1}varepsilon _{i}H(theta _{i},X_{i+1})}$

is a bounded sequence, so the iteration cannot converge to ${displaystyle theta ^{*}}$ if the initial guess ${displaystyle theta _{0}}$ is too far away from ${displaystyle theta ^{*}}$ . As for C3) note that if ${displaystyle theta _{n}}$ converges to ${displaystyle theta ^{*}}$ then

${displaystyle theta _{n+1}-theta _{n}=-varepsilon _{n}H(theta _{n},X_{n+1})rightarrow 0,{text{ as }}nrightarrow infty .}$

so we must have ${displaystyle varepsilon _{n}downarrow 0}$ ，and the condition C3) ensures it. A natural choice would be ${displaystyle varepsilon _{n}=1/n}$ . Condition C5) is a fairly stringent condition on the shape of $g(theta)$ ; it gives the search direction of the algorithm.

Example (where the stochastic gradient method is appropriate)^[8][edit]

Suppose ${displaystyle Q(theta ,X)=f(theta )+theta ^{T}X}$ , where $f$ is differentiable and ${displaystyle Xin mathbb {R} ^{p}}$ is a random variable independent of $theta$ . Then ${displaystyle g(theta )=operatorname {E} [Q(theta ,X)]=f(theta )+theta ^{T}operatorname {E} X}$ depends on the mean of $X$ , and the stochastic gradient method would be appropriate in this problem. We can choose ${displaystyle H(theta ,X)={frac {partial }{partial theta }}Q(theta ,X)={frac {partial }{partial theta }}f(theta )+X.}$

Kiefer–Wolfowitz algorithm[edit]

The Kiefer–Wolfowitz algorithm was introduced in 1952 by Jacob Wolfowitz and Jack Kiefer,^[19] and was motivated by the publication of the Robbins–Monro algorithm. However, the algorithm was presented as a method which would stochastically estimate the maximum of a function. Let $M(x)$ be a function which has a maximum at the point $theta$ . It is assumed that $M(x)$ is unknown; however, certain observations $N(x)$ , where ${displaystyle operatorname {E} [N(x)]=M(x)}$ , can be made at any point $x$ . The structure of the algorithm follows a gradient-like method, with the iterates being generated as follows:

${displaystyle x_{n+1}=x_{n}+a_{n}{bigg (}{frac {N(x_{n}+c_{n})-N(x_{n}-c_{n})}{2c_{n}}}{bigg )}}$

where ${displaystyle N(x_{n}+c_{n})}$ and ${displaystyle N(x_{n}-c_{n})}$ are independent, and the gradient of $M(x)$ is approximated using finite differences. The sequence ${c_{n}}$ specifies the sequence of finite difference widths used for the gradient approximation, while the sequence ${a_{n}}$ specifies a sequence of positive step sizes taken along that direction. Kiefer and Wolfowitz proved that, if $M(x)$ satisfied certain regularity conditions, then $x_{n}$ will converge to $theta$ in probability as ${displaystyle nto infty }$ , and later Blum^[4] in 1954 showed $x_{n}$ converges to $theta$ almost surely, provided that:

A suitable choice of sequences, as recommended by Kiefer and Wolfowitz, would be $a_{n}=1/n$ and $c_{n}=n^{{-1/3}}$ .

Subsequent developments and important issues[edit]

The Kiefer Wolfowitz algorithm requires that for each gradient computation, at least $d+1$ different parameter values must be simulated for every iteration of the algorithm, where $d$ is the dimension of the search space. This means that when $d$ is large, the Kiefer–Wolfowitz algorithm will require substantial computational effort per iteration, leading to slow convergence.
1. To address this problem, Spall proposed the use of simultaneous perturbations to estimate the gradient. This method would require only two simulations per iteration, regardless of the dimension $d$ .^[20]
In the conditions required for convergence, the ability to specify a predetermined compact set that fulfills strong convexity (or concavity) and contains the unique solution can be difficult to find. With respect to real world applications, if the domain is quite large, these assumptions can be fairly restrictive and highly unrealistic.

Further developments[edit]

An extensive theoretical literature has grown up around these algorithms, concerning conditions for convergence, rates of convergence, multivariate and other generalizations, proper choice of step size, possible noise models, and so on.^[21]^[22] These methods are also applied in control theory, in which case the unknown function which we wish to optimize or find the zero of may vary in time. In this case, the step size $a_{n}$ should not converge to zero but should be chosen so as to track the function.^[21]^{, 2nd ed., chapter 3}

C. Johan Masreliez and R. Douglas Martin were the first to apply
stochastic approximation to robust estimation.^[23]

The main tool for analyzing stochastic approximations algorithms (including the Robbins–Monro and the Kiefer–Wolfowitz algorithms) is a theorem by Aryeh Dvoretzky published in the proceedings of the third Berkeley symposium on mathematical statistics and probability, 1956.^[24]

References[edit]

^ Toulis, Panos; Airoldi, Edoardo (2015). «Scalable estimation strategies based on stochastic approximations: classical results and new insights». Statistics and Computing. 25 (4): 781–795. doi:10.1007/s11222-015-9560-y. PMC 4484776. PMID 26139959.
^ Le Ny, Jerome. «Introduction to Stochastic Approximation Algorithms» (PDF). Polytechnique Montreal. Teaching Notes. Retrieved 16 November 2016.
^ ^a ^b Robbins, H.; Monro, S. (1951). «A Stochastic Approximation Method». The Annals of Mathematical Statistics. 22 (3): 400. doi:10.1214/aoms/1177729586.
^ ^a ^b Blum, Julius R. (1954-06-01). «Approximation Methods which Converge with Probability one». The Annals of Mathematical Statistics. 25 (2): 382–386. doi:10.1214/aoms/1177728794. ISSN 0003-4851.
^ Sacks, J. (1958). «Asymptotic Distribution of Stochastic Approximation Procedures». The Annals of Mathematical Statistics. 29 (2): 373–405. doi:10.1214/aoms/1177706619. JSTOR 2237335.
^ ^a ^b Nemirovski, A.; Juditsky, A.; Lan, G.; Shapiro, A. (2009). «Robust Stochastic Approximation Approach to Stochastic Programming». SIAM Journal on Optimization. 19 (4): 1574. doi:10.1137/070704277.
^ Problem Complexity and Method Efficiency in Optimization, A. Nemirovski and D. Yudin, Wiley -Intersci. Ser. Discrete Math 15 John Wiley New York (1983) .
^ ^a ^b Introduction to Stochastic Search and Optimization: Estimation, Simulation and Control, J.C. Spall, John Wiley Hoboken, NJ, (2003).
^ Chung, K. L. (1954-09-01). «On a Stochastic Approximation Method». The Annals of Mathematical Statistics. 25 (3): 463–483. doi:10.1214/aoms/1177728716. ISSN 0003-4851.
^ Fabian, Vaclav (1968-08-01). «On Asymptotic Normality in Stochastic Approximation». The Annals of Mathematical Statistics. 39 (4): 1327–1332. doi:10.1214/aoms/1177698258. ISSN 0003-4851.
^ Lai, T. L.; Robbins, Herbert (1979-11-01). «Adaptive Design and Stochastic Approximation». The Annals of Statistics. 7 (6): 1196–1221. doi:10.1214/aos/1176344840. ISSN 0090-5364.
^ Lai, Tze Leung; Robbins, Herbert (1981-09-01). «Consistency and asymptotic efficiency of slope estimates in stochastic approximation schemes». Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete. 56 (3): 329–360. doi:10.1007/BF00536178. ISSN 0044-3719. S2CID 122109044.
^ Polyak, B T (1990-01-01). «New stochastic approximation type procedures. (In Russian.)». 7 (7).
^ Ruppert, D. «Efficient estimators from a slowly converging robbins-monro process».
^ ^a ^b Polyak, B. T.; Juditsky, A. B. (1992). «Acceleration of Stochastic Approximation by Averaging». SIAM Journal on Control and Optimization. 30 (4): 838. doi:10.1137/0330046.
^ On Cezari’s convergence of the steepest descent method for approximating saddle points of convex-concave functions, A. Nemirovski and D. Yudin, Dokl. Akad. Nauk SSR 2939, (1978 (Russian)), Soviet Math. Dokl. 19 (1978 (English)).
^ Kushner, Harold; George Yin, G. (2003-07-17). Stochastic Approximation and Recursive Algorithms and | Harold Kushner | Springer. www.springer.com. ISBN 9780387008943. Retrieved 2016-05-16.
^ Bouleau, N.; Lepingle, D. (1994). Numerical Methods for stochastic Processes. New York: John Wiley. ISBN 9780471546412.
^ Kiefer, J.; Wolfowitz, J. (1952). «Stochastic Estimation of the Maximum of a Regression Function». The Annals of Mathematical Statistics. 23 (3): 462. doi:10.1214/aoms/1177729392.
^ Spall, J. C. (2000). «Adaptive stochastic approximation by the simultaneous perturbation method». IEEE Transactions on Automatic Control. 45 (10): 1839–1853. doi:10.1109/TAC.2000.880982.
^ ^a ^b Kushner, H. J.; Yin, G. G. (1997). Stochastic Approximation Algorithms and Applications. doi:10.1007/978-1-4899-2696-8. ISBN 978-1-4899-2698-2.
^ Stochastic Approximation and Recursive Estimation, Mikhail Borisovich Nevel’son and Rafail Zalmanovich Has’minskiĭ, translated by Israel Program for Scientific Translations and B. Silver, Providence, RI: American Mathematical Society, 1973, 1976. ISBN 0-8218-1597-0.
^ Martin, R.; Masreliez, C. (1975). «Robust estimation via stochastic approximation». IEEE Transactions on Information Theory. 21 (3): 263. doi:10.1109/TIT.1975.1055386.
^ Dvoretzky, Aryeh (1956-01-01). «On Stochastic Approximation». The Regents of the University of California.

Источник

From Wikipedia, the free encyclopedia

The earliest, and prototypical, algorithms of this kind are the Robbins–Monro and Kiefer–Wolfowitz algorithms introduced respectively in 1951 and 1952.

Robbins–Monro algorithm[edit]

${displaystyle theta _{n+1}=theta _{n}-a_{n}(N(theta _{n})-alpha )}$

$qquad sum _{{n=0}}^{{infty }}a_{n}=infty quad {mbox{ and }}quad sum _{{n=0}}^{{infty }}a_{n}^{2}<infty quad$

Complexity results[edit]

If ${textstyle f(theta )}$ is twice continuously differentiable, and strongly convex, and the minimizer of ${textstyle f(theta )}$ belongs to the interior of ${textstyle Theta }$ , then the Robbins–Monro algorithm will achieve the asymptotically optimal convergence rate, with respect to the objective function, being ${textstyle operatorname {E} [f(theta _{n})-f^{*}]=O(1/n)}$ , where ${textstyle f^{*}}$ is the minimal value of ${textstyle f(theta )}$ over ${textstyle theta in Theta }$ .^[5]^[6]
Conversely, in the general convex case, where we lack both the assumption of smoothness and strong convexity, Nemirovski and Yudin^[7] have shown that the asymptotically optimal convergence rate, with respect to the objective function values, is ${textstyle O(1/{sqrt {n}})}$ . They have also proven that this rate cannot be improved.