Numerical Methods

Code:

EA0017

Acronym:

MN

Keywords
Classification	Keyword
OFICIAL	Interp/Personal professional attitudes and capac.
OFICIAL	Basic Sciences

Instance: 2011/2012 - 1S

Active?	Yes
Web Page:	http://moodle.fe.up.pt/course/view.php?id=776
Responsible unit:	Mining Engineering Department
Course/CS Responsible:	Master in Environmental Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
MIEA	58	Syllabus since 2006/07	2	-	6	56	162

Teaching language

Suitable for English-speaking students

Objectives

Objectives, skills and Learning outcomes
a) Background:
To have had Calculus, Fundaments of Informatics, Linear Algebra and Calculus.
To be interested in the usage of mathematics as a laboratorial tool.

b) Specific Aims:
To provide the students:
• a set of numerical tools able to be used in their professional life;
• to be able to look at applied mathematics in a critical way and to use it without prior misconceptions.

c) Previous knowledge:
To be able to produce fluxograms and to do program analysis;
To be a able to use previously writen routines and to integrate them in a script; to program in a structured way using a 4th level language;
To be a able to use spreadsheets with a scientific purpose; to use algebraic manipulators.
To have a sound knowledge of the basic principles of Linear Algebra and Calculus and to be able to use them in an applied way.

d) Percentual distribution (scientific and technological components):
Scientific component: 70%
Technological component: 30%.

e) Learning Outcomes
At the end of this course unit, students should be able to:
• solve problems of numerical calculus concerning each one of the topics of this course unit;
• understand and deal with: precision and error checking; error measurement and its propagation; intrinsic numerical instabilities;
• perform critical analysis of numerical singularities and instabilities;
• match numerical methods to a given problem;
• solve convergence problems;
• analyze algorithms behavior and their connection with the formulation of a physical problem.
Ideally, at the end of the semester they must be autonomous in:
• programming in a structured way;
• using a spreadsheet for scientific calculus in a numerical approach;
• using algebraic manipulators and to understand the scope and limitations of the found solutions;
• programming in a 4th level language
• using of numerical methods with a critical eye.

Program

1. Introduction
b. Refresher in Calculus, Linear Algebra and in 4th generation programming;
c. Entry test
2. Roots of transcendental equations: bisection; secant method; Newton’s method; fixed point method as an historical curiosity and its aberrations; Muller’s method; Velocities and convergence.
3. Systems of linear equations: Gauss decomposition with backwards substitution and Gauss-Jordan decomposition; pivoting; LU factorization and its different variants; Iterative methods.
4. Floating-point representation:
a. Numerical errors; its propagation and consequences; rules of good practice
b. Matrix condition number and numerical instability; Intrinsic error; the importance of condition control; its physical and statistical meaning.
c. Numerical calculation of functions: approximation and error minimization; problems of error propagation applied to the different methods previously illustrated.
5. Mid-term evaluation 1
6. Stable methods in matrix factorization
a. LU factorization: Factorization from Gauss routine with and without pivoting; Direct LU factorization; Conditioning strategies.
b. Determination of eigenvalues and eigenvectors of a matrix – QR factorization; Francis’s algorithm and Householder routine;
7. SVD decomposition and its virtuosities; Sensitivity analysis and its meaning
8. Interpolation: polynomial interpolation; splines.
9. Functional approximation: least squares; continuous least squares; Taylor and Padé approximations; Fourier method; FFT and its applications.
10. Function zeros: the specific problem of polynomial resolution – strategies to solve the problem; polynomials with pathological behavior.
11. Mid-term evaluation 2
12. Numerical solution of ordinary differential equations with first point conditions and numerical integration:
a. Classic methods and extrapolation problems: Taylor expansion; Euler e Runge-Kutta.
b. Modified Euler as an introduction to Predictor-Corrector methods:
c. Multi-step methods, predictor-corrector methods; convergence criteria, errors and their propagation
13. Differentiation and quadrature
a. The problem of numerical differentiation. Usage of overcoming strategies
b. Numerical integration: trapezium rule and Simpson’s rule, Gaussian quadrature; Improper integrals; Multiple integrals. Singularities. Other quadrature methods.
c. Adaptative Runge-kutta
14. Mid-term test 3
15. Ordinary differential equations with contour conditions: heuristic methods; finite differences method; Partial derivatives equations: parabolic, hyperbolic and elliptic.
16: Differential equations with partial derivatives: parabolic; hyperbolic and elliptic types.
17. Introduction to linear optimization and non-linear optimization. Use of heuristic methods to solve simple multivariate problems: Powell’s methods; Polytope; Weaknesses of heuristic methods. Presentation of an algorithm of quasi-Newton method to illustrate problems: matrix condition, control of the numerical error. Sensitivity analysis.
18. Final test

Mandatory literature

Fausett, Laurene V.; Applied numerical analysis using Matlab. ISBN: 0-13-319849-9
Moler, Cleve B.; Numerical computing with Matlab. ISBN: 0-89871-560-1
Valença, Maria Raquel; Análise numérica. ISBN: 972-674-195-5
J. H. Heinbockel; Numerical methods for scientific computing. ISBN: 978-1-4120-3153-0
E. Joseph Billo; Excel for scientists and engineers. ISBN: 978-0-471-38734-3
Gerald, Wheatley; Applied Numerical Analysis, Pearson Education, 2007. ISBN: 8131717402, 9788131717400
by Stormy Attaway; MATLAB. ISBN: 978-0-7506-8762-1

Complementary Bibliography

Acton, Forman S.; Numerical methods that work. ISBN: 0-88385-450-3
Vetterling, William T. 070; Numerical Recipes. ISBN: 0-521-43721-0
Jon Mathews, R. L. Walker; Mathematical methods of physics. ISBN: 0-8053-7002-1
Farlow, Jerry 340; Differential equations & linear algebra. ISBN: 0-13-186061-5
Lloyd N. Trefethen, David Bau III; Numerical linear algebra. ISBN: 0-89871-361-7
Ekkehard Holzbecher; Environmental modeling. ISBN: 978-3-540-72936-5

Teaching methods and learning activities

1. Expositive lectures correspond to about 33% of the total time. Two thirds of it, (i.e. 22% of the total time) correspond to the theoretical fundaments of numerical methods; the remaining time is dedicated to the presentation of the practical implementations of the methods in a spreadsheet and/or in a 4th generation programming language.
2. Each one of the methods is implemented first in a spreadsheet. Afterwards the students may be required to produce a flowchart of the algorithm and its implementation in a programming environment. There is no emphasis on mathematical proof but instead the methods are often taught using geometric analogies; reasoning is largely heuristic.
3. Due to short contact time, practical classes are mainly tutorial to clarify issues that raided to student during the resolution of proposed problems.
4. The spreadsheet is used as” a paper and pencil facility” to implement the methods, but with mathematical capabilities.
5. Students are stimulated to feel that they are able to use the methods taught in a experimental spirit not possible in other course units of Maths. Then they are faced with a method that fails: there is a singularity, or the required precision diminishes or even instabilities occurs. At this point, students are able to go deeper into the structure of a numerical method, because they feel they can solve the problem.
6. Afterwards a connection between each one of the subjects of the course units of Mathematical Analysis and Linear Algebra and the numerical method that is being used is established. At this moment, but only if necessary, mathematical deductions, will be presented

The students are provided, for each one of the taught methods, with:
- a spreadsheet containing a solved exercise;
- a problem to deal with, which should constitute a part of the portfolio to be delivered;
- eventually, a more difficult problem to be solved.
The students must run the algorithms under different conditions in order to get a good practical understanding of the capabilities and shortcomings of each one of the methods.

Software

Folha de cálculo
Octave
Maxima
Matlab 6 R12.1

keywords

Physical sciences > Mathematics > Applied mathematics > Engineering mathematics
Physical sciences > Mathematics > Applied mathematics > Numerical analysis
Technological sciences > Engineering > Simulation engineering

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Description	Type	Time (hours)	Weight (%)	End date
Attendance (estimated)	Participação presencial	56,00
Homework 1	Trabalho escrito
Homework 2	Trabalho escrito
Homework 3	Trabalho escrito
Homework 4	Trabalho escrito
Homework 5	Trabalho escrito
Homework 6	Trabalho escrito
Homework 7	Trabalho escrito
Homework 8	Trabalho escrito
Homework 9	Trabalho escrito
Homework 10	Trabalho escrito
Homework11	Trabalho escrito
Homework 12	Exame
Entry test	Exame	2,50
Mid-term test 1	Exame	2,50
Mid-term test 2	Exame	2,50
Mid-term test 3	Exame	2,50
Final test	Exame	2,50
	Total:	-	0,00

Eligibility for exams

1. Registered student attendance in a minimum of ¾ of the mandatory classes.
2. Delivery, at the deadline, at least ¾ of the total homework.
3. Only the homework that corresponds to the previous paragraph and that was answered in a positive way in at least 35% of its extension during the mid-term tests will be considered.
4. Positive marks in all the mid-term tests.

Calculation formula of final grade

This course unit has continuous assessment (i.e. it is assessed the process of learning and not the learning outcomes).
Students have to deliver a group of assignments during the semester. Its sum will constitute a final personal portfolio. The assessment (quantitative) will be based on that portfolio.
The mid-term tests will provide information about the capabilities of the student concerning the assignments. If the proficiency of the student in a exercise will not be proved in the mid-term test, the corresponding assignment will not count for its final grade.
Portfolio = 70% of the total grade
Mid-term tests = 30% of the total grade.

Examinations or Special Assignments

Students may be asked to carry out an extensive assignment.
in 2010/2011 consisted in a set of numerical MatLab routines with interpreted results.
In 2011/2012 there was no extensive assignment.

Special assessment (TE, DA, ...)

Students, who cannot attend classes, should work outside class time with a colleague who attend classes regularly and must have a reasonable number of contact hours with the teacher (outside classes).
The assessment is based on the presentation of the same portfolio that is to be produced by regular students. Mid-term tests are mandatory.

Classification improvement

Students should not be able to improve their grades, due to the continuous assessment nature of this course unit.
However, in order to comply with FEUP’s rules, students may improve their grades if they solve a pack of extra assignments within a deadline agreed between students and professor. It will be followed by an individual final test that will assess the way exercises were solved.

Observations

This course unit is complemented by an e-learning module.