- •Численные методы.
- •Действия над приближенными числами.
- •Относительная погрешность.
- •Число верных знаков.
- •Округление чисел.
- •Свойства погрешностей.
- •Универсальный математический пакет программ MathCad: основные сведения.
- •Примеры вычислений в среде MathCad.
- •Найти обратную матрицу
- •Построить график функции
- •Приближенное решение алгебраических и трансцендентных уравнений.
- •Программа на языке qbasic
- •Метод Ньютона (метод касательных).
- •Метод простых итераций (метод последовательных приближений).
- •То итерационный процесс
- •Предельное значение
- •Геометрическая иллюстрация метода итераций.
- •Интерполяция функций. Многочлен Лагранжа.
- •Текст программы на языке qbasic имеет вид
- •Блок-схема программы вычисления процедуры-функции lx() вычисления многочлена Лагранжа k – й степени в точке х1.
- •Интерполяционная функция Ньютона.
- •Аппроксимация функций по методу наименьших квадратов.
- •Текст программы на языке qbasic имеет вид
- •Текст программы на языке qbasic для вычисления среднего квадратического отклонения.
- •Метод Гаусса решения системы линейных уравнений.
- •Текст программы решения системы уравнений методом Гаусса на языке qbasic.
- •Приближенное вычисление определенных интегралов.
- •Формула прямоугольников.
- •Блок-схема программы вычисления интеграла по формуле прямоугольников.
- •Текст программы на языке qbasic интегрирования по формуле прямоугольников.
- •Формула трапеций.
- •Блок-схема программы вычисления интеграла по формуле Симпсона
- •Текст программы на qbasic интегрирования по формуле Симпсона.
- •Численное интегрирование дифференциальных уравнений.
- •Метод Эйлера.
- •Метод Рунге-Кутта.
- •Блок-схема программы вычисления решения дифференциального уравнения по методу Рунге-Кутта.
- •Блок-схема процедуры-функции метода Рунге-Кутта.
- •Расчетные формулы для метода Рунге- Кутта.
- •Результаты работы программы
- •Одномерная оптимизация.
- •Метод дихотомии.
- •Текст программы нахождения минимума методом градиентного спуска.
Одномерная оптимизация.
Оптимизация задачи – это процесс выбора наилучшего решения из множества возможных.
Одномерная оптимизация – это процесс нахождения экстремума функции одной переменной.
Пусть f(x) – функция, определенная на промежутке [a, b].
Функцию f(x) называют унимодальной, если на отрезке [a, b] существует единственная точка х*, в которой f(x) принимает экстремальное значение.
Для определенности будем считать, что речь идет о минимуме функции (в случае максимума, взяв функцию –f(x), сведем задачу к нахождению минимума). Функция f(x) называется целевой функцией, аргументы х называются параметрами.
Отметим, что функция f(x) не обязательно должна быть гладкой или даже непрерывной. Из определения унимодальности следует, что если х1 < x2 ≤ x*, то f(x1) > f(x2). Аналогично, если x* ≤ x1 < x2 , то f(x1) < f(x2).
Интервал x i-1 ≤ x* ≤ x i называется интервалом неопределенности. Алгоритм выбора абсцисс {x i} называется стратегией поиска.
Оптимальной стратегией поиска называется та, которая при заданном количестве вычислений, дает наименьший интервал неопределенности.
Один из путей более эффективного поиска точки x* состоит из построения вложенных отрезков [a1, b1], [a2, b2], ... [ai , b i], содержащих точку минимума. Действительно, пусть
a i < x 1 < x 2 < b i. Сравним f(x) в пробных точках.
Если f(x1) ≤ f(x2), то можно сократить отрезок поиска точки x*, перейдя к отрезку [ai, x 2] . Если f(x1) ≥ f(x2) то можно перейти к отрезку [x 1, b i].
f(x1) ≤ f(x2) f(x1) ≥ f(x2)
ai x* x*
x1 x 2 bi ai x 1 x2 bi
Решение достигается при получении заданной точности Е, т. е. при условии, что длина отрезка, на котором расположено значение х* , меньше Е, и x* равно половине длины этого интервала..
Способ получения точек х1 и х2 определяет метод оптимизации. Мы рассмотрим два метода: метод дихотомии и метод золотого сечения.
Метод дихотомии.
В этом методе пробные точки х1 и х2 располагаются близко к середине рассматриваемого отрезка [a, b].
(1)
Здесь h – малое число.
В конце вычислений в качестве приближенного значения х* берут середину последнего из найденных отрезков, убедивших предварительно, что достигнуто неравенство
Алгоритм метода дихотомии следующий.
Шаг 1. Определить х1 и х2 по формулам (1) и вычислить f(x1) и f(x2). Перейти к шагу 2.
Шаг 2. Сравнить f(x1) и f(x2). Если f(x1) ≤ f(x2), то перейти к отрезку [a, x2], положив
b = x2. Если f(x1) ≥ f(x2), то перейти к отрезку [x1, b], положив a = x1. Перейти к шагу 3.
h h
f(x1) ≤ f(x2)
a x1 O x2 b
f(x1) ≥ f(x2), a x1 h h x2 b
O
Шаг 3.Найти достигнутую точность (здесь n – номер итерации). Если Еn больше заданной точности Е, то перейти к следующей итерации, вернувшись к шагу 1.
Если En < E, то завершить поиск х*, перейдя к шагу 4.
Шаг 4. Положить xmin = (a + b)/2.
Блок-схема программы нахождения минимума методом дихотомии.
Начало
Описание
процедуры-функции
Ввод dih(x)
a, b, h, E
[a, b] – отрезок неопределенности
x1 = (a + b − h)/2 h – параметр метода
x2 = (a + b + h)/2 Е – точность оптимизации.
dih(x1) < dih(x2)
да нет Определение границ нового
b = x2 a = x1 отрезка неопределенности.
|b – a| < E
да
xmin = (a + b)/2 Точка минимума.
Вывод xmin
End
При использовании метода дихотомии надо учитывать следующее.
-
Величина h не может быть слишком малой, т. к.при при чрезмерно малом h сравнение функций в точках х1 и х2 затруднительно.
-
Величина h не может быть слишком большой, т.к. погрешность E > 2h/
П р и м е р. Методом дихотомии с точностью Е = 0. 1 найти минимум функции
f(x) = x4 + e– x
Используя пакет MathCAD,. строим график этой функции. В интервале [0, 1] функция имеет один минимум (унимодальная).
DEF FNdih (x) = x ^ 4 + EXP(-x)
a = 0
b = 1
h = .02
E = .1
m1: x1 = (a + b - h) / 2
x2 = (a + b + h) / 2
IF FNdih(x1) < FNdih(x2) THEN
b = x2
GOTO m2
END IF
a = x1
m2: IF ABS(b - a) > E THEN GOTO m1
x0 = (a + b) / 2
WRITE "xmin=", x0
END
Ответ программы xmin = 0.5306.
Для нахождения минимума используется встроенная функция Minimize
Метод золотого сечения.
Метод дихотомии, хотя и является простым в использовании методом, имеет существенный недостаток. Этот недостаток состоит в том, что на каждом шаге итерации функцию приходится вычислять дважды. Этот недостаток преодолен в методе золотого сечения.
Золотым сечением называют деление отрезка на две части так, что отношение длины всего отрезка к длине большей части равно отношению длины большей части к длине меньшей части.
х2
l – x2
A x1 С1 C B x
AB = l, AC = x2, CB = l - x 2
Взяв только положительное значение, получим
Из соотношения (1) следует, что если от точки А отложить отрезок АС1 , равный l – x2, то получим точку x1, которая дает золотое сечение отрезка АС. Таким образом. находим две пробные точки рассматриваемого отрезка. Далее, в зависимости от соотношения между значениями функции в точках С и С1, отсекаем часть отрезка АВ (АС1 или СВ). На оставшемся отрезке сохранится одна пробная точка. Вторую точке найдем по правилу «золотого сечения.
Опишем алгоритм поиска.
Шаг 1. Начальный отрезок [a,b] делим точками х1 и х2 по «правилу золотого сечения».
Вычисляем значения функции f(x1) и f(x2) и En = (b – a) / 2 . Переходим к шагу (2).
Шаг 2. Проверка окончания поиска: если Еn > E , то переходим к шагу 3, иначе к шагу 4 (Е – допустимая погрешность вычисления точки минимума).
Шаг 3, Переход к новому отрезку и новым пробным точкам.
Если f(x1) ≤ f(x2), то полагаем b = x2, x2 = x1, f(x2) = f(x1), x 1 = a + (b – a) α., вычисляем f(x1).
Если f(x1) ≥ f(x2), то полагаем a = x1, x1 = x2, f(x1) = f(x2), x2 = a + (b – a) β, вычисляем f(x2), En = (b – a)/2. Перейти к шагу 2.
Шаг 4. Окончание поиска: положить х* =.
Блок-схема программы нахождения минимума методом «золотого сечения».
Начало
Описание
процедуры-функции
Ввод gs(x)
a, b, E
[a,b] – отрезок неопределенности
α = 0.38197 Е – точность оптимизации
β = 0.61803
x1 = a + (b – a)
x2 = a + β(b – a)
f1 = gs(x1)
f2 = gs(x2)
нет да
f1< f2
a = x1, x1 = x2 b = x2, x2 = x1,
x2 = a + β (b – a) x1 = a + α (b-a)
f1 = f2 f2 = f1
f2 = gs(x2) f1 = gs(x1)
нет |b – a| < E
да
xmin =
Вывод xmin end
П р и м е р Методом «золотого сечения» найти точку минимума функции f(x) = x2 + ex.
Используя пакет MathCAD, строим график этой функции.
Из графика видно, что функция имеет минимум в интервале [-1, 0]
Программа нахождения минимума методом «золотого сечения» имеет вид.
DEF FNgs (x) = x ^ 2 + EXP(x)
a = -1
b = 0
E = .001
alfa = .38197
beta = .61803
x1 = a + alfa * (b - a)
x2 = a + beta * (b - a)
f1 = FNgs(x1)
f2 = FNgs(x2)
m2: IF f1 < f2 THEN
b = x2
x2 = x1
x1 = a + alfa * (b - a)
f2 = f1
f1 = FNgs(x1)
GOTO m1
END IF
a = x1
x1 = x2
x2 = a + beta * (b - a)
f1 = f2
f2 = FNgs(x2)
m1: IF ABS(b - a) > E GOTO m2
x0 = (a + b) / 2
WRITE "xmin=", x0
END
Ответ программы: xmin = -0.3517317.
Округляя с двумя дополнительными знаками, имеем xmin = -0.35173.
Находим минимум, используя пакет MathCAD.
Для нахождения минимума используется встроенная функция Minimize
Многомерная оптимизация.
Общая задача нелинейного программирования без ограничений состоит в нахождении минимума функции, зависящей от n переменных f(x) = f(x1, x2, ...,xn). Функция f(x) называется целевой функцией, где (x – вектор {x1, x2, ..., xn).
Как правило, численные методы отыскания экстремума состоят в построении последовательности векторов {x (k)}, удовлетворяющих условию f(x (0)) > f(x (1)) > ... > f(x (n)). Методы построения таких последовательностей называются методами спуска. В этих методах элементы последовательности {x (k)} вычисляются по формулам
x (k + 1) = x (k) – α g (k), (k = 0, 1, 2, ..., ) (1)
Здесь g (k) – направление спуска, α – длина шага в этом направлении. Как известно, градиент функции в точке направлен в сторону наискорейшего возрастания функции в этой точке. Следовательно, спускаться надо в направлении, противоположном градиенту. Вектор. противоположный градиенту, называется антиградиентом. Выбирая антиградиент в качестве направления спуска, приходим к итерационному процессу вида (1), где
g (k) =
Мы будем рассматривать метод градиентного спуска с дроблением шага.
Алгоритм метода градиентного спуска с дроблением шага следующий
y
x
Шаг 1. Задать параметр точности Е, начальный шаг α > 0, выбирать начальное значение (начальную точку) х. Общих правил для нахождения х нет. Если есть какие-либо сведения об области существования минимума рассматриваемой функции, то выбираем х из этой области. Вычислить f (х)) и перейти к шагу 2.
Шаг 2. Вычислить и проверить условие достижения точности | < E. Если это условие выполняется, то вычисления закончить, полагая xmin = x, вычислить f(x). иначе перейти к шагу 3.
Шаг 3. Найти и f(x1). Если f(x1) < f(x), то положить x = x1, f(x) = f(x1) и перейти к шагу 2, иначе к шагу 4.
Шаг 4. Положить α = α/ 2 и перейти к шагу 3.
Блок-схема программы нахождения минимума функции методом градиентного спуска.
Ввод n – размерность пространства,
n, α, E, x(). в котором задана целевая функция f(x), α – начальный шаг, Е – параметр точности вычислений, x () массив, в в котором размещены координаты начальной точки х (0) спуска .
Описание процедуры k = 0
процедуры gr(x, g,y) количество итераций
вычисления градиента g
и значения целевой s = 0
функции у.
i = 1, n
обращение к процедуре
gr(x(), g(), y)
s = s + (g(i))2 Вычисление градиента
s < E Проверка достижения точности
нет
k = k + 1
Вывод x1min, x2min
k, fmin
j = 1, n
End
x1(j) = x(j) – α g(j)
gr (x1(),g1(), y1)
y1 < y
да
нет
y =y1
α = ½ α Дробление шага
xI(i) = x1(i) i = 1, n