Piecewise linear continuation

Piecewise linear continuation

implicial Continuation

Simplicial Continuation, or Piecewise Linear Continuation (Allgower and Georg [1] , [3] ) is a one parameter continuation method which is well suited to small to medium embedding spaces. The algorithm has been generalized to compute higher dimensional manifolds by (Allgower and Gnutzman [2] ) and (Allgower and Schmidt [4] ).

The algorithm for drawing contours is a simplicial continuation algorithm, and since it is easy to visualize, it serves as a good introduction to the algorithm.

Contour Plotting

The contour plotting problem is to find the zeros (contours) of f(x,y)=0, ( f(cdot), a smooth scalar valued function) in the square 0leq x leq 1, 0leq y leq 1,,

The square is divided into small triangles, usually by introducing points at the corners of a regular square mesh ih_xleq xleq (i+1)h_x,, jh_yleq y leq (j+1)h_y,, making a table of the values of f(x_i,y_j), at each corner (i,j),, and then dividing each square into two triangles. The value of f(x_i,y_j), at the corners of the triangle defines a unique Piecewise Linear interpolant lf(x,y), to f(cdot), over each triangle. One way of writing this interpolant on the triangle with corners (x_0,y_0),~(x_1,y_1),~(x_2,y_2), is as the set of equations: (x,y) = (x_0,y_0)+(x_1-x_0,y_1-y_0)s+(x_2-x_0,y_2-y_0)t,: 0leq s,: 0leq t,: s+t leq 1,: lf(x,y) = f(x_0,y_0)+(f(x_1,y_1)-f(x_0,y_0))s+(f(x_2,y_2)-f(x_0,y_0))t,The first four equations can be solved for (s,t), (this maps the original triangle to a right unit triangle), then the remaining equation gives the interpolated value of f(cdot),. Over the whole mesh of triangles, this piecewise linear interpolant is continuous.

The contour of the interpolant on an individual triangle is a line segment (it is an interval on the intersection of two planes). The equation for the line can be found, however the points where the line crosses the edges of the triangle are the endpoints of the line segment.

The contour of the piecewise linear interpolant is a set of curves made up of these line segments. Any point on the edge connecting (x_0,y_0), and (x_1,y_1), can be written as:(x,y) = (x_0,y_0) + t (x_1-x_0,y_1-y_0),,with t, in (0,1),, and the linear interpolant over the edge is: f sim f_0 + t (f_1-f_0),So setting f = 0,:t = -f_0/(f_1-f_0), and (x,y) = (x_0,y_0)-f_0*(x_1-x_0,y_1-y_0)/(f_1-f_0),Since this only depends on values on the edge, every triangle which shares this edge will produce the same point, so the contour will be continuous. Each triangle can be tested independently, and if all are checked the entire set of contour curves can be found.

Piecewise Linear Continuation

Piecewise linear continuation is similar to contour plotting (Dobkin, Silvio, Thurston and Wilks [5] ), but in higher dimensions. The algorithm is based on the following results:

Lemma 1







References

[1] Eugene L. Allgower, K. Georg, Introduction to Numerical Continuation Methods, SIAM Classics in Applied Mathematics 45. 2003.

[2] Eugene L. Allgower, Stefan Gnutzmann, An Algorithm for Piecewise Linear Approximation of Implicitly Defined Two-Dimensional Surfaces. SIAM Journal on Numerical Analysis, Volume 24, Number 2, 452--469, 1987.

[3] E. L. Allgower, K. Georg, Simplicial and Continuation Methods for Approximations, Fixed Points and Solutions to Systems of Equations SIAM Review, Volume 22, 28--85, 1980.

[4] Eugene L. Allgower, Phillip H. Schmidt, An Algorithm for Piecewise-Linear Approximation of an Implicitly Defined Manifold SIAM Journal on Numerical Analysis, Volume 22, Number 2, 322--346, April 1985.

[5] David P. Dobkin, Silvio V. F. Levy, William P. Thurston and Allan R. Wilks, Contour Tracing by Piecewise Linear Approximations. ACM Transactions on Graphics, 9(4) 389-423, 1990.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Numerical continuation — is a method of computing approximate solutions of a system of parameterized nonlinear equations, The parameter λ is usually a real scalar, and the solution an n vector. For a fixed parameter value λ,, maps Euclidean n space into itself. Often the …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • Dirac delta function — Schematic representation of the Dirac delta function by a line surmounted by an arrow. The height of the arrow is usually used to specify the value of any multiplicative constant, which will give the area under the function. The other convention… …   Wikipedia

  • Manifold — For other uses, see Manifold (disambiguation). The sphere (surface of a ball) is a two dimensional manifold since it can be represented by a collection of two dimensional maps. In mathematics (specifically in differential geometry and topology),… …   Wikipedia

  • Function (mathematics) — f(x) redirects here. For the band, see f(x) (band). Graph of example function, In mathematics, a function associates one quantity, the a …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”