Fritsch and Carlson is non-linear?

Question

I was reading about this interpolation method and saw that it was mentioned that the algorithm is non-linear. What does that exactly mean? I am confused because I don't get what is "non-linearity" in this case. I have set of points, I go over each interval and find the slopes that need to be modified and modify them. So I loop only once; is it not linear then?

Answer 1

However "straightforward" Fritsch and Carlson's proposed method for Monotone Piecewise Cubic Interpolation (1980) that preserve monotonicity may be, the mapping is not linear.

Linearity would imply that solutions exhibit the superposition principle in that on any common set of nodes $\{x_i\}$, the function $f$ which interpolates monotone increasing $\{y_i\}$,

$$ f(x_i) = y_i $$

and the function $g$ which interpolates monotone increasing $\{z_i\}$,

$$ g(x_i) = z_i $$

would add up to the function $h$ which interpolates $\{y_i + z_i\}$,

$$ h(x_i) = y_i + z_i $$

But it doesn't generally happen that $h = f + g$. I think an example that illustrates this is for $\{x_i\}=\{0,1,2,3\}$, $y_0 = y_1 = 0, y_2 = y_3 = 1$, and $z_0 = 0, z_1 = z_2 = 1, z_3 = 2$. If these data are added, the resulting $h(x) = x$ on $[0,3]$, which is not the sum $f(x) + g(x)$.

---

Here are some crude pictures of the three monotone cubic spline interpolants $f,g,h$ for the data above:

Following the steps outlined here, the resulting splines are easily found. The function $f$ must be constant on the first and last intervals, the function $g$ must be constant on the middle interval, and as already noted, $h(x)=x$. To prove $h \neq f + g$ is suffices to inspect the middle interval, where clearly $h$ and $g$ are flat (without curvature), but the function $f$ has an inflection point and switches from concave up to concave down.

The monotone cubic splines are secretly cubic Hermite splines, where function values are specified by input data and slopes $m_i$ are chosen to ensure monotonicity (and continuity of the first derivative). In the case of $f$ we have slopes $f'(0)=f'(1)=f'(2)=f'(3)=0$, while for $g$ we impose $g'(0)=g'(3)=1$ and $g'(1)=g'(2)=0$. Since $h'(x) = 1$ identically, this gives a more concrete demonstration that $h \neq f+g$.