Описание логической структуры решения задачи

Аннотация

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Общие сведения

Для реализации поставленной задачи, а именно, для нахождения экстремумов функции на промежутке от a=0 до b=2 с точностью 0,001 , а так же для расчета некоторого количества значений функции, мной была составлена программа на алгоритмическом языке Бейсик.

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

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

 

 

 

 

 

 

 

 

Описание логической структуры решения задачи.

1.Метод квадратичной интерполяции-экстраполяции.

Данный метод относится  к классу прямых методов, опирающихся  на идею построения аппроксимирующего  полинома второго порядка на основании  информации о значениях функции  в n+1 точке – узлах интерполяции.

Начальный этап

1. Выбрать произвольную точку x¹ÎRⁿ
2. Задаться величиной шага h=0.001
3. Определить погрешность
4. Положить счётчик числа итераций равным 1, а также b=x¹

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

Шаг 1. Вычислить f_i в 3-х точках: a, b и с – центральной (b) и двух соседних: a=b-h, c=b+h. Затем, по формуле

  (1)

или

     (2)

найти аппроксимирующий минимум d

Шаг 2. Проверить критерий близости 2-х точек b и d

 и

Если оба условия  выполняются – фиксируем аппроксимирующий минимум

и останавливаемся. Если оба критерия не выполняются, полагаем b=d и возвращаемся на шаг 1.

 

2. Аналитический способ отделения экстремумов

Аналитический способ отделения экстремумов основан на следующем принципе:

1. " Если функция F(x), определяющая уравнение F(x)=0, в точке x имеет точку экстремума, то производная F`(x) = 0.

Для отделения корней аналитическим способом выбирается отрезок [A;B], на котором находятся все интересующие вычислителя экстремумы. Причем на отрезке [A;B] функция F(x) определена, непрерывна и F(a)*F(b)<0. Требуется указать все частичные отрезки [a;b], содержащие по одной точке экстремума.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Используемые технические  и программные средства.

Разработка данного  программного комплекса велась в  среде разработки «MS QBasic», которая представляет средство для написания, то есть текстовый редактор, отладки и исполнения программы. То есть, по сути, является интерпретатором языка Бейсик, что означает, что для выполнения программы на компьютере необходим «MS QBasic» либо один из его аналогов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Входные и выходные данные.

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

А так же пределы ее интегрирования:

a = 2; b = 5

И точность расчета равная 0.00001.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Графическое изображение  алгоритма решения задачи.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Текст программы на языке Бейсик

DECLARE FUNCTION OTD% (a!, b!, e!)

DECLARE FUNCTION FU! (x!)

DECLARE FUNCTION FU1! (x!)

DECLARE FUNCTION mki! (x1!, h!, e!)

DIM n!, x!, dx!, a!, b!, e!

DIM count%

CLS

x = 0

dx = 1

INPUT "n="; n

PRINT "ЙННННННННЛНННННННННННННННЛННННННННННННННН»"

PRINT "є"; "#"; TAB(10); "є"; "x"; TAB(26); "є"; "y"; TAB(42); "є"

FOR i = 1 TO n

y! = FU(x!)

PRINT "МННННННННОНННННННННННННННОННННННННННННННН№"

PRINT "є"; i; TAB(10); "є"; x; TAB(26); "є"; y; TAB(42); "є"

x = x + dx

NEXT i

PRINT "ИННННННННКНННННННННННННННКНННННННННННННННј"

INPUT "a="; a

INPUT "b="; b

INPUT "e="; e

count = OTD(a, b, e)

PRINT "extremum count: "; count

 

FUNCTION FU! (x!)

FU = .1 * x ^ 3 - 2 * x ^ 2 + 10 * x

END FUNCTION

 

FUNCTION FU1! (x!)

FU1 = .3 * x ^ 2 - 4 * x + 10

END FUNCTION

 

FUNCTION mki! (x1!, h!, e!)

DIM f0!, f1!, f2!, x0!, x2!, c!, b!

xm = x1

DO

x1 = xm

x0 = x1 - h

x2 = x1 + h

f0 = FU(x0)

f1 = FU(x1)

f2 = FU(x2)

c = 1 / 2 / h / h * (f0 - 2 * f1 + f2)

b = ((-1) * f0 * (2 * x1 + h) + 4 * f1 * x1 - f2 * (2 * x1 - h)) / 2 / h / h

xm = (-1) * b / 2 / c

LOOP UNTIL ((xm - x1) < e)

mki = xm

END FUNCTION

 

FUNCTION OTD% (a!, b!, e!)

DIM h!, xn!, dx!, x1!

DIM count%

count = 0

xn = a

dx = .2

DO

IF ((FU1(xn) < 0) AND (FU1(xn + dx) > 0)) OR ((FU1(xn) > 0) AND (FU1(xn + dx) < 0)) THEN

h = mki(xn, .1, .001)

count = count + 1

PRINT "extremum: ("; h; ";"; FU(h); ")"

END IF

xn = xn + dx

LOOP WHILE (xn <= (b - dx))

OTD = count

END FUNCTION

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Контрольный пример.

В результате выполнения программы было рассчитано 5 значений функции, а полученные данные были сведены  в таблицу, так же были найдены экстремумы функции f(x)=0.

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

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

В ходе исследования графика  видно, что на участке [2;5], исследуемой функции, есть только один экстремум, он же максимум функции, и визуально его координаты совпадают с расчетными.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованное литературы:

1. И.П. Натансон : Краткий курс высшей математики
2. И.И. Валуцэ, Г.Д. Дилигун : Математика для техникумов
3. И.А. Сахарников : Высшая математика
4. П.П. Коровнин : Математический анализ
5. Л.И.Лихтарников, А.Н. Поволоцкий : основы математического анализа