I have some code that outputs two arrays that contain x-values and y-values. I now need to root-find using these points, but is this possible without knowing the function? How does one implement, say, the bisection method using only a set of (x, y) pairs (no function f(x))? All of the examples that I'm finding online show the bisection method being used with a predefined polynomial function. Do I need to first find an approximate function in order to use the bisection method?
Asked
Active
Viewed 271 times
2
loltospoon
- 239
- 1
- 9
-
5You could fit a curve to the points and get roots from that. What do roots mean here? All you need to do is look for consecutive points with alternating signs for the y-component, then do a linear interpolation to figure out the x where y = 0 between them. You're doing too much searching and not enough thinking. – duffymo Mar 17 '17 at 01:04
1 Answers
0
I assume by root you mean point with y=0.0
find 2 consequent points (x0,y0),(x1,y1) such that y0*y1<=0.0 that means they are crossing zero so root is somewhere between them so take n points around this place and form polynomial (interpolation or BEZIER or whatever) and then use bisection or any other method.
For starters you can use linear interpolation so just solve this:
x(t) = x0 + (x1-x0).t // parametric line x
y(t) = y0 + (y1-y0).t // parametric line y
y(t) = 0.0 // root y
x(t) = ? // root x
---------------------
0.0 = y0 + (y1-y0).t
t = -y0/(y1-y0)
---------------------
x(t) = x0 + (x1-x0).t
x(t) = x0 + -y0/((y1-y0).(x1-x0)) // this is your approximate root
You may want to look at:
Also handle special cases when y0 or y1 are zero. That means they are the root and you do not need to interpolate. If they are both zero then you got infinite number of roots in-between them
