Билет№54Численные методы решения задач аппроксимации

.

Интерполяция является частным случаем аппроксимации.

Это - задача о нахождении такой аналитической функции L(x), которая принимает в точках (узлах) х_i заданные значения у_i. Иными словами, аппроксимирующая функция в случае интерполяции обязательно проходит через заданные точки.

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

В связи с интерполяцией рассматриваются три основные проблемы:

1. Выбор интерполяционной функции L(x).

2. Оценка погрешности интерполяции R(x)/

3. Размещение узлов интерполяции для обеспечения наивысшей возможной точности восстановления функции

Чаще всего в качестве интерполяционной функции используется полином n-степени (полиноминальная функция)

Это объясняется тем, что полином n-степени, содержащий n+1 параметр и проходящий через все заданные точки – единственный

 

24) Метод треугольника, трапеции, золотого сечения

Постановка задачи одномерной оптимизации

Задача одномерной оптимизации определяется следующим образом:

1. Допустимое множество — множество

2. Целевую функцию — отображение f:

3. Критерий поиска min, max

Метод деления пополам

Метод основан на последовательном сужении интервала, содержащего единственный корень уравнения F(x)=0 до тех пор, пока не будет достигнута заданная точность к.

Идея метода состоит в делении исходного промежутка изоляции корня [x_n, x_k] пополам точкой х_ср=(х_н+х_к)/2 и вычислении значений функции на левом конце f(x_ср) и в середине f(x_ср).

Алгоритм метода (рис. 8.4):

1. Определить новое приближение корня х в середине от
резка [a,b|: x^a+b)/^.

2. Найти значения функции в точках а и х: F(a) и F(x).

3. Проверить условие F(a)*F(x)<(). Если условие выполнено,
то корень расположен на отрезке (а,х|. В этом случае необходи
мо точку b переместить в точку х (Ь=х). Если условие не выпол
нено, то корень расположен на отрезке [х,Ь]. В этом случае необ
ходимо точку а переместить в точку х (а=х).

4. Перейти к пункту 1 и вновь поделить отрезок пополам.
Алгоритм продолжить до тех пор, пока не будет выполнено усло
вие I F(x) I <e.

Метод золотого сечения

Метод основан на делении текущего отрезка [а, Ь], где содержится искомый экстремум, на две неравные части, подчиняющиеся правилу золотого сечения, для определения следующего отрезка, содержащего максимум.

Золотое сечение определяется по правилу: отношение всего отрезка к большей его части равно отношению большей части отрезка к меньшей. Ему удовлетворяют две точки c u d, расположенные симметрично относительно середины отрезка.

Путем сравнения R(с) и R(d) определяют следующий отрезок, где содержится максимум. Если R(d) > R(c), то в качестве следующего отрезка выбирается отрезок [с, b], в противном случае — отрезок [a, d].

Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка d является и точкой золотого сечения отрезка [с, Ь], т.е.

Поэтому на каждой следующей итерации (кроме "запуска" метода на исходном отрезке) нужно вычислять только одно значение критерия оптимальности.

Существуют аналитические формулы для расчета новой точки на отрезке, где находится максимальное значение R(x), которую нетрудно получить:

Условие окончания поиска — величина отрезка, содержащего максимум, меньше заданной погрешности.

Метод обеспечивает более быструю сходимость к решению, чем многие другие методы, и применим, очевидно, только для одноэкстремаль-ных функций¹.

 

25) Метод сканирования

Метод сканирования

Метод заключается в последовательном переборе всех значений а < х < b с шагом ℮ (погрешность решения) с вычислением критерия оптимальности R в каждой точке. Путем выбора наибольшего из всех вычисленных значений R и находится решение задачи х*.

Достоинство метода в том, что можно найти глобальный максимум критерия, если R(х) — многоэкстремальная функция. К недостаткам данного метода относится значительное число повторных вычислений R(x), что в случае сложной функции R(x) требует существенных затрат времени.

На практике можно реализовать одну из осноных модификаций метода - последовательное уточнение решения, или сканирование с переменным шагомНа первом этапе сканирование осуществляют с крупным шагом, затем отрезок, внутри которого получено наибольшее значение R(x), разбивается на более мелкие отрезки, ищется новый отрезок, внутри которого находится уточненное значение максимума. Он (новый отрезок) опять делится на более мелкие и т.д., до тех пор, пока величина

отрезка, содержащего максимальное значение R(x), не будет меньше заданной погрешности. Главный недостаток этого варианта метода — возможность пропуска "острого" глобального максимума R(x).

 

26) Жизненный цикл, классификация