Метод кубической интерполяции

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

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

Стратегия поиска

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

Алгоритм

Шаг 1. Задать начальную точку х⁰,величину шага и малые положительные числа и .

Шаг 2. Вычислить производную .

Шаг 3. Проверить знак производной в точке х⁰:

а) если , вычислить , вплоть до точки х^M, в которой ;

б) если , вычислить , вплоть до точки х^M, в которой .

Шаг 4. Положить , и вычислить , , , .

Шаг 5. Найти точку минимума кубического интерполяционного полинома по формуле

где , ,

и значение .

Шаг 6. Проверить условие убывания:

а) если , перейти к шагу 7;

б) если , вычислять по формуле до тех пор,

пока не будет выполнено неравенство .

7. Проверить выполнение условий окончания:

, :

а) если оба условия выполнены, процедура закончена и ;

б) если хотя бы одно из условий не выполнено, положить либо , , если , либо , , если . Перейти к шагу 5.

Замечания.

1. На шагах 2 и 3 реализуется эвристическая процедура поиска границ интервала неопределенности, где изменение знака производной свидетельствует о переходе через точку минимума.

2. Формула, используемая на шаге 5, гарантирует, что точка не выйдет за границы интервала [х₁,х₂].

3. На шаге 6 проверяется, действительно ли точка является приближением к минимуму.

4. На шаге 7 из трех точек х₁, х₂, выбираются две, в которых знаки первых производных различны, после чего процедура кубической интерполяции повторяется.

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

Пример 6.7. Найти минимум функции методом кубической интерполяции.

1. Зададим х⁰=1; ; ; .

2. Вычислим ; .

3. Так как , то . Вычислим . Поэтому , M = 1.

4⁰. Положим , и вычислим

; ;

;

5⁰. Вычислим

; ;

; ; .

6⁰. Проверим условие убывания. Так как , то переходим к шагу 7.

7⁰. Проверим условие окончания: . Условие не выполняется. Так как справедливо , то ; . Переходим к шагу 5.

5¹. Вычислим , ; ; ; .

6¹. Проверим условие убывания. Так как , то переходим к шагу 7.

7¹. Проверим условия окончания: (выполняется) и (выполняется). Поэтому расчет окончен и . Точная координата точки минимума , откуда следует, что применение кубической интерполяции даёт лучший результат, чем применение квадратичной интерполяции.

Варианты заданий. Таблица 1.

№ варианта	Метод сканирования	Метод половинного деления	Метод золотого сечения	Метод кубической интерполяции
	Для функции: R(x)=DSin(Ax+C) найти максимум на следующем интервале: x	Найти безусловный минимум функции f(x) одной переменной, т.е. такую точку , что .
1.	= А=1,0; В=1,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,04	= А=1,0; В=1,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,04	= А=1,0; В=1,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,04	Найти минимум функции х⁰=1; ; ; .
2.	= А=1,0; В=2,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,05	= А=1,0; В=2,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,05	= А=1,0; В=2,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,05	Найти минимум функции х⁰=0,5; ; ; .
3.	= А=2,0; В=1,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,04	= А=2,0; В=1,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,04	= А=2,0; В=1,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,04	Найти минимум функции х⁰=0,5; ; ; .
4.	= А=1,0; В=1,0; С=2,0; D=2,0. Ошибка задается по х: ε =0,05	= А=1,0; В=1,0; С=2,0; D=2,0. Ошибка задается по х: ε =0,05	= А=1,0; В=1,0; С=2,0; D=2,0. Ошибка задается по х: ε =0,05	Найти минимум функции х⁰=1; ; ; .
5.	= А=2,0; В=2,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,04	= А=2,0; В=2,0; С=1,0; D=1,0. Ошибка задается по х: ε ε =0,04	= А=2,0; В=2,0; С=1,0; D=1,0. Ошибка задается по х: ε =0,04	Найти минимум функции х⁰=1; ; ; .
6.	= А=1,0; В=1,0; С=2,0; D=2,0. Ошибка задается по х: ε =0,04	= А=1,0; В=1,0; С=2,0; D=2,0. Ошибка задается по х: ε =0,04	= А=1,0; В=1,0; С=2,0; D=2,0. Ошибка задается по х: ε =0,04	Найти минимум функции х⁰=0,5; ; ; .
Продолжение таблицы 1.
7.	= А=1,0; В=2,0; С=1,0; D=2,0. Ошибка задается по х: ε =0,04	= А=1,0; В=2,0; С=1,0; D=2,0. Ошибка задается по х: ε =0,04	= А=1,0; В=2,0; С=1,0; D=2,0. Ошибка задается по х: ε =0,04	Найти минимум функции х⁰=1; ; ; .
8.	= А=2,0; В=1,0; С=2,0; D=1,0. Ошибка задается по х: ε =0,04	= А=2,0; В=1,0; С=2,0; D=1,0. Ошибка задается по х: ε =0,04	= А=2,0; В=1,0; С=2,0; D=1,0. Ошибка задается по х: ε =0,04	Найти минимум функции х⁰=1; ; ; .
9.	= А=3,0; В=1,0; С=2,0; D=1,0. Ошибка задается по х: ε =0,05	= А=3,0; В=1,0; С=2,0; D=1,0. Ошибка задается по х: ε =0,05	= А=3,0; В=1,0; С=2,0; D=1,0. Ошибка задается по х: ε =0,05	Найти минимум функции х⁰=1; ; ; .
10.	= А=4,0; В=1,0; С=1,0; D=2,0. Ошибка задается по х: ε =0,05	= А=4,0; В=1,0; С=1,0; D=2,0. Ошибка задается по х: ε =0,05	= А=4,0; В=1,0; С=1,0; D=2,0. Ошибка задается по х: ε =0,05	Найти минимум функции х⁰=1; ; ; .