From: rusin@moriarty.math.niu.edu (Dave Rusin)
Newsgroups: sci.math.num-analysis
Subject: Re: Roots with rotation
Date: 2 Dec 1996 19:36:53 GMT
In article <32A03BAE.7E46@cenplus.com>,
Fred Siegeltuch wrote:
>Given:
>Two real continuous functions: f(x) and g(x), a rotation of g(x)about
>the origin, and a bounding rectangle {(Xl, Yl), (Xh, Yh)}.
>
>Find:
>The all intersections of f and rotated g within the bounding rectangle.
>
>I need this problem solved (approximately) for a piece of educational
>software I am trying to write. Any suggestions appreciated.
I hope the educational software helps teach the difference between a
function and its graph. I assume you are rotating the latter.
The graph of g is the set of points of the form { (x,y): y=g(x) }.
If you rotate a point (x,y) counterclockwise through an angle of theta,
you end at the point (x cos(theta) - y sin(theta), x sin(theta)+y cos(theta) );
equivalently, the coordinates of the original point may be recovered from
the coordinates of the new point, (x',y') as
x= x' cos(theta) + y' sin(theta)
y= -x' sin(theta) + y' cos(theta).
so that a point (x', y') is in the rotated graph iff the (x,y) so
described is in the original graph, that is, iff
-x' sin(theta) + y' cos(theta) = g( x' cos(theta) + y' sin(theta) ).
This point is in the intersection of (the rotated graph of g) and
(the graph of f) iff it satisfies both the above condition and the
condition y' = f(x'). In particular, you can find the y-coordinates
of such points easily from the x-coordinates, and those x-coordinates
are the solutions of
-x sin(theta) + f(x) cos(theta) = g( x cos(theta) + f(x) sin(theta) ).
Now, your ability to solve such an equation depends on the type of
functions f and g are. If both are polynomial, then the above is
a polynomial equation (of degree equal to deg(f)*deg(g) ), and so has
at most a finite number of solutions; the graphs meet only finitely
many times, for any fixed theta. Other functions likely to be
of interest in elementary educational software will also lead to only
finitely many intersections within a compact set, although of course
a function like f(x)=sin(1/x) will allow for infinitely many
functions near the origin.
You can adapt the discussion above to curves defined implicitly
(rotated curves occur frequently in the context of conic sections, for
example). Then the intersection of (the solution set of f(x,y)=0) and
(the rotation of the solution set to g(x,y)=0) may be computed by solving
two equations in two unknowns, which is perhaps best accomplished via
Newton's method (viewing F=(f,g) as a single function F: R^2 -> R^2),
although if e.g. F is a polynomial map of low degree one may use
resultants to reduce this to a one-variable problem.
It would be embarassing to release educational software which did not
screen its allowed input to prohibit a user from trying functions for
which the algorithms encoded within do not work well. Rotating the graph
of y=x^100 by theta=0.01 and asking for its intersection with
y=x^99 will require careful treatment.
dave
==============================================================================
[So I wrote some notes to myself but never sent them... -- djr]
==============================================================================
(Sigh) Why do I do this?
Query: where does the graph of y=x^99 cross that of y=x^100 if the latter
is rotated through an angle of theta?
Relevant equation is seen to be: either x=0 or
98 99 98 100
f(x): = c x - x (s x + c) - s = 0
where s=sin(theta), c=cos(theta).
Clearly one solution is at x=0. Are there others? (i.e., roots of f?
After all, it's only a 9899-degree polynomial...)
Since this is an odd-degree polynomial with negative lead coeff and
negative value at 0 [assuming 0 < theta < pi here], there's at least
one negative root x. For example, when theta=0.01, there's one
at -0.947627044545. Others still?
Well, let's look at slope. Deriv of f is x^97*following:
98 100 99 98 99
(der) 98 c - 99 x (s x + c) - 9800 x (s x + c) s
This in turn has a derivative equal to
100 2 98 2 4 2
- 99 c (t Y + 1) (980001 Y t + 19602 t Y + 1)
where t=tan(theta) and Y=x^98/tan(theta). Solving for t^2Y in the
quadratic shows no real roots, so this 2nd deriv is negative for all
real Y (no matter what theta), i.e., the 1st deriv factor "der" is
decreasing for all x.
Thus the only critical points of f occur at x=0 and at the one value of
x making (der)=0. Rewriting der as
99
- x (s X + c) (9899 s X + 99 c) + 98 c
with X=x^98 shows that the critical point occurs where x=
c
98 -----------------------------
99
(s X + c) (9899 s X + 99 c)
Since the function f may be written
100
c X - X x (s X + c) - s,
when this condition holds f equals
2 2
c (9801 X t + X - 9899 t X - 99 t)
------------------------------------
9899 t X + 99
So we can see that f has only the one (negative) root or three
according as this relative maximum value of f is positive or not.
(For some t it is, for others it isn't).
The borderline cases would be those for which this extreme value of f
is exactly zero. If this happens, we can solve for X to get
2 2 4 1/2
- 1 + 9899 t +- (1 + 3861398 t + 97990201 t )
1/19602 -------------------------------------------------
t
Comparing to the condition relating x and X shows x must be
166442626947036914196392708547441272754174391385070720783418386394246498487848\
144489532867529310267931330402683286369274634556991752057008774985379841708812\
921998679540467222357937444992535070018680969095217346220353265330397418711625\
461039462920736899162011747125187489437575855756435085186703913184717559452671\
494033145104448613835321011109264966478953167255668416545268488793737652476590\
669432783679150171789366044832033929166848
/ 99 2 2 4 1/2 99
/ c (19601 + 9899 t + (1 + 3861398 t + 97990201 t ) )
/
2 2 4 1/2
(1930699 + 97990201 t + 9899 (1 + 3861398 t + 97990201 t ) )
At the same time, its 98th power should equal the
above X. This gives an equation to solve for t. I get a root near
theta=.00127, giving t=.0012700007, x=0.9730323 and X=.068623.
It appears pictorially that this is the only root: increase theta, and
the "bend" in x^100 is too high to touch x^99; decrease it, and the
"bend" sinks lower, forcing the point of intersection towards x=1
(when theta=0) and beyond (as theta decreases).