Roots of a function: Difference between revisions

Content added Content deleted
(omit m4)
m (Fixed lang tags.)
Line 46: Line 46:
=={{header|ALGOL 68}}==
=={{header|ALGOL 68}}==
Finding 3 roots using the secant method:
Finding 3 roots using the secant method:
⚫
<lang algol68>MODE DBL = LONG REAL;
<pre>
⚫
MODE DBL = LONG REAL;
FORMAT dbl = $g(-long real width, long real width-6, -2)$;
FORMAT dbl = $g(-long real width, long real width-6, -2)$;


Line 116: Line 115:
)
)
OUT printf($"No third root found"l$); stop
OUT printf($"No third root found"l$); stop
ESAC
ESAC</lang>
⚫
Output:<lang algol68>1st root found at x = 9.1557112297752398099031e-1 (Approximately)
</pre>
Output:<pre>

⚫
1st root found at x = 9.1557112297752398099031e-1 (Approximately)
2nd root found at x = 2.1844288770224760190097e 0 (Approximately)
2nd root found at x = 2.1844288770224760190097e 0 (Approximately)
3rd root found at x = 0.0000000000000000000000e 0 (Exactly)</pre>
3rd root found at x = 0.0000000000000000000000e 0 (Exactly)</lang>
=={{header|AutoHotkey}}==
=={{header|AutoHotkey}}==
Poly(x) is a test function of one variable. <br>We search for its roots.
Poly(x) is a test function of one variable. <br>We search for its roots.
Line 312: Line 308:
=={{header|Fortran}}==
=={{header|Fortran}}==
{{works with|Fortran|90 and later}}
{{works with|Fortran|90 and later}}
<lang fortran> PROGRAM ROOTS_OF_A_FUNCTION
<lang fortran>PROGRAM ROOTS_OF_A_FUNCTION

⚫
IMPLICIT NONE
IMPLICIT NONE

⚫
INTEGER, PARAMETER :: dp = SELECTED_REAL_KIND(15)
INTEGER, PARAMETER :: dp = SELECTED_REAL_KIND(15)
REAL(dp) :: f, e, x, step, value
REAL(dp) :: f, e, x, step, value
LOGICAL :: s
LOGICAL :: s
⚫
⚫
f(x) = x*x*x - 3.0_dp*x*x + 2.0_dp*x
⚫
⚫
x = -1.0_dp ; step = 1.0e-6_dp ; e = 1.0e-9_dp
⚫
s = (f(x) > 0)
DO WHILE (x < 3.0)
⚫
value = f(x)
⚫
IF(ABS(value) < e) THEN
⚫
WRITE(*,"(A,F12.9)") "Root found at x =", x
⚫
s = .NOT. s
⚫
ELSE IF ((value > 0) .NEQV. s) THEN
⚫
WRITE(*,"(A,F12.9)") "Root found near x = ", x
⚫
s = .NOT. s
⚫
END IF
⚫
x = x + step
⚫
END DO
⚫
END PROGRAM ROOTS_OF_A_FUNCTION</lang>
⚫
The following approach uses the Secant Method[http://en.wikipedia.org/wiki/Secant_method] to numerically find one root. Which root is found will depend on the start values x1 and x2 and if these are far from a root this method may not converge.
⚫
<lang fortran> INTEGER, PARAMETER :: dp = SELECTED_REAL_KIND(15)
⚫
INTEGER :: i=1, limit=100
REAL(dp) :: d, e, f, x, x1, x2
f(x) = x*x*x - 3.0_dp*x*x + 2.0_dp*x
f(x) = x*x*x - 3.0_dp*x*x + 2.0_dp*x
⚫
⚫
x1 = -1.0_dp ; x2 = 3.0_dp ; e = 1.0e-15_dp
⚫
x = -1.0_dp ; step = 1.0e-6_dp ; e = 1.0e-9_dp
⚫
DO
⚫
⚫
IF (i > limit) THEN
⚫
s = (f(x) > 0)
⚫
WRITE(*,*) "Function not converging"
EXIT
DO WHILE (x < 3.0)
⚫
value = f(x)
⚫
IF(ABS(value) < e) THEN
⚫
WRITE(*,"(A,F12.9)") "Root found at x =", x
⚫
s = .NOT. s
⚫
ELSE IF ((value > 0) .NEQV. s) THEN
⚫
WRITE(*,"(A,F12.9)") "Root found near x = ", x
⚫
s = .NOT. s
END IF
END IF
d = (x2 - x1) / (f(x2) - f(x1)) * f(x2)
x = x + step
⚫
END DO
⚫
IF (ABS(d) < e) THEN
⚫
⚫
WRITE(*,"(A,F18.15)") "Root found at x = ", x2
⚫
END PROGRAM ROOTS_OF_A_FUNCTION</lang>
⚫
EXIT
⚫
The following approach uses the Secant Method[http://en.wikipedia.org/wiki/Secant_method] to numerically find one root. Which root is found will depend on the start values x1 and x2 and if these are far from a root this method may not converge.
⚫
END IF
⚫
<lang fortran>INTEGER, PARAMETER :: dp = SELECTED_REAL_KIND(15)
⚫
x1 = x2
⚫
INTEGER :: i=1, limit=100
x2 = x2 - d
i = i + 1
REAL(dp) :: d, e, f, x, x1, x2
⚫
⚫
END DO</lang>
⚫
f(x) = x*x*x - 3.0_dp*x*x + 2.0_dp*x
⚫
x1 = -1.0_dp ; x2 = 3.0_dp ; e = 1.0e-15_dp
⚫
DO
⚫
IF (i > limit) THEN
⚫
WRITE(*,*) "Function not converging"
⚫
EXIT
⚫
END IF
d = (x2 - x1) / (f(x2) - f(x1)) * f(x2)
⚫
IF (ABS(d) < e) THEN
⚫
WRITE(*,"(A,F18.15)") "Root found at x = ", x2
⚫
EXIT
⚫
END IF
⚫
x1 = x2
⚫
x2 = x2 - d
⚫
i = i + 1
⚫
END DO</lang>




Line 367: Line 363:
J has builtin a root-finding operator, '''<tt>p.</tt>''', whose input is the (reversed) coeffiecients of the polynomial. Hence:
J has builtin a root-finding operator, '''<tt>p.</tt>''', whose input is the (reversed) coeffiecients of the polynomial. Hence:


1{::p. 0 2 _3 1
<lang j> 1{::p. 0 2 _3 1
2 1 0
2 1 0</lang>


We can determine whether the roots are exact or approximate by evaluating the polynomial at the candidate roots, and testing for zero:
We can determine whether the roots are exact or approximate by evaluating the polynomial at the candidate roots, and testing for zero:


(0=]p.1{::p.) 0 2 _3 1
<lang j> (0=]p.1{::p.) 0 2 _3 1
1 1 1
1 1 1</lang>


As you can see, <tt>p.</tt> is also the operator which evaluates polynomials. This is not a coincidence.
As you can see, <tt>p.</tt> is also the operator which evaluates polynomials. This is not a coincidence.
Line 399: Line 395:
=={{header|Maple}}==
=={{header|Maple}}==


f := x^3-3*x^2+2*x;
<lang maple>f := x^3-3*x^2+2*x;
roots(f,x);
roots(f,x);</lang>


outputs:
outputs:


[[0, 1], [1, 1], [2, 1]]
<lang maple>[[0, 1], [1, 1], [2, 1]]</lang>


which means there are three roots. Each root is named as a pair where the first element is the value (0, 1, and 2), the second one the multiplicity (=1 for each means none of the three are degenerate).
which means there are three roots. Each root is named as a pair where the first element is the value (0, 1, and 2), the second one the multiplicity (=1 for each means none of the three are degenerate).
Line 416: Line 412:
===Solve===
===Solve===
This requires a full equation and will perform symbolic operations only:
This requires a full equation and will perform symbolic operations only:
In[1]:= Solve[x^3-3*x^2+2*x==0,x]
<lang mathematica>In[1]:= Solve[x^3-3*x^2+2*x==0,x]
Out[1]= {{x->0},{x->1},{x->2}}
Out[1]= {{x->0},{x->1},{x->2}}</lang>


===NSolve===
===NSolve===
This requires merely the polynomial and will perform numerical operations if needed:
This requires merely the polynomial and will perform numerical operations if needed:
In[2]:= NSolve[x^3 - 3*x^2 + 2*x , x]
<lang mathematica>In[2]:= NSolve[x^3 - 3*x^2 + 2*x , x]
Out[2]= {{x->0.},{x->1.},{x->2.}}
Out[2]= {{x->0.},{x->1.},{x->2.}}</lang>
(note that the results here are floats)
(note that the results here are floats)


===FindRoot===
===FindRoot===
This will numerically try to find one(!) local root from a given starting point:
This will numerically try to find one(!) local root from a given starting point:
In[3]:= FindRoot[x^3 - 3*x^2 + 2*x , {x, 1.5}]
<lang mathematica>In[3]:= FindRoot[x^3 - 3*x^2 + 2*x , {x, 1.5}]
Out[3]= {x->0.}
Out[3]= {x->0.}
In[4]:= FindRoot[x^3 - 3*x^2 + 2*x , {x, 1.1}]
In[4]:= FindRoot[x^3 - 3*x^2 + 2*x , {x, 1.1}]
Out[4]= {x->1.}
Out[4]= {x->1.}</lang>
(note that there is no guarantee which one is found).
(note that there is no guarantee which one is found).


===FindInstance===
===FindInstance===
This finds a value (optionally out of a given domain) for the given variable (or a set of values for a set of given variables) that satisfy a given equality or inequality:
This finds a value (optionally out of a given domain) for the given variable (or a set of values for a set of given variables) that satisfy a given equality or inequality:
In[5]:= FindInstance[x^3 - 3*x^2 + 2*x == 0, x]
<lang mathematica>In[5]:= FindInstance[x^3 - 3*x^2 + 2*x == 0, x]
Out[5]= {{x->0}}
Out[5]= {{x->0}}</lang>


===Reduce===
===Reduce===
This will (symbolically) reduce a given expression to the simplest possible form, solving equations and performing substitutions in the process:
This will (symbolically) reduce a given expression to the simplest possible form, solving equations and performing substitutions in the process:
In[6]:= Reduce[x^3 - 3*x^2 + 2*x == 0, x]
<lang mathematica>In[6]:= Reduce[x^3 - 3*x^2 + 2*x == 0, x]
Out[6]= x==0||x==1||x==2
Out[6]= x==0||x==1||x==2</lang>
(note that this doesn't yield a "solution" but a different expression that expresses the same thing as the original)
(note that this doesn't yield a "solution" but a different expression that expresses the same thing as the original)


Line 448: Line 444:
A general root finder using the False Position (Regula Falsi) method, which will find all simple roots given a small step size.
A general root finder using the False Position (Regula Falsi) method, which will find all simple roots given a small step size.


<lang ocaml>
<lang ocaml>let bracket u v =
let bracket u v =
((u > 0.0) && (v < 0.0)) || ((u < 0.0) && (v > 0.0));;
((u > 0.0) && (v < 0.0)) || ((u < 0.0) && (v > 0.0));;


Line 481: Line 476:
x fx (if fx = 0.0 then "exact" else "approx") in
x fx (if fx = 0.0 then "exact" else "approx") in
let f x = ((x -. 3.0)*.x +. 2.0)*.x in
let f x = ((x -. 3.0)*.x +. 2.0)*.x in
List.iter showroot (search (-5.0) 5.0 0.1 f);;
List.iter showroot (search (-5.0) 5.0 0.1 f);;</lang>
</lang>


Output:
Output:
Retrieved from "https://rosettacode.org/wiki/Roots_of_a_function"