Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Метод парабол
|
|
 |
Рассмотрим алгоритм квадратичной интерполяции или метод парабол, т.е. в качестве аппроксимирующей функции используется парабола. Для однозначного задания параболы необходимы три точки. Пусть имеются три точки, для кот–х вып–ся a< c< b, f (c) £ f (a), f (c) £ f (b). Так как [ a, b ] – отрезок неопределенности и f (x) – унимодальная функция, то найти такую точку c нетрудно. Парабола, проходящая через три точки (a, f (a)), (c, f (c)), (b, f (b)), имеет вид
Поскольку f – унимодальная функция, то хотя бы одно из неравенств f (c) £ f (a), f (c) £ f (b) строгое и, следовательно, коэф–т при старшем члене P(x) положителен. Тогда P (x) достигает минимума в точке
,
причем (a+c)/2 £ t£ (c+b)/2. Эта точка и выбирается в качестве точки очередного вычисления знач–я функции.
Если оказалось, что t=c, условимся в качестве точки очередного вычисления выбирать точку (a+c)/2. Итак, следующее вычисление проводится в точке
Определим новый отрезок неопределенности с лежащей внутри него точкой, для которой выполняются условия аналогичные условиям, которым удовлетворяла точка c. В силу унимодальности функции f и в зависимости от выполнения или невыполнения условий x< c, f (x)< f (c), f (x)= f (c)это будут отрезки с точкой внутри: [ a, c ] и x; [ x, b ] и c; [ x, c ] и (x + c)/2; [ a, x ] и c; [ c, b ] и x; [ c, x ] и (x + c)/2. Смотри рисунок. Далее строится парабола, определяется ее минимум, и т.д., до тех пор, пока длина отрезка неопределенности не удовлетворяет заданной точности.
Схема алгоритма:
 |
Шаг 1. Задаются a, c, b и e. Вычислить ya=f(a), yc=f(c), yb=f(b).
Шаг 2. Вычислить , y=f(x), где
Шаг 3. А) При x< c.
Если y< yc, то b=c, c=x, yb=yc, yc=y.
Если y> yc, то a=x, ya=y.
Если y=yc, то a=x, b=c, c=(x+c)/2, ya=y, yb=yc, yc=f(c).
Б) При x> c.
Если y< yc, то a=c, c=x, ya=yc, yc=y.
Если y> yc, то b=x, yb=y.
Если y=yc, то a=c, b=x, c=(x+c)/2, ya=yc, yb=y, yc=f(c).
Шаг 4. Если b-a£ e, то закончить поиск, положив 
, иначе перейти к шагу 2.