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\left(\sum _{i=1}^n{w}_i{x}_i\right)\ne \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:

$f\left({\displaystyle \sum _i}{w}_i{x}_i\right)$ $=f\left({\displaystyle \sum _i}{w}_i(x_i-x_1)+x_1\right)$

$=f(x_1)+{\displaystyle \sum _i}{w}_i{f}^{\prime }(x_1)(x_i-x_1)+O\left({\parallel {\displaystyle \sum _i}{w}_i(x_i-x_1)\parallel }^2\right).$

If $h={\max }_i\parallel x_i-x_1\parallel$, then $\parallel {\sum }_i{w}_i(x_i-x_1)\parallel \le {\sum }_i|w_i|h=h$, and so the error term in the Taylor expansion can be simplified to $O(h^2)$.

Substituting another Taylor expansion

$f(x_i)-f(x_1)=f^{\prime }(x_1)(x_i-x_1)+O(h^2),$

into the first, we obtain:

$f\left({\displaystyle \sum _i}{w}_i{x}_i\right)$ $=f(x_1)+{\displaystyle \sum _i}{w}_i\left(f(x_i)-f(x_1)+O(h^2)\right)+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:

$$\parallel f\left(\sum _i{w}_i{x}_i\right)-\sum _i{w}_{i}f(x_i)\parallel \le M{h}^2,$$

where $M$ is the maximum, as $\xi$ ranges inside the convex hull formed by the points $x_i$, of the quantity $\parallel f^{\prime \prime }(\xi )\parallel =\underset{u\ne 0}{sup}\frac{\parallel f^{\prime \prime }(\xi )(u,u)\parallel }{{\parallel u\parallel }^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\parallel x_i-x_k\parallel$.

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,w_i(t)=\left(\genfrac{}{}{0pt}{}{3}{i}\right){(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).

Figure 1: Circle drawn using approximate mapping of line segment

Title	approximate non-linear transformation of affine combination
Canonical name	ApproximateNonlinearTransformationOfAffineCombination
Date of creation	2013-03-22 16:50:35
Last modified on	2013-03-22 16:50:35
Owner	stevecheng (10074)
Last modified by	stevecheng (10074)
Numerical id	7
Author	stevecheng (10074)
Entry type	Example
Classification	msc 41A58
Classification	msc 51N20