Report

Interpolation By Radial Basis Function (RBF) By: Reihane Khajepiri , Narges Gorji Supervisor: Dr.Rabiei 1 1. Introduction • Our problem is to interpolate the following tabular function: Where the nodes ∈ and ( ) ∈ ℛ. • The interpolation function has the form () ≃ = () , =1 such that ()’s are the basis of a prescribed ndimensional vector space of functions on , i.e., =< 1 , 2 , … , >. 2 • This is a system of linear equations in unknowns. It can be written in matrix form as = , or in details as 1 (1 ) 2 (1 ) (1 ) 1 (1 ) ⋯ 1 (2 ) 2 (2 ) (2 ) 2 (2 ) = ⋮ ⋮ ⋱ ⋮ ⋮ 1 ( ) 2 ( ) ⋯ ( ) ( ) • The × matrix appearing here is called the interpolation matrix. • In order that our problem be solvable for any choice of arbitrary ( ), it is necessary and sufficient that the interpolation matrix be nonsingular. • The ideal situation is that this matrix be nonsingular for all choices of distinct nodes . 3 • Classical methods for numerical solution of PDEs such as finite difference, finite elements, finite volume, pseudo-spectral methods are base on polynomial interpolation. • Local polynomial based methods (finite difference, finite elements and finite volume) are limited by their algebraic convergence rate. • MQ collection methods in comparison to finite element method have superior accuracy. 4 • Global polynomial methods such as spectral methods have exponential convergence rate but are limited by being tied to a fixed grid. Standard" multivariate approximation methods (splines or finite elements) require an underlying mesh (e.g., a triangulation) for the definition of basis functions or elements. This is usually rather difficult to accomplish in space dimensions > 2. • RBF method are not tied to a grid but to a category of methods called meshless methods. The global non polynomial RBF methods are successfully applied to achieve exponential accuracy where traditional methods either have difficulties or fail. • RBF methods are generalization of Multi Quadric RBF , MQ RBF have a rich theoretical development. 5 2. Literature Review • RBF developed by Iowa State university, Rolland Hardy in 1968 for scattered data be easily used in computations which polynomial interpolation has failed in some cases. RBF present a topological surface as well as other three dimensional shapes. • In 1979 at Naval post graduate school Richard Franke compared different methods to solve scattered data interpolation problem and he applied Hardy's MQ method and shows it is the best approximation & also the matrix is invertible. 6 • In 1986 Charles Micchelli a mathematician with IBM proved the system matrix for MQ is invertible and the theoretical basis began to develop. His approach is based on conditionally positive definite functions. • In 1990 the first use of MQ to solve PDE was presented by Edward Kansa. • In 1992 spectral convergence rate of MQ interpolation presented by Nelson &Madych. 7 • Originally, the motivation for two of the most common basis meshfree approximation methods (radial basis functions and moving least squares methods) came from applications in geodesy, geophysics, mapping, or meteorology. • Later, applications were found in many areas such as in the numerical solution of PDEs, artificial intelligence, learning theory, neural networks, signal processing, sampling theory, statistics ,finance, and optimization. 8 Remaking Images By RBF 9 • It should be pointed out that meshfree local regression methods have been used independently in statistics for more than 100 years. • Radial Basis Function "RBF" interpolate a multi dimensional scattered data which easily generalized to several space dimension & provide spectral accuracy. So it is so popular 10 3. RBF Method 3.1 Radial Function • In many applications it is desirable to have invariance not only under translation, but also under rotation & reflection. This leads to positive definite functions which are also radial. Radial functions are invariant under all Euclidean transformations (translations, reflections & rotations) • Def: A function : ℛ → ℛ is called radial provided there exist a univariate function : [0, ∞) → ℛ such that () = () where r = And . is some norm on ℛ , usually the Euclidean norm. 11 • For a radial function : 1 = 2 (1 ) = (2 ) 1 , 2 ∈ ℛ . By radial functions the interpolation problem becomes insensitive to the dimension s of the space in which the data sites lie. Instead of having to deal with a multivariate function (whose complexity will increase with increasing space dimension s) we can work with the same univariate function for all choices of s. 12 3.2 Positive Definite Matrices & Functions • Def : A real symmetric matrix A is called positive semidefinite if its associated quadratic form is non negative For c= =1 =1 [1 , … , ] ∈ ≥0 (1) • If the only vector c that turns (1) into an equality is the zero vector , then A is called positive definite. • An important property of positive definite matrices is that all their eigenvalues are positive, and therefore a positive definite matrix is non-singular (but certainly not vice versa). 13 • Def: A real-valued continuous function is positive definite on if & only if =1 =1 ( − ) ≥ 0 (2) For any N pairwise different points 1 , 2 , … , ∈ & c = [1 , … , ] • The function is strictly positive definite on if the only vector c that turns (2) into an equality is the zero vector. 14 3.3 Interpolation of scattered data • One dimensional data polynomial &fourier interpolation has the form: S(x) = () : basis function { } : are distinct ( ) = → • For any set of basis function () independent of data points & sets of distinct data points { } such that the linear system of equation for determining the expansion coefficient become non-singular {Haar theorem} • Def: An n-dimensional vector space Γ of functions on a domain is said to be a Haar space if the only element of Γwhich has more than n-1 roots in is the zero element. 15 • Theorem1. Let Γ have the basis {1 , 2 , … , }. These properties are equivalent: a) Γ is a Haar space. b) det( ( )) ≠ 0 for any set of distinct points 1 , 2 , … , ∈ . Any basis for a Haar space is called Chebyshev system. • A Haar space is a space of functions that guarantees invertibility of the interpolation matrix. • Some examples of Chebyshev systems on ℝ: 1)1, , 2 , … , 2) 1 , 2 , … , , (1 < 2 < ⋯ < ) 3)1, ℎ, ℎ, … , ℎℎ, ℎ 4)( + 1 )−1 , ( + 2 )−1 , … ,( + )−1 , 0 ≤ 1 ≤ ⋯ ≤ 16 3-4 development of RBF method • Hardy present RBF which is linear combination of translate of a single basis function that is radially symmetric a bout its center. () = | − | S ( ) = is determined • Problems in Continuously differentiability of S result to the following form: S = 2 + − 2 c≠0 Which is a linear combination of translate of the hyperbola basis function. 17 Accurate representation of a topographic profile in more than one dimensional space S , = − 2 + − 2 S , = S , = S , = 2 + − 2 + − 2 2 + || − ||2 S , = = 18 3.5 RBF categories: • We have two kinds of RBF methods 1. Basis RBF 2. Augmented RBF • RBF basic methods: n distinct data points { } & corresponding data values { }, • The basic RBF interpolant is given by = − = = ( − ) • Micchelli gave sufficient conditions for φ(r) to guarantee that the matrix A is unconditionally nonsingular. RBF method is uniquely solvable. 19 Def: A function ∶ 0, ∞ → ℛ is completely monotone on[0,∞] if : 1. [0, ∞) 2. ∞ (0, ∞) 3. −1 () ≥ 0; r>0 ; 20 Types of basis function: • Infinitely smooth RBF • Piecewise smooth RBF 21