Курсовая работа: Программа вычисления минимума заданной функции

👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

Вычислить минимум функции F(x)=L(x 1
)x 2
-2.5L(x 2
)x-3 на отрезке [a;b] с точностью ε.
L(x 1
), L(x 2
) значения интерполяционного многочлена, построенного для таблично заданной функции f(x) в точках x 1
, x 2
.
2. Постановка задачи и формализация

Для решения поставленной задачи необходимо разработать программные модули, выполняющие следующие действия:
- главный модуль, получающий исходные данные (таблично заданную f(x), a, b, x 1
, x 2
, ε), передающий их на обработку и выводящий промежуточные и конечные результаты (L(x 1
), L(x 2
), найденный минимум функции)
- модуль поиска значения интерполяционного многочлена L(x 1
), L(x 2
)
- модуль поиска минимума функции F(x) численным методом, использующий L(x 1
), L(x 2
) как коэффициенты при x 2
и x
3. Выбор, обоснование, краткое описание методов

3.1 Поиск значений интерполяционного многочлена в точках
x
1

и
x
2


Требуется найти L(x 1
), L(x 2
) - значения интерполяционного многочлена, построенного для таблично заданной функции f(x) в точках x 1
,x 2
Здесь решается задача аппроксимации, которая состоит в замене некоторой функции
у = f(х) другой функцией g(х,а 0
,а 1
,...,a n
) таким образом, чтобы отклонение g(х,а 0
,а 1
,...,a n
) от f(x) удовлетворяло в некоторой области (на множестве X) определенному условию. Этим условием является g(x i
,a 0,
a 1
,…a n
)=f(x i
) при i=0,n, которое означает, что аппроксимируемая функция f(x) совпадает с g(x i
,a 0,
a 1
,…a n
) в т.н. узлах интерполяции x 0
,x 1
,…,x n
.
Это частный случай аппроксимации, называемый интерполяцией.
Задача интерполяции может быть решена множеством методов, среди которых:
1) интерполяционный многочлен Лагранжа
интерполяционные формулы Ньютона Выберем для решения задачи интерполяции интерполяционный многочлен Лагранжа, так как его построение просто в алгоритмизации, не требует вычисления конечных разностей функции, , может быть умещено в одну небольшую процедуру – функцию.
Кроме того, метод Лагранжа работает и для неравноотстоящих интерполяционных узлов, к тому же не имеет различий, если точки x 1
и x 2
для поиска значений L(x 1
), L(x 2
) лежат в начале или в конце отрезка, где таблично задана функция.
Задача интерполяции будем решать построением многочлена Лагранжа, который имеет вид:
Степень многочлена n обеспечивается n+1 интерполяционным узлом. Для задания таблицы значений функции будем использовать два массива x() и y(). Полином должен удовлетворять условию L n
(x i
)=y(i)
Необходимо численным методом найти минимум функции F(x)=L(x 1
)x 2
-2.5L(x 2
)x-3
на отрезке [a;b] с точностью ε, при том, что L(x 1
) и L(x 2
) – коэффициенты, полученные вычислением полинома Лагранжа в т очках
x 1
, x 2
. Это задача одномерной оптимизации.
Выбор метода:
Для решения задачи одномерной оптимизации существует множество методов, среди которых:
оптимизация методом квадратичной интерполяции Выберем метод дихотомии, т.к. он прост в алгоритмизации, обеспечивает быструю сходимость (на каждой итерации отрезок неопределённости сужается почти вдвое). Его недостаток в виде необходимости многократного вычисления F(x) не играет особой роли, т.к. F(x) – обыкновенный полином и расчёт его значений не затратит много ресурсов ПК.
Пусть f(x)- унимодальная на [a;b] и требуется найти минимум f(x) с абсолютной погрешностью Е. Идея метода дихотомии состоит в проведении на каждой итерации двух отсчётов (вычислений значений функции), отстоящих от середины отрезке неопределённости [а;b] на величину de[0;2E] и сравнения значения исследуемой функции в двух точках х (
n
-1)
и
x (
n
-1)
. определяемых рекуррентными формулами:
N = 1,2,...- номер итерации, а 0
=а , b 0
= b .
Вычисления проводятся до тех пор, пока b-а >Е.
Тогда с абсолютной погрешностью, не превосходящей Е, полагают
Длина конечного отрезка неопределённости:
L 0
=b-a – длина начального отрезка
На каждой итерации отрезок неопределённости [a N
;b N
] уменьшается примерно вдвое. Число отсчётов функции n и число итераций N связаны соотношением N=n/2
Практически величина d выбирается из условий различимости двух отсчётов функции
Процедура поиска минимума методом дихотомии использует большее количество отсчётов функции для локализации точки минимума на отрезке заданной длины.
Геометрическая иллюстрация метода дихотомии

4. Проверка условий сходимости методов.
Поиск значений интерполяционного многочлена в точках
x
1

и
x
2


Для правильной работы этого метода необходимо, чтобы функция была ограничена на отрезке интерполирования. Выполнение этого условия очевидно по заданию.
Условия унимодальности на отрезке [a;b] (первая производная возрастает, вторая больше нуля) выполняются, следовательно, отрезок [a;b] остаётся таким же как по заданию [0;2]
5. Тестирование программных модулей

5.1 Тестирование модуля поиска значений интерполяционного многочлена в точках
x
1

и
x
2


Рассчитаем значения функции f(x)=x 2
, заданной в виде таблицы
в точках x 1
=-1, x 2
=0.5. Т.к. исходная функция – полином, то интерполирующая будет ей в точности соответствовать и f(x .1
)=L(x 1
)=1, f(x 2
)=L(x 2
)=0.25
Схема алгоритма управляющей программы

Схема алгоритма модуля поиска значений интерполяционного многочлена в точк
e
xl

DECLARE FUNCTION LX (k, x(), y(), xl)
PRINT "Kursovaya rabota po informatike OTLADKA"
PRINT "Gruppa PS0601, Adamskiy Alexey"
PRINT TAB(20); "L(x1)=f(x1)="; LX(2, x(), y(), -1)
PRINT TAB(20); "L(x2)=f(x2)="; LX(2, x(), y(), .5)
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
5.2 Тестирование модуля поиска минимума функции
F
(
x
) на отрезке [
a
;
b
]

Проверим работоспособность модуля, найдя с его помощью минимум функции F(x)=x 2
на отрезке [a;b]. Очевидно, что x min
=0, F(x min
)=0.
5.2.1 Схема алгоритма тестирующей программы:

Схема алгоритма управляющей программы

Схема алгоритма модуля
f
(
x
,
LX
1,
LX
2)

DECLARE FUNCTION dihotom (a, b, e, LX1, LX2)
DECLARE FUNCTION F (xmin, LX1, LX2)
PRINT "Kursovaya rabota po informatike OTLADKA"
PRINT "Gruppa PS0601, Adamskiy Alexey"
PRINT TAB(10); "Minimum F(x): xmin="; xmin; "F(xmin)="; F(xmin, 1, 0)
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
Модуль отработал верно. Минимум найден корректно.
Протестируем всю программу, задав (тоже самое, что f(x)=x 2
)
x 1
=-1, x 2
=0. F(x)=L(x 1
)*x 2
+L(x 2
)*x, [a;b]=[-2;1].
Очевидно, что L(x 1)
=1, L(x 2
)=0, а минимум функции F(x) лежит в точке x=0
Cхемы алгоритмов других модулей совпадают с приведёнными в пп 5.1.1 и 5.2.1
DECLARE FUNCTION dihotom (a, b, e, LX1, LX2)
DECLARE FUNCTION LX (k, x(), y(), xl)
DECLARE FUNCTION F (xmin, LX1, LX2)
PRINT "Kursovaya rabota po informatike OTLADKA"
PRINT "Gruppa PS0601, Adamskiy Alexey"
PRINT TAB(10); "Znacheniya polinoma Lagranzha v x1,x2"
PRINT TAB(15); "L(x1)="; LX1; "L(x2)="; LX2
PRINT TAB(10); "Poisk minimuma F(x)"
xmin = dihotom(-2, 1, .0001, LX1, LX2)
PRINT TAB(10); "Minimum F(x): xmin="; xmin; "F(xmin)="; F(xmin, LX1, LX2)
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) <= e
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
Проверка результатов тестирования в среде MathCAD не требуется из-за очевидности полученных результатов.
6. Детализированная схема алгоритма

DECLARE FUNCTION dihotom (a, b, E, LX1, LX2)
DECLARE FUNCTION LX (k, x(), y(), xl)
DECLARE FUNCTION F (xmin, LX1, LX2)
PRINT "Kursovaya rabota po informatike"
PRINT "Gruppa PS0601, Adamskiy Alexey"
INPUT "Vvedite k,a,b,x1,x2,E"; k, a, b, x1, x2, E
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.821948 FOR i = 0 TO k READ y(i) NEXT i
PRINT TAB(10); "Znacheniya polinoma Lagranzha v x1,x2"
PRINT TAB(15); "L(x1)="; LX1; "L(x2)="; LX2
PRINT TAB(10); "Poisk minimuma F(x)"
PRINT TAB(10); "Minimum F(x): xmin="; xmin; "F(xmin)="; F(xmin, LX1, LX2)
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 / 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 <= E
F = LX1 * x ^ 2 - 2.5 * LX2 * x - 3
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
1. Обоснованы и выбраны численные методы:
- интерполяции таблично заданной функции с помощью полинома Лагранжа - одномерной оптимизации по методу дихотомии
2. Разработаны, протестированы модули, реализующие следующие методы:
- поиск значений интерполяционного многочлена Лагранжа в требуемых точках (x 1
, x 2
) - поиск минимума функции F(x) с помощью метода дихотомии с требуемой точностью
3. Программа модульная, содержит следующие модули:
- основной модуль, принимающий исходные данные, передающий их на обработку и выводящий конечный и промежуточный результаты - модуль поиска значений интерполяционного многочлена в точках x 1
и x 2
- модуль, задающий F(x) с параметрами LX1, LX2, найденными модулем интерполирования - модуль поиска минимума функции F(x) на отрезке [a;b] методом дихотомии
4. Получены следующие результаты:
Полином Лагранжа L(x 1
)=1.853346, L(x 2
)=1.823337
Искомый минимум функции F(x) найден с точностью E=0.0001, x min
=1.229506
5. Полученные результаты были проверены в
MathCAD
:
Полученные в ходе работы программы результаты, очень хорошо согласуются с результатами, полученными в MathCAD, требуемая точность E=0.0001 соблюдалась, если научно подойти к выбору dв методе дихотомии.
1. Гловацкая А.П., Загвоздкина А.В., Кравченко О.М., Семёнова Т.И., Шакин В.Н: Практикум Численные методы и оптимизация по дисциплине «Информатика»
2. А.П.Гловацкая: Конспект лекций «Информатика. Вычислительная математика» Москва, МТУСИ, 2006г.
3. Семёнова Т.И, Шакин В.Н.: Практикум Математический пакет MathCADв дисциплине «Информатика», Москва, МТУСИ, 2006г.
4. А.В. Загвоздкина: Конспект лекций за 1 семестр 2007-2008 учебного года

Название: Программа вычисления минимума заданной функции
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа
Добавлен 13:23:33 05 февраля 2011 Похожие работы
Просмотров: 259
Комментариев: 14
Оценило: 2 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Курсовая работа: Программа вычисления минимума заданной функции
МЕТОДЫ ПЛАНИРОВАНИЯ ПРИБЫЛИ
Мой Герой Эссе На Английском
Отчет по практике по теме Производство ароматических углеводородов на предприятии ОАО 'Башнефть-Уфанефтехим'
Как Может Начинать Сочинение Характеристика Царя Соломона
Курсовая работа по теме Оценка привлекательности стратегических зон хозяйствования предприятия ОАО 'ВЗТДиН'
Курсовая работа: Становление и развитие рыночной системы в России. Статистический анализ социально-экономического положения Российской Федерации за период с 2000 г. по 2005 г.
Курсовая работа: Организация и планирование поточной линии обработки детали для массового производства
Отчет по практике: Хозяйственная деятельность предприятия ОАО "Комбинат Южуралникель"
Курсовая Работа На Тему Нормирование Труда Служащих
Реферат: Лакокрасочные материалы. Скачать бесплатно и без регистрации
Дипломная работа по теме Автоматизированный учет ДТП
Сочинение Для Третьего Класса Золотая Осень
Менингококковая Инфекция Реферат
Реферат На Тему Эпоха Барокко
Контрольная работа по теме Расчет подъемной установки с цилиндрическим барабаном
Реферат: Понятие юридического лица
Пишем Доклад Реферат Курсовую Работу Серпикова
Что Такое Счастье Сочинение 9.3 Аргументы
Контрольная работа по теме Теорема Безу
Реферат: Teen Sex Essay Research Paper In the
Контрольная работа: Розробка плану виробництва
Отчет по практике: Биология чёрного байкальского хариуса
Реферат: Державно-правовий устрій Австро-Угорщини