Вычислительные методы

Федеральное агентство по образованию

ГОУ ВПО Уральский федеральный  университет имени первого президента России Б. Н. Ельцина

Кафедра Вычислительной Техники.

 

 

 

 

 

 

 

 

 

 

Курсовая работа

По дисциплине «Информатика»

 

 

 

 

 

 

 

 

 

 

 

 

 

Студент          Якушев М.А.

гр. Фт-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], и алгоритм нахождения численного решения уравнения сводится к итерационной процедуре вычисления:

По теореме Банаха последовательность приближений стремится к корню  уравнения  .

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

Геометрическая интерпретация

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

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

где α — угол наклона касательной в точке .

Следовательно искомое выражение  для  имеет вид:

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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)/x*x); end;

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 Метод «золотого»  сечения

 

 

 

 -

 

 +

+ -