Representing a Function with Finitely Many Numbers🔗
Here is a taut string, pinned at both ends and pulled sideways. The whole curve is its displacement \(u(x)\) on \(0 \le x \le 1\), and we want to store it in a computer with a handful of numbers. A computer cannot store a curve, so every method in this course, the multilayer perceptron included, stores a short list of numbers and a rule that turns the list back into a curve. On this page we build such choices by hand, measure what each one loses, and arrive at hat functions whose nodes can move.
Readings at fixed stations🔗
The obvious move is to measure the string. Put three sensors along it, at \(x = 0\), \(\tfrac12\), \(1\). For the displacement \(u(x) = 0.8\sin(\pi x) + 0.4\sin(2\pi x) + 0.2\sin(3\pi x)\) they read \(0\), \(0.60\), \(0\), and everything between the sensors is unknown. So we guess. The simplest guess connects neighboring readings with straight lines, and we have a curve again. Now look where the guess is wrong. The lines never rise above \(0.60\), while the string peaks at \(1.11\) near \(x = 0.23\), so the worst miss is \(0.82\), about three quarters of the largest displacement.
Would more sensors fix this? Between two sensors a distance \(h\) apart the curve bends away from a straight line by about \(u''h^2/8\) at the middle, so halving \(h\) should cut the miss to a quarter. Five sensors read \(0\), \(1.11\), \(0.60\), \(0.31\), \(0\) and miss by \(20.1\) percent of the largest displacement, nine by \(6.3\), and seventeen by \(1.6\). The first two halvings divide the miss by \(3.7\) and \(3.2\), short of four, because a segment still spans a large part of the shortest wavelength in the curve and the bend inside it is far from a parabola. From nine sensors on each halving divides the miss by \(4.0\).
These gaps are visible only because the curve is known. Suppose only the seventeen readings were available. Which curves could have produced them? Add the wave \(0.3\sin(16\pi x)\) to the displacement. At every station \(16\pi x_i\) is a multiple of \(\pi\), so the wave is zero there and not one reading changes, while the curve moves by \(0.3\) at each crest. Two functions that agree at every station are aliases on that grid, and the readings cannot tell them apart. The lab below starts from three stations. Sweep the station count, then switch the added wave on and find the counts at which no reading moves.
Coefficients on shapes🔗
Here is a different idea. Instead of asking where the string is, ask what it is made of. The string vibrates in sine modes, and the displacement above is the first three of them weighted by \(0.8\), \(0.4\), \(0.2\). Those three numbers give the whole curve, with no grid anywhere. Check it at mid-span, where the second mode vanishes and the first and third read \(1\) and \(-1\), so \(u(\tfrac12) = 0.8 - 0.2 = 0.6\). Add two displacements and their coefficients add, scale one and its coefficients scale, so the three coefficients are coordinates and the displacement is a point in a three-dimensional space of functions. In the lab below the displacement is the solid black curve, and it stays fixed. The sliders set three weights, and the gray dashed curve is their weighted sum. Start from the weights \((0.5, 0, 0)\) and move them until the gray curve lies on the black one. One slider moves the whole gray curve, since each weight belongs to a shape that spans the string, and the distance to the displacement reads zero at \((0.8, 0.4, 0.2)\). The lab also reports the error in the three norms defined further down the page, the largest gap, the root-mean-square gap, and the slope error, and traces them as the sliders move. The Solve button finds those weights without searching. The modes are orthogonal and each has squared norm \(\tfrac12\), so each weight is one inner product, \(a_k = 2\int_0^1 u(x)\sin(k\pi x)\,dx\), which is the projection developed further down the page.
So far every curve was smooth, because every sine is smooth. Now press on the string at one point. The point load bends it into two straight segments with a corner at mid-span, and no sum of three sines has a corner. The closest sum is the best available, and which sum is closest depends on how the error is measured. That depends on what matters. If it is clearance under the string, only the worst gap matters, and that is the sup norm. If it is the overall misfit, all the gaps count at once, so square them, integrate, and take the root, and that is the \(L^2\) norm. If it is the elastic energy, the values are the wrong thing to look at, since the energy is an integral of the squared slope, and the root of the integrated squared slope error is the \(H^1\) seminorm. For the five-sensor guess the three read \(0.22\), \(0.093\), and \(1.20\). In relative terms the values are off by \(14\) percent and the slopes by \(42\). The lab below draws the gap, its square, and its slope error, and the station slider shows the three falling at different rates.
A spike of height one on a base of width \(0.04\) has sup norm one, \(L^2\) norm \(0.115\), and elastic energy \(50\), and quartering the base leaves the first, halves the second, and quadruples the third, so the three can disagree without bound.
Now go back to the corner. In the lab below the point-load displacement is the solid black curve, and three weighted sines make the gray dashed one. The sum closest in \(L^2\) has weights \(c_k = 2\sin(k\pi/2)/(k\pi)^2\), that is \((0.2026, 0, -0.0225)\), and it is also the closest in \(H^1\), because the sines are orthogonal in both inner products. It misses by \(9.9\) percent of the peak in the largest gap, \(4.8\) percent in the root-mean-square gap, and \(31.5\) percent in the slopes. The sum closest in the sup norm has different weights, \((0.2045, 0, -0.0318)\), and it trades the other way, \(5.5\) percent in the largest gap against \(6.7\) in the root-mean-square gap and \(33.9\) in the slopes. Each sum is closer in the norm it minimizes, and no sum of three sines reaches the corner itself.
Name \(L^2\) and ask which sum of three sines is closest to the parabola \(x(1-x)\), the shape of the string under a uniform load. In ordinary geometry a perpendicular dropped from the point onto the plane finds the closest point, and a perpendicular needs a dot product. For functions the dot product is the integral of the product, \(\langle f, g\rangle = \int_0^1 f g\,dx\), and the sine modes are orthogonal in it. Slide one coefficient and the squared error is a bowl whose bottom sits where the error is orthogonal to the mode, at \(c_1 = 2\langle u, \sin(\pi x)\rangle = 8/\pi^3 = 0.258\), one division per coefficient and no search. The closest sum misses the parabola by \(0.87\) percent. Push \(c_1\) twenty percent higher and the eye cannot tell the new curve from the old, while its error norm is \(23\) times larger. The first lab below slides the coefficient. The second lab adds modes to three targets and shows how fast the coefficients fall, one power of \(k\) for each derivative the target keeps continuous, so a smooth target needs few modes and a step's coefficients fall like \(1/k\).
Can a smooth family reach a corner?🔗
Three sines could not make a corner. Can a family of smooth shapes come as close as we like to any continuous function, a corner included? Here is Bernstein's idea, tried first on a function it can handle, the string displacement \(u(x) = 0.8\sin(\pi x) + 0.4\sin(2\pi x) + 0.2\sin(3\pi x)\) from the coefficients lab. Take readings of the displacement at the \(n + 1\) points \(k/n\). To estimate the displacement at a point \(x\), flip \(n\) coins that land heads with probability \(x\). The fraction of heads \(k/n\) lands near \(x\), so average the readings \(f(k/n)\) with the probability of exactly \(k\) heads as the weight,
The weights are nonnegative and add to one, so \(B_n f(x)\) is a weighted average of readings taken near \(x\), and it is a polynomial of degree \(n\) in \(x\). As \(n\) grows the fraction of heads concentrates around \(x\) with spread \(\sqrt{x(1-x)/n}\), the average uses readings closer to \(x\), and the gap shrinks. For the displacement the largest gap sits near \(x = 0.24\), below the hump, and it is \(0.30\) with \(8\) coins, \(0.17\) with \(16\), \(0.091\) with \(32\), and \(0.024\) with \(128\), so each doubling of \(n\) halves it. Voronovskaya's formula predicts the gap at a point where \(f\) is twice differentiable, \(x(1-x)\,|f''(x)|/(2n)\), and its largest value over the string is \(3.18/n\), which gives \(0.099\) at \(n = 32\) and \(0.025\) at \(n = 128\). The formula holds for large \(n\), and at \(8\) coins it overstates the gap, \(0.40\) against the measured \(0.30\). So the gap falls like \(1/n\), and at no finite \(n\) does the polynomial reproduce the displacement, since a Bernstein polynomial reproduces only straight lines exactly. The coefficients lab reproduced this displacement with three sine weights, and Bernstein needs \(128\) coins to reach \(2\) percent of its largest value, because his construction averages readings and never solves for the best weights. Raise the number of coins in the lab below, then move the probe and watch the weights crowd around it.
Now the corner function \(|x - \tfrac12|\). With two coins the three weights are three hills, one at each wall and one at mid-span, and for the corner function \(|x - \tfrac12|\) their sum reads \(\tfrac14\) at mid-span where the function is \(0\), because every neighbor of the corner sits higher than the corner and any average overshoots there. As \(n\) grows the fraction of heads concentrates near \(x\), the hills narrow like \(1/\sqrt{n}\), and so does the gap. At \(n = 8\) the gap at the corner is \(0.137\) against a prediction of \(0.4/\sqrt{n} = 0.141\), and at \(n = 32\) it is \(0.070\) against \(0.071\). The corner has no second derivative, so Voronovskaya's formula does not apply, and the gap falls like \(1/\sqrt{n}\), slower than the bump's \(1/n\). Raise the degree below and watch the hills narrow while the gap at the corner follows the prediction.
Weierstrass's theorem states the general fact. Every continuous function on an interval is within any tolerance of some polynomial. Notice what the theorem does not say. It names neither the polynomial nor the degree, and it says nothing about slopes, since every \(B_n f\) has slope zero at the corner where the slope of \(f\) jumps from \(-1\) to \(1\). Universal approximation theorems for networks have the same form, existence without a procedure that finds the approximation.
Hat functions as a basis🔗
Look again at the straight segments. They are a basis too. Take one shape per station, equal to one at its own station, zero at every other station, and straight in between, a hat function \(\phi_i\). Weight each hat by the reading at its station and add,
and the sum is the straight-segment guess, with the readings as its coefficients. A hat is local, since it is zero outside the two segments beside its station, so each coefficient changes the curve only there. The finite element method is built on this basis. Courant proposed piecewise-linear hats in 1943, and Galerkin's method chooses their weights by making the error orthogonal to every hat in the energy inner product, which for the string gives the readings, as the energy projection showed above.
How many shapes can hats model? Every continuous function on the interval, since the gap of the straight-segment guess goes to zero as the spacing \(h\) shrinks. For a function with \(|u''| \le M\) the gap is at most \(Mh^2/8\), so halving the spacing divides it by four. Take the string displacement in the lab below. Five stations miss by \(20.1\) percent of the largest displacement, seventeen by \(1.6\), and thirty-three by \(0.4\). The bump from the coefficient-decay lab is narrower and needs more hats, \(13.4\) percent at nine stations, \(2.1\) at thirty-three, and \(0.5\) at sixty-five.
Back to the point load. One hat whose node sits on the corner describes it with one number, \(0.25\), and on the five-station grid the hats do it with \(0.125\), \(0.25\), \(0.125\) and no error, while the closest three sines miss by \(4.8\) percent and thirty-three still miss by \(0.20\). A shape that shares the function's corner needs one number where smooth shapes need infinitely many.
The square pulse, equal to one on \([0.3, 0.7]\) and zero elsewhere, is the case hats cannot finish. Every sum of hats is continuous, and the pulse jumps. The largest gap stays between \(60\) and \(80\) percent at every station count, because the straight segment across each jump misses both sides. The root-mean-square gap still falls, from \(46.5\) percent at five stations to \(23.3\) at seventeen and \(11.6\) at sixty-five, halving each time the stations are quadrupled, since the region of large error narrows with the spacing. So which shapes to use depends on the function, and so far we have placed them by hand.
Let the nodes move🔗
The nodes of a hat basis need not sit on an even grid. Where would we want them? Hot fluid pushes a temperature front along a pipe, one shape \(T(x - ct)\) whose whole history is its position. Thirty-two evenly spaced stations reach an error of \(8.7\) percent, because most of them record a flat line wherever the front sits. A straight-segment curve with only four nodes, \(0.02\) on either side of each edge, reaches \(4.9\) percent, and when the front moves the nodes move with it while the stations stay where we put them. Fixed nodes make the family a linear subspace, so fitting it is one solve, and the projection theorem guarantees that the solve finds the unique closest member. Moving nodes give a non-convex problem, and no such guarantee. The gain is on fields whose features sit in a few places, and the lab below moves the front.
The book's notebooks on functions as points, norms, projection, and Weierstrass by coin flips run the computations on this page. The second page continues with noisy readings, kernels, families of functions, and shapes that move.