Math/CS 466/666

466/666 NUMERICAL METHODS I (3+0) 3 credits

Instructor  Course Section                       Time            Room
------------------------------------------------------------------------
Eric Olson  Math/CS 466/666 Numerical Methods I  TR 4:30-5:45pm  DMSC106

Course Information

Instructor:

Eric Olson

email:

ejolson at unr dot edu

Office:

Tuesday and Thursday at 3pm in DMS 238 and by appointment.

Homepage:

http://fractal.math.unr.edu/~ejolson/466/

Assistant:

Jordan Blocher

Jordan's email:

jordanblocher at gmail dot com

Required Texts:

Richard Burden, Douglas Faires and Annette Burden, Numerical Analysis, 10th Edition, Cengage Learning, 2015.

Supplemental Texts on Numerical Methods:

Justin Solomon, Numerical Algorithms: Methods for Computer Vision, Machine Learning and Graphics, CRC Press, 2015.

David Kincaid and Ward Cheney, Numerical Analysis: Mathematics of Scientific Computing, 3rd Revised Edition, Pure and Applied Undergraduate Texts, American Mathematical Society, 2002.

Joe Hoffman and Steven Frankel, Numerical Methods for Engineers and Scientists, Second Edition, CRC Press, 2001.

Classic Texts on Numerical Methods:

Kendall Atkinson, An Introduction to Numerical Analysis, Second Edition, Wiley, 1989.

Richard Hamming, Numerical Methods for Scientists and Engineers, Second Edition, Dover, 1986.

Eugene Isaacson, Analysis of Numerical Methods, Revised Edition, Dover Books on Mathematics, 1993.

Supplemental Texts on Computer Programming:

JTC1/SC22/WG14, C99 Programming Standard, ISO/IEC, 2007.

Simon Long, Learn to Code with C, MagPi, 2017.

Richard Smedley, Conquer the Command Line, MagPi, 2016.

Classic Texts on Computer Programming:

Brian Kernighan, Dennis Ritchie, C Programming Language, 2nd Edition, Prentice Hall, 1988.

Brian Kernighan, Rob Pike, Unix Programming Environment, Pretice-Hall Software Series, 1984.

Student Learning Outcomes

1. Students will be able to implement a numerical method to solve a nonlinear equation using the bisection method and Newton's method.

2. Students will be able to solve linear systems using direct and iterative methods.

3. Students will be able to construct interpolating functions.

Announcements

[17-Dec-2018] Answers to Programming Project 2

[13-Dec-2018] Final Exam

[12-Dec-2018] Answers to Quiz 2 and Exam Part 2

[08-Dec-2018] Answers to Written Exam Part I

[05-Dec-2018] Answers to Programming Project 1

[30-Nov-2018] Programming Project 2

[11-Dec-2018] Computer Exam Part II

• Given a differential equation y'=f(x,y) with initial value y(x₀)=y₀. Fill in the missing routines in the provided program skeleton which uses RK4 to approximate the value of y(x_N) for x_N=b with b and N specified.

• Given A∈R^n×n and b∈Rⁿ, fill in the missing routines in the provided program skeleton which uses Gaussian elimination with partial pivoting to find the factorization A=PLU and then solve linear system Ax=b.

• Consider the first-order approximation of the derivative given by
  f'(x) ≈ D_h(f)   where   D_h(f) = (f(x+h)-f(x))/h.

  Fill in the missing routines in the provided program skeleton for a second-order approximation R_h(f) using Richarson extrapolation of the form R_h(f) = α D_h(f) + β D_2h(f) for a suitable choice of α and β. Note that the exact details of the required extrapolation may change for the problem given on the actual exam.

[06-Dec-2018] Written Exam Part I

• Statement of Taylor's theorem including all hypothesis and an exact form of the remainder term.

• Statement of Newton's method.

• Use of Taylor's theorem to show that Newton's method is quadratically convergent.

• Explain why the number of correct digits in the approximation about doubles with each iteration of Newton's method.

• Know how to construct Newton's table of divided differences.

• Know how to read off an interpolating polynomial from a table of divided differences.

• Use Taylor's theorem to show that (f(x+h)-f(x-h))/(2h) approximates f'(x) to O(h²) and that (f(x+h)-2f(x)+f(x-h))/h² approximates f''(x) to O(h²). Be prepared to analyze similar approximations of derivatives.

• Given an approximation of g(x) denoted by approx(h,x) that is accurate to O(h^k) use Richardson's extrapolation to find an approximation that is accurate to at least O(h^k+1) involving approx(h,x) and approx(2h,x). Be prepared to find similar extrapolations, for example, involving approx(h,x) and approx(h/3,x) and so forth.

• Statement of the RK4 method from memory.

• Consider the row elimination and permutation matrices given by
  E_i,j = [ r_i ← r_i − α r_j ]   and   P_i,j = [ r_i ↔ r_j ]

  Find i, j, k and l such that E_3,2 P_1,2 = P_i,j E_k,l.

[20-Nov-2018] Quiz 2

• Given a differential equation y'=f(x,y) with initial value y(x₀)=y₀. Write a taylor2 time step for a specified function f to complete the missing routine in the provided program skeleton.

• Given values of x_i for i = 1,2,...,n find weights w_i such that the quadrature
  ∫_-1¹ f(x) dx ≈ Σ w_i f(x__i)

  is exact for polynomials up to degree n-1. Then complete the missing routines in the provided program skeleton to approximate the specified integral.

• Fill in the missing routines of the provided program skeleton for Newton's method to find a root of the equation f(x)=0 with a specified function f and starting value x₀.

[06-Nov-2018] Programming Project 1

[01-Nov-2018] Web Campus

[18-Oct-2018] Quiz 1

• Statement of Taylor's theorem including all hypothesis and an exact form of the remainder term.

• Statement of Newton's method.

• Use of Taylor's theorem to show that Newton's method is quadratically convergent.

• Explain why the number of correct digits in the approximation about doubles with each iteration of Newton's method.

• Know how to construct Newton's table of divided differences.

• Know how to read off an interpolating polynomial from a table of divided differences.

• Use Taylor's theorem to show that (f(x+h)-f(x-h))/(2h) approximates f'(x) to O(h²) and that (f(x+h)-2f(x)+f(x-h))/h² approximates f''(x) to O(h²). Be prepared to analyze similar approximations of derivatives.

• Given an approximation of g(x) denoted by approx(h,x) that is accurate to O(h^k) use Richardson's extrapolation to find an approximation that is accurate to at least O(h^k+1) involving approx(h,x) and approx(2h,x). Be prepared to find similar extrapolations, for example, involving approx(h,x) and approx(h/3,x) and so forth.

[02-Oct-2018] Homework 1 Due

[28-Aug-2018] Introductory Lecture

Extra Credit

Problem 1

Theorem 3.3. Suppose x₀, x₁, . . . x_n are distinct numbers in the interval [a,b] and f ∈ Cⁿ⁺¹[a,b]. Then, for each x in [a,b], a number ξ(x) (generally unknown) between min{x, x₀, x₁, . . . , x_n} and the max{x, x₀, x₁, . . . , x_n} and hence in (a,b), exists with
f(x)=P(x)+(1/(n+1)!) f⁽ⁿ⁺¹⁾(ξ(x)) (x−x₀)(x−x₁) . . . (x−x_n),

where P(x) is the interpolating polynomial given by

P(x)= f(x₀)L_n,0(x)+f(x₁)L_n,1(x)+ . . . +f(x_n)L_n,n(x).

Sample Code

• aug30 Fixed Point Iteration
• sep04 Newton's Method
• sep06 Newton's Method
• sep11 Machine Epsilon
• sep13 Aitken's Acceleration
• sep18 Muller's Method
• sep20 Divided Differences (incomplete)
• sep25 Divided Differences
• sep27 Approximation of First Derivative
• oct02 Approximation of Second Derivative
• oct04 Rounding Error (incomplete)
• oct09 Rounding Error
• oct11 Extrapolation of Riemann Sums
• oct16 Weights for Newton-Cotes
• oct18 Newton-Cotes Quadrature
• oct25 Orthogonal Polynomials
• nov01 Adaptive Gauss Quadrature
• nov06 Taylor's ODE Integrator
• nov08 Trapezoid and RK2 Integrator
• nov13 RK4 Integrator
• nov15 RK2/4 Adaptive Integrator
• nov27 Gaussian Elimination (incomplete)
• nov29 Gaussian Elimination
• dec04 LU backsubstitution

Homework and Programming Assignments

• Homework 1 (due October 2):
  • Chapter 2.2 # 1abcd, 2ab, 26
  • Chapter 2.3 # 6abcdef, 8, 30
  • Chapter 2.4 # 10
  • Chapter 2.5 # 3, 4
  • Chapter 2.6 # 4abefh
• Homework 2 (due November 1):
  • Chapter 3.4 # 1ac, 2d, 3ac, 4d, 5abc, 11ab
• Programming Project 1 (due November 29) (answers)
• Programming Project 2 (due at final exam) (answers)

Grading

     2 Quizzes                 20 points each
     1 Exam                    60 points
     1 Final Exam             100 points
     2 Homework Assignments    20 points each
     2 Programming Projects    20 points each
     1 In-class Lab Work       20 points
    ------------------------------------------
                              300 points total

    Grade        Minimum Percentage
      A                 90 %
      B                 80 %
      C                 70 %
      D                 60 %

Final Exam

The final exam is scheduled for Thursday, December 13 from 4:50-6:50pm in DMSC 106.

Equal Opportunity Statement

Academic Conduct