Math 350 Numerical Methods    Spring 2008

 

Instructor:  Dr. M. Reese

 

Office:  Eggleston 105

Phone:  233-8752 (On campus: extension 8752)

e-mail:  mreese@vwc.edu

Office hours: 

  • MF      10:30-11:30 am
  • MW     1:30-3:30pm
  • TTh      12-2 pm

Or by appointment

 

Dates to remember:

Holidays: 

Spring Break:  March 17-24

Tests: 

February 27, March 28, April 25

Final: 

Monday, May 12   11:30-2pm

Last day to drop: 

April 9

 

Catalog description:  Examines efficient methods used in solving numerical problems with the aid of a computer. Topics include floating point arithmetic (Ch 1), interpolation and approximation (Ch 3,8), integration (Ch 4), roots of nonlinear equations (Ch 2), ordinary differential equations (Ch 5), and systems of linear equations (Ch 6). (Added italics indicate chapters from Numerical Analysis, 8e, by Burden and Faires.)

 

Numerical Methods, also known as numerical analysis and scientific computing, is a combination of mathematics and computer science.  The object of the course is to learn to use the computer to solve problems that are not feasibly solved by pencil-and-paper.  We will learn how to identify problems that require a numerical solution, how to implement a variety of numerical methods, and how to estimate the error propagation that can occur when numerical methods are applied. 

 

Required Text:  Numerical Analysis, 8e, by Burden and Faires

Required software:  Maple 11 (bundled for free with the textbook) The textbook Maple is good for one year.  You may purchase (at a discount) a copy that will not expire.  Ask me for the code if you are interested.

 

Estimated workload:  Five to seven hours per week outside class completing homework assignments or preparing for tests.  If you find you need more time than this, let me know.

 

Attendance policy:  Attendance is required.  Absence will be excused only at the discretion of the instructor.  A maximum of six (6) absences will be excused.  Excessive absence will reduce your grade one letter for each absence in excess of six.

 

Accommodations for students with special needs:  The standard procedures for meeting the responsibilities associated with this course can be modified for students with certain disabilities.  To qualify for such accommodation, a student must provide the College with appropriate professional documentation that confirms the presences of the disability.  To begin the confirmation process of for further information about it, contact our coordinator of disability services, Mrs. Fayne Pearson, at 455-3246.

 

 

Grading

Daily assignments

25%

Programming projects

75%

 

Scale:  A (90-100), B (80-89), C (70-79), D (60-69), F (below 60)

 

Daily assignments may not be handed in late under any circumstances.  I will drop 3 low or zero scores to calculate the average.  Each assignment will be worth 10 points.

 

Programming projects will receive an on-time bonus of 3 points.  Any late programming project will not receive the bonus and will be further penalized 10 points per day late.

 

Programming projects

Chapter

Due dates

A system that will solve equations of a single variable using bisection, fixed point, Newton, secant and acceleration methods.

2

February 25

A system that will interpolate using Lagrange/divided difference interpolation, cubic splines, Hermite cubic, Bezier curves methods.

3

March 14

A system that does automatic and numerical differentiation, and numerical integration.

4

April 10

A system that will solve IVPs using Euler and Runge-Kutta methods.

5

April 25

A system that solves linear systems by direct methods.

6

May 12

 

 

 

Day-by-day

Week

Day

Topic (Read the section before class.)

Assignment

1

Jan 28

Introduction

Read 1.1 #1a,3a,4a,9

 

Jan 30

Computer Arithmetic (1.2)

#1a,4d,11,17,28

 

Feb 2

Computer Arithmetic (1.2)

 

2

Feb 4

Algorithms (1.3)

#1,6,18

 

Feb 6

Bisection Method (2.1)

#1,5a,19

 

Feb 8

Fixed-point iteration (2.2)

#1,3,5,23

3

Feb 11

Newton’s method (2.3)

#6a,11a,27

 

Feb 13

Error analysis for iterative methods (2.4)

#1d,3d,5,6,8a

 

Feb 15

Accelerating convergence (2.5)

#1a,2,3,9

4

Feb 18

Müller’s method (2.6)

#2a,4a,7

 

Feb 20

Project work day

 

 

Feb 22

Interpolation & Lagrange polynomial (3.1)

#1a,3a,5,11,19a

5

Feb 25

Divided differences (3.2)

#4a,7,18

 

Feb 27

Hermite Interpolation (3.3)

#1,5,10

 

Feb 29

Cubic spline interpolation (3.4)

#1,2,32

6

Mar 3

Parametric curves (3.5)

#3a,4

 

Mar 5

Discrete least squares approximation (8.1)

#3,5,9

 

Mar 7

Orthogonal polys & least squares approx (8.2)

#1e,3e,5e,7,9

7

Mar 10

Project work day

 

 

Mar 12

Numerical differentiation (4.1)

#1,3,5

 

Mar 14

Richardson’s extrapolation (4.2)

#1d,5,11

Spring   Break

8

Mar 26

Numerical integration (4.3)

#1d,3d,5d,9d

 

Mar 28

Numerical integration (4.4)

#1a,3a,5a,22

9

Mar 31

Romberg integration (4.5)

#1a,3a,5a,7

 

Apr 2

Adaptive quadrature methods (4.6)

#3a,5a

 

Apr 4

Gaussian quadrature (4.7)

#1a,2a,3a

10

Apr 7

Project work day

 

 

Apr 9

Initial value problems (5.1)

#1a,2a,3a,5

 

Apr 10

Euler’s method (5.2)

#1a,3a

11

Apr 14

Higher-order Taylor’s methods (5.3)

#1a,3a,11

 

Apr 16

Runge-Kutta methods (5.4)

#1a,13a,29

 

Apr 18

Systems of differential equations (5.9)

#1a,9

12

Apr 21

Project work day

 

 

Apr 23

Linear systems of equations (6.1)

#3,5,7, (12)

 

Apr 25

Pivoting strategies (6.2)

#1a,3a,9a

13

Apr 28

Linear algebra (6.3,4)

6.3# TBA

 

Apr 30

Matrix factorization (6.5)

#1,3a,5a

 

May 2

Project work day

 

14

May 5

Snow or catch-up day (TBA)

 

Monday May 12  @11:30   Final Exam (5th project due)

 

 

INSTRUCTIONS FOR PROJECTS

There are three major components to a project: software development, testing and analysis.

Software Development (75/100points): Project development consists of four parts: code, execution, output and use.

  1. Code - the actual computer implementation of the project.
  2. Execution (20/100 points) - the software must correctly perform what it was designed to do.
  3. Output (20/100 points) - clear display of solutions (tables and graphs) and information associated with the solution (errors, iteration count, accuracy, etc.). If there are graphs or tables as output, how clearly do they display the information?
  4. Use (35/100 points) - three parts: ease (user-friendliness), robustness, and documentation.

a.       Ease (10/25) - How easy is it for the user to give the software input and to obtain output?

b.       Robustness (10/25) - A software system is more robust if it solves a wider range of problems than another system designed to solve the same types of problems. For example, does the software package solve just the test problems or is it general enough to solve any problem of which the test problems are simply an example? (A software package that solves a class of problems is more robust than one that just solves the test problems.)

c.       Documentation (10/25) - For the projects, the team that develops the associated software, must give a short oral presentation on how to use the software. In addition, a read-me file is to be made and accessible for users in the testing the software.

Testing (10/100 points): This part consists of running the software on the test problems given. Results from the test problems should be kept in a file. A hard copy of this output file is to be handed in. In general, the software should output results in tables that facilitate the understanding of associated solution. In the process of testing the software, e-mail the user-support person about any problems that you have found.  Hand in all e-mail associated with testing.

Analysis (15/100 points): The purpose of an analysis is to get you to critically evaluate the methods and the results obtained from the software as it was run on the test problems. An analysis requires you to carefully look at the results. What is the error? What explains the error - the test problem itself, the precision used, the numerical method, or the implementation, or some of these or all of these? If you ask the computer to solve a (real) problem it is because you don't know the solution. If you knew the solution, you would not have a problem. So how do you know that the solution to your problem is the solution that the computer software has obtained?

An analysis consists of two parts: summary tables and/or graphs associated with the output, and a textual part.

 

  1. Summary Tables and Graphs - Usually the software development team will supply tables and graphs. If this is not the case, a way to summarize the information must be found. The form for the summary is usually a table and/or a graph. Your team must decide how this is best done.
  2. Text - The textual part must address the questions listed above. Note: A description of the output is not an analysis. In particular address at least the following types of questions.

a.       Why were the results expected or surprising?

b.       What are the primary sources of error; that is, what explains the error? Is it round-off, the problem, severe cancellation, numerical truncation, the particular implementation?

c.       How many digits of the solution(s) are accurate? How would you know they are accurate if you did not know the solution?

d.       Is there a pattern in the error? If there is, why does this occur?

Be specific when using words like "faster," "more efficient," "accurate."  What are meant by these words? Relate these words to the results. For example, if you say that Newton's method is "faster" than the bisection method, this is not specific nor is it very meaningful. On the other hand suppose you wrote, "For test problem 1, 2, 3 and 5, Newton's method, on average, took 0.05 flops per digit of accuracy while bisection method took 2.5 flops per digit of accuracy." (flop = floating point operation) This statement is clear, meaningful and precise.  Here, "fast" means flops per digit of accuracy. If you use "fast" in regard to an algorithm, you must define it. That is, you must specify how you are measuring the efficiency of the algorithm being used. If you specify seven digits of accuracy for all solutions of test problems, then you might use execution time as a way to measure efficiency. However, if for one test problem, the accuracy is 4 digits and on another the accuracy is 12 digits, then execution time does not measure how fast the algorithm obtains a solution. What is a solution?

POLICIES AND PROCEDURES ASSOCIATED WITH TEAM WORK

  1. Hand-in a written Division of Labor statement at least one week before the due date. The division of labor should be equitable over the semester:  You should program on 2 projects, test on 1 project, and co-write the analysis for 2 projects. For each project, choose a "user support" person. This person is responsible for handling questions during the testing phase.
  2. If all items of the "Division of Labor" are correctly fulfilled by the responsible person(s), then all members of the team will receive the same point distribution. An individual in a team will be rated differently for one or more of the following reasons.

·         The individual's share of the labor as outlined in the "Division of Labor" is not fulfilled. 

·         The individual's portion is incomplete or poorly completed.

 

PROCEDURES FOR TURNING IN PROJECTS AND TESTING/ANALYSIS

  1. One hard copy document with the results is to be submitted.  A report cover is required.
  2. Format for the projects.

a.        The "Division of Labor" statement. (Credits)

b.       The analysis. (No more than 2 pages, not including graphs or tables.)

c.        The source code.  (Also, send me an electronic copy.)

d.       The user's "manual" and read-me files.

e.        The testing results.

Example division of labor statement:

Credits

System Name

 

Programmer 1

 

Programmer 2/user support

 

Testing

 

Analyst 1

 

Analyst 2