Spend some time browsing around the web site of MIT’s Computer Science and Artificial Intelligence Laboratory, and you’ll find hundreds if not thousands of documents with titles like “On Modeling Nonlinear Shape-and-Texture Appearance Manifolds” and “Non-linear Drawing systems,” or, on the contrary, titles like “Packrat Parsing: Simple, Powerful, Lazy, Linear Time” and “Linear-Time-Encodable and List-Decodable Codes.”
The distinction between linear and nonlinear phenomena is everywhere in the sciences and engineering. But what exactly does it mean?
Suppose that, without much effort, you can toss a tennis ball at about 20 miles per hour. Now suppose that you’re riding a bicycle at 10 miles per hour and toss a tennis ball straight ahead. The ball will travel forward at 30 miles per hour. Linearity is, essentially, the idea that combining two inputs — like the velocity of your arm and the velocity of the bike — will yield the sum of their respective outputs — the velocity of the ball.
Now suppose that, instead of tossing a tennis ball, you toss a paper airplane. Depending on the airplane’s design, it might sail straight ahead, or it might turn loops. Some paper planes seem to behave more erratically the harder you throw them: the bike’s added velocity might make it almost impossible to get the plane to do anything predictable. That’s because airflow over a paper plane’s wings can be very nonlinear.
If the bicycle had built-in sensors and an onboard computer, it could calculate the velocity of the tennis ball in a fraction of a second. But it could never hope to calculate all the airflows over the paper plane’s wing in time to do anything useful. “I think that it’s a reasonable statement that we mostly understand linear phenomena,” says Pablo Parrilo, the Finmeccanica Career Development Professor of Engineering MIT’s Laboratory for Information and Decision Systems.
To make the distinction between linearity and nonlinearity a bit more precise, recall that a mathematical equation can be thought of as a function — something that maps inputs to outputs. The equation y = x, for instance, is equivalent to a function that takes as its input a value for x and produces as its output a value for y. The same is true of y = x2.
The equation y = x is linear because adding together inputs yields the sum of their respective outputs: 1 = 1, 2 = 2, and 1 + 2 = 1 + 2. But that’s not true of y = x2: if x is 1, y is 1; if x is 2, y is 4; but if x is 3, y is not 5.
This example illustrates the origin of the term “linear”: the graph of y = x is a straight line, while the graph of y = x2 is a curve. But the basic definition of linearity holds for much more complicated equations, such as the differential equations used in engineering to describe dynamic systems.
While linear functions are easy enough to define, the term “nonlinear” takes in everything else. “There’s this famous quote — I’m not sure who said it first — that the theory of nonlinear systems is like a theory of non-elephants,” Parrilo says. “It’s impossible to build a theory of nonlinear systems, because arbitrary things can satisfy that definition.” Because linear equations are so much easier to solve than nonlinear ones, much research across a range of disciplines is devoted to finding linear approximations of nonlinear phenomena.
Russ Tedrake, for example, the X Consortium Associate Professor of Electrical Engineering and Computer Science at MIT, has adapted theoretical work done by Parrilo to create novel control systems for robots. A walking robot’s gait could be the result of a number of mechanical systems working together in a nonlinear way. The collective forces exerted by all those systems might be impossible to calculate on the fly. But within a narrow range of starting conditions, a linear equation might describe them well enough for practical purposes. Parrilo’s theoretical tools allow Tedrake to determine how well a given linear approximation will work within how wide a range of starting conditions. His control system thus consists of a whole battery of linear control equations, one of which is selected depending on the current state of the robot.