Вычислительные методы
Федеральное агентство по образованию
ГОУ ВПО Уральский федеральный
университет имени первого
Кафедра Вычислительной Техники.
Курсовая работа
По дисциплине «Информатика»
Студент Якушев М.А.
гр. Фт-190102
Преподаватель Исупова Н.В.
Екатеринбург
2010 год.
Введение
Данная курсовая работа направлена на изучение вычислительных методов, которые широко используются для решения сложных математических задач, таких как:
- Вычисление значения заданной функции
- Вычисление корня уравнения
- Решение обыкновенных дифференциальных уравнений
- Решение систем линейных уравнений
В данной курсовой работе будут содержаться следующие математические модели:
- Метод дихотомии
- Метод Ньютона
- Метод «золотого» сечения
- Метод равномерного перебора
- Метод Гаусса
- Метод трапеций
- Задачи Коши
- Метод Эйлера
- Метод Рунге-Кутта
С их помощью будут составлены программы в MathCAD и Pascal
1. Задача 1(Вычисление значения заданной функции)
1.1 Постановка задачи
Вычислить значение заданной функции. Осуществить вывод значений вводимых исходных данных и результат вычисления значения функции, сопровождая вывод наименованиями переменных.
1.2 Исходные данные
f(x)=
Δx=0, [0,5;7];
1.3 Решение задачи в пакете MathCad 14.0
a=2.6
b=-0.39
x=0, 0.5..7
1.4 Блок-схема
1.5 Текст программы (написан в пакете Turbo Pascal 7.0)
program sys;
uses crt;
var x,y,j : real;
const
a=2.6;
b=-0.39;
begin
clrscr;
write('vvedite shag:');
read(j);
Write('vvedite na4alnoe zna4enie x=');
read(x);
writeln('x y');
while x<=7 do begin
if x<2.8 then begin
y:=(a+b)/(exp(x)+cos(x));
writeln(x:4:2, ' ' ,y:4:2);
x:=x+j;
end;
if (2.8<=x) or (x<6) then begin
y:=(a+b)/(x+1);
writeln(x:4:2, ' ' ,y:4:4);
x:=x+j;
end;
if x>=6 then begin
y:=exp(x)+sin(x);
writeln(x:4:2, ' ' ,y:4:2);
x:=x+j;
end;
end;
readkey;
end.end.
1.6 Вывод на экран
1.7 Вывод
Значения функции F(x), полученные в результате работы в пакете MatchCad 14.0 совпадают со значениями функции, полученными в результате работы в пакете Turbo Pascal 7.0 при заданном интервале.
2. Задача 2 (Вычисление корня уравнения)
2.1 Постановка задачи
Вычислить корень уравнения вида f(x)=0 при заданном интервале и абсолютной погрешности. Определить количество итераций, необходимое для нахождения корня.
2.2 Исходные данные
(ln(x)*ln(x))/x
[2;4] , ε=0.0001
2.3 Математическая модель
2.3.1 Метод дихотомии
Метод дихотомии, который называют еще методом биекции или методом половинного деления – это один из простых способов решения алгебраических уравнений. Перед его применением необходимо отделить корни уравнения одним из известных способов, например, графическим методом. Будем считать, что корень t уравнения f(x)=0 отделен на отрезке [a;b]. Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления (дихотомии). Другими словами, требуется найти приближенное значение корня с заданной точностью ε.
Пусть функция f непрерывна на отрезке [a;b], f(a)*f(b)<0, ε=0.01 и t, принадлежащее отрезку [a;b] – единственный корень уравнения f(x)=0, a≤t≤b.(Мы не рассматриваем случай, когда корней на отрезке [a;b] несколько, т.е. более одного. В качестве ε можно взять и другое достаточно малое положительное число, например, 0,0001.)
Поделим отрезок [a;b] пополам. Получим точку c=a+b2, a<c<b и два отрезка [a;c] и [c;b]. Если f(c)=0, то корень t найден (t=c). Если нет, то из двух полученных отрезков [a;c] и [c;b] надо выбрать один [a1;b1] такой, что f(a1)*f(b1)<0, то есть [a1;b1]=[a;c], если f(a)*f(c)<0 или [a1;b1]=[c;b], если f(c)*f(b)<0. Новый отрезко [a1;b1] делим пополам. Получаем середину этого отрезка c1=a1+b12 и так далее.
Для того, чтобы найти приближенное значение корня с точностью до ε>0, необходимо остановить процесс половинного деления на таком шаге n, на котором |bn-cn|<ε и вычислить x=an+bn2. Тогда можно взять t≈x.
2.3.2 Метод Ньютона
Чтобы численно решить уравнение методом простой итерации, его необходимо привести к следующей форме: , где — сжимающее отображение.
Для наилучшей сходимости метода в точке очередного приближения должно выполняться условие . Решение данного уравнения ищут в виде , тогда:
В предположении, что точка приближения «достаточно близка» к корню , и что заданная функция непрерывна , окончательная формула для такова:
С учётом этого функция определяется выражением:
Эта функция в окрестности корня осуществляет сжимающее отображение[1], и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:
По теореме Банаха последовательность приближений стремится к корню уравнения .
Иллюстрация метода Ньютона (синим изображена функция , нуль которой необходимо найти, красным — касательная в точке очередного приближения ). Здесь мы можем увидеть, что последующее приближение лучше предыдущего .
Геометрическая интерпретация
Основная идея метода заключается в следующем: задаётся начальное приближение вблизи предположительного корня, после чего строится касательная к исследуемой функции в точке приближения, для которой находится пересечение с осью абсцисс. Эта точка и берётся в качестве следующего приближения. И так далее, пока не будет достигнута необходимая точность.
Пусть — определённая на отрезке и дифференцируемая на нём действительнозначная функция. Тогда формула итеративного исчисления приближений может быть выведена следующим образом:
где α — угол наклона касательной в точке .
Следовательно искомое выражение для имеет вид:
Итерационный процесс
2.4 Решение задачи в пакете MathCad 14.0
2.5 Блок-схема
2.5.1 Метод дихтомии
+
-
- +
2.5.2 Метод Ньютона
- +
2.6. Текст программы (написан в пакете Turbo Pascal 7.0)
2.6.1 Метод дихтомии
program xD;
uses crt;
var x,eps,a,b,c:real;
n:integer;
function f(x:real):real;
begin
F:=ln(x)-x+1.8
end;
begin
clrscr;
writeln('Vvedite a b');
read(a,b);
writeln('Vvedite eps');
read(eps);
n:=0;
repeat
c:=(a+b)/2;
if (f(a)*f(c))<0 then b:=c else a:=c;
n:=n+1;
until (b-a)<=eps;
x:=(a+b)/2;
writeln ('x=', x:5:3);
writeln ('delili raz=', n);
readkey;
end.
2.6.2 Метод Ньютона
program xvd;
uses crt;
const e=0.1/1000; n=1000;
var X0:real;
k:integer;
function F(x:real):real;
begin F:=(ln(x)*ln(x))/x;
end;
function F1(x:real):real;
begin F1:=(2*ln(x)/x*x)-(ln(x)*ln(x)
procedure xD (H:integer; e:real; var x0:real; var k:integer);
var xs,xn,y,del:real;
begin
xs:=x0;
k:=1;
repeat
y:=f1(xs);
xn:=Xs-f(xs)/y;
del:=abs(xn-xs);
if del<e then begin
x0:=xn;
writeln('sna4enie kopn9=',x0,' K=',k);
end
Else begin if k>N then Writeln('oIIIiBka')
else begin
k:=k+1;
xs:=xn;
end;
end;
until del<e;
end;
begin
clrscr;
x0:=1;
xD(n,e,x0,k);
writeln('sna4enie korn9=',X0:8:5,' K=',k:4);
readkey;
end.
2.7 Вывод на экран
2.7.1 Метод дихтомии
2.7.2 Метод Ньютона
2.8 Вывод
Корень уравнения, полученный в результате работы в пакете MathCad 14.0 cовпадает с корнем уравнения, полученным в результате работы в пакете TurboPascal 7.0 на заданном интервале с помощью метода дихтомии (половинного деления) и метода итераций. Но метод половинного деления выгоднее при решении подобных задач ,так как, используя его, пользователь сразу получает нужный и точный ответ.
3. Задача 3
3.1 Постановка задачи:
Вычислить с заданной точностью экстремум функции. Вывести таблицу значений аргумента х и функции y=f(x), и значение экстремума.
3.2 Исходные данные
Функция (ln(x)*ln(x))/x
Интервал [1;5];
Абсолютная погрешность: 10⁻⁵
3.3 Математическая модель
3.3.1 Метод золотого сечения
Пусть задана функция . Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки и такие, что:
Иллюстрация выбора промежуточных точек метода золотого сечения.
, где — пропорция золотого сечения.
Таким образом:
То есть точка делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.
3.3.2 Метод равномерного перебора
Метод перебора (метод равномерного поиска) — простейший из методов поиска значений действительно-значных функций по какому-либо из критериев сравнения (на максимум, на минимум , на определённую константу). Применительно к экстремальным задачам является примером прямого метода условной одномерной пассивной оптимизации.
Проиллюстрируем суть метода равномерного поиска посредством рассмотрения задачи нахождения минимума.
Пусть задана функция
.
И задача оптимизации выглядит так:
Пусть также задано число наблюдений n.
Тогда отрезок разбивают на равных частей точками деления:
Вычислив значения в точках , найдем путем сравнения точку , где — это число от до такую, что
для всех от до .
Тогда интервал неопределённости составляет величину , а погрешность определения точки минимума функции соответственно составляет : .
Модификация
Если заданное количество измерений чётно (n = 2k), то разбиение можно проводить другим, более изощрённым способом:
, где δ — некая константа из интервала .
Тогда в худшем случае интервал неопределённости имеет длину
3.4 Решение задачи в пакете MathCad 14.0
3.5 Блок-схема
3.5.1 Метод «золотого» сечения
-
+
+ -
3.5.2 Метод равномерного перебора
- +
- +
3.6 Текст программы (написан в пакете Turbo Pascal 7.0)
3.6.1 Метод «золотого» сечения
Program mn;
uses crt;
const EPS=0.001;
Var a,b,x,Fa,Fb,Fx:real;
k:integer;
Function F(x:real):real;
begin F:=ln(x)-x+1.8=0; end;
Begin
Clrscr;
Repeat
Writeln('please, inter A and B');
Readln(a,b);
Fa:=F(a);
Fb:=F(b);
if Fa*Fb>0 then writeln('please,inter other A and B');
until Fa*Fb<0;
k:=0;
While ABS(b-a)>EPS do begin
X:=(a+b)/2;
Writeln(x:8:4);
k:=k+1;
Fx:=F(x);
if Fx=0 then writeln('kopeHb=',x);
if Fa*Fx<0 then begin
else begin
a:=x;
Fa:=Fx;
end;
end;
Writeln('KopeHb=',x:8:5);
Writeln('F(x)=',Fx);
Writeln('k=',k);
Readkey;
End.
3.6.2 Метод равномерного перебора.
Program EXTRE;
uses crt;
var
A,B,Xmin,Ymin,x,h,y:real;
function f(x:real):real;
begin
f:=ln(x)*ln(x)/x;
end;
begin
clrscr;
writeln('vvedite interval i shag ckanirovania');
readln(a,b,h);
Ymin:=1E20;
x:=A;
writeln(' x y');
while x<b do begin
Y:=f(x);
if Y<Ymin then
begin
Ymin:=Y;
Xmin:=X;
end;
writeln(x:8:4,' ', y:8:4);
x:=x+h;
end;
writeln(' min=',Xmin:8:4);
writeln('znachtnie min=',Ymin:8:4);
readln;
end.
3.7 Вывод на экран
3.7.1 Метод «золотого» сечения
3.7.2 Метод равномерного перебора
3.9 Вывод
Значение точки минимума, полученное в результате работы в пакете MathCad 14.0 совпадает со значениями, полученными в результате работы в пакете TurboPascal 7.0 с помощью метода «золотого» сечения и метода равномерного перебора. Метод «золотого» сечения при оптимизации выгоднее, так как при нем нет вероятности того, что точка минимума будет пропущена программой из-за задания слишком большого шага.
4. Задача 4 (вычисление определенного интеграла)
4.1 Постановка задачи
Вычислить значение интеграла на заданном отрезке интегрирования [a;b]. Считать заданным число разбиений отрезка интегрирования n и численный метод решения. На печать вывести приближенное, точное значение интеграла и относительную погрешность вычисления(точность вычисления).
4.2 Исходные данные
4.3 Математическая модель
4.3.1 Метод Гаусса
Пусть система линейных алгебраических уравнений имеет n неизвестных и ранг ее матрицы равен n, то есть система имеет единственное решение.
Предположим, что а11№ 0 и более того, что а11 - максимальный коэффициент по модулю в матрице А. Этого всегда можно добиться перестановкой уравнений, а также переименованием переменных, то есть перестановкой столбцов.
Разделим обе части первого уравнения на а11. Получим x1+с12х2+…+с1nхn=d1 (41)
Умножим
обе части полученного
Далее умножим уравнение 4 на а31 и вычтем его из третьего уравнения системы, х1 тоже пропадет. И так далее.
В результате получим систему, порядок которой на единицу меньше порядка исходной системы, так как в уравнениях системы отсутствуют слагаемые с х1 и отсутствует первое уравнение вида (41)
4.3.2 Метод трапеций
Аппроксимация в этом методе
осуществляется полиномом первой степени.
Суть метода ясна из рисунка.
На единичном интервале
В случае равномерной сетки (h = const )
При этом
, а
. Погрешность метода трапеций в два раза
выше, чем у метода средних прямоугольников!
Однако на практике найти среднее значение
на элементарном интервале можно только
у функций, заданных аналитически (а не
таблично), поэтому использовать метод
средних прямоугольников удается далеко
не всегда. В силу разных знаков погрешности
в формулах трапеций и средних прямоугольников
истинное значение интеграла обычно лежит
между двумя этими оценками.
(5)
4.4 Решение задачи в пакете MathCad 14.0
4.5 Блок-схема
4.5.1 Метод Гаусса
4.5.2 Метод трапеций
-
+
4.6 Текст программы (написан в программе TurboPascal 7.0)
4.6.1 Метод Гаусса
Program INTEGRAL_GAUSS8;
uses crt;
var a,b,integ:real;
function f(x:real):real;
begin
f:=ln(x)*ln(x)*x;
end;
function gauss8 (a,b:real):real;
var a1,a2,x,g:real;
i:integer;
ag,xg:array [1..8] of real;
begin
ag[1]:=0.10122854;
ag[2]:=0.22238104;
ag[3]:=0.31370664;
ag[4]:=0.36268378;
ag[5]:=0.36268378;
ag[6]:=0.31370664;
ag[7]:=0.22238104;
ag[8]:=0.10122854;
xg[1]:=(-0.96028986);
xg[2]:=(-0.79666648);
xg[3]:=(-0.52553242);
xg[4]:=(-0.18343464);
xg[5]:=0.18343464;
xg[6]:=0.52553242;
xg[7]:=0.79666648;
xg[8]:=0.96028986;
a:=0;
b:=4;
a1:=(a+b)*0.5;
a2:=(b-a)*0.5;
g:=0.0;
for i:=1 to 8 do
begin
x:=a1-a2*xg[i];
g:=g+ag[i]*f(x);
end;
gauss8:=g*a2;
end;
begin
clrscr;
integ:=gauss8(a,b);
writeln('integ= ',integ:8:2);
readkey;
end.
4.6.2 Метод трапеций
program Trap;
uses crt;
const p=3.14;
var a,b,x,dx,z,dz,zt:real;
n,i,k:integer;
function f(x:real):real;
begin
f:=ln(x)*ln(x)/x;
end;
begin
clrscr;
k:=0;
a:=1;
b:=4;
zt:=1;
n:=60;
while k<5 do
begin
z:=(f(a)+f(b))/2;
dx:=(b-a)/n;
x:=a;
for i:=1 to n-1 do
begin
x:=x+dx;
z:=z+f(x);
end;
z:=z*dx;
writeln(' deleniy= znachenia integrala');
writeln(' ',n,' ',z:8:2,' ',zt:8:2);
k:=k+1;
n:=n*2;
readkey;
end.
4.7 Вывод на экран
4.7.1 Метод Гаусса
4.7.2 Метод трапеций
4.8 Вывод
Значение интеграла, полученное в результате работы в пакете MathCad 14.0 почти совпадает со значениями, полученными в результате работы в пакете TurboPascal 7.0 с помощью метода Гаусса и метода трапеций. Метод трапеций ищет значение интеграла точнее.
5. Задача 5 (Поиск частного решения дифференциального уравнения)
5.1 Постановка задачи
Найти частный интеграл (частное решение) дифференциального уравнения.
5.2 Исходные данные
Дифференциальное уравнение: y’=y*e^x²;
Начальные условия: y(0)=1.
5.3 Математическая модель
5.3.1 Задача Коши
Задача Коши для дифференциального уравнения n-го порядка – это нахождение такого решения этого уравнения, которое будет удовлетворять заданным начальным условиям.
5.3.2 Метод Эйлера
Наиболее простой численный метод решения (систем) обыкновенных дифференциальных уравнений. Впервые описан Леонардом Эйлером в 1768 году в работе «Интегральное исчисление»[1]. Метод Эйлера является явным, одношаговым методом первого порядка точности, основанном на аппроксимации интегральной кривой кусочно линейной функцией, т. н. ломаной Эйлера.
Описание метода
Пусть дана задача Коши для уравнения первого порядка
где функция f определена на некоторой области . Решение разыскивается на интервале [x0,b). На этом интервале введем узлы
Приближенное решение в узлах x
Эти формулы обобщаются на случай систем обыкновенных дифференциальных уравнений.
Оценка погрешности
Метод Эйлера является методом первого порядка. Если функция f непрерывна в D и непрерывно дифференцируема по переменной y в D, то имеет место следующая оценка погрешности
где h — средний шаг, то есть существует C > 0 такая, что .
Заметим, что условия гладкости на правую часть, гарантирующие единственность решения задачи Коши, необходимы для обоснования сходимости метода Эйлера.
Значение метода Эйлера
Метод Эйлера являлся исторически первым методом численного решения задачи Коши. О. Коши использовал этот метод для доказательства существования решения задачи Коши. В виду не высокой точности и вычислительной неустойчивости для практического нахождения решений задачи Коши метод Эйлера применяется редко. Однако в виду своей простоты метод Эйлера находит свое применение в теоретических исследованиях дифференциальных уравнений, задач вариационного исчисления и ряда других математических проблем.
Модифицированный метод Эйлера с пересчетом
Вычисления по методу Эйлера с пересчетом делаются в два этапа.
Прогноз:
Коррекция:
Модифицированный метод Эйлера
с пересчетом имеет второй порядок
точности, однако для его реализации
необходимо дважды вычислять правую
часть функции. Заметим, что метод
Эйлера с пересчетом представляет собой
разновидность методов Рунге-
5.3.3 Метод Рунге-Кутта
Метод позволяет решать системы обыкновенных дифференциальных уравнений (ОДУ) первого порядка следующего вида:
которые имеют решение:
где t - независимая переменная (например, время); X, Y и т.д. - искомые функции (зависимые от t переменные). Функции f, g и т.д. - заданы. Также предполагаются заданными и начальные условия, т.е. значения искомых функций в начальный момент.
Одно диф. уравнение - частный случай системы с одним элементом. Поэтому, далее речь пойдет для определенности о системе уравнений.
Метод может быть полезен и для решения диф. уравнений высшего (второго и т.д.) порядка, т.к. они могут быть представлены системой диф. уравнений первого порядка.
Метод Рунге-Кутта
заключается в рекурентном
5.4 Решение задачи в пакете MatchCad 14.0
5.4.1 Стандартный метод решения с использованием блока Odesolve
5.4.2 Метод Рунге-Кутта с использованием блока rkfixed
5.5 Блок-схема
5.5.1 Модифицированный метод Эйлера
5.5.2 Метод Рунге-Кутта
5.6. Текст программы (написан в пакете Turbo Pascal 7.0)
5.6.1 Модифицированный метод Эйлера
program dddd;
uses crt;
var
x0,y0,h,x,y,xn:real;
i,n:integer;
function fd(x,y:real):real;
begin
fd:=y*exp(x);
end;
begin
clrscr;
x0:=0;
y0:=1;
xn:=1;
h:=0.1;
n:=trunc((xn-x0)/h);
x:=x0;
y:=y0;
writeln('znachenie x znachenie y');
writeln(x:6:2,' ',y:8:2);
for i:=1 to n do
begin
y:=y+h*fd(x,y);
x:=x+h;
writeln(x:6:2,' ',y:8:2);
end;
readln;
end.
5.6.2 Метод Рунге-Кутта
program sl;
uses crt;
var
x0,y0,h,x,y,xn,k0,k1,k2,k3,t:
i,n:integer;
function fd(x,y:real):real;
begin
fd:=y*exp(x);
end;
begin
clrscr;
x0:=0;
y0:=1;
xn:=1 ;
h:=0.1;
n:=trunc((xn-x0)/h);
x:=x0;
y:=y0;
writeln('znachenie x znachenir y');
writeln(x:6:2,' ',y:8:6);
for i:=1 to n do
begin
k0:=h*fd(x,y);
t:=x+h/2;
k1:=h*fd(t,y+0.5*k0);
k2:=h*fd(t,y+0.5*k1);
x:=x+h;
k3:=h*fd(x,y+k2);
y:=y+(k0+2*(k1+k2)+k3)/6;
writeln (x:6:2,' ',y:8:6);
end;
readln;
end.
5.7 Вывод на экран
5.7.1 Модифицированный метод Эйлера
5.7.2 Метод Рунге-Кутта 5.9 Вывод
Значения дифференциального
- Вычислительные сети
- Вычислить с максимальной точностью значение суммы k элементов
- Вычитаемые временные разницы и отложенные налоговые активы: понятие, порядок формирования и отражение в отчетности
- Вычитка и редактирование учебного издания для младшей школы
- Вышивальный промысел как вид ДПИ
- Вышивание
- Вышивка как средство приобщения детей младшего школьного возраста к декоративно-прикладному искусству
- Вычисления определенных интегралов методом Монте-Карло
- Вычисления результанта 2-ч полиномов
- Вычисления статических моментов, центра масс и моментов инерции
- Вычислительная модель финансов предприятия
- Вычислительная практика
- Вычислительная сеть как составная часть защищенной компьютерной системы
- Вычислительные машины