- •Введение
- •Основы алгоритмизации
- •Алгоритм, его свойства
- •Базовые алгоритмические структуры
- •Алгоритмы численных методов
- •Алгоритмы методов решения нелинейных уравнений
- •Метод половинного деления
- •Метод итераций
- •Метод Ньютона
- •Метод хорд
- •Алгоритмы методов интерполяции функции
- •Метод Лагранжа
- •Первая интерполяционная формула Ньютона
- •Вторая интерполяционная формула Ньютона
- •Алгоритм аппроксимации функции методом наименьших квадратов
- •Алгоритмы методов численного интегрирования
- •Метод средних прямоугольников
- •Метод трапеций
- •Метод Симпсона
- •Алгоритмы методов решения обыкновенных дифференциальных уравнений
- •Алгоритмы методов одномерной оптимизации
- •Метод дихотомии
- •Метод золотого сечения
- •Метод средней точки
- •Алгоритмы методов многомерной оптимизации
- •Создание схем алгоритмов с использованием графического редактора ms Visio
- •Назначение ms Visio
- •Создание документа, открытие и сохранение файлов
- •Создание простых схем
- •3.4.Настройка внешнего вида блоков схемы алгоритма
- •3.5. Работа с текстом
- •Список литературы
Метод трапеций
Алгоритм метода трапеций, представленный на рис. 2.4-2, должен быть дополнен процедурой-функцией f(x), в которой вычисляется значение подынтегральной функции.
Рис. 2.4-2. Алгоритм метода трапеций
Алгоритм метода основан на замене подынтегральной функции f(x) в пределах элементарного отрезка [xi;xi+1] интерполяционным многочленом первой степени[3]. Вычисление интеграла проводится с использованием формулы:
Оценка погрешности проводится с использованием метода двойного просчета, где формуле Рунге k=2.
Метод Симпсона
Схема алгоритма метода Симпсона, представленная на рис. 2.4-3, должна быть дополнена процедурой-функцией f(x), в которой вычисляется значение подынтегральной функции.
Рис. 2.4-3. Алгоритм метода Симпсона
Алгоритм метода Симпсона основан на замене подынтегральной функции f(x) в пределах двух элементарных отрезков [xi;xi+2] интерполяционным многочленом второй степени[3]. Количество отрезков должно быть четным (n=2m). Вычисление интеграла проводится с использованием формулы:
Оценка погрешности проводится с использованием метода двойного просчета, где формуле Рунге k=4.
Алгоритмы методов решения обыкновенных дифференциальных уравнений
Схема алгоритма решения обыкновенных дифференциальных уравнений (ОДУ) методами Рунге-Куттыс заданной точностью представлена на рис. 2.5-1.
Рис.2.5-1. Алгоритм решения ОДУ методами Рунге-Кутты
В зависимости от порядка метода схема алгоритма дополняется соответствующей процедурой, в которой производится вычисление функции y(xi), по формулам соответствующим порядку метода Рунге-Кутты (рис.2.5-2).
Рис.2.5-2. Решение ОДУ методами Рунге-Кутты с постоянным шагом
Заданная погрешность обеспечивается дополнением алгоритмов решения методом двойного просчета, в котором оценка погрешности производится по формуле Рунге:
где p – порядок метода Рунге-Кутты.
Если условие выполняется, то шаг для следующей точки выбирается равным величине h, иначе шаг уменьшается вдвое и продолжается уточнение yiв точке хi.
Алгоритмы методов одномерной оптимизации
Метод дихотомии
Схема алгоритм метода дихотомии, представленная на рис. 2.6-1, требует дополнения процедуры-функции f(x), в которой вычисляется значение целевой функции.
Рис.2.6-1. Алгоритм метода дихотомии
В методе дихотомии используется функция f(x), унимодальная на отрезке [a;b][3].На отрезке [a0;b0], где a0=a, аb0 = b, выбираются две точки симметричные относительно середины отрезка:
где d - параметр метода, величина которого (0<d<e/2.).
Вычислим и сравним значения функций f(a1) и f(b1). В силу унимодальности функции можно провести сокращение отрезка неопределенности по следующему правилу:
Еслиf(a1) £f(b1), то x*Î[a0;b1] ;
Если f(a1) >f(b1), то x*Î[a1;b0].
Сокращение отрезка проводятся до тех пор, пока не выполнится неравенствоΔn=|bn-an|≤ε.
Метод золотого сечения
Схема алгоритма метода золотого сечения, представленная на рис. 2.6-2, требует дополнения процедуры-функции f(x), в которой вычисляется значение целевой функции.
Рис.2.6-2. Алгоритм метода золотого сечения
В методе дихотомии используется функция f(x), унимодальная на отрезке [a;b] [3].В основу метода положено разбиение отрезка неопределенности [a;b] в соотношении золотого сечения:
или ,
где k1=0.382, а k2=0.618.
Сравнение значений функции в точках х1 и х2 позволяет, в силу унимодальности функции f(x), отбросить ту часть отрезка, где заведомо нет точки минимума. Известно, что и точка х1и точка х2дваждыосуществляет золотое сечение на отрезке[a;b]. Это приводит к тому, что значение целевой функции на каждой итерации (кроме первой) вычисляется один раз.
После каждой итерации длина отрезка неопределенности сокращается в 1.618 раза. Сокращение отрезка проводятся до тех пор, пока не выполнится неравенствоΔn=|bn-an|≤ε.