Numerical Methods Qualification Exam Problems and Solutions (University of Maryland)/August 2006

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Problem 1[edit | edit source]

Consider the definite integral

Let denote the approximation of by the composite midpoint rule with uniform subintervals. For every set


Let be defined by


Assume that .

Problem 1a[edit | edit source]

Show that the quadrature error satisfies

Hint: Use integration by parts over each subinterval .

Solution 1a[edit | edit source]

Integrating by parts over arbitrary points and gives

Since is defined on we use


Using the first interval we get

And for the second we get

Since these apply to arbitrary half-subintervals, we can rewrite equation with the its indecies shifted by one unit. The equation for the interval is

Combining and and writing it in the same form as the integration by parts, we have

Then our last step is to sum this over all of our subintervals, noting that

Problem 1b[edit | edit source]

Derive a sharp bound on the error of the form

for every .

Here denotes the maximum norm over . Recall that the above bound is sharp when the inequality is an equality for some nonzero .

Solution 1b[edit | edit source]

Applying the result of part (a), the triangle inequality, and pulling out the constant , we have,

is some constant less than infinity since is compact and is continuous on each of the finite number of intervals for which it is defined.

The above inequality becomes an equality when

where is any constant.

Problem 2[edit | edit source]

Consider the (unshifted) method for finding the eigenvalues of an invertible matrix

Problem 2a[edit | edit source]

Give the algorithm.

Solution 2a[edit | edit source]

The QR algorithm produces a sequence of similar matrices whose limit tends towards being upper triangular or nearly upper triangular. This is advantageous since the eigenvalues of an upper triangular matrix lie on its diagonal.

i = 0   
A_1 = A 
while ( error > tolerance  )   
   A_i=Q_i R_i  (QR decomposition/factorization)
   A_{i+1}=R_i Q_i (multiply R and Q, the reverse multiplication)
   i=i+1 (increment)

Problem 2b[edit | edit source]

Show that each of the matrices generated by this algorithm are orthogonally similar to .

Solution 2b[edit | edit source]

From the factor step (QR decomposition) of the algorithm, we have

which implies

Substituting into the reverse multiply step, we have

Problem 2c[edit | edit source]

Show that if is upper Hessenberg then so are each of the matrices generated by this algorithm.

Solution 2c[edit | edit source]

A series of Given's Rotations matrices pre-multiplying , a upper Heisenberg matrix, yield an upper triangular matrix i.e.

Since Givens Rotations matrices are each orthogonal, we can write


If we let , we have , or more generally for


In each case, the sequence of Given's Rotations matrices that compose have the following structure

So is upper Hessenberg.

From the algorithm, we have

We conclude is upper Hessenberg because for the th column of is a linear combination of the first columns of since is also upper Hessenberg.

Problem 2d[edit | edit source]


For this the sequence has a limit. Find this limit. Give your reasoning.

Solution 2d[edit | edit source]

The eigenvalues of can be computed. They are and . Furthermore, the result of matrix multiplies in the algorithm shows that the diagonal difference, , is constant for all .

Since the limit of is an upper triangular matrix with the eigenvalues of on the diagonal, the limit is

Problem 3[edit | edit source]

Let be symmetric and positive definite. Let . Consider solving using the conjugate gradient method. The iterate then satisfies

for every ,

where denotes the vector A-norm, is the initial residual, and


Problem 3a[edit | edit source]

Prove that the error is bounded by


where is any real polynomial of degree or less that satisfies . Here denotes the matrix norm of that is induced by the vector A-norm.

Solution 3a[edit | edit source]

We know that for every , so if we can choose a such that


then we can solve part a.

Rewrite r^(0)[edit | edit source]

First note from definition of

Rewrite Krylov space[edit | edit source]

Therefore, we can rewrite as follows:

Write y explicitly[edit | edit source]

We can then write explicitly as follows:

Substitute and Apply Inequality[edit | edit source]

We substitute into the hypothesis inequality and apply a norm inequality of matrix norms to get the desired result.

Problem 3b[edit | edit source]

Let denote the Chebyshev polynomial. Let and denote respectively the smallest and largest eigenvalues of . Apply the result of part (a) to

to show that


You can use without proof the fact that


where denotes the set of eigenvalues of , and the facts that for every the polynomial has degree , is positive for , and satisfies


Solution 3b[edit | edit source]

Overview[edit | edit source]

We want to show that

Maximize Numerator of p_n(z)[edit | edit source]

By hypothesis,

Since only the numerator of depends on , we only need to maximize the numerator in order to maximize . That is find

Rewrite T_n[edit | edit source]

Let . Then



Max of T_n is 1[edit | edit source]

Denote the argument of as since the argument depends on . Hence,



Thus .

Now, since is real for ,


Show T_n(1)=1[edit | edit source]

Let , then

Using our formula we have,

In other words, if , achieves its maximum value of .