Методы прямого поиска.

Ряд методов минимизации основан на сравнении значений функции f , вычисляемых в точках х₁, х₂ … х_п . Эти методы часто называют методами прямого поиска, а точки x_i - пробными точками.

Будем считать, что требуется найти приближение к точке минимума унимодальной на отрезке [a, b] функции f . Предположим также, что число пробных точек п заранее фиксируется и за приближение к точке минимума принимается одна из этих точек.

Оптимальный пассивный поиск.

Задается правило вычисления сразу всех пробных точек х₁, х₂ … х_п и за принимается та точка х_к, для которой . Оценим погрешность этого метода. Для удобства примем х₀ = а, x_п+1 = b. В силу выбора точки = х_к справедливы неравенства f (x_k-1) > f (x_k) и f (x_k) > f (x_k+1) . В силу свойства 3 унимодальной функции следует, что . Значит,

 - x_k max{| x_k - x_k-1 | , | x_k+1 - x_k| } .

Так как положение точки минимума заранее неизвестно, то для справедлива следующая гарантированная оценка погрешности:

.

Можно показать, что величина, стоящая в правой части неравенства, станет минимальной, если точки х₁, х₂ … х_п расположить на отрезке [a,b] равномерно в соответствии с формулой х_i = a + ih , где h=(b-a) / n. Метод с таким выбором пробных точек называется оптимальным пассивным поиском.

13

Постановка задачи приближения функций.

…………

На практике постоянно приходится сталкиваться с вычислением значения функции y = f(x). Для элементарных, а также основных специальных функций алгоритмы вычисления включены в математическое обеспечение ЭВМ. Однако встречаются ситуации, когда непосредственное вычисление затруднено либо приводит к слишком большим затратам машинного времени. Укажем на некоторые типичные ситуации:

1. Функция f задана таблицей своих значений

y_i = f(x_i), i = 0, 1, 2, … , n, (27)

а вычисления проводятся в точках х_i, не совпадающих с табличными.

2. Непосредственное вычисление значения y = f(x) связано с проведением сложных расчетов и приводит к значительным затратам машинного времени, которые могут оказаться неприемлимыми, если функция f вычисляется многократно.

3. При заданном значении х значение f(x) находится из эксперимента. Такой способ вычисления в большинстве случаев нельзя использовать в вычислительных алгоритмах, т.к. он связан с необходимостью прерывания вычислительного процесса для проведения эксперимента. Исключение представляет случай, когда ЭВМ используется для управления технологическим процессом, сложной технической системой или включена в систему обработки и планирования физического эксперимента. Как правило, однако, экспериментальные данные получают до начала вычислений на ЭВМ. Нередко они представляют собой таблицу типа (27) с тем отличием, что табличные значения y_i* отличаются от истинных значений y_i, т.к. заведомо содержат ошибки эксперимента.

Возникающие проблемы часто решают следующим образом. Функцию f(x) приближенно заменяют другой функцией g(x), вычисляемые значения которой и принимают за значения f(x). Такая замена оправданна лишь тогда, когда значения g(x) вычисляются быстро и надежно, а погрешность приближения f(x) - g(x) достаточно мала.

В каждом конкретном случае при выборе постановки задачи приближения и метода ее решения приходиться сталкиваться со следующими проблемами:

1. Необходимо решить, какую информацию о функции f можно использовать как входные данные для вычисления приближения g. Например, часто известна или может быть получена таблица значений функции, а иногда - и таблица ее производных.

2. Полезно иметь некоторую дополнительную априорную информацию об аппроксимируемой функции. Часто она бывает качественного характера, например, известно, что функция f "достаточно гладкая", периодическая, монотонная, четная и т.п. Иногда удается получить некоторые количественные характеристики функции f , например, величина периода, оценка уровня погрешности в заданных значениях и т.д.

3. Знание свойств функции f часто позволяет осознанно выбирать класс G аппроксимирующих функций. Широко используются классы функций вида

_т(х)  а₀₀(х)  а₁₁(х)    а_т_т(х),

являющихся линейными комбинациями фиксированного набора некоторых базисных функций ₀(х), ₁(х),  , _т(х).

Если в качестве базисных функций используются степенные функции _к(х) = х^к, то возникает задача приближения алгебраическими многочленами

Р_т(х)  а₀  а₁х    а_тх^т .

Для аппроксимации периодических функций часто используются тригонометрические многочлены (ряд Фурье)

.

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

4. Необходим критерий выбора в классе G конкретной аппроксимирующей функции g, являющейся в смысле этого критерия наилучшим приближением к f . Например, требование совпадения функции g с функцией f в некоторых фиксированных точках приводит к задаче интерполяции. Другой распространенный критерий - требование минимизации среднеквадратичного отклонения - лежит в основе метода наименьших квадратов. Существует также большое число других критериев.

5. Важно понимать, что решение указанных выше вопросов тесно связано с тем, как мы собираемся использовать приближение g и какая точность нам нужна.

Задачу выбора в классе G конкретной приближающей функции можно рассматривать как задачу идентификации, если интерпретировать функцию y = g(x, ) как математическую модель реальной функциональной зависимости y = f(x).