Jump to content

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

From Wikibooks, open books for an open world

Problem 1

[edit | edit source]

Let be continuous on . A polynomial of degree not greater than is said to be a best (or Chebyshev) approximation to if minimizes the expression

Problem 1a

[edit | edit source]

Show that a sufficient condition for to be a best approximation is that there exists points such that

.

Solution 1a

[edit | edit source]

Assume there exists such that



Then for



Let and .


Then takes on the sign of since



Since changes signs times (by hypothesis), has zeros.


However and thus can only have at most zeros. Therefore and

Problem 1b

[edit | edit source]

Compute the best linear approximation to . [Hint: Drawing a line through the parabola will allow you to conjecture where two points of oscillation must lie. Use conditions from (a) to determine the third point and coefficients of .]

Solution 1b

[edit | edit source]

First we need to find the roots of in [0,1], which are given by



So our points at which to interpolate are




Our linear interpolant passes through the points and , which using point-slope form gives the equation



or


Problem 2

[edit | edit source]

We will be concerned with the least squares problem of minimizing

.

Here is an matrix of rank (which implies ) and is the Euclidean vector norm. Let

be the QR decomposition of . Here are respectively .

Problem 2a

[edit | edit source]

Show that the solution of the least squares problem satisfies the QR equation and that the solution is unique. Further show that .


Solution 2a

[edit | edit source]

The two problems are equivalent

[edit | edit source]

First notice


Then we can write


Note that multiplying by orthogonal matrices does not affect the norm.


Then solving is equivalent to solving , which is equivalent to solving . Note that a solution exists and is unique since is n-by-n and non-singular.

Show that

[edit | edit source]

Similarly

Then

, or simply , as desired.

Problem 2b

[edit | edit source]

Use the QR equation to show that the least squares solution satisfies the normal equations .

Solution 2b

[edit | edit source]

Problem 3

[edit | edit source]

Let be real symmetric and let be given. For , define as the linear combination of the vectors with the coefficient of equal to one and orthogonal to the vectors ; i.e.

        

Problem 3a

[edit | edit source]

Find formulas for and

Solution 3a

[edit | edit source]

Using Gram Schmidit, we have

Problem 3b

[edit | edit source]

Show that Where do you use the symmetry of ?

Solution 3b

[edit | edit source]

Since

, if , then


Since is symmetric,


From hypothesis,

Also from hypothesis,


Using the above results we have,

Problem 3c

[edit | edit source]

For which non-zero vectors does hold?

Solution 3c

[edit | edit source]

For ,


If , then


Since is a scalar, is an eigenvector of .