Как найти начальный интервал неопределенности

Метод Риддера (Ridder’s method) является итерационным численным методом решения нелинейного уравнения  непрерывной функции. Данный метод относится к методам интервалов локализации корня.

В соответствии с методом задача поиска корня в уравнении сводится к задаче:

– создание уникальной экспоненциальной функции   вида ;

– поиска корня уравнения экспоненциальной функции , который будет являться приближением корня функции .

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

Рис.1. Метод Риддера.

Значение функции  в трех точках определяется в следующем виде:

› В точке  значение функции определяется ;

› В точке  значение функции определяется ;

› В точке  значение функции определяется .

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

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

Задача поиска корня уравнения f(x) сводится к поиску значения корней квадратного уравнения относительно переменной . Корень квадратного уравнения определяется по формуле:

Используя математические преобразования данное уравнение можно привести к виду:

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

В результате подстановки переменной  в данное уравнение получим формулу  для определения точки пересечения функции  с осью абсцисс.

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

,

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

 .

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

 или .

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

.

Данный метод решения нелинейного уравнения характеризуется определёнными свойствами:

– приближенное значение корня на любой итерации всегда оказывается внутри интервала локализации корня [a,b];

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

Алгоритм нахождения корня нелинейного уравнения по методу Риддера

1. Найти начальный интервал неопределенности  одним из методов отделения корней, задать малое положительное число . Положить .

2. Определить среднюю точку в рассматриваемом интервале и найти значения функции в трех точках: по краям рассматриваемого интервала ,  и в середине интервала.

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

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

1 интервал: если , то новый интервал 

2 интервал: если , то новый интервал 

5. Проверяем значение корня на предмет заданной точности, в случае: 

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

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

Пример решения уравнений методом Риддера

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

Вариант решения нелинейного уравнения в программном комплексе MathCAD.

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

Рис.2. Результаты расчета по методу Риддера

Для обеспечения заданной точности  при поиске уравнения в диапазоне  необходимо выполнить 5 итерации. На последнем шаге итерации приближенное значение корня нелинейного уравнения будет определяться значением: .

Алгоритм

Шаг 1.

Положить
.
Вычислить.

Шаг 2.

Положить
.
Заметим, что точкиделят интервалнаравные части. Вычислить значенияи.

Шаг 3.

Сравнить
и.

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

Если
,
перейти к шагу 4.

Шаг 4.

Сравнить
и.

Если
,
исключить интервал,
положив.
Т.к. в середине нового интервала
оказывается,
положить.
Перейти к шагу 5.

Если
,
исключить интервалыи,
положив.
Заметим, чтопродолжает оставаться средней точкой
нового интервала. Перейти к шагу 5.

Шаг 5.

Вычислить
.
Если величинаменьше заданной точности,
закончить поиск. В противном случае
перейти к шагу 2.

Пример

Пусть
определена на отрезке.
Найтис точностью.

Итерация 1.

Шаг 1.

Шаг 2.

Шаг 3.

следовательно, исключается интервал,
поэтому

Переходим
к шагу 5.

Шаг 5.

следовательно, поиск надо продолжать,
т.е. перейти к следующей итерации на
шаге 2 с отрезком,
при этом.

Итерация 2.

Шаг 2.

Шаг 3.

следовательно, переходим к шагу 4.

Шаг 4.

следовательно, исключаются интервалы,
поэтому новое значение,
старые значения сохраняются для.
Переходим к шагу 5.

Шаг 5.

следовательно, поиск надо продолжать,
т.е. перейти к следующей итерации на
шаге 2 с отрезком,
при этом.

Итерация 3.

Шаг 2.

Шаг 3.

следовательно, переходим к шагу 4.

Шаг 4.

следовательно, исключаются интервалы,
поэтому новое значение,
старые значения сохраняются для.
Переходим к шагу 5.

Шаг 5.

следовательно, поиск надо продолжать,
т.е. перейти к следующей итерации на
шаге 2 с отрезком.

Последующие
итерации аналогичны проделанным и далее
не рассматриваются. Окончание процедуры
происходит при выполнении условия
на шаге 5.

Выводы

В нашем
примере за 3 итерации (т.е. при шести
вычислениях функции
)
исходный интервал поиска сузился с 8 до
1. Как видите, метод дихотомии позволяет
довольно быстро попасть в область
экстремума. Так для определения положения
экстремума с точность вот длины начального интервала надо
сделать всего 14 измерений показателя
качества (это 7 итераций дихотомии), т.к..
Это намного лучше, чем метод сканирования,
который требует 101 измерение.

Алгоритм получения границ начального интервала неопределённости

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

Алгоритм
полученияначального интервала состоит
из двух этапов:

• Выбор
  «удачного» направления

• Движение
  в этом направлении до получения точки
  минимума

Исходными
данными являются начальная точка
и величина шага.
Рассмотрим шаги первого этапа алгоритма
получения начального интервала.

Шаг 1.

Вычислить
значение функции в начальной точке

Шаг 2.

Вычислить
значения аргумента и функции после шага
..

Шаг 3.

Вычислить
значения аргумента и функции после шага
.

Шаг 4.

Шаг 4.1

Если
,
то шагудачное направление. Оставляем его и
обозначим.

Шаг 4.2

Если
,
то шагудачное направление. Оставляем его и
обозначим.

Шаг 4.3

Если
,
то начальный интервал уже найден: точка
минимума лежит междуи.

Шаг 4.1

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

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

Шаг 1.

Переприсвоение:
.

Шаг 2.

Расчёт
новой длины шага:
.

Шаг 3.

Расчёт
аргумента и функции в третьей точке:
.

Шаг 4.

Сравнение
и:

• если
  ,
  перейти к шагу 1

• если
  ,
  окончание поиска: интервал неопределённости
  равен

Эффективность
поиска граничных точек непосредственно
зависит от величины шага. Если шаг велик,
то получаем грубые оценки координат
граничных точек, и построенный интервал
оказывается весьма широким. С другой
стороны, если шаг мал, то для определения
граничных точек может потребоваться
достаточно большой объём вычислений.
Несомненным достоинством методов такого
рода является то, что они основаны лишь
на вычислении значений функции. При
этом не требуется, чтобы исследуемые
функции были дифференцируемы. Более
того, допустимы случаи, когда целевую
функцию нельзя даже записать в
аналитическом виде.

Единственным
требование является возможность
определения значений
в заданных точкахс помощью прямых расчётов или имитационных
экспериментов.

Пример

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

Выполним
шаги первого этапа алгоритма.

Шаг 1.

Вычислим
значение функции в начальной точке:
.

Шаг 2.

Вычислим
значение аргумента и функции слева от
начальной точки:
.

Шаг 3.

Вычислим
значения аргумента и функции справа от
начальной точки:
.

Шаг 4.

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

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

Итерация 1

Шаг 1.

Выполняем
присвоение:
.

Шаг 2.

Расcчитываем
новую длину шага.

Шаг 3.

Находим в
третьей точке:
.

Шаг 4.

Сравниваем
и.следовательно, надо вновь идти на шаг
1 и делать вторую итерацию.

Итерация 2

Шаг 1.

Выполняем
присвоение:
.

Шаг 2.

Расcчитываем
новую длину шага.

Шаг 3.

Находим в
третьей точке:
.

Шаг 4.

Сравниваем
и..
Поскольку,
процедуру поиска начального интервала
заканчиваем. Начальный интервал:.

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

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

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

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

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

Пример

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

Рассчитаем
значение аргумента в 9 точках по формуле:
.

	1	2	3	4	5	6	7	8	9
	1	1.5	2	2.5	3	3.5	4	4.5	5

Рассчитаем
значения функции в каждой точке:

	1	2	3	4	5	6	7	8	9
	1	1.5	2	2.5	3	3.5	4	4.5	5
	9	6.25	4	2.25	1	0.25	0	0.25	1

Сравнивая
значения функции в 9 точках, находим:
.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Предложите, как улучшить StudyLib

(Для жалоб на нарушения авторских прав, используйте

другую форму
)

2. Метод Фибоначчи. Метод “золотого сечения”

Одним из методов однопараметрической
оптимизации является метод Фибоначчи.

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

Предположим, что имеется интервал неопределенности (x₁,x₃) и известно значение
функции f(x₂) внутри этого интервала
(см. рис. 9.3). Если можно
вычислить функцию всего один раз в точке х₄,
то где следует поместить точку х₄, для
того чтобы получить наименьший возможный интервал неопределенности?

Положим х₂–х₁=L и х₃–х₂=R, причем L > R, как показано на
рис. 9.3, и эти значения будут
фиксированы, если известны x₁, x₂ и х₃.
Если х₄ находится в интервале (х₁; х₂), то:

1. если f(x₄) < f(x₂),
   то новым интервалом неопределенности будет (x₁,x₂) длиной х₂–х₁=L ;
2. если f(х₄)>f(x₂),
   то новым интервалом неопределенности будет (х₄,х₃) длиной х₃–х₄.

Поскольку не известно, какая из этих ситуаций будет иметь
место, выберем х₄ таким образом, чтобы
минимизировать наибольшую из длин х₃-х₄ и х₂-х₁. Достигнуть этого
можно, сделав длины х₃ – х₄ и х₂ – х₁ равными т.е.
поместив х₄ внутри интервала симметрично
относительно точки х₂, уже лежащей
внутри интервала. Любое другое положение точки х₄ может привести к тому, что полученный
интервал будет больше L. Помещая х₄ симметрично относительно х₂, мы ничем не рискуем в любом случае.
Если окажется, что можно выполнить еще одно вычисление функции,
то следует применить описанную процедуру к интервалу (х₁, х₂), в котором уже есть
значение функции, вычисленное в точке х₄,
или к интервалу (х₄,х₃), в
котором уже есть значение функции, вычисленное в точке х₂.

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

На n -м вычислении n -ю точку следует
поместить симметрично по отношению к (n — 1) -й точке.
Положение этой последней точки в принципе зависит от нас. Для
того чтобы получить наибольшее уменьшение интервала на данном
этапе, следует разделить пополам предыдущий интервал. Тогда точка х будет совпадать с точкой х_n-1. Однако при этом мы не получаем
никакой новой информации. Обычно точки х_n-1 и х_n отстоят
друг от друга на достаточном расстоянии, чтобы определить, в какой
половине, левой или правой, находится интервал неопределенности.
Они помещаются на расстоянии е/2 по обе стороны от
середины отрезка L_n-1 ; можно самим задать
величину е или выбрать эту величину равной минимально
возможному расстоянию между двумя точками.

Интервал неопределенности будет иметь длину L_n, следовательно, L_n-1 = 2L_n – е
(рис.9.4, нижняя часть). На
предыдущем этапе точки х_n-1 и х_n-2 должны быть помещены симметрично
внутри интервала L_n-2 на расстоянии L_n-2 от концов этого интервала.
Следовательно, L_n-2 = L_n-1+L_n
(pис.9.4, средняя часть).

Замечание. Из рисунка ясно, что на предпоследнем
этапе х_n-2 остается в качестве
внутренней точки.

Аналогично L_n-3=L_n-2+L_n-1
(pис. 9.4, верхняя часть)

В общем случае L_j-1=L_j + L_j+1
при 1<j<n.

Таким образом,

Если определить последовательность чисел Фибоначчи
следующим образом: F₀=1, F₁=l, и F_k=F_k-1+F_k-2 для k = 2, 3,..., то

Если начальный интервал (a;b) имеет длину L = (b-а), то

Следовательно, произведя n вычислений функции,
мы уменьшим начальный интервал неопределенности в l/F_n раз по сравнению с его начальной
длиной (пренебрегая е), и это – наилучший результат.

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

После того как найдено положение первой точки, числа Фибоначчи
больше не нужны. Используемое значение е
может определяться из практических соображений. Оно должно быть
меньше L₁F_n+x, в противном
случае мы будем напрасно тратить время на вычисление функции.

Таким образом, поиск методом
Фибоначчи, названный так ввиду
появления при поиске чисел Фибоначчи, является итерационной
процедурой. В процессе поиска интервала (x1; x2) с точкой х₂, уже
лежащей в этом интервале, следующая точка х₂ всегда выбирается такой, что х₃–х₄ = х₂–х₁
или х₄-х₁ = х₃-x₂,
т.е. x₄=х₁-х₂+х₃.

Если f(x₂) = f₂ и f(x₄) = f₄,
то можно рассмотреть четыре случая
(рис. 9.5).

Следующий из методов одномерной оптимизаци называется методом “золотого сечения”.

Не всегда можно заранее определить, сколько раз придется
вычислять функцию. В методе Фибоначчи это нужно знать для
определения L₂, т.е. положения
начальной точки (см. уравнение 2.4).

Метод “золотого сечения”
почти столь же эффективен,
как и метод Фибоначчи, однако при этом не требуется знать n – количество вычислений функции, определяемое
вначале. После того как выполнено j вычислений,
исходя из тех же соображений, что и ранее (см. уравнение 2.1),
записываем

Однако если n не известно, то мы не можем
использовать условие L_n-1 = L_n – е.
Если отношение последующих интервалов будет постоянным, т.е.

то

т.е.

Таким образом, , откуда .
Тогда

Следовательно, , т.е.

В результате анализа двух рассмотренных значений функции будет
определен тот интервал, который должен исследоваться в дальнейшем.
Этот интервал будет содержать одну из предыдущих точек и
следующую точку, помещаемую симметрично ей. Первая точка находится
на расстоянии L₁/t от одного конца
интервала, вторая – на таком же расстоянии от другого. Поскольку

то из уравнения (2.4) видно, что поиск методом “золотого
сечения” является предельной формой поиска методом Фибоначчи.
Название “золотое сечение” произошло от названия
отношения в уравнении (2.7). Видно, что L_j-1
делится на две части так, что отношение целого к большей части равно
отношению большей части к меньшей, т.е. равно так называемому
“золотому отношению”.

Таким образом, если ищется интервал (х₀, х₃) и имеются два значения
функции f₁ и f₂ в точках x₁ и x₂, то следует
рассмотреть два случая (рис. 9.6).

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

Схема алгоритма метода “золотого сечения” представлена
на рис 9.7

Здесь c – константа,

При выводе x – координата точки, в которой функция F(x) имеет минимум (или максимум), FM – значение функции F(x) в этой точке.