Jump to content

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

From Wikibooks, open books for an open world

Problem 1

[edit | edit source]

Let be distinct real numbers, and consider the matrix

Prove that can be expressed as

where the column vector generates a polynomial

satisfying

You may cite anything you know about polynomial interpolation to justify that is nonsingular.

Solution 1

[edit | edit source]

We want to show that



or equivalently the th, th entry of is for and for i.e.

First notice that

Also notice that

Hence,

Problem 2

[edit | edit source]

Let be a real matrix of order with eigenvalues and linearly independent eigenvectors .

Suppose you want to find an eigenvector corresponding to the eigenvalue and you are given such that

Specify a numerical algorithm for finding and give a convergence proof for this algorithm demonstrating that it is convergent under appropriate circumstances

Solution 2

[edit | edit source]

Shifted Inverse Power Method

[edit | edit source]

Let

Then,

which implies

Since shifting the eigenvalues and inverting the matrix does not affect the eigenvectors,


Assume for all . Generate to find . Start with arbitrary such that .


For 
  
  
   (Rayleigh quotient)
End



Convergence of Power Method

[edit | edit source]

If , for all , then will be dominated by .


Since are linearly independent, they form a basis of . Hence,


From the definition of eigenvectors,


To find a general form of , the approximate eigenvector at the kth step, examine a few steps of the algorithm:


From induction,

Hence,

Comparing a weighted and ,

since by assumption.

The above expression goes to as since , for all . Hence as grows, is parallel to . Because , it must be that .


Problem 3

[edit | edit source]

Suppose A is an upper triangular, nonsingular matrix. Show that both Jacobi iterations and Gauss-Seidel iterations converge in finitely many steps when used to solve .

Solution 3

[edit | edit source]

Derivation of Iterations

[edit | edit source]

Let where is a diagonal matrix, is a lower triangular matrix with a zero diagonal and is an upper triangular matrix also with a zero diagonal.


The Jacobi iteration can be found by substituting into , grouping , and solving for i.e.



Since by hypothesis, the iteration is



Similarly, the Gauss-Seidel iteration can be found by substituting into , grouping , and solving for i.e.



Since by hypothesis, the iteration has identical from as Jacopi:


Convergence in Finite Number of Steps

[edit | edit source]

Jacobi and Gauss-Seidel are iterative methods that split the matrix into , , and : Diagonal, Upper (everything above the diagonal), and Lower (everything below the diagonal) triangular matrices, respectively. Their iterations go as such


(Gauss-Seidel)
(Jacobi)


In our case is upper triangular, so is the zero matrix. As a result, the Gauss-Seidel and Jacobi methods take on the following identical form



Additionally, can be written



Subtracting from we get



In our problem, is diagonal and is upper triangular with zeros along the diagonal. Notice that the product will also be upper triangular with zeros along the diagonal.

Let ,



Also, let be the related matrix



Where is , is , and is .


Finally, the product (call it (1)) is



Here is almost identical in structure to , except that its diagonal elements are zeros.

At this point the convergence in steps (the size of the starting matrix) should be apparent since is just where and each time is multiplied by , the k-th super-diagonal is zeroed out (where k=0 is the diagonal itself). After applications of , the result will be the zero matrix of size .

In brief, is the zero matrix of size .


Therefore , i.e. the Jacobi and Gauss-Seidel Methods used to solve converge in steps when is upper triangular.

Examples of (1)

[edit | edit source]