M471 Introduction to Numerical Methods

Winter 2020

Instructor:

Shixu Meng

Office:

East Hall 3060

When:

Section 001: MoWeFr 8:00AM - 9:00AM

Section 002: MoWeFr 9:00AM - 10:00AM

Where:

1084 EH

Office Hours:

MF: 10:00 AM-11:30 AM

Course updates: We have switched to remote teaching starting from Mar 16. Check yourCanvasfor additional details and updates.

Course Description: This is a survey of the basic numerical methods which are used to solve scientific problems. The emphasis is evenly divided between the analysis of the methods and their practical applications. Some convergence theorems and error bounds are proved. The course also provides an introduction to MATLAB, an interactive program for numerical linear algebra, as well as practice in computer programming.

Prerequisites: Math 216, 286, or 316; Math 214, 217, 417, or 419; and a working knowledge of one high-level computer language.

Syllabus: M471-syllabus

Grader (GSI): Yuxuan Bao

Tips about Matlab programming: To use Matlab, go to the University’s software download page to get a copy to install on your computer. Here is a Matlab user guide: Interactive Matlab Course, Introduction to Matlab can also be useful. This is a Cheatsheet.

Week 1

01/08(W)

1.1 Review of Calculus

HW 1 (due on 01/15): Section 1.1: 2(c), 4(b), 6(c)

Lec-1.1

01/10(F)

1.1 Review of Calculus

HW1 (due on 01/15): Section 1.1: 19, 25(b)

Decimal_binary_convert

Week 2

01/13(M)

1.2 Round-off Errors and Computer Arithmetic

HW2 (due on 01/22): Section 1.2: 19(a,b), 20[for numbers given in 19(a,b)]

Lec-1.2

01/15(W)

1.2 Round-off Errors and Computer Arithmetic

HW2 (due on 01/22): Section 1.2: 3(b), 4(a), 6(c), 14(a, b, d[find relative error obtained from 14(b)])

01/17(F)

1.3 Algorithms and Convergence

HW2 (due on 01/22): Section 1.2: 16(b), 21, 25(a), 26

Lec-1.3

Pseudo_Code_Summary

Matlab code on Canvas

Week 3

01/20(M)

No class meeting

01/22(W)

1.3 Algorithms and Convergence

HW3(due on 01/29): Section 1.3: 6(b), 7(b), 11

ComputerProject1

01/24(F)

2.1 The Bisection Method

HW3(due on 01/29): Section 2.1: 1, 11(a,b), 14[find approximation correct to within 0.01]

Lec-2.1

Matlab code on Canvas

Week 4

01/27(M)

2.2 Fixed-Point Iteration

HW4(due on 02/05): Section 2.2: 1(d), 4(a)[only compute p1, p2, p3, p4], 10[Replace 10^-4 by 10^-3 in the problem statement. Hence, for the fixed pt algorithm, stopping criterion is |p_n-p_n-1|<10^-3.]

Lec-2.2

Matlab code on Canvas

01/29(W)

2.3 Newton’s Methods and its Extensions

HW4(due on 02/05): Section 2.3: 1, 6(a)

Lec-2.3

Matlab code on Canvas

01/31(F)

2.3 Newton’s Methods and its Extensions

HW4 (due on 02/05): Section 2.3: 4(a), 30

Week 5

02/03(M)

Midterm I review

M471-1st-midterm-practice

practice_soln

formular_theorems_midI

02/05(W)

Midterm I

02/07(F)

2.4 Error Analysis for Iterative Methods

HW5 (due on 02/19): Section 2.4: 10[hint: write f(x)=(x-p)^m q(x)], 14

Lec-2.4

Matlab code on Canvas

Week 6

02/10(M)

2.5 Accelerating Convergence

HW5 (due on 02/19): Section 2.5: 4,6

Lec-2.5

Matlab code on Canvas

02/12(W)

3.1 Interpolation and Lagrange Polynomial

HW5 (due on 02/19): Section 3.1: 2(d),9, 23

Lec-3.1

02/14(F)

3.1 Interpolation and Lagrange Polynomial

F: no homework

Second Computer Project (due on Wed 03/18)

ComputerProject2

Matlab code on Canvas

Week 7

02/17(M)

3.3 Divided Differences

HW6 (due on 02/26): Section 3.3: 7(a), 14, 16

Lec-3.3

02/19(W)

3.4 Hermite Interpolation

HW6 (due on 02/26): Section 3.4: 2(a & b)[Use Theorem 3.9], 4(a & b)

Lec-3.4

02/21(F)

3.4 Hermite Interpolation

HW6 (due on 02/26): Section 3.4: 2(a & b) [Use divided difference], 7[do H3 only], 10

Week 8

02/24(M)

3.5: Cubic Spline Interpolation(Thomas Algorithm for Tridiagonal Linear System)

HW7 (due on 03/11): Section 3.5: 11,13

Lec-3.5

02/26(W)

HW7 (due on 03/11): Section 3.5: 4(c),6(c)

Matlab code on Canvas

02/28(F)

HW7 (due on 03/11): Section 3.5: 21(a),(c)[Use Theorem 3.13 to estimate max|f(x)-s(x)| only]

Thomas

Week 9

03/02 –03/06: Spring Break

Week 10

03/09(M)

4.1 Numerical Differentiation

HW8 (due on 03/20): Section 4.1: 2(b),4(b), 6(c), 8(c), 10(a)

Lec-4.1

03/11(W)

4.3 Elements of Numerical Integration

HW8 (due on 03/20): Section 4.3: 1(a,c), 3[Find error bound and actual error for 1(a,c); hint: for 1(c), antiderivative is x^3 (ln(x)/3-1/9)], 5[repeat 1(a,c) using Simpson’s rule]

Lec-4.3

03/13(F)

Class canceled

Week 11

03/16(M)

4.3 Elements of Numerical Integration

HW8 (due on 03/20): Section 4.3: 19, 22, 23

03/18(W)

Midterm II open book

03/20(F)

4.4 Composite Numerical Integration

HW9 (due on 04/01): Section 4.4: 1(a,c), 3[for 1(a,c)], 13(a,b).

Lec-4.4

Week 12

03/23(M)

4.7 Gaussian Quadrature

HW9 (due on 04/01): Section 4.7: 1(a,c)

Lec-4.7

03/25(W)

5.1 The Elementary Theory of Initial Value Problems

HW9 (due on 04/01): Section 5.1: 1(a), 2(a), 3(a)

Lec-5.1

03/27(F)

5.2 Euler’s Method

HW9 (due on 04/01): Section 5.2: 1(a), 3(a)

Lec-5.2

ComputerProject3

Week 13

03/30(M)

5.3 High-order Taylor Methods

HW10 (due on 04/08): Section 5.3: 1(a), 10(a), Discussion problem 1

Lec-5.3

04/01(W)

5.4 Runge-Kutta Methods

HW10 (due on 04/08): Section 5.4: 2(d), 7[repeat for 2(d)], 15[repeat for 2(d)]

Lec-5.4

04/03(F)

5.6 Multistep Methods

HW10(due on 04/08): Section 5.6: 1(a)[use AB2 and AB3 methods only].

Lec-5.6

Week 14

04/06(M)

5.10: Zero-Stability

HW11(due on 04/15): Section 5.10: 5(a) [Hint: for analyzing consistency by local truncation error, do 3rd order Taylor expansion for y_{i-2}, y_{i-1} and y_{i+1} about y_i respectively. In the difference equation, replace the approximate solution by exact values and plug these Taylor expansions into the equation. See what you have after some cancellation.]

Lec-5.10

04/08(W)

5.11: Stiff Differential Equations

ComputerProject 4

Lec-5.11-part1

04/10(F)

5.11: Stiff Differential Equations

HW11(due on 04/15): Section 5.11: 10.

Lec-5.11-part2

Week 15

04/13(M)

6.1: Linear System of Equations

6.2: Pivoting Strategies

No Hw

Lec-6.1-2

04/15(W)

7.3: Jacobi iterative method

No Hw

Lec-7.3-part 1

04/17(F)

7.3: Gauss-Siedel iterative method

No Hw

Lec-7.3-part 2