Convex Combination

Visualization of a convex combination of degree 1., 2. and 3. in Geogebra 

Introduction

edit

Let   be a real vector space. A Linear combination is called a convex combination if all coefficients   are from the unit interval [0,1] and the sum of all   for the vectors   with   equals 1:

 

Convex combinations in the plane

edit

When considering convex combinations in the plane, the underlying vector space is the two-dimensional space  . First, we consider convex combinations of two vectors in  . By the condition  , both scalars are dependent on each other. If  , then set   and  , for example.

Convex combinations as mappings into vector space

edit

Considering now a mapping  , we can generally represent 1st order convex combinations of 2 vectors   as follows over the mapping  :

 

Animation of a convex combination of two vectors as a figure

edit

 


Convex combinations of 2 vectors in function spaces

edit

Treating convex combination with   or   provides an illustration in secondary school vector spaces as special linear combinations. However, convex combinations can also be applied to function spaces. For example, let  , then   and   give rise to a new function   with:

 

The subscript   in   is used because a different function   is defined as a function of  .

Example of convex combinations of functions

edit

Let   and as the first function   a polynomial is defined.

 

A trigonometric function   is chosen as the second function.

 

The following figure illustrates the convex combination  .

Animation for convex combinations of functions

edit

The following animation shows several convex combinations of two given functions[1].

 

Geogebra: Interactive Applet - Download:' Geogebra-File

Remark - Deformation

edit

If the first function   describes the initial shape and   describes the target shape, convex combinations can be described, for example, in computer graphics for the deformation of an initial shape into a target shape.

Convex combinations of convex combinations

edit

In the animation above you can see a convex combination of 2 vectors viewed in the plane or in a function space. If one uses three points then one can create a 1st order convex combination between every two points. We will now consider higher order convex combinations by constructing, for example, a 2nd order convex combination from two 1st order convex combinations. Generally from 2 convex combinations of order   one convex combination of order   can be formed.

Convex hull

edit

The set of all convex combinations of a given set of vectors is called a convex hull (see also p-convex hull).

Video convex combinations in the plane

edit

Geogebra: Interactive applet - Download:' Geogebra-File

Remarks Video about convex combinations of order 1, 2 and 3 in Geogebra

edit

In the video you can see convex combinations of the

  • 1st order between   and   without auxiliary points,
  • 2nd order between   and   with auxiliary point  ,
  • 3rd order between   and   with auxiliary points  ,

Convex combinations as polynomials of t

edit

Convex combinations can be conceived as polynomials where the coefficients come from a vector space   (see also Polynomial Algebra). For example, if one chooses  , one can take a convex combination   to be an element of Polynomial Algebra  .

3D convex combination - 1st order

edit

For example, choosing   and  , a 1st order convex combination is defined as follows.

 

Thus, a 1st order convex combination yields a polynomial of degree 1. with argument  . Represent the convex combination in Geogebra 3D with   (see also Representation of a Straight Line by Direction Vector and Location Vector).

3D convex combination - 2nd order

edit

Choosing again   and   with an auxiliary point  , two 1st order convex combinations yield 2nd order convex combinations.

 

Represent   as a polynomial   and calculate for   ( ) the coefficients in  .

Bernstein polynomial - order 1

edit
 

Calculation of the polynomial - order 2

edit
 

Bernstein polynomial - order 2

edit
 

Bernstein polynomial - order 3

edit
 

Task: calculation of the polynomial - order 3

edit
  • Calculate the polynomial of degree 3 and derive from it the general formula for the coefficients of  . To do this, use the notation   and   for convex combinations of order   between points   and   with auxiliary points  .
  • Prove your conjecture by complete induction.
 

Interactive geogebra worksheet

edit

The video shows an interaction with the convex combinations above. From Geogebra, the worksheet created was uploaded to the Geogebra materials page. You can use this directly in your browser at the following link:

Interactive Worksheet: Convex Combination on Geogebra

Convex combination as a figure

edit

A convex combination can be used to interpolate points   and  . Furthermore, if the auxiliary points  ,....  are given for a convex combination  -th order. The convex combinations can be generally thought of as mapping from the interval   to   as follows:

 

Convex Combinations in Geogebra - Download

edit

In Geogebra, you can dynamically visualize the geometric meaning of convex combinations. At the

In the example files convex combinations of two points (vectors  ) are treated.


Definition of convex combinations as mappings/curves in vector space

edit

1st order convex combination

edit
  • 1st order convex combination generate all points on the connecting line between the two points  .
 .

2nd order convex combination

edit
  • A 2nd order convex combination arises with another auxiliary points   in the plane from the following two 1st order convex combinations:
  (1st order convex combination between  )
  (1st order convex combination between  )
  (2nd order convex combination. Order between   with auxiliary point  )

3rd order convex combination

edit

A 3rd order convex combination arises with two more auxiliary points   in the plane from the following three 1st order convex combinations:

  (1st order convex combination between  )
  (1st order convex combination between  )
  (1st order convex combination between  )

2nd order convex combinations from 1st order KK

edit

From the three 1st order convex combinations, construct two 2nd order convex combinations as follows:

  (2nd order convex combination. Order between   with auxiliary point  )
  (2nd order convex combination. Order between   with auxiliary point  )

3rd order convex combinations from 2nd order KK

edit

From the two 2nd order convex combinations, a 3rd order convex combination is now obtained as follows:

  (2nd order convex combination. Order between   with auxiliary points  )

Convex combinations of n-th order

edit

In general, a convex combination of  -th order has.

  •   auxiliary points  
  •   1st order convex combinations,
  •   2nd order convex combinations,
  • ...
  •   convex combinations  -th order,
  • ...
  •   convex combination n-th order,

In 3D graphics, 3rd-order convex combinations are particularly important (see Bezier curves).

Convex combination of functions

edit

Let   be a domain of definition of functions and   be a vector space over the body   (e.g.   and   the set of continuous functions from   to  . A convex combination of two continuous functions   with   is defined by:

 

Where

 


Convex combinations of more than 2 vectors

edit

In the above case, two vectors from the underlying vector space were studied as convex combinations and higher order convex combinations were also constructed. Now the procedure is extended to more than 2 vectors, again using a parametrization over vectors  .

Convex combinations of 3 vectors

edit

Extend the approach to convex combination with two parameters   and vectors   via:

 

and the mapping for the convex combinations into the closed triangle defined by the three vectors  :

 

Convex combinations of 4 vectors

edit

For 4 vectors, again use as parameterization  

 
 

The mapping   then represents all vectors from the convex hull of  .

 


Task

edit
  • (Geogebra) Analyze the Geogebra sample files and describe the importance of the auxiliary points for the shape of the locus line in the Dynamic Geometry Software (DGS) Geogebra.
  • What role do the auxiliary points play in creating differentiable interpolations (tangent vectors).
  • (Interpolation) Compare Lagrange or Newton interpolations for many data points with interpolation by several 3rd order convex combinations. What are the strengths and weaknesses (oscillation between data points) of the different methods. Veranschaulichen Sie diese mit Geogebra.

Aufgabe - 3. Ordnung und funktionale Darstellung

edit
  • (Konvexkombination 3-ter Ordnung) Berechnen Sie die Punkte von Konvexkombinationen 3. Ordnung im   mit Maxima CAS (siehe auch Maxima Tutorial der FH-Hagen).
K(t):= A * (1-t)^3 + H1 * (1-t)^2 * t + H2 * (1-t) * t^2 + B * t^3
Definieren Sie die Punkte als 3x1-Matrizen mit:
A : matrix( [-1], [3], [-4] )
  • (Unterschied Konvexkombination 3er Ordnung und kubischen Splines) Analysieren Sie Gemeinsamkeiten und Unterschiede von kubischen Splines und Konvexkombinationen 3er Ordnung! Was ist der Anwendungskontext von kubischen Splines? Wann würden Sie Konvexkombinationen verwenden?

Learning Task - Convex combination of Functions

edit
  • (Convex combination of Functions) Choose     and represent the convex combination of   and   in Geogebra with a slider   (analogous to the GIF animation), where   and  . What do you observe when you move the slider from 0 to 1?   is bounded and   is unbounded on  . What is the property of   for  ?
  • (Convex combinations and polynomialgebras) Summarize the convex combination of order   with coefficients from a vector space by powers of   and consider the coefficients from the vector space   in general. How are the coefficients of the polynomials formed from the points or auxiliary points for the powers? (See also Polynomial algebra and Bezier curves).

Learning Task - Bernstein polynomials and de-Casteljau algorithm

edit
  • (Bernstein polynomials) Analyze the connection of convex combinations as special linear combinations from linear algebra with Bernstein polynomials and Bezier curves. Bernstein polynomials for a certain degree   represent a decomposition of one. Which relation exists concerning a decomposition of one for convex combinations. What is the meaning of a polynomial representation with respect to a decomposition of one?
 

Interpolations

edit

Convex combinations can also be used to interpolate polynomials. Start first with first order interpolations by interpolating the points with straight lines of the form  . Here, the points   are given data points that are interpolated piecewise using the functions  . Compute from the convex combinations   the functional representation   with  :

 

Calculation of t as a function of x

edit

Given  . We now compute the corresponding   for the convex combination with the preliminary consideration that   for   and   for  . The following figure takes the linear transformation  .

 

Calculation of the function value at x

edit

The convex combination

 

gives the interpolation point of the graph. However, we only need the y-coordinate of the corresponding interpolation point  . So we use the following term:  .

Functional representation

edit

Substituting for   gives the linear interpolation function   over:

 .

Learning Tasks

edit
  • Calculate the coefficients   of the function   with  !
  • Transfer this interpolation to convex combination of order 3 and consider how, depending on the data points, you must choose the two auxiliary points of the interpolation so that the interpolation is differentiable and generates differentiable transitions between the interpolation points in the plot.
  • What geometric properties must auxiliary points between two adjacent interpolation intervals have for differentiability.

Interpolation with convex combination of order 3

edit

 

See also

edit

References

edit
  1. Bert Niehaus (2022) Convex combination of two functions in a vector space of functions - URL: https://www.geogebra.org/m/kkuufrck (Retrieved 14/01/2022 - 15:20 )