Introduction to Numerical Methods

Instructor: Leon Kaganovskiy
Office: HNS 110 or HNS 204 (Physics Computer Lab), Office Phone: 360-5997
Office Hours:

Mon: 11-12:30 and 4-6,   Tue :  4-6 (office/computer lab HNS 204),  Wed: 11-12:30 and 4-6,  Thu :  research day,  Fri   :  4:30-6:30 (office/computer lab HNS 204)

I am available at other times by appointment.   

email: lkaganovskiy@ncf.edu - best way to ask a question.    Also if you need me ASAP:  (941) 366-6134;  (941) 961-3896

 

Book:  Elementary Numerical Analysis, 3rd Edition, Kendall Atkinson and Weimin Han, ISBN: 0-471-43337-3, Hardcover 576 pages.

Course Goals and Objectives:

This course is an interdisciplinary introduction to Numerical Methods for science students.  It covers the topics corresponding to Chapters 1-8 of the Atkinson’s book. The course focuses on  the development and mathematical analysis of practical algorithms for the basic areas of numerical analysis such as root-finding, polynomial interpolation, best mini-max interpolation, Chebyshev polynomial, least squares, splines, numerical integration and differentiation, Richardson extrapolation, Gaussian elimination with LU factorization, iterative methods, ODE methods – Euler’s, Trapezoid, Runge-Kutta, Adams-Bashforth and Adams-Moulton.  This course serves as an informal prerequisite for many Science classes which require Numerical Methods.   In addition, it introduces students to powerful computing package – Matlab.  Work required of students includes weekly homework and substantial programming projects which counts 50% of the grade.  The other 50% comes from two exams.

Minimal Prerequisites:  The course is at the intermediate - sophomore/junior level.  It should be accessible for the students in Science and Mathematics majors.  The specific prerequisites are Single Variable Calculus, Differential Equations (Calculus I Differential Equations Introduction is enough); some familiarity with computer programming, Linear Algebra (only need to know matrix manipulations for Ch6, we will not get into Eigenvalues and Eigenvectors, so the whole Linear Algebra course is NOT a prerequisite).

Programming Language:  The predominant programming languages used in numerical analysis are Fortran and MATLAB.  In this course we will focus on Matlab. Many numerical analysis programs in Matlab will be provided. For students unacquainted with MATLAB, a short introduction is available from the following sources: Matlab Tutorial Brief,   Matlab Primer (more comprehensive, but longer),   Matlab Intro Plotting,    Matlab Tutorial MIT,  or just Google it.

A student version of MATLAB can be obtained from the company Mathworks, Inc. at a somewhat reduced price (>100$). This student version is essentially the full version, without some special add-on toolboxes. Matlab is available at the second floor Physics Computer Lab. Programs in languages other than Fortran and Matlab are also sometimes acceptable, but no programming assistance will be given in the use of such languages.

Grading Policy: The final grade will be based on tests and problems, as follows:

  1. There will be two exams, and each will count 25% of the course grade. The first exam will be given approximately halfway through the semester. The second test will be given during the scheduled final examination time, and it will cover only the second half of the course.

1st exam – 1 week before Spring break, Final – exam week.     Exact dates and times will be announced in class.

  1. Homework assignments will count 50% of the course grade. Late homework will be accepted only by special permission of the instructor.

 

Attendance Policy:

There are no specific attendance credit points, but you are responsible for attending all the classes and keeping abreast of all the material presented in class.

Special Need Students:

Students with the need for special accommodations must work with the Counseling and Wellness Center, which will establish the specific accommodations and communicate them to me.

Academic Dishonesty Policy:

Any suspected instance of plagiarism will be reported to the office of the Provost and handled in accordance with the College’s policy.

 

Topics to be covered and Homework Assigned  (exact due dates will be announced in class).

This course plan may be modified during the semester. Such modifications will be announced in advance during class periods, and the students are responsible for keeping abreast of such changes. The WWW page for the course will also be used to list assignments and other notes, and students are responsible for checking this web page regularly.

Chapter 1 - Taylor Polynomials.  Just review yourself if you have trouble with Taylor expansions.

Chapter 2 - Error and Computer Arithmetic. 

                     I will only mention some examples of round-off errors, it is better to see them later in the

                        specific context of numerical problems.

Chapter 3 - Root-finding - cover in full.  

                    3.1 The Bisection Method - only 1st order accurate, but guaranteed to converge. 

                            HW:   # 1a, c (graph), 2, 7 (which one gives more accurate answers), 9, 12 (write down f(a) and f(b)); 

                    3.2 Newton's Method - 2nd order accurate.   HW:  # 2a,c, 3, 5, 6, 10 (note the order of convergence, multiplicity of the root); 

                    3.3 Secant Method.   HW: # 1, 3, 4, 6

                    3.4 Fixed Point Iterations.   HW:  # 1 (for c, use initial guess 1),  3, 5, 7, 8, 9 (take initial guess =1), 11, 14, 17

                    3.5 Ill-behaving root-finding problems.  

                            HW: # 1 (investigate both roots, speed up the convergence), 5, 6 (use eps = -0.009, -0.001, 0.001, 0.09, -0.01), 8

Chapter 4 - Interpolation and Approximation - cover in full

                    4.1 Polynomial Interpolation, Lagrange Form, Divided Difference Form.  

                            HW:  # 1, 8, 12, 13, 15, 16, 19, 20, 25, 26, 32

                    4.2 Error Analysis in Polynomial Interpolation.  HW: # 1, 4, 8 (solution is just one line), 9(solution is just one line), 11, 14, 17 (numerically)

                    4.3 Splines, Cubic Splines.   HW:  # 1, 6, 11, 20

                    4.4 Best Polynomial Approximation, Minimax Problems.  HW:  # 2, 3, 5, 7

                    4.5 Chebyshev Polynomials.   HW:  # 2, 3, 7, 9 (b - induction)

                    4.6 A Near-Minimax Approximation Using Chebyshev Polynomials.  

                            HW:  # 1, 2, 3, 4, 10 (should be just a couple of lines)

                    4.7 Least Squares Approximations.   HW:  # 2, 3 b,d,e, 6, 7, 8

Chapter 5 - Numerical Integration and Differentiation - cover in full

                    5.1 The Trapezoidal and Simpson Rules.   HW: #  2a,c,d,f, 3a,c,d,f, 8, 9a,c,d,f, 11a-c, 12

                    5.2 Error Analysis of Integration Methods.   Richardson Extrapolation - the

                            order of accuracy.  Periodic Integrands.    HW:  # 2ace, 3ace, 5ad, 7, 14, 15, 20

                    5.3 Gaussian Integration, Weighted Quadrature.   HW:  # 2adef  compare to Trapezoid and Simpson, 4bc, 6 (very short), 11

                    5.4 Numerical Differentiation.   Differentiation Using Interpolation.  The Method of

                            Undetermined Coefficients.   Errors.   HW:   # 1b, 4(do only n = 1,2), 6 (use Taylor to show better convergence),

                            7, 9bc, 13 (we only have double precision, no table, just plot)

Chapter 6 - Solution of Systems of Linear Equations - cover most of the topics

                    6.1 and 6.2 - review if you need it.   Mostly deals with matrix manipulations.

                    6.3 Gaussian Elimination.  Partial Pivoting.   HW: 3, 4, 5 (which one has better accuracy), 6c

                    6.4 LU - Factorization,  Tri-diagonal Systems.   HW: 1, 6, 7,  9, 10

                    6.5 Error and Stability in Solving Linear Systems     HW: 1, 2, 5, 6 (very short), 7a,b

                    6.6 Iterations Methods - Jacobi, Gauss-Seidel.   HW: use tril to form N for Gauss-Seidel, 2, 3, 5,

                                    6 (  A = 2*eye(n)+diag(ones(1,n-1),+1)+diag(ones(1,n-1),-1)  ), 7, 9, 11,12  (11 and 12 are short).

Chapter 8 - Ordinary Differential  Equations - cover most

                    8.1 An Introduction to Theory of Differential Equations.  Direction Fields.   HW: 2, 5, 6

                    8.2 Euler's Method - 1st order accurate.  HW: 1a,f,  2 (look at x_final=2, 6, 10), 3

                    8.3 Convergence Analysis of Euler's Method.  Richardson Extrapolation.   

                            HW: 2, 3, 5 only b, 7, 9, 11(very short)

                    8.4 Numerical Stability.  Implicit Methods.

                            HW: 1, 2 (only Haun Method), 3 (look at x _final= 1, 3, 5, ratio of errors as h decreases), 4 (look at x_final=1, 3, 5, ratio of errors as h decreases),

                                    do #8 first - 7 (have to solve exactly without iterations, look at x_final=1, 3, 5), 8 ( explains why 7 has to be done without iterations),

                    8.5 Taylor and Runge-Kutta Methods.

                            HW: 3, 5, 8 only a and b (include the ratio or errors in the table), 9 (include Richardson Estimate from #4),  11 a,b,c (use xspan = 2,4,6,8,10,

                                    note how many points were used),  13  - interesting, but not required ( solve analytically or Maple and numerically RK4, compare).

                    8.6 Multistep Methods.  Adams-Bashforth and Adams-Moulton.

                            HW: 1 (c use x = 6, 12, 18), 2( also c only), 4( also c only), 6

                    8.7 Systems of Differential Equations

                            HW: 4, 5 (take x = 3, 6, 9, show only results for the second component), 6 (take x = 3, 6, 9, use tol = 1e-7,

                                    show only results for the second component), 8 - repeat only #5 (take x = 3, 6, 9, show only results for the second component) , 9, 10

                    8.8  Two-Point Boundary Value Problems

                            HW: 5, 7, 8 (derivative BC only changes one equation), 10                   

Chapter 9 - Partial Differential Equations - optional

                    9.1 The Poisson Equation    HW:  4, 7, 8, 9

                    9.2  The Heat Equation       HW:  7, 8,  10, 11

                    9.3  Wave Equation            HW: 5, 7, 8, 9