Piecewise-Polynomial Approximation

Ariel Chenet

We begin by considering the approximation of continuous function by piece-wise linear functions.

A piece-wise linear function is a function that has a finite set of points where it is not linear, and is linear between any two adjacent pairs of finite points. More symbolically, a piece-wise linear function $f:I->k$ , where $I$ is a real number interval $[a,b]$ and $k$ is a field, generally the real or complex numbers in most applications, is a function such that there exists a set of points $a=x_{0}<x_{1}\dots<x_{n}=b$ with the property: for any $i$ and $j$ such that $j=i+1$ , $f$ is linear on the interval $[x_{i},x_{j}]$ , ie, there exists elements in $k$ $m_{i}$ and $c_{i}$ such that $f(x)=m_{i}x+c_{i}$ on the interval $[x_{i},x_{j}]$ .

Theorem 1.

Let $f$ be a piece-wise linear function on the real interval $I=[a,b]$ with points of non-linearity $x_{0}=a,x_{1},\dots,x_{n}$ .

Then for any $i\in\{0,\dots,n-1\}$ , for all $x\in[x_{i},x_{i+1}]$ , $f(x)$ has value

\frac{x(f(x_{i+1})-f(x_{i}))+(f(x_{i})x_{i+1}-f(x_{i+1})x_{i})}{x_{i+1}-x_{i}}

Proof.

To prove this, we take our $x$ input and find the borders of the interval $[x_{i},x_{i+1}]$ which contain it. Because $f$ is linear between these two points, it must be the line that passes between the points $(x_{i},f(x_{i}))$ and $x_{i+1},f(x_{i+1}))$ . The value of a point on this line is

\frac{x(f(x_{i+1})-f(x_{i}))+(f(x_{i})x_{i+1}-f(x_{i+1})x_{i})}{x_{i+1}-x_{i}}

∎

A piece-wise linear function with $n$ points of non-linearity has a simple representation as the set of values of the function at the points of non-linearity. The values $v_{i}=f(x_{i})$ give the values of the function at points where the derivative of the function is not a constant number. These values uniquely define the function.

Given these values $v_{0},\dots v_{n}$ , we can write a simple formula for the value of the function, which we can then implement in JavaScript.

      function approximate(xvals, fvals, xin) {
        if (xvals.length != fvals.length) {
          console.error("mismatched array lengths");
          return;
        }
        var { left, right } = findIndexes(xvals, xin);
        var fxi = fvals[left],
          fxj = fvals[right];
        var xi = xvals[left],
          xj = xvals[right];
        return (xin * (fxj - fxi) + (fxi * xj - fxj * xi)) / (xj - xi);
      }

      function findIndexes(xvals, xin) {
        var i = 0;
        while (i < xvals.length) {
          if (xvals[i] <= xin && xvals[i + 1] >= xin) {
            return { left: i, right: i + 1 };
          }
          i++;
        }
        throw new Error("could not find indexes");
      }

Below is an implementation of the preceding code.

Input the x values of the points of non-linearity in the “x values” field, and the values of the function to estimate f in the “f values” field, using the format [ x1, x2, x3 ], when x1, x2 and x3 represent any three 64-bit integers.

Enter the input value of the variable x you’d like to approximate the value of f(x) for, click “approximate” button, and the approximate value of f(x) should appear below the input fields and button, in the part of the page where is currently written "The approximate value of f(x) will display here."

x values

f values

x input

The approximate value of f(x) will display here.