Элементы теории погрешностей. Интерполяция и аппроксимация функций

Наиболее простым способом сужения интервала неопределенности является деление его на некоторое число равных частей с последующим вычислением значений целевой функции в точках разбиения. Пусть n - число элементарных отрезков, h = (b-a)/n - шаг разбиения. Вычисляют значения целевой функции yk = fk(x) в узлах xk = a + k h (k=0,1, … , n). Сравнивая полученные значения f(xk), среди них находят минимальное. В данном методе, который можно назвать методом перебора, основная трудность состоит в выборе n и оценке погрешности.

Более экономичным способом уточнения оптимального параметра является использование свойства унимодальности целевой функции, которое позволяет построить процесс сужения интервала неопределенности. Если оптимальное значение функции находится в точке xi, то из рисунка видно, что оптимальное значение функции может находиться в интервале [xi-1, xi+1], т.е. интервал неопределенности сужается до длины двух шагов. Если этот интервал слишком велик, то его можно снова уменьшить путем нового разбиения. Получится интервал, равный двум длинам нового шага разбиения, и т.д.

9.2 Метод золотого сечения

На каждом шаге, за исключением первого, вычисление значения функции f(x) производится лишь один раз. Эта точка называется золотым сечением и выбирается специальным образом.

Геометрическая идея метода:

На первом шаге процесса оптимизации внутри отрезка [a0, b0] выбирают две внутренние точки x1 и x2 и вычисляют значения целевой функции f(x1) и f(x2). Так как в данном случае f(x1) < f(x2), то очевидно, что минимум расположен на одном из прилегающих к x1 отрезков [a0, x1] или [x1, x2]. Поэтому отрезок [x2,b0] можно отбросить, сузив тем самым первоначальный интервал неопределенности.

Второй шаг проводится на отрезке [a1, b1], где a1 = a0 и b1 = x2. Нужно снова выбрать две внутренние точки, но одна из них (x1) осталась из предыдущего шага, поэтому достаточно вычислить лишь одну точку x3, вычислить значение f(x3) и провести сравнение. Так как здесь f(x3) > f(x1), то ясно, что минимум находится на отрезке [x3, b1]. Этот отрезок можно обозначить [a2, b2], снова выбрать одну внутреннюю точку и повторить процедуру сужения интервала неопределенности. Процесс оптимизации повторяется до тех пор, пока длина очередного отрезка [an, bn] не станет меньше заданной величины .

Вывод соотношения золотого сечения:

Пусть длина интервала неопределенности равна l, а точка деления делит его на части l1, l2 : l1 > l2, l = l1 + l2 .Золотое сечение интервала неопределенности выбирается так, чтобы длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка:

Из этого соотношения можно найти точку деления, определив отношение l2/l1 .Для этого

l12 = l2 * l l12 = l2 * (l1 + l2)

l22 + l1 * l2 - l12 = 0

Так как интерес представляет только положительное решение, то

Отсюда l1 0.618*l, l2 0.382*l.

На первом шаге исходный интервал неопределенности равен d0 = b0 - a0 .При этом x1 - a0 = b0 - x2 = 0.382*d0 и b0 - x1 = x2 - a0 = 0.618*d0.

После первого шага оптимизации получается новый интервал неопределенности d1 = b1 - a1 = x2 - a0 = 0.618*d0.

После второго шага оптимизации имеем d2 = b2 - a2 = b1 - x3 = 0.618*d1 = 0.6182 * d0.

Используя полученные соотношения, можно записать координаты точек деления y и z отрезка [ak,bk] на k+1 шаге оптимизации (y < z):

y = 0.618*ak + 0.382*bk : z = 0.382*ak + 0.618*bk.

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

dk = bk - ak = 0.618k * d0.

Процесс оптимизации заканчивается при выполнении условия dk < .При этом искомая величина лежит в интервале ak < xopt < bk. В качестве оптимального значения можно принять xopt = ak (или xopt = bk или xopt = (ak + bk)/2).

9.3 Метод наискорейшего спуска

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

2. Вычисление нормированного вектора-градиента в этой точке.

3. Определение направления поиска по формуле

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

5. Если выполняется условие:

,

то поиск прекращается и выводят полученные результаты. В противном случае выполняют этап 6.

6. За новое начальное приближение принимают найденную на этапе 4 точку ( = , = ) и расчеты повторяют с пункта 2.

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

h(k+1) = h(k) /z,

где z > 1. Условие окончания поиска при этом может быть записано в виде h(k) < .

Размещено на Allbest.ru