MATH 4600-100 (4132), Fall 2015

Introduction to Numerical Analysis

Catalog Description:
A survey of the ideas, methods, and algorithms in Numerical Analysis.
Desired Learning Outcomes:
Students will be able to:
Requisites:
MATH 3400 Elementary Differential Equations and (3200 Applied Linear Algebra or 3210 Linear Algebra) and (3600 Applied Numerical Methods or CS 2300 or 2400 or ET 2100).
Instructor:
Martin J. Mohlenkamp, mohlenka@ohio.edu, (740)593-1259, 315-B Morton Hall.
Office hours: Monday, Wednesday, and Friday 9:40-10:35am, or by appointment.
Web page:
http://www.ohiouniversityfaculty.com/mohlenka/20161/4600-5600/.
Class hours/ location:
Monday, Wednesday, and Friday 3:05-4pm in 314 Morton Hall.
Text:
None. We will scavenge materials from the internet.
Computational Resources:
We will do our computations in the Sagemath Cloud.
Tests:
None.
Journal:
Each week you will submit a journal documenting that you have performed the requested tasks and learned. Typical components are:
Writing quality counts:
We will use the Good Problems method of gradually increasing the criteria, and its writing guides on Layout, Logic, Flow, Intros, Symbols, and Graphs.
Extensions:
Journals are due at specified times and will be graded soon thereafter. If you email me before I have graded it, you can have a 24 hour extension, with penalty 5%. You can get further extensions with penalty 5% per 24 hours.
Partners and Ratings:
You will work with a partner (assuming an even number of students) and submit a single journal. You will rate the relative contribution of your partner and these ratings will be used to adjust the journal scores at the end of the term, using a statistical analysis.
Project:
Working with a partner, you will develop a final project based on a paper in the SIAM Undergraduate Research Online (SIURO) journal. The goal is to validate (or refute) the analysis and numerical results presented in the paper. (If you can extend or improve the results, that would be even better.) You will give a presentation on what you did, and submit a final report.
Final Exam:
The final exam is scheduled for Wednesday, December 9, 12:20-2:20 pm. Your final project will substitute for this exam, and be due at the scheduled ending time of the exam.
Attendance:
This is a "lab" class, so your attendance, participation, and collaboration is essential. You are allowed 4 absences (out of 40 classes) without penalty; these include university excused absences for illness, death in the immediate family, religious observance, jury duty, or involvement in University-sponsored activities. Each additional absence will reduce your final average by 0.5%. Your attendance record will be available in Blackboard.
Grade:
Your grade is based on your journals at 80% and your project at 20%. Excessive absences will subtract from your final average. A final average of 90% guarantees you at least an A-, 80% a B-, 70% a C-, and 60% a D-.
Academic Misconduct:
Your work must be done by you, not by someone else for you. Your words must be your own; any text not your own must be properly quoted and cited. You can ask others questions, look in books, use resources from the internet, and generally use whatever help you can find; such help must be acknowledged by naming the person, citing the book, giving the internet link, etc. A minor, first-time violation of this policy will receive a warning and discussion and clarification of the rules. Serious or second violations will result in a grade penalty on the assignment. Very serious or repeated violations will result in failure in the class and be reported to the Office of Community Standards and Student Responsibility, which may impose additional sanctions. You may appeal any sanctions through the grade appeal process.
Special Needs:
If you have specific physical, psychiatric, or learning disabilities and require accommodations, please let me know as soon as possible so that your learning needs may be appropriately met. You should also register with Student Accessibility Services to obtain written documentation and to learn about the resources they have available.
Learning Resources:
People:
Your classmates are your best resource. Use them!
Numerical Analysis Material:
Sage/ Python:

MATH 5600-100 (4147)

For students enrolled in MATH 5600, the above syllabus is modified as follows:

Requisites:
Formally none. In practice Calculus, Linear Algebra, Elementary Differential Equations, and working knowledge of a programming language are needed.
Exploration:
In addition to the journal, each week submit individually an "exploration" of some additional topic you encountered and thought was interesting or useful. In scope, this exploration should be 10% the size of the journal.
Project
You will do your project individually and use a paper from the SIAM Journal on Numerical Analysis (SINUM) or the SIAM Journal on Scientific Computing (SISC).
Grade:
Your grade is based on your journals at 75%, your explorations at 5%, and your project at 20%.

Schedule

Subject to change. Many of the tasks will be filled in as we go along.

Week Date Topic/Materials/Tasks
1
Mon Aug 24
  • Introduction, syllabus, etc.
  • Get set up on the Sagemath Cloud:
    • Use Firefox (or Chrome), not Internet Explorer.
    • Sign up for a free account using your real name and your University email address (@ohio.edu). Sign in.
    • Click on "Help" in the upper left and read about it.
    • Look for a project in your account titled with your name. I created this and shared it with you. Your submissions as an individual, such as your biography, go here.
    • Look for a project "NumericalClass". I will put things here for the whole class to use.
  • Do your Biographical Survey
Wed Aug 26
  • Find your partner for this week's tasks and journal, and sit next to them. (Look in NumericalClass/partners.sagews to find out who your partner is.)
  • Look for a project shared with your partner. You will submit your journal using this project.
  • One of you upload the journal sample to this shared project. You can then both edit it.
  • Play with this journal and make it into your own journal. A cell with code is run by entering it, holding the "shift" key and hitting the "enter" (return) key. A cell with pretty text can be made using either html or markdown. (You can see how a cell with text was made by selecting it and hitting the button in the upper left that looks like an eye with a slash through it.) (Note that if a cell has too many lines in it, then it does not work, or at least does not produce output.)
  • Skim the tutorial Guided Tour and try some things in your journal.
Thu Aug 27 8am Biographical survey (counts as a journal) due. (No 5600 exploration due.)
Fri Aug 28
  • Read about Taylor's theorem. In your journal, state and prove Taylor's theorem with Lagrange form of the remainder. Be sure to cite your source(s).
  • To learn about some functions you likely will use today, do: var?, derivative?, plot?, points?, factorial?
  • Copy the sage cell on Taylor Series into your journal. Modify it so that it gives the Lagrange form of the remainder. Make it plot the function and the Taylor Polynomial.
  • For the function \(f(x)=\cos(x)\), we can easily bound \(|f^{(k+1)}(x)|\) and so can easily bound the Lagrange form of the remainder. For this function, illustrate graphically that the actual remainder satisfies the bound you obtained.
2
Mon Aug 31
  • Catch up
Tue Sep 1 8am journal for Aug 26-28 draft due; I will make comments and corrections but not grade it.
Wed Sep 2
  • Find your partner for this week's tasks and journal, and sit next to them.
  • Read the Good Problems handout on Flow. All future journals will have some points for demonstrating the flow skills.
  • In deciding how much to write, a good standard is: If someone reads only the text (none of the code) in your journal, it should still make sense to them.
  • To learn about some functions you likely will use today, do: expand?, show?, point?
  • Read about Interpolation. In a few sentences, summarize what it is.
  • Read about Polynomial interpolation. In a few sentences, summarize what it is. State and prove the polynomial interpolation error/remainder, assuming the function is sufficiently differentiable. Be sure to cite your source(s).
  • Read about the Lagrange Polynomial. In a few sentences, summarize what it is. Read the example, reproduce it (making sage do most of the work), and plot the result to show it interpolates as desired.
Thu Sep 3 8am journal for Aug 26-28 (and 5600 exploration) due.
Fri Sep 4 (drop deadline)
  • Upload the rating file to your (individual) project. In it rate your partner from last week.
  • Read about lists, the for statement, range, defining functions
  • Make a function that inputs a list of points \([x_0,\dots,x_{n-1}]\) and an index \(k\) with \(0\le k \le n-1 \) and outputs the Lagrange interpolating polynomial that is 1 at \(x_k\) and 0 and the other \(x_i\).
  • Make a function that inputs a list of points \([x_0,\dots,x_{n-1}]\) and values \([y_0,\dots,y_{n-1}]\) and outputs the interpolating polynomial that passes through all \((x_i,y_i)\). It should use the function you made above.
  • Test your function on the example we used earlier.
3
Mon Sep 7 Labor day holiday, no class
Wed Sep 9
  • Find your partner for this week's tasks and journal, and sit next to them.
  • One of you create a project in which to work on your journal, using the naming convention "3 Name1 and Name2". Set the other person and me as collaborators on that project.
  • Read the Good Problems handout on Introductions and Conclusions. All future journals will have some points for including an introduction and a conclusion.
  • Read about Rate of convergence.
  • Read about Newton's Method. State and prove the quadratic convergence of Newton's method (under certain assumptions).
  • Make a function that inputs \(f\), \(x_0\), and \(k\) and outputs a list of the results of performing Newton's method \(k\) times starting at \(x_0\). (Use N() on the input \(x_0\) to make sure the computation is numerical rather than symbolic.)
  • Use your function to demonstrate that Newton's method has quadratic convergence when applied to \(f(x)=x^2-2\) starting at \(x_0=3\).
Thu Sep 10 8am journal for Sep 2-4 (and 5600 exploration) due.
Fri Sep 11
  • Rate your partner from last week.
  • Read about the Secant method (see also here). State and prove the convergence rate of the secant method (under certain assumptions).
  • Make a function that inputs \(f\), \(x_0\), \(x_1\), and \(k\) and outputs a list of the results of performing the secant method \(k\) times starting with \(x_0\) and \(x_1\).
  • Use your function to demonstrate that the secant method has the claimed rate of convergence when applied to \(f(x)=x^2-2\) starting with \(x_0=3\) and \(x_1=2\).
4
Mon Sep 14
  • Find your partner for this week's tasks and journal, sit next to them, and set up a project for your journal.
  • Read the Good Problems handout on Logic. Starting with this journal, you need to make your logic clear and use logical connectives.
  • Read about Numerical Integration. In a few sentences, summarize what it is.
  • Read about the Trapezoid(al) Rule. Write a (sage/python) function that inputs a function \(f\), a number \(a\), and a number \(b\) and outputs the trapezoidal approximation to \(\int_a^b f(x) dx\). (Do the single-interval trapezoidal rule, not the composite rule.)
  • Write similar functions for the (single-interval) midpoint-rule and Simpson's rule.
  • Each of these three methods is supposed to be exact for polynomials up to some degree and not further. For each method, state the supposed exactness degree and use your functions to demonstrate that this degree is correct.
Tue Sep 15 8am journal for Sep 9-11 (and 5600 exploration) due.
Wed Sep 16
  • Rate your partner from last week.
  • Read about Newton-Cotes formulas. In a few sentences, summarize what they are. (Also read about their error analysis.)
  • Write a function that inputs a function \(f\), numbers \(a\), \(b\), and \(n\), and a (sage/python) function \(R\) like the ones you made Monday, and outputs an approximation to \(\int_a^b f(x) dx\) using a composite rule with \(n\) intervals and the method \(R\) on each interval.
  • Test your function using the three methods from Monday on the integral \(\int_1^{3/2} x^2 \ln(x) dx\). Which method performs best? Does this agree with their theoretical performance? Explain your conclusions.
Fri Sep 18
  • Determine the values of \(c_1\), \(c_2\), and \(x_2\) that make the approximation \(\int_0^2 f(x)\,dx\approx c_1 f(0)+ c_2f(x_2)\) as accurate as possible. Validate your choices with a test.
5
Mon Sep 21
  • Find your partner for this week's tasks and journal, sit next to them, and set up a project for your journal.
  • Familiarize yourself with NumPy.
  • Do "import numpy" and "from numpy.random import randn" and then use randn to generate a random scalar \(a\), and three random \(10\times 10\) matrices \(A\), \(B\), and \(C\).
  • Do "from numpy import identity,zeros,dot" and use these to create the identity matrix \(I\) and zero matrix \(O\).
  • Read about Norm and Matrix norm. From numpy.linalg import norm. To test an equality like \(A=B\), we can check \(\|A-B\|\approx 0\).
  • Test the following equalities
    • \(O+A=A\)
    • \(A+B=B+A\)
    • \(A+(B+C)=(A+B)+C\)
    • \(IA=A\)
    • \(AB=BA\)
    • \(A(BC)=(AB)C\)
    • \(a(B+C)=aB+aC\)
    • \(A(B+C)= AB+AC\)
Tue Sep 22 8am journal for Sep 14-18 (and 5600 exploration) due.
Wed Sep 23
  • Rate your partner from last week.
  • Read about eigenvalues and eigenvectors. In a few sentences, summarize what they are.
  • From numpy.linalg import eig. Create a random \(10\times 10\) matrix \(A\) and compute its eigenvalues and eigenvectors using eig. Run a test to verify that they really are eigenvalues and eigenvectors.
Fri Sep 25
  • Read about invertible matrices. In a few sentences, summarize what they are.
  • From numpy.linalg import inv. Create a random \(10\times 10\) matrix \(A\) and compute its inverse using inv. Run a test to verify that the inverse satisfies the properties that it is suppose to.
6
Mon Sep 28
  • Find your partner for this week's tasks and journal, sit next to them, and set up a project for your journal.
  • Read about the Singular Value Decomposition (SVD). State its definition.
  • Generate a random \(10\times 7\) matrix \(A\), compute its SVD using numpy.linalg.svd, and run tests to show the results satisfy the definition of the SVD.
  • Read about the (Moore-Penrose) pseudoinverse. State its definition.
  • Use numpy.linalg.pinv to compute the psuedoinverse and run tests to show it satisfies the definition.
  • Use the SVD of \(A\) produced by svd() to construct the psedoinverse of \(A\) and compare with the one produced by pinv().
Tue Sep 29 8am journal for Sep 21-25 (and 5600 exploration) due.
Wed Sep 30
  • Rate your partner from last week.
  • Read about Systems of linear equations
  • Create a random \(10\times 10\) matrix \(A\) and random \(10 \times 1\) vector \(y\). Compute \(b = Ay\) and then use numpy.linalg.solve to solve \(Ax=b\) for \(x\). Compare \(x\) and \(y\).
  • Let \(B\) be the \(10\times 9\) matrix containing the first 9 columns of \(A\). Use the pseudoinverse \(B^+\) to "solve" \(Bz=b\) for \(z\). Compare \(z\) with \(y\) and \(Bz\) with \(b\). How should we interpret \(z\)? How can we test that \(z\) is correct?
Fri Oct 2 Reading day holiday, no class
7
Mon Oct 5
MATH 4600 students:
Sometime this week, browse SIURO.
MATH 5600 students:
For your exploration due next week:
  • Read a paper from SINUM or SISC.
  • Write a paragraph or two summarizing (in your own words) what the paper is about.
  • Do some small sage/python computation somehow related to the paper.
  • Include the full citation to the paper in your journal and upload a copy of the paper.
  • Find your partner for this week's tasks and journal, sit next to them, and set up a project for your journal.
  • Read about Numerical ordinary differential equations.
    • Define what it means for a method to be "consistent".
    • Define what it means for a method to be "convergent".
    • Define what it means for a method to have "order p".
  • Read about the Euler method. Prove that the Euler method is consistent.
  • Make a function that does one step of the Euler method. The inputs are
    • \(f\), which defines the differential equation \(\dot{\mathbf{x}} = f(\mathbf{x},t)\);
    • \(\mathbf{x}_0\), the initial value of \(\mathbf{x}\);
    • \(t_0\), the initial value of \(t\); and
    • \(h\), the step size in \(t\).
    The output is the approximate value of \(\mathbf{x}(t_0+h)\).
  • Make a function of the same form that does one step of the (explicit) Midpoint Method.
  • Validate your codes by reproducing the Euler and Midpoint parts of these vector form exercises.
Tue Oct 6 8am journal for Sep 28-30 (and 5600 exploration) due.
Wed Oct 7
  • Rate your partner from last week.
  • Fix \(\mathbf{x}_0=2\), \(t_0=0\), and \(h=1/3\). Test your Euler and Midpoint codes versus the exact solution for the ODEs defined by \(f(\mathbf{x},t)=0\), \(f(\mathbf{x},t)=1\), \(f(\mathbf{x},t)=t\), and \(f(\mathbf{x},t)=t^2\). What do the results indicate about the consistency, convergence, and/or order of these two methods?
  • Fix \(\mathbf{x}_0=\left[\begin{array}{c}1\\0\end{array}\right]\), \(t_0=0\), and \(f(\mathbf{x},t)= f\left(\left[\begin{array}{c}x_1\\x_2\end{array}\right],t\right) =\left[\begin{array}{c}x_2\\-x_1\end{array}\right]\). Test your Euler and Midpoint codes versus the exact solution as \(h\rightarrow 0^+\). What do the results indicate about the consistency, convergence, and/or order of these two methods?
Fri Oct 9
  • Read about Runge-Kutta methods. Write a function similar to your Euler and Midpoint codes that implements "the" Runge-Kutta 4 method. Run tests on it like you did on Wednesday. What do the results indicate about the consistency, convergence, and/or order of the RK4 method?
8
Mon Oct 12
MATH 4600 students:
Browse SIURO more.
MATH 5600 students:
For your exploration due next week, explore another paper from SINUM or SISC.
  • Find your partner for this week's tasks and journal, sit next to them, and set up a project for your journal.
  • Make a function that does several steps of an ODE method. The inputs should be:
    • \(f\), which defines the differential equation \(\dot{\mathbf{x}} = f(\mathbf{x},t)\);
    • \(\mathbf{x}_0\), the initial value of \(\mathbf{x}\);
    • \(a\), the initial value of \(t\);
    • \(b\), the final value of \(t\);
    • \(n\), the number of steps to take in \(t\) to get from \(a\) to \(b\); and
    • \(M\), a function that does a single ODE step, like the ones you made last week.
    The outputs should be:
    • \(T\), an array with the values of \(t\) used and
    • \(X\), an array with the computed values of \(x\) at those values of \(t\).
  • Validate your code on the vector form exercises.
  • Fix \(\mathbf{x}_0=\left[\begin{array}{c}1\\0\end{array}\right]\), \(a=0\), \(b=2\pi\), and \(f(\mathbf{x},t)= f\left(\left[\begin{array}{c}x_1\\x_2\end{array}\right],t\right) =\left[\begin{array}{c}x_2\\-x_1\end{array}\right]\). Test your Euler, Midpoint, and RK4 codes versus the exact solution as \(n\rightarrow \infty\). What do the results indicate about the consistency, convergence, and/or order of these methods?
Tue Oct 13 8am journal for Oct 5-9 due.
Wed Oct 14
  • Rate your partner from last week.
  • Read about adaptive stepsize.
  • Make a function that adaptively chooses the step size. The inputs should be
    • \(f\), \(\mathbf{x}_0\), \(a\), \(b\), and \(M\) as above;
    • \(M_2\), a higher-order method than \(M\); and
    • \(\epsilon\), a target accuracy.
    The outputs should be:
    • \(T\), an array with the values of \(t\) used, with last entry \(b\), and
    • \(X\), an array with the computed values of \(x\) at those values of \(t\).
    At each step it should try both \(M\) and \(M_2\) with the current \(h\). If the difference is more than \(\epsilon/(h(b-a))\) then reject that step and try again with \(h\mapsto h/2\); if it is less than \(\epsilon/(h(b-a))\) then take that step and consider increasing \(h\). (Note that this algorithm is different than in the adaptive stepsize description.)
  • Fix \(x_0=1\), \(a=0\), \(b=1\), and \(f(x,t)=-\sin(10\pi t^2(3-2t))(60\pi t(1-t))\), which has exact solution \(x(t)=\cos(10\pi t^2(3-2t))\). Test your function using Euler for \(M\), Midpoint for \(M_2\), and \(\epsilon=10^{-3}\). Plot the output (as points) and the exact solution to demonstrate that you have a good approximation and that \(h\) is adapting.
Thu Oct 15 8am 5600 exploration about a paper due.
Fri Oct 16 Catch up.
9
Mon Oct 19
  • Find your partner for this week's tasks and journal, and sit next to them.
  • Read about Numerical Differentiation and these examples on determining the coefficients and order for a method.
  • Determine the coefficients \(a_1\), \(a_2\), and \(a_3\) so that \(f'(x_0)=\frac{a_1f(x_0)+a_2f(x_0+h) +a_3f(x_0+2h)}{h} +\mathcal{O}(h^p)\) for the largest possible \(p\).
  • Determine the coefficients \(b_1\), \(b_2\), and \(b_3\) so that \(f''(x_0)=\frac{b_1f(x_0)+b_2f(x_0+h) +b_3f(x_0+2h)}{h^2} +\mathcal{O}(h^q)\) for the largest possible \(q\).
  • Write functions to implement your formulas. Test them on \(f(x)=e^{3x}\) at \(x_0=2\) using \(h=2^{-i}\) for \(i=0,1,2,\dots,15\) to verify the \(p\) and \(q\) you determined above.
Tue Oct 20 8am journal for Oct 12-16 due.
Wed Oct 21
  • Rate your partner from last week.
  • Read about Loss of Significance.
  • Repeat your test from Monday but let \(i\) go up to 31 and describe the results. Make log-log plots showing the errors as functions of \(h\).
Thu Oct 22 8am 5600 exploration about a paper due.
Fri Oct 23
  • Upload talktemplate.tex and OHIOCLR.pdf. Modify talktemplate.tex into a short but coherent talk on Numerical Differentiation and Loss of Significance, using your results from Monday and Wednesday. Do the first derivative case only. Include the graph you made Wednesday. Your main product today is the resulting slides; in your journal comment briefly on problems you encountered, cool things you learned, etc.
10
Mon Oct 26 Think about what paper you want to do for your final project. The goal of the project is to validate (or refute) the analysis and numerical results presented in the paper. Here are some aspects to consider:
  • It is best if the paper is from SIURO for 4600 students or SINUM or SISC for 5600 students.
  • It is best if the paper is recent, so the method in it is neither well-established nor discredited.
  • Avoid papers that give subtle improvements for complicated problems. They likely need too much coding.
  • Look for a paper whose numerical results are based on simple-to-reproduce test problems. If it uses any data sets, make sure they are publically available.
MATH 4600 students:
Decide if the three of you will do the project together, two will be together and one alone, or all three alone. I will adjust my expectations based on the number of people working on the project. By Friday let me know the grouping and propose the paper(s) you want to work on.
MATH 5600 students:
For your exploration due Thursday, decide on the paper you want to work on. It can be one you did an exploration on or a new one. Explain why you think this a good choice for the project. I will either accept it or tell you to look for another.
Tue Oct 27 8am journal for Oct 19-23 due.
Wed Oct 28
  • Find your partner for this week's tasks and journal, sit next to them, and set up a project for your journal.
  • Rate your partner from last week.
  • (Re)read about Matrix norm. State the formula for the matrix norm induced by \(\|\cdot\|_2\) in terms of the singular values.
  • Write a function that inputs a matrix \(A\) and outputs its matrix norm induced by \(\|\cdot\|_2\).
  • Read about Condition Number. Summarize in your own words. State the relationship between condition number and the error in solving a linear system. State the formula for the condition number of a matrix with respect to \(\|\cdot\|_2\) in terms of the singular values.
  • Write a function that inputs a matrix \(A\) and outputs its condition number with respect to \(\|\cdot\|_2\).
  • Write a function to construct a random-looking square matrix with specified size, norm, and condition number. The inputs should be:
    • \(m\), the size of the matrix;
    • \(n\), the norm of the matrix; and
    • \(k\), the condition number of the matrix.
    The output is \(A\), which is a \(m\times m\) matrix with norm \(n\) and condition number \(k\).
  • Validate your three functions against each other.
Thu Oct 29 8am 5600 project proposal (counts as an exploration) due.
Fri Oct 30 (drop deadline with WP/WF)
  • Write a function to test how the error in solving a linear system depends on \(m\), \(n\), and \(k\), as used above. The inputs are \(m\), \(n\), and \(k\). The function should create \(A\) with that size, norm, and condition number; create a \(m\times 1\) vector \(y\); compute \(b=Ay\); solve \(Ax=b\) for \(x\), and return the relative error between \(x\) and \(y\).
  • State the theoretical dependence of that relative error on \(m\), \(n\), and \(k\). Use your function to test this dependence.
11
Mon Nov 2
  • Look at NumericalClass/ratinganalysis.sagews for how the ratings of partners will be used to adjust journal grades. If you can think of a better way to make adjustments, please suggest it.
  • Work on your project.
Tue Nov 3 8am journal for Oct 28-30 due.
Wed Nov 4
  • Find your partner for this week's tasks and journal, sit next to them, and set up a project for your journal.
  • Rate your partner from last week.
  • Read the Good Problems handout on Graphs. Starting with this journal, pay extra attention to titles, labels, and legends on your graphs.
  • Read about Analysis of algorithms.
  • Suppose \(A\) and \(B\) are \(k\times k\) matrixes. Determine the number of multiplications needed to compute \(C=AB\), as a function of \(k\).
  • Read about the python timeit library. Sage has its own timeit function, so to get the python one, do "import timeit as pytimeit".
  • Run the code:
    import timeit as pytimeit
    s = lambda k : "from numpy import dot; from numpy.random import randn; A=B=randn("+str(k)+","+str(k)+")"
    ks = [2**j for j in range(10)]
    T = [pytimeit.timeit("C=dot(A,B)",setup=s(k),number=2**13/k)/(2**13/k) for k in ks]
    plot_loglog(points(zip(ks,T)))
    Explain what it does. Analyze T further to determine how well it agrees with your analysis on the number of multiplications. Produce at least one illustrative graph (with title, axis labels, and legend).
  • Perform a similar analysis for multiplying a \(k\times k\) matrix on a \(k\times 1\) vector.
Thu Nov 5 8am 5600 exploration due. It can (should) be related to your project.
Fri Nov 6
  • Read about the Fast Fourier transform. What is the point of it?
  • Read about numpy.fft.
  • Run tests on numpy.fft.fft similar to those you did for matrix-vector multiplication. How well do they agree with the theoretical results?
12
Mon Nov 9
  • How long should the final project presentations be? Nominally, we have (3 classes)(55 minutes/class)/(16 presentations) = 10.5 minutes/presentation but transition costs will reduce that to 8 minutes. If we run past the end of class then they could be longer.
  • Work on your project.
Tue Nov 10 8am journal for Nov 4-6 due.
Wed Nov 11 Veterans day holiday, no class
Thu Nov 12 8am 5600 exploration due. It can (should) be related to your project.
Fri Nov 13
  • Rate your partner from last week.
  • Find your partner for this week's tasks and journal, sit next to them, and set up a project for your journal. You will keep this partner next week.
  • Read about Stiff equations. What are they?
  • The description above has a motivating example of the ODE \(\dot{x}=-15x\) with \(x_0=1\) on \(t\in [0,1]\) and shows what the Euler method does for \(h=1/4\) and \(h=1/8\). Apply your Euler, midpoint, and RK4 programs from Week 7 using your (non-adaptive) ODE stepping program from Week 8 to this ODE. Produce a plot with the exact solution these three methods using \(h=1/4\) and a second plot using \(h=1/8\). Interpret the results.
13
Mon Nov 16
  • Notice the presentation and report guidelines at the end of the schedule.
  • Work on your project.
Wed Nov 18
  • The second order ODE \(\ddot{x}+1001\dot{x}+1000x=0\) with \(x(0)=1\) and \(\dot{x}(0)=0\) has exact solution \(x(t)=-\frac{1}{999}\exp(-1000t)+\frac{1000}{999}\exp(-t)\). Plot this function on \([0,1]\) and observe how nicely it behaves.
  • It is equivalent to the first-order system \(\dot{\mathbf{x}} = \left[\begin{array}{cc} 0 & 1 \\ -1000 & -1001\end{array}\right] \mathbf{x}\) with \(\mathbf{x}_0 =\left[\begin{array}{c} 1 \\ 0\end{array}\right]\). Run your convergence test from Week 8 on this ODE on \(t\in [0,1]\) using Euler, midpoint, and RK4; measure error with respect to the exact solution \(x(t)\) above (not the exact \(\mathbf{x}(t)\)). Interpret the results. How small does \(h\) need to be to get error less than \(1/10\)?
Thu Nov 19 8am rough draft of final project due. For 5600 students counts as an exploration.
Fri Nov 20
  • Coding tips:
    • Pull out chunks as their own functions/ subroutines and test them separately.
    • Put a comment before each line saying what it is supposed to do and what type of object (array, list of k vectors, ...) it creates. Check the comments versus the algorithm to make sure what they say agrees with what is supposed to happen. Then check the code line against the comment to make sure the code does what the comment says it does.
  • Read about Explicit and implicit methods. State the distinction between them.
  • Make a function that does one step of the Backward Euler method. Have the same inputs and outputs as your Euler method did in Week 7. To solve the equation for the next value of \(x\), use scipy.optimize.root.
  • Repeat your tests from Wednesday using your Backward Euler function. Compare and contrast with the results from Wednesday.
14
Mon Nov 23
  • Rate your partner from last week.
  • Look in NumericalClass/partners.sagews for the presentation order.
  • Work on your presentation.
Tue Nov 24 8am journal for Nov 13, 18, and 20 due. (No 5600 Exploration this week or next.)
Wed Nov 25 Thanksgiving holiday, no class
Fri Nov 27 Thanksgiving holiday, no class
15
Mon Nov 30 Presentations:
  • Must be at least 10 and at most 15 minutes long.
  • Must use \(\LaTeX\) slides in the beamer class.
  • Aim for half the presentation to explain to the class what the paper is about and half to show what you did.
  • Worth 10% of your project grade.
  • You will rate each other
Wed Dec 2 More presentations
Fri Dec 4 More presentations
16
Wed Dec 9 Final Exam 12:20-2:20 pm (virtual, your presence is not required).
  • Presentation slides due.
    • You can improve them based on feedback from your presentation.
    • Worth 10% of your project grade.
  • Project report due. The grading is based on the following rubric:
    • Introduction (5%)
    • Conclusion (5%)
    • Logical Connectives (5%)
    • Flow (5%)
    • Graphs (5%)
    • References, citations, quoting, attribution (5%). These points are for properly attributing bits from the paper that your project is on. Improperly taking material from other sources (including Wikipedia) will be considered academic misconduct.
    • Your analysis of their analysis (20%). Summarize the central points of what they tried to do. Walk through the main algorithm and analysis. Expand and fill in details on some small piece. (Limit your analysis to what is in the paper; you do not need to verify statements using other sources. Ignore side issues, generalizations, and special cases when possible.)
    • Your reproduction of their numerical results (30%). Since the amount and difficulty of the numerical results in the papers varies widely, please consult with me on which parts to reproduce.

Unused bits....

Root finding

Interpolation

Linear Algebra

Quadrature

Differential Equations

Unfiled


Martin J. Mohlenkamp
Last modified: Mon Nov 23 14:13:35 EST 2015