Intermediate Value Theorem

[mr_e_man]

Suppose f is a continuous function on the real number line, and f(x) is positive at one end of an interval, and f(x) is negative at the other end. Then the IVT says f(x) = 0 somewhere in that interval.
More generally, f(x) reaches all values between f(a) and f(b) (and possibly other values) as x varies in the interval a ≤ x ≤ b.


For example, taking f(x) = x^2 - 5, we find f(2) = -1, and f(3) = +4; then the theorem says x^2 - 5 = 0 for some x between 2 and 3. This proves that √5 exists (in the system of "real numbers").

Or consider the sine function: sin(3) = +0.14, and sin(4) = -0.76, so there must be some x between 3 and 4 such that sin(x) = 0. This is one possible definition of π.
Of course we also have sin(-4) = +0.76 and sin(4) = -0.76, so the theorem says there's at least one x between -4 and 4 such that sin(x) = 0, but it doesn't say there's exactly one such x.
Also, notice that sin(2) = 0.91 is not between 0.76 and -0.76, even though 2 is between -4 and 4. This is one of those "possible other values" allowed by the theorem.

The function doesn't need to be smooth. The IVT applies as well to |x|, or weird functions like Cantor's or Weierstrass's, which are continuous but not smooth.

In this context, "continuous" means that small changes in the input, x, can produce only small changes in the output, f(x).
More precisely, it means that, for any reasonable definition of "small" in the output space (the y axis, if you graph y=f(x) in 2D), there is another reasonable definition of "small" in the input space (the x axis), such that any small change in the input produces a small (or zero) change in the output.
Still more precisely, see the epsilon-delta definition of continuity.

A discontinuous function may or may not have the intermediate value property. For example, the floor function has ⌊0⌋ = 0 and ⌊1⌋ = 1, but there is no x between 0 and 1 such that ⌊x⌋ = 0.5. On the other hand, though the following function is discontinuous, it does have the intermediate value property:

f(x) = {
0, if x = 0
(1/x)*sin(100/x), if x ≠ 0
}

(Graph this function on WolframAlpha or Desmos or whatever.)


Here's an illustration of the IVT, for f(x) = x^2 - 5 on the interval -2 ≤ x ≤ 4. Instead of a 2D graph, I'll show the input and the output separately in 1D spaces.

IVT 1.png (6.37 KiB) Viewed 190 times

[mr_e_man]

Of course we will talk about higher dimensions.

Just as the 1-dimensional IVT guarantees a solution to 1 equation in 1 variable, there are generalizations that guarantee a solution to a system of n equations in n variables. (There's a 3Blue1Brown video about the 2D case.)

Suppose F is a collection of n continuous functions of n real variables, or equivalently, F is a continuous function from n-dimensional space to n-dimensional space. We'll focus on what F does to a rectangular box. Given some information about what F does to the faces of the box, we want to know if F(x) = 0 for some point x inside the box.

First, let's see what can go wrong when trying to generalize the IVT.
It isn't enough to know what F does to the vertices of the box.
It isn't enough to know that each face of the box, after F is applied, intersects the corresponding axis in the output space.
It isn't enough to know that the faces, after F is applied, completely surround 0 in the output space.
This information doesn't ensure that 0 is in the output.

IVT 2.png (26.91 KiB) Viewed 189 times

Now, let's see what can go right!
It is enough to know that each face of the box, after F is applied, is in the corresponding half-space in the output space. This is the Poincare-Miranda theorem.

IVT 3.png (21 KiB) Viewed 189 times

More generally, if there's a box in the output space, such that each face of the input box, after F is applied, is in the exterior half-space defined by the corresponding face of the other box --
That wording is too difficult. Let me use symbols.

Denote the input box A, and its faces A₁⁻, A₁⁺, A₂⁻, A₂⁺, ... , A_n⁻, A_n⁺. For each index i, the face A_i⁻ has a constant i'th coordinate; call it a_i⁻. The face A_i⁺ also has a constant i'th coordinate; call it a_i⁺. We have a_i⁻ ≤ x_i ≤ a_i⁺, for each index i, for each point x in A.
Suppose we can find a box B in the output space, with the following property. (Denote the faces B_i⁻, B_i⁺, and the coordinates b_i⁻, b_i⁺, like we did for A.) For each index i, for each point x in the face A_i⁻, letting y = F(x), we have y_i ≤ b_i⁻. And for each point x in the face A_i⁺, letting y = F(x), we have y_i ≥ b_i⁺.
Then the Poincare-Miranda theorem says that F(A) contains B. In other words, for any point y in B, there is at least one point x in A such that F(x) = y.

IVT 4.png (21.35 KiB) Viewed 189 times

And this is relatively easy to compute (e.g. we don't need to use derivatives or integrals or algebraic topology). We can evaluate F(A₁⁻) using interval arithmetic, to get a box C containing F(A₁⁻), and then take b₁⁻ = c₁⁺, and do similarly for all the other faces of A, to construct the box B.

IVT 5.png (30.94 KiB) Viewed 189 times

(In the image, the blue box on the left is A, the blue blob on the right is F(A) which we want to compute, the four overlapping red boxes are given by interval arithmetic, and the green box is B which is the part of F(A) guaranteed by Poincare-Miranda. The loops and wrinkles are there to remind you that F doesn't need to be invertible.)

[mr_e_man]

For a while, it seemed to me that Poincare-Miranda was too specific to be useful. The transformed box isn't likely to have the right orientation; two opposite faces may not be separated by any (hyper)plane aligned with the coordinate axes, so the theorem can't be applied.

IVT 6.png (8.28 KiB) Viewed 188 times

But recently I gave it a second thought. Of course there's a simple fix: a linear transformation!

Assuming F is differentiable, you could take this to be the inverse of the Jacobian matrix.
Not assuming F is differentiable, you could evaluate F at a vertex of the box and at the n adjacent vertices, or maybe at the midpoints of faces instead. Then subtract the output points to get n vectors, arrange these to form a matrix, and take its inverse.

After applying Poincare-Miranda, and undoing the linear transformation, we'd get a parallelotope guaranteed to be part of the output of F.

IVT 7.png (26.22 KiB) Viewed 188 times

This still may not work in some cases. Two opposite faces of the output may not be separated by any (hyper)plane.

Part of the problem is curvature. One face could be cupped inside another face (without touching it). To mitigate the effects of curvature, assuming F is smooth, you could divide the input box into smaller boxes, and try to apply Poincare-Miranda to each of them individually.

Or the output could be sub-dimensional, confined to a (hyper)surface. Then there's no chance of finding an n-dimensional box contained in the output, and little chance of the output containing 0, and even if 0 is there, we may not be able to prove it.