Автор работы: Пользователь скрыл имя, 29 Октября 2012 в 11:35, курсовая работа
Под одномерной минимизацией понимается раздел численных методов, связанных с вычислением (или оценкой) минимума одномерной функции действительной переменной, заданной, как правило, на некотором ограниченном отрезке найти min f(x)=f(x*), (1.1)
axb
где x*-искомая точка минимума на [a, b].
1. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ 3
1.1. НЕОБХОДИМЫЕ СВЕДЕНИЯ ИЗ МАТЕМАТИКИ 3
1.1.1. Постановка задачи одномерной минимизации 3
1.1.2. Классификация одномерных функций 4
1.1.3. Ряд Тейлора 6
1.1.5. Замечания относительно глобального минимума 12
1.2. МЕТОДЫ ИСКЛЮЧЕНИЯ ИНТЕРВАЛОВ 13
1.2.1. Метод деления пополам 13
Алгоритм Свенна для поиска интервала унимодальности 13
Алгоритм деления пополам 14
1.2.2. Метод золотого сечения 15
1.2.3. Сравнение методов исключения интервалов 17
1.3. ПОЛИНОМИАЛЬНАЯ АППРОКСИМАЦИЯ 18
1.3.1. Квадратичная аппроксимация 18
Алгоритм последовательной квадратичной аппроксимации 22
1.3.2. Кубическая аппроксимация 25
1.4. МЕТОДЫ С ИСПОЛЬЗОВАНИЕМ ПРОИЗВОДНЫХ 28
1.4.1. Метод Ньютона-Рафсона 28
1.4.2. Методы средней точки и секущих 30
1.4.3. Численная аппроксимация производных 31
Расчет коэффициентов аппроксимации в Microsoft Excel. 35
Построение графиков в Excel и использование функции ЛИНЕЙН. 44
Программа на языке Pascal. 47
Схема алгоритма. 47
Результаты расчета Pascal. 53
Заключение. 54
Список литературы 55
, (1.29)
где Dx=h здесь принято называть конечно-разностным интервалом.
Когда модуль |h| «достаточно» малая величина, то и ошибка аппроксимации (1.29) будет также малой. Формула (1.29) называется правой конечно-разностной аппроксимацией производной f’(x).
Аналогично для точки x-h имеем формулу левой конечно-разностной аппроксимации:
f’(x)» . (1.30)
Если в формулах (1.29)-(1.30) выполнить еще по одному шагу тейлоровского разложения, результатами будут равенства вида
f(x+h)»f(x)+hf’(x),
f(x-h)»f(x)-hf’(x).
Вычтем первое из второго и поделим полученную разность на h; это приведет к равенству
» f’(x), (1.31)
называемому центральной конечно-разностной аппроксимацией для первой производной.
Заметим, что в (1.31) для расчета оценки производной требуются значения функции в двух точках, а не в одной, как для правой и левой аппроксимации. Такое привлечение дополнительной информации повышает точность оценки производной, и это-общее правило для численных методов оптимизации.
Чтобы проиллюстрировать применение конечно-разностных формул, рассмотрим функцию
f(x)=x3, которая имеет производную f’(x)=3x2.
Правая аппроксимация дает в данном случае оценку f’(x), равную:
,
так что ошибкой отбрасывания будет 3xh+h2. Если же воспользоваться центральной аппроксимацией, то в качестве оценки величины 3x2 получим
,
и здесь ошибка есть просто h2.
Тейлоровское разложение функции f(x) позволяет строить формулы аппроксимации конечными разностями ее производных не только первого, но и более высоких порядков. Для этого запишем разложения до производных второго порядка включительно справа и слева от точки разложения x соответственно:
f(x+h)»f(x)+hf’(x)+
f(x-h)»f(x)-hf’(x)+
. (1.32)
Разложение Тейлора позволяет также строить формулы конечно-разностной аппроксимации производных и высших порядков.
Функция y=f(x) задана таблицей 1
Таблица 1
Исходные данные.
|
12.85 |
154.77 |
9.65 |
81.43 |
7.74 |
55.86 |
5.02 |
24.98 |
1.86 |
3.91 |
12.32 |
145.59 |
9.63 |
80.97 |
7.32 |
47.63 |
4.65 |
22.87 |
1.76 |
3.22 |
11.43 |
108.37 |
9.22 |
79.04 |
7.08 |
48.03 |
4.53 |
20.32 |
1.11 |
1.22 |
10.59 |
100.76 |
8.44 |
61.76 |
6.87 |
36.85 |
3.24 |
9.06 |
0.99 |
1.10 |
10.21 |
98.32 |
8.07 |
60.54 |
5.23 |
25.65 |
2.55 |
6.23 |
0.72 |
0.53 |
Требуется выяснить - какая из функций - линейная, квадратичная или экспоненциальная наилучшим образом аппроксимирует функцию заданную таблицей 1.
Решение.
Поскольку в данном примере каждая пара значений встречается один раз, то между и существует функциональная зависимость.
Для проведения расчетов данные целесообразно расположить в виде таблицы 2, используя средства табличного процессора Microsoft Excel.
Таблица 2
Расчет сумм.
Поясним как таблица 2 составляется.
Шаг 1. В ячейки A2:A26 заносим значения .
Шаг 2. В ячейки B2:B26 заносим значения .
Шаг 3. В ячейку C2 вводим формулу =A2^2.
Шаг 4. В ячейки C3:C26 эта формула копируется.
Шаг 5. В ячейку D2 вводим формулу =A2*B2.
Шаг 6. В ячейки D3:D26 эта формула копируется.
Шаг 7. В ячейку F2 вводим формулу =A2^4.
Шаг 8. В ячейки F3:F26 эта формула копируется.
Шаг 9. В ячейку G2 вводим формулу =A2^2*B2.
Шаг 10. В ячейки G3:G26 эта формула копируется.
Шаг 11. В ячейку H2 вводим формулу =LN(B2).
Шаг 12. В ячейки H3:H26 эта формула копируется.
Шаг 13. В ячейку I2 вводим формулу =A2*LN(B2).
Шаг 14. В ячейки I3:I26 эта формула копируется.
Последующие шаги делаем с помощью автосуммирования .
Шаг 15. В ячейку A27 вводим формулу =СУММ(A2:A26).
Шаг 16. В ячейку B27 вводим формулу =СУММ(B2:B26).
Шаг 17. В ячейку C27 вводим формулу =СУММ(C2:C26).
Шаг 18. В ячейку D27 вводим формулу =СУММ(D2:D26).
Шаг 19. В ячейку E27 вводим формулу =СУММ(E2:E26).
Шаг 20. В ячейку F27 вводим формулу =СУММ(F2:F26).
Шаг 21. В ячейку G27 вводим формулу =СУММ(G2:G26).
Шаг 22. В ячейку H27 вводим формулу =СУММ(H2:H26).
Шаг 23. В ячейку I27 вводим формулу =СУММ(I2:I26).
Аппроксимируем функцию линейной функцией . Для определения коэффициентов и воспользуемся системой
Используя итоговые суммы таблицы 2, расположенные в ячейках A27, B27, C27 и D27, запишем систему в виде
решив которую, получим и .
Таким образом, линейная аппроксимация имеет вид .
Решение системы проводили, пользуясь средствами Microsoft Excel. Результаты представлены в таблице 3.
Таблица 3
Результаты коэффициентов линейной аппроксимации.
В таблице 3 в ячейках A37:B38 записана формула {=МОБР(A33:B34)}.
В ячейках D37:D38 записана формула {=МУМНОЖ(A37:B38;C33:C34)}.
Далее аппроксимируем функцию квадратичной функцией . Для определения коэффициентов , и воспользуемся системой
Используя итоговые суммы таблицы 2,
расположенные в ячейках A27, B27, C27, D27, E27, F27 и G27 запишем систему в виде
решив которую, получим , и .
Таким образом, квадратичная аппроксимация имеет вид
Решение системы проводили, пользуясь средствами Microsoft Excel. Результаты представлены в таблице 4.
Таблица 4
Результаты коэффициентов квадратичной аппроксимации.
В таблице 4 в ячейках E38:G40 записана формула {=МОБР(E33:G35)}.
В ячейках I38:I40 записана формула {=МУМНОЖ(E38:G40;H33:H35)}.
Теперь аппроксимируем функцию экспоненциальной функцией . Для определения коэффициентов и прологарифмируем значения и используя итоговые суммы таблицы 2, расположенные в ячейках A27, C27, H27 и I27 получим систему
где .
Решив систему, найдем , .
После потенцирования получим .
Таким образом, экспоненциальная аппроксимация имеет вид
.
Решение системы проводили, пользуясь средствами Microsoft Excel. Результаты представлены в таблице 5.
Таблица 5
Результаты коэффициентов экспоненциальной аппроксимации.
В таблице 5 в ячейках D45:E46 записана формула {=МОБР(D42:943)}.
В ячейках G45:G46 записана формула {=МУМНОЖ(D45:E46;F42:F43)}.
В ячейке G47 записана формула =EXP(G45).
Вычислим среднее арифметическое и по формулам:
Результаты расчета и средствами Microsoft Excel представлены в таблице 6.
Таблица 6
Вычисление средних значений X и Y.
В ячейке F49 записана формула =A26/25.
В ячейке F50 записана формула =B26/25.
Для того, чтобы
рассчитать коэффициент корреляции
и коэффициент детерминированно
Таблица 7
Вычисление остаточных сумм.
Поясним как таблица 7 составляется.
Ячейки A2:A27 и B2:B27 уже заполнены (см. табл. 2).
Далее делаем следующие шаги.
Шаг 1. В ячейку J2 вводим формулу =(A2-$F$49)*(B2-$F$50).
Шаг 2. В ячейки J3:J26 эта формула копируется.
Шаг 3. В ячейку K2 вводим формулу =(A2-$F$49)^2.
Шаг 4. В ячейки K3:K26 эта формула копируется.
Шаг 5. В ячейку L2 вводим формулу =(B2-$F$50)^2.
Шаг 6. В ячейки L3:L26 эта формула копируется.
Шаг 7. В ячейку M2 вводим формулу =($D$37+$D$38*A2-B2)^2.
Шаг 8. В ячейки M3:M26 эта формула копируется.
Шаг 9. В ячейку N2 вводим формулу
=($I$38+$I$39*A2+$I$40*A2^2-
Шаг 10. В ячейки N3:N26 эта формула копируется.
Шаг 11. В ячейку O2 вводим формулу
=($G$47*EXP($G$46*A2)-B2)^2.
Шаг 12. В ячейки O3:O26 эта формула копируется.
Последующие шаги делаем с помощью автосуммирования .
Шаг 13. В ячейку J27 вводим формулу =СУММ(J2:J26).
Шаг 14. В ячейку K27 вводим формулу =СУММ(K2:K26).
Шаг 15. В ячейку L27 вводим формулу =СУММ(L2:L26).
Шаг 16. В ячейку M27 вводим формулу =СУММ(M2:M26).
Шаг 17. В ячейку N27 вводим формулу =СУММ(N2:N26).
Шаг 18. В ячейку O27 вводим формулу =СУММ(O2:O26).
Теперь проведем расчеты коэффициента корреляции по формуле
(только для линейной
и коэффициента детерминированности по формуле . Результаты расчетов средствами Microsoft Excel представлены в таблице 8.
Таблица 8
Результаты расчета.
В таблице 8 в ячейке D53 записана формула =J27/(K27*L27)^(1/2).
В ячейке D54 записана формула =1- M27/L27.
В ячейке D55 записана формула =1- N27/L27.
В ячейке D56 записана формула =1- O27/L27.
Анализ результатов расчетов показывает, что квадратичная аппроксимация наилучшим образом описывает экспериментальные данные.
Рассмотрим результаты эксперимента, приведенные в исследованном выше примере.
Исследуем характер зависимости в три этапа:
Рис.4.1.
График зависимости y от x
Рис.4.2. График линейной аппроксимации
Рис.4.3. График квадратичной аппроксимации.
Рис.4.4. График экспоненциальной аппроксимации.
Примечание: Полученное при построении линии тренда значение коэффициента детерминированности для экспоненциальной зависимости не совпадает с истинным значением , поскольку при вычислении коэффициента детерминированности используются не истинные значения , а преобразованные значения с дальнейшей линеаризацией.
Таблица 9