Numerical Methods
By traditional way finding root of a polynomial function is always time consuming. There are a couple of solutions to this problem. One is Newton-Raphson method. Another is division by two methods. Below you will find implementation of these methods.
The Algorithm
Pascal Source Code (Newton-Raphson Method)
{ This program finds root of F(x)=x^2-e^x-1=0 function for x0=1 and
eps=0.0001 using Newton-Raphson method.
}
uses crt;
var x1,x0,eps:real;i:integer;
Function f(x:real):real;
begin
f:=sqr(x)-exp(x)-1;
end;
Function ft(x:real):real;
begin
ft:=2*x-exp(x);
end;
Begin
clrscr;
writeln('F(x) = x^2-e^x-1=0');
writeln('x0 de?eri : 1.0000');x0:=1.0000;
eps:=0.0001; i:=1; x1:=x0;
repeat
x0:=x1;
x1:=x0-f(x0)/ft(x0);
writeln('x',i,' value : ',x1:7:4);
i:=i+1;
until abs((x1-x0)) < eps;
readln;
End.
Sample Execution for Newton-Raphson Method
F(x) = x^2-e^x-1=0
x0 value : 1.0000
x1 value : -2.7844
x2 value : -1.5961
x3 value : -1.2000
x4 value : -1.1486
x5 value : -1.1478
x6 value : -1.1478
Pascal Source Code Pascal (Division by Two)
using Division by Two method.
}
uses crt;
var eps:real; i:integer; ch:char;
Function f(x:real):real;
begin
f:=(x*x)+(3*x)-28;
end;
Procedure Division_by_Two(Xs,Xe:real;x,y:integer);
var Xm,k:real;
begin
i:=0;
repeat
Xm:=(Xs+Xe)/2;
if (F(Xm)*F(Xs)) > 0 then Xs:=Xm
else if (F(Xm)*F(Xs)) < 0 then Xe:=Xm;
gotoxy(x,y+i);write(i+1:2,'. Xm=',Xm:5:3,' F(Xm)=',F(Xm):6:3);
i:=i+1;
k:=1000*F(Xm);
until abs(round(k)) <= 1 ;
end;
BEGIN
clrscr; eps:=0.001;
writeln(' ------ F(x)=x^2+3x-28=0 -----');
writeln(' For interval (3,5) eps:0.001');
writeln(' ---- Division by Two method ---- ');
Division_by_Two(3,5,5,4);
repeat ch:=readkey until ch<>#27; clrscr;
writeln(' ------ F(x)=x^2+3x-28=0 -----');
writeln(' For interval (0,7) eps:0.001');
writeln(' ---- Division by Two method ---- ');
Division_by_Two (0,7,5,4);
repeat ch:=readkey until ch=#27;
END.
Sample Execution for Division by Two Method
------ F(x)=x^2+3x-28=0 -----
For interval (3,5) eps:0.001
---- Division by Two method ----
1. Xm=4.000 F(Xm)= 0.000
------ F(x)=x^2+3x-28=0 -----
For interval (0,7) eps:0.001
---- Division by Two method ----
1. Xm=3.500 F(Xm)=-5.250
2. Xm=5.250 F(Xm)=15.313
3. Xm=4.375 F(Xm)= 4.266
4. Xm=3.938 F(Xm)=-0.684
5. Xm=4.156 F(Xm)= 1.743
6. Xm=4.047 F(Xm)= 0.518
7. Xm=3.992 F(Xm)=-0.086
8. Xm=4.020 F(Xm)= 0.215
9. Xm=4.006 F(Xm)= 0.064
10. Xm=3.999 F(Xm)=-0.011
11. Xm=4.002 F(Xm)= 0.027
12. Xm=4.001 F(Xm)= 0.008
13. Xm=4.000 F(Xm)=-0.001