MATH/APPM 4650
Class notes, January 23
Algorithms and convergence
Most of today's notes including all examples will be on the board, but here are the basic concepts.
Algorithms
Definition: An algorithm is stable if small changes in inputs (starting values) produce small changes in outputs.
What does "small" mean? Usually depends on the problem.
There's no definition that's both universal and useful.
Generally we have some program that takes input x0 and outputs xN after N steps.
If the input is changed slightly to y0, the output changes to some yN.
Hopefully xN is not too far from yN!
The best one can hope for is usually linear error.
Definition: An algorithm has linear error growth if after N steps, the absolute error is
| yN - xN | ~ C N.
Here C is a constant that may depend on the initial error, but not on N.
Linear growth is your friend.
Definition: An algorithm has polynomial error growth if after N steps, the absolute error is
| yN - xN | ~ C Nk
for some power k.
Polynomial growth is an acquaintance you have nothing against.
Definition: An algorithm has exponential error growth if after N steps, the absolute error is
| yN - xN | ~ C AN
for some A> 1.
Exponential growth is your enemy!
Convergence
Definition: If an converges to a as n goes to infinity, we say that it converges with order O(1/np) if
(an - a) * np <= some constant
for all n.
Definition: If F(h) converges to L as h goes to zero, we say that it converges with order O(hp) if
(F(h) - L) / hp <= some constant
for all h.
Clearly these definitions mean the same thing if h = 1/n, which is a common notation.