Применение численных методов в информатике

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение 
высшего профессионального образования 
«УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

 
Факультет информатики и робототехники 

 

 

 

Реферат

 по дисциплине «Численные методы» 
На тему: «Применение численных методов в информатике» 

 

 

 

Выполнил: Студент 2го курса 
группы ЭБ-201з 
Шакиров Д.А. 
Проверил: Янтудин М.Н.

 

 

Уфа 2014 
Оглавление

 

 

 

Введение.

 

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

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

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

Целью моей работы является решение задачи Коши для дифференциального уравнения 1-го порядка.

 

Задачами моей работы являются:

1. Изучить численные методы  решения дифференциальных уравнений;

2. Самостоятельно вычислить  первую точку интегральной кривой заданными методами;

3. Написать программу  для построения интегральной кривой.

 

 

1. Постановка задачи.

Решить методами Эйлера и Эйлера модифицированного задачу Коши для дифференциального уравнения 1-го порядка на отрезке [X0; Xk] с шагом h и начальным условием: Y(X0) = Y0.

Ответ должен быть получен в виде таблицы результатов: 

X	Y(1)	Y(2)	YT
X0	Y0(1)	Y0(2)	Y(X0)
X1	Y1(1)	Y1(2)	Y(X1)
…	…	…	…
Xk	Yk(1)	Yk(2)	Y(Xk)

 

 

Где Y(1), Y(2) — решения, полученные различными численными методами, YT — точное решение дифференциального уравнения.

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

Данные таблицы визуализировать на форме в виде графиков.

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

Дифференциальное уравнение	X0	Xk	h	Y0	Общее решение
y’ * ctg(x) = 2-y	0	1	0.1	1	y = 2- cos(x)

 

 

 

 

2. Описание методов решения.

 

2. 1. Суть задачи.

Чтобы решить обыкновенное дифференциальное уравнение, необходимо знать значения зависимой переменной и (или) её производных при некоторых значениях независимой переменной. Если эти дополнительные условия задаются при одном значении независимой переменной, то такая задача называется задачей с начальными условиями, или задачей Коши. Часто в задаче Коши в роли независимой переменной выступает время.

Задачу Коши можно сформулировать следующим образом:

Пусть дано дифференциальное уравнение  и начальное условие y(x0) = у0. Требуется найти функцию у(x), удовлетворяющую как указанному уравнению, так и начальному условию.

Численное решение задачи Коши сводится к табулированию искомой функции.

График решения дифференциального уравнения называется интегральной кривой.

2. 2. Геометрический смысл задачи.

y’ = f(x,y) - тангенс угла наклона касательной к графику решения в точке (х, у) к оси 0Х, - угловой коэффициент (рис. 1).

 

                                        Рисунок 1. Геометрический смысл задачи Коши.

Существование решения:

Если правая часть f(x, y) непрерывна в некоторой области R, определяемой неравенствами

|x-x0| < а; |y-y0| < b,

то существует, по меньшей мере, одно решение у = у(х), определённое в окрестности |х — х0| < h, где h - положительное число.

Это решение единственно, если в R выполнено условие Липшица

|f(x,y)-f(x,y)| ≤N|y-y|(x,y),

где N - некоторая постоянная (константа Липшица), зависящая, в общем случае, от а и b. Если f(x, у) имеет ограниченную производную

f’y(x, y) в R, то можно положить N = мах |f’y(х, у)| при (х, y) принадлежащим R.

 

2. 3. Численные методы решения задачи Коши.

При использовании численных методов выполняется замена отрезка [х0, X] - области непрерывного изменения аргумента х множеством . состоящего из конечного числа точек х0 < х1 < ... < xn = Х - сеткой.

При этом xi называют узлами сетки.

Во многих методах используются равномерные сетки с шагом:

Задача Коши, определённая ранее на непрерывном отрезке [х0, X], заменяется её дискретным аналогом - системой уравнений, решая которую можно последовательно найти значения y1, y2,…,yn - приближённые значения функции в узлах сетки.

Численное решение задачи Коши широко применяется в различных областях науки и техники, и число разработанных для него методов достаточно велико. Эти методы могут быть разделены на следующие группы:

 

•      Одношаговые методы, в которых для нахождения следующей точки на

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

 Одношаговыми являются  метод Эйлера и методы Рунге - Кутта.

•      Методы прогноза и коррекции (многошаговые), в которых для отыскания следующей точки кривой у = f(x) требуется информация более чем об одной из предыдущих точек. Чтобы получить достаточно точное численное значение, часто прибегают к итерации. К числу таких методов относятся методы Милна, Адамса - Башфорта и Хемминга.

•      Явные методы, в которых функция Ф не зависит от yn+1.

•      Неявные методы, в которых функция Ф зависит от yn+1.

 

2. 4. Метод Эйлера.

Иногда этот метод называют методом Рунге-Кутта первого порядка точности.

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

Пусть дано дифференциальное уравнение первого порядка:

Y’ = f(x, y)

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

y(x0) = y0

 

Выберем шаг h и введём обозначения:

xi = х0 + ih и yi = y(xi), где i = 0, 1, 2, ...,

xi - узлы сетки,

yi - значение интегральной функции в узлах.

Проведем прямую АВ через точку (xi, yi) под углом α. При этом tg α = f(xi, yi)

В соответствий с геометрическим смыслом задачи, прямая АВ является касательной к интегральной функции. Произведем замену точки интегральной функции точкой, лежащей на касательной АВ.

Тогда yi+1 = yi + Δy

Из прямоугольного треугольника ABC 

Приравняем правые части tg α = f(xi, yi) и . Получим Отсюда Δу = h ∙ f(xi, yi).

Подставим в это выражение формулу yi+1 = yi + Δy, а затем преобразуем его. В результате получаем формулу расчета очередной точки интегральной функции:

 

Рисунок 2. Метод Эйлера.

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

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

 

 

F(x, у) - заданная функция — должна быть описана отдельно.

h = (Xk — X0)/N

Входные параметры:

i = 0, …, N - 1

Х0, XK—начальное и конечное

значения независимой переменной;

x = X0 + i ∙ h

Y0 — значение y0 из начального  условия 

y(x0) = y0;

Yi+1 = Yi + h ∙ F(x, Yi)

N - количество отрезков  разбиения;

Выходные параметры:

У - массив значений искомого решения в узлах сетки.

End

 

Рисунок 3. Блок-схема процедуры решения дифференциального уравнения методом Эйлера.

Метод Эйлера - один из простейших методов численного решения обыкновенных дифференциальных уравнений. Но существенным его недостатком является большая погрешность вычислений. На рисунке 2 погрешность вычислений для i-гo шага обозначена ε. С каждым шагом погрешность вычислений увеличивается.

 

  2.5.Метод Рунге - Кутта 4-го порядка

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

y' = f(x,y)

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

y(x0) = y0

Выберем шаг h и введём обозначения:

xi = x0 + ih и yi = y(xi), где i = 0,1, 2, ....

Аналогично описанным выше методам производится решение дифференциального уравнения. Отличие состоит в делении шага на 4 части.

Согласно методу Рунге - Кутта четвёртого порядка, последовательные значения yi искомой функции у определяются по формуле:

yi+1 = yi + Δyi

где, i = 0, 1, 2, …

Это явный четырехэтапный метод четвертого порядка точности.

Методы Рунге - Купа легко программируются и обладают значительной точностью и устойчивостью для широкого круга задач.

F(x, у)- заданная функция – должна быть описана отдельно.

Входные параметры:

ХО, ХК. - начальное и конечное

значения независимой переменной;

Y0 - значение у0 из начального условия

N—количество отрезков разбиения;

Выходные параметры:

Y - массив значений искомого  решения в узлах сетки;

Здесь приведена блок-схема алгоритма основной программы для решения задачи Коши и получения результатов с фиксированным количеством отрезков разбиения N. В основной программе происходит обращение к процедуре RUNGE(X0, ХК, Y0, N, Y), вычисляющей значения искомой функции уi в точках хi методом Рунге - Кутта.

Исходными данными в данной задаче являются:

Х0, ХК - начальное и конечное значения независимой переменной;

Y0 - значение у0 из начального условия у(х0) = у0;

N - количество отрезков разбиения.

Результаты работы программы выводятся в виде двух столбцов: X - массив значений узлов сетки; Y - массив значений искомого решения в соответствующих узлах сетки.

 

2. 6. Решение поставленной задачи методами Эйлера и Рунге-Кутта 4-ого порядка.

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

1. Строим оси координат;

2. Отмечаем A(1; 2) — первую точку интегральной кривой;

3. Ищем угол наклона  касательной к графику в точке A:

4. Строим касательную l0 в точке А под углом α0;

5. Находим х1 по формуле: xi = х0 + ih, где h — шаг интегрирования

x1 = 1 + 1 · 0,1 = 1,1;

6. Проводим прямую x = x1 = 1,1  до пересечения с прямой l0, отмечаем точку B(x1; y1);

7. Ищем y точки B:

Из прямоугольного треугольника ABC ,

Δy = y1 — y0,

Δx = x1 — x0 = h,

f(x0; y0) = (y1 — y0)/h =>

y1 = y0 + h · (f(x0; y0)) = 0 + 0,1 · f(1;0) = 0 + 0,1 · 3 = 0,3

Следовательно, точка B имеет координаты (1,1; 0,3).

 

 

Рисунок 8. Решение задачи методом Эйлера.

Метод Рунге-Кутта 4-го порядка

1. Строим оси координат;

2. Отмечаем А(1; π/2) — первую точку интегральной кривой;

3. Ищем угол наклона  касательной к графику в точке A:

tg α =y0/x0+Sin(y0/x0)

 tg α = f(x0,y0)=π /2+Sin(π/2)=2.571

 α=arctg(2.571)=1.2

 α0= α *180/ π =68.745

4. Строим касательную l0 в точке А под углом α0;

5. Находим х1 по формуле: xi = х0 + ih, где h — шаг интегрирования

x1 = 1 + 1 · 0,1 = 1,1;

6. Отмечаем середину отрезка x0x1: x0 + h/2, проводим прямую из этой точки до прямой l0, отмечаем точку B(xB; yB);

7. Ищем координаты В:

xB = x0+h/4=1+ 0.012=1.012

yB = y0+h/4*f(x0,y0)=1,571+0.012*2.571=1.603

Следовательно, точка B имеет координаты (1,012; 1,603);

8. Ищем угол наклона  касательной к графику в точке B:

tg α1 = f(x0 +h/4;y0+h/4*f(x0,y0))=1.603/1.012+Sin(1.603/1.012)=2.583

α1=arctg(2.583)=1.201

α1= α1 *180/ π =68.838

9. Строим касательную  l1 в точке B под углом α1;

10. Проводим прямую x = x1 до пересечения с прямой l1, отмечаем точку C(x1; y1);

11. Ищем y точки C:

xC= x0+h/2=1+0.025=1.025

yC=y0+h/2*f(x0 +h/4;y0+h/4*f(x0,y0))=1.636

Следовательно, точка C имеет координаты (1,025; 1,636).

12. Через полученую точку C прведем прямую под углом α2, где:

tg α2 =f(x0+h/2;y0+h/2*f(x0 +h/4,y0+h/4*f(x0,y0))=1.636/1.025+Sin(1.636/1.025)=2.595

α2=arctg(2.595)=1.203

α2= α2 *180/ π=68.928

13. На полученой прямой отложим точку D, с координатами:

xD= x0+3/4h=1.308

yC=y0+3/4h*f(x0+h/2;y0+h/2*f(x0 +h/4,y0+h/4*f(x0,y0))=1.668

Следовательно, точка D имеет координаты (1,308; 1,668).

14. Через точку D проведем прямую под углом α3, тангенс которого:

tg α3 =f(x0+3/4h;y0+3/4h*f(x0+h/2;y0+h/2*f(x0 +h/4,y0+h/4*f(x0,y0)))=1.668/1.308+

+Sin(1.668/1.308)=2.607

α3=arctg(2.607)=1.205

α3= α3 *180/ π=69.016

15. Найдем координаты точки E, лежащей на прямой проходящей под углом α3:

xB=x0+h=1+0.05=1.05

yB=y0+h*f(x0+3/4h;y0+3/4h*f(x0+h/2;y0+h/2*f(x0 +h/4,y0+h/4*f(x0,y0)))=1.701

Следовательно, точка E имеет координаты (1,05; 1,701).

Заключение

 

В своей работе я решил дифференциальное уравнение двумя методами: методом Эйлера и методом Рунге-Кутта 4-ого порядка.

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