SYLLABUS - MATH 4650 and CSC 4656: Numerical Analysis I

Summer Semester - 1999

Professor: Weldon A. Lodwick

Office: CU-Denver Building, Room 622

Telephone: 556-8462 (office - voice mail), 556-8442 (secretary)

E-Mail: weldon.lodwick@cudenver.edu

Web Site: http://www-math.cudenver.edu/~wlodwick

Text: Numerical Analysis 6^th Edition by Richard L. Burden and J. Douglas Faires, Brooks/Cole Publishing Company, 1997.

Office Hours: M/W 9:00 - 10:00 AM - math resource lab

M/W 1:20 - 2:20 PM - room 622, CU Denver Building

If you cannot make these hours, you are welcome to see me in class to make an appointment for another time. You can also schedule meetings outside office hours by exchange of e-mail. Please do not see office hours exclusively as a time to address problems with the course. You can use them to clarify points you don't understand, to get additional readings, to talk about the subject matter in relation to your special interests, or to go over work in progress. Sometimes talking to me will clarify your own thinking and I would encourage you to do this.

Students with Disabilities: If you have a disability that requires accommodation in this course, please see me as soon as possible. I am happy to make appropriate accommodations, provided timely notice is received.

Note: For this summer session, not only is the pace faster because there are 10 weeks, but we are losing two class periods (June 1^st and July 5^th). Thus, we have 18 class periods and the time for each class meeting has been extended as you noted from the schedule of classes. We have 23-26 sections that we hope to cover. You can expect to prepare one or two sections per class period. Therefore, it is imperative to keep up with the pace of the class.

Below is the proposed outline. The weeks listed are tentative and indicates my best estimate as to the pace of the class.

This class studies numerical methods for solving equations, solving linear systems, interpolation, differentiation, and integration. The prerequisites are Math 2411 (or Math 2410), Math 3191 and programming experience (such as CSC1401 or Math3250). Math 4650 (CSC4656) is required for the "Computer Science and Engineering" major, and the "Computer Science" and "Actuarial Science" options in the Mathematics degree and the Applied Mathematics degree (as well as some other programs). Moreover, this course follows the guidelines for the Numerical Analysis test given by the Society of Actuaries.

I believe that teaching is a process that involves an active partnership. My role is that of a guide to your learning. Therefore, I am responsible to open the way, to encourage, and to nudge you toward your own learning. I will help guide you toward this learning by providing mathematics for you to experience. It is my aim to communicate mathematics in a way that is supportive and nurturing of your efforts. Your role is to find a way to experience and articulate the mathematics that is presented and that you encounter. I believe that it is your responsibility to let me know when you find yourself not understanding mathematical concepts that are presented in class. Once you make this known, it is our responsibility to work on trying to attain clarity. I will try to be as proactive as possible. I believe that results on examinations, quizzes, and assignments give us the opportunity to clearly see where the areas of mathematical understanding are and what areas need more attention.

By the end of the semester you should be able to read, understand and apply numerical analysis methods associated with the topics covered in the semester to correctly solve associated problems at the level of our textbook. Secondly, given a problem that requires computational methods, you should be able to: (i) translate the description of the problem into an algorithm, (ii) choose and apply the appropriate software method(s), and (iii) obtain the correct solution(s). Lastly, by the end of the semester, you should be able to judge for yourself, the veracity of statements made in numerical analysis texts that are at the same level as our text.

EVALUATION

There are three evaluative criteria: (i) assigned computer projects (35% of your grade), (ii) short weekly quizzes (15% of your grade), and (iii) exams: midterm (25% of your grade) and final (25% of your grade). Evaluation is based on a point system so that it is very important that you turn in your projects and complete tests/quizzes as thoroughly as possible rather than taking a zero score.

ASSIGNED COMPUTER PROJECT: All project development and testing will be completed in assigned project/study teams. While you are to work in teams, your grade is individual. How this will be accomplished is outlined in the section below titled "Project Instructions." Working in teams is pedagogical and practical. First, current software development is most often done in teams. Secondly, the projects are for the most part too time-consuming for a single person to complete alone within the time allotted. In addition, if everyone in your study/project team scores 80% or better, each member will receive an addition 5%.

There are four projects:

1. A system that will solve equations of a single variable using bisection, fixed point, Newton, secant and acceleration methods - chapter two.
2. A system that will interpolate using Lagrange/divided difference interpolation, cubic splines, Hermite cubic, Bezier curves methods - chapter three.
3. Automatic and numerical differentiation, and numerical integration - chapter four
4. Direct methods for solving linear systems - chapter six.

Each team is responsible for developing the associated software for one of the four projects listed above. This effort is worth 100 points. In addition, for each of the other three projects, the team is responsible for testing and analyzing the software developed by another team. This effort is worth 25 points each. The instructions and evaluative criteria breakdown are given below in "Project Instructions."

Each student will have an account on linus (one of the math department's networked computers) since it has MATLAB, a software package that you may use but are not required to use. MATLAB is an interpretive software package that may facilitate the completion of your projects and testing. Regardless of whether you use C, C++ or MATLAB, the projects that are developed must run on linus and it is from linus that all testing will take place. That is, you are free to develop the software required by each project in any language and on any computer you wish as long as its execution works on linus. My suggestion is to use MATLAB, since it can link C++ (or other executable files), it has graphics already built in and it is an interpretive language originally developed to handle mathematical problems.

QUIZZES: There will be five ten minute quizzes each worth 15 points given at the beginning of class on the Mondays listed below. A quiz consists of a definition and/or a short calculation found in the sections covered in the previous two classes. An example question is: "Define relative error." In writing down a definition, I expect the exact words as they are used in the text. A problem that asks you to compute two iterations of the bisection method for a particular equation of a single variable is the type of short calculation I will ask on quizzes.

EXAMINATIONS: There will be one midterm and one final exam. The midterm will be Wednesday June 30^th and is worth 125 points. The final exam will be Wednesday August 4^th and is worth 125 points. The midterm will cover the material between the first day of class through June 23^rd. The final exam will cover the remaining material and therefore is not comprehensive.

Midterm 125 June 30^th

Final 125 August 4^th

Quizzes 75 6/7, 6/14, 6/28, 7/19, 7/26

Project 175

----

Total 500 points

The following distribution of grades is guaranteed. However, the final distribution could be "curved" downward.

A+ 97-100%, A 93-96.9%, A- 90-92.9%

B+ 87-89.9%, B 83-86.9%, B- 80-82.9%

C+ 77-79.9%, C 73-76.9%, C- 70-72.9%

D+ 67-69.9%, D 63-66.9%, D- 60-62.9%

TEXT PROBLEMS: A list of problems from the text is given below. I will hold you responsible for doing these, though I will not collect these problems. However, the spirit if not the actual contents of these problems may be part of the exams and quizzes.

The following text problems I expect you to know how to work.

Section Problems

1.2 1-5,7,9-11,17,19,26

1.3 1,3,4,6,7,13,14

2.1 1,3,7,9,13-15

2.2 1, 2, 5,7,9

2.3 1-10,27,28

2.4 4-7,9

3.1 1-5,21,22

3.2 1,4,6,14

3.3 1,2,7

3.4 1-5,11

3.5 1

4.1 16,18,21

4.3 1-8,10,15 (especially d, e)

4.4 1-5,7

4.6 1,6

4.7 1,5,7

6.1 2,3,5,11,16

6.2 1,5,7,9

6.3 1-3,11,12

6.5 1-3

6.6 1-4,6,25

9.1 1-3,9

9.2 1-3

9.3 1-3

4. 1

General advice: Keep all materials that I turn back in case you think I have not credited you with the points you earned. I can only correct your score if you have what I have turned back to you. It is a good idea to xerox anything that you turn in just in case I lose what you turn in. Please check to make sure that the points you earned are the points I have recorded. Note: The statistics that I have read about correctness of professors in recording grades state that there is a 6% error rate in our recording of your grades. Please make sure that I have correctly recorded your points.

Advice on exam taking: Some exams may be longer (or more demanding or both) to what you are accustomed. If the class average is below 65%, I will curve the exam so that the average is 75%. Thus, it is wise (imperative) for you take exams as follows. Do all the problems you can do first. Don't waste too much time on making sure that you have done your arithmetic correctly since arithmetic mistakes are usually discounted at half a point per mistake unless your arithmetic mistake totally trivializes the problem in which case the deduction will be severe. That is, you should work on generating the most number of points per unit of time.

Drops and incomplete grades: See Schedule of Courses for the relevant dates with respect to dropping this course. The incomplete policy of the Mathematics Department and the College of Liberal Arts and Sciences is strictly enforced. Incomplete grades are given only in situations in which a student who has been in good standing all semester, is prevented from completing a course assignment (for example the final exam) due to circumstances beyond her/his control (for example, hospitalization, jury duty, revised job assignments, death in the family).

Late Projects: A penalty of 25% of the total points associated with the project per class period that a project or testing/analysis is late will be assessed.

Missing Examinations: In general, I do not give make-up exams. If you miss a test for acceptable reasons and we have met before the test and agreed that indeed this is the case your score on the test that you missed will be the percentage that you receive on the final exam. You are to take the final exam on the given date. If you have more than two final exams on August 4^th or another acceptable reason, this will have to be resolved at least one week in advance of our final exam. There are cases where an exam is missed without your being able to notify me ahead of time. These will be exceptional cases and we can work these out as long as your reasons are legitimate.

Legitimate Excuses: Legitimate excuses for missing tests and quizzes are for reasons that are beyond your control. You may be required to produce an official, signed excuse. If you are needed in a wedding, for example, you must talk to me prior to the (blessed) event. If you are legally arrested, then this is not a legitimate excuse. For matters that are within your control, the general rule is that it is not excused. However, talk to me prior to the event.

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

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

1. Code - the actual computer implementation of the project. Since this is not a coding class, I will not, in general, give points for average cleverness in implementation or penalize for mildly inefficient performance. When the coding is clearly superior or clearly inferior, then points will be involved.
2. Execution (50/100 points) - the algorithm as run must correctly perform what it was designed to do.
3. Output (25/100 points) - relevant, clear display of solution (tables and graphs) and information associated with the solution (errors, iteration count, flops, accuracy, time/efficiency measures). If there are graphs or tables as output, how clear do the graphics/tables display the information required?
4. Use (25/100 points) - the software is to be used by the class and by me. Use consists of three parts: ease (user-friendliness), robustness, and documentation.

1. Ease (7.5/25) - How easy is it to use your software? How easy is it for the user to give the software input and to obtain output?
2. Robustness (7.5/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, as it's designed, solve just the test problems or is it general enough to solve any problem of which the test problems are simply an instance? If the software can solve a class of problems rather than just the specific test problems, then the software package that solves a class of problems is more robust than one that just solves the test problems.
3. Documentation (15/25) - For the projects, the team that develops the associated software, must given an oral presentation with handouts 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. An internal "help file" is clearly useful to include. This is very easily done in MATLAB.

Testing (10 points): This part simply consists of running the software developed on the test problems given. Results from the test problems are to be kept in a file. A hard copy of this output file is to be handed in. In general, the teams that develop the software are to output results in tables and graphs in such a way that the way the results are displayed facilitates the understanding of associated solution to the class of problems that the software was designed to solve. Thus, in the analysis of the performance associated with the test problems, direct reference to tables and graphs generated by the software will be made. In the process of testing the software, email the team's user-support person about any problems or fantastically clever/useful features that you have found with an electronic copy to me.

The software development team must supply the user with error (absolute and relative error) associated with the test problems when relevant. Moreover, such factors as iteration counts, flops, digits of accuracy per flop, execution times, when these are relevant must be supplied to the user by the development teams. These factors are used directly in the analysis. Therefore, it is to be expected that in the testing, these factors are part of the output.

Analysis (15 points): The purpose of an analysis is to get you to critically evaluate 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 in the form of a table and/or 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.

1. Why were the results expected or surprising?
2. What are the primary sources of error; that is, what explains the error? Is it round-off, pathology of the problem, severe cancellation, numerical truncation, the particular implementation? For example, suppose one codes X³⁴⁴ = X^344, and X³⁴⁴ = X*X*…*X 344 times for X = 2.71828182845945. Is there a difference in accuracy? That is, while the two ways are mathematically equivalent, they are not computationally equivalent. Moreover, A + B - A can be different than A - A + B when implemented on a computer. That is, a computer is not associative with respect to addition/subtraction nor is it distributive. In particular, A*(B + C) is not always the same as A*B + A*C. Therefore, the way arithmetic is coded can make a difference. This is what I mean by error associated with the "implementation" of the mathematics.
3. How many digits of the solution(s) are accurate? How would you know they are accurate if you did not know the solution?
4. Is there a pattern in the error? If there is, why does this occur?

Be careful when using words like "faster," "more efficient," "accurate." Be specific. What are meant by these words? Back up your words. That is, directly 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." This statement is clear, meaningful and precise, assuming that in your summary table of results these figures had been correctly averaged. Here, "fast" means flops per digit of accuracy. If you use "fast" in regard to a mathematical algorithm, you must define it. That is, you must specify how you are measuring the efficiency of the algorithm being used. If one specifies seven digits of accuracy for all solution of test problems, then one 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 is12 digits, then execution time does not measure how fast the algorithm obtains a solution. What is a solution?

1. A written "Division of Labor" document is to be produced and handed in at least one week prior to a team's turning in an assignment (project software, testing/analysis). If your team is developing software, make sure that a "user support" person is identified along with hers/his email address. This person is responsible for handling questions coming from the class that is associated with the software.
2. If needed, the teams should meet with me to discuss the division of labor prior to formulating the document. It is assumed that the division is equitable.
3. 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.

1. The individual's share of the labor as outlined in the "Division of Labor" is not fulfilled
2. The individual's portion is incomplete.
3. The individual's part is poorly completed.

1. The completion dates for projects are as follows: project 1 - June 25^th, project 2, July 9^th, project 3, July 16^th, and project 4, July 23^rd. The testing and analysis must be turned in electronically by 11:59:59pm one week after the completion date of the project. The hard copy is to be turned in no later than the following class period. In particular, electronic versions of the project testing and analysis are due: project 1 - July 2^nd, project 2 - July 16^th, project 3 - July 23^rd, project 4 - July 30^th.

1. One hard copy document per team with the results is to be submitted.
2. Format for the teams responsible for creating the software associated with the projects.

1. A hard copy of the source code and the location of the directory with the file names where the source files and results can be found and run. Note: You must set the permission so that I can read and execute the programs.
2. A hard copy of the "Division of Labor."
3. A hard copy of the user's "manual" and read-me files along with the directory in which they are found.
4. A hard copy of the testing results along with the location of the output files.
5. A hard copy of the analysis.

1. Format for testing/analysis (teams not responsible for software development) - turn in parts (b), (d) and (e) from the above.

Note: For testing and analysis, the textual part must be no more than three pages. This count does not include your graphs and tables. Attached output files can be put in an appendix and not counted as part of the textual part of what you turn in.