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

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

Все методы оптимизации, описанные нами, требуют наличия начального приближения для величин параметров. Выбор хорошего начального приближения может способствовать успешному нахождению положения оптимума или более быстрой сходимости к решению, чем при неудачном начальном приближении. К сожалению, в то время как мы можем создавать формализованные алгоритмы оценивания при известном начальном приближении, для выбора последнего мы должны в значительной степени полагаться на свою интуицию и априорное знание. Тем не менее мы можем выдвигать некоторые предположения, которые могут оказаться полезными во многих случаях. Обширную дискуссию по таким методам можно найти в работе Китрелла и др. [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).

Источник

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

Глава 4. Решение уравнений

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

Обращение к функции осуществляется следующим образом:

root ( f ( x ), x ), где f ( x ) – выражение, равное нулю; x – аргумент, варьируя который, система ищет значение, обращающее в нуль ( рис. 4.1 ).

Уравнение

начальное приближение

решение

или

другие корни

Задан интервал поиска корней

Рис. 4. 1 Использование функции root

Mathcad позволяет вместо начального приближения задавать диапазон значений аргумента, в котором лежит значение искомого корня. В этом случае обращение к функции root должно иметь четыре параметра:

где a и b – границы интервала, в котором лежит один корень уравнения. Внутри интервала не должно быть больше одного корня, так как Mathcad выводит на экран лишь один корень, лежащий внутри интервала.

Значение функции на границах интервала должно быть разного знака, иначе, возможно, корень не будет найден.

Если функция имеет мнимый корень,

то начальное приближение задается комплексным числом

— начальное приближение

Рис. 4. 2 Решение уравнения с комплексными корнями

Если уравнение имеет несколько корней, то для их нахождения можно использовать разложение функции f ( x ) на простые множители:

,

где ,

и т. д. (рис. 4.3)

у этой функции 3 корня

диапазон значений х для вывода графика

Рис. 4. 3 Определение трех корней уравнения

1) в стандартном меню Mathcad выберите команду Tools → Worksheet Options → Built – In Variables (Инструменты → Параметры документов → Встроенные переменные);

2) в открывшемся окне поменяйте значение Convergence Tolerance ( TOL ) (Погрешность сходимости).

Для повышения точности расчета корня можно заменить f ( x ) на

.

Корень можно найти и по графику, увеличив масштаб. Для этого необходимо:

1) выделить график, щелкнув левой кнопкой мыши внутри графика;

2)в главном меню Mathcad выбрать команду Format → Graph → Zoom (Формат→График→Масштаб);

3) при нажатии левой кнопки мыши обвести пунктирной линией область графика вблизи искомого корня, которую надо увеличить;

Прямо с графика можно передать в буфер обмена численное значение корня. Для этого выполните следующие действия:

1) Выделите график, щелкнув левой кнопкой мыши внутри графика,

2) в главном меню Mathcad выберите команду Format → Graph → Trace (Формат→График→Трассировка),

3) щелкните левой кнопкой мыши внутри графика – появится перекрестье осей,

4) двигая мышь при нажатой левой кнопке, установите перекрестье на пересечении графика с осью абсцисс. При этом численные значения координат перекрестья появляются в открытом окне X – Y Trace (Трассировка X и Y ).

5) правильно выбрав положение перекрестья, нажмите кнопки Copy X и Copy Y – численные значения будут помещены в буфер

6) вне поля графика запишите имя, которое хотите дать корню, и оператор присваивания :=. Нажмите кнопку Paste (Вставить) в стандартном меню Mathcad или в контекстном меню, открывающемся при нажатии правой кнопки мыши.

Рис. 4. 4 Определение корня уравнения по графику

В окне X – Y Trace есть пункт Track Data Points (Отмечать расчетные точки). Если установить этот флажок, при перемещении мыши пунктирное перекрестье на графике будет перемещаться скачками, отмечая расчетные значения функции. Если флажок снять, движение перекрестья становится плавным.

Источник

Как находить графически начальное приближение?

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

Как определить по графику начальное приближение
Как определить по графику начальное приближение?

Начальное приближение
Здравствуйте! Как найти начальное приближение для СНУ?

Начальное приближение в алгебраическом уравнении
Здравствуйте! Помогите пожалуйста разобраться. Нужно выполнить следующее задание: Решить систему.

wer1, по такой СНАУ можно построить график функций?

Вот из этой задачи и сказали начальное приближение найти графически

решая второе и третье уравнения (график тут не нужен вовсе), получим

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

Источник

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

Nickolay.info. Обучение. Лекции по численным методам. Приближённое решение нелинейных алгебраических уравнений

1. Приближенное решение нелинейных алгебраических уравнений

Дано нелинейное алгебраическое уравнение

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

Решить уравнение – это найти такое x* ∈ R: f(x*)=0. Значение x* называют корнем уравнения. Нелинейное уравнение может иметь несколько корней. Геометрическая интерпретация корней уравнения представлена на рис. 1. Корнями уравнения (1) являются точки x₁*, x₂*, x₃*, в которых функция f(x) пересекает ось x.

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

В приближенных методах процесс нахождения решения, вообще говоря, бесконечен. Решение получается в виде бесконечной последовательности <x_n>, такой, что . По определению предела, для любого (сколь угодно малого) ε, найдется такое N, что при n>N, |x_n – x*| / (x) не меняет знак на отрезке [a, b], т.е. f(x) – монотонная функция, в этом случае отрезок [a,b] будет интервалом изоляции.

Если корней несколько, то для каждого нужно найти интервал изоляции.

Существуют различные способы исследования функции: аналитический, табличный, графический.

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

Графический способ – это построение графика функции 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]:

Источник

Нелинейные системы и уравнения

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

Решение нелинейных уравнений

Вычисления по (4) проводятся до тех пор, пока \( f(x_k) \) не станет близким к нулю. Более точно, до тех пор, пока \( |f_(x_k)| > \varepsilon \), где \( \varepsilon \) — малая величина.

Простейшая реализация метода Ньютона может выглядеть следующим образом:

Чтобы найти корень уравнения \( x^2 = 9 \) необходимо реализовать функции

Данная функция хорошо работает для приведенного примера. Однако, в общем случае могут возникать некоторые ошибки, которые нужно отлавливать. Например: пусть нужно решить уравнение \( \tanh(x) = 0 \), точное решение которого \( x = 0 \). Если \( |x_0| \leq 1.08 \), то метод сходится за шесть итераций.

Теперь зададим \( x_0 \) близким к \( 1.09 \). Возникнет переполнение

Проблема заключается в том, что при таком начальном приближении метод Ньютона расходится.

Еще один недостаток функции naive_Newton заключается в том, что функция f(x) вызывается в два раза больше, чем необходимо.

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

Решение нелинейных систем

Таким образом, \( k \)-я итерация метода Ньютона состоит из двух стадий:

2. Находится значение вектора на следующей итерации \( \pmb^ <(k+1)>= \pmb^ <(k)>+ \pmb <\delta>\).

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

Можно также воспользоваться методами, реализованными для систем линейных уравнений.

Источник