что такое начальное приближение функции

Графический способ – это построение графика функции f(x) и определение числа корней по количеству пересечений графика с осью x.

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

Решить уравнение x 3 ‑ 6x 2 +3x+11=0, т.е. f(x)= x 3 ‑ 6x 2 +3x+11.

X₁== 0.268;

X₂== 3.732;

Найдем интервалы изоляции для каждого из корней.

Рассмотрим для второго корня отрезок [1, 3]:

Источник

Что такое начальное приближение функции

Все методы оптимизации, описанные нами, требуют наличия начального приближения для величин параметров. Выбор хорошего начального приближения может способствовать успешному нахождению положения оптимума или более быстрой сходимости к решению, чем при неудачном начальном приближении. К сожалению, в то время как мы можем создавать формализованные алгоритмы оценивания при известном начальном приближении, для выбора последнего мы должны в значительной степени полагаться на свою интуицию и априорное знание. Тем не менее мы можем выдвигать некоторые предположения, которые могут оказаться полезными во многих случаях. Обширную дискуссию по таким методам можно найти в работе Китрелла и др. [124].

Мы должны сразу предостеречь читателя от преувеличения важности нахождения хорошего начального приближения. Во многих случаях хорошее решение получалось даже тогда, когда в качестве начальных приближений были взяты совершенно произвольные значения. В этих случаях ценой нескольких минут дополнительного времени расчетов на ЭВМ можно избавиться от значительных затрат на поиски начального приближения. Поэтому мы предлагаем (если машинное время дефицитно или очень дорого) пытаться оценивать параметры методом «грубой силы». Только в случае неудачи этой стратегии следует прибегать к более тонким процедурам.

Наиболее очевидный метод для получения начальных приближений состоит в использовании априорной информации. Оценки, рассчитанные по результатам предыдущих экспериментов; величины, полученные при исследовании аналогичных систем или из теоретических соображений, — все они могут употребляться в качестве начальных приближений.

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

Поскольку все наши параметры ограничены прямоугольной областью в пространстве 0, мы можем провести поиск методом сетки: вычислить значения целевой функции в каждой точке регулярной прямоугольной сетки и выбрать точку с наилучшим значением в качестве начального приближения. Основная трудность этого подхода состоит в так называемом «проклятье размерности»: для сетки с уровнями по каждой из I переменных общее число точек, в которых должна быть вычислена функция цели, равно Это недопустимо большое число при всех значениях и I, кроме самых малых.

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

Действительно, с большой вероятностью среди ста точек найдется одна, представляющая собой решение в пределах 1%-ной погрешности! Однако этот 1% относится ко всему объему допустимой области. Если в задаче параметров, то относительная точность каждого параметра есть только или 31,6% допустимого диапазона при 1—4. Метод случайного поиска не позволяет преодолеть «проклятье размерности», но имеет все же некоторые преимущества перед методом сетки. Он позволяет преобразовать область поиска так, чтобы учесть предпочтительность некоторых областей в пространстве параметров (эту процедуру можно рассматривать как взятие выборки из априорного распределения), а также использовать последовательный критерий останова: прекратить расчеты, как только найдено значение функции, значительно лучшее, чем среднее из всех ранее найденных. Иногда до начала поиска требуется преобразовать переменные. Например, если неизвестен даже порядок величины параметра, его следует заменить его логарифмом.

Начальные значения не всегда необходимы для всех параметров модели. Если некоторые параметры входят в уравнения модели линейно и имеются начальные приближения для остальных параметров, то линейные параметры можно оценить методом множественной линейной регрессии. Положим, например, что модель имеет вид Если имеем начальное значение и положим гц то начальное значение для можно найти, решая линейную задачу минимизации суммы квадратов: Разработаны специальные варианты метода Гаусса для частично линейных моделей (см. [132] и [91]).

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

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

(б) Многоступенчатое оценивание. Разбивая данные на группы, можно оценить некоторые вспомогательные параметры для каждой группы; далее оцениваются исходные параметры как функции вспомогательных. Например, скорость химической реакции выражается уравнением

где у — скорость, концентрация, температура, и оцениваемые параметры. Скорость у измеряется как функция х при нескольких значениях скажем Предположим, что мы воспользуемся данными, снятыми при для оценивания коэффициента в уравнении

Оцененные можно использовать затем как результаты эксперимента для оценки и в линеаризованной модели

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

(в) Упрощение модели. Часто имеется возможность приблизить исследуемую модель набором более простых, в которых некоторые эффекты опущены и удалены соответствующие параметры. После того как параметры упрощенной модели будут оценены, анализ остатков (см. раздел 7.13) может показать, какие члены следует добавить в модель на следующем этапе. Этот метод служит не только для получения начальных приближений для заданной модели, но также (и это, вероятно, более важно) для синтеза модели, когда ничего о ней не известно. Примеры такого синтеза модели приведены Боксом и Йоулом [38], Петерсоном [156], Боксом и Хантером [33], Хантером и Мезаки [112] и Китреллом, Хантером и Мезаки [122].

(г) Упрощенный метод оценивания. Заменим заданную целевую функцию некоторой другой, более просто минимизируемой. Приведем несколько примеров: (1) линеаризуем модель, как это делалось выше в пункте (а); (2) в многооткликовой модели мы применим одно из уравнений для получения предварительных оценок параметров. На самом деле, однако, иногда легче получить оценки, используя все уравнения модели, так как иначе теряется информация, относящаяся к значениям некоторых параметров. Как простой пример рассмотрим модель, состоящую из трех уравнений:

Очевидно, что все три параметра можно оценить независимо, только если использовать все три уравнения; (3) в моделях динамики мы можем употреблять результаты интегрирования или дифференцирования, чтобы получить начальные приближения для метода интегрирования уравнений (см. раздел 8.1).

Источник

Julia и метод покоординатного спуска

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

Поиск экстремума ведется в направлении осей координат, т.е. в процессе поиска изменяется только одна координата. Таким образом, многомерная задача сводится к одномерной.

Алгоритм

Подготовка

Сверим версии пакетов:

Зададим функцию для отрисовки поверхности либо линий уровня, в которой было бы удобно регулировать границы графика:

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

Покоординатный спуск

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

Далее опробуем различные методы одномерной оптимизации

Метод Ньютона

Идея метода проста как и реализация

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

Обратная параболическая интерполяция

Метод не требующий знания производной и имеющий неплохую сходимость

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

Последовательная параболическая интерполяция

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

Выйдя из весьма дрянной стартовой точки дошло за три шага! Хорош… Но у всех методов есть недостаток — они сходятся к локальному минимуму. Возьмём теперь для исследований функцию Экли

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

Теория. Хоть реализация сложна, метод порой показывает себя хорошо перепрыгивая локальные минимумы

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

Источник