MATH4141/MATH6651/PHYS5070
FW00
Final
examination Thursday,
Dec. 7,
Calculators may
be used as aids.
Note formula
sheet attached to exam paper.
There are a total
of 8 questions on this paper and the marks are given at the beginning of each
question..
The total number of marks on this paper are 83.
1. (20
marks)
(a) Show that two consecutive search directions
in the method of steepest descent are
orthogonal.
(b) Apply the conjugate directions method to the function 2x2 + 4xy + 6y2
- 3x + 5y + 2 taking x0 = (0, 0). Carry out steps 1, 3, 4 and 5 of the
algorithm as given on the formula sheet once
each. Do not carry out the search in step 6. Do the required searches analytically.
(c) If f(x)
is the quadratic function c + bTx + (1/2)xTAx in Rn with A a symmetric, positive-definite matrix, show that a straight line
search from an initial point x0
in the direction u (i.e. taking x = x0 + tu)
yields a minimum for f at
2. (7
marks)
(a) Use the Gerschgorin
circle theorem to estimate the location
of the eigenvalues of the matrix A
(b) If A is a square matrix with an eigenvalue s
and corresponding eigenvector x show
that the matrix A - qI has an s - q with the same eigenvector.
3. (14
marks)
(a) Show that an elementary reflector P is both a symmetric and orthogonal
matrix.
(b) Find the
elementary reflector P used in
Householder's method to reduce the matrix
to tridiagonal form. Do not
carry out the reduction to tridiagonal form.
4. (5 marks)
(a) Given the matrix A =
, the matrix ATA has eigenvectors 
. Use this information
to find two eigenvectors of the matrix AAT.
(b) Explain how the singular value decomposition
of a matrix enables you to determine the rank of the matrix.
(c) Give one example of other information can be
obtained from the singular value decomposition of a matrix?
5. (4
marks)
(a) Define the discrete fourier transform of a set of
data {yj, j = 0, 2m-1}.
(b) Explain how the data in part (a) are
reordered in order to implememt the fast fourier
transform.
(c) Define the convolution of two data sets and explain how the convolution can be
inverted using the discrete convolution
theorem.
6. (17
marks) The
Maclaurin polynomial of degree 6 for x cosec(x) is given by
(a) Use
Chebyshev economization to reduce this to a polynomial of at most degree
5. The monic Chebyshev polynomial of
degree 6 is
(b) If the maximum error in the polynomial
approximation of degree 6 given above is approximately 2.4´10-4 on
[-1, 1] what is the maximum error of the polynomial approximation derived in
part (a)?
(c) Find the [2/2]
Padé approximant for x cosec(x) using the fourth
degree Maclaurin polynomial obtained from the one given above.
(d) Compare the
location of the singularity in the Padé approximant closest to zero with the
one in x cosec(x).
7. (6
marks)
(a) Given
that Q is approximated by P with a certain error define both the absolute and relative error in this approximation.
(b) What are the advantages and disadvantages of
the Fibonacci and Golden search methods for finding the minimum of a function?
(c) What is the property of Chebyshev polynomials
that make them the optimal choice for polynomial approximations of functions.
(d) What is the advantage of using the continued fraction form of Padé
approximants?
8. (10
marks) Given a
set of basis functions {g0(x), g1(x), ..., gn(x)}
we can approximate a general function f(x) by g(x) = c0g0(x)
+ c1g1(x) + ... + cngn(x).
(a) Derive the formula for the coefficients ci,
i = 0, n that make g(x) a least squares approximation
to f(x) on the interval [a, b] with non-negative weight function w(x).
(b) Give the formula for the ci when
the basis functions gk(x) are orthogonal on
the interval
[a, b] with weight function w(x).
(c) Give two examples of orthogonal basis
functions along with the corresponding interval and weight function.
(d) What additional information besides the
interval [a, b] and weight function w(x) is required to uniquely define a set
of orthogonal polynomials?
THE END