33 Вопрос

численное нахождения минимума униамадальной функции. метод золотого сечения

Численные методы поиска экстремумов функций одной переменной

Как было уже сказано, в общем случае функция     может иметь несколько экстремумов (минимумов или максимумов). Задача поиска экстремумов сводится к их локализации и уточнению значений   и  . В дальнейшем для функций одной переменной под экстремумом будем подразумевать минимумв точке экстремума. Все рассмотренные ниже численные методы предполагают, что локализация экстремумов каким-либо образом произведена (например, графически или аналитически) и задача численных методов будет состоять в уточнении полученных результатов с заданной точностью . Будем считать, что  [a,b], где a и b границы интервала поиска. В пределах отрезка [a,b] функция  необязательно непрерывная, могут существовать разрывы первого рода. Достаточно чтобы функция  на отрезке [a, b] была унимодальной, то есть, содержащей на указанном отрезке один минимум. ^Метод золотого сечения

Золотым сечением отрезка называется деление отрезка на две неравные части так, чтобы отношение длины всего отрезка к длине большей части равнялось отношению длины большей части к длине меньшей части отрезка. Золотое сечение отрезка [a, b] производится двумя точками  и  , где  . Точки x₁ и x₂ расположены симметрично относительно середины отрезка и выполняется  и  . Упражнение 6. Точка x₁ в свою очередь производит золотое сечение отрезка [a, x₂]. Аналогично точка x₂ производит золотое сечение отрезка [x₁, b]. Доказать это. Опираясь на это свойство золотого сечения, предложен следующий метод минимизации унимодальной функции  на отрезке [a, b]. Его суть - деление интервала поиска минимума по правилу золотого сечения, вычисление значения  в точках деления, сравнение значений и отбрасывание той части интервала, на которой заведомо отсутствует минимум. Точка x₁ производит золотое сечение [a, x₂], точка x₂ - золотое сечение отрезка [x₁. На каждом шаге длина нового интервала неопределенности равна 0,618 длины старого интервала и на каждом шаге вычисляется лишь одно значение, b]. Поэтому на оставшемся интервале нужно определить одну точку, производящую золотое сечение. Процесс деления продолжают до тех пор, пока длина интервала неопределенности не станет меньше заданной точности , а не два, как в методе деления отрезка пополам.  Упражнение 7. Найти наименьшее n, начиная с которого точность метода золотого сечения больше точности метода деления отрезка пополам в 2 раза, в 10 раз. Упражнение 8. Написать алгоритм описанного метода. Сравнение методов одномерной оптимизации показывает, что в большинстве случаев для гладких   метод квадратичной интерполяции дает заметный выигрыш во времени. При сложных  метод золотого сечения может давать существенный выигрыш во времени. Метод квадратичной интерполяции удобен тем, что обнаруживает как максимумы, так и минимумы  , причем даже за пределами первоначально заданного интервала поиска.

34 Вопрос интерполяция функции многочлен лагранжа Интерполяционный многочлен Лагранжа

"Пусть некоторая функция y=f(x) задана таблично:

i	xi	yi
0	x0	y0
1	x1	y1
.	.	.
.	.	.
.	.	.
n	xn	yn

Где x₀, x₁,..., x_n - узлы интерполяции. Причем, расстояние между узлами интерполяции произвольное.

В интерполировании находят значение функции в заданной точке x_k, принадлежащей отрезку [x₀;x_n], но x_k не совпадает ни с одним узлом интерполяции (x_k не равно x₀, x₁,...,x_n.)

Интерполяционную функцию подбирают из определенного класса функций. Часто такую функцию находят в виде интерполяционного многочлена F_n(x).

В качестве интерполяционного многочлена будем рассматривать интерполяционный многочлен Лагранжа L_n(x).

Многочлен Лагранжа строят следующим образом (24):

L_n(x)=l₀(x)+l₁(x)+l₂(x)+...+l_n(x), где l_i(x) вычисляется по следующей формуле (25):

Следовательно, интерполяционный многочлен Лагранжа для неравно отстающих узлов выглядит (26) [5]:

На практике данный способ реализуется следующим образом: используя формулу Лагранжа, найти приближенное значение функции:

i	xi	f(xi)
0	-1	-1,35078
1	-0,7	-0,14846
2	1,3	3,50988
3	2,5	16,13892
4	5,6	177,07487

в точке t=2,005 с помощью: