# 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={\mathrm{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 ${\mathrm{min}}_{k}{\mathrm{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\mathrm{cos}t,r\mathrm{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 |
---|---|

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 |