Convex Combination

From Wikiversity
Jump to navigation Jump to search
Visualization of a convex combination of degree 1., 2. and 3. in Geogebra 

Introduction[edit | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

convex combination as an illustration in a GIF animation


Convex combinations of 2 vectors in function spaces[edit | edit source]

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 | edit source]

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 | edit source]

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

convex combination of two functions in geogebra

Geogebra: Interactive Applet - Download:' Geogebra-File

Remark - Deformation[edit | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

Geogebra: Interactive applet - Download:' Geogebra-File

Remarks Video about convex combinations of order 1, 2 and 3 in Geogebra[edit | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

Calculation of the polynomial - order 2[edit | edit source]

Bernstein polynomial - order 2[edit | edit source]

Bernstein polynomial - order 3[edit | edit source]

Task: calculation of the polynomial - order 3[edit | edit source]

  • 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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

1st order convex combination[edit | edit source]

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

2nd order convex combination[edit | edit source]

  • 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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

For 4 vectors, again use as parameterization

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


Task[edit | edit source]

  • (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 | edit source]

  • (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 | edit source]

  • (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 | edit source]

  • (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 | edit source]

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 | edit source]

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 | edit source]

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 | edit source]

Substituting for gives the linear interpolation function over:

.

Learning Tasks[edit | edit source]

  • 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 | edit source]

Interpolation with convex combination of order 3

See also[edit | edit source]

References[edit | edit source]

  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 )