COMP SCI 350 Scientific Computing

Spring 2007

Course web site: [http://www.uwgb.edu/shayw/courses/350]

Meeting times: TR 2:00 – 3:15 in MAC 122

 

Professor:  Bill Shay                                                           Office: MAC C308                                                                                        

Phone: 465-2316/5038                                                          email: shayw@uwgb.edu

Office Hours:  MWF: 9:00-10:00; TR: 3:30-4:30; or by appointment.

Prerequisite:  COMP SCI 257; MATH 202; COMP SCI 242.

 

Text:  Introduction to Numerical Analysis by Alastair Wood

 

Course:  What is Scientific Computing (sometime called numerical analysis)? Often considered as a field with one foot in mathematics and another in computer science perhaps it is best described as the study of problems for which mathematical theory provides no feasible solution. Some examples include:

 

·         Given a polynomial P(x), find x for which P(x)=0. If P is a 2nd degree polynomial (ax2 + bx + c) then x=. If P is a 3rd degree polynomial (x3 + ax2 + bx + c) then one solution is

x = where , , and

        .   There is even a formula for a 4th degree polynomial but I’ve never seen it (and don’t want to). However, Galois Theory has proven that if the degree of P is greater than 4 there can exist NO general formula to find the zeroes of P(x). Besides, most complex problems are modeled by nonpolynomial equations for which there is no hope of finding general solutions. How can we deal with such problems?

 

·         Consider a system of linear equations . In precalculus algebra you may have seen Cramer’s rule which defines the exact solution to this system (if such exists) using determinants. Using expansion techniques the determinant of an matrix can be found using n! calculations. Often a typical exercise for n = 3 or 4, the calculations become impossible for large n. For example, if n = 30 then n! is approximately 1032. If a computer could make 1 trillion calculations per second it would require about 1020 seconds (or about 3 * 1013 years) to make the calculations. Furthermore, it’s not unusual to encounter simulations requiring the solutions of hundreds, if not thousands, of simultaneous equations.

 

·         The fundamental theorem of calculus states that, under certain conditions,where F(x) is the antiderivative of f(x). What if ? Since there is no known expression for the antiderivative of f(x) the fundamental theorem is of little help in solving the problem. Most real integration problems fall into the category of being unable to find the appropriate antiderivative.

 

·         Computers can only add, subtract, multiply, and divide. How then can a computer evaluate a trig function such as cos(x) or other functions such as ex?

 

Anyway, you get the idea. There are many examples of mathematical problems for which theory provides no way to actually solve the problem. This is where Numerical methods and techniques enter the picture. Instead of actually solving problems we look for ways of finding approximate solutions using basic arithmetic. It’s a compromise between not getting the exact solution (which we couldn’t get anyway) and actually finding something but which is not exact. Problems and issues abound as we must question the viability and accuracy of the calculated solutions. It’s particularly difficult since we must estimate the accuracy without knowing what we are trying to approximate. It’s a very inexact science and constitutes a field in which precise answers are nonexistent. Numerical Analysts are somewhat like lawyers in that they must provide strong evidence that their results are a good approximation of reality. Given the absence of any ironclad proof of accuracy, this is all that is left.

Syllabus  (give or take a week)

 

Weeks

Topics

1

Mathematical fundamentals: Approximation to functions : Taylor series, theoretical maximum and actual errors. Maclaurin Series. Introduction to Maple. Sections 1.1 – 1.4.

2

Computational error: absolute and relative error; rounding vs. chopping. Truncation errors. Error propagation. Chapter 2.

3, 4

Sequences and iteration. Linear, quadratic, and exponential sequences. First and second order recurrence relations. Compound interest. Applications to card tricks. Chapter 5.

4, 5

Finding roots of equations. Bisection method, error analysis, fixed point methods, acceleration techniques. Newton-Raphson iteration. Deflation. Sections 6.1-6.4, 6.6, 6.7.

6, 7

Solving Systems of equations: Gauss elimination, iterative methods. Gauss Seidel and Jacobi iteration. Ill-conditioned systems. Chapter 9

8, 9

Using polynomials to approximate functions. Linear and quadratic interpolation, error bounds. Interpolating using polynomials of degree n, Lagrange polynomials, divided differences. Chapter 3.

10, 11

Using non-polynomials to approximate functions: Cubic splines, least-squares, B-splines, Bezier Curves. Applications to Computer Graphics. Chapter 4.

12, 13

Numerical differentiation. Approximating first and second order derivatives. Applications to differential equations. Chapter 7. 

14, 15

Numerical Integration. Riemann Sums, Trapezoidal rule, Simpson’s rules. Romberg integration. Error formulas. Chapter 8.

 

 

GRADING: Four exams (15% each); four Homework sets (10% each). The final exam is scheduled for Thursday May 10, 2007 from 1:00 - 3:00. PLEASE NOTE: This date is known many months in advance and must be taken as scheduled.  Any activities such as work schedules, vacations, trips, etc. must be planned around this date.