Программа вычисления минимума заданной функции (стр. 1 из 2)
1. Индивидуальное задание
Вычислить минимум функции F(x)=L(x1)x2-2.5L(x2)x-3 на отрезке [a;b] с точностью ε.
L(x1), L(x2) значения интерполяционного многочлена, построенного для таблично заданной функции f(x) в точках x1, x2.
Исходные данные:
a=0; b=2;
x1=0.041770;
x2=0.587282;
ε=10-4;
| x | 0 | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 |
| f(x) | 1.858652 | 1.851659 | 1.851401 | 1.848081 | 1.841914 | 1.833125 | 1.821948 |
2. Постановка задачи и формализация
Для решения поставленной задачи необходимо разработать программные модули, выполняющие следующие действия:
- главный модуль, получающий исходные данные (таблично заданную f(x), a, b, x1, x2, ε), передающий их на обработку и выводящий промежуточные и конечные результаты (L(x1), L(x2), найденный минимум функции)
- модуль поиска значения интерполяционного многочлена L(x1), L(x2)
- модуль поиска минимума функции F(x) численным методом, использующий L(x1), L(x2) как коэффициенты при x2 и x
3. Выбор, обоснование, краткое описание методов
3.1 Поиск значений интерполяционного многочлена в точках x1 и x2
3.1.1 Постановка задачи
Требуется найти L(x1), L(x2) - значения интерполяционного многочлена, построенного для таблично заданной функции f(x) в точках x1,x2 Здесь решается задача аппроксимации, которая состоит в замене некоторой функции
у = f(х) другой функцией g(х,а0,а1,...,an) таким образом, чтобы отклонение g(х,а0,а1,...,an) от f(x) удовлетворяло в некоторой области (на множестве X) определенному условию. Этим условием является g(xi,a0,a1,…an)=f(xi) при i=0,n, которое означает, что аппроксимируемая функция f(x) совпадает с g(xi,a0,a1,…an) в т.н. узлах интерполяции x0,x1,…,xn. Это частный случай аппроксимации, называемый интерполяцией.
3.1.2 Выбор и описание метода
Задача интерполяции может быть решена множеством методов, среди которых:
1) интерполяционный многочлен Лагранжа
интерполяционные формулы Ньютона Выберем для решения задачи интерполяции интерполяционный многочлен Лагранжа, так как его построение просто в алгоритмизации, не требует вычисления конечных разностей функции, , может быть умещено в одну небольшую процедуру – функцию.
Кроме того, метод Лагранжа работает и для неравноотстоящих интерполяционных узлов, к тому же не имеет различий, если точки x1 и x2 для поиска значений L(x1), L(x2) лежат в начале или в конце отрезка, где таблично задана функция.
Описание метода:
Задача интерполяции будем решать построением многочлена Лагранжа, который имеет вид:
Степень многочлена n обеспечивается n+1 интерполяционным узлом. Для задания таблицы значений функции будем использовать два массива x() и y(). Полином должен удовлетворять условию Ln(xi)=y(i)
3.2 Поиск минимума функции F(x) на отрезке [a;b]
3.2.1 Постановка задачи
Необходимо численным методом найти минимум функции F(x)=L(x1)x2-2.5L(x2)x-3
на отрезке [a;b] с точностью ε, при том, что L(x1) и L(x2) – коэффициенты, полученные вычислением полинома Лагранжа в точках x1, x2. Это задача одномерной оптимизации.
Выбор метода: Для решения задачи одномерной оптимизации существует множество методов, среди которых:
1) метод прямого перебора
2) метод дихотомии
3) метод золотого сечения
4) метод Фибоначчи
5) метод касательных
6) метод Ньютона
оптимизация методом квадратичной интерполяции Выберем метод дихотомии, т.к. он прост в алгоритмизации, обеспечивает быструю сходимость (на каждой итерации отрезок неопределённости сужается почти вдвое). Его недостаток в виде необходимости многократного вычисления F(x) не играет особой роли, т.к. F(x) – обыкновенный полином и расчёт его значений не затратит много ресурсов ПК.
Описание метода:
Пусть f(x)- унимодальная на [a;b] и требуется найти минимум f(x) с абсолютной погрешностью Е. Идея метода дихотомии состоит в проведении на каждой итерации двух отсчётов (вычислений значений функции), отстоящих от середины отрезке неопределённости [а;b] на величину de[0;2E] и сравнения значения исследуемой функции в двух точках х(n-1)и
x(n-1). определяемых рекуррентными формулами:
 |
 |
Если
, то 
Иначе
N = 1,2,...- номер итерации, а0=а , b0 = b .
Вычисления проводятся до тех пор, пока b-а >Е.
Тогда с абсолютной погрешностью, не превосходящей Е, полагают
x*=(aN+bN)/2
Длина конечного отрезка неопределённости:
L0=b-a – длина начального отрезка
На каждой итерации отрезок неопределённости [aN;bN] уменьшается примерно вдвое. Число отсчётов функции n и число итераций N связаны соотношением N=n/2
Практически величина d выбирается из условий различимости двух отсчётов функции
Процедура поиска минимума методом дихотомии использует большее количество отсчётов функции для локализации точки минимума на отрезке заданной длины.
Геометрическая иллюстрация метода дихотомии
4. Проверка условий сходимости методов. Поиск значений интерполяционного многочлена в точках x1 и x2
Для правильной работы этого метода необходимо, чтобы функция была ограничена на отрезке интерполирования. Выполнение этого условия очевидно по заданию.
Условия унимодальности на отрезке [a;b] (первая производная возрастает, вторая больше нуля) выполняются, следовательно, отрезок [a;b] остаётся таким же как по заданию [0;2]
5. Тестирование программных модулей
5.1 Тестирование модуля поиска значений интерполяционного многочлена в точках x1 и x2
Рассчитаем значения функции f(x)=x2, заданной в виде таблицы
в точках x1=-1, x2=0.5. Т.к. исходная функция – полином, то интерполирующая будет ей в точности соответствовать и f(x.1)=L(x1)=1, f(x2)=L(x2)=0.25
Схема алгоритма управляющей программы
Схема алгоритма модуля поиска значений интерполяционного многочлена в точкexl
5.1.1 Код тестирующей программы
DECLARE FUNCTION LX (k, x(), y(), xl)
CLS
LOCATE 1, 15
PRINT "Kursovaya rabota po informatike OTLADKA"
LOCATE 2, 18
PRINT "Gruppa PS0601, Adamskiy Alexey"
DIM x(0 TO 2) AS SINGLE
DIM y(0 TO 2) AS SINGLE
x(0) = -2: x(1) = 0: x(2) = 1
y(0) = 4: y(1) = 0: y(2) = 1
PRINT TAB(20); "L(x1)=f(x1)="; LX(2, x(), y(), -1)
PRINT TAB(20); "L(x2)=f(x2)="; LX(2, x(), y(), .5)
END
FUNCTION LX (k, x(), y(), xl)
l = 0 FOR i = 0 TO k L1 = y(i) FOR j = 0 TO k IF i <> j THEN L1 = L1 * (xl - x(j)) / (x(i) - x(j)) NEXT j l = l + L1 NEXT i
LX = l
END FUNCTION
Результат тестирования
Модуль отработал верно.
5.2 Тестирование модуля поиска минимума функции F(x) на отрезке [a;b]
программный модуль минимум функция
Проверим работоспособность модуля, найдя с его помощью минимум функции F(x)=x2 на отрезке [a;b]. Очевидно, что xmin=0, F(xmin)=0.
5.2.1 Схема алгоритма тестирующей программы:
Схема алгоритма управляющей программы
Схема алгоритма модуля f(x,LX1,LX2)
5.2.2 Кодтестирующейпрограммы
DECLARE FUNCTION dihotom (a, b, e, LX1, LX2)
DECLARE FUNCTION F (xmin, LX1, LX2)
CLS
LOCATE 1, 15
PRINT "Kursovaya rabota po informatike OTLADKA"
LOCATE 2, 18
PRINT "Gruppa PS0601, Adamskiy Alexey"
xmin = dihotom(-2, 1, .0001, 1, 0)
PRINT TAB(10); "Minimum F(x): xmin="; xmin; "F(xmin)="; F(xmin, 1, 0)
END
FUNCTION dihotom (a, b, e, LX1, LX2)
PRINT TAB(10); "Promezhutochnie rezul`tati"
PRINT " a b x1 x2 f(x1) f(x2) b-a" DO x1 = (a + b - e / 4) / 2 x2 = (a + b + e / 4) / 2 PRINT USING " ##.###### #.##### #.##### #.##### #.##### #.##### #.#####"; a; b; x1; x2; F(x1, LX1, LX2); F(x2, LX1, LX2); b - a IF F(x1, LX1, LX2) > F(x2, LX1, LX2) THEN a = x1 ELSE b = x2 LOOP UNTIL ABS(b - a) <= e
dihotom = (a + b) / 2
END FUNCTION
FUNCTION F (x, LX1, LX2)
F = LX1 * x ^ 2 + LX2 * x
END FUNCTION
5.2.3 Результат тестирования
Модуль отработал верно. Минимум найден корректно.
5.3 Прогонка программы
Протестируем всю программу, задав
(тоже самое, что f(x)=x2)