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

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

Problem 1[edit]

Let be a real symmetric matrix of order with distinct eigenvalues, and let be such that and the inner product for every eigenvector of .

Problem 1a[edit]

Let denote the space of polynomials of degree at most . Show that



defines an inner product on , where the expression on the right above is the Euclidean inner product in

Solution 1a[edit]

Symmetry[edit]

Linearity of 1st Argument[edit]

Let




Positive Definiteness[edit]


"Zeroness"[edit]

We also need to show that if and only if .

Forward Direction (alt)[edit]

Suppose . It suffices to show . However, this a trivial consequence of the fact that (which is clear from the fact that for with degree less than and that does not lie in the orthogonal compliment of any of the distinct eigen vectors of ).

Forward Direction[edit]

Claim: If , then .


From hypothesis



where are the orthogonal eigenvectors of and all are non-zero



Notice that is a linear combination of , the coefficients of the polynomial , and the scaling coefficient of the eigenvector e.g.


Since and , this implies .

Reverse Direction[edit]

If , then

Problem 1b[edit]

Consider the recurrence



where the and are scalars and . Show that , where is a polynomial of degree

Solution 1b[edit]

By induction.

Base Case[edit]


Induction Step[edit]

Claim:


Hypothesis:

Suppose


where (respectively ) has degree (respectively ). Then for

which is as desired.

Problem 1c[edit]

Suppose the scalars above are such that and is chosen so that . Use this to show that that the polynomials in part (b) are othogonal with respect to the inner product from part (a.

Solution 1c[edit]

Since and , it is equivalent to show that for .


Since

,


it is then sufficient to show that



Claim [edit]

By induction.

Base Case[edit]

Induction Step[edit]

Assume:


Claim:


Claim [edit]

By induction.

Base Case[edit]


Induction Step[edit]

Assume:


Claim:



Problem 2[edit]

Consider the n-panel trapezoid rule for calculating the integral of a continuous function ,

where


Problem 2a[edit]

Find a piecewise linear function such that

for any continuous function such that is integrable over [0,1]. Hint: Find by applying the fundamental theorem of calculus to .

Solution 2a[edit]

Rewrite given equation on specific interval[edit]

For a specific interval , we have from hypothesis


.


Distributing and rearranging terms gives


Apply Hint[edit]

Starting with the hint and applying product rule, we get


.


Also, we know from the Fundamental Theorem of Calculus


.


Setting the above two equations equal to each other and solving for yields


Choose G'(t)[edit]

Let . Therefore since is linear



By comparing equations (1) and (2) we see that


and


.


Plugging in either or into equation (3), we get that



Hence


Problem 2b[edit]

Apply the previous result to , , to obtain a rate of convergence.

Solution 2b[edit]

Problem 3[edit]

Let denote the set of all real-valued continuous functions defined on the closed interval be positive everywhere in . Let be a system of polynomials with for each , orthogonal with respect to the inner product



For a fixed integer , let be the distinct roots of in . Let



be polynomials of degree . Show that



and that



Hint: Use orthogonality to simplify


Solution 3a[edit]

Solution 3b[edit]

Claim[edit]


Proof[edit]

Since is a polynomial of degree for all , is a polynomial of degree .


Notice that for where are the distinct roots of . Since is a polynomial of degree and takes on the value 1, distinct times