Math/CS 466/666

466/666 NUMERICAL METHODS I (3+0) 3 credits

Instructor  Course Section                     Time              Room
------------------------------------------------------------------------
Eric Olson  Math 466/666 Numerical Methods I   TR 3:00-4:15pm    DMS106

Course Information

Instructor:: Eric Olson
email:: ejolson at unr dot edu (better to contact me through WebCampus).
Office:: DMS 238 and through Zoom by appointment.
Homepage:: https://fractal.math.unr.edu/~ejolson/466-21/
Assistant:: Jordan Blocher
Live Stream:: If you can't come to class due to sickness, quarantine or other reasons, please join via the Zoom link in WebCampus.
Required Texts:: Justin Solomon, Numerical Algorithms: Methods for Computer Vision, Machine Learning and Graphics, CRC Press, 2015.
Supplemental Texts on Numerical Methods:: Anthony Ralston and Philip Rabinowitz, A First Course in Numerical Analysis, Second Edition, Dover, 1978.; Richard Hamming, Numerical Methods for Scientists and Engineers, Second Edition, Dover, 1986.

Information about Software

The Julia 1.6 Language, official documentation and software download.
Thomas Breloff, Plots--Powerful Convenience for Visualization in Julia.
Jupyter Lab, A Comprehensive List of Links for the Juptyer Project.

Lecture Notes

Aug 24 -- Outline of course and Newton's method
Aug 26 -- Rate of convergence of Newton's method
Aug 31 -- Double precision base-2 floating point
Sep 02 -- Introduction to Julia (newton.jl)
Sep 07 -- Rounding errors and loss of precision
Sep 09 -- The Kahan summation formula
Sep 14 -- Gaussian elimination (gauss.jl)
Sep 16 -- Operation count of LU factorization
Sep 21 -- Matrix 1 and ∞ norms
Sep 23 -- Condition number of a matrix
Sep 28 -- Homework and the log1p function
Sep 30 -- A=QR and Hausholder reflectors
Oct 05 -- Do-it-yourself Hausholder (hhqrscript.jl, hhqr.jl)
Oct 07 -- Starting project 1 (cholesky.jl)
Oct 12 -- Applications of eigenvectors
Oct 14 -- Theory on eigenvalues and eigenvectors
Oct 19 -- Power method for the largest eigenvalue
Oct 22 -- Review for the midterm exam
Oct 28 -- Shifted inverse power method (shiftpower.jl)
Nov 02 -- Deflation and the QR method (deflate.jl)
Nov 04 -- The shifted QR method (shiftedqr.jl)
Nov 09 -- The matrix 2 norm and the SVD
Nov 16 -- The polynomial interpolation theorem
Nov 18 -- The Lagrange polynomial basis (lagrange.jl)
Nov 23 -- Inverse Interpolation (iint.jl)
Nov 30 -- Analysis of Inverse Interpolation
Dec 07 -- Review

Student Learning Outcomes

Upon completion of this course

Students will be able to implement a numerical method to solve a nonlinear equation using the bisection method and Newton's method.
Students will be able to solve linear systems using direct and iterative methods.
Students will be able to construct interpolating functions.

Announcements

[13-Dec-2021] Exam 1 Solutions

I have posted my solutions of Exam 1 for your convenience. Please look at my solutions to see if there are any improvements you can make to yours or I can make to mine.

[11-Dec-2021] Homework 2 Solutions

I have posted my solutions of Homework 2 for your convenience. Please look at my solutions to see if there are any improvements you can make to yours or I can make to mine.

[15-Dec-2021] Final Exam

The final exam will be held in person on Wednesday, December 15 from 2:30 to 4:30pm at DMS 106. Given the excellent results on the computing exam last week, the final will consist of only a written exam and no computing component. Please prepare and know the topics listed on review for the in-class midterm that was given October 26 along with the following additional topics:

State the power method for finding the eigenvector corresponding to the (unique) eigenvalue of largest magnitude for a matrix A (Oct 7 and 19)
Given the eigenvalues of B=A^TA be able to compute the matrix 2 norm of A (Nov 9)
Be able to find an interpolating polynomial through given points (x_i,y_i) using the Lagrange basis functions (Nov 18)
Proof of the polynomial interpolation theorem (Nov 16 and 18)
Relationship between the QR and Cholesky factorization (Homework 2)
Analysis of the matrix A=uv^T where u^Tv=1 (Homework 2)

Note this is a closed-book, closed-notes, no computers and calculators exam. Attendance is mandatory to take the test unless you have made arrangements with the DRC or have other special considerations. Please bring your student identification to the final.

[02-Dec-2021] Computing Exam

The in-class computing exam will be Thursday December 2. This will be an open book, open notes, open web browser and web search exam. Do not use any email, post questions to forums or use any other type of electronic messaging service during the exam.

In preparation please know how to perform the following:

Given a matrix A find the Hausholder reflector H so the first column of HA is a vector of the form ce₁, that is, the first column has been reduced to a non-zero element below which are all zeros.
Perform n iterations of Newtons method for a specified function f starting from a specified initial condition x₀.
Given a matrix A and a starting vector X₀ perform n iterations of the power method to approximate the eigenvector whose eigenvalue is largest in magnitude. Use the Rayleigh quotient (least squares) to approximate the eigenvalue.
Given a specified sequence a_n use the Kahan summation formula to accurately find the sum for n=1,2,...,N of the terms a_n. That is, compute Σ_n=1^N a_n using Kahan summation.
Find the interpolating polynomial through specified points (x_k,y_k) for k=1,2,...,n and evaluate that polynomial at the point x=α.

You will be asked to complete two of four problems based on the above material to receive full credit. For Math 666 or extra credit please complete a third problem. Note this exam is meant to test that you can use the computer for practical computation. It is fine to bring your own notebook computer to use during the exam but please make sure you have sufficient power and that the software is properly installed.

[15-Dec-2021] Final Exam

The final exam will be held on Wednesday, December 15 from 2:30 to 4:30pm at DMS 106.

[15-Dec-2021] Project 2

This project explores the polar decomposition of an invertible matrix. Please form your own teams on WebCampus consisting of 3 to 4 students and welcome any student who wishes to join your group so no people are left out. If you prefer to work independently that is also fine. Each team should present their work in the form of a typed report using clear and properly punctuated English. Pencil and paper calculations may be typed or hand written. Where appropriate include full program listings and output. Every team member should participate in the work and be prepared to independently answer questions concerning the material. One report per team must be submitted through WebCampus as a single pdf file to complete this project.

[27-Oct-2021] Homework 2

Please work the following problems from our text:

Problems 5.7, 5.8, 5.12
Problems 6.3, 6.6, 6.11

These problems will be due on Nov 30, 2021.

[10-Nov-2021] Project 1 Solutions

I have posted my solutions of Project 1 for your convenience. Please look at my solutions to see if there are any improvements you can make to yours or I can make to mine.

[26-Oct-2021] In Class Written Exam

There will be a written exam in class on Tuesday October 26 covering the following topics from the lecture and homework:

Statement of Newton's method (Aug 26)
Proof and interpretation of quadraditic convergence (Aug 26)
Example of loss of precision (Sep 7)
Backwards error analysis and condition number (Sep 7 and Sec 23)
Compute matrix 1 and ∞ norms (Sep 21)
Prove Hausholder reflector is an othogonal matrix (Sep 30)
Eigenvectors of distinct eigenvalues are independent (Oct 14)
Eigenvalues of a Hermitian matrix are real (Oct 14)
Factor a matrix A into LU by hand (Homework 1)
Operations for interval arithmetic (Homework 1)

No computers or calculators will be allowed. Attendance is mandatory to take the test unless you have made arrangements with the DRC or have other special considerations. Please bring your student identification to the exam.

[17-Oct-2021] Homework 1 Solutions

I have posted my solutions of Homework 1 for your convenience. Please look at my solutions to see if there are any improvements you can make to yours or I can make to mine.

[01-Oct-2021] Homework 1 Due

Please turn in your homework as a scanned pdf file to WebCampus by midnight on Friday October 1.

[24-Sep-2021] Project 1

This project explores the Cholesky factorization of a symmetric positive definite matrix. For this project the class has not been randomly grouped into teams. Instead, please form your own teams on WebCampus consisting of 3 to 4 students. Please welcome any student who wishes to join your group so no people are left out. If you prefer to work independently that is also fine.

Each team should present their work in the form of a typed report using clear and properly punctuated English. Pencil and paper calculations may be typed or hand written. Where appropriate include full program listings and output. Every team member should participate in the work and be prepared to independently answer questions concerning the material. One report per team must be submitted through WebCampus as a single pdf file to complete this project.

prog1.pdf, prog1b.dat, prog1c.dat.

[09-Sep-2021] Homework 1

Please work the following problems from our text:

Problems 2.4, 2.5, 2.9, 2.11
Problems 3.1, 3.3, 3.11, 3.12

These problems will be due on Oct 1, 2021.

[23-Aug-2021] Welcome to Fall 2021

I am looking forward to seeing you Tuesday. As you may know, the campus currently has mandatory mask rules in place. To avoid people getting sick while attending class not only is it import to follow these and related guidelines, but to understand the spirit in which these rules were made. Please employ your best judgment to prevent the spread of the epidemic and its contagious variants.

Do not come to class if you are sick--even if it's something other than COVID-19. If you are subject to quarantine because of exposure to the disease, please stay home. If you are already sick or in quarantine and can't come on the first day of class, check the WebCampus page for this course later today for the Zoom link and other information.

While this section of Math 466/666 is not high-flex, in anticipation of increased absences due to the epidemic I will live-stream our class meetings each day at a link available in WebCampus and maintain an online archive of course materials including lecture notes, assignments and other announcements. Unless there is a change in policy, in-person attendance will be required for all exams and the final.

Last year I discovered that Zoom worked well for office hours as it provided greater flexibility to meet with students: Our meeting times can be arranged around individual schedules and there is no need to go to campus just to ask a question. Please send me a message on WebCampus to schedule all office hours.

As in previous semesters, students should avoid congregating around instructional space entrances before or after class sessions and exit the instructional space immediately after the end of instruction to help ensure social distancing and allow for the persons attending the next scheduled class session to enter. Note that students who cannot wear a face covering due to a medical condition or disability, or who are unable to remove a mask without assistance may seek accommodation through the Disability Resource Center.

[22-Aug-2017] Textbook Announced

The primary textbook we will be using for the course is Numerical Algorithms: Methods for Computer Vision, Machine Learning and Graphics by Justin Solomon. A free pdf version of this book is available from Justin's website at CSAIL MIT. This is a standard numerical methods text covering the standard topics that includes a few remarks about computer vision and machine learning. Hardbound versions may be obtained from Amazon and other online booksellers

Grading

     1 Exam on Theory          50 points
     1 Exam on Computing       50 points
     1 Final Exam             100 points
     2 Homework Assignments    20 points each
     2 Programming Projects    30 points each
    ------------------------------------------
                              300 points total

Exams and quizzes will be interpreted according to the following grading scale:

    Grade        Minimum Percentage
      A                 90 %
      B                 80 %
      C                 70 %
      D                 60 %

The instructor reserves the right to give plus or minus grades and higher grades than shown on the scale if he believes they are warranted.

Final Exam

The final exam will be held in person on Wednesday, December 15 from 2:30 to 4:30pm at DMS 106.

Course Policies

Communications Policy

Lectures and classroom activities will held in person and live streamed through through Zoom at the scheduled meeting time listed in MyNevada for this course. Please check the canvas page for the Meeting ID and Join URL under the Zoom tab if you are unable to make it to class. If you wish to set up an appointment for office hours please send me a message through WebCampus.

Late Policy

Students must have an approved university excuse to be eligible for a make-up exam. If you know that you will miss a scheduled exam please let me know as soon as possible. Homework may be turned in late--with a possible deduction of points depending on the circumstances--as long as I have not already graded the assignment.

Plagiarism

Students are encouraged to work in groups and consult resources outside of the required textbook when doing the homework for this class. Please cite any sources you used to complete your work including Wikipedia, other books, online discussion groups as well as personal communications. Exams and quizzes, unless otherwise noted, will be closed book, closed notes and must reflect your own independent work. Please consult the section on academic conduct below for additional information.

Diversity

This course is designed to comply with the UNR Core Objective 10 requirement on diversity and equity. More information about the core curriculum may be found in the UNR Catalog here.

COVID-19 Policies

Statement on COVID-19 Training Policies

Students must complete and follow all guidelines as stated in the Student COVID-19 Training modules, or any other trainings or directives provided by the University.

Statement on COVID-19 Face Coverings

In response to COVID-19, and in alignment with State of Nevada Governor Executive Orders, Roadmap to Recovery for Nevada plans, Nevada System of Higher Education directives, the University of Nevada President directives, and local, state, and national health official guidelines face coverings are required at all times while on campus, except when alone in a private office. This includes the classroom, laboratory, studio, creative space, or any type of in-person instructional activity, and public spaces. A "face covering" is defined as a covering that fully covers a person's nose and mouth, including without limitation, cloth face mask, surgical mask, towels, scarves, and bandanas (State of Nevada Emergency Directive 024). Students that cannot wear a face covering due to a medical condition or disability, or who are unable to remove a mask without assistance may seek an accommodation through the Disability Resource Center.

Statement on COVID-19 Social Distancing

Face coverings are not a substitute for social distancing. Students shall observe current social distancing guidelines where possible in accordance with the Phase we are in while in the classroom, laboratory, studio, creative space (hereafter referred to as instructional space) setting and in public spaces. Students should avoid congregating around instructional space entrances before or after class sessions. If the instructional space has designated entrance and exit doors students are required to use them. Students should exit the instructional space immediately after the end of instruction to help ensure social distancing and allow for the persons attending the next scheduled class session to enter.

Statement on COVID-19 Disinfecting Your Learning Space

Disinfecting supplies are provided for you to disinfect your learning space. You may also use your own disinfecting supplies.

Contact with Someone Testing Positive for COVID-19

Students must conduct daily health checks in accordance with CDC guidelines. Students testing positive for COVID-19, exhibiting COVID-19 symptoms or who have been in direct contact with someone testing positive for COVID-19 will not be allowed to attend in-person instructional activities and must leave the venue immediately. Students should contact the Student Health Center or their health care provider to receive care and who can provide the latest direction on quarantine and self-isolation. Contact your instructor immediately to make instructional and learning arrangements.

Local, State and Federal COVID-19 Information

Statement on Academic Success Services

Your student fees cover usage of the University Math Center, University Tutoring Center, and University Writing and Speaking Center. These centers support your classroom learning; it is your responsibility to take advantage of their services. Keep in mind that seeking help outside of class is the sign of a responsible and successful student.

Equal Opportunity Statement

The University of Nevada Department of Mathematics and Statistics is committed to equal opportunity in education for all students, including those with documented physical disabilities or documented learning disabilities. University policy states that it is the responsibility of students with documented disabilities to speak with the Disability Resource Center during the first week of each semester to discuss appropriate accommodations to ensure equity in grading, classroom experiences and outside assignments. For assistance with accessibility, or to report an issue, please use the Accessibility Help Form. The form is set up to automatically route your request to the appropriate office that can best assist you.

Statement on Audio and Video Recording

Surreptitious or covert video-taping of class or unauthorized audio recording of class is prohibited by law and by Board of Regents policy. This class may be videotaped or audio recorded only with the written permission of the instructor. In order to accommodate students with disabilities, some students may be given permission to record class lectures and discussions. Therefore, students should understand that their comments during class may be recorded.

Academic Conduct

Bring your student identification to all exams. Work independently on all exams and quizzes. Behaviors inappropriate to test taking may disturb other students and will be considered cheating. Don't send electronic messages, talk or pass notes with other students during a quiz or exam. Homework may be discussed freely. When taking a quiz or exam over Zoom or in the classroom don't read notes or books unless explicitly permitted. Sanctions for violations are specified in the University Academic Standards Policy. If you are unclear as to what constitutes cheating, please consult with me.

Final Exam

The final exam will be held in person on Wednesday, December 15 from 2:30 to 4:30pm at DMS 106.

Last Updated: Tue Nov 23 08:39:53 AM UTC 2021