# approximate non-linear transformation of affine combination

Consider applying an arbitrary transformation $f$ to an affine combination $\sum_{i=1}^{n}w_{i}x_{i}$ of some points $x_{i}$, with non-negative weights $w_{i}$ that sum to unity. Obviously, in general,

 $f\Bigl{(}\sum_{i=1}^{n}w_{i}x_{i}\Bigr{)}\neq\sum_{i=1}^{n}w_{i}f(x_{i})\,.$

However, sometimes it is desirable to compute the image $f(\sum_{i}w_{i}x_{i})$ as if $f$ were a linear (or affine) transformation; the result is then hoped to be a good approximation to the true value. (See below for an application.)

Actually, it is possible to show that, provided that $f$ is twice continuously differentiable, the approximation is good to first order, despite the absence of any derivatives of $f$ in the formula. The domain and range of $f$ may be any normed vector spaces.

First, we write:

 $\displaystyle f\Bigl{(}\sum_{i}w_{i}x_{i}\Bigr{)}$ $\displaystyle=f\Bigl{(}\sum_{i}w_{i}(x_{i}-x_{1})+x_{1}\Bigr{)}$ $\displaystyle=f(x_{1})+\sum_{i}w_{i}f^{\prime}(x_{1})(x_{i}-x_{1})+O\Bigl{(}% \Bigl{\lVert}\sum_{i}w_{i}(x_{i}-x_{1})\Bigr{\rVert}^{2}\Bigr{)}\,.$

If $h=\max_{i}\lVert x_{i}-x_{1}\rVert$, then $\lVert\sum_{i}w_{i}(x_{i}-x_{1})\rVert\leq\sum_{i}\lvert w_{i}\rvert h=h$, and so the error term in the Taylor expansion can be simplified to $O(h^{2})$.

Substituting another Taylor expansion

 $\displaystyle f(x_{i})-f(x_{1})=f^{\prime}(x_{1})(x_{i}-x_{1})+O(h^{2})\,,$

into the first, we obtain:

 $\displaystyle f\Bigl{(}\sum_{i}w_{i}x_{i}\Bigr{)}$ $\displaystyle=f(x_{1})+\sum_{i}w_{i}\Bigl{(}f(x_{i})-f(x_{1})+O(h^{2})\Bigr{)}% +O(h^{2})$ $\displaystyle=\sum_{i}w_{i}f(x_{i})+O(h^{2})\,.$

Furthermore, it is not hard to see, by accounting the error from the Taylor expansions more carefully, that we have the bound:

 $\Bigl{\lVert}f\Bigl{(}\sum_{i}w_{i}x_{i}\Bigr{)}-\sum_{i}w_{i}f(x_{i})\Bigr{% \rVert}\leq Mh^{2}\,,$

where $M$ is the maximum, as $\xi$ ranges inside the convex hull formed by the points $x_{i}$, of the quantity $\lVert f^{\prime\prime}(\xi)\rVert=\sup\limits_{u\neq 0}\frac{\lVert f^{\prime% \prime}(\xi)(u,u)\rVert}{\lVert u\rVert^{2}}$. Finally, the point $x_{1}$ over which we performed Taylor expansions can be replaced by any other point $x_{k}$, and so correspondingly $h$ can be replaced by $\min_{k}\max_{i}\lVert x_{i}-x_{k}\rVert$.

## Application in computer graphics

The principle just derived is often applied in vector-based computer graphics when curved objects are drawn by cubic Bézier curves:

 $\gamma(t)=\sum_{i=0}^{3}w_{i}(t)\,x_{i}\,,\quad w_{i}(t)=\binom{3}{i}(1-t)^{n-% i}t^{i}\,,$

which are affine combinations of the control points $x_{i}$. To compute and display a smooth transformation $f$ of such curves, it may be too much work to compute $f(\gamma(t))$ repeatedly for many parameter values $t$. Provided $\gamma$ is not too wavy, computing and displaying $\sum_{i=0}^{3}w_{i}(t)\,f(x_{i})$ is vastly more efficient, and may result in little or no visually perceptible difference.

As a concrete example, consider bending a straight line segment into a circle. Mathematically, we are mapping the interval $[0,2\pi]$ via $t\mapsto(r\cos t,r\sin t)$. If the interval is split into sub-segments, each considered as a cubic Bézier curve with its interior control points both set at the midpoint of the line segment, then a circle can be approximated by transforming these control points. The following diagram shows the approximation for 24 segments (three Bézier curves per $45^{\circ}$ arc).

Title approximate non-linear transformation of affine combination ApproximateNonlinearTransformationOfAffineCombination 2013-03-22 16:50:35 2013-03-22 16:50:35 stevecheng (10074) stevecheng (10074) 7 stevecheng (10074) Example msc 41A58 msc 51N20