¢
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.
¢
Why is it important to know
the precision of the machine you are using?
So that you do not try to obtain a precision that
is impossible for the machine to attain.
¢
What is interpolation?
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.
¢
What is extrapolation?
See above; if the point is between
a and m the process is interpolation. If the point is outside, it is
extrapolation.
¢
What is curve fitting? Is it the same as interpolation?
Interpolation should not be confused with function (or curve) fitting Function
fitting allows constraining the fitted function independeltly from the sample
points. As a result, fitted functions are more stable than interpolated
functions.
¢
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.
¢
What is the Lagrange
interpolation polynomial? Do not given an equation, just provide a
description.
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.
¢
The text discusses three
algorithms used to compute the values of the Lagrange interpolation
polynomial. List these algorithms below.
Ø
________________________________________________________
Ø
________________________________________________________
Ø
________________________________________________________
Direct
implementation of Lagrange's formula, Neville's algorithm, Newton’s
algorithm
¢
Describe the problem(s)
associated with higher-order polynomials.
They fluctuate wildly. They do go through the points specified, but at
others they may not even come close.
¢
Describe
the development of the cubic spline in
terms of how it is constructed.
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.
¢
The text provides some suggestions for the use of polynomial
interpolation algorithms. For
each feature listed below state the recommended algorithm from the following
choices:
A. Neville
B. Lagrange C.
Newton D. Cubic Spline
E.Burlisch-Stoer.
Place the letter
corresponding to the correct algorithm in the space provided.
|
Feature |
Correct Algorithm (letter orresponding to) |
|
Error estimate desired |
A |
|
Couple of sample points |
B |
|
Medium to large number of sample points |
A |
|
Many efvaluations on fixed sample |
C |
|
Keep curvature under constraint |
D |
|
Function hard to reproduce |
E |
¢
Describe the following
algorithms for finding the zeros of functions
Ø
Bisection Algorithm
Probably the simplest root finding algorithm. It consists of guessing 2 root bracketing values that result in differing signs for the value of the
function at the points. The interval is successively divided – as long as signs differ on a interval then we know that at least one root is on the
interal.
Ø
Newton’s Algorithm
Guess the root. Find the
value of the function at the point.
Find the slope of the
tangent to the curve at that point (the first derivative).
Find the point where the
tangent intersects the x axis.
Repeat.
Ø
Secant Algorithm
To improve the slow convergence of the bisection method, the secant method assumes that the function is approximately linear in the local
region of interest and uses the zero-crossing of the line connecting the limits of the interval as the new reference point. The next iteration
starts from evaluating the function at the new
reference point and then forms another line. The process is repeated until the
root is found.
¢
Newton’s method in some cases is very fast. List a situation in which
you would not want to
use Newton’s method.
When you do not have a
good estimate of the location of the root or roots.