Transfinite interpolation

Last updated March 15, 2019

In numerical analysis, transfinite interpolation is a means to construct functions over a planar domain in such a way that they match a given function on the boundary. This method is applied in geometric modelling and in the field of finite element method.^[1]

Numerical analysis study of algorithms that use numerical approximation for the problems of mathematical analysis

Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis. Numerical analysis naturally finds application in all fields of engineering and the physical sciences, but in the 21st century also the life sciences, social sciences, medicine, business and even the arts have adopted elements of scientific computations. As an aspect of mathematics and computer science that generates, analyzes, and implements algorithms, the growth in power and the revolution in computing has raised the use of realistic mathematical models in science and engineering, and complex numerical analysis is required to provide solutions to these more involved models of the world. Ordinary differential equations appear in celestial mechanics ; numerical linear algebra is important for data analysis; stochastic differential equations and Markov chains are essential in simulating living cells for medicine and biology.

In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity. For example, the position of a planet is a function of time. Historically, the concept was elaborated with the infinitesimal calculus at the end of the 17th century, and, until the 19th century, the functions that were considered were differentiable. The concept of function was formalized at the end of the 19th century in terms of set theory, and this greatly enlarged the domains of application of the concept.

The finite element method (FEM), is a numerical method for solving problems of engineering and mathematical physics. Typical problem areas of interest include structural analysis, heat transfer, fluid flow, mass transport, and electromagnetic potential. The analytical solution of these problems generally require the solution to boundary value problems for partial differential equations. The finite element method formulation of the problem results in a system of algebraic equations. The method approximates the unknown function over the domain. To solve the problem, it subdivides a large system into smaller, simpler parts that are called finite elements. The simple equations that model these finite elements are then assembled into a larger system of equations that models the entire problem. FEM then uses variational methods from the calculus of variations to approximate a solution by minimizing an associated error function.

The transfinite interpolation method, first introduced by William J. Gordon and Charles A. Hall,^[2] receives its name due to how a function belonging to this class is able to match the primitive function at a nondenumerable number of points.^[3] In the authors' words:

“

We use the term ‘transfinite’ to describe the general class of interpolation schemes studied herein since, unlike the classical methods of higher dimensional interpolation which match the primitive function F at a finite number of distinct points, these methods match F at a non-denumerable (transfinite) number of points.

”

Transfinite interpolation is similar to the Coons patch, invented in 1967. ^[4]

In mathematics, a Coons patch, is a type of manifold parametrization used in computer graphics to smoothly join other surfaces together, and in computational mechanics applications, particularly in finite element method and boundary element method, to mesh problem domains into elements.

Formula

With parametrized curves ${\vec {c}}_{1}(u)$ , ${\vec {c}}_{3}(u)$ describing one pair of opposite sides of a domain, and ${\vec {c}}_{2}(v)$ , ${\vec {c}}_{4}(v)$ describing the other pair. the position of point (u,v) in the domain is

${\begin{array}{rcl}{\vec {S}}(u,v)&=&(1-v){\vec {c}}_{1}(u)+v{\vec {c}}_{3}(u)+(1-u){\vec {c}}_{2}(v)+u{\vec {c}}_{4}(v)\\&&-\left[(1-u)(1-v){\vec {P}}_{1,2}+uv{\vec {P}}_{3,4}+u(1-v){\vec {P}}_{1,4}+(1-u)v{\vec {P}}_{3,2}\right]\end{array}}$

where, e.g., ${\vec {P}}_{1,2}$ is the point where curves ${\vec {c}}_{1}$ and ${\vec {c}}_{2}$ meet.

Related Research Articles

In the mathematical subfield of numerical analysis, a B-spline, or basis spline, is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. Any spline function of given degree can be expressed as a linear combination of B-splines of that degree. Cardinal B-splines have knots that are equidistant from each other. B-splines can be used for curve-fitting and numerical differentiation of experimental data.

The surface area of a solid object is a measure of the total area that the surface of the object occupies. The mathematical definition of surface area in the presence of curved surfaces is considerably more involved than the definition of arc length of one-dimensional curves, or of the surface area for polyhedra, for which the surface area is the sum of the areas of its faces. Smooth surfaces, such as a sphere, are assigned surface area using their representation as parametric surfaces. This definition of surface area is based on methods of infinitesimal calculus and involves partial derivatives and double integration.

In geometry, an affine transformation, affine map or an affinity is a function between affine spaces which preserves points, straight lines and planes. Also, sets of parallel lines remain parallel after an affine transformation. An affine transformation does not necessarily preserve angles between lines or distances between points, though it does preserve ratios of distances between points lying on a straight line.

Unit quaternions, also known as versors, provide a convenient mathematical notation for representing orientations and rotations of objects in three dimensions. Compared to Euler angles they are simpler to compose and avoid the problem of gimbal lock. Compared to rotation matrices they are more compact, more numerically stable, and more efficient. Quaternions have applications in computer graphics, computer vision, robotics, navigation, molecular dynamics, flight dynamics, orbital mechanics of satellites and crystallographic texture analysis.

In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset.

In Mathematics and Statistics, a piecewise linear or segmented function is a real-valued function defined on the real numbers or a segment thereof, whose graph is composed of straight-line sections. It is a piecewise-defined function, each of whose pieces is an affine function.

In mathematics, a spline is a function defined piecewise by polynomials. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low degree polynomials, while avoiding Runge's phenomenon for higher degrees.

Curve fitting is the process of constructing a curve, or mathematical function, that has the best fit to a series of data points, possibly subject to constraints. Curve fitting can involve either interpolation, where an exact fit to the data is required, or smoothing, in which a "smooth" function is constructed that approximately fits the data. A related topic is regression analysis, which focuses more on questions of statistical inference such as how much uncertainty is present in a curve that is fit to data observed with random errors. Fitted curves can be used as an aid for data visualization, to infer values of a function where no data are available, and to summarize the relationships among two or more variables. Extrapolation refers to the use of a fitted curve beyond the range of the observed data, and is subject to a degree of uncertainty since it may reflect the method used to construct the curve as much as it reflects the observed data.

The particle-in-cell (PIC) method refers to a technique used to solve a certain class of partial differential equations. In this method, individual particles in a Lagrangian frame are tracked in continuous phase space, whereas moments of the distribution such as densities and currents are computed simultaneously on Eulerian (stationary) mesh points.

In numerical analysis, a cubic Hermite spline or cubic Hermite interpolator is a spline where each piece is a third-degree polynomial specified in Hermite form: i.e., by its values and first derivatives at the end points of the corresponding domain interval.

A parallel of a curve is the

A parametric surface is a surface in the Euclidean space $which is defined by a parametric equation with two parameters Parametric representation is a very general way to specify a surface, as well as implicit representation. Surfaces that occur in two of the main theorems of vector calculus, Stokes' theorem and the divergence theorem, are frequently given in a parametric form. The curvature and arc length of curves on the surface, surface area, differential geometric invariants such as the first and second fundamental forms, Gaussian, mean, and principal curvatures can all be computed from a given parametrization.$

Lattice Boltzmann methods (LBM) is a class of computational fluid dynamics (CFD) methods for fluid simulation. Instead of solving the Navier–Stokes equations, the discrete Boltzmann equation is solved to simulate the flow of a Newtonian fluid with collision models such as Bhatnagar–Gross–Krook (BGK). By simulating streaming and collision processes across a limited number of particles, the intrinsic particle interactions evince a microcosm of viscous flow behavior applicable across the greater mass.

In mathematics of stochastic systems, the Runge–Kutta method is a technique for the approximate numerical solution of a stochastic differential equation. It is a generalisation of the Runge–Kutta method for ordinary differential equations to stochastic differential equations (SDEs). Importantly, the method does not involve knowing derivatives of the coefficient functions in the SDEs.

Active contour model, also called snakes, is a framework in computer vision introduced by Michael Kass, Andrew Witkin and Demetri Terzopoulos for delineating an object outline from a possibly noisy 2D image. The snakes model is popular in computer vision, and snakes are widely used in applications like object tracking, shape recognition, segmentation, edge detection and stereo matching.

In numerical linear algebra, the Alternating Direction Implicit (ADI) method is an iterative method used to solve Sylvester matrix equations. It is a popular method for solving the large matrix equations that arise in systems theory and control, and can be formulated to construct solutions in a memory-efficient, factored form. It is also used to numerically solve parabolic and elliptic partial differential equations, and is a classic method used for modeling heat conduction and solving the diffusion equation in two or more dimensions. It is an example of an operator splitting method.

In kinematics, the motion of a rigid body is defined as a continuous set of displacements. One-parameter motions can be defined as a continuous displacement of moving object with respect to a fixed frame in Euclidean three-space (E³), where the displacement depends on one parameter, mostly identified as time.

In fluid mechanics, meteorology and oceanography, a trajectory traces the motion of a single point, often called a parcel, in the flow.

In geology, numerical modeling is a widely applied technique to tackle complex geological problems by computational simulation of geological scenarios.

References

↑ Dyken, Christopher; Floater, Michael S. (2009). "Transfinite mean value interpolation". Computer Aided Geometric Design. 1 (26): 117–134. CiteSeerX 10.1.1.137.4822 . doi:10.1016/j.cagd.2007.12.003.
↑ Gordon, William; Hall, Charles (1973). "Construction of curvilinear coordinate systems and application to mesh generation". International Journal for Numerical Methods in Engineering. 7 (4): 461–477. doi:10.1002/nme.1620070405.
↑ Gordon, William; Thiel, Linda (1982). "Transfinite mapping and their application to grid generation". Applied Mathematics and Computation. 10–11 (10): 171–233. doi:10.1016/0096-3003(82)90191-6.
↑ Steven A. Coons, Surfaces for computer-aided design of space forms, Technical Report MAC-TR-41, Project MAC, MIT, June 1967.

This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[Dyken2009-1] Dyken, Christopher; Floater, Michael S. (2009). "Transfinite mean value interpolation". Computer Aided Geometric Design. 1 (26): 117–134. CiteSeerX 10.1.1.137.4822 . doi:10.1016/j.cagd.2007.12.003.

[Hall73-2] Gordon, William; Hall, Charles (1973). "Construction of curvilinear coordinate systems and application to mesh generation". International Journal for Numerical Methods in Engineering. 7 (4): 461–477. doi:10.1002/nme.1620070405.

[Gordon82-3] Gordon, William; Thiel, Linda (1982). "Transfinite mapping and their application to grid generation". Applied Mathematics and Computation. 10–11 (10): 171–233. doi:10.1016/0096-3003(82)90191-6.

[coons-4] Steven A. Coons, Surfaces for computer-aided design of space forms, Technical Report MAC-TR-41, Project MAC, MIT, June 1967.