Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Метод парабол






 
 

Рассмотрим алгоритм квадратичной интерполяции или метод парабол, т.е. в качестве аппроксимирующей функции используется парабола. Для однозначного задания параболы необходимы три точки. Пусть имеются три точки, для кот–х вып–ся 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.


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.005 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал