Как найти максимум методом золотого сечения

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 18 февраля 2018 года; проверки требуют 12 правок.

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

Описание метода[править | править код]

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

, где — пропорция золотого сечения.

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

То есть точка делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.

Алгоритм[править | править код]

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

Формализация[править | править код]

1. Шаг 1. Задаются начальные границы отрезка и точность .
2. Шаг 2. Рассчитывают начальные точки деления: и значения в них целевой функции: .
3. Шаг 3.

Алгоритм взят из книги Мэтьюза и Финка «Численные методы. Использование MATLAB».

Реализация данного алгоритма на языке F#, в которой значения целевой функции используются повторно:

let phi = 0.5 * (1.0 + sqrt 5.0)
let minimize f eps a b = 
    let rec min_rec f eps a b fx1 fx2 = 
        if b - a < eps then 
            0.5 * (a + b)
        else 
            let t = (b - a) / phi
            let x1, x2 = b - t, a + t
            let fx1 = match fx1 with Some v -> v | None -> f x1
            let fx2 = match fx2 with Some v -> v | None -> f x2
            if fx1 >= fx2 then
                min_rec f eps x1 b (Some fx2) None
            else
                min_rec f eps a x2 None (Some fx1)
    min_rec f eps (min a b) (max a b) None None

// Примеры вызова:
minimize cos 1e-6 0.0 6.28 |> printfn "%.10g"
// = 3.141592794; функция f вызвана 34 раза.
minimize (fun x -> (x - 1.0)**2.0) 1e-6 0.0 10.0 |> printfn "%.10g"
// = 1.000000145; функция f вызвана 35 раз.

Метод чисел Фибоначчи[править | править код]

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

Алгоритм[править | править код]

1. Шаг 1. Задаются начальные границы отрезка и число итераций , рассчитывают начальные точки деления: и значения в них целевой функции: .
2. Шаг 2. .
3. Шаг 3.

Литература[править | править код]

1. Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
3. Коршунов Ю. М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
4. Максимов Ю. А., Филлиповская Е. А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
5. Максимов Ю. А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575—576.
7. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1973. — С. 832 с илл..
8. Джон Г. Мэтьюз, Куртис Д. Финк. Численные методы. Использование MATLAB. — 3-е издание. — М., СПб.: Вильямс, 2001. — С. 716.

См. также[править | править код]

• Золотое сечение
• Числа Фибоначчи

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

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

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

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

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

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

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

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

На
рис. 3 приведены два этапа поиска максимума
функции методом золотого сече­ния.

Рис.
3. Иллюстрация метода золотого сечения:
1 – интервал, включающий в себя искомый
максимум функции после первого этапа
(первого золотого сечения в точках c
и
d);
2
–
то же, после второго этапа (новая точка
е
и
старая точка d)

Алгоритм метода золотого сечения для минимизации функции.

Начальный
этап. Выбрать
допустимую конечную длину интервала
неопределённости l
> 0. Пусть [а,
b]
– начальный интервал неопределённости.
Положить

и
.
Вычислить R(c)
и R(d),
положить k
= 1 и перейти к основному этапу.

Основной этап.

Шаг
1. Если b_­k
– a_k
< l,
то остановиться; точка минимума
принадлежит интервалу [а_k,
b_k].
В противном случае если R(c_k)
> R(d_k),
то перейти к шагу 2, а если R(c_k)
≤ R(d_k),
то к шагу 3.

Шаг
2.
Положить a_k+1

= c_k
и b_k+1

= b_k,

.
Вычислить R(d_k+1)
и перейти к шагу 4.

Шаг
3.
Положить a_k+1

= a_k
и b_k+1

= d_k,

.
Вычислить R(c_k+1)
и перейти к шагу 4.

Шаг
4.
Заменить k
на k
+
1 и перейти к шагу 1.

Пример.

Дана
функция R(x)
= D
sin(Ах^B
+ С), где
коэффициенты имеют следующие значения:
А
=1,0,
В = 1,0,
С
= 1,0,
D
= 1,0.
Найти максимум на интервале: [-1, 2]. Ошибка
задается по х:
ε
=0,05.

Результаты
расчетов. Для “запуска” метода
найдем две симметричные точки золотого
сечения для отрезка [-1, 2]:

x₁
=0,145898, х₂
=0,85410197.

Значения
критериев в этих точках соответственно
R(x₁)
= 0,911080, R(x₂)
=
0,960136. Следовательно, новым отрезком
является [0,145898; 2], внутри которого
находится максимальное из найденных
значений R.
Точка
золотого сечения для нового отрезка
будет x₃
=0,58359214, a
R(x₃)
=0,99991813.
Далее приведены только координаты
лучших точек при очередном шаге, номер
шага и значения критерия в этих точках.

х₃
= 0,58359214; R₃
= 0,99991813;

х₄
=0,58359214; R₄
= 0,99991813

х₅
= 0,58359214; R₅
= 0,99991813;

х₆
= 0,58359214; R₆
= 0,99991813

х₇
= 0,58359214; R₇
= 0,99991813;

х₈
= 0,55920028; R₈
= 0,99993277;

х₉
= 0,55920028;
R₉
= 0,99993277.

Всего
было проведено 10 вычислений критерия
оптимальности.

Соседние файлы в папке Системный анализ и принятие решений

• #
• #

  27.02.2016389.68 Кб50Тугаринов.xmcd

From Wikipedia, the free encyclopedia

The golden-section search is a technique for finding an extremum (minimum or maximum) of a function inside a specified interval. For a strictly unimodal function with an extremum inside the interval, it will find that extremum, while for an interval containing multiple extrema (possibly including the interval boundaries), it will converge to one of them. If the only extremum on the interval is on a boundary of the interval, it will converge to that boundary point. The method operates by successively narrowing the range of values on the specified interval, which makes it relatively slow, but very robust. The technique derives its name from the fact that the algorithm maintains the function values for four points whose three interval widths are in the ratio φ:1:φ where φ is the golden ratio. These ratios are maintained for each iteration and are maximally efficient. Excepting boundary points, when searching for a minimum, the central point is always less than or equal to the outer points, assuring that a minimum is contained between the outer points. The converse is true when searching for a maximum. The algorithm is the limit of Fibonacci search (also described below) for many function evaluations. Fibonacci search and golden-section search were discovered by Kiefer (1953) (see also Avriel and Wilde (1966)).

Basic idea[edit]

The discussion here is posed in terms of searching for a minimum (searching for a maximum is similar) of a unimodal function. Unlike finding a zero, where two function evaluations with opposite sign are sufficient to bracket a root, when searching for a minimum, three values are necessary. The golden-section search is an efficient way to progressively reduce the interval locating the minimum. The key is to observe that regardless of how many points have been evaluated, the minimum lies within the interval defined by the two points adjacent to the point with the least value so far evaluated.

The diagram above illustrates a single step in the technique for finding a minimum. The functional values of are on the vertical axis, and the horizontal axis is the x parameter. The value of has already been evaluated at the three points: , , and . Since is smaller than either or , it is clear that a minimum lies inside the interval from to .

The next step in the minimization process is to “probe” the function by evaluating it at a new value of x, namely . It is most efficient to choose somewhere inside the largest interval, i.e. between and . From the diagram, it is clear that if the function yields , then a minimum lies between and , and the new triplet of points will be , , and . However, if the function yields the value , then a minimum lies between and , and the new triplet of points will be , , and . Thus, in either case, we can construct a new narrower search interval that is guaranteed to contain the function’s minimum.

Probe point selection[edit]

From the diagram above, it is seen that the new search interval will be either between and with a length of a + c, or between and with a length of b. The golden-section search requires that these intervals be equal. If they are not, a run of “bad luck” could lead to the wider interval being used many times, thus slowing down the rate of convergence. To ensure that b = a + c, the algorithm should choose .

However, there still remains the question of where should be placed in relation to and . The golden-section search chooses the spacing between these points in such a way that these points have the same proportion of spacing as the subsequent triple or . By maintaining the same proportion of spacing throughout the algorithm, we avoid a situation in which is very close to or and guarantee that the interval width shrinks by the same constant proportion in each step.

Mathematically, to ensure that the spacing after evaluating is proportional to the spacing prior to that evaluation, if is and our new triplet of points is , , and , then we want

However, if is and our new triplet of points is , , and , then we want

Eliminating c from these two simultaneous equations yields

or

where φ is the golden ratio:

The appearance of the golden ratio in the proportional spacing of the evaluation points is how this search algorithm gets its name.

Termination condition[edit]

Any number of termination conditions may be applied, depending upon the application. The interval ΔX = X₄ − X₁ is a measure of the absolute error in the estimation of the minimum X and may be used to terminate the algorithm. The value of ΔX is reduced by a factor of r = φ − 1 for each iteration, so the number of iterations to reach an absolute error of ΔX is about ln(ΔX/ΔX_o) / ln(r) where ΔX_o is the initial value of ΔX.

Because smooth functions are flat (their first derivative is close to zero) near a minimum, attention must be paid not to expect too great an accuracy in locating the minimum. The termination condition provided in the book Numerical Recipes in C is based on testing the gaps among , , and , terminating when within the relative accuracy bounds

where is a tolerance parameter of the algorithm, and is the absolute value of . The check is based on the bracket size relative to its central value, because that relative error in is approximately proportional to the squared absolute error in in typical cases. For that same reason, the Numerical Recipes text recommends that , where is the required absolute precision of .

Algorithm[edit]

Note! The examples here describe an algorithm that is for finding the minimum of a function. For maximum, the comparison operators need to be reversed.

Iterative algorithm[edit]

1. Specify the function to be minimized, f(x), the interval to be searched as {X₁,X₄}, and their functional values F₁ and F₄.
2. Calculate an interior point and its functional value F₂. The two interval lengths are in the ratio c : r or r : c where r = φ − 1; and c = 1 − r, with φ being the golden ratio.
3. Using the triplet, determine if convergence criteria are fulfilled. If they are, estimate the X at the minimum from that triplet and return.
4. From the triplet, calculate the other interior point and its functional value. The three intervals will be in the ratio c:cr:c.
5. The three points for the next iteration will be the one where F is a minimum, and the two points closest to it in X.
6. Go to step 3

"""Python program for golden section search.  This implementation
   does not reuse function evaluations and assumes the minimum is c
   or d (not on the edges at a or b)"""
import math

gr = (math.sqrt(5) + 1) / 2


def gss(f, a, b, tol=1e-5):
    """Golden-section search
    to find the minimum of f on [a,b]
    f: a strictly unimodal function on [a,b]

    Example:
    >>> f = lambda x: (x-2)**2
    >>> x = gss(f, 1, 5)
    >>> print("%.15f" % x)
    2.000009644875678

    """
    c = b - (b - a) / gr
    d = a + (b - a) / gr
    while abs(b - a) > tol:
        if f(c) < f(d):  # f(c) > f(d) to find the maximum
            b = d
        else:
            a = c

        # We recompute both c and d here to avoid loss of precision which may lead to incorrect results or infinite loop
        c = b - (b - a) / gr
        d = a + (b - a) / gr

    return (b + a) / 2

"""Python program for golden section search.  This implementation
   reuses function evaluations, saving 1/2 of the evaluations per
   iteration, and returns a bounding interval."""
import math


invphi = (math.sqrt(5) - 1) / 2  # 1 / phi
invphi2 = (3 - math.sqrt(5)) / 2  # 1 / phi^2


def gss(f, a, b, tol=1e-5):
    """Golden-section search.

    Given a function f with a single local minimum in
    the interval [a,b], gss returns a subset interval
    [c,d] that contains the minimum with d-c <= tol.

    Example:
    >>> f = lambda x: (x-2)**2
    >>> a = 1
    >>> b = 5
    >>> tol = 1e-5
    >>> (c,d) = gss(f, a, b, tol)
    >>> print(c, d)
    1.9999959837979107 2.0000050911830893
    """

    (a, b) = (min(a, b), max(a, b))
    h = b - a
    if h <= tol:
        return (a, b)

    # Required steps to achieve tolerance
    n = int(math.ceil(math.log(tol / h) / math.log(invphi)))

    c = a + invphi2 * h
    d = a + invphi * h
    yc = f(c)
    yd = f(d)

    for k in range(n - 1):
        if yc < yd:  # yc > yd to find the maximum
            b = d
            d = c
            yd = yc
            h = invphi * h
            c = a + invphi2 * h
            yc = f(c)
        else:
            a = c
            c = d
            yc = yd
            h = invphi * h
            d = a + invphi * h
            yd = f(d)

    if yc < yd:
        return (a, d)
    else:
        return (c, b)

Recursive algorithm[edit]

public class GoldenSectionSearch {
    public static final double invphi = (Math.sqrt(5.0) - 1) / 2.0;
    public static final double invphi2 = (3 - Math.sqrt(5.0)) / 2.0;

    public interface Function {
        double of(double x);
    }

    // Returns subinterval of [a,b] containing minimum of f

    public static double[] gss(Function f, double a, double b, double tol) {
        return gss(f, a, b, tol, b - a, true, 0, 0, true, 0, 0);
    }
    private static double[] gss(Function f, double a, double b, double tol,
                                double h, boolean noC, double c, double fc,
                                boolean noD, double d, double fd) {
        if (Math.abs(h) <= tol) {
            return new double[] { a, b };
        }
        if (noC) {
            c = a + invphi2 * h;
            fc = f.of(c);
        }
        if (noD) {
            d = a + invphi * h;
            fd = f.of(d);
        }
        if (fc < fd) {  // fc > fd to find the maximum
            return gss(f, a, d, tol, h * invphi, true, 0, 0, false, c, fc);
        } else {
            return gss(f, c, b, tol, h * invphi, false, d, fd, true, 0, 0);
        }
    }

    public static void main(String[] args) {
        Function f = (x)->Math.pow(x-2, 2);
        double a = 1;
        double b = 5;
        double tol = 1e-5;
        double [] ans = gss(f, a, b, tol);
        System.out.println("[" + ans[0] + "," + ans[1] + "]");
        // [1.9999959837979107,2.0000050911830893]
    }
}

import math


invphi = (math.sqrt(5) - 1) / 2  # 1 / phi
invphi2 = (3 - math.sqrt(5)) / 2  # 1 / phi^2


def gssrec(f, a, b, tol=1e-5, h=None, c=None, d=None, fc=None, fd=None):
    """Golden-section search, recursive.

    Given a function f with a single local minimum in
    the interval [a,b], gss returns a subset interval
    [c,d] that contains the minimum with d-c <= tol.

    Example:
    >>> f = lambda x: (x-2)**2
    >>> a = 1
    >>> b = 5
    >>> tol = 1e-5
    >>> (c,d) = gssrec(f, a, b, tol)
    >>> print (c, d)
    1.9999959837979107 2.0000050911830893
    """

    (a, b) = (min(a, b), max(a, b))
    if h is None:
        h = b - a
    if h <= tol:
        return (a, b)
    if c is None:
        c = a + invphi2 * h
    if d is None:
        d = a + invphi * h
    if fc is None:
        fc = f(c)
    if fd is None:
        fd = f(d)
    if fc < fd:  # fc > fd to find the maximum
        return gssrec(f, a, d, tol, h * invphi, c=None, fc=None, d=c, fd=fc)
    else:
        return gssrec(f, c, b, tol, h * invphi, c=d, fc=fd, d=None, fd=None)

Fibonacci search[edit]

A very similar algorithm can also be used to find the extremum (minimum or maximum) of a sequence of values that has a single local minimum or local maximum. In order to approximate the probe positions of golden section search while probing only integer sequence indices, the variant of the algorithm for this case typically maintains a bracketing of the solution in which the length of the bracketed interval is a Fibonacci number. For this reason, the sequence variant of golden section search is often called Fibonacci search.

Fibonacci search was first devised by Kiefer (1953) as a minimax search for the maximum (minimum) of a unimodal function in an interval.

See also[edit]

• Ternary search
• Brent’s method
• Binary search

References[edit]

• Kiefer, J. (1953), “Sequential minimax search for a maximum”, Proceedings of the American Mathematical Society, 4 (3): 502–506, doi:10.2307/2032161, JSTOR 2032161, MR 0055639
• Avriel, Mordecai; Wilde, Douglass J. (1966), “Optimality proof for the symmetric Fibonacci search technique”, Fibonacci Quarterly, 4: 265–269, MR 0208812

• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), “Section 10.2. Golden Section Search in One Dimension”, Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

 Метод золотого сечения также является последовательным методом минимизации. Опираясь на свойства золотого сечения отрезка, этот метод использует найденные значения F(X) более рационально, чем метод деления отрезка пополам, что позволяет переходить к  очередному отрезку, содержащему точку Х* после вычисления одного, а не двух значений F(X).

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

Правило золотого сечения: Отношение всего Отрезка к большей его части равно отношению большей части от­Резка к меньшей. Ему удовлетворяют две точки с и D, располо­Женные симметрично относительно середины отрезка:

Путем сравнения  F(с) И F(D) Определяют следующий отрезок, где содержится максимум. Если F(D) > F(с), то в качестве сле­дующего отрезка выбирается отрезок [с, B], в противном слу­чае — отрезок [а, D].

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

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

Существуют аналитические формулы для расчета новой точ­ки на отрезке, где находится максимальное значение F(X).

Золотое сечение отрезка [A; B] осуществляется двумя точками:

  (3)

Причем Х1 есть вторая точка золотого сечения отрезка [A; X2], а Х2 – первая точка золотого сечения отрезка [X1; B].

Зная одну из точек золотого сечения отрезка [A; B], другую можно найти по одной из формул

X1 = A + B – X2, X2 = A + B – X1. (4)

Пусть F(X)  Q[A; B] и требуется найти точку минимума Х* функции F(X) на [A; B]. Построим последовательности {An}, {Bn}, {}, N = 1, 2, …, следующим образом:

  (5)

Первая и вторая точки золотого сечения (3) отрезка [An-1; Bn-1].

Для определения чисел An, Bn, По найденным An-1, Bn-1, Необходимо выполнить следующие операции:

1)  найти одну из точек золотого сечения отрезка [An-1; Bn-1] по известной другой точке , используя формулы (4) или (3);

2)  вычислить значение F(X) во вновь найденной точке золотого сечения;

3) сравнить значения  и  и найти An, bn, Xn по формулам (5).

Таким образом, на каждом шаге определения An, Bn и , N=2, 3, …, требуется вычисление одного значения F(X). Положив , найдем точку минимума Х* с точностью N:

  (6)

Откуда следует, что число шагов N метода золотого сечения, обеспечивающее заданную точность  нахождения точки Х*, должно удовлетворять неравенству:

  (7)

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

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

На рис. 18 приведены два этапа поиска максимума функ­ции методом золотого сече­ния: 1 – интервал,  включающий в себя искомый максимум функции после первого этапа (первого золотого сечения в точках C и D); 2 – то же, после второго этапа (новая точка E и старая точка D).

 Пример 17. Найти минимальное значение F* и точку минимума Х* функции На отрезке [1.5; 2]. Точку Х* Найти с точностью =0,05.

Решение. Вычисления проведем по формулам (5) представив результаты в табл. 12.

Таблица 12

 Первоначальные значения Х1 И х2 находим по формулам (3), а значения точности   по формуле (6).

Из таблицы получаем  

Заметим, что если воспользоваться формулой (7), то необходимое число шагов N можно определить заранее. В нашем случае N  4,79, т. е. N = 5, и отпадает необходимость во втором столбце табл. 12.

Пример 18. Найти точку минимума Х*И минимум F* функции F(X)=X2+3X(Lnx-1) на отрезке [0.5; 1] С точностью =0,05.

Решение. Вычисления представим в табл. 13.

Таблица 13

 Следовательно, Х* 0,646, и  F* F (0,646) = -2,368.

Решение нелинейных уравнений метод золотого сечения

1. МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

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

Если известно, что функция f ( x ) унимодальная на отрезке [ a , b ], то положение точки минимума можно уточнить, вычислив f ( x ) в двух внутренних точках отрезка. При этом возможны две ситуации:

Минимум реализуется на отрезке [ a , x ₂ ] .

Минимум реализуется на отрезке [ x ₁ , b ] .

В методе золотого сечения каждая из точек x ₁ и x ₂ делит исходный интервал на две части так, что отношение целого к большей части равно отношении большей части к меньшей, т.е. равно так называемому “золотому отношению”. Это соответствует следующему простому геометрическому представлению:

Итак, длины отрезков [ a , x ₁ ] и [ x ₂ , b ] одинаковы и составляют 0,382 от длины ( a , b ) . Значениям f ( x ₁ ) и f ( x ₂ ) определяется новей интервал ( a , x ₂ ) или ( x ₁ , b ) , в котором локализован минимум. Найденный интервал снова делится двумя точками в том же отношении, причем одна из новых точек деления сов падает с уже использованной на предыдущем шаге.

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

Таким образом, длина интервала неопределенности на каждом шаге сжимается с коэффициентом 0,618. На первом шаге необходимы два вычисления функции, на каждом последующем – одно.

Длина интервала неопределенности после S вычислений значений f ( x ) составляет:

Алгоритм метода золотого сечения для минимизации функции f ( x ) складывается из следующих этапов:

1. Вычисляется значение функции f ( x₁ ) , где x₁ = a +0,382( b – a ) .
2. Вычисляется значение функции f ( x₂ ) , где x₁ = b +0,382( b – a ) .
3. Определяется новый интервал (a,x2) или (x1,b), в котором локализован минимум.
4. Внутри полученного интервала находится новая точка ( x₁ в случае 1) или ( x₂ в случае 2), отстоящая от его конца на расстоянии, составляющем 0,382 от его длины. В этой точке рассчитывается значение f ( x ). Затем вычисления повторяются, начиная с пункта 3, до тех пор, пока величина интервала неопределенности станет меньше или равна ε, где ε – заданное сколь угодно малое положительное число.

Блок-схема алгоритма поиска минимума функции f ( x ) методом золотого сечения.

Используя метод золотого сечения, минимизировать функцию f (х)= x 2 +2х на интервале (-3,5). Алина конечного интервала не­определенности не должна превосходить 0,2.

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode

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

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

Метод золотого сечения — это итеративный метод поиска экстремумов (минимума или максимума) функции одной переменной на заданном отрезке [a; b]. Метод золотого сечения был продемонстрирован в 1953 году Джеком Кифером. В его основе лежит принцип деления отрезка в пропорции золотого сечения.

Теоретические сведения

Пусть задана функция f(x) и отрезок [a; b], на котором требуется найти экстремум. Рассматриваемый отрезок делится в оба направления точками x1 и x2 в отношении золотого сечения. То есть:

φ — это пропорция золотого сечения.

Следовательно координаты x1 и x2 находятся по формулам:

Таким образом точки x1 и x2 делят отрезки [a; x2] и [x1; b] соответственно в пропорции золотого сечения. Это свойство далее будет использоваться для построения итеративного процесса вычисления экстремума функции.

Описание алгоритма

1. Задаются начальные параметры: границы отрезка [a; b] и точность вычислений ε.
2. Рассчитываются координаты точек деления: . Затем вычисляется значение функции f(x) в этих точках: . ЕСЛИ (случай поиска минимума функции. Для поиска точки максимума изменить неравенство на ), ТО. ИНАЧЕ.
3. ЕСЛИ требуемая точность достигнута: , ТО и конец алгоритма. ИНАЧЕ возврат к шагу 2.

Реализация алгоритма

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

Класс GoldenSection, позволяющий выполнить поиск экстремума функции на отрезке [a; b] с точностью ε, содержит (по порядку): определение константы пропорции золотого сечения φ, метод, вычисляющий значение целевой функции f(x), метод, выполняющий поиск минимума функции и метод, выполняющий поиск максимума функции.

Численные методы: решение нелинейных уравнений

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

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

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

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

В простейшем случае у нас имеется функция , заданная на отрезке ( a , b ) и принимающая определенные значения.

Каждому значению x из этого отрезка мы можем сопоставить число , это и есть функциональная зависимость, ключевое понятие математики.

Нам нужно найти такое значение при котором такие называются корнями функции

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

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

Простейшим методом нахождения корней уравнения является метод деления пополам или дихотомия.

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

Алгоритм состоит в следующем.

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

Поделим отрезок пополам и введем среднюю точку .

Тогда либо , либо .

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

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

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

К достоинствам метода деления пополам следует отнести его высокую надежность и простоту.

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

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

Метод Ньютона: теоретические основы

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

Уравнение касательной к функции в точке имеет вид:

В уравнении касательной положим и .

Тогда алгоритм последовательных вычислений в методе Ньютона состоит в следующем:

Сходимость метода касательных квадратичная, порядок сходимости равен 2.

Таким образом, сходимость метода касательных Ньютона очень быстрая.

Запомните этот замечательный факт!

Без всяких изменений метод обобщается на комплексный случай.

Если корень является корнем второй кратности и выше, то порядок сходимости падает и становится линейным.

Упражнение 1. Найти с помощью метода касательных решение уравнения на отрезке (0, 2).

Упражнение 2. Найти с помощью метода касательных решение уравнения на отрезке (1, 3).

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

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

Визуализация метода Ньютона

Метод Ньютона (метод касательных) применяется в том случае, если уравнение f(x) = 0 имеет корень , и выполняются условия:

1) функция y= f(x) определена и непрерывна при ;

2) f(a)·f(b) 0. Таким образом, выбирается точка с абсциссой x₀, в которой касательная к кривой y=f(x) на отрезке [a;b] пересекает ось Ox. За точку x₀ сначала удобно выбирать один из концов отрезка.

Рассмотрим метод Ньютона на конкретном примере.

Пусть нам дана возрастающая функция y = f(x) =x 2 -2, непрерывная на отрезке (0;2), и имеющая f ‘(x) = 2x > 0 и f ”(x) = 2 > 0.

Уравнение касательной в общем виде имеет представление:

В нашем случае: y-y₀=2x₀·(x-x₀). В качестве точки x₀ выбираем точку B₁(b; f(b)) = (2,2). Проводим касательную к функции y = f(x) в точке B₁, и обозначаем точку пересечения касательной и оси Ox точкой x₁. Получаем уравнение первой касательной:y-2=2·2(x-2), y=4x-6.

Точка пересечения касательной и оси Ox: x₁ =

Рисунок 2. Результат первой итерации

Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x₁, получаем точку В₂ =(1.5; 0.25). Снова проводим касательную к функции y = f(x) в точке В₂, и обозначаем точку пересечения касательной и оси Ox точкой x₂.

Точка пересечения касательной и оси Ox: x₂ = .

Рисунок 3. Вторая итерация метода Ньютона

Затем находим точку пересечения функции y=f(x) и перпендикуляра, проведенного к оси Ox через точку x₂, получаем точку В₃ и так далее.

В3 = ()

Рисунок 4. Третий шаг метода касательных

Первое приближение корня определяется по формуле:

= 1.5.

Второе приближение корня определяется по формуле:

=

Третье приближение корня определяется по формуле:

Таким образом, i-ое приближение корня определяется по формуле:

Вычисления ведутся до тех пор, пока не будет достигнуто совпадение десятичных знаков, которые необходимы в ответе, или заданной точности e – до выполнения неравенства |xi–xi-1|