Exam 1 Review

Exam 1 will be in the DMS106 computer lab. The first part of the exam will be without computers; the second part you will use a computer. Do not type or use the mouse until the first part of the quiz has been collected. This review sheet has been prepared to help focus your studying. The exact exam will have fewer and possibly some different questions.

Non-Computer Part

Do not use the computer in any way for this part of the quiz.

State Taylor's theorem with remainder for a scalar function in one variable.
State Newton's method for finding roots of a scalar function in one variable.
State the power method for finding the eigenvalue with largest magnitude.
State the trapezoid method for computing a definite integral.
Explain what it means for an iterative scheme to be quadratically convergent.
Prove that Newton's method is quadratially convergent.
Define the condition number cond(A) of a matrix A.
Suppose Ax = b and let x* be an approximation to x with residual r = b − A x*. Show that
|x − x*|/|x| ≤ cond(A) |r|/|b|.
Find the 1-norm and ∞-norm of a given matrix A and a vector x.
Show that a symmetric matrix must have real eigenvalues.
Show that the power method converges to the eigenvalue of largest magnitude. You may assume A is an n by n matrix and has n distinct eigenvalues such that the eigenvalue of largest magnitude is unique.
Suppose P(h) is an approximation to f(3) with an error term of the form
P(h) = f(3) + τ h³ + O(h⁵)
where τ is an unknown constant. Find constants α and β such that
α P(3h) + β P(h) = f(3) + O(h⁵).
State what it means for a matrix A to be diagonally dominant.
State Jacobi's iterative method for solving Ax = b.
Prove that if A is diagonally dominant then Jacobi's iterative method converges.
State Euler's explicit method for solving the ordinary differential equation y' = f(t,y) with initial value y(0) = y₀.

Computer Part

Please use the Ubuntu virtual machine for this part of the quiz. You may also use your notes and textbooks as well as use online resources such as Wikipedia and Google. However, do not use email or any other messaging service. Following each question are directions for how to electronically submit your answers where program.c is the name of your program and output.txt is an output file obtained by running the program with the command ./a.out >output.txt. If you wish to change any part of your submission simply the appropriate submit command again. You may check each of your submissions with the command

        /nfs/home/ejolson/opt/bin/submit -pn

where n is equal the number used in submit command.

Write or modify a C computer program to compute and print out the sum
S(n) = 1 + 1/2 + 1/3 + 1/4 + … + 1/n
for n equal to 10, 100 and 1000. Please submit your program and the output using the commands
```
	/nfs/home/ejolson/opt/bin/submit -q1 program.c
	/nfs/home/ejolson/opt/bin/submit -q2 output.txt
```
Write or modify a C computer program to implement Newton's method and use it to approximate the solution cos(x) = x starting with an initial guess of x⁰ = 1. Print the first 5 iterations of the method. Please submit your program and the output using the commands
```
	/nfs/home/ejolson/opt/bin/submit -q3 program.c
	/nfs/home/ejolson/opt/bin/submit -q4 output.txt
```
Write or modify a C computer program to use the trapezoid quadrature method to approximate the definite integral
∫₀³ exp(−x²) dx
using n = 10 subdivisions. Please submit your program and the output using the commands
```
	/nfs/home/ejolson/opt/bin/submit -q5 program.c
	/nfs/home/ejolson/opt/bin/submit -q6 output.txt
```
Write or modify a C computer program to use the power method to approximate the eigenvalue with the largest magnitude for the matrix
```
    [1    2    3]
    [           ]
A = [4    5    6]
    [           ]
    [7    8    9]
```
Take the initial vector x⁰ = (1, 1, 1) and print the first 5 iterations of the method. Please submit your program and the output using the commands
```
	/nfs/home/ejolson/opt/bin/submit -q7 program.c
	/nfs/home/ejolson/opt/bin/submit -q8 output.txt
```
Write or modify a C computer program to use Euler's explicit method for finding y(2) where y(t) solves the ordinary differential equation
y' = cos(t+y)
with initial condition y(0)=0. Run your program with n = 100 time steps of size h = 2 / n and print the resulting value of y(2). Submit your program and the output using the commands
```
	/nfs/home/ejolson/opt/bin/submit -q9 program.c
	/nfs/home/ejolson/opt/bin/submit -q10 output.txt
```

Tue Oct 14 14:55:35 PDT 2014