Peeter Joot's (OLD) Blog.

Math, physics, perl, and programming obscurity.

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.

Refining an approximate horizontal intersection.

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 x_1, which is given by the tangent

\begin{aligned}\frac{f(x_0) - b}{x_0 - x_1} = f'(x_0).\end{aligned} \hspace{\stretch{1}}(2.1)

Rearranging and solving for x_1, we have

\begin{aligned}x_1 = x_0 - \frac{f(x_0) - b}{f'(x_0)}\end{aligned} \hspace{\stretch{1}}(2.2)

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.

Refining an approximation for the intersection with an arbitrarily oriented 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

\begin{aligned}\mathbf{r}(x) = x \mathbf{e}_1 + f(x) \mathbf{e}_2,\end{aligned} \hspace{\stretch{1}}(3.3)

for which the tangent direction vector is

\begin{aligned}\mathbf{t}(x) = \frac{d\mathbf{r}}{dx} = \mathbf{e}_1 + f'(x) \mathbf{e}_2.\end{aligned} \hspace{\stretch{1}}(3.4)

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

\begin{aligned}(x_0, f(x)) + \alpha \mathbf{t}(x_0).\end{aligned} \hspace{\stretch{1}}(3.5)

For the line to intersect this, suppose we have one point on the line \mathbf{p}_0, and a direction vector for that line \hat{\mathbf{u}}. The points on this line are therefore all the endpoints of

\begin{aligned}\mathbf{p}_0 + \beta \hat{\mathbf{u}}.\end{aligned} \hspace{\stretch{1}}(3.6)

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

\begin{aligned}(x_0, f(x_0)) + \alpha \mathbf{t}(x_0) = \mathbf{p}_0 + \beta \hat{\mathbf{u}}.\end{aligned} \hspace{\stretch{1}}(3.7)

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

\begin{aligned}\left((x_0, f(x_0)) -\mathbf{p}_0 \right) \wedge \mathbf{t}(x_0) = \beta \hat{\mathbf{u}} \wedge \mathbf{t}(x_0).\end{aligned} \hspace{\stretch{1}}(3.8)

If the lines are not parallel, then both sides are scalar multiples of \mathbf{e}_1 \wedge \mathbf{e}_2, and dividing out one gets

\begin{aligned}\beta = \frac{\left((x_0, f(x_0)) -\mathbf{p}_0 \right) \wedge \mathbf{t}(x_0)}{\hat{\mathbf{u}} \wedge \mathbf{t}(x_0)}.\end{aligned} \hspace{\stretch{1}}(3.9)

Writing out \mathbf{t}(x_0) = \mathbf{e}_1 + f'(x_0) \mathbf{e}_2, explicitly, this is

\begin{aligned}\beta = \frac{\left((x_0, f(x_0)) -\mathbf{p}_0 \right) \wedge \left(\mathbf{e}_1 + f'(x_0) \mathbf{e}_2\right)}{\hat{\mathbf{u}} \wedge \left(\mathbf{e}_1 + f'(x_0) \mathbf{e}_2\right)}.\end{aligned} \hspace{\stretch{1}}(3.10)

Further, dividing out the common \mathbf{e}_1 \wedge \mathbf{e}_2 bivector, we have a ratio of determinants

\begin{aligned}\beta = \frac{\begin{vmatrix}x_0 -\mathbf{p}_0 \cdot \mathbf{e}_1 & f(x_0) - \mathbf{p}_0 \cdot \mathbf{e}_2 \\ 1 & f'(x_0) \\ \end{vmatrix}}{\begin{vmatrix}\hat{\mathbf{u}} \cdot \mathbf{e}_1 & \hat{\mathbf{u}} \cdot \mathbf{e}_2 \\ 1 & f'(x_0) \\ \end{vmatrix}}.\end{aligned} \hspace{\stretch{1}}(3.11)

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

\begin{aligned}\mathbf{p}_0 + \beta \hat{\mathbf{u}},\end{aligned} \hspace{\stretch{1}}(3.12)

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

\begin{aligned}x_1 = \mathbf{p}_0 \cdot \mathbf{e}_1 + (\hat{\mathbf{u}} \cdot \mathbf{e}_1)\frac{\begin{vmatrix}x_0 -\mathbf{p}_0 \cdot \mathbf{e}_1 & f(x_0) - \mathbf{p}_0 \cdot \mathbf{e}_2 \\ 1 & f'(x_0) \\ \end{vmatrix}}{\begin{vmatrix}\hat{\mathbf{u}} \cdot \mathbf{e}_1 & \hat{\mathbf{u}} \cdot \mathbf{e}_2 \\ 1 & f'(x_0) \\ \end{vmatrix}}.\end{aligned} \hspace{\stretch{1}}(3.13)

This looks a whole lot different than the original x_1 for the horizontal from back at 2.2, but substitution of \hat{\mathbf{u}} = \mathbf{e}_1, and \mathbf{p}_0 = b \mathbf{e}_2, 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})

Refining an approximation for the intersection of two curves in a plane.

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

\begin{aligned}\mathbf{s}(x) &= x \mathbf{e}_1 + s(x) \mathbf{e}_2 \\ \mathbf{r}(x) &= x \mathbf{e}_1 + r(x) \mathbf{e}_2.\end{aligned} \hspace{\stretch{1}}(4.14)

Tangent direction vectors at the point x_0 are then

\begin{aligned}\mathbf{s}'(x_0) &= \mathbf{e}_1 + s'(x_0) \mathbf{e}_2 \\ \mathbf{r}'(x_0) &= \mathbf{e}_1 + r'(x_0) \mathbf{e}_2.\end{aligned} \hspace{\stretch{1}}(4.16)

The intersection of interest is therefore the solution of

\begin{aligned}(x_0, s(x_0)) + \alpha \mathbf{s}' = (x_0, r(x_0)) + \beta \mathbf{r}'.\end{aligned} \hspace{\stretch{1}}(4.18)

Wedging with one of tangent vectors \mathbf{s}' or \mathbf{r}' provides our solution. Solving for \alpha this is

\begin{aligned}\alpha = \frac{(0, r(x_0) - s(x_0)) \wedge \mathbf{r}'}{\mathbf{s}' \wedge \mathbf{r}'} = \frac{\begin{vmatrix}0 & r(x_0) - s(x_0) \\ \mathbf{r}' \cdot \mathbf{e}_1 & \mathbf{r}' \cdot \mathbf{e}_2 \end{vmatrix}}{\begin{vmatrix}\mathbf{s}' \cdot \mathbf{e}_1 & \mathbf{s}' \cdot \mathbf{e}_2 \\ \mathbf{r}' \cdot \mathbf{e}_1 & \mathbf{r}' \cdot \mathbf{e}_2 \end{vmatrix}}= -\frac{r(x_0) - s(x_0)}{r'(x_0) - s'(x_0) }.\end{aligned} \hspace{\stretch{1}}(4.19)

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

\begin{aligned}x_1 = x_0 -\frac{r(x_0) - s(x_0)}{r'(x_0) - s'(x_0) }.\end{aligned} \hspace{\stretch{1}}(4.20)

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 r(x) = f(x), and s(x) = b, 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: