Читайте также:
|
Метод квадратичной интерполяции использует аппроксимацию целевой функции f(x) в окрестности точки минимума посредством квадратичной функции 
Известно, что минимум такой квадратичной функции имеет координаты:
(выражение для 
получено из уравнения 
)
Полагаем, что 
.
Выберем на отрезке унимодальности три точки: 
, так, что xmin 
.Этот отрезок должен быть достаточно мал, для того чтобы предположить, что на нем 
.
Вычислим значения f(x) в выбранных точках и на основании основного условия интерполяции получим следующие три равенства (или систему из трех нелинейных уравнений):
где 
Решая систему, находим A, B, C. Подставим полученные выражения в полученную выше формулу для :
где XM – приближенное значение xmin.
Рассмотрим, в чем заключается алгоритм поиска минимума функции методом квадратичной интерполяции.
Пусть f(x) – унимодальная функция, а величина t – некоторое приближенное значение точки минимум, принадлежащее отрезку унимодальности [a,b]. Выберем шаг h≈xmin-t. ε – заданная точность.
Рассмотрим процедуру поиска минимума по шагам:
1. Вычислим f(t) и f(t+h).
2. Если f(t)<f(t+h), то положим 
и вычислим f(x1), x2=t+h.
3. В противном случае положим x2=t+2h и вычислим f(x2), 
.
4. Используя точки t, x1, x2 вычислим XM, а затем f(XM). Таким образом, имеем значения функции в четырех точках.
5. Если |t- XM| < ε, то процедура поиска минимума завершена и xmin= XM.
6. Если процедура не завершена, то t= XM и происходит переход к п.3
Пример 1.6.4-1. Пусть требуется найти минимум функции f(x) = 2x2 – ex с точностью ε=0.01. Начальное значение t=1, h=0.5.
| n | xi | f(xi) |
| 1 x1 xm t x2 | 0.5 0.04 1.5 | -1.14872 -1.04372 -0.71828 0.018311 |
| 0.37459 0.5 0.04702 1.00 | -1.17370 -1.14872 -1.04372 -0.71828 | |
| 0.37890 0.37459 1.00 0.04702 | -1.17354 -1.17376 -0.71828 -1.04372 | |
| 0.35412 0.37890 0.37459 1.00 | -1.17412 -1.17354 -1.17376 -0.71828 |
Точность достигнута после 4-й итерации xmin=0.3545, f(xmin)=-1.17376.
(Четыре значения хi на каждой итерации соответствуют x1, xm, t,x2).
Дата добавления: 2015-07-20; просмотров: 459 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Метод золотого сечения | | | Метод касательных |