ACMS 40390: Fall 2016 - Numerical Analysis
Course Information
Instructor: Zhiliang Xu,
zxu2@nd.edu 152B Hurley Hall
Office phone number: (574)631-3423
Class time: M, W, F, 11:30am - 12:20pm.
Classroom: 112 Pasquerilla Center
Teaching assistants: Luyi Shen, lshen4@nd.edu
Office hours:
Xu: M, T 2:00pm - 3:00pm or by appointment and drop-in (when available), 152B Hurley Hall
Luyi Shen: T 11:15am - 2:15pm, B21 Hayes-Healy
Textbook: Richard L. Burden and J. Douglas Faires, Numerical Analysis, 10th Edition.
Prerequisites:
MATH 20750 or MATH 20860 or MATH 30650 or ACMS 20750 or PHYS 20452
The course requires a certain amount of programming. C, C++ or Matlab programming languages are preferred. However, you may also use software programs including Fortran, Mathematica.
Syllabus is here.
Tips about programming:
- To learn about basics of Unix system and Unix shell, UNIX
Tutorials Point, is a good basic introduction. Much of the specific information about the actual
setup at Notre Dame is out of date, but the sections on basic UNIX are still good.
Another good website is http://software-carpentry.org/
- The Unix machines for you to test are: darrow.cc.nd.edu, remote201.helios.nd.edu,
remote202.helios.nd.edu, ..., and remote208.helios.nd.edu.
Computer laboratories: Fitzpatrick 149 (Engineering Library) with 36 Linux machines. Cushing 303 with 32 Linux machines.
- Instruction and help on Unix systems
- To learn about basics of C programming, the website
ANSI C for Programmers on UNIX Systems
and the document ANSI C for Programmers on UNIX Systems (pdf file) are good starting places.
- To learn about basics of C++ programming, the book "Engineering problem solving with C++" by Delores Etter and Jeanine Ingber is a good reference.
- Unfortunately, Windows and Moc OS do not come with a build-in compiler.
We need to install a compiler by ourselves.
On Windows, we may use
Microsoft Visual Studio (use Visual C++ Express edition) for the C and C++ programming.
On Mac OS, we can use xCode environment.
A brief introduction for using xCode is available
here .
A free IDE (Integrated Development Environment) that we can also use is Eclipse , which actually
runs on all major operating systems (Windows, Linux, Mac OS).
A good source to look at to know how to set up the compiler and Eclipse step by step is
"Setting up Eclipse CDT on Windows, Linux/Unix, Mac OS X" . Or
a short tutorial by Brian Lee at University of Manitoba "Eclipse (C/C++) Plugin Tutorial" .
- To use Matlab, go to the University's oit software download page
https://oit.nd.edu/software/licenseinfo/index.shtml to get a copy to install on your computer. A help is here with an user guide Interactive Matlab Course
Important Dates
| First test review |
Monday, 09/19 |
in class |
| First in class test |
Wednesday, 09/21 |
in class |
| Second test review |
Monday, 10/24 |
in class |
| Second in class test |
Wednesday, 10/26 |
in class |
| Final exam |
TBA |
TBA |
Week 1:
Wednesday (08/24): Sections 1.1 HW(due on 08/31): Section 1.1: 2(c), 4(b), 6(c)
Section 1.1 Review of Calculus
Friday (08/26): Sections 1.1 HW(due on 08/31): Section 1.1: 19
Week 2:
Monday (08/29): Sections 1.1, 1.2 HW(due on 09/07): Section 1.1: 21, 25(b)
Section 1.2 Round-off Errors and Computer Arithmetic
Wednesday (08/31): Section 1.2 HW(due on 09/07): Section 1.2: 19(b)
Friday (09/02): Section 1.2 HW(due on 09/07): Section 1.2 exercise: 3(c), 6(d), 26 (modify the question as follows).
Answer the following question for 26: In the laboratory, it was found that T was 15oC under these conditions. Assume that the data are rounded values accurate to the places given, show that the laboratory figure T = 15oC is within the bounds of accuracy for ideal gas law.
Short review of converting binary-decimal numbers.
Week 3:
Monday (09/05): Section 1.2 HW(due on 09/14): Section 1.2: 15(d), 21.
Wednesday (09/07): Sections 1.2, 1.3 HW(due on 09/14): Section 1.2: 25.
Friday (09/09): Section 1.3 HW(due on 09/14): Section 1.3: 1(b). Solve the following revised problem. Use three-digit chopping arithmetic to compute the following sums: (1+1/8+1/27), (1/27 + 1/8 + 1). Which method is more accurate, and why?
6(a,b). Hint: use the fact that sin(x) <= x when x >= 0.
Week 4:
Monday (09/12): Sections 1.3, 2.1 HW(due on 09/21):
Section 1.3 Exercise:
7(a). Hint: Use the second Taylor polynomial of sin(h) about h = 0.
Section 2.1 Exercise:
1, 7a, 7b(For (b), only need to find p3 instead), 12(a,d).
Section 2.1 The Bisection Method
Matlab code for bisection method .
The C++ sample code for the bisection method is
ALG021_bisection.cpp .
Wednesday (09/14): Sections 2.2 HW(due on 09/21):
Section 2.1
Exercise 18. Modify this problem as follows: Use Thm 2.1 to find a bound for the number of iterations needed to achieve an approximation with absolute error within 10^-3 to the solution of x^3 + x-4 = 0 lying in the interval [1,4].
Section 2.2
Exercise 1(a), 10.
Modify exercise 10 as follows: Use Thm 2.3 to show that g(x) = 2^-x has a unique fixed point on [1/3, 1]. Use fixed-point iteration to find p_3 approximation to the fixed point. Choose p_0 = 1.
Section 2.2 Fixed Point Iteration
Main Matlab code for fixed-point iteration , Matlab code of Routine for fixed-point .
The sample C code for the fixed-point iteration method:
ALG022_fixed_pt_iter.cpp
Computer project 1 (due on 09/23):
Implement the bisection method (Algorithm 2.1) to solve exercise 16 in Section 2.1. Use |w_n - w_{n-1}|/|w_n| <= 10-5 as the stopping criterion.
Hints:
1. Use the sample code ALG021_bisection_2.cpp uploaded to Resources/C++ Program in Sakai as the base code.
2. Formulate the equation of the problem in the form of f(w) =0. Since w<0, make your initial interval between some negative value and 0.
3. Modify Func() in the code to compute f(w) defined above.
4. Stop the iteration when |w_n - w_{n-1}|/|w_n| <= 10-5 means that
"if ((absval(FP) < ZERO || (C < TOL)) " need to be modified as well.
Friday (09/16): Sections 2.2, 2.3 HW(due on 09/21):
Section 2.2 Exercise:
8. (Change the problem as follows) Develop a fixed-point iteration method which guarantees to find the solution of x3-x-1=0. Use P0 = 1 and the developed fixed-point method to compute the approximate solution till P2.
10. (Change the problem as follows) Use Corollary 2.5 to estimate the number of iterations required to achieve absolute error less than 10-4. Use P0 = 1.
Section 2.3 Exercise: 2.
Section 2.3 Newton's Method
Matlab demo code for Newton's method
The sample code for the Newton's method is
ALG023_Newton.cpp The code is set to solve cos(x)-x=0
Matlab demo code for Secant method solving exercise2.3.6.a
The sample code for the Secant method is
ALG024_Secant_ex_2_3_6_2.cpp The code is set to solve exercise2.3.6.a
Week 5:
Friday (09/23): Sections 2.4 HW(due on 09/28):
Section 2.3 Exercise:
8. Use the Secant method to solve exercise 6b. Compute p2 and p3.
Section 2.4 Exercise: 6a.
Computer project 2 (due on 09/28):
Implement the Newton's method (Algorithm 2.4) to solve lambda in Exercise 2.3.22.
Instructions:
1. Use the base code ALG023_Newton_3.cpp in Resources/C++ Program to start.
2. Rewrite the given equation of the problem as f(lambda) = 0 for solving for lambda.
3. Calculate derivative of f(lambda) .
3. Modify the F(double X) function of the code to evaluate the problem function f(lambda)
4. Modify the FP(double X) function of the code to evaluate derivative of f(lambda) .
5. Use |pn -pn-1|/|pn|< 10-4 as the criterion to stop iteration.
6. Let the initial guess be a small positive number.
6. Submit the code to your dropbox folder.
Week 6:
Monday (09/26): Sections 2.4, 3.1 HW(due on 10/05):
Section 2.4 Exercise:
4. Use the modified Newton's method to solve 2c. Let p0 = 3.5. Compute p1 and p2.
Section 3.1 Interpolation and the Lagrange Polynomial
Using Matlab to plot solution of exercise 2(a)
syms x
xi=[1.0, 1.25, 1.6]
fi = sin(3.14159*xi)
xx=1.0:0.02:1.6
plot(xx,sin(3.14159*xx), '--g', xi, fi, 'or')
hold on
ezplot('sin(3.14159*1.25)*(x-1)*(x-1.6)*80/(-7)+sin(1.6*3.14159)*100/21*(x-1)*(x-1.25)',[1,1.6])
The Matlab code for the Lagrange Interpolating Polynomial is
Lagrange Interpolating Polynomial and
Lagrange basis Polynomial .
To use this sample code to solve Example 3.1.1, do the following:
Download these two files and in Matlab add paths where we save these two files;
In the command window, excute the following statement to see the curve of the 2nd degree Lagrange polynomial for interpolating points taken from 1/x:
xi = [2.0, 2.5, 4.0];
fi = 1./xi;
lp = lagrange_2(xi, fi);
xx = 0.5:0.01:5;
plot(xx, polyval(lp, xx), xi, fi, 'or', xx, 1./xx, '--g');
To evaluate the value of the interpolating polynomial at a number x, use the command: polyval(lp, x).
Remark: the return values from calling " lagrange_2(xi, fi)" are coefficents of the interpolating
polynomial from the highest degree to zeroth degree in the form of P_n(x) = a_n*x^n + a_{n-1} *x^{n-1} + ... + a_0.
(a_n, ..., a_0) are return values.
Wednesday (09/28): Section 3.1 HW(due on 10/05):
Exercise 3.1:
6(d). Using Lagrange interpolating polynomial of degree three to approximate f(0.25).
Hint: All points are used for interpolation.
Friday (09/30): Sections 3.1, 3.3 HW(due on 10/05):
Exercise 3.1:
6(c). Using Lagrange interpolating polynomial of degree two to approximate f(0.18).
14(b).
17. Determine a bound for the step size for this table.
Section 3.3 Divided Differences
Week 7:
Monday (10/3): Section 3.3 HW(due on 10/12):
Exercise 3.3:
2(a). Using the divided difference approach to construct interpolating polynomial of degree three to approximate f(0.43).
14.
Wednesday (10/5): Sections 3.3, 3.4 HW(due on 10/12):
Exercise 3.3:
16.
Friday (10/7): Section 3.4 HW(due on 10/12):
Exercise 3.4:
1(c). Use Theorem 3.9 to construct Hermite interpolating polynomial.
2(c). Use Newton's divided differences to construct Hermite interpolating polynomial.