View
12
Download
0
Category
Preview:
Citation preview
Numerical Methods
Lecture Notes #01
Pavel Ludvík,<pavel.ludvik@vsb.cz>
Department of Mathematics and Descriptive GeometryV�B-TUO
http://homen.vsb.cz/~lud0016/
February 10, 2016
Lecture Notes #01
The Professor
Contact Information, O�ce Hours
Pavel Ludvík
O�ce A832O�ce phone number 59 732 4179E-mail pavel.ludvik@vsb.czWeb http://homen.vsb.cz/~lud0016/
O�ce Hours by appointment
Lecture Notes #01
Course Information
Expectations and Procedures
Necessary and Su�cient Conditions
Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.
Oral exam 0-20 CP, successful completion at least 5 CP.
Grading (in Czech); International grading system is a little di�erent
86 - 100 excellent66 - 85 satisfactory51 - 65 mediocre0 - 50 failed
Lecture Notes #01
Course Information
Expectations and Procedures
Necessary and Su�cient Conditions
Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.
Oral exam 0-20 CP, successful completion at least 5 CP.
Grading (in Czech); International grading system is a little di�erent
86 - 100 excellent66 - 85 satisfactory51 - 65 mediocre0 - 50 failed
Lecture Notes #01
Course Information
Expectations and Procedures
Necessary and Su�cient Conditions
Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.
Oral exam 0-20 CP, successful completion at least 5 CP.
Grading (in Czech); International grading system is a little di�erent
86 - 100 excellent66 - 85 satisfactory51 - 65 mediocre0 - 50 failed
Lecture Notes #01
Course Information
Expectations and Procedures
Necessary and Su�cient Conditions
Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.
Oral exam 0-20 CP, successful completion at least 5 CP.
Grading (in Czech); International grading system is a little di�erent
86 - 100 excellent66 - 85 satisfactory51 - 65 mediocre0 - 50 failed
Lecture Notes #01
Course Information
Expectations and Procedures
Necessary and Su�cient Conditions
Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.
Oral exam 0-20 CP, successful completion at least 5 CP.
Grading (in Czech); International grading system is a little di�erent
86 - 100 excellent66 - 85 satisfactory51 - 65 mediocre0 - 50 failed
Lecture Notes #01
Course Information
Expectations and Procedures
Necessary and Su�cient Conditions
Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.
Oral exam 0-20 CP, successful completion at least 5 CP.
Grading (in Czech); International grading system is a little di�erent
86 - 100 excellent66 - 85 satisfactory51 - 65 mediocre0 - 50 failed
Lecture Notes #01
Course Information
Expectations and Procedures
Necessary and Su�cient Conditions
Exercises
Conditions for obtaining credit points (CP):
Participation in exercises, 20% can be to apologize.
Completion of a home project (0-15 CP) and delivering all homeworks(0-5 CP).
Exam
Written exam 0-60 CP, successful completion at least 25 CP.
Oral exam 0-20 CP, successful completion at least 5 CP.
Grading (in Czech); International grading system is a little di�erent
86 - 100 excellent66 - 85 satisfactory51 - 65 mediocre0 - 50 failed
Lecture Notes #01
Course Information
Expectations and Procedures
Expectations
Please be on time.
Please pay attention.
Students are expected and encouraged to ask questions in class!
Students are expected and encouraged to make use of consultationswith the instructor!
Lecture Notes #01
Course Information
Expectations and Procedures
Expectations
Please be on time.
Please pay attention.
Students are expected and encouraged to ask questions in class!
Students are expected and encouraged to make use of consultationswith the instructor!
Lecture Notes #01
Course Information
Expectations and Procedures
Expectations
Please be on time.
Please pay attention.
Students are expected and encouraged to ask questions in class!
Students are expected and encouraged to make use of consultationswith the instructor!
Lecture Notes #01
Course Information
Expectations and Procedures
Expectations
Please be on time.
Please pay attention.
Students are expected and encouraged to ask questions in class!
Students are expected and encouraged to make use of consultationswith the instructor!
Lecture Notes #01
Course Information
Book and Other Study Materials
The recommended text for the course is the book:
Title: Numerical AnalysisAuthors: Richard L. Burden, John D. FairesEdition: 9Publisher: Cengage Learning, 2011
Lecture Notes #01
Course Information
Book and Other Study Materials
Other materials:
Title: Numerical Methods for EngineersAuthors: Steven Chapra, Raymond CanaleEdition: 6Publisher: McGraw-Hill Education, 2009
Solved examples:http://mdg.vsb.cz/wiki/public/ZM_NM_examples.pdf
My web: http://homen.vsb.cz/~lud0016/
Qaurteroni, A., Sacco, R., Saleri, F.: Numerical Mathematics. Springer,2007.
Süli, E., Mayers, D.: An introduction to Numerical Analysis. CambridgeUniversity Press, 2003.
Lecture Notes #01
Course Information
Book and Other Study Materials
Other materials:
Title: Numerical Methods for EngineersAuthors: Steven Chapra, Raymond CanaleEdition: 6Publisher: McGraw-Hill Education, 2009
Solved examples:http://mdg.vsb.cz/wiki/public/ZM_NM_examples.pdf
My web: http://homen.vsb.cz/~lud0016/
Qaurteroni, A., Sacco, R., Saleri, F.: Numerical Mathematics. Springer,2007.
Süli, E., Mayers, D.: An introduction to Numerical Analysis. CambridgeUniversity Press, 2003.
Lecture Notes #01
Course Information
Book and Other Study Materials
Other materials:
Title: Numerical Methods for EngineersAuthors: Steven Chapra, Raymond CanaleEdition: 6Publisher: McGraw-Hill Education, 2009
Solved examples:http://mdg.vsb.cz/wiki/public/ZM_NM_examples.pdf
My web: http://homen.vsb.cz/~lud0016/
Qaurteroni, A., Sacco, R., Saleri, F.: Numerical Mathematics. Springer,2007.
Süli, E., Mayers, D.: An introduction to Numerical Analysis. CambridgeUniversity Press, 2003.
Lecture Notes #01
Course Information
Book and Other Study Materials
Other materials:
Title: Numerical Methods for EngineersAuthors: Steven Chapra, Raymond CanaleEdition: 6Publisher: McGraw-Hill Education, 2009
Solved examples:http://mdg.vsb.cz/wiki/public/ZM_NM_examples.pdf
My web: http://homen.vsb.cz/~lud0016/
Qaurteroni, A., Sacco, R., Saleri, F.: Numerical Mathematics. Springer,2007.
Süli, E., Mayers, D.: An introduction to Numerical Analysis. CambridgeUniversity Press, 2003.
Lecture Notes #01
Course Information
Book and Other Study Materials
Other materials:
Title: Numerical Methods for EngineersAuthors: Steven Chapra, Raymond CanaleEdition: 6Publisher: McGraw-Hill Education, 2009
Solved examples:http://mdg.vsb.cz/wiki/public/ZM_NM_examples.pdf
My web: http://homen.vsb.cz/~lud0016/
Qaurteroni, A., Sacco, R., Saleri, F.: Numerical Mathematics. Springer,2007.
Süli, E., Mayers, D.: An introduction to Numerical Analysis. CambridgeUniversity Press, 2003.
Lecture Notes #01
Course Information
Book and Other Study Materials
Software tools
Mathworks Mathlab � available on computers in the classrooms (foraccess to the classrooms ask at F312)
Octave � free alternative to MatLab:http://mdg.vsb.cz/wiki/public/soubory/qtoctave0.7.2_
octave3.0.0_Portable_win32.zip
Practical introduction to MatLab � .
Learning videos for Mathlab:
Getting Started with MatLab � http://www.mathworks.com/videos/
getting-started-with-matlab-68985.html.Using Basic Plotting Functions � http://www.mathworks.com/
videos/using-basic-plotting-functions-69018.html.Writing a MatLab Program � http://www.mathworks.com/videos/
writing-a-matlab-program-69023.html.
Lecture Notes #01
Course Information
Book and Other Study Materials
Software tools
Mathworks Mathlab � available on computers in the classrooms (foraccess to the classrooms ask at F312)
Octave � free alternative to MatLab:http://mdg.vsb.cz/wiki/public/soubory/qtoctave0.7.2_
octave3.0.0_Portable_win32.zip
Practical introduction to MatLab � .
Learning videos for Mathlab:
Getting Started with MatLab � http://www.mathworks.com/videos/
getting-started-with-matlab-68985.html.Using Basic Plotting Functions � http://www.mathworks.com/
videos/using-basic-plotting-functions-69018.html.Writing a MatLab Program � http://www.mathworks.com/videos/
writing-a-matlab-program-69023.html.
Lecture Notes #01
Course Information
Book and Other Study Materials
Software tools
Mathworks Mathlab � available on computers in the classrooms (foraccess to the classrooms ask at F312)
Octave � free alternative to MatLab:http://mdg.vsb.cz/wiki/public/soubory/qtoctave0.7.2_
octave3.0.0_Portable_win32.zip
Practical introduction to MatLab � .
Learning videos for Mathlab:
Getting Started with MatLab � http://www.mathworks.com/videos/
getting-started-with-matlab-68985.html.Using Basic Plotting Functions � http://www.mathworks.com/
videos/using-basic-plotting-functions-69018.html.Writing a MatLab Program � http://www.mathworks.com/videos/
writing-a-matlab-program-69023.html.
Lecture Notes #01
Course Information
Book and Other Study Materials
Software tools
Mathworks Mathlab � available on computers in the classrooms (foraccess to the classrooms ask at F312)
Octave � free alternative to MatLab:http://mdg.vsb.cz/wiki/public/soubory/qtoctave0.7.2_
octave3.0.0_Portable_win32.zip
Practical introduction to MatLab � .
Learning videos for Mathlab:
Getting Started with MatLab � http://www.mathworks.com/videos/
getting-started-with-matlab-68985.html.Using Basic Plotting Functions � http://www.mathworks.com/
videos/using-basic-plotting-functions-69018.html.Writing a MatLab Program � http://www.mathworks.com/videos/
writing-a-matlab-program-69023.html.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures I
Ideal scenerio � one topic per week:
1 Course Contents, Mathematical Preliminaries and Error Analysis.
2 Solution of Nonlinear Equations, Roots Separation, Bisection Method,Regula Falsi (i.e., False-Position Method).
3 Newton's Method and Fix-Point Iterations.
4 Direct Methods for Solving Linear Equations, Gaussian Elimination andLU-Decomposition.
5 Eigenvalues and Eigenvectors, Numerical Calculation.
6 Iterative Methods for Solving Linear Equations.
7 Interpolation by Polynomials and Splines.
8 Least Squares Approximation.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures I
Ideal scenerio � one topic per week:
1 Course Contents, Mathematical Preliminaries and Error Analysis.
2 Solution of Nonlinear Equations, Roots Separation, Bisection Method,Regula Falsi (i.e., False-Position Method).
3 Newton's Method and Fix-Point Iterations.
4 Direct Methods for Solving Linear Equations, Gaussian Elimination andLU-Decomposition.
5 Eigenvalues and Eigenvectors, Numerical Calculation.
6 Iterative Methods for Solving Linear Equations.
7 Interpolation by Polynomials and Splines.
8 Least Squares Approximation.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures I
Ideal scenerio � one topic per week:
1 Course Contents, Mathematical Preliminaries and Error Analysis.
2 Solution of Nonlinear Equations, Roots Separation, Bisection Method,Regula Falsi (i.e., False-Position Method).
3 Newton's Method and Fix-Point Iterations.
4 Direct Methods for Solving Linear Equations, Gaussian Elimination andLU-Decomposition.
5 Eigenvalues and Eigenvectors, Numerical Calculation.
6 Iterative Methods for Solving Linear Equations.
7 Interpolation by Polynomials and Splines.
8 Least Squares Approximation.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures I
Ideal scenerio � one topic per week:
1 Course Contents, Mathematical Preliminaries and Error Analysis.
2 Solution of Nonlinear Equations, Roots Separation, Bisection Method,Regula Falsi (i.e., False-Position Method).
3 Newton's Method and Fix-Point Iterations.
4 Direct Methods for Solving Linear Equations, Gaussian Elimination andLU-Decomposition.
5 Eigenvalues and Eigenvectors, Numerical Calculation.
6 Iterative Methods for Solving Linear Equations.
7 Interpolation by Polynomials and Splines.
8 Least Squares Approximation.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures I
Ideal scenerio � one topic per week:
1 Course Contents, Mathematical Preliminaries and Error Analysis.
2 Solution of Nonlinear Equations, Roots Separation, Bisection Method,Regula Falsi (i.e., False-Position Method).
3 Newton's Method and Fix-Point Iterations.
4 Direct Methods for Solving Linear Equations, Gaussian Elimination andLU-Decomposition.
5 Eigenvalues and Eigenvectors, Numerical Calculation.
6 Iterative Methods for Solving Linear Equations.
7 Interpolation by Polynomials and Splines.
8 Least Squares Approximation.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures I
Ideal scenerio � one topic per week:
1 Course Contents, Mathematical Preliminaries and Error Analysis.
2 Solution of Nonlinear Equations, Roots Separation, Bisection Method,Regula Falsi (i.e., False-Position Method).
3 Newton's Method and Fix-Point Iterations.
4 Direct Methods for Solving Linear Equations, Gaussian Elimination andLU-Decomposition.
5 Eigenvalues and Eigenvectors, Numerical Calculation.
6 Iterative Methods for Solving Linear Equations.
7 Interpolation by Polynomials and Splines.
8 Least Squares Approximation.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures I
Ideal scenerio � one topic per week:
1 Course Contents, Mathematical Preliminaries and Error Analysis.
2 Solution of Nonlinear Equations, Roots Separation, Bisection Method,Regula Falsi (i.e., False-Position Method).
3 Newton's Method and Fix-Point Iterations.
4 Direct Methods for Solving Linear Equations, Gaussian Elimination andLU-Decomposition.
5 Eigenvalues and Eigenvectors, Numerical Calculation.
6 Iterative Methods for Solving Linear Equations.
7 Interpolation by Polynomials and Splines.
8 Least Squares Approximation.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures I
Ideal scenerio � one topic per week:
1 Course Contents, Mathematical Preliminaries and Error Analysis.
2 Solution of Nonlinear Equations, Roots Separation, Bisection Method,Regula Falsi (i.e., False-Position Method).
3 Newton's Method and Fix-Point Iterations.
4 Direct Methods for Solving Linear Equations, Gaussian Elimination andLU-Decomposition.
5 Eigenvalues and Eigenvectors, Numerical Calculation.
6 Iterative Methods for Solving Linear Equations.
7 Interpolation by Polynomials and Splines.
8 Least Squares Approximation.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures II
9 Numerical Di�erentiation and Integration.
10 Extrapolation in Integral Calculation. Gaussian Quadrature.
11 Initial Value Problems for Ordinary Di�erential Equations - Euler'smethod and Runge-Kutta Methods.
12 Multistep Methods.
13 (In Case of Optimistic Scenario: Ordinary Di�erential Equations of
Higher Order.)
14 Stand by.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures II
9 Numerical Di�erentiation and Integration.
10 Extrapolation in Integral Calculation. Gaussian Quadrature.
11 Initial Value Problems for Ordinary Di�erential Equations - Euler'smethod and Runge-Kutta Methods.
12 Multistep Methods.
13 (In Case of Optimistic Scenario: Ordinary Di�erential Equations of
Higher Order.)
14 Stand by.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures II
9 Numerical Di�erentiation and Integration.
10 Extrapolation in Integral Calculation. Gaussian Quadrature.
11 Initial Value Problems for Ordinary Di�erential Equations - Euler'smethod and Runge-Kutta Methods.
12 Multistep Methods.
13 (In Case of Optimistic Scenario: Ordinary Di�erential Equations of
Higher Order.)
14 Stand by.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures II
9 Numerical Di�erentiation and Integration.
10 Extrapolation in Integral Calculation. Gaussian Quadrature.
11 Initial Value Problems for Ordinary Di�erential Equations - Euler'smethod and Runge-Kutta Methods.
12 Multistep Methods.
13 (In Case of Optimistic Scenario: Ordinary Di�erential Equations of
Higher Order.)
14 Stand by.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures II
9 Numerical Di�erentiation and Integration.
10 Extrapolation in Integral Calculation. Gaussian Quadrature.
11 Initial Value Problems for Ordinary Di�erential Equations - Euler'smethod and Runge-Kutta Methods.
12 Multistep Methods.
13 (In Case of Optimistic Scenario: Ordinary Di�erential Equations of
Higher Order.)
14 Stand by.
Lecture Notes #01
Course Information
Syllabus
Program of Lectures II
9 Numerical Di�erentiation and Integration.
10 Extrapolation in Integral Calculation. Gaussian Quadrature.
11 Initial Value Problems for Ordinary Di�erential Equations - Euler'smethod and Runge-Kutta Methods.
12 Multistep Methods.
13 (In Case of Optimistic Scenario: Ordinary Di�erential Equations of
Higher Order.)
14 Stand by.
Lecture Notes #01
Course Information
Syllabus
What are numerical methods and what is it for?
Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmeticoperations on numbers.
Q: What are numerical methods for?
A: To accurately approximate solutions of problems that cannot be solvedexactly. They reduce the di�cult analytic problems to purelyarithmetical ones.
Q: What kind of applications can bene�t from numerical studies?
A: Image processing / computer vision, computer graphics (rendering,animation), climate modeling, weather predictions, �virtual�crash-testing of cars, medical imaging (CT = Computer Tomography),AIDS research (virus decay vs. medication), �nancial mathematics
Lecture Notes #01
Course Information
Syllabus
What are numerical methods and what is it for?
Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmeticoperations on numbers.
Q: What are numerical methods for?
A: To accurately approximate solutions of problems that cannot be solvedexactly. They reduce the di�cult analytic problems to purelyarithmetical ones.
Q: What kind of applications can bene�t from numerical studies?
A: Image processing / computer vision, computer graphics (rendering,animation), climate modeling, weather predictions, �virtual�crash-testing of cars, medical imaging (CT = Computer Tomography),AIDS research (virus decay vs. medication), �nancial mathematics
Lecture Notes #01
Course Information
Syllabus
What are numerical methods and what is it for?
Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmeticoperations on numbers.
Q: What are numerical methods for?
A: To accurately approximate solutions of problems that cannot be solvedexactly. They reduce the di�cult analytic problems to purelyarithmetical ones.
Q: What kind of applications can bene�t from numerical studies?
A: Image processing / computer vision, computer graphics (rendering,animation), climate modeling, weather predictions, �virtual�crash-testing of cars, medical imaging (CT = Computer Tomography),AIDS research (virus decay vs. medication), �nancial mathematics
Lecture Notes #01
Course Information
Syllabus
What are numerical methods and what is it for?
Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmeticoperations on numbers.
Q: What are numerical methods for?
A: To accurately approximate solutions of problems that cannot be solvedexactly. They reduce the di�cult analytic problems to purelyarithmetical ones.
Q: What kind of applications can bene�t from numerical studies?
A: Image processing / computer vision, computer graphics (rendering,animation), climate modeling, weather predictions, �virtual�crash-testing of cars, medical imaging (CT = Computer Tomography),AIDS research (virus decay vs. medication), �nancial mathematics
Lecture Notes #01
Course Information
Syllabus
What are numerical methods and what is it for?
Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmeticoperations on numbers.
Q: What are numerical methods for?
A: To accurately approximate solutions of problems that cannot be solvedexactly. They reduce the di�cult analytic problems to purelyarithmetical ones.
Q: What kind of applications can bene�t from numerical studies?
A: Image processing / computer vision, computer graphics (rendering,animation), climate modeling, weather predictions, �virtual�crash-testing of cars, medical imaging (CT = Computer Tomography),AIDS research (virus decay vs. medication), �nancial mathematics
Lecture Notes #01
Course Information
Syllabus
What are numerical methods and what is it for?
Q: What are numerical methods?
A: Numerical methods are algorithms based on simple arithmeticoperations on numbers.
Q: What are numerical methods for?
A: To accurately approximate solutions of problems that cannot be solvedexactly. They reduce the di�cult analytic problems to purelyarithmetical ones.
Q: What kind of applications can bene�t from numerical studies?
A: Image processing / computer vision, computer graphics (rendering,animation), climate modeling, weather predictions, �virtual�crash-testing of cars, medical imaging (CT = Computer Tomography),AIDS research (virus decay vs. medication), �nancial mathematics
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Q: Why to review calculus? In numerical mathematics??
A: When developing numerical schemes we will use theorems from calculusto guarantee that our algorithms make sense.
Key concepts from calculus:
Limits
Continuity
Convergence
Di�erentiability
Extreme Value Theorem
Intermediate Value Theorem
Mean Value Theorem
Taylor's Theorem
Lecture Notes #01
Calculus Review
Limit/Convergence
De�nition (Limit)
A function f de�ned on a set X ⊂ R has the limit L at x0, written
limx→x0
f (x) = L
if for any sequence (xn) approaching x0 a sequence (f (xn)) approaches L.
De�nition (Continuity (at a point))
Let f be a function de�ned on a set X ⊂ R, and x0 ∈ X . Then f iscontinuous at x0 if
limx→x0
f (x) = f (x0).
Lecture Notes #01
Calculus Review
Limit/Convergence
De�nition (Limit)
A function f de�ned on a set X ⊂ R has the limit L at x0, written
limx→x0
f (x) = L
if for any sequence (xn) approaching x0 a sequence (f (xn)) approaches L.
De�nition (Continuity (at a point))
Let f be a function de�ned on a set X ⊂ R, and x0 ∈ X . Then f iscontinuous at x0 if
limx→x0
f (x) = f (x0).
Lecture Notes #01
Calculus Review
Continuity/Convergence
De�nition (Continuity (in an interval))
A function f is continuous on a set X ⊂ R (i.e., f ∈ C (X )) if it iscontinuous at each point x ∈ X .
Lecture Notes #01
Calculus Review
Continuity/Convergence
De�nition (Continuity (in an interval))
A function f is continuous on a set X ⊂ R (i.e., f ∈ C (X )) if it iscontinuous at each point x ∈ X .
Lecture Notes #01
Calculus Review
Di�erentiability
Theorem
If f is a function de�ned on a set X ⊂ R and x0 ∈ X , then the following
statements are equivalent:
(a) f is continuous at x0
(b) If {xn}∞n=1is any sequence in X converging to x0, then limn→∞ f (xn) = f (x0).
De�nition
Let f be a function de�ned on an open interval containing x0 (i.e.,x0 ∈ (a, b)). Then f is di�erentiable at x0 if
f ′(x0) = limx→x0
f (x)− f (x0)
x − x0exists.
If the limit exists, we call f ′(x0) a derivative of f at x0.
Lecture Notes #01
Calculus Review
Di�erentiability
Theorem
If f is a function de�ned on a set X ⊂ R and x0 ∈ X , then the following
statements are equivalent:
(a) f is continuous at x0
(b) If {xn}∞n=1is any sequence in X converging to x0, then limn→∞ f (xn) = f (x0).
De�nition
Let f be a function de�ned on an open interval containing x0 (i.e.,x0 ∈ (a, b)). Then f is di�erentiable at x0 if
f ′(x0) = limx→x0
f (x)− f (x0)
x − x0exists.
If the limit exists, we call f ′(x0) a derivative of f at x0.
Lecture Notes #01
Calculus Review
Continuity
Theorem (Di�erentiability ⇒ Continuity)
If f is di�erentiable at x0, then f is continuous at x0.
Lecture Notes #01
Calculus Review
Continuity
Theorem (Di�erentiability ⇒ Continuity)
If f is di�erentiable at x0, then f is continuous at x0.
Lecture Notes #01
Calculus Review
Extreme Value Theorem
Theorem (Extreme Value Theorem)
If f ∈ C [a, b] then
∃m,M ∈ [a, b]∀x ∈ [a, b] : f (m) ≤ f (x) ≤ f (M).
I.e., f attains its minimum at m and maximum at M.
Moreover, if f is di�erentiable on (a, b) then the numbers m,M occur either
at endpoints a, b or where f ′(x) = 0.
Lecture Notes #01
Calculus Review
Mean and Intermediate Value Theorem
Theorem (Mean Value Theorem)
If f ∈ C [a, b] and f is di�erentiable on (a, b), then ∃c ∈ (a, b) such that
f ′(c) =f (b)− f (a)
b − a.
Theorem (Intermediate Value Theorem)
If f ∈ C [a, b] and K ∈ (f (a), f (b)), then there ex ts a number c ∈ (a, b) forwhich f (c) = K .
Lecture Notes #01
Calculus Review
Mean and Intermediate Value Theorem
Theorem (Mean Value Theorem)
If f ∈ C [a, b] and f is di�erentiable on (a, b), then ∃c ∈ (a, b) such that
f ′(c) =f (b)− f (a)
b − a.
Theorem (Intermediate Value Theorem)
If f ∈ C [a, b] and K ∈ (f (a), f (b)), then there ex ts a number c ∈ (a, b) forwhich f (c) = K .
Lecture Notes #01
Calculus Review
Taylor's Theorem
Theorem (Taylor's Theorem)
Suppose f ∈ C [a, b], f (n+1) exists on (a, b) and x0 ∈ [a, b]. Then∀x ∈ (a, b), ∃ξ ∈ (x0, x) with
f (x) = Pn(x) + Rn(x)
where
Pn is called the Taylor polynomial of degree n, and Rn(x) is theremainder term (truncation error).
This theorem is extremely important for numerical analysis:Taylor expansion is a fundamental step in the derivation of many of thealgorithms we see in this class.
Lecture Notes #01
Calculus Review
Taylor's Theorem
Theorem (Taylor's Theorem)
Suppose f ∈ C [a, b], f (n+1) exists on (a, b) and x0 ∈ [a, b]. Then∀x ∈ (a, b), ∃ξ ∈ (x0, x) with
f (x) = Pn(x) + Rn(x)
where
Pn is called the Taylor polynomial of degree n, and Rn(x) is theremainder term (truncation error).
This theorem is extremely important for numerical analysis:Taylor expansion is a fundamental step in the derivation of many of thealgorithms we see in this class.
Lecture Notes #01
Computer Arithmetic and Finite Precision
Finite Precision: A 64-bit real number, double
The Binary Floating Point Arithmetic Standard 754-1985 (IEEE - TheInstitute for Electrical and Electronics Engineers) standard speci�ed thefollowing layout for a 64-bit real number:
sc10 c9 . . . c1 c0m51m50 . . .m1m0
where
Symbol Bits Description
s 1 The sign bit: 0 = positive, 1 = negativec 11 The characteristic (exponent)m 52 The mantisa
r = (−1)s2c−1023(1+m), c =10∑k=0
ck2k , m =
51∑k=0
mk
252−k
Lecture Notes #01
Computer Arithmetic and Finite Precision
Finite Precision: Examples
r = (−1)s2c−1023(1+m), c =10∑k=0
ck2k , m =
51∑k=0
mk
252−k
Remarks:
210 = 1024 and (11111111111)2 = 2047.
We cannot represent an exact zero!
Example 1: 3.0
0 10000000000 1000000000000000000000000000000000000000000000000000
(−1)0 · 2210−1023 ·
(1+
1
2
)= 1 · 21 · 3
2= 3.0
Lecture Notes #01
Computer Arithmetic and Finite Precision
Finite Precision: Examples
r = (−1)s2c−1023(1+m), c =10∑k=0
ck2k , m =
51∑k=0
mk
252−k
Remarks:
210 = 1024 and (11111111111)2 = 2047.
We cannot represent an exact zero!
Example 1: 3.0
0 10000000000 1000000000000000000000000000000000000000000000000000
(−1)0 · 2210−1023 ·
(1+
1
2
)= 1 · 21 · 3
2= 3.0
Lecture Notes #01
Computer Arithmetic and Finite Precision
Finite Precision: Examples
r = (−1)s2c−1023(1+m), c =10∑k=0
ck2k , m =
51∑k=0
mk
252−k
Example 2: The Smallest Positive Real Number
0 00000000000 0000000000000000000000000000000000000000000000000001
r = (−1)0 · 20−1023 ·(1+
1
252
)= (1+ 2
−52) · 2−1023 · 1 ≈ 10−308
Example 3: The Largest Positive Real Number
0 11111111110 1111111111111111111111111111111111111111111111111111
r = (−1)0 · 21023 ·(1+
1
2+
1
22+ · · ·+ 1
251+
1
252
)= 2
1023 ·(2− 1
252
)≈ 10
308
Lecture Notes #01
Computer Arithmetic and Finite Precision
Finite Precision: Examples
r = (−1)s2c−1023(1+m), c =10∑k=0
ck2k , m =
51∑k=0
mk
252−k
Example 2: The Smallest Positive Real Number
0 00000000000 0000000000000000000000000000000000000000000000000001
r = (−1)0 · 20−1023 ·(1+
1
252
)= (1+ 2
−52) · 2−1023 · 1 ≈ 10−308
Example 3: The Largest Positive Real Number
0 11111111110 1111111111111111111111111111111111111111111111111111
r = (−1)0 · 21023 ·(1+
1
2+
1
22+ · · ·+ 1
251+
1
252
)= 2
1023 ·(2− 1
252
)≈ 10
308
Lecture Notes #01
Computer Arithmetic and Finite Precision
Finite Precision: Consequences
There are gaps in the �oating-point representation. I.e., any number inthe interval [
3.0, 3.0+1
252
)is represented by value 3.0.
Floating point �numbers� represents intervals!
Lecture Notes #01
Computer Arithmetic and Finite Precision
Quantifying the Error
Let p∗ be an approximation to p, then
De�nition (The Absolute Error)
|p − p∗|
De�nition (The Relative Error)
|p−p∗||p| , p 6= 0
Lecture Notes #01
Computer Arithmetic and Finite Precision
Quantifying the Error
Let p∗ be an approximation to p, then
De�nition (The Absolute Error)
|p − p∗|
De�nition (The Relative Error)
|p−p∗||p| , p 6= 0
Lecture Notes #01
Computer Arithmetic and Finite Precision
Sources of Numerical Errors - Roundo� Errors (Rounding andTruncating) I
Examples in 5-digit arithmetic
Rounding 5-digit arithmetic:
(96384+ 26.678)− 96410 =
(96384+ 00027)− 96410 =
96411− 96410 = 1.0000
Truncating 5-digit arithmetic:
(96384+ 26.678)− 96140 =
(96384+ 00026)− 96410 =
96410− 96410 = 0.0000
Lecture Notes #01
Computer Arithmetic and Finite Precision
Sources of Numerical Errors - Roundo� Errors (Rounding andTruncating) I
Examples in 5-digit arithmetic
Rounding 5-digit arithmetic:
(96384+ 26.678)− 96410 =
(96384+ 00027)− 96410 =
96411− 96410 = 1.0000
Truncating 5-digit arithmetic:
(96384+ 26.678)− 96140 =
(96384+ 00026)− 96410 =
96410− 96410 = 0.0000
Lecture Notes #01
Computer Arithmetic and Finite Precision
Sources of Numerical Errors - Roundo� Errors (Rounding andTruncating) II
Rearrangement changes the result:
(96384− 96410) + 26.678 = −26.000+ 26.678 = 0.67800
Numerically, order of computation matters!
Lecture Notes #01
Algorithms
De�nition (Algorithm)
An algorithm is a procedure that describes, in an unambiguous manner, a�nite sequence of steps to be performed in a speci�c order.
In this class, the objective of an algorithm is to solve a problem orapproximate a solution to a problem.Algorithms work very similarly to the meal recipes.
Lecture Notes #01
Algorithms
De�nition (Algorithm)
An algorithm is a procedure that describes, in an unambiguous manner, a�nite sequence of steps to be performed in a speci�c order.
In this class, the objective of an algorithm is to solve a problem orapproximate a solution to a problem.Algorithms work very similarly to the meal recipes.
Lecture Notes #01
Algorithms
Key Concepts for Numerical Algorithms � Stability
De�nition (Stability)
An algorithms is said to be stable if small changes in the input, generatesmall changes in the output.
At some point we need to quantify what �small� means!If an algorithm is stable for a certain range of initial data, then it is said tobe conditionally stable.
Lecture Notes #01
Algorithms
Key Concepts for Numerical Algorithms � Stability
De�nition (Stability)
An algorithms is said to be stable if small changes in the input, generatesmall changes in the output.
At some point we need to quantify what �small� means!If an algorithm is stable for a certain range of initial data, then it is said tobe conditionally stable.
Lecture Notes #01
Algorithms
Key Concepts for Numerical Algorithms � Error Growth
Suppose E0 > 0 denotes the initial error, and En represents the error after noperations.
If En ≈ C · E0 · n (for a constant C which is independat of n), then thegrowth is linear.
If En ≈ Cn · E0, C > 1, the the growth is exponential � in this case theerror will dominate very fast (undesirable scenario).
Linear error growth is usually unavoidable, and in the case where C andE0 are small the results are generally acceptable. � Stable algorithm.
Exponential error growth is unacceptable. Regardless of the size of E0 theerror grows rapidly. � Unstable algorithm.
Lecture Notes #01
Algorithms
Reducing the E�ects of Roundo� Error
The e�ects of roundo� errors can be reduced by using higher-order-digitarithmetic such as the double or multiple-precision arithmetic available onmost computers.
Disadvantages in using double precision arithmetic are that it takes morecomputation time and the growth of the roundo� error is not
eliminated but only postponed.
Sometimes, but not always, it is possible to reduce the growth of theroundo� error by restructuring the calculations.
Lecture Notes #01
Algorithms
Key Concepts - Rate of Convergence
De�nition (Rate of Convergence)
Suppose the sequence β = {βn}∞n=1 converges to zero, and α = {αn}∞n=1converges to a number α.If ∃K > 0 : |αn − α| < K · βn, for n large enough, then we say that {αn}∞n=1converges to α witha Rate of Convergence O(βn) (�Big Oh of βn�).We write
αn = α+O(βn)
Note: The sequence β = {βn}∞n=1 is usually chosen to be
βn =1
np
for some positive value of p.
Lecture Notes #01
Algorithms
Key Concepts - Rate of Convergence
De�nition (Rate of Convergence)
Suppose the sequence β = {βn}∞n=1 converges to zero, and α = {αn}∞n=1converges to a number α.If ∃K > 0 : |αn − α| < K · βn, for n large enough, then we say that {αn}∞n=1converges to α witha Rate of Convergence O(βn) (�Big Oh of βn�).We write
αn = α+O(βn)
Note: The sequence β = {βn}∞n=1 is usually chosen to be
βn =1
np
for some positive value of p.
Lecture Notes #01
Algorithms
Rate of Convergence: Example
Consider the sequence (as n→∞)
αn = sin
(1
n
)− 1
n.
Then αn = O(1n3
).
Lecture Notes #01
Algorithms
Generalizing to Limits of Functions
De�nition (Rate of Convergence)
Supposelimh→0
G (h) = 0, and limh→0
F (h) = L.
If ∃K > 0∀h < H (for some H > 0):
|F (h)− L| ≤ K |G (h)|
thenF (h) = L+O(G (h)).
We say that F (h) converges to L with a Rate of convergence O(G (h)).
Note: Usually we consider G (h) = hp for some positive p.
Lecture Notes #01
Algorithms
Generalizing to Limits of Functions
De�nition (Rate of Convergence)
Supposelimh→0
G (h) = 0, and limh→0
F (h) = L.
If ∃K > 0∀h < H (for some H > 0):
|F (h)− L| ≤ K |G (h)|
thenF (h) = L+O(G (h)).
We say that F (h) converges to L with a Rate of convergence O(G (h)).
Note: Usually we consider G (h) = hp for some positive p.
Recommended