Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$y_1=ax^2 + bx + c$

$y_2=dx^2 + ex + f$

Question: what is the proper way for me to test that $y_1 > y_2$ over an interval (say 0 to 10, inclusive) for all numbers in that interval?

I assume it has something to do with testing the integral of y1 - y2, but not sure.

=== Added some context ===

I'm working on a continuous game theory program written in Python, and am working on the concept of strict domination. $y1$ and $y2$ are meant to be the utility functions for a given agent. $y1$ strictly dominates $y2$ if, over the range of other player actions in question (i.e. the interval of $x$), $y1>y2$.

share|improve this question
3  
What methods are at your disposal and what level of rigor are you after? For example, if you have $y_1$ and $y_2$, why not just plot them both? Or plot the difference $y_1-y_2$ and see where that's positive? Basically, you are wanting to solve the quadratic inequality $(a-d)x^2+(b-e)x+(c-f)>0$, so it's really just an algebra problem. –  JohnD Jan 8 '13 at 20:27
1  
Also, are you wanting to test the truthfulness of the inequality at certain $x$ values or are you wanting to find all $x$ values for which the inequality is true? –  JohnD Jan 8 '13 at 20:30
add comment

4 Answers

up vote 8 down vote accepted

Solve $ y_{1} = y_{2} $ and then use the solutions (if there are any) to construct the sign diagram of $ y_{1} - y_{2} $ over the interval.

Having $ \displaystyle \int_{a}^{b} (y_{1} - y_{2}) \,d{x} > 0 $ is a necessary condition for $ y_{1} > y_{2} $ over the interval $ [a,b] $, but definitely not sufficient.

share|improve this answer
add comment

While Haskell Curry's answer gives a mathematical solution to the problem, I thought I would offer a more programmer-oriented solution; in particular, it's worth noting that the problem can be solved without ever calculating a square root.

First of all, as already noted, your question is equivalent to considering the function $f(x) = y_1(x)-y_2(x) =Ax^2+Bx+C$ (with $A=a-d$, etc.) and testing whether $f(x) \gt 0$ over an interval $x\in [x_1, x_2]$; I'll use this formulation of the problem.

Next, consider the vertex of the parabola $(x,f(x))$; that is, the point $x_0=-B/2A$ that represents the axis of symmetry of the function $f$. ($f$ can be written as $f(x) = A(x-x_0)^2+M$ for some constant $M$ and this is in fact the genesis of the quadratic formula, but that's irrelevant to the problem at hand). If $x_0$ isn't in the interval $[x_1, x_2]$ (and note that this also covers the degenerate case where $A=0$, i.e. where there is no vertex) then the function $f$ must be either strictly increasing or strictly decreasing over that range; this means that we can just look at the signs of $f(x_1)$ and $f(x_2)$ and be sure that if both are positive, then $f$ is positive over the whole range.

On the other hand, if $x_0$ is within the interval, then $f$ takes on either a maximum or a minimum there (depending on the sign of $A$), and this means that $f(x)$ will be strictly increasing on one of the two intervals $[x_1, x_0]$ or $[x_0, x_2]$ and strictly decreasing on the other. Here, we can just look at the sign of $f(x)$ at all three points $x=x_0$, $x=x_1$ and $x=x_2$; if any of them are negative then obviously $f$ is negative at some point in the interval, but if all three are positive then by the 'bitonicity' of $f$ we know that it must be positive within the entirety of the interval. This gives us the following (pseudocode) function:

bool PositiveOnRange(Quadratic f, float x1, float x2)
{
  if (f.evalAt(x1) <= 0) return false; // negative at one end of the range
  if (f.evalAt(x2) <= 0) return false; // negative at the other end
  if ( f.A == 0 ) return true; // not actually quadratic
  float x0 = -f.B/(2.0*f.A);
  if ( (x0 < x1) || (x0 > x2) ) return true; // vertex not in range
  return ( f.evalAt(x0) > 0 ); // sign at vertex
}

For functions that aren't as simple as quadratics, the most straightforward approach might be a combination of subdivision and interval arithmetic; essentially, when evaluating a function (it works particularly well for polynomials, but note that exponentials and arbitrary monotonic functions are well-behaved for interval arithmetic too), rather than evaluating it at a point evaluate it 'at' an interval. Intervals can be added and multiplied with simple rules, and any monotonic function $f(x)$ evaluated at an interval $I=[a, b]$ yields the (possibly mis-ordered) interval $f(\!(I)\!) = [f(a), f(b)]$. Interval arithmetic isn't necessarily strict - for an arbitrary function $f$, if we compute $f(\!(I)\!) = J = [J_l, J_r]$ then it doesn't necessarily mean that every value $J_l\lt y\lt J_r$ will be $f(x)$ for some $x\in I$ - but it is conservative, in the sense that if $f(\!(I)\!) = J$, then for every $x\in I$ we have $f(x)\in J$.

Using interval arithmetic, the problem can then be solved with a divide-and-conquer algorithm: start with the interval $I=[x_L, x_R]$ you want to confirm $f()\gt 0$ on. Start by evaluating $f(x_L)$ and $f(x_R)$ to make sure that your endpoints are both positive. Assuming that passes, compute $f(\!(I)\!)$ and test to see whether it contains 0. If not, then you're done; you know that your function must be positive on the interval. If it does contain $0$, on the other hand, then evaluate $f$ at the midpoint $x_M = \frac{(x_L+x_R)}{2}$. Again, if this fails then you're done; if it succeeds, then consider the two intervals $I_L = [x_L, x_M]$ and $I_R = [x_M, x_R]$. You can evaluate $f(\!(I_L)\!)$ to see if it contains 0 (and recurse down until you either fail or finally start getting intervals that are 'good'), and do the same with $f(\!(I_R)\!)$. This gives the following pseudocode (which should probably be converted to use an explicit stack of intervals rather than recursion and of course needs some sanity-checks to keep from recursing infinitely, but those are programming details):

bool PositiveOnRange(Function f, float xL, float xR)
{
  // we presume that xL and xR have already been tested and confirmed positive.
  Interval testInterval = f.evalOnInterval(Interval(xL, xR));
  if ( !(testInterval.Contains(0)) ) return true;
  float xM = 0.5*(xL+xR);
  if ( f.evalAt(xM) < 0 ) return false;
  return (PositiveOnRange(f, xL, xM) && PositiveOnRange(f, xM, xR));
}
share|improve this answer
add comment

It depends on what you mean by "$y_1>y_2$ over an interval" ...

The wording of your question seems to suggest you may want something like $$ \int_a^b w(x)(y_1(x)-y_2(x))\, \mathrm{d}x > 0 $$ meaning that some weighted sum of the polynomials favours $y_1$ over $y_2$ over the interval.

Other notions of $>$ could be something like

$$ \mathrm{max}_{x\in[a,b]}\ y_1 > \mathrm{max}_{x\in[a,b]}\ y_2 $$

Or perhaps

$$ y_1>y_2\ \forall x\in[a,b] $$

Or even as JohnD commented, you may just be interested in one or all values of $x$ for which $y_1>y_2$.

There are different situations where you could use each of those (other possibilities exist too), you just need to be clear on what it is that you need for $>$.

share|improve this answer
add comment

One method is to check the first point, so in this case, check $y_1(0)\geq y_2(0)$. Then consider the derivatives and verify that $y_1'(x)\geq y_2'(x)$ for all $x\in[0,10]$.

share|improve this answer
1  
Surely this condition is sufficient but not necessary? For example, $y_1=20-x$ and $y_2=x$ fail your condition, but $y_1\ge y_2$ for $1\le x\le 10$. –  user108903 Jan 8 '13 at 20:32
1  
This is an extremely strong condition. It is also not a necessary condition. –  Calvin Lin Jan 8 '13 at 20:32
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.