Jump to content

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

From Wikibooks, open books for an open world

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

and


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



i.e.



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]

Let



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



Hence,



so



Max of T_n is 1

[edit | edit source]

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


,


Then,




Thus .


Now, since is real for ,



Hence,


Show T_n(1)=1

[edit | edit source]

Let , then



Using our formula we have,



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