1. Introduction - IUST Personal Webpages

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

similar documents