- •Раздел 6.
- •Раздел 6. Модели и алгоритмы решения задач численными методами с использованием математических пакетов Рекомендации по использованию учебного пособия
- •Тема 6.1. Элементы теории погрешностей
- •6.1.1. Точные и приближенные числа
- •6.1.2. Абсолютная и относительная погрешность
- •Тема 6.2. Методы решения нелинейных уравнений
- •6.2.1. Постановка задачи
- •Отделение корней (локализация корней);
- •Итерационное уточнение корней.
- •6.2.2. Отделение корней
- •6.2.2.1. Графическое отделение корней
- •6.2.2.2. Аналитическое отделение корней
- •6.2.3. Уточнение корней
- •6.2.3.1. Метод половинного деления
- •6.2.3.2. Метод итерации
- •6.2.3.3. Метод Ньютона (метод касательных)
- •6.2.3.4. Метод хорд
- •6.2.3.5. Сравнение методов решения нелинейных уравнений
- •6.2.4. Технология решения нелинейных уравнений средствами MathCad
- •Тема 6.3. Интерполяция функций
- •6.3.1. Постановка задачи
- •6.3.2. Интерполяционная формула Лагранжа
- •6.3.3. Интерполяционные формулы Ньютона
- •6.3.3.1. Конечные разности
- •6.3.3.2. Первая интерполяционная формула Ньютона
- •6.3.3.3. Вторая интерполяционная формула Ньютона
- •6.3.4. Сплайн – интерполяция
- •6.3.5. Сравнение интерполяционных многочленов по применению
- •6.3.6. Технология интерполяции функций в среде математических пакетов
- •Тема 6.4. Численное интегрирование
- •6.4.1. Постановка задачи
- •6.4.2. Метод прямоугольников
- •6.4.3. Формула трапеций
- •6.4.4. Формула Симпсона
- •6.4.5. Оценка погрешности численного интегрирования
- •6.4.6. Технология вычисления интегралов в среде математических пакетов
- •Тема 6.5. Методы решения обыкновенных дифференциальных уравнений
- •6.5.1. Постановка задачи
- •6.5.2. Метод Эйлера
- •6.5.3. Методы Рунге-Кутты
- •6.5.4. Решение оду n-го порядка
- •6.5.5. Сравнение методов решения оду
- •6.5.6. Технология решения обыкновенных дифференциальных уравнений средствами математических пакетов
- •6.6.2. Метод дихотомии
- •6.6.3. Метод золотого сечения
- •6.6.4. Сравнение методов
- •6.6.5. Технология решения задач одномерной оптимизации средствами математических пакетов
- •Тема 6.7. Аппроксимация функций
- •6.7.1. Постановка задачи аппроксимации
- •6.7.2. Метод наименьших квадратов
- •6.7.3. Технология решения задач аппроксимации функций средствами математических пакетов
- •Тема 6.8. Многомерная оптимизация
- •6.8.1. Постановка задачи и основные определения
- •6.8.2. Методы спуска
- •6.8.3. Метод градиентного спуска с дроблением шага
- •6.8.4. Метод наискорейшего спуска
- •6.8.5. Проблема оврагов. Метод покоординатного спуска
- •6.8.6. Технология решения задач многомерной оптимизации средствами математических пакетов
- •Список литературы
- •Тема 6.4. Численное интегрирование................................................71
- •Тема 6.5. Методы решения обыкновенных дифференциальных Уравнений............................................................................. 92
- •Тема 6.6. Одномерная оптимизация................................................ 115
- •Тема 6.7. Аппроксимация функций....................................................132
- •Тема 6.8. Методы многомерной оптимизации............................... 149
- •Список литературы.................................................................... 204
6.5.6. Технология решения обыкновенных дифференциальных уравнений средствами математических пакетов
При решении ОДУ его следует привести к нормальной форме (к виду разрешенному относительно производной исходного ОДУ)
Для ОДУ с разделяющимися переменными исходное уравнение можно привести к виду , тогда выражение задает решение задачи Коши с начальными условиями как функцию y от переменной х.
Пример 6.5.6-1. Решить ОДУ вида .
Найдем частное решение данного ОДУ с использованием средств Mathcad, сначала методом разделения переменных, а затем с использованием функции odesolve(x, xk, n), где х – имя переменной, относительно которой решается уравнение, xk – конец интервала интегрирования, n – количество шагов, на которых вычисляется решение ОДУ. Результаты подтверждают правильность преобразований.
-
произвольная постоянная
Аналитическое решение ОДУ
Численное решение ОДУ
Аналитическое выражение для решений ОДУ удается получить достаточно редко, поэтому широкое распространение при решении ОДУ получили численные методы.
Пример 6.5.6-2. Решить ОДУ на отрезке [0;3] методами Рунге-Кутты с постоянным шагом h=0,6.
В приведенном ниже документе решение, полученное методом Эйлера, обозначено как y1, методом Рунге-Кутты 2-го порядка – y2, а 4-го порядка – y4.
-
Метод Эйлера
Метод Рунге-Кутты 2-го порядка
Метод Рунге-Кутты 4-го порядка
В Mathcad нет средств символьного решения ОДУ, но достаточно широко представлены методы численного решения задачи Коши. Для этого предназначена, например, функция rkfixed(y, x0, xend, N, D), где y – первоначально равно y0, x0 и xend – начальное и конечное значения аргумента, N – количество проводимых вычислений решения, а переменной D(x,y) должно быть присвоено выражение для вычисления правой части уравнения. Результатом вычислений функции rkfixed( ) служит матрица, в первом столбце которой содержатся координаты узлов x0 … xend, а во втором – значения приближенного решения в соответствующих узлах. В функции rkfixed( ) вместо метода Рунге-Кутты используется метод Булирша-Штера. Ниже приведены решения и их графическая иллюстрация, полученные с шагом 0.6 и 0.15.
Пример 6.5.6-3. Решить ОДУ у’= на отрезке [0;3] методами Рунге-Кутты с постоянным шагом h=0.6 и h=0.15.
Решение ОДУ 2-го порядка вида у”=F(x, y, z), где z=y’ также может быть получено методом Рунге-Кутты 4-го порядка. Ниже приведены формулы для решения ОДУ:
Система Mathcad имеет специальную встроенную функцию для решения дифференциальных уравнений. Она имеет вид: Odesolve ( x , b [ , steps ] ).
Для решения задачи Коши необходимы так называемые начальные условия и указание конца интервала. Эти данные вместе с самим уравнением записываются в блок функции Given, и лишь затем применяется сама функция odesolve( ). Функция имеет ряд особенностей. Если указано число шагов step, то решение выполняется с фиксированным шагом, иначе - адаптивным методом.
Тема 6.6. Одномерная оптимизация
6.6.1. Постановка задачи
6.6.2. Метод дихотомии
6.6.3. Метод золотого сечения
6.6.4. Сравнение методов
6.6.5. Технология решения задач одномерной оптимизации средствами
математических пакетов
6.6.1. Постановка задачи
Задача оптимизации – одна из важнейших составляющих многих инженерных задач. Найти оптимальное решение – означает найти наилучший, в смысле заданного критерия, вариант из всех возможных. При решении задачи оптимизации рассматривается некоторая функция, называемая целевой (или критериальной), и аргументы (параметры целевой функции), называемые параметрами оптимизации.
По количеству независимых переменных различают задачи одномерной оптимизации (n=1) и многомерной оптимизации (n ³ 2). При этом задача нахождения максимума целевой функции сводится к задаче нахождения минимума путем замены функции f(x) на -f(x), поэтому в дальнейшем будем говорить только о поиске минимума функции, то есть такого x*Î[a, b], при котором f(x*) = min f(x).
В области допустимых значений функция f(x) может иметь несколько экстремумов (минимумов или максимумов - рис. 6.6.1-1). Говорят, что функция f(x) имеет в точке x* локальный минимум, если существует некоторая положительная величина d, такая, что если ½х – х*½< d, то f(x)³ f(x*), т.е. существует d - окрестность точки х*, такая, что для всех значений х в этой окрестности f(x)³ f(x*). Функция f(x) имеет глобальный минимум в точке x*, если для всех х справедливо неравенство f(x)³ f(x*). Таким образом, глобальный минимум является наименьшим из локальных.
Рис. 6.6.1-1
Задачей одномерной оптимизации является нахождение точек локального минимума и соответствующих им значений функции, а в некоторых случаях требуется вычислить глобальный минимум. Однако, во всех случаях эта задача сводится к задаче нахождения локального минимума.
Интервал, на котором локализован единственный минимум, называется отрезком неопределенности.
Известно, что необходимым условием существования экстремума дифференцируемой функции f(x) является выполнение равенства f¢(х) = 0. Точка х, удовлетворяющая данному условию, называется точкой стационарности. Достаточным условием существования минимума в точке стационарности является выполнение неравенства f¢¢(х)>0, а максимума - f¢¢(х)<0.
Задача одномерной оптимизации имеет единственное решение в том случае, если функция f(x) на отрезке [a;b] имеет только один экстремум. Тогда говорят, что функция унимодальная на отрезке [a;b].
Достаточными условиями унимодальности функции на отрезке [a;b] являются:
Для дифференцируемой функции f(x) ее производная f¢(х) - неубывающая.
Для дважды дифференцируемой функции f(x) выполняется неравенство f¢¢(х)³0.
Все численные методы одномерной оптимизации применяются только для унимодальных на определенном интервале функций.
Пример 6.6.1-1. Провести исследование функции f(x) = x3 – x + e-x на предмет существования экстремумов.
Вначале проведем графическое исследование. Построим график функции f(x) (рис. 6.6.1-2). Из графика видно, что f(x) имеет две точки минимума: х1 и х2, причем точка х1 – точка глобального минимума. Исходя из графика, можно принять следующие отрезки неопределенности: для точки х1 - [-4;-3], а для точки х2 - [0;1].
Рис. 6.6.1-2
Проверим достаточное условие существования минимума на выбранных отрезках:
f¢(x) = 3x2 – 1 – e-x; f¢¢ (x) = 6x + e-x,
f¢(0) < 0, f¢(1) > 0, f¢¢ (x) > 0 для хÎ[0;1],
f¢(-4) < 0, f¢(-3) > 0, f¢¢ (x) > 0 для хÎ[-4;-3].
Условия существования минимума выполнены, поскольку f¢¢(x) > 0 для всех хÎ[0;1] и хÎ[-4;-3]. Следовательно, функция f(x) является унимодальной на выбранных отрезках.
На практике численные методы одномерной оптимизации применяют в следующих случаях:
значения функции f(x) определены в ходе эксперимента;
целевая функция очень сложна или не имеет непрерывных производных;
классические методы поиска оптимального значения не применимы.
Суть методов одномерного поиска заключается в том, что на каждой итерации интервал неопределенности уменьшается и стягивается к точке минимума. Уменьшение отрезка происходит до тех пор, пока на некоторой n-й итерации отрезок неопределенности [bn;an] не станет соизмеримым с заданной погрешностью e, то есть будет выполняться условие |bn-an| < e. Тогда за точку минимума можно принять любую точку, принадлежащую этому отрезку, в частности, его середину.
Простейшим способом сужения интервала неопределенности является деление его на некоторое число равных частей с последующим вычислением значений целевой функции в точках разбиения. Очевидно, что за минимум принимают наименьшее из этих значений – это так называемый метод сканирования. На практике чаще применяют одну из основных модификаций метода – метод прямого перебора с переменным шагом. Суть его заключается в следующем. От начальной точки интервала неопределенности двигаются с начальным шагом до тех пор, пока функция в точках разбиения уменьшается (т.е. функция убывает). Если функция в очередной точке стала возрастать, то происходит сужение интервала неопределенности путем возврата от этой рассматриваемой (которая станет правой границей нового интервала) точки на два шага назад. Полученная таким образом точка будет левой границей нового отрезка. Новый отрезок вновь исследуют таким же образом, но уже с уменьшенным в два раза шагом. Процесс повторяется до момента достижения заданной точности минимума. Это весьма трудоемкий путь. Более эффективными являются методы одномерного поиска с другими способами выбора узлов и сужения интервалов неопределенности.
Рассмотрим, в частности, метод дихотомии и метод золотого сечения.