This is Words and Buttons Online — a collection of interactive #tutorials, #demos, and #quizzes about #mathematics, #algorithms and #programming.
This is not only a tongue-twister but an actual interactive introduction. Here will be a living plot illustrating an iterative algorithm for solving systems of 2 linear equations. But first, a bit of theory.
Inherently, iterative algorithms consist of three steps:
Our example is a linear solver. It solves a system that looks like this:
a11 x + a12 y = b1
a21 x + a22 y = b2
We want to find (x, y) for every possible set of as and bs.
Geometrically speaking, a linear equation of two variables is just a straight line in 2D space. A system of two equations is a pair of lines. And the solution is the point where they intersect. It's as simple as that!
Our algorithm rationale is as follows. A point in space lies further from any point on a line than its own projection on that line. When we project a point on a line, it comes closer to all the points of the line simultaneously.
The solution we're looking for is a point in 2D that lies on both lines simultaneously. So if we project any point in space onto the first line, and then onto the second, and then again onto the first, and so on, it will get closer and closer to the solution. With every projection, the point “travels” towards a solution one step at a time.
After a while, that step gets too small, the point “stops”, and we then know that we are somewhere near the solution already.
In terms of the 3 steps from above it looks like this:
The plot below is the interactive illustration of the algorithm. You can move the equation-lines, change the starting point, or set your own tolerance.
As you can see, everything matters.
You can get some more precise solution with more iterations, but sometimes you'd need too many. (This particular algorithm doesn't go past 100) Some systems can be solved very fast and some can't be solved at all. And sometimes you can solve an unpleasant system simply by taking a lucky guess with a starting point.
This was probably the simplest iterative algorithm ever. It has no much use in “real life” though. Real iterative algorithms for solving linear systems look like this:
https://en.wikipedia.org/wiki/Iterative_method#Linear_systems.
Iterative algorithms may seem simple in their 3-step idea, but every single step brings a problem on its own.
Finding good initial values is not a real problem for us. We can pick just any point on a plane. But it gets vitally important if you use algorithms in a batch. Some algorithms may work fast and have terrible precision, some vice versa. It makes sense to use some fast algorithm if only to find a good initial guess for a precise one.
Sometimes you don't even know what sub-algorithms do you have in your batch, you let the algorithm choose how it will evolve. You let it make attempts and choose the best results. Simply put, this is how genetic algorithms work.
The next problem is the termination criteria. As you might have noticed, what we use for termination criteria doesn't work all that well even for the simplest case. Yes, there is some correlation between the threshold we pick and an error we get but it also depends on the system itself. The sharper the angle between our lines, the sooner we will stop and the larger our error will be.
Even in our simple case establishing some good termination criteria is not trivial.
The last problem is the convergence. The algorithm converges if it gets closer to the solution on every iteration and diverges if it gets even further. Our algorithm can only converge or not converge meaning full stop. It happens when the lines are parallel. They simply don't have a point of intersection and therefore we will never find it.
But convergence is not a categorical thing. It is measurable. Convergence analysis is the main part of developing a good iterative algorithm. Better convergence means fewer iterations and faster results.
This introduction demonstrates three ideas: initial guess, termination criteria, and convergence. These three are enough to build an iterative algorithm for any particular task.
Iterative algorithms may become very sophisticated at low-level, but at high-level, they are as simple as 1-2-3.
| Index #mathematics #algorithms #demos | ← there's more. |
+ Github & RSS |