## Newton’s method for intersection of curves in a plane.

Posted by peeterjoot on March 7, 2010

[Click here for a PDF of this post with nicer formatting]Note that this PDF file is formatted in a wide-for-screen layout that is probably not good for printing.

# Motivation.

Reading the blog post Problem solving, artificial intelligence and computational linear algebra some variations of Newton’s method for finding local minumums and maximums are given.

While I’d seen the Hessian matrix eons ago in the context of back propagation feedback methods, Newton’s method itself I remember as a first order root finding method. Here I refresh my memory what that simpler Newton’s method was about, and build on that slightly to find the form of the solution for the intersection of an arbitrarily oriented line with a curve, and finally the problem of refining an approximation for the intersection of two curves using the same technique.

# Root finding as the intersection with a horizontal.

The essence of Newton’s method for finding roots is following the tangent from the point of first guess down to the line that one wants to intersect with the curve. This is illustrated in figure (\ref{fig:newtonsIntersectionHorizontal}).

Algebraically, the problem is that of finding the point , which is given by the tangent

Rearranging and solving for , we have

If one presumes convergence, something not guarenteed, then a first guess, if good enough, will get closer and closer to the target with each iteration. If this first guess is far from the target, following the tangent line could ping pong you to some other part of the curve, and it is possible not to find the root, or to find some other one.

# Intersection with a line.

The above pictorial treatment works nicely for the intersection of a horizontal line with a curve. Now consider the intersection of an arbitrarily oriented line with a curve, as illustrated in figure (\ref{fig:newtonsIntersectionAnyOrientation}). Here it is useful to setup the problem algebraically from the begining. Our problem is really still just that of finding the intersection of two lines. The curve itself can be considered the set of end points of the vector

for which the tangent direction vector is

The set of points on this tangent, taken at the point , can also be written as a vector, namely

For the line to intersect this, suppose we have one point on the line , and a direction vector for that line . The points on this line are therefore all the endpoints of

Provided that the tangent and the line of intersection do in fact intersect then our problem becomes finding or after equating 3.5 and 3.6. This is the solution of

Since we don’t care which of or we solve for, setting this up as a matrix equation in two variables isn’t the best approach. Instead we wedge both sides with (or ), essentially using Cramer’s method. This gives

If the lines are not parallel, then both sides are scalar multiples of , and dividing out one gets

Writing out , explicitly, this is

Further, dividing out the common bivector, we have a ratio of determinants

The final step in the solution is noting that the point of intersection is just

and in particular, the coordinate of this is the desired result of one step of iteration

This looks a whole lot different than the original for the horizontal from back at 2.2, but substitution of , and , shows that these are identical.

# Intersection of two curves.

Can we generalize this any further? It seems reasonable that we would be able to use this Newton’s method technique of following the tangent to refine an approximation for the intersection point of two general curves. This is not expected to be much harder, and the geometric idea is illustrated in figure (\ref{fig:newtonsIntersectionTwoCurves})

The task at hand is to setup this problem algebraically. Suppose the two curves , and are parameterized as vectors

Tangent direction vectors at the point are then

The intersection of interest is therefore the solution of

Wedging with one of tangent vectors or provides our solution. Solving for this is

To finish things off, we just have to calculate the new coordinate on the line for this value of , which gives us

It is ironic that generalizing things to two curves leads to a tidier result than the more specific line and curve result from 3.13. With a substitution of , and , we once again recover the result 2.2, for the horizontal line intersecting a curve.

# Followup.

Having completed the play that I set out to do, the next logical step would be to try the min/max problem that leads to the Hessian. That can be for another day.

## Leave a Reply