Numerical analysis exam: the methods that always come up

Numerical analysis (calcolo numerico, or Numerical Methods, depending on the university) is one of those exams that look “easy” because it does not have the heavy theory of first-year Calculus, and that is exactly why many students underestimate it. The problem is not understanding what a method does. It is carrying it out correctly by hand, with a calculator, in limited time, without MATLAB to check every step.

I have worked with several Politecnico (Italian engineering university) students on this exam, and the pattern is always the same. They understand the idea of Newton or Simpson perfectly well in lectures, and then in the written test they lose marks on mechanical details: a badly written stopping criterion, a forgotten Jacobian, a sign error in a table of iterations. Here I give you the method I use to get ready: what the exam really asks, where most marks are lost, and three exercises worked all the way down to the numbers.

What the exam asks

The typical structure, at almost every Italian university, is a written paper with exercises to solve by hand (often with a scientific calculator, sometimes with a laptop and MATLAB/Octave for the programming part) on four families of problems:

1. Roots of a function: solving $f(x)=0$ with an iterative method (Newton, bisection, fixed point), with a stopping criterion and an error estimate.
2. Interpolation: building the polynomial that passes through a set of points (Lagrange or Newton with divided differences) and using it to estimate a value.
3. Numerical integration (quadrature): approximating ${\int }_a^{b}f(x)dx$ with the trapezium rule or Simpson’s rule, with an error estimate.
4. Ordinary differential equations (ODEs): solving $y^{\prime }=f(x,y)$ with explicit Euler or Runge-Kutta, again with error analysis.

On top of all this, the course puts two cross-cutting ideas that come back in every chapter: conditioning (how much a small error in the data is amplified in the result) and stability (whether a method amplifies or damps rounding errors step after step). A well-set exam always asks, in at least one exercise, for a comment on one of these two aspects — not only for the number to come out right.

Where the marks are lost, in practice

After correcting and reviewing dozens of exercises with my students, the mistakes almost always cluster in the same places:

1. A stopping criterion written at random. “Iterate until it converges” is not a criterion. You need an explicit threshold: $|x_{n+1}-x_n|<\epsilon$ or $|f(x_n)|<\epsilon$, declared before you start iterating, not after seeing where the number stops.

2. Forgetting the derivative in Newton. Newton’s method needs $f^{\prime }(x)$ at every iteration. If $f^{\prime }(x_n)$ is close to zero, the method can diverge or oscillate: examiners often ask you to discuss this, not just to apply the method.

3. Interpolation: confusing the degree of the polynomial with the number of points. With $n+1$ points the interpolating polynomial has degree (at most) $n$, not $n+1$. It is a trivial mistake, but it throws off the whole calculation of the Lagrange coefficients.

4. Quadrature: applying Simpson with an odd number of intervals. Composite Simpson needs an even number of sub-intervals (so an odd number of nodes). With an odd number of intervals the composite formula does not apply — and yet it is the most common mistake when $n$ is chosen at random without checking the parity.

5. Quadrature error: forgetting that it depends on the fourth derivative (Simpson) or the second (trapezium), not on the function itself. The error estimate asks you to bound $|f^{\prime \prime }(\xi )|$ or $|f^{(4)}(\xi )|$ on the interval, not to recompute the integral with a more precise method.

6. ODEs: using Euler and expecting the accuracy of Runge-Kutta. Explicit Euler is first order — the local error is $O(h^2)$, the global one $O(h)$. With a step $h$ that is not very small, the error is visible by eye after just two or three steps, and that is normal: it is not a sign that you got the calculation wrong.

7. Not commenting on conditioning and stability when asked. An exercise that asks “is the problem well conditioned?” is not answered with “yes” or “no”: you estimate quantitatively how much a relative error in the data is amplified in the result.

The method, step by step

Newton’s method for $f(x)=0$

You start from an initial point $x_0$ close to the root you are looking for, and iterate:

Geometrically: you approximate the function with the tangent line at $x_n$ and take as the new estimate the point where that line meets the $x$-axis. When the root is simple (that is, $f^{\prime }(\text{root})\ne 0$) and you start close enough, convergence is quadratic: the number of correct digits roughly doubles at every iteration. Stop when $|x_{n+1}-x_n|<\epsilon$ (or on $|f(x_n)|$), and always state the tolerance you chose.

Interpolation: Lagrange and Newton with divided differences

Given $n+1$ points $(x_0,y_0),\dots ,(x_n,y_n)$ with distinct $x_i$, there is a unique polynomial of degree at most $n$ that passes through all of them. The Lagrange form writes it as a combination of the basis polynomials:

Each $L_i(x_i)=1$ and $L_i(x_j)=0$ for $j\ne i$: that is why the sum passes exactly through all the points. Let us do a small concrete example: with the points $(0,1)$, $(1,2)$, $(3,16)$, you want $P(2)$. You compute the three basis polynomials at $x=2$:

The Newton form (divided differences) is algebraically equivalent but more convenient when you have to add one more point without redoing the whole calculation: it is the one to prefer if the exercise asks you to “update” an existing interpolation.

Quadrature: trapezium and Simpson

The composite trapezium rule on $[a,b]$ divided into $n$ sub-intervals of width $h=(b-a)/n$:

with error $-\frac{(b-a)h^2}{12}{f}^{\prime \prime }(\xi )$ for a suitable $\xi \in [a,b]$. Composite Simpson ($n$ even) uses a parabola over every two intervals:

with error $-\frac{(b-a)h^4}{180}{f}^{(4)}(\xi )$: it converges much faster than the trapezium rule (the error scales as $h^4$ instead of $h^2$) for the same computational effort.

Euler and Runge-Kutta for ODEs

For $y^{\prime }=f(x,y)$, $y(x_0)=y_0$, explicit Euler moves forward in a straight line with the current slope:

Fourth-order Runge-Kutta (RK4) averages four estimates of the slope inside the step (one at the start, two at the midpoint, one at the end):

Euler is first order (global error $O(h)$), RK4 fourth order ($O(h^4)$): with the same step $h$, RK4 is orders of magnitude more accurate, which is why exercises almost always ask you to compare them.

Conditioning and stability

Conditioning is about the problem, not the method: an ill-conditioned problem amplifies errors in the data even with a perfect algorithm (classic example: solving a nearly singular linear system). Stability is about the method: an unstable method amplifies rounding errors at every step, however well posed the starting problem is. Keeping the two apart is almost always asked for explicitly in at least one question of the exam.

Three worked exercises

Exercise 1 — Newton for a cubic root

Find the zero of $f(x)=x^3-2x-5$ starting from $x_0=2$, with $f^{\prime }(x)=3x^2-2$, stopping when $|x_{n+1}-x_n|<10^{-5}$.

Between $x_2$ and $x_3$ the difference is already below $10^{-5}$: the root is $x\approx 2.09455148$. Note the speed: from $x_1$ to $x_2$ you gain three correct digits, from $x_2$ to $x_3$ you gain another five — that is quadratic convergence in action.

Exercise 2 — Simpson for ${\int }_1^2\frac{1}{x}dx$

The exact value is $\ln 2\approx 0.6931472$. With $n=4$ sub-intervals, $h=0.25$:

Actual error: $\approx 1.07\times 10^{-4}$. The theoretical bound, with $f^{(4)}(x)=24/x^5$ and maximum $|f^{(4)}|=24$ on $[1,2]$ (reached at $x=1$):

The actual error sits well inside the theoretical bound, as it should: the bound is (rightly) pessimistic, not an exact value. For comparison, the composite trapezium rule with the same $h$ would give $0.6970238$ — an error of about $3.9\times 10^{-3}$, almost forty times worse with the same number of function evaluations.

Exercise 3 — Euler vs RK4 on $y^{\prime }=x+y$, $y(0)=1$

Exact solution: $y(x)=2e^x-x-1$. With step $h=0.1$, two steps:

Euler: $y_{n+1}=y_n+h(x_n+y_n)$

RK4, same step:

With the same step, RK4 is about fifty thousand times more accurate than Euler after two steps — the difference between order 1 and order 4 is not a theoretical nuance, you can see it even on a small exercise.

How we work in the lessons

On numerical analysis I work almost always on paper and with a calculator, not on MATLAB — because that is how you will be asked at the exam, and because carrying out one or two Newton iterations or a Simpson quadrature by hand is what makes you really understand what happens inside the method (and where the error hides when something does not add up). We start from the exercises of your course’s tutorial sessions and redo them together with the table of iterations written out in full — not just the final result — and when the mechanism is solid we move on to past exam papers, timed as if it were the real test.

If your course also includes a MATLAB lab part, we cover that separately: you will find the dedicated path on the computer science page, with an eye to writing vectorised code instead of explicit loops.

Part of what is used here comes from other exams: matrices and linear systems are in linear algebra: rank, kernel and image, the convergence of an iteration is read with the same tools as sequences in Calculus 1, and if your course moves straight on to dynamical systems, the link is with the automatic control exam.

For the general picture of how I work on university maths, see the maths page; if you are still preparing an entrance test and have not yet met these topics, look at the admission tests section.

Do you want to test yourself before writing to your university? You will find the university exam practice tests on Calculus 1 and 2, Linear algebra, Physics 1 and 2 — the correct answer is free, the guided solution comes with the first lesson. If you just want a quick second opinion on an exercise that does not add up, write to me through the contact page: a 30-minute introductory call is usually enough to tell whether the problem is the method or the execution.