Метод квадратичной интерполяции

Этот метод основан на замене f(x) в промежутке квадратичной параболой, экстремум которой вычисляется аналитически. После приближенного нахождения экстремума (максимума или минимума) можно задать и повторить поиск. Таким образом, с помощью итерационной процедуры значение уточняется до получения его с заданной точностью. Алгоритм метода квадратичной интерполяции Задаем начальное приближение x0 вычисляем два смежных значения аргумента x1=x0−h и x2=x0+h Вычисляем три значения f(x0),f(x1) и f(x2) Находим коэффициенты параболы a,b,c (считая, что на указанном отрезке представляет собой параболу ax^2+bx+c) и по найденным коэффициентам вычисляем положение экстремума x*=−b/2a. 5. Проверяем условие |x*-x0|<ε. Если условие не выполняется, задаем x0=x* и идем к пункту 1. Если выполняется, считаем x* найденным с заданной точностью ε Легко показать,что

Примеры программ на языке BASIC, реализующие описанные выше мтеоды, можно найти в
Пример выполненного домашнего задания по теме №4

Методы многомерной минимизации

Общие сведения

Функция Ф(x,y) задает в трехмерном пространстве x,y,Ф некоторую поверхность. Рассмотрим рельеф этой поверхности,используя известные из топографии линии уровня. Для этого проведем равноотстоящие плоскости Ф=const и найдем линии их пересечения с поверхностью Ф(x,y); проекции этих линий на плоскость Oxy называются линиями уровня. Полученная в итоге картина напоминает топографическое изображение рельефа горизонталями. По виду линий уровня принято выделять три типа рельефа: Типы рельефа котловинный овражный неупорядоченный При котловинном рельефе линии уровня напоминают эллипсы:   В малой окрестности невырожденного минимума рельеф функции котловинный. Необходимые условия минимума функции двух переменных ∂Ф/∂x=0, ∂Ф/∂y=0 приводят к тому, что в разложении функции Ф(x,y) в окрестности минимума (x*,y*) отличными от нуля являются следующие члены: Ф(x,y)=Ф(x*,y*)+0,5Фxx(Δx)^2+ ФxyΔxΔy+0,5Фyy(Δy)^2+... причем квадратичная форма в правой части этого выражения - положительно определенная в окрестности минимума, что означает, что ее линии уровня представляют собой эллипсы. В окрестности максимума эта квадратичная форма отрицательно определенная, а в седловинах - знакопеременна. Вблизи такого минимума функция мало меняется при заметных изменениях переменных. Поэтому, даже если мы не очень точно определеим те значения переменных, которые должны минимизировать функцию, само значение функции при этом будет мало отличаться от минимального. При овражном типе рельефа на линиях уровня появляются участки с большой кривизной или точки излома. Геометричесукое место точек излома называют истинным оврагом, если угол направлен в сторону возрастания функции и гребнем, если в тсорону убывания:   Чаще встречается ситуация, в которой линии уровня всюду гладкие, однако на них имеются участки с большой кривизной; геометрические места точек с наибольшей кривизной называют разрешимыми оврагами или гребнями. В качестве примера можно привести рельеф функции Ф(x,y)=10(y-sinx)^2+0,1x^2, приведенный нпа следующем рисунке:   Рельеф, изображенный на этом рисунке, имеет ярко выраженный извилистый разрешимый овраг, "дно" которого - синусоида, а низшая точка - начало координат. В физических задачах овражный рельеф указывает на то, что вычислитель не учел какую-то закономерность, имеющую вид связи между переменными. Обнаружение и явный учет этой закономерности облегчают решение задачи. Так, если в приведенном выше примере ввести новые переменные ξ=x, η=y-sinx, то рельеф становится котловинным. Неупорядоченный тип рельефа характеризуется наличием многих максимумов, минимумов и седловин. Примером может служить функция Ф(x,y)=(1+sin^2x)(1+sin^2y):   На первый взгляд кажется, что для нахождения точки минимума функции Ф(x,y) можно просто решить систему нелинейных уравнений ∂Ф/∂x=0, ∂Ф/∂y=0 любым известным численным мтеодом (например, методом простых итераций) и затем отбросить те решения, которые являются седловинами или максимумами. Однако на практике эти методы обычно сходятся в настолько малой окрестности минимума, что выбрат ьполдходящее нулевое приближение удается далеко не всегда. Все эффективные методы поиска минимума функции многих переменных сводятся к выбору направления движения по склонам ко "дну"; разные методы отличаются способами выбора траектории спуска. На сегодняшний день пока не предложено метода, одинаково эффективного для всех типов рельефа; метод, приспособленный к одному типу рельефа, может оказаться плохим на рельефе другого типа. Общим для всех является необходимость выбора точки начального приближения (x0,y0) - то есть такой точки, из которой начинается спуск. После этого ищется следующая точка (x1,y1), значение функции в которой Ф(x1,y1) должно быть меньше значения функции в исходной точке Ф(x0,y0). Выбор начального прибилижения обычно представяле тсобой достаточно серьезную проблему, потому что