Good morrow cousin! Perhaps you're feeling good about yourself this fine day. Well that will be just about enough of that. For I have an equation for you to solve:
y = x − sin(x)
No, I don't give you x and ask for y -- that would be too easy. You do the other thing.
Suppose y = 1. Solve for x.
This is one time where you should give up. If you were thinking about some clever algebraic manipulation, arcsines and inverses and what all else, good luck with that. All the sources I can find (see Footnote) assure me this equation has no closed-form solution.
If we can't solve this equation, then how do we solve it?
Footnote: This isn't just a random equation some crazy person invented. It's Kepler's equation, give or take a parameter or two. It appears when trying to figure out where a planet is currently located in orbit, which, yes, is something people do. The point presently is its pedigree means the equation has been thrashed by many big brain types over the years, which is how we know it has no closed-form solution.
This is an example of a transcendental equation. A beasty solved usually by, well, guessing. Call it what you will. Iteration. Perturbation. Hail Mary mathematics. It all means the same thing. That being said, Kepler's equation provides an interesting lesson in thinking about solutions. A chance to work on your equation fu. The first thing we should ask is whether a solution exists. If the answer is no, then we can stop now.
Does a solution exist? That depends on the behavior of the RHS, which I'm going to call f(x) so I can refer to it. If f(x) is bounded or discontinuous, there might be trouble. If, say, f(x) is never bigger than 1, then f(x) = 2 has no solution. Or, if f(x) can't be negative, then f(x) = −1 has no solution. Or if it skips over values here and there. We need to crawl around in its pelt for a bit.
We know that | sin(x) | ≤ 1, so f(x) is never smaller than x − 1 and never larger than x + 1, But since x can be anything, we can conclude f(x) is not bounded. So far so good. Furthermore f(x) is continuous because it is the difference of two continuous functions -- x and sin(x) -- and there's a famous theorem that says the difference of two continuous functions is continuous. Ergo, by applying the Intermediate Value Theorem, we can safely conclude f(x) can take on any value in (−∞, +∞).
We have a hunting license -- no matter what y is, there exists an x such that y = x − sin(x). But a hunting license is different than actually bagging a bambi. How to proceed?
Note dy/dx = 1 − cos(x), which is nonnegative, so f(x) is nondecreasing, i.e., if x1 < x2 then f(x1) ≤ f(x2). A plan of attack suggests itself: 1) Guess an x, 2) if f(x) < y, increase x until f(x) > y. If f(x) > y, decrease x until f(x) < y. This gets us in the ballpark of the answer, bracketing the solution between the last two guesses, one on either side. We then repeat the process taking smaller steps until we're happy with the precision. There are more sophisticated techniques for this solving these kinds of equations, but the bracketing method as it is called will suffice for our needs.
We begin by moving everything to the LHS, so we really look for solutions of y − x + sin(x) = 0, where y is given. This because when we bracket zero the current guess and the previous guess will be of opposite sign, which is easy to check by testing if their product is negative. Everything else is just code. I whipped this up in Javascript:
---
And there's the solution. I can't add anything the code doesn't say already. There's nothing here in the way of abstract concepts or grand theorems. We pretty much just hound the solution to exhaustion using our machine savants. One day, I suspect, those machines will turn on us, but that day is not today.
Postscript
Crikey. Look at the sweat and tears this tiny speck of an equation caused us (if you are not sweating, imagine solving this equation by hand). You expect tigers or sharks to be dangerous. But this? It's like one of those poison dart frogs of the Amazon rainforest. A happy rainbow livery and neurotoxinous enough to kill you with a burp.
I don't know about you, but to me it's unnerving something so simple looking can be such a pain in the fur. You're prepared for Fourier transforms or Stoke's equations or whatever to ruin your day. But then some little equation shows up and makes a mockery of your problem solving skills, just when you were starting to feel good about yourself. If that's not a perfect metaphor for life, I don't know what is.
y = x − sin(x)
No, I don't give you x and ask for y -- that would be too easy. You do the other thing.
Suppose y = 1. Solve for x.
This is one time where you should give up. If you were thinking about some clever algebraic manipulation, arcsines and inverses and what all else, good luck with that. All the sources I can find (see Footnote) assure me this equation has no closed-form solution.
If we can't solve this equation, then how do we solve it?
Footnote: This isn't just a random equation some crazy person invented. It's Kepler's equation, give or take a parameter or two. It appears when trying to figure out where a planet is currently located in orbit, which, yes, is something people do. The point presently is its pedigree means the equation has been thrashed by many big brain types over the years, which is how we know it has no closed-form solution.
This is an example of a transcendental equation. A beasty solved usually by, well, guessing. Call it what you will. Iteration. Perturbation. Hail Mary mathematics. It all means the same thing. That being said, Kepler's equation provides an interesting lesson in thinking about solutions. A chance to work on your equation fu. The first thing we should ask is whether a solution exists. If the answer is no, then we can stop now.
Does a solution exist? That depends on the behavior of the RHS, which I'm going to call f(x) so I can refer to it. If f(x) is bounded or discontinuous, there might be trouble. If, say, f(x) is never bigger than 1, then f(x) = 2 has no solution. Or, if f(x) can't be negative, then f(x) = −1 has no solution. Or if it skips over values here and there. We need to crawl around in its pelt for a bit.
We know that | sin(x) | ≤ 1, so f(x) is never smaller than x − 1 and never larger than x + 1, But since x can be anything, we can conclude f(x) is not bounded. So far so good. Furthermore f(x) is continuous because it is the difference of two continuous functions -- x and sin(x) -- and there's a famous theorem that says the difference of two continuous functions is continuous. Ergo, by applying the Intermediate Value Theorem, we can safely conclude f(x) can take on any value in (−∞, +∞).
We have a hunting license -- no matter what y is, there exists an x such that y = x − sin(x). But a hunting license is different than actually bagging a bambi. How to proceed?
Note dy/dx = 1 − cos(x), which is nonnegative, so f(x) is nondecreasing, i.e., if x1 < x2 then f(x1) ≤ f(x2). A plan of attack suggests itself: 1) Guess an x, 2) if f(x) < y, increase x until f(x) > y. If f(x) > y, decrease x until f(x) < y. This gets us in the ballpark of the answer, bracketing the solution between the last two guesses, one on either side. We then repeat the process taking smaller steps until we're happy with the precision. There are more sophisticated techniques for this solving these kinds of equations, but the bracketing method as it is called will suffice for our needs.
We begin by moving everything to the LHS, so we really look for solutions of y − x + sin(x) = 0, where y is given. This because when we bracket zero the current guess and the previous guess will be of opposite sign, which is easy to check by testing if their product is negative. Everything else is just code. I whipped this up in Javascript:
function keplerBracket(y)
{
// solve: y = x - sin(x) for x
var err;
var tol = 0.001;
var toggle = 1;
var this_x = y;
var delta_x = 1.0;
var sanityCheck = 0;
while (sanityCheck++ < 10000) {
err = y - this_x + Math.sin(this_x);
if (Math.abs(err) < tol) return this_x;
if (err*toggle < 0) {
toggle = -toggle;
delta_x = delta_x / 2.0;
}
this_x = this_x + toggle * delta_x;
}
alert("keplerBracket: No convergence");
return 0;
}
Here, you can try it out. Enter y in the box and press solve (enter a valid number, not something wiseass like "potato"):
{
// solve: y = x - sin(x) for x
var err;
var tol = 0.001;
var toggle = 1;
var this_x = y;
var delta_x = 1.0;
var sanityCheck = 0;
while (sanityCheck++ < 10000) {
err = y - this_x + Math.sin(this_x);
if (Math.abs(err) < tol) return this_x;
if (err*toggle < 0) {
toggle = -toggle;
delta_x = delta_x / 2.0;
}
this_x = this_x + toggle * delta_x;
}
alert("keplerBracket: No convergence");
return 0;
}
---
And there's the solution. I can't add anything the code doesn't say already. There's nothing here in the way of abstract concepts or grand theorems. We pretty much just hound the solution to exhaustion using our machine savants. One day, I suspect, those machines will turn on us, but that day is not today.
Postscript
Crikey. Look at the sweat and tears this tiny speck of an equation caused us (if you are not sweating, imagine solving this equation by hand). You expect tigers or sharks to be dangerous. But this? It's like one of those poison dart frogs of the Amazon rainforest. A happy rainbow livery and neurotoxinous enough to kill you with a burp.
I don't know about you, but to me it's unnerving something so simple looking can be such a pain in the fur. You're prepared for Fourier transforms or Stoke's equations or whatever to ruin your day. But then some little equation shows up and makes a mockery of your problem solving skills, just when you were starting to feel good about yourself. If that's not a perfect metaphor for life, I don't know what is.
No comments:
Post a Comment