{"id":90,"date":"2013-08-11T21:00:00","date_gmt":"2013-08-11T21:00:00","guid":{"rendered":"https:\/\/jasoncantarella.com\/wordpress\/?page_id=90"},"modified":"2022-08-04T21:29:59","modified_gmt":"2022-08-05T01:29:59","slug":"math-4500","status":"publish","type":"page","link":"https:\/\/jasoncantarella.com\/wordpress\/courses\/math-4500\/","title":{"rendered":"Math 4500: Numerical Analysis I"},"content":{"rendered":"

Welcome to the homepage for Numerical Analysis (Math 4500\/6500)! I will post all the homework assignments for the course on this page. Our text for the course is Cheney and Kincaid, Numerical Mathematics and Computing<\/em>\u00a0(seventh edition). If you want to save money and get the 6th edition<\/a> for a lot less money, you’ll be fine. During Spring 2020, the class meets twice a week at 12:30-1:45 TR in Boyd 322. Office hours are Wednesday 2-5pm in Boyd 448.<\/strong><\/p>\n

Numerical analysis is the art and science of doing mathematics with a computer. This is where you can start to bridge the gap between the formal mathematics that you have learned so far and the mixture of mathematics, statistics, and computation you’ll need for a 21st century job such as working for the algorithms group at StitchFix.<\/a><\/p>\n

To be really prepared for an industry job, this is the first<\/em> class in a series which should include<\/p>\n

MATH 4500 and MATH 4600 (taken together or in either order)<\/p>\n

MATH 4510<\/p>\n

MATH 4900 (Optimization with Prof. Hu, Fall 2019)<\/p>\n

and<\/p>\n

MATH 4900 (Learning from Data with Prof. Adams, Spring 2020)<\/p>\n

or<\/p>\n

MATH 4050 (Advanced Linear Algebra with Prof. Wang, Spring 2021)<\/p>\n

In this class, we will learn the fundamentals of numerical mathematics, covering the basics of numerical arithmetic, finding the roots of equations, and numerical differentiation and integration. We’ll then jump ahead to\u00a0<\/p>\n

Mathematica<\/em> will be an integral part of the course. Current UGA students can get a copy for your laptop or home computer free of charge by visiting the EITS page here<\/a>. \u00a0Some of the homework assignments and projects will require you to write Mathematica<\/em> programs, and you’ll be completing most of the Introduction to the Wolfram Language online course<\/a>. Here are some brief notes on Mathematica Programming<\/a>.\u00a0<\/p>\n

Syllabus and Policies<\/h2>\n

Please examine the\u00a0course syllabus<\/a>. If you think you can get by with this copy, save a tree! Don’t print it out.\u00a0 Please subscribe to the course Google calendar<\/a>. <\/span>The course syllabus lists the various policies for the course (don’t miss the attendance policy).<\/span><\/p>\n

Lecture Notes<\/h2>\n

Here are links to my lecture notes for the course. Each lecture is usually accompanied by one or more\u00a0Mathematica<\/em>\u00a0notebooks explaining and demonstrating the concepts from class. <\/span><\/p>\n

    \n
  1. Introduction. What numerical analysis is all about. Mathematica. Examples of problems you can solve with Mathematica.\u00a0<\/li>\n
  2. \u00a0<\/span>Bisection and Newton’s method.<\/a> Bisection method. Linear convergence. Newton’s method. Proof of Newton theorem on quadratic convergence in 1-d. This lecture comes with demonstrations of the <\/span>bisection method<\/a>, Newton’s method<\/a>, <\/span>\u00a0unstable behavior of Newton’s method in one complex variable.<\/a><\/span><\/li>\n
  3. Newton’s method in n-dimensions. (notes part 1)<\/a>. (notes part 2).<\/a> Newton-Kantorovich conditions for convergence. Demonstration for inverse kinematics<\/a>. Ortega’s proof of the NK theorem<\/a>.<\/span>\u00a0<\/li>\n
  4. The secant method<\/a>. Superlinear convergence of the secant method. Fibonacci numbers!<\/span> Comparison of Newton’s method and the secant method<\/a>.<\/span><\/li>\n
  5. Interpolation of Data<\/a>. In this lecture, we discuss the surprisingly difficult and subtle problem of estimating the value of a function between given data points. We include a demonstration of <\/span>interpolating polynomials<\/a>.<\/span><\/li>\n
  6. Error in Interpolation of Functions<\/a>. We dig deeper into interpolation errors, discussing <\/span>interpolating polynomials and nodes <\/a>\u00a0and\u00a0the <\/span>effect of choice of nodes on interpolation error.<\/a><\/li>\n
  7. Everything you didn’t learn about Taylor’s theorem in MATH 3100.<\/a> General form. Remainder terms.\u00a0<\/li>\n
  8. Introduction to Error Analysis.<\/a> Interval Arithmetic. Hickey\/Ju\/Emden paper on fundamental model.<\/a>\u00a0<\/li>\n
  9. Models of computer arithmetic.<\/a> Fixed and floating point. Demonstrations for linear equations and probability computation.<\/li>\n
  10. Floating point arithmetic.<\/a> Loss of significance when subtracting nearly equal numbers. Accumulation of roundoff error in repeated addition.<\/li>\n
  11. Details of IEEE floating point on modern computers<\/a>.\u00a0<\/span>Machine Numbers<\/a>,\u00a0<\/span>\u00a0Conversion to single and double precision floating point number<\/a>s\u00a0(try this with some digits of Pi, such as 3.141592653589793238462643). Here’s the GAO report on the Patriot missile example<\/a>.<\/span><\/li>\n
  12. Estimating Derivatives and Richardson Extrapolation<\/a>. We give a rigorous procedure, called Richardson extrapolation, for bounding approximation errors. <\/span>\n
      \n
    1. Demonstration notebook: <\/span>symbolic Richardson extrapolation.<\/a><\/li>\n
    2. Demonstration notebook: <\/span>Richardson extrapolation and derivatives<\/a>.<\/span><\/li>\n
    3. Minihomework: Richardson extrapolation.<\/a><\/li>\n
    4. Graduate material: Lanczos derivative and minihomework.<\/a>\n
        \n
      1. Graduate reading: Lanczos’ Generalized Derivative<\/a><\/li>\n<\/ol>\n<\/li>\n<\/ol>\n<\/li>\n
      2. Estimating Derivatives by Polynomial Fitting<\/a>. We can use interpolating polynomials to estimate derivatives. <\/span>\n
          \n
        1. Demonstration Notebook: <\/span>the approximation for the second derivative<\/a>.\u00a0<\/span><\/li>\n
        2. Minihomework: Derivatives by Polynomial Interpolation.<\/a><\/li>\n<\/ol>\n<\/li>\n
        3. Numerical Integration and the Trapezoid Rule<\/a>. We now return to Math 2260 and reintroduce our old friend the Trapezoid rule.
          <\/span>\n
            \n
          1. Trapezoid rule videos (3 part playlist).<\/a> (Notebook<\/a>)<\/li>\n
          2. Minihomework: The Trapezoid Rule.<\/a><\/li>\n
          3. Graduate material: Numerical treatment of improper integrals and minihomework.<\/a><\/li>\n<\/ol>\n<\/li>\n
          4. The Romberg integration algorithm<\/a> is our first really modern integrator.<\/span>\n
              \n
            1. Trapezoid rule error video.<\/a> (Notebook<\/a>)<\/li>\n
            2. Romberg integration video.<\/a> (Notebook<\/a>)<\/li>\n
            3. Minihomework: Romberg integration<\/a>.<\/li>\n
            4. Additional reference material: Dahlquist\/Bjorck Chapter.<\/a><\/li>\n
            5. Graduate material: Error Analysis of the Trapezoid Rule<\/a>.\u00a0<\/span>\n
                \n
              1. Peano kernel error estimate video.<\/a> (Notebook<\/a>)<\/li>\n
              2. Bernoulli numbers and polynomials video.<\/a> (Notebook<\/a>)<\/li>\n
              3. Graduate minihomework: Bernoulli Polynomials minihomework<\/a>.<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n<\/li>\n
              4. Minimization of functions of one variable<\/a>. This is the start of our last big topic: numerical optimization. We have some <\/span>examples (including Brent’s method)<\/a>.<\/span><\/li>\n
              5. Theory of Brent’s method<\/a>. The source material here is\u00a0<\/span>Chapter 5 of Brent’s book<\/a>, which contains the original algorithm.<\/span><\/li>\n
              6. \u00a0Inexact Minimization.<\/a>\u00a0The source material is\u00a0<\/span>Section 4.8 of Practical Optimization<\/a>\u00a0by Antoniou and Lu. We give a<\/span>\u00a0<\/span>Mathematica implementation of Fletcher’s method for inexact minimization<\/a>.<\/span><\/li>\n
              7. Function Minimization without Derivatives: The Nelder-Mead Simplex Algorithm<\/a>. The Nelder-Mead algorithm isn’t particularly fast, but it’s incredibly robust, and it’s easy to code. The paper\u00a0<\/span>Convergence Properties of the Nelder-Mead Algorithm in Low Dimensions<\/a>\u00a0proves that Nelder-Mead converges for strictly convex functions on the plane. There’s also a good discussion of Nelder-Mead in\u00a0<\/span>this section of Numerical Analysis with MATLAB<\/a>. Here’s a\u00a0\u00a0<\/span>Nelder-Mead Mathematica demonstration<\/a>.<\/span><\/li>\n
              8. The Nelder-Mead Algorithm in N dimensions<\/a>. We can fairly easily extend Nelder-Mead to arbitrary dimensions. Here’s the\u00a0Nelder-Mead Mathematica Demonstration (Nd)<\/a>.<\/li>\n
              9. Compass Search and Other 0th order methods<\/a>. The Nelder-Mead algorithm can be extended to various algorithms which search in particular directions.<\/li>\n
              10. Simulated Annealing and Markov Chain Methods<\/a>. An educated form of guessing.<\/li>\n
              11. Minimization of Functions of N Variables I: Introduction to Direction Set Methods<\/a>. Direction set methods use the equivalent of knowing the derivative of your function for multivariable problems. Unlike one variable problems where knowing the derivative is a convenience, this can be almost a necessity in order to make progress with some multivariable problems. \u00a0The\u00a0<\/span>demonstration<\/a>\u00a0gives the basic algorithm, we also link to <\/span>optimizing the Rosenbrock Banana Function<\/a>.<\/span><\/li>\n
              12. Direction Set Methods for Minimization of Functions of N variables II: Conjugate Directions and the Conjugate Gradient Algorithm<\/a>. This has source material from\u00a0Numerical Recipes in C online (you want section 10.6)<\/a>, but I’ll try to replace it with a better reference before we get here.<\/li>\n
              13. Constrained optimization<\/a>.<\/li>\n<\/ol>\n

                Homework Assignments<\/span><\/span><\/h1>\n

                Each assignment will contain some regular problems and some challenge problems. The regular problems are required for everyone. The challenge problems are required for students in MATH 6500, but extra credit for students in MATH 4500.<\/p>\n