What
is the difference between interpolation and extrapolation?
Interpolation is a technique that allows the examination of a function over the range covered by a set of points at which the function’s values are known. These points are called the sample points. Interpolation is useful to compute a function whose evaluation is time-coming. With interpolation it suffices to compute the function’s values for a small number of well-chosen sample points. Then, evaluation of the function between the sample points can be made with interpolation.
Given that a value of a function is known at a number of points from a to m and an analytic expression is not available for the funtion. We want to find the value of the function at another point.
If the point is between a and m the process is interpolation. If the point is outside, it is extrapolation.
Numerical methods is one of the components of the field of computer science.
Define this
component.
The following is a quote from my manual (Related Topics, The Field) which is quoted from the Association for Computing Machinery.
General methods for efficiently and accurately using computers to solve equations from mathematical models are central to this area. The effectiveness and efficiency of various approaches to the solution of equations, and the development of high-quality mathematical
software are included.
I
discuss interpolation in my manual. Describe polynomial interpolation.
There are several methods used in interpolation; one difference is the type of function used. The other is the particular algorithm used to determine the function. For example, if the function is periodic, interpolation can be obtained by computing a sufficient number of coefficients of the Fourier series for that function.
In the absence of any information about the function, polynomial interpolation gives fair results. This type interpolation generally involves substituting a polynomial for the function.
Define the Lagrange interpolation polynomial.
The Lagrange interpolation polynomial is the unique polynomial of minimum degree going through the sample points. The degree of the polynomial is equal to the number of supplied points minus one.
In my
manual I state three approaches for the Lagrange interpolation polynomial. List
these approaches.
Direct implementation of Lagrange's formula
Newton's algorithm
Neville's algorithm
Describe the cubic spline interpolation approach.
A third order polynomial constrained in its derivatives at the endpoints.
A unique cubic spline is defined on each interval between two points. The
interpolated function is required to be continuous up to the second derivative
at each of the points.
In my
manual I list some situations and provide the recommended interpolation
approach. Fill
in the blanks in the table below.
|
Situation |
Recommended Interpolation Approach |
|
Error estimate desired |
Neville |
|
Couple of sample points |
Lagrange |
|
Medium to large number of sample points |
Neville |
|
Many evaluations on fixed sample |
Newton |
|
Keep curvature under constraint |
Cubic spline |
In my
manual I discuss 3 integration approaches. Describe each of these as listed
below.
Trapeze
This is a method that is not normally used in practice, merely to introduce techniques. It involves approximating the area as a series of trapezoids.
Romberg
Based on the fact that the truncation error of the trapezoidal rule is nearly proportional to the square of the integration interval.
Simpson
Uses connected parabolic segments. Replaces the function to integrate by a second order Lagrange interpolation polynomial.
Genetic Algorithms. Define the following. Be specific.
Chromosome
All living organisms consist of cells. In each cell there is the same set of chromosomes. Chromosomes are strings of DNA and serve as a model for the whole organism.
Genetic algorithms process populations of strings.
Roughly speaking, the strings of GAs that represent the problem are analogous to chromosomes in biological systems. A chromosome should in some way contain information about solution that it represents.
Crossover
Occurs after reproduction, a process for combining strings. Crossover operates on selected genes from parent chromosomes and creates new offspring.
Mutation
After a crossover is performed, mutation takes place. Mutation is intended
to prevent falling of all solutions in the population into a local optimum of
the solved problem. Mutation operation randomly changes the offspring resulted
from crossover. In case of binary encoding we can switch a few randomly chosen
bits from 1 to 0 or from 0 to 1.
Fitness Function
A function that determines "survival of the most fit"
Describe a general situation in which GAs should be
considered as a solution technique.
The Genetic Algorithm can solve problems that do not have a precisely-defined solving method, or if they do, when following the exact solving method would take far too much time. They are suitable for problems with a large solution space and many local max or min. They are useful when you do not need a precise answer, merely one that is “good enough”. You do not have to make any statements about differentiability and continuity. Continuously differentiable problems with few local optimum are usually solved most efficiently with traditional methods.
In
terms of problem solving approaches, what is a heuristic?
A rule of thumb. Many problems have no solution technique that meets limitations on time, data, and so on. Heuristics are a natural choice in these situations. They are typically used in conjunction with standard approaches.