MATH 3NA3 - Numerical Linear Algebra

3 unit(s)

Conditioning and numerical stability, rounding and truncation errors, convergence rates, linear and nonlinear  systems of equations, eigenvalue problems, least squares, QR and singular-value decomposition, optimization.

Three lectures; one term

Prerequisite(s): MATH 2LA3 or MATH 2R03; and one of MATH 1MP3, COMPSCI 1MD3, DATASCI 2G03, PHYSICS 2G03

Course Description

Most problems in physics, engineering and applied mathematics are formulated in terms of equations (e.g. ordinary differential, partial differential, or stochastic) which cannot be solved analytically. However, one can almost always  reduce this one difficult problem to many simple problems which can be solved numerically on a computer. More    precisely, we reduce the problem to a large system of linear algebraic equations.

For an excellent explanation of what numerical analysis really is read Trefethen’sThe Definition of Numerical analysis. For a nice introduction to Numerical Analysis, I suggest reading Trefethen’s entry in thePrinceton    Companion to Mathematics.

This course will teach you efficient methods for solving very large systems of linear algebraic equations. With this knowledge as a foundation you will be able to easily tackle any advanced course in scientific computatio n or numerical analysis. You will also learn the basic mathematical concepts of numerical error analysis (i.e.        sensitivity, conditioning and accuracy) and estimation of computational complexity, which are essential for     developing a useful numerical algorithm.

The course material will be a mix of applied problems, theoretical analysis, algorithm development, and practical programming. matlab will be the computer language used for all examples and assignments, as it has been           developed explicitly for numerical linear algebra.

If you are not familiar with matlab, you prepare for the course by making sure you understand the basics of the user interface, programming and graphics. This will make it much easier to complete the assignments and practices         concepts we cover in class. I’ve provided short matlab tutorials on the Avenue page to help you get started.

Course Website

Avenue to Learn

Textbooks

Primary Textbook:

The primary text for the course is the Numerical Mathematics, 2nd edition by M R Grasselli & D E Pelinovsky, which is available as a pdf file to download on Avenue.

Supplementary:

•    A guide to Matlab (ebook)

•     McMaster also provides access to many e- books, includingNumerical Linear Algebra by Allaire and Kaber.

Software

Student edition of Matlab. We highly recommend that you buy this software. matlab is an essential part of this course and will be very useful in any future mathematically intensive courses.

If you don’t have matlab on your computer and don’t want to buy the student version you can also use Octave https://www.gnu.org/software/octave/  which is very similar.

Virtual Course Delivery (only applicable if the University decides to move courses online)

To follow and participate in virtual classes it is expected that you have reliable access to the following:

•     A computer that meets performance requirementsfound here.

•     An internet connection that is fast enough to stream video.

•     Computer accessories that enable class participation, such as a microphone, speakers and webcam when needed.

If you think that you will not be able to meet these requirements, please contactuts@mcmaster.caas soon as you can. Please visit theTechnology Resources for Students pagefor detailed requirements. If you use assistive             technology or believe that our platforms might be a barrier to participating, please contactStudent Accessibility    Services,sas@mcmaster.ca, for support.

Course Overview and Assessment

Outline

The course is organized as follows (note that the content is tentative). Please check the Avenue to Learn site             regularly for news, updated weekly lecture topics, assignments and information on the test and final exam. The text is supplemented with additional lecture material (e.g. indicated by “notes”) which is an integral part of the course.

1.    Introduction to the course scientific computation Matlab, §1. 1- 1.5, 1 lecture)

•     The matlab session.

•     Using matlab help (e.g. built-in functions).

using Matlab (m-file tutorials from website,A guide to

•     Working with matrices and vectors.

•     Advanced data structures: structure arrays, field arrays, cells.

•     Creating and printing figures.

•     Basic control structures (sequential, repetition, selection).

•     Editing, saving and executing scripts.

•     Functions, sub functions and cell mode.

•     Some useful built-in functions.

2.    Numerical solution of linear systems of equations (Chapters 1 and 2, 13 lectures)

•     Floating pointing point arithmetic. (§1.6)

•     Finite dimensional vectors spaces, linear maps, vector and matrix norms, sensitivity and conditioning, error bounds (lecture notes).

•     Direct methods: LU factorization (§2.2), computational complexity, sensitivity (§2.5).

•     Special matrices: symmetric positive definite, banded, sparse, Cholesky factorization (§3.6).

•     Iterative methods for solving linear systems: Jacobi, Gauss-Seidel, SOR (§2.4).

•     Convergence properties of iterations: necessary and sufficient conditions, rate of convergence.

3.    Nonlinear equations (zeros of a function) (Chapter 5, 3 lectures)

•     One dimension: interval bisection, fixed- point iteration, Newton’s method (§5. 1, 5.2).

•     Multi-dimensions (§5.3).

4.    Matrix factorizations, orthogonality and data fitting by least squares (Chapter 3, 9 lectures)

•     Symmetric and orthogonal matrices (§3. 1).

•     Orthogonal projections (§3.2).

•     Reduced QR factorization (§3.3, 3.4).

•     Least-squares method, data fitting (§3.5).

5.    Eigenvalues and eigenvectors (Chapter 4, 10 lectures)

•     Basic properties (§4. 1–4.3).

•     Power iteration, Rayleigh quotient iteration, deflation (§4.4).

•     Simultaneous iteration, orthogonal iteration, QR iteration, Hessenberg reduction (§4.5).

•     Singular Value Decomposition (§4.6).

•     Sensitivity (§4.7).

COURSE EVALUATION

Evaluation

There will be six bi-weekly assignments, one mid-term test, and a final exam.

This course may use proctoring software (TBD) for tests/exams. This software may require you to turn on your video camera, present identification, monitor and record your computer activities, and lockdown your browser during the exam. This software may be required to be installed before the exam begins. If you have questions about whether    this software will be used, or concerns about the use of this software, please contact your instructor.

Assignments

Six problem sheets will be given and marked for credit. Each assignment will have a significant Matlab component. Assignments are to be submitted as a pdf file on Avenue by 18:00 on the due date. No late assignments will be       accepted. Solutions to assignments and the test will be posted on Avenue. The tentative assignment schedule is:

Assignment posted Assignment due

September 9  September 23

October 7      October 28    November 11 November 25

September 23

October 7

October 21

November 11

November 25

December 9

Test

There will be one 1- hour test (during the regular class time):

Wednesday 26 October, 11:30- 12:30 (tentative)

The test will be posted as an Avenue quiz at 11:30 and you will have until 13:45 to submit your answers.

Final Exam

There will be a 2.5-hour final examination given on Avenue’s quizzing tool during the December examination period.

Grading System

The final mark will be calculated as follows:

Assessment

I reserve the right to change the weight of any portion of this marking scheme. If changes are made, your grade will be calculated using the original weightings and the new weightings, and you will be given the higher of the two        grades. At the end of the course the grades may be adjusted, but this can only increase your grade and will be done uniformly. I will use the grade equivalence chart in the university calendar to convert between letter grades, grade  points and percentages.

Important message

The instructor and university reserve the right to modify elements of the course during the term. The              university may change the dates and deadlines for any or all courses in extreme circumstances. If either type of modification becomes necessary, reasonable notice and communication with the students will be given      with explanation and the opportunity to comment on changes. It is the responsibility of students to check      their McMaster email and course websites weekly during the term and to note any changes. Announcements will be made in class and by using the course email distribution list.

REQUESTS FOR RELIEF FOR MISSED ACADEMIC TERM WORK

McMaster Student Absence Form (MSAF):  In the event of an absence for medical or other reasons, students should

review and follow the Academic Regulation in the Undergraduate Calendar “Requests for Relief for Missed Academic Term Work” .

If you MSAF an assignment that assignment will be treated as the lowest mark assignment and your assignment mark will be based on the other five assignments.

If you MSAF the test, the marks will be shifted to the final exam (resulting in a final worth 60% of your final grade). Note that MSAF-ing the test cannot improve your final grade!

ACADEMIC ACCOMMODATION OF STUDENTS WITH DISABILITIES

Students with disabilities who require academic accommodation must contactStudent Accessibility Services (SAS) at 905-525-9140 ext. 28652 or[email protected]to make arrangements with a Program Coordinator. For further          information, consult McMaster University’sAcademic Accommodation of Students with Disabilities  policy.

ACADEMIC ACCOMMODATION FOR RELIGIOUS, INDIGENOUS OR SPIRITUAL OBSERVANCES (RISO)

Students requiring academic accommodation based on religious, indigenous or spiritual observances should follow the procedures set out in theRISOpolicy. Students should submit their request to their Faculty Office normally       within 10 working days of the beginning of term in which they anticipate a need for accommodation or to the         Registrar's Office prior to their examinations. Students should also contact their instructors as soon as possible to   make alternative arrangements for classes, assignments, and tests.

COURSES WITH AN ON- LINE ELEMENT

Some courses may use on- line elements (e.g. e-mail, Avenue to Learn (A2L), LearnLink, web pages, capa, Moodle,     ThinkingCap, etc.). Students should be aware that, when they access the electronic components of a course using     these elements, private information such as first and last names, user names for the McMaster e- mail accounts, and program affiliation may become apparent to all other students in the same course. The available information is          dependent on the technology used. Continuation in a course that uses on- line elements will be deemed consent to  this disclosure.   If you have any questions or concerns about such disclosure, please discuss this with the course       instructor.

ONLINE PROCTORING

This course may use proctoring software (TBD) for tests/exams . This software may require students to turn on their  video camera, present identification, monitor and record their computer activities, and/or lock/restrict their browser or other applications/software during tests or exams. This software may be required to be installed before the

test/exam begins.  If you have questions about whether this software will be used, or concerns about the use of this software, please contact your instructor.

ACADEMIC INTEGRITY

You are expected to exhibit honesty and use ethical behaviour in all aspects of the learning process. Academic credentials you earn are rooted in principles of honesty and academic integrity.

It is your responsibility to understand what constitutes academic dishonesty.

Academic dishonesty is to knowingly act or fail to act in a way that results or could result in unearned academic         credit or advantage. This behaviour can result in serious consequences, e.g. the grade of zero on an assignment, loss

of credit with a notation on the transcript (notation reads: “Grade of F assigned for academic dishonesty”), and/or suspension or expulsion from the university. For information on the various types of academic dishonesty please   refer to theAcademic Integrity Policy, located athttps://secretariat.mcmaster.ca/university-policies-procedures-   guidelines/

The following illustrates only three forms of academic dishonesty:

•    plagiarism, e.g. the submission of work that is not one’s own or for which other credit has been obtained.

•    improper collaboration in group work.

•    copying or using unauthorized aids in tests and examinations.

AUTHENTICITY / PLAGIARISM DETECTION

Some courses may use a web- based service (Turnitin.com) to reveal authenticity and ownership of student                  submitted work. For courses using such software, students will be expected to submit their work electronically either directly to Turnitin.com or via an online learning platform (e.g. A2L, etc.) using plagiarism detection (a service              supported by Turnitin.com) so it can be checked for academic dishonesty.

Students who do not wish their work to be submitted through the plagiarism detection software must i nform the  Instructor before the assignment is due. No penalty will be assigned to a student who does not submit work to the plagiarism detection software. All submitted work is subject to normal verification that standards of academic        integrity have been upheld (e.g., on- line search, other software, etc.). For more details about McMaster’s use of    Turnitin.com  please go towww.mcmaster.ca/academicintegrity.

CONDUCT EXPECTATIONS

As a McMaster student, you have the right to experience, and the responsibility to demonstrate, respectful and   dignified interactions within all our living, learning and working communities. These expectations are described in theCode of Student Rights & Responsibilities (the “Code”).All students share the responsibility of maintaining a    positive environment for the academic and personal growth of all McMaster community members, whether in     person or online .

It is essential that students be mindful of their interactions online, as the Code remains in effect in virtual learning environments. The Code applies to any interactions that adversely affect, disrupt, or interfere with reasonable       participation in University activities. Student disruptions or behaviours that interfere with university functions on  online platforms (e.g. use of Avenue 2 Learn, WebEx or Zoom for delivery), will be taken very seriously and will be investigated. Outcomes may include restriction or removal of the involved students’ access to these platforms.

Additional information about the Code and netiquette can be foundhere.