Steffensen's method: Difference between revisions
no edit summary
No edit summary |
|||
Line 44:
The function <code>steffensen_aitken</code> will find a fixed point for us, but how can we use that to find a root? In particular, suppose one wants to find <math>t</math> such that <math>g(t) = 0</math>. Then what one can do (and what we will try to do) is find a fixed point <math>p</math> of <math>f(t) = g(t) + t</math>. For then <math>p = f(p) = g(p) + p</math>, and therefore <math>g(p) = 0</math>.
===The problem we wish to solve===
Suppose we have two quadratic planar [[wp:Bézier_curve|Bézier curves]], with control points <math>(-1,0), (0,10), (1,0)</math> and <math>(2,1), (-8,2), (2,3)</math>, respectively. These two parabolas are shown in the following figure. As you can see, they intersect at four points.
::[[File:Steffensen's method Figure-1.png|none|alt=Two parabolas in the plane that intersect at four points, plus their Bézier control polygons.]]
We want to try to find the points of intersection.
The method we will use is ''implicitization''. In this method, one first rewrites one of the curves as an [[wp:Implicit_function|implicit equation]] in <math>x</math> and <math>y</math>. For this we will use the parabola that is convex upwards: it has implicit equation <math>5x^2 + y - 5 = 0</math>. Then what one does is plug the parametric equations of the ''other'' curve into the implicit equation. This gives <math>5(x(t))^2 + y(t) - 5 = 0</math>, where <math>t</math> is the independent parameter for the curve that is convex ''leftwards''. After expansion, this will be a degree-4 equation in <math>t</math>. Find its four roots and you have found the points of intersection of the two curves.
That is easier said than done.
| |||