Numerical Analysis Practice Problems


Download Numerical Analysis Practice Problems


Preview text

NUMERICAL ANALYSIS PRACTICE PROBLEMS
JAMES KEESLING
The problems that follow illustrate the methods covered in class. They are typical of the types of problems that will be on the tests.
1. Solving Equations Problem 1. Suppose that f : R → R is continuous and suppose that for a < b ∈ R, f (a) · f (b) < 0. Show that there is a c with a < c < b such that f (c) = 0.
Problem 2. Solve the equation x5 − 3x4 + 2x3 − x2 + x = 3. Solve using the Bisection method. Solve using the Newton-Raphson method. How many solutions are there?
Problem 3. Solve the equation x = cos x by the Bisection method and by the NewtonRaphson method. How many solutions are there? Solve the equation sin(x) = cos x by the Bisection method and by the Newton-Raphson method. How many solutions are there?
Problem 4. Let h be a continuous function h : Rn → Rn. Let x0 ∈ Rn. Suppose that hn(x0) → z as n → ∞. Show that h(z) = z.
Problem 5. Solve the equation x4 = 2 by the Newton-Raphson method. How many real solutions are there? For which starting values x0 will the method converge?
Problem 6. Suppose that f : R → R is continuous and that f (z) = 0. Suppose that f (z) = 0. Let g(x) = x − ff((xx)) . Show that there is an ε > 0 such that for any x0 ∈ [z − ε, z + ε], gn(x0) → z as n → ∞
Problem 7. Show that the Newton-Raphson method converges quadratically. That is, suppose that the fixed point is z and that the error of the nth iteration is |xn − z| = h, then |xn+1 − z| ≈ h2 for h small enough.
1

2

JAMES KEESLING

2. Iteration and Chaos
There are many circumstances where iteration does not lead to a fixed point. The simplest example is that of the quadratic family of maps fµ(x) = µ · x · (1 − x) where 0 ≤ µ ≤ 4 and 0 ≤ x ≤ 1. For some values of µ0 and x0 the iterates fµn0(x0) will converge to a point. For some choices, the iterates will converge to a periodic set of points. For some, the iterates will not converge at all, but exhibit more random or chaotic behavior. The full range of behavior can be represented by the bifurcation diagram in Figure 1 and in more detail in the critical parts of the diagram in Figure 2.
We will not go into all of the details of these diagrams, but we will cover Sharkovsky’s theorem which many see as the fundamental theorem of Chaos Theory.

1.0 0.8 0.6 0.4 0.2

1

2

3

4

Figure 1. Bifurcation diagram for the quadratic family with 0 ≤ µ ≤ 4.

NUMERICAL ANALYSIS PRACTICE PROBLEMS

3

1.0 0.8 0.6 0.4 0.2

3.6

3.7

3.8

3.9

4.0

Figure 2. Bifurcation diagram for the quadratic family with 3.5 ≤ µ ≤ 4.
Problem 8. Show that if 0 ≤ µ ≤ 1, then fµn(x) → 0 as n → ∞ for all 0 ≤ x ≤ 1.
Problem 9. Assume that fµ(x) = µ·x·(1−x). Show that if 1 ≤ µ ≤ 3, then fµn(x) → 1− µ1 as n → ∞ for all 0 < x < 1.
Problem 10. Suppose that f : [a, b] → R is continuous. Suppose that there is a point x0 such that x0 has period three under f . That is, f 3(x0) = x0 and f (x0) = x0 = f 2(x0). Show that for any n, there is a z ∈ [a, b] such that z has period n under f .

4

JAMES KEESLING

3. Lagrange Polynomials
Problem 11. Determine the polynomial p(x) of degree 5 passing through the points (0, 0) , 12 , 0 , (1, 0) , 32 , 1 , (2, 0) , 52 , 0 . Determine the polynomials Li(x) for this set
of xi’s where

0 Li(xj) = 1

i=j i=j

Problem 12. Determine the VanderMonde matrix for the points 0, 91 , 29 , . . . , 1 .
4. Numerical Integration Problem 13. Determine the closed Newton-Cotes coefficients for eleven points, {a0, a1, . . . , a10}. Use these values to estimate the integral
41 −4 1 + x2 dx.

Problem 14. Suppose that {xi}ni=0 is a set of points in R such that xi = xj for all i = j. Let j0 ∈ {0, 1, . . . , n}. Give a formula for a polynomial p(x) such that p(x) has degree n and such that p(xj) = 0 for j = j0 and p(xj0) = 1.

Problem 15. Estimate 0 π sin(x2)dx using Gaussian quadrature.
Problem 16. Show that Gaussian quadrature using n + 1 points is exact for polynomials of degree k ≤ 2n + 1.

Problem 17. Explain the Romberg method for approximating the integral. If the interval is divided into 2n subintervals and the Romberg method is applied, what is the error of
the method?

Problem 18. Consider the points

x0

=

1 2

,

x1

=

3 4

,

x2

=

4 5

in [0, 1]. What should {a0, a1, a2}

be so that the estimate

1 0

f (x)dx



a0

·

f (x0)

+

a1

·

f (x1)

+

a2

·

f (x2)

is

exact

for

f (x)

a

polynomial of degree k ≤ 2?

Problem 19. Consider the points

x0

=

π 2

,

x1

=

3π 4

in [0, π]. What should {A0, A1} be

so that the estimate

π 0

f (x)dx



A0

·

f (x0)

+

A1

·

f (x1)

is

exact

for

f (x)

all

polynomials

of degree k ≤ 1?

NUMERICAL ANALYSIS PRACTICE PROBLEMS

5

Solution. Let let f (x) be a function on [0, π]. Then the estimate will be 0π p(x)dx

where p(x) is the Lagrange polynomial which is f π2 at π2 and f 34π at 34π . Now

p(x) = f

π

· p0(x) + f



· p1(x) where p0(x) =

(x



3π 4

)

and p1(x) =

(

x



π 2

)

.

Now

2

4

(

π 2



3π 4

)

(

3π 4



π 2

)

0π p(x)dx =

π 0

f

π 2

· p0(x) + f

3π 4

· p1(x) dx. This shows that A0 =

π 0

p0(x)dx

and

A1 =

π 0

p1(x)dx.

Thus,

A0

=

π

and

A1

=

0.

Problem 20. Give the Legendre polynomials up to degree 10. List the properties that determine these polynomials.
5. Numerical Differentiation
Problem 21. Determine the coefficients to compute the first derivative of f (x) = sin(x2) at a = 2 using the points {a − 2h, a − h, a, a + h, a + 2h}. Give the estimate of the derivative as a function of h. Determine the best value of h for the greatest accuracy of the answer. How many digits accuracy can you expect with this choice of h?

Problem 22. Determine the coefficients to compute the second and third derivative of f (x) = sin(x2) at a = 2 using the points {a − 2h, a − h, a, a + h, a + 2h}. Give the estimate of the second and third derivatives as functions of h. Determine the best value of h for the greatest accuracy of the answer. How many digits accuracy can you expect with this choice of h?

Problem 23. Suppose that k ≤ n. Show that when estimating the kth derivative of f (x) at a using the points {a + m0 · h, a + m1 · h, a + m2 · h, · · · , 1 + mn · h}, the result is exact for f (x) a polynomial of degree p ≤ n.
Problem 24. Estimate ddnxnf at x = a using the points {a − 4 · h, a − 2 · h, a − h, a, a + h, a + 2 · h, a + 4 · h}. For which n can this be done? What is the best h? What is the error?
6. Differential Equations Problem 25. Solve the differential equation for ddxt = f (t, x) = t · x2 with x(0) = 1. Solve using Picard iteration for five iterations. Solve using the Taylor method of order 3,4, and 5. Solve using the Euler method, modified Euler, Heun, and Runge-Kutta methods using h = 210 and n = 20. Compare the answers and the errors for each of these methods.
Problem 26. How would you go about solving the differential equation dd2t2x = −x with x(0) = 1 and x (0) = 1 with each of the methods listed in the previous problem. What changes would need to be made in the programs? Solve this problem as a linear differential equation using the linearode program. Solve on the interval [0, 1] with h = 110 .

6

JAMES KEESLING

Problem 27. Find a Taylor expansion for the solution x(t) = a0 + a1t + a2t2 + · · · for the differential equation ddxt = t · x with the boundary condition x(0) = 1. Solve for {a0, a1, a2, a3, a4, a5}. Do this by hand solving for these coefficients recursively. Solve for
the coefficients using the Taylor Method program included in your program collection. Can
you determine the general an?

Problem 28. Consider the following differential equation.
dx =t·x
dt x(0) = 1
Solve on the interval [0, 1] using h = .1. Solve using the Taylor Method of degree 4, 5, 6, 7, and 8. Compare these results with Runge-Kutta using the same h.

Problem 29. Compare Euler, Heun, and Runge-Kutta on [0, 1] using h = .1.
dx =t·x
dt x(0) = 1

Problem 30. Use the Euler method to solve the following differential equation
dx =x
dt x(0) = 1

Solve on [0, 1] using h = n1 . Do this by hand to show that xi = 1 + n1 i. What does this say about the following limit?

1n

lim 1 +

n→∞

n

Problem 31. Solve dx = M · x with M = 1 1 .

dt

01

Problem 32. Solve dx = M · x with M = 0 1 and with x(0) = 0 .

dt

−1 0

1

NUMERICAL ANALYSIS PRACTICE PROBLEMS

7

Problem 33. Convert dd2t2x + x = 0 to a first-order differential equation. Solve over the interval [0, π] with h = 1π0 assuming the initial conditions x(0) = 1 and x (0) = 0. Use the program linearode.

Problem 34. Convert dd3t3x +x = 0 to a first-order differential equation. Solve this equation over the interval [0, 1] for the initial conditions x (0) = 0, x (0) = 1, and x(0) = 0. Use the
program linearode.

7. Simulation and Queueing Theory
Problem 35. Explain the basis for the bowling program. Run some examples with different values for the probability of a strike, spare, and open frame for each frame. Discuss the results.

Problem 36. Consider a recurring experiment such that the outcome each time is in-
dependent of the previous times that the experiment was performed. Suppose that the
probability of a success each time the experiment is performed is p, 0 < p < 1. What is the probability of ten successes in 20 experiments? What is this value for p = 41 ? Use the simulation program to do 100 simulations with p = 14 and n = 20. Record the average number of successes in the 100 simulations.

Problem 37. Use the program dice to simulate rolling a die fifty times. Simulate tossing a coin fifty times using the program coin.

Problem 38. Simulate rolling ten dice using the dice program. Do this twenty times, compute the sum of the dice each time, and record the results.

Problem 39. Assume a queueing system with Poisson arrival rate of α and a single server

with an exponential service rate σ. Assume that σ > α > 0. This is an M/M/1/F IF O

queue. Determine the steady-state probabilities for n, {pn}∞ n=0 for this system. Determine

the expected number of customers in the system, E[n] = n =

∞ n=0

npn.

The

solutions

are

p = α n · 1 − α ∞ and E[n] = ( ασ ) .

n

σ

σ n=0

(1

−(

α σ

))

Problem 40. Use the Queue program to simulate a queueing system for M/M/1/F IF O
with α = 9 and σ = 10. Simulate a queueing system for M/M/2/F IF O with α = 9 and σ = 10. How do the results compare with the theoretical calculations for {pn}∞ n=0 in each of these cases?

8

JAMES KEESLING

Problem 41. Suppose that points are distributed in an interval [0, t] as a Poisson process with rate λ > 0. Show that the probability of the number of points in the interval being k is given by the following Poisson Distribution.
(λ · t)k exp(−λt)
k!

Problem 42. Assume that you have a program that will generate a sequence of independent random numbers from the uniform distribution on [0, 1]. Your calculator has a program that is purported to have this property. It is the rand() function. Determine a program that will generate independent random numbers from the exponential waiting time with parameter α. The probability density function for this waiting time is given by f (t) = α · e−α·t and the cumulative distribution function is given by F (t) = 1 − e−α·t.

Problem 43. Suppose that there are an infinite number of servers in the queueing system
M/M/∞. Suppose that the arrival rate is α and the service rate for each server is σ. Determine the steady-state probabilities {pn}∞ n=0 for this system. Explain how this could be used to model the population of erythrocytes in human blood. What would α and σ be
in this case? Determine approximate numerical values for α and σ in this case.

Problem 44. In Gambler’s Ruin two players engage in a game of chance in which A wins a dollar from B with probability p and B wins a dollar from A with probability q = 1 − p. There are N dollars between A and B and A begins the n dollars. They continue to play the game until A or B has won all of the money. What is the probability that A will end up with all the money assuming that p > q. Assume that p = 2308 which happens to be the house advantage in roulette. What is the probability that A will win all the money if n = $100 and N = $1, 000, 000, 000? Assume that p = 2308 which happens to be the house advantage in roulette. What is the probability that A will win all the money if n = $10 and N = $100? Estimate this by Monte-Carlo simulation using the gamblerruin program in your calculator library.
Problem 45. Suppose that Urn I is chosen with probability 21 and Urn II is also chosen with probability 12 . Suppose that Urn I has 5 white balls and 7 black balls and Urn II has 8 white balls and 3 black balls. After one of the urns is chosen, a ball is chosen at random from the urn. What is the probability that the urn was Urn I given that the ball chosen was white?

Problem 46. A test for a disease is positive with probability .95 when administered to a person with the disease. It is positive with probability .03 when administered to a person not having the disease. Suppose that the disease occurs in one in a million persons. Suppose that the test is administered to a person at random and the test is positive. What is the

NUMERICAL ANALYSIS PRACTICE PROBLEMS

9

probability that the person has the disease. Solve this exactly using Bayes’ Theorem. Estimate the probability by Monte-Carlo simulation using the program medicaltest in your calculator library.

Problem 47. Let f : [a, b] → [a, b] be continuous. Show that n1 ·

n i=1

f

((b



a)·rand()+a)

·

(b − a) converges to ab f (x)dx as n → ∞. This limit is the basic underlying principle of

Monte-Carlo simulation.

8. Cubic Splines
Problem 48. Determine the natural cubic spline through the points {(0, −1), (1, 0), (2, 2), (3, 0), (4, −2)}. Give the cubic polynomial for the spline on each of the intervals {[0, 1], [1, 2], [2, 3], [3, 4]}.

Problem 49. Let S(x) be the natural cubic spline over the interval [x0, xn] determined
by the knots {(x0, y0), (x1, y1), . . . , (xn, yn)}. Let Si(x) be the cubic polynomial for the
spline over the interval [xi, xi+1]. Give the equations to determine the coefficients for Si(x) = ai + bi(x − xi) + ci(x − xi)2 + di(x − xi)3 for i ∈ {0, 1, 2, . . . , n − 1}.

Preparing to load PDF file. please wait...

0 of 0
100%
Numerical Analysis Practice Problems