Teaching objectives
A university lab on the numerical solution of equations, built around a single question that no room ever abandons: I want to solve this equation and I want to do it cheaply.
The order is not that of a topology chapter — definition, theorem, applications — but that of somebody who meets the problem head on. The first room explains nothing: it shows the equation x² = 2cos 3x + 5, an empty table and a field to type values into. No graph, no starting interval and no hints, which is exactly the real situation of someone who runs into an equation they cannot solve. The goal is to get below 1 % error in ten tries, and it is calibrated so that a disciplined strategy achieves it in exactly ten: it genuinely bites, and that frustration is what makes bisection in room 3 land as a relief rather than as one more procedure to memorise.
From room 4 onwards — with bisection already built — everything is measured in the same unit, one evaluation of the function, and every method that shows up fills a card with three boxes: which hypotheses it asks for, what it shrinks, and by how much it multiplies it per evaluation. Room 15 shows the complete card, computed live by running each method on each equation.
The lab pits two methods against each other, and only two: bisection and Newton. One asks for almost nothing and cannot fail; the other asks for a lot and flies. Everything else — the plane, Banach's theorem, the cobweb, the relaxation parameter — is there to explain why the second one wins and what has to be paid for it.
The three equations
The whole lab hangs on three equations that reappear in every room, so that comparing methods means something:
x² = 2cos 3x + 5(root 2.446382). The main one. It has no closed form, but its right-hand side lives in [3; 7], so the interval can be narrowed by reasoning, without spending a single evaluation.ln x = 3 − x(root 2.207940). Isolating x in the two obvious ways gives two iterations with opposite destinations:3 − ln xconverges ande^(3−x)does not.x² = x + 1(the golden ratio). The only one with an exact solution, so it serves as a yardstick for measuring the error for real.
What is learned
- Turning blind probing into a method, recognising that what one does by instinct — looking for two values whose difference has opposite signs — already is bisection.
- Measuring the cost of a method in evaluations of the function rather than in "steps", which is the only unit that lets two different methods be compared.
- Reading contractivity in the plane, on a figure, and knowing the constant has to work for all pairs at once.
- Reconstructing Banach's theorem in parts: the jumps shrink geometrically, the triangle inequality puts the whole tail inside a circle computable in advance, and the fixed point is unique.
- Translating that bound into ε and N: demanding a distance and knowing from which step it holds, without knowing the solution.
- Choosing a rewriting
x = g(x)by looking at|g′|, and building one to measure with the relaxation parameter. - Placing Newton where it belongs: not a trick, but the member of that family which picks the best parameter at each point without needing the answer.
- Knowing when not to use Newton: it is the only method in the lab that can run away, and the student has to find a starting point that makes it jump.
Key mathematical ideas
- The unit of measurement is part of the result. A method is judged in evaluations of the function, not in "steps": Newton doubles the digits at every step but pays two evaluations per step, and that accounting is what really decides.
- Methods are ranked by what they demand you know in advance. Continuity plus a sign change buys 0.5 per evaluation. Proven contractivity buys whatever C you have. A derivative plus a close enough starting point buys quadratic convergence. There are no free lunches, and that progression is the spine of the lab.
- Bisection cannot fail and cannot improve, for the same reason. Its factor of 1/2 does not depend on the function because the method never looks at the function: only at its sign.
- Contracting is a uniform condition. It shows better in the plane than on the line: a map that squashes horizontally and stretches vertically brings most pairs closer and is still not contractive, because a single pair moving apart rules out any C < 1.
- The error bound is known before you start.
C^m/(1−C)·d(x₀,x₁)needs only the constant and the first jump, both measurable from the outset. No other method in the lab gives that, and in the plane it is drawn as a circle containing the whole tail of the path. - Newton is inevitable, not ingenious. In the family
g_λ(x) = x − λ f(x), the best λ is1/f′(x*)— and it is useless, because it requires knowing the solution. Recomputing it at the point you are standing on,λₙ = 1/f′(xₙ), gives exactly Newton's formula. The price is the second evaluation per step. - Brouwer is the opposite end from Banach. It asks only for continuity and delivers pure existence: no uniqueness, no algorithm, no convergence of the iteration.
Notes for the classroom
- Rooms 1, 5, 12 and 15 work best projected. Room 1 can be played as a whole group, with the class dictating values: the moment somebody proposes narrowing the range using the fact that the cosine never exceeds 1, the lab has done half its job.
- Room 5 (the map that squashes and stretches a cat's face) is the most memorable. Ask the class to look for the pair of points that moves apart the most before saying anything; the typical mistake is to look for it horizontally.
- Room 7 explains itself step by step, lighting up in the drawing the distances each inequality talks about. It is worth pausing at every step and asking the class to anticipate the next one before pressing.
- Room 12 is the hinge of the lab and deserves time. Having students find the λ window by moving the slider before seeing the condition
|1 − λf′| < 1completely changes how Newton's formula reads afterwards. - Room 15 closes it: let the class bet on the ranking before revealing the table, and dwell on the optimal-λ row, which beats everything and is useless.
- The plane block (rooms 5-8) can be taught on its own as a visual introduction to Banach's theorem, without the rest of the lab.
- The hardest rooms are 1 and 12. Room 1 because it frustrates on purpose; room 12 because it demands understanding that the iteration can be designed rather than accepted as it comes.
Room-by-room contents
Room 1 · By eye
The whole lab in miniature, with no help whatsoever: the equation x² = 2cos3x + 5 written out, an empty table and a field to type values into. There is no graph — deliberately: with the curve in front of you, finding the solution is pointing a finger — no starting interval and no hints. Each value tried adds a row with both sides, their difference and the relative error, highlighting the best attempt. The goal is to get below 1 % in ten tries, calibrated so that a disciplined strategy achieves it in exactly ten from a cold start. On the tenth without success, the one hint that costs no evaluation appears — the right-hand side lives in [3;7], so x² does too — and probing continues: the room never blocks.
Student tasks
- Get below 1 % error in ten tries.
- Recognise, by looking at the difference column, which strategy was actually followed.
Room 2 · Trapping the solution
The theorem behind the probing: if f is continuous and changes sign between a and b, it vanishes in between. On a table of values of f at five points, the student must say in which intervals Bolzano guarantees a solution. The trap is the last one, with both endpoints positive and two solutions inside: the theorem does not see them, and that does not make it false. It gives guarantees, not a census.
Student tasks
- Mark the intervals where Bolzano guarantees a solution.
- Tell guaranteeing from there being one, in the trap interval.
Room 3 · Cutting in half
The method follows straight from the previous theorem. On the trigonometric equation trapped in [2;3], with the signs of f written under each endpoint and under the midpoint, the student chooses six times which half to keep; picking the one that does not preserve the sign change prompts an explanation of why the solution would be left outside. A stack of bars makes the shrinking visible. It closes with the detail that makes bisection competitive: the endpoints are inherited, so each cut costs a single evaluation.
Student tasks
- Correctly choose six times the half that preserves the sign change.
- Determine how many new evaluations each cut costs.
Room 4 · What did it cost you?
The lab's unit of measurement is installed: one evaluation of the function, which in a real problem may be a simulation lasting hours. The probing the student has just done is redrawn as error against evaluations, on a logarithmic scale, next to the line of perfect bisection. If there is no record of their probing, a typical one is shown. It closes by opening the card each method will fill in: which hypotheses it asks for, what it shrinks, and by how much per evaluation.
Student tasks
- Compare your own sequence with perfect bisection.
- Compute how many evaluations bisection needs to leave [2;3] below one millionth.
Room 5 · Off the line
The opener of the plane block, because a figure that shrinks reads at a glance and a graph does not. A cat's face and its image under T(v) = Av + b, with A = diag(0.5 · 1.3): it squashes to half the width and stretches 30 % vertically. Two glowing draggable points measure the ratio between the distance before and after, and the readout remembers the largest seen. The task is to explore and find the largest possible ratio, which turns out to be 1.3 with both points on the same vertical. Only then does the definition of contractive appear, with its "for all pairs" hard-earned: this map brings most pairs closer and is still not contractive.
Student tasks
- Move the points and find the largest possible ratio between distances.
- Mark what is true of the map, knowing the definition demands a single C below 1 valid for all pairs.
Room 6 · Where the cat ends up
We switch to a similarity that does contract: it rotates 30°, shrinks to 0.6 and translates. Since rotating and translating do not change distances, every pair comes closer by the same factor. The room starts with one image already drawn, so that what the transformation does is visible before betting anything; then the student clicks where they think the successive cats will pile up, and each miss adds one more image as a hint. On success it is revealed that the point is the solution of v = Av + b, a two-by-two linear system.
Student tasks
- Bet on where the cats will pile up before iterating.
- Compute how many images are needed for the drawing to measure less than 0.01.
Room 7 · Why it gets somewhere
An emergent explanation in four steps, lighting up in the drawing the distances each inequality talks about. Step 1: the jump from x₁ to x₂ is the image of the one from x₀ to x₁, so it measures at most C times it — and both jumps light up with their lengths. Step 2: the same one rung down, and chaining gives C². Step 3: the triangle inequality, with the chord from x₀ to x₃ drawn next to the three jumps. Step 4: "analogously", the general case and the sum of the geometric series. The conclusion — the bound can be made as small as you like — leads into the challenge, and solving it unlocks a slider where the student demands an ε and the drawing answers with the N that suffices and the corresponding ball.
Student tasks
- Follow the four steps and watch each distance light up in the drawing.
- Compute how many steps guarantee being within 0.001 of the limit.
- Demand different values of ε and read off the N needed in each case.
Room 8 · One, and only one
A hundred starting points scattered over the plane iterating at once, all collapsing to the same spot. Then uniqueness proved without iterating or drawing: four steps the student must put in order, written with d(·,·) rather than subtracting points, so they hold equally in the plane, on the line and anywhere there is a distance. It closes with the full statement of Banach's theorem.
Student tasks
- Iterate the cloud of a hundred points and see the destination does not depend on the start.
- Put the four steps of the uniqueness proof in order.
Room 9 · The same picture, on the line
Back to one dimension with what we learned: what was a cat piling up in the plane is a crossing with the diagonal y = x here. A slider raises and lowers a cubic and the student counts the crossings themselves — the green dots only appear after answering; shifting it makes two crossings merge and vanish, which could not happen in the plane. Second part: x² on the open interval (0;1) has no fixed point at all, which is the line version of what completeness was in the plane.
Student tasks
- Count the crossings of the curve with the diagonal.
- Determine how many fixed points x² has on the open interval (0;1).
Room 10 · The cobweb
Go up to the curve, bounce off the diagonal, repeat. The candidates are not toy straight lines but the genuine rewritings of the lab's equations —3 − ln x, e^(3−x), x² − 1, 1 + 1/x and √(1+x)—, all curves, so the slope varies and what really matters shows up: the slope AT the crossing decides. The bench spans the width of the room and animates on its own, ten steps every time a function is picked or the starting point is moved; there are no step buttons. The room does not let anyone through before all five have been tried, and meanwhile says in red how many are left. Only then does it ask, and it asks about what has just been seen.
Student tasks
- Try the five rewritings and see which ones close in on the solution.
- Mark the ones that converge and say what tells them apart.
Room 11 · The cone of slopes
The practical problem: we do not know where the crossing is, so we cannot evaluate the derivative there; it must be bounded over a whole interval. And that has the same picture as in the plane, the cone of slopes ±C anchored at a movable point. On g(x) = 3 − ln x over [1.5;3] the student tightens the cone to its limit and finds sup|g′| = 2/3. It closes with the list of what must be checked to apply Banach, including the condition always forgotten: that g maps the interval into itself.
Student tasks
- Find the tightest C by moving the anchor and the cone.
- Mark everything that must be checked to apply Banach on an interval.
Room 12 · Building one that converges
The hinge of the lab. Instead of settling for whichever rewriting turns up, the student builds their own: g_λ(x) = x − λ·f(x) is a whole family with a single knob, and all of its fixed points are the solution. As λ moves, the cobweb redraws itself and goes from running away to converging slowly to dropping almost in one go, with the slope at the solution read live. The window is 0 < λ < 2/f′(x*) ≈ 0.198 and the optimum is λ = 1/f′(x*) ≈ 0.0989; once it is found, the optimal iteration is drawn in green on top of the student's own, so the comparison does not rely on memory. And there is the catch that makes the next room inevitable: computing that λ requires knowing the solution.
Student tasks
- Find the largest λ for which the iteration still converges.
- Compute the λ that kills the slope at the solution and compare it with their own.
Room 13 · Newton, with no rabbit in the hat
The way out is one line long: if you do not know the solution, use the point you are standing on. Substituting λₙ = 1/f′(xₙ) into the relaxed iteration gives exactly Newton's formula, which stops being a separate trick and becomes the member of the family that picks the best parameter at each point without needing the answer. Then the geometric reading: the tangents are drawn one by one on the trigonometric equation and the picture zooms in after each —half a second, a long way in—, because from the second one on the crossings land less than a pixel apart. The challenge is about understanding, not arithmetic: which line is drawn and where one looks.
Student tasks
- Follow the derivation and draw the successive tangents with their zoom.
- Recognise how the next iterate is built.
Room 14 · What Newton costs
Quadratic convergence doubles the correct digits at each step, and it is paid for in three currencies: the derivative is needed and each step costs two evaluations; the derivative must not vanish near the path; and there is a guarantee only if you start close enough. The challenge is to find a starting point from which Newton escapes the stretch, and there are plenty because f′ vanishes inside. What they have in common is that the tangent is nearly horizontal, and there the crossing is flung away.
Student tasks
- Compute how many correct digits there are three steps after having two.
- Find a starting point from which Newton escapes, and identify what they have in common.
Room 15 · The scoreboard
The complete card: four methods by three equations, and in each cell the evaluations until six correct decimals, computed live by actually running each method. The student bets on the ranking before the table is revealed. The optimal-λ row carries an asterisk on purpose: it beats everything and is useless, because computing that λ requires knowing the solution. That is the watermark of the whole lab — methods are ranked by what they demand you know in advance, not by how clever they look. It closes by choosing a method for a concrete situation.
Student tasks
- Predict the ranking of the three methods before seeing the table.
- Choose the right method for an equation that is expensive to evaluate, with no derivative and a known sign change.
Room 16 · When contracting is not an option
The closing room. The end of the scale: demanding only continuity from the function. Brouwer's theorem with the animated coffee cup, and the warning that in dimension two or more the proof is not elementary. It is compared with Banach column by column — what each asks against what each gives — and the lab closes with the question it opened with: what the probing of the first room, bisection, golden search and the iteration have in common. The answer is the contraction factor per evaluation.
Student tasks
- Mark every true statement when comparing Brouwer with Banach.
- Identify what the lab's four methods have in common.
Rooms to project
The most striking ones to show and discuss in class.