Метод золотого сечения программа

Метод золотого сечения программа

Нахождение экстремума функции Методом Золотого Сечения.

Условие:
Вычислить экстремум функции y(x)=x+lg(1/x); с заданной точностью ε,
т.е. найти координаты (xe, ye).

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

Решение:

В программе есть смысл оформить следующие подпрограммы:

  1. Процедура ExtremGC, вычисляющая экстремум с заданной точностью (будет вызываться из главной программы)
      Входные параметры:
  2. границы интервала [a, b]
  3. начальное значение шага dx
  4. точность ε
    • Выходные:

    • координаты (xe, ye) экстремума
    • конечное значение шага dx
    • количество разбиений n
  5. Функции dannFunc, вычисляющая значение y(x) (будет вызываться из процедура ExtremGC) и позволяющая в будущем достаточно легко адаптировать код программы под новые функции.


На Pascal для функции y(x)=x+lg(1/x); это будет выглядеть так:

function dannFunc (x: real): real;
begin
if x

Первая строка проверяет входной параметр на допустимость (индивидуально для конкретной функции) и выдает соответствующее сообщение.
Вторая строка возвращает вычисленное значение функции.
Так как в Pascal отсутствует функция десятичного логарифма, но есть натурального, то воспользовался формулой lgA = lnA / ln10;

<Нахождение экстремума функции на отрезке. Метод золотого сечения>
procedure ExtremGC (a, b, eps: real;
var xe, ye, dx1: real;
var nn: longint);
var x1, x2, zc, y1, y2 :real;
begin
nn:= 0;
zc:=(1+sqrt(5))/2; <

1.618 -константа золотого сечения>

while (b-a>eps) do
begin
x1:=b-((b-a)/zc); x2:=a+((b-a)/zc);
y1:= dannFunc(x1); y2:= dannFunc(x2);
if y1>=y2 then a:=x1 else b:=x2; <поиск минимума>

Данная процедура получает семь параметров. Первые три параметра передаются по значению, а следующие четыре — по ссылке.

Рассчитываем переменную zc:=(1+sqrt(5))/2; .
По идее – это константа, так как все данные в формуле известны и не зависят от параметров, но оформить ее как константу нельзя, потому что используется функция извлечения квадратного корня.

Читайте также:  Microsoft basic optical mouse

Цикл while(b-a>eps) do сознательно не оптимизирован… Конечно, метод золотого сечения позволяет (т.е. достаточно) считать функцию только в одной новой точке, а не в двух (при каждой итерации как сделано в моем примере), но для учебной задачи, где заданная функция достаточно проста и машинное время на ее выполнение не критично, это вполне допустимо (если, конечно, Ваш преподаватель не акцентировал на этом моменте особое внимание).

Суть метода (цикла): имеющийся отрезок [a,b] делится точками х1 и х2 где a ‘);)

  • Инициализация переменных с клавиатуры (
  • readln(a, b, eps); )

  • Вызов процедуры ExtrеmGC(a, b, eps, xe, ye, dx1, n);
  • Вывод на экран переменных xe, ye, dx1, n (в удовлетворяющем Ваш вкус виде), которые получили инициализацию в ExtrеmGC.
  • Заданная функция в моем примере y(x)=x+lg(1/x); имеет два максимума в точках +0 и +∞ и один минимум в точке

    0,4343. Значение функции в точке экстремума y(0,4343)=

    Правила ввода функции

    1. Примеры правильного написания F(x):
      1) 10•x•e 2x ≡ 10*x*exp(2*x)
      2) x•e -x +cos(3x) ≡ x*exp(-x)+cos(3*x)
      3) x 3 -x 2 +3 ≡ x^3-x^2+3

    Не всегда можно определить заранее, сколько раз придется вычислять функцию. Метод золотого сечения почти столь же эффективен при n-2, что и метод Фибоначчи, однако при этом не требуется знать n – количество вычислений функции.
    Сущность этого метода заключается в следующем. Интервал неопределенности делится на две неравные части так, что отношение длины большего отрезка к длине всего интервала равно отношению длины меньшего отрезка к длине большего (рис 3).

    где τ — «золотое сечение»

    На каждом шаге этой итеративной процедуры, кроме первого, вычисляется только одно значение функции. Однако Химмельблау рекомендовал вычислять на каждом шаге две точки, для того чтобы не накапливалась погрешность, так как τ имеет приближенное значение (рис 4).
    Если длина конечного интервала неопределенности равна δ, то для достижения требуемой точности число вычислений значений функции по методу золотого сечения можно найти по условию

    Читайте также:  Функция тарирования что это

    Пример . Методом золотого сечения найти точку минимума x * функции f(x) на отрезке [a;b] с точностью ε и значение целевой функции в этой точке:
    f(x)=x 4 +2x 2 +4x+1=0 , [-1;0], ε=0.1
    Решение. Положим a1 = a, b1 = b. Вычислим λ1 = a1 + (1- 0.618)(b1 — a1), μ1 = a1 + 0.618(b1 — a1).
    Вычислим f(λ1) = -0.5623, f(μ2) = -0.2149
    Итерация №1.
    Поскольку f(λ1) f(μ2), то a3 = -0.7639, b3 = b2, λ3 = -0.618
    μ3 = a3 + 0.618(b3 — a3) = -0.7639 + 0.618(-0.382 +0.7639), f(μ3) = f(-0.5279) = -0.5623
    Итерация №3.
    Поскольку f(λ3) x как середину интервала [a,b]: x=(-0.618-0.70818104)/2 = -0.66309052.
    Ответ: x = -0.66309052; F(x) = -0.57965758

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

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

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

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

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

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

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

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

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

    Читайте также:  Скорость mbps что это

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

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

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

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

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

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

    Ссылка на основную публикацию
    Adblock detector