We can prove the harmonic series diverges, so it's obvious what's wrong with the program from last class.
However, there are genuine research problems involving numerical computations which blow up.
They can go both ways: we might not get infinity when we're expecting it, and we might get infinity when we're not.
The most famous of these problems is the Navier Stokes equation for a viscous fluid in three dimensions.
Do the solutions of these equations go to infinity?
Mathematically, we don't know. (It's a Clay Millennium problem.)
Numerically, we don't know if we know.
Simulations have been done, and they seem to blow up.
Is it the equations, or just errors in the numerical simulation?
Example: Here are some fluid mechanical simulations by Prof. Keith Julien and collaborators.
How do you know what you're seeing is real?
This is the goal of numerical analysis.
It's not just about running the program!
Basic principle: Program cautiously! Algorithms can surprise you.
Example: Newton's method for solving equations.
Newton's method is very useful numerically: when it works, it's great; but it doesn't always work!
We'll discuss it in detail later in the course.
The basic idea is to find a root by approximating a curve with its tangent line.
The formula for getting the new guess is the following:
Suppose we try to use this algorithm to find the complex solutions of f(z) = z3 - 1 = 0.
There are three solutions: 1, -0.5 + 0.866 i, -0.5 - 0.866 i.
Newton's method will always converge to one of them.
However, it's really difficult to know in advance which one will be reached from a given starting point.
Below is a famous plot of this: points colored blue will converge to 1, points colored green converge to -0.5 + 0.866 i, points colored red converge to -0.5 - 0.866 i.
We obtain a fractal; there are green, blue, and red bits mixed all around.
A very simple algorithm leads to very complicated behavior!
This sort of thing is common. Algorithms can surprise you!
Basic principle: A little paper-and-pencil work can save a lot of computer time.
Example: Telescoping series.
Consider the series
The error in using N terms looks like the integral of 1/x2, from N to infinity.
If we use only the first N terms,
the most we could possibly be off by
is the sum of rectangles from N to infinity.
That's less than the integral from N to infinity.
And we know how to calculate that exactly.
It's ln(1+1/N). Which is roughly 1/N.
So using 1,000,000 terms, we are sure that our answer is within 10-6 of the true sum.
Here is a Maple program to do this.
| > | total:=0:
for i from 1 to 1000000 by 1 do total:=evalf(total+1/(i^2+i)): end do: print(total); |
What do you think the true answer is? Looks like 1.
How far off are we? 6 * 10-6.
Larger than our theoretical prediction! Why?
Is there a better way? Yes!
Using partial fractions, we can write
No computer time required!
Of course, this is a very special case.
However, one can often do things much more efficiently by doing hand computations first.
A few hours on paper can save you days of computation time.
Review of calculus theorems
Rolle's Theorem:
If f is a continuous and differentiable function and f(a) = f(b), then there is a c between a and b such that f'(c) = 0.
Proof on board.
Generalized Rolle's Theorem:
If f has n derivatives and is zero at (n + 1) points, then there is a c such that f(n)(c) = 0.
The function f (in red) has zeroes at a, b, and c.
By Rolle's Theorem, its derivative f' (in green) must have zeroes at points d and e.
By Rolle's Theorem for f', the function f'' (not pictured) must have a zero between d and e.
In this way, three zeroes of the original function give a zero of the second derivative.
Mean Value Theorem:
If f is continuous and differentiable, then there is a c between a and b such that f'(c) = [ f(b) - f(a) ] / [b-a].
Proof: Subtract the secant line between a and b from the function, and use Rolle's Theorem.
Taylor's Theorem:
Suppose f has at least (n+1) derivatives and x0 is any point. Let Pn(x) be the nth Taylor polynomial
Proof on board.
Taylor's Theorem is the most important theorem in Numerical Analysis!
This is true despite the fact that we almost never know what ξ is!