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.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 «Kursovayarabota 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
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)) NEXTj 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 «Kursovayarabota po informatike OTLADKA»
LOCATE 2, 18
PRINT «Gruppa PS0601,Adamskiy Alexey»
PRINT
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 PRINTUSING " ##.###### #.##### #.##### #.##### #.##### #.##### #.#####";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)
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)
x1=-1, x2=0.F(x)=L(x1)*x2+L(x2)*x, [a;b]=[-2;1].
Очевидно, что L(x1)=1, L(x2)=0, а минимум функции F(x) лежит в точке x=0
Cхемы алгоритмов других модулей совпадаютс приведёнными в пп 5.1.1 и 5.2.1
5.3.1 Кодпрограммыприпрогонке
DECLARE FUNCTION dihotom(a, b, e, LX1, LX2)
DECLARE FUNCTION LX (k,x(), y(), xl)
DECLARE FUNCTION F (xmin,LX1, LX2)
CLS
LOCATE 1, 15
PRINT «Kursovayarabota po informatike OTLADKA»
LOCATE 2, 18
PRINT «Gruppa PS0601,Adamskiy Alexey»
PRINT
x(0) = -2: x(1) = 0: x(2)= 1
y(0) = 4: y(1) = 0: y(2) =1
LX1 = LX(2, x(), y(), -1)
LX2 = LX(2, x(), y(), 0)
PRINT TAB(10);«Znacheniya polinoma Lagranzha v x1,x2»
PRINT TAB(15);«L(x1)=»; LX1; «L(x2)=»; LX2
PRINT
PRINT TAB(10); «Poiskminimuma F(x)»
xmin = dihotom(-2, 1,.0001, LX1, LX2)
PRINT TAB(10);«Minimum F(x): xmin=»; xmin; «F(xmin)=»; F(xmin, LX1, LX2)
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 PRINT USING " ##.###### #.##### #.##### #.##### #.######.##### #.#####"; a; b; x1; x2; F(x1, LX1, LX2); F(x2, LX1, LX2); b — a x1= (a + b — e / 4) / 2 x2 = (a + b + e / 4) / 2 IF F(x1, LX1, LX2) > F(x2,LX1, LX2) THEN a = x1 ELSE b = x2 LOOP UNTIL ABS(b — a)
dihotom = (a + b) / 2
END FUNCTION
FUNCTION F (x, LX1, LX2)
F = LX1 * x ^ 2 + LX2 * x
END FUNCTION
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)) NEXTj l = l + L1 NEXT i
LX = l
END FUNCTION
5.3.2 Результат прогонки программы
/>
Программа отработала верно
Проверка результатов тестирования в среде MathCAD не требуется из-за очевидностиполученных результатов.
6. Детализированная схема алгоритма
/>
/>
/>
/>
7. Кодпрограммы
DECLARE FUNCTION dihotom (a, b, E,LX1, LX2)
DECLARE FUNCTION LX (k, x(), y(), xl)
DECLARE FUNCTION F (xmin, LX1, LX2)
CLS
LOCATE 1, 15
PRINT «Kursovaya rabota poinformatike»
LOCATE 2, 18
PRINT «Gruppa PS0601, AdamskiyAlexey»
PRINT
LOCATE 5, 18
INPUT «Vveditek,a,b,x1,x2,E»; k, a, b, x1, x2, E
DIM x(0 TO k) AS SINGLE
DIM y(0 TO k) AS SINGLE
DATA 0,0.1, 0.2,0.3,0.4,0.5,0.6 FOR i= 0 TO k READ x(i) NEXT i
DATA 1.858652,1.851659,1.851401,1.848081,1.841914,1.833125,1.821948FOR i = 0 TO k READ y(i) NEXT i
LX1 = LX(k, x(), y(), x1)
LX2 = LX(k, x(), y(), x2)
PRINT TAB(10); «Znacheniyapolinoma Lagranzha v x1,x2»
PRINT TAB(15); «L(x1)=»;LX1; «L(x2)=»; LX2
PRINT
PRINT TAB(10); «Poisk minimumaF(x)»
xmin = dihotom(a, b, E, LX1, LX2)
PRINT TAB(10); «Minimum F(x):xmin=»; xmin; «F(xmin)=»; F(xmin, LX1, LX2)
END
FUNCTION dihotom (a, b, E, LX1, LX2)
PRINT TAB(10); «Promezhutochnierezul`tati»
PRINT " a b x1 x2 f(x1) f(x2) b-a"DO x1 = (a + b — E / 1.3) / 2 x2 = (a + b + E / 1.3) / 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 b — a
dihotom = (a + b) / 2
END FUNCTION
FUNCTION F (x, LX1, LX2)
F = LX1 * x ^ 2 — 2.5 * LX2 * x — 3
END FUNCTION
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
8. Полученные результаты
/>
Выводы
1. Обоснованы и выбраны численные методы: — интерполяции таблично заданнойфункции с помощью полинома Лагранжа — одномерной оптимизации по методудихотомии
2. Разработаны, протестированы модули, реализующие следующиеметоды: — поиск значенийинтерполяционного многочлена Лагранжа в требуемых точках (x1, x2) — поиск минимума функции F(x) с помощью метода дихотомии с требуемой точностью
3. Программа модульная, содержит следующие модули: — основной модуль, принимающийисходные данные, передающий их на обработку и выводящий конечный ипромежуточный результаты — модуль поиска значений интерполяционного многочленав точках x1 и x2 — модуль, задающийF(x) с параметрами LX1, LX2, найденными модулеминтерполирования — модуль поиска минимума функции F(x) на отрезке [a;b] методом дихотомии
4. Получены следующие результаты: Полином Лагранжа L(x1)=1.853346, L(x2)=1.823337
Искомый минимум функции F(x) найден сточностью E=0.0001, xmin=1.229506
F(xmin)=-5.802835
5. Полученные результаты были проверены в MathCAD: Полученные в ходе работы программы результаты, оченьхорошо согласуются с результатами, полученными в MathCAD, требуемая точность E=0.0001 соблюдалась, если научно подойти к выбору d в методе дихотомии.
Список литературы
1. Гловацкая А.П., Загвоздкина А.В., Кравченко О.М.,Семёнова Т.И., Шакин В.Н: Практикум Численные методы и оптимизация подисциплине «Информатика»
Москва, МТУСИ, 2004г.
2. А.П.Гловацкая: Конспект лекций «Информатика.Вычислительная математика» Москва, МТУСИ, 2006г.
3. Семёнова Т.И, Шакин В.Н.: Практикум Математическийпакет MathCAD в дисциплине «Информатика», Москва,МТУСИ, 2006г.
4. А.В. Загвоздкина: Конспект лекций за 1 семестр2007-2008 учебного года