Решение дифференциальных уравнений на графах

Решение дифференциальных уравнений на графах

2.1 Графы и алгоритмы на графах…………………………………….…6

2.3 Метод наискорейшего спуска………………………………………10

2.4 Метод Рунге-Кутта-Мерсона………………………………………..12

3. Практическая реализация методов

3.1 Входные и выходные данные, их структура и представление в ПЭВМ… …………………………………………………………………..…19

3.2 Блок-схема алгоритма решения задачи ……………………..……..21

3.2.2 Блок-схема метода Фибоначчи …………………………….…….25

3.2.3 Блок-схема метода наискорейшего спуска ………………….….26

3.2.4 Блок-схема метода Рунге-Кутта-Мерсона ……. ………………27

3.2.5 Блок-схема метода Эйлера…………………………………. 28

3.3.1 Основная программа реализации на графах ………………. …28

3.3.2 Основная программа реализации методом Фибоначчи …….….30

3.3.3 Основная программа реализации методом дихотомии, хорд, Ньютона и простой итерации… ……………………………………..…….31

3.3.4 Основная программа реализации методом Ньютона с точностью 0.0001 ………………………………………………………………..….…. 32

4. Результаты работы программ ………………………………….………33

Введение

В данной курсовой будут рассмотрены методы оптимизации функции и алгоритмы а графах.

В достаточно общем виде математическую задачу оптимизации можно сформулировать следующим образом:

Минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.

Оптимизация как раздел математики существует достаточно давно. Оптимизация — это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином «оптимизация» в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или «оптимального» решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По этому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

Граф, в котором направление линий не выделя ется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным.

Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социаль ных и других систем. Теория графов находит своё применение в таких задачах как: транспортные маршруты, обменные схемы, управление проектами, модели коллективов и групп, модели организационных структур.

В рамках курсового проекта необходимо создать обучающую программу на языке Borland С++ реализующую решение на графах, обыкновенных дифференциальных уравнений, системы ОДУ, описывающей простейшую модель экосистемы (модель Лотка-Вольтерра), методы оптимизации. На основе работы программы сделать выводы о эффективности того или иного метода.

2.1 Графы и алгоритмы на графах

Задание 1. Составьте программу на С, выполняющую ввод графа (в виде абстрактной структуры или системы дорог, соединяющих населенные пункты). Рекомендуется хранение графа в виде списка инцидентности (допускается использование матрицы смежности или инцидентности)

Задание 2. Дополните программу функцией, выполняющей решение задачи в соответствии с вариантом (см. ниже).

Найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными (различными) вершинами и отлична от каждой из них.

2.2 Метод Фибоначчи

Для выбранной функции найдите наибольшее значение методом чисел Фибоначчи.

Каждый член которой равен сумме двух предыдущих называется числами Фибоначчи.

Числа Фибоначчи удовлетворяют многим интересным тождествам например:

F n +1 F n -1 — F n 2 =(-1) n (1)

zl n -2 ≤ F n ≤ zl n -1 (2)

F n / F n -1 ≈ zl , при n >7 , (3)

где F n –число Фибоначчи, а zl -золотое сечение ( zl =(1+5 ½ )/2).

Исходя из свойства 3 видно что числа этой довольно интересной последовательности можно применять для нахождения максимумов функций также как и в метод золотого сечения.

Алгоритм процедуры поиска максимума:

1. Находим три числа Фибоначчи F n F n -1 F n -2 n >8;
2. Производим шаги 3-4 пока | a — b |> eps
3. y=a+ F n-2 (b-a)/F n ; z= a+ F n-1 (b-a)/F n ;
4. если f(y)>f(z) то b=z иначе a=y;
5. Искомый максимум – f (( a + b )/2);

2.3 Метод наискорейшего спуска

Для выбранной функции найдите наименьшее значение методом наискорейшего спуска( варианты взять из задания 3, столбец 3 таблицы вариантов, целевая функция – сумма квадратов невязок системы уравнений).

2.4 Метод Рунге-Кутта-Мерсона

Разработайте программу для решения системы ОДУ, описывающей простейшую модель экосистемы (модель Лотка-Вольтерра). Предусмотрите вывод результатов в текстовый файл и ввод коэффициентов системы ( a , b , c , a ) и начальных условий с терминала.

Автоматическое изменение шага в ходе решения систем дифференциальных уравнений необходимо, если решение требуется получить с заданной точностью. При высокой точности (погрешность ) и решении в виде кривых с сильно различающейся крутизной автоматическое изменение шага обеспечивает уменьшение общего числа шагов в несколько раз, резко уменьшается вероятность числовой неустойчивости, даёт более равномерное расположение точек графика кривых (решений) при их выводе на печать. Данный метод обеспечивает приближённую оценку погрешностей на каждом шаге интегрирования. Погрешность интегрирования имеет порядок h 5 . Этот метод реализуется следующим алгоритмом: Задаём число уравнений N , погрешность ε = E , начальный шаг интегрирования h = H и начальное значение y 10 ,…, y N 0 . С помощью пяти циклов с управляющей переменной J =1,2. N вычисляем коэффициенты:

Находим (в последнем цикле) значение (12)

Проверяем выполнения условий

Если условие (14) не выполняется, то делим шаг h на 2 и повторяем вычисления. Если это условие выполняется и выполняется условие (15), значение x i +1 = x i + h и Y j ( i +1) , то считаем, что решение системы дифференциальных уравнений найдено с заданной точностью. Если условие (15) не выполняется , шаг h увеличивается вдвое и вычисления повторяются.

2.5 Метод Эйлера

Для выбранной функции найдите наибольшее значение взятием производной и решением возникающего уравнения f ‘( x )=0.

Методы Эйлера численного решения дифференциальных уравнений первого и второго порядков.

Метод численного решения дифференциального уравнения первого порядка

с начальным условием основан на разложении решения в ряд Тейлора в -окрестности точки :

При отбрасывании всех членов ряда, содержащих производные второго и высших порядков получим: , где -правая часть уравнения (1).

Пользуясь значением из разложения в — окрестности точки получим

Аналогично продолжая для следующей точки , получим

Если дано уравнение второго порядка

с начальными условиями и , то как такое уравне- ние можно свести к системе двух уравнений первого порядка

Тогда приближенные значения функций и в точке можно высислить по формулам

где — правая часть уравнения (4).

При достаточно малой величине шага метод Эйлера дает решение с большой точностью, т.к. погрешность решения близка к

1. Результаты работы программ

График функции для поиска точек её экстремумов

Дифференцирование мотодом Эйлера

Метод наискорейшего спуска

3.Практическая реализация методов .

3.1 Входные и выходные данные, их структура и представление в ПЭВМ.

Коэффициенты в уравнениях вводятся с клавиатуры. В программе также есть ограничение на ввод коэффициентов в зависимости от типа уравнения. В качестве входных параметров мы используем начальное приближение, а также вводим начальное и конечное значение нашей производной, шаг и точность вычисления. В качестве выходных параметров выступают значение неизвестной переменной, а также .

Решение системы дифференциальных уравнений на графах Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — Ракчеева Евгения Михайловна

В работе излагается численный метод решения системы дифференциальных уравнений, которая описывает неустановившееся течение воды в канале или речном русле. Модель записывается на основе уравнений Сен-Венана. Для нее ставится начально-краевая задача.

Похожие темы научных работ по математике , автор научной работы — Ракчеева Евгения Михайловна

The decision of system of the differential equations on columns

This paper is devoted to consider of the numerical method of the decision of system of the differential equations. This system describes the unsteady current of water in the channel or a river channel. The model enters the name on the basis of equations Saint-Venant.

Текст научной работы на тему «Решение системы дифференциальных уравнений на графах»

Решение системы дифференциальных уравнений на графах

Решение системы дифференциальных уравнений на графах

В работе излагается численный метод решения системы дифференциальных уравнений, которая описывает неустановившееся течение воды в канале или речном русле.

Решение рассматривается на совокупности отрезков, образующих одномерный клеточный комплекс или граф.

Задача работы состоит в том, чтобы определить расход воды — £?| >•••> “рас-

ход воды С^(1,х) и отметка свободной поверхности воды

Найдем данное решение в следующий момент времени I ,+|= / *+ т, которое строится с помощью разностных уравнений:

Соотношения (5), (6) нелинейны и в общем случае должны решаться с помощью итераций. Если течение гладкое и волны невелики по амплитуде, то можно ограничиться одной итерацией. Это означает, что уравнения (5), (6) линеаризуются. Линеаризацию можно провести следующим образом, обозначив через ((-0)1*’ главную линейную часть функции С**1 относительно (г‘,(?*):

Таким образом, уравнения (5), (6) заменяются на линейные уравнения вида:

Численное решение математических моделей объектов заданных системами дифференциальных уравнений

Введение:

При математическом моделировании ряда технических устройств используются системы дифференциальных нелинейных уравнений. Такие модели используются не только в технике, они находят применение в экономике, химии, биологии, медицине, управлении.

Исследование функционирования таких устройств требуют решения указанных систем уравнений. Поскольку основная часть таких уравнений являются нелинейными и нестационарными, часто невозможно получить их аналитическое решение.

Возникает необходимость использовать численные методы, наиболее известным из которых является метод Рунге — Кутты [1]. Что касается Python, то в публикациях по численным методам, например [2,3], данных по применение Рунге — Кутты крайне мало, а по его модификации — методу Рунге-Кутта-Фельберга вообще нет.

В настоящее время, благодаря простому интерфейсу, наибольшее распространение в Python имеет функцию odeint из модуля scipy.integrate. Вторая функция ode из этого модуля реализует несколько методов, в том числе и упомянутый пятиранговый метод Рунге-Кутта-Фельберга, но, вследствие универсальности, имеет ограниченное быстродействие.

Целью настоящей публикации является сравнительный анализ перечисленных средств численного решения систем дифференциальных уравнений с модифицированным автором под Python методом Рунге-Кутта-Фельберга. В публикации так же приведены решения по краевым задачам для систем дифференциальных уравнений (СДУ).

Краткие теоретические и фактические данные по рассматриваемым методам и программным средствам для численного решения СДУ

Для одного дифференциального уравнения n – го порядка, задача Коши состоит в нахождении функции, удовлетворяющей равенству:

и начальным условиям

Перед решением эта задача должна быть переписана в виде следующей СДУ

(1)

с начальными условиями

Модуль имеет две функции ode() и odeint(), предназначенные для решения систем обыкновенных дифференциальных уравнений (ОДУ) первого порядка с начальными условиями в одной точке (задача Коши). Функция ode() более универсальная, а функция odeint() (ODE integrator) имеет более простой интерфейс и хорошо решает большинство задач.

Функция odeint() имеет три обязательных аргумента и много опций. Она имеет следующий формат odeint(func, y0, t[,args=(), . ]) Аргумент func – это имя Python функции двух переменных, первой из которых является список y=[y1,y2. yn], а второй – имя независимой переменной.

Функция func должна возвращать список из n значений функций при заданном значении независимого аргумента t. Фактически функция func(y,t) реализует вычисление правых частей системы (1).

Второй аргумент y0 функции odeint() является массивом (или списком) начальных значений при t=t0.

Третий аргумент является массивом моментов времени, в которые вы хотите получить решение задачи. При этом первый элемент этого массива рассматривается как t0.

Функция odeint() возвращает массив размера len(t) x len(y0). Функция odeint() имеет много опций, управляющих ее работой. Опции rtol (относительная погрешность) и atol (абсолютная погрешность) определяют погрешность вычислений ei для каждого значения yi по формуле

Они могут быть векторами или скалярами. По умолчанию

Вторая функция модуля scipy.integrate, которая предназначена для решения дифференциальных уравнений и систем, называется ode(). Она создает объект ОДУ (тип scipy.integrate._ode.ode). Имея ссылку на такой объект, для решения дифференциальных уравнений следует использовать его методы. Аналогично функции odeint(), функция ode(func) предполагает приведение задачи к системе дифференциальных уравнений вида (1) и использовании ее функции правых частей.

Отличие только в том, что функция правых частей func(t,y) первым аргументом принимает независимую переменную, а вторым – список значений искомых функций. Например, следующая последовательность инструкций создает объект ODE, представляющий задачу Коши.

При построении численных алгоритмов будем считать, что решение этой дифференциальной задачи существует, оно единственно и обладает необходимыми свойствами гладкости.

При численном решении задачи Коши

(2)

(3)

по известному решению в точке t =0 необходимо найти из уравнения (3) решение при других t. При численном решении задачи (2),(3) будем использовать равномерную, для простоты, сетку по переменной t с шагом т > 0.

Приближенное решение задачи (2), (3) в точке обозначим . Метод сходится в точке если при . Метод имеет р-й порядок точности, если , р > 0 при . Простейшая разностная схема для приближенного решения задачи (2),(3) есть

(4)

При имеем явный метод и в этом случае разностная схема аппроксимирует уравнение (2) с первым порядком. Симметричная схема в (4) имеет второй порядок аппроксимации. Эта схема относится к классу неявных — для определения приближенного решения на новом слое необходимо решать нелинейную задачу.

Явные схемы второго и более высокого порядка аппроксимации удобно строить, ориентируясь на метод предиктор-корректор. На этапе предиктора (предсказания) используется явная схема

(5)

а на этапе корректора (уточнения) — схема

В одношаговых методах Рунге—Кутта идеи предиктора-корректора реализуются наиболее полно. Этот метод записывается в общем виде:

(6),

Формула (6) основана на s вычислениях функции f и называется s-стадийной. Если при имеем явный метод Рунге—Кутта. Если при j>1 и то определяется неявно из уравнения:

(7)

О таком методе Рунге—Кутта говорят как о диагонально-неявном. Параметры определяют вариант метода Рунге—Кутта. Используется следующее представление метода (таблица Бутчера)

Одним из наиболее распространенных является явный метод Рунге—Кутта четвертого порядка

(8)

Метод Рунге—Кутта— Фельберга

Привожу значение расчётных коэффициентов метода

(9)

С учётом(9) общее решение имеет вид:

(10)

Это решение обеспечивает пятый порядок точности, остаётся его адаптировать к Python.

Вычислительный эксперимент по определению абсолютной погрешности численного решения нелинейного дифференциального уравнения с использованием обеих функций def odein(),def oden() модуля scipy.integrate и адаптированного к Python методов Рунге—Кутта и Рунге—Кутта— Фельберга

Адаптированные к Python методы Рунге—Кутта и Рунге—Кутта— Фельберга имеют меньшую абсолютную, чем решение с применением функции odeint, но большую, чем с использованием функции edu. Необходимо провести исследование быстродействия.

Численный эксперимент по сравнению быстродействия численного решения СДУ при использовании функции ode с атрибутом dopri5 (метод Рунге – Кутты 5 порядка) и с использованием адаптированного к Python метода Рунге—Кутта— Фельберга

Сравнительный анализ проведём на примере модельной задачи, приведенной в [2]. Чтобы не повторять источник, приведу постановку и решение модельной задачи из [2].

Решим задачу Коши, описывающую движение тела, брошенного с начальной скоростью v0 под углом α к горизонту в предположении, что сопротивление воздуха пропорционально квадрату скорости. В векторной форме уравнение движения имеет вид

где – радиус вектор движущегося тела, – вектор скорости тела, – коэффициент сопротивления, вектор силы веса тела массы m, g – ускорение свободного падения.

Особенность этой задачи состоит в том, что движение заканчивается в заранее неизвестный момент времени, когда тело падает на землю. Если обозначить , то в координатной форме мы имеем систему уравнений:

К системе следует добавить начальные условия: (h начальная высота), . Положим . Тогда соответствующая система ОДУ 1 – го порядка примет вид:

Для модельной задачи положим . Опуская довольно обширное описание программы, приведу только листинг из комментариев к которому, думаю, будет ясен принцип её работы. В программу добавлен отсчёт времени работы для сравнительного анализа.

Flight time = 1.2316 Distance = 5.9829 Height =1.8542
Flight time = 1.1016 Distance = 4.3830 Height =1.5088
Flight time = 1.0197 Distance = 3.5265 Height =1.2912
Flight time = 0.9068 Distance = 2.5842 Height =1.0240
Время на модельную задачу: 0.454787

Для реализации средствами Python численного решения СДУ без использования специальных модулей, мною была предложена и исследована следующая функция:

def increment(f, t, y, tau
k1=tau*f(t,y)
k2=tau*f(t+(1/4)*tau,y+(1/4)*k1)
k3 =tau *f(t+(3/8)*tau,y+(3/32)*k1+(9/32)*k2)
k4=tau*f(t+(12/13)*tau,y+(1932/2197)*k1-(7200/2197)*k2+(7296/2197)*k3)
k5=tau*f(t+tau,y+(439/216)*k1-8*k2+(3680/513)*k3 -(845/4104)*k4)
k6=tau*f(t+(1/2)*tau,y-(8/27)*k1+2*k2-(3544/2565)*k3 +(1859/4104)*k4-(11/40)*k5)
return (16/135)*k1+(6656/12825)*k3+(28561/56430)*k4-(9/50)*k5+(2/55)*k6

Функция increment(f, t, y, tau) обеспечивает пятый порядок численного метода решения. Остальные особенности программы можно посмотреть в следующем листинге:

Время на модельную задачу: 0.259927

Предложенная программная реализация модельной задачи без использования специальных модулей имеет почти в двое большее быстродействие, чем с функцией ode, однако нельзя забывать, что ode имеет более высокую точность численного решения и возможности выбора метода решения.

Решение краевой задачи с поточно разделёнными краевыми условиями

Приведем пример некоторой конкретной краевой задачи с поточно разделенными краевыми условиями:

(11)

Для решения задачи (11) используем следующий алгоритм:

1. Решаем первые три неоднородные уравнения системы (11) с начальными условиями

Введем обозначение для решения задачи Коши:

2. Решаем первые три однородные уравнения системы (11) с начальными условиями

Введем обозначение для решения задачи Коши:

3. Решаем первые три однородные уравнения системы (11) с начальными условиями

Введем обозначение для решения задачи Коши:

4. Общее решение краевой задачи (11) при помощи решений задач Коши записывается в виде линейной комбинации решений:

где p2, p3 — некоторые неизвестные параметры.

5. Для определения параметров p2, p3, используем краевые условия последних двух уравнений (11), то есть условия при x = b. Подставляя, получим систему линейных уравнений относительно неизвестных p2, p3:
(12)
Решая (12), получим соотношения для p2, p3.

По приведенному алгоритму с применением метода Рунге—Кутта—Фельберга получим следующую программу:

y0[0]= 0.0
y1[0]= 1.0
y2[0]= 0.7156448588231397
y3[0]= 1.324566562303714
y0[N-1]= 0.9900000000000007
y1[N-1]= 0.1747719838716767
y2[N-1]= 0.8
y3[N-1]= 0.5000000000000001
Время на модельную задачу: 0.070878

Вывод

Разработанная мною программа отличается от приведенной в [3] меньшей погрешностью, что подтверждает приведенный в начале статьи сравнительный анализ функции odeint с реализованным на Python метода Рунге—Кутта—Фельберга.

3. Н.М. Полякова, Е.В. Ширяева Python 3. Создание графического интерфейса пользователя (на примере решения методом пристрелки краевой задачи для линейных обыкновенных дифференциальных уравнений). Ростов-на-Дону 2017.