Метод деления отрезка пополам.

Белорусский национальный технический университет

Энергетический факультет

Кафедра «ТЭС»

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

по дисциплине “Информатика ”

Тема: ”построение графика временной функции”

Выполнил: Лобанок Н.В

Проверил: Тарасевич Л.А

Минск 2011

CОДЕРЖАНИЕ

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

2. Постановка задачи (условие задачи, которое выдано).

3. Выбор и обоснование метода просчета. (Алгоритмы расчетов: метод решения нелинейного уравнения и т.д.).

4. Блок-схемы метода просчета.

5. Листинг программы.

6. Результаты расчетов.

7. Литература.

Введение

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

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

Особенностями языка являются строгая типизация и наличие средств структурного (процедурного) программирования. Паскаль был одним из первых таких языков. По мнению Н. Вирта, язык должен способствовать дисциплинированию программирования, поэтому, наряду со строгой типизацией, в Паскале сведены к минимуму возможные синтаксические неоднозначности, а сам синтаксис автор постарался сделать интуитивно понятным даже при первом знакомстве с языком.

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

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

Задана временная функция:

y=ǀpt3+qt2+ct+k+mǀ

k – корень нелинейного уравнения x=e-x, которое нужно решить методом деления отрезка пополам с точностью ε = 10-3, при начальном значении x0=0, xk=1,

m – наименьший по абсолютному значению корень квадратного уравнения:

az2+bz+d=0

при a=1, b=-4, d=3.

Составить схему алгоритма и программу построения графика функции y, работающую как в машинном, так и в реальном времени. Реальное время в диапазоне (t0 - tkon) формируется таймером в виде программного модуля с метками Tk, называемыми временем квантования. При вычислении функции использовать алгоритм Горнера (схему Горнера).

Причем t0=0 c; tkon=115 c ; Tk = 0,25 c;

Коэффициенты:

P=1; q=cos 30°; c=sin 35°.

Таблица имен и переменных в функциях.

Переменная Тип Описание
a,b Real Начало и конец отрезка нахождения корня
c, x1,x0 Real Промежуточные значения корня в функциях
Disk Real Вспомогательная переменная для нахождения дискриминанта
g[0..4] Array of real Массив для нахождения значения функции при помощи схемы Горнера
P,q,c Real Коэффициенты функции
u,z Real Вспомогательные переменные для построения графика
t0,tkon,tk const Начальное время, конечное время и время квантования
T Real Промежуточные значения времени

Таблица имен и переменных в основной программе.

Переменная Тип Описание
i,j Integer Счетчики
Cc Integer Переменная, предназначенная для выбора пункта меню
Prexit Boolen Параметр, отвечающий за выход из меню
Key Char Параметр, предназначенный для выбора определённого пункта меню
GrDriver Integer Параметр, который задаёт тип видеоадаптера
GrMode Integer Параметр, который задаёт режим видеоадаптера

Описание методов решения нелинейного

Уравнения.

Метод деления отрезка пополам.

Суть метода сводится к сужению интервала нахождения корня до заданной погрешности.

Алгоритм нахождения корня:

1) f(a)*f(b)<0 – проверка условия нахождения корня на отрезке [a,b];

2) делится отрезок [a,b] пополам c=(a+b)/2;

3) проверяется, на каком из отрезков [a,с] или [с,b] находится корень:

если f(a)*f(c)<0 то корень находится на [a,с],

если f(a)*f(c)>0 то корень находится на [c,b]

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

|a-с|<eps

|a-b|<eps

|f(c)|<eps

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

Метод хорд.

Метод хорд является более быстрым способом нахождения корня уравнения f(x0)=0 лежащем на отрезке [a,b], в током, что f(a)*f(b)<0. Требуется найти корень с погрешностью e. Для определенности пусть f(a)<0,f(b)>0. Делится отрезок в отношении - f(a)/f(b). Это дает приближенное значение корня x, равное x=a+h, где

x=a+ -(f(a))*(b-a)/-(f(a)+f(b); h= -(f(a))*(b-a)/-(f(a)+f(b);

Далее применяя этот прием к тому из отрезков [a,x] или [x,b] на концах, которого функция имеет противоположные знаки, получим второе приближение корня.

Геометрический метод хорд эквивалентен замене кривой y=f(x), хордой проходящей через точки (a и b) уравнения хорды:

(x-a)/(b-a)=(y-f(a))/(f(b)-f(a)), полагая, что x=x1 y=0, получим

x1=a – f(a)*(b-a)/(f(b)-f(a)), где x1-первое приближение корня. Для сходимости процесса корень должен быть отделен и вторая производная должна сохранять знак на [a,b].

Рабочие формулы метода хорд:

а) для случая f(a)<0

xn+1= xn- f(xn)*(b-xn)/f(b)-f(xn)

б) для случая f(a)>0

xn+1= xn- f(xn)*(xn-a)/f(xn)-f(a)

Метод простой итерации.

Суть метода состоит в замене уравнения f(x) на уравнение x=φ(x). Процесс нахождения корня итерационный.

x2 = φ(x1)

xn+1 = φ(xn)

Счёт заканчивается при выполнении условия:

| xn+1-xn|<=eps или | f(xn+1)|<=eps

Условие, при котором данный процесс будет сходящимся, определяется следующей теоремой:

если интервал (a,b) является интервалом изоляции корня уравнения x=φ(x) и во всех точках данного интервала удовлетворяется условие

| φ(x)|<=q<1,

то процесс нахождения корня будет сходящимся, вычисления прекращаются при выполнении условия:

|xn+1-xn|<=(1-q)/q*eps

Где q-наименьшее значение | φ(x)| при изменении x: a<=x<=b

Очень важно при использовании данного метода преобразование уравнения f(x)=0 к уравнению вида x= φ(x) таким образом, чтобы итерационный процесс был сходящимся.

Метод Ньютона.

Метод основан на последовательном приближении к корню уравнения при заданных начальных условиях: начальное приближение и точность вычисления. В методе Ньютона осуществляется экстрополяция с помощью касательной к кривой в данной точке. В основе метода лежит разложение функции по формуле Тейлора. Члены, содержащие h во второй и более высоких степенях, отбрасываются. Для нахождения корня используется соотношение xn+1 = xn + h. Предполагается, что переход от xn к xn+1 приближает значение функции к нулю.

h = -f(x)/f’(x) тогда

xn+1 = xn -f(x)/f’(x)

Условие окончания счёта:

|xn+1-xn|<=eps

| f(xn+1)|<=eps

Очень важным при использовании данного метода является выбор начального приближения. Начальное приближение выбирается из условия

F(x0)*f’’(x0)>0

В противном случае сходимость итерационного процесса не гарантируется.

Схема Горнера.

Один из методов вычисления полинома – разложение его по схеме Горнера.

Полином

f(x) = antn + an-1tn-1 +… + a4t4+ a3t3+ a2t2+ a1t + a0

по схеме Горнера представляется в виде

f(x) = (((…(ant+ an-1)t +…+a4)t + a3)t + a2)t +a1)t + a0

Данное разложение полинома удобно тем, что в нём отсутствует возведение в степень, что значительно ускоряет вычисление полинома.

Блок-схема метода деления отрезка пополам:

Метод деления отрезка пополам. - student2.ru

Блок-схема метода хорд:

 
  Метод деления отрезка пополам. - student2.ru

Метод деления отрезка пополам. - student2.ru Нет Да

Метод деления отрезка пополам. - student2.ru

Метод деления отрезка пополам. - student2.ru Нет Да

 
  Метод деления отрезка пополам. - student2.ru

Нет Метод деления отрезка пополам. - student2.ru

       
  Метод деления отрезка пополам. - student2.ru
    Метод деления отрезка пополам. - student2.ru
 

n:=k
Да

       
  Метод деления отрезка пополам. - student2.ru
 
    Метод деления отрезка пополам. - student2.ru

Блок-схема метода простой итерации:

 
  Метод деления отрезка пополам. - student2.ru

Нет Метод деления отрезка пополам. - student2.ru

 
  Метод деления отрезка пополам. - student2.ru

Метод деления отрезка пополам. - student2.ru Метод деления отрезка пополам. - student2.ru Метод деления отрезка пополам. - student2.ru

k=j(x1)
Да

 
  Метод деления отрезка пополам. - student2.ru

Метод деления отрезка пополам. - student2.ru Нет

x1:=k

Метод деления отрезка пополам. - student2.ru

Метод деления отрезка пополам. - student2.ru Да

 
  Метод деления отрезка пополам. - student2.ru

Метод деления отрезка пополам. - student2.ru

 
  Метод деления отрезка пополам. - student2.ru

Блок-схема метода Ньютона:

       
    Метод деления отрезка пополам. - student2.ru
 
  Метод деления отрезка пополам. - student2.ru

x0:=a xx0:=a
xxxxx

 
  Метод деления отрезка пополам. - student2.ru

Метод деления отрезка пополам. - student2.ru

Метод деления отрезка пополам. - student2.ru

Нет

x0:=x
Метод деления отрезка пополам. - student2.ru

Метод деления отрезка пополам. - student2.ru

Метод деления отрезка пополам. - student2.ru

Да

 
  Метод деления отрезка пополам. - student2.ru

 
  Метод деления отрезка пополам. - student2.ru

 
  Метод деления отрезка пополам. - student2.ru

Блок-схема схемы Горнера:

Метод деления отрезка пополам. - student2.ru Метод деления отрезка пополам. - student2.ru

 
  Метод деления отрезка пополам. - student2.ru

Листинг программы.

Program kurs;

uses crt,graph;

var GrMode,Grdriver:integer;

cc,j,i:integer;

s:string;

key:char;

prexit:boolean;

menu:array[1..5] of string;

function f(x:real):real;

begin

f:=exp(-x)-x;

end;

function p1(a,b:real):real;

var c:real;

const e=0.001;

begin

repeat

c:=(a+b)/2;

if f(a)*f(c)<0 then b:=c else a:=c;

until abs(a-b)<e;

p1:=a;

end;

function p2(a,b:real):real;

var x1,x0:real;

const e=0.001;

begin

if f(a)<0 then begin x1:=a;

repeat

x0:=x1;

x1:=x0-f(x0)*(b-x0)/(f(b)-f(x0));

until abs(x0-x1)<e; end

else begin x1:=b;

repeat

x0:=x1;

x1:=x0-f(x0)*(x0-a)/(f(x0)-f(a));

until abs(x0-x1)<e; end;

p2:=x1;

end;

function p3(q:real):real;

var x0,x1:real;

const e=0.001;

begin

x1:=q;

repeat

x0:=x1;

x1:=exp(-x0);

until abs(x0-x1)<e;

p3:=x1;

end;

function p4(q:real):real;

var x0,x1:real;

const e=0.001;

begin

x1:=q;

repeat

x0:=x1;

x1:=x0-f(x0)/(-exp(-x0)-1);

until abs(x1-x0)<e;

p4:=x1;

end;

procedure nl;

var a,b,q,l:real;

s:string;

begin

a:=0; b:=1; q:=0.5;

Outtextxy(100,100,'Reshenie nelineinogo uravneniya:');

Outtextxy(100,150,'Metod bisekcii: k = ');

str(p1(a,b),s); Outtextxy(320,150,s);

Outtextxy(100,200,'Metod hord: k = ');

str(p2(a,b),s); Outtextxy(320,200,s);

Outtextxy(100,250,'Metod prostyh iteracij: k = ');

str(p3(q),s); Outtextxy(320,250,s);

Outtextxy(100,300,'Metod Njutona: k = ');

str(p4(q),s); Outtextxy(320,300,s);

readkey;

end;

function kv:real;

var a,b,d,disk,x1,x2,r:real;

begin

a:=1; b:=-4; d:=3;

disk:=b*b-4*a*d;

x1:=(-b+sqrt(disk))/(2*a);

x2:=(-b-sqrt(disk))/(2*a);

if abs(x1)<abs(x2) then r:=x1 else r:=x2;

kv:=r;

end;

procedure kvadr;

var s:string;

begin

Outtextxy(100,100,'Naimenshij po absolutmomu znacheeniju koren uravneniya');

Outtextxy(100,150,'a*z*z+b*z+d=0');

Outtextxy(100,200,'pri a = 1, b = -4, d = 3');

str(kv:3:3,s);

outtextxy(100,250,'m = '); outtextxy(130,250,s);

readln;

end;

procedure graf;

const t0=0; tkon=115; tk=0.75;

var i:integer;

s:string;

p,q,c,k,m,o,gr,t:real; u,z: integer;

g:array[0..4] of real;

begin

p:=1; q:=cos(30*pi/180); c:=sin(35*pi/180);

cleardevice;

setcolor(green);

Outtextxy(100,50,'Znacheniya koefficientov osnovnoi funkcii');

setcolor(white);

str(p:3:3,s);

outtextxy(100,100,'p = ');outtextxy(150,100,s);

str(q:3:3,s);

outtextxy(100,130,'q = ');outtextxy(150,130,s);

str(c:3:3,s);

outtextxy(100,160,'c = ');outtextxy(150,160,s);

str(p1(0,1):3:3,s);

outtextxy(100,190,'k = ');outtextxy(150,190,s);

str(kv:3:3,s);

outtextxy(100,220,'m = ');outtextxy(150,220,s);

readkey; cleardevice;

setcolor(green);

rectangle(490,40,630,300);

rectangle(490,40,630,20);

line(530,20,530,300);

outtextxy(500,30,'t y');

setcolor(8);

for i:=1 to 15 do line(52,400-20*i,420,400-20*i);

for i:=1 to 12 do line(50+30*i,95,50+30*i,398);

setcolor(yellow);

line (50,5,50,400); line(50,400,470,400);

line (50,5,48,10); line (50,5,52,10);

outtextxy(470,410,'t');

line (470,400,465,398); line (470,400,465,402); setcolor(yellow);

outtextxy(60,10,'y*10^6 ');

for i:=1 to 120 do

if i mod 10 = 0 then

begin

line(50+3*i,398,50+3*i,402);

str(i,s);

outtextxy(40+3*i,410,s);

end;

outtextxy(45,410,'0');

for i:=1 to 16 do

begin

line(48,400-20*i,52,400-20*i);

str(0.1*i:3:1,s);

outtextxy(10,395-20*i,s);

end;

t:=t0;

u:=50; z:=400-round(abs((p1(0,1)+kv)/5000));

g[1]:=p;

g[2]:=q;

g[3]:=c;

g[4]:=kv+p1(0,1);

repeat

if t>tkon then t:=tkon;

gr:=0;

for i:=1 to 3 do

gr:=(gr+g[i])*t;

gr:=gr+g[4];

setcolor(white);

if frac(t/5)=0 then begin

str(t:2:0,s);

outtextxy(495,round(50+2*t),s);

str(abs(gr):3:1,s);

outtextxy(550,round(50+2*t),s); end;

setcolor(red);

line(u,z,round(50+3*t),(400-round(abs(gr)/5000)));

u:=round(50+3*t); z:=400-round(abs(gr)/5000) ;

if t<>tkon then t:=t+tk;

if cc=3 then delay(100);

until t=tkon;

readln;

end;

begin

GrDriver:=detect;

initgraph(GrDriver,GrMode,' ');

cleardevice;

setcolor(white);

menu[1]:=' Reshenie kvadratnogo uravneniya ';

menu[2]:=' Reshenie nelineynogo uravneniya ';

menu[3]:=' Grafik v realnom vremeni ';

menu[4]:=' Grafik v mashinnom vremeni ';

menu[5]:=' Vyhod iz programmy ';

cc:=1;

prexit:=false;

repeat

begin

setcolor(8);

cleardevice;

end;

Setcolor(4+127);

Outtextxy(170,100,'Menu');

for i:=1 to 5 do begin setcolor(green);

if i=cc then setcolor(6) else setcolor(yellow);

outtextxy(150,200+20*i,menu[i]);end;

key:=readkey;

case ord(key) of

13:begin cleardevice;

case cc of

1:kvadr;

2:nl;

3:graf;

4:graf;

5:prexit:=true; end;end;

72:dec(cc);

80:inc(cc); end;

if cc<1 then cc:=5;

if cc>5 then cc:=1;

until prexit;

closegraph;

end.

Результаты расчетов:

T Y
0.0 1.6
3580.0
27798.2
92906.1
219153.7
426791.0
736068.0
1167234.7
1532395.7

Наши рекомендации