NM18

M1314.001200 Introduction to Numerical Methods

Syllabus

Instructions for how to install MATLAB on your computer.

Lecture notes: 

part I (ch. 1-2 of textbook) (updated 3 April with some typos fixed)

part II (relevant sections of ch. 3-5 of textbook) 

note on functions of several variables (an example with some MATLAB code for plotting functions of two variables) 

Exams / solutions:

Mid-term exam, solution

Final exam, solution

Plan for lectures:

5 March [1]

Plan: introduction to course content and to MATLAB; ch. 1 of textbook; p. 2-5 in lecture notes part I.

Homework for this class: none

12 March [2]

Plan: sections 2.1-2.4 of textbook; p. 5-22 (including statement, but not proof, of Theorem 2.2. We leave 2.2.2 Types of convergence for next lecture) in lecture notes part I. 

Homework: Install MATLAB on your own computer. Exercises ch. 1: 1, 4-8. In Ex. 6, also consider what happens if the problem is changed to [(100/3)-33]/0.3300. 

Solutions

19 March [3]

Plan: sections 2.5-2.6 of textbook; p. 22-34 (starting with proof of Th. 2.2, ending with Th. 2.3, plus 2.2.2 Types of convergence) in lecture notes part I. 

Homework: 

Questions not from the textbook: 

1. Write a program that, for a given input x (a real number), creates a variable y that takes on the following values, depending on the value of x: 1000*x if x is negative, square root of 2 if x is 0, 100*x if x is in the interval (0, 3], and 10*x if x is greater than 3. Test your program by running it for x = -5, 0, 2.95, 3, 5 and checking that it gives the right answer. (Hint: use if .... elseif ... else ... end. You can look these up in MATLAB's help function or by googling for instance else matlab. Also, googling relational matlab should give you information about >, <, etc.)

2. Write a program that first creates a 10 x 1 vector (call it x) of zeros. (Hint: google zeros matlab.) Give the first element of the vector, x(1), the value 3.5. Then, using for ... end (google for matlab), for each i=2,3,...,10, let x(i) = x(i-1)^(1.1). Print the whole vector at the end. 

3. Consider the sequences given by 1/k and 1/(k^2). In each case, how large must k be before the value of the sequence is less than 10^(-6)? Answer the question by hand, and then write a program to check your answers. 

4. Write a program that creates a function handle / anonymous function (google anonymous function matlab) called fun1 that calculates x^2-3. Write a function file (google function file matlab to get information about how to do this) that you call fun2 that also calculates x^2-3. Finally create a function fun3 that also calculates x^2-3, but this time save the function at the end of your script file. Then evaluate x^2-3 at x=2, by using fun1, fun2 and fun3.

5. Similarly to question 4., create a function handle fun1b, a file function fun2b and a local function fun3b as above, but as a second output argument, include the derivative of the function f(x) = x^2-3. For the anonymous function, let the two output arguments be two entries in a 2x1 vector. Again evaluate all functions at x=2.

Textbook exercises:

ch. 2: 1-3. In 1, write a program to find out what the sequences converge to. In 2, write a program to check your answer. In the last part of 3, try to answer the question and provide some kind of justification, even if you cannot prove it. 

Solutions

26 March [4]

Plan: Discuss solutions to programming questions 1-5 that were homework for last week, and problem 2.9 in the textbook (this week's homework), and other MATLAB issues. 

Homework: Exercises ch. 2: 8, 9. In 9, use Newton's method / backtracking (follow pseudo code 2.5.1 on p. 26 in the textbook). Although not everything is relevant at this stage, it might be a good idea to read section 7.3 pp. 161-164 in the textbook, on testing. In addition to the functions in the problem, test your program on (e) f(x) = arctan(x), x_0 = 2, 100; (f) f(x) = -0.02 + exp(x)/[1 + exp(x)], x_0 = 2, (g) same function as in (d) but x_0 = 4.5. For the last three parts of the question (as stated in the textbook), "What rate of ..." etc., you do not need to do any kind of "proof" here. Just think about what the rate of convergence looks like. This probably requires printing |f(x)| for each iteration. Plot the functions in (e) and (f) for x between -10 and 10 (google plot matlab, linspace matlab, subplot matlab). Judging from the graph, what might happen for the last function (f) if you choose a starting value such as x_0 = 5? You can try.

Solutions

2 April [5]

Plan: section 2.7 of textbook; p. 34-40 (starting with Th. 2.4) in lecture notes part I. 

Homework: Exercise 2.11 in the textbook. Use Newton's method for the local step and the global strategy described on p. 35 in the textbook. Test your algorithm on f(x)= x^4 - 4x^3 + 4x^2 + 4, with x_0 = -1, 0.5, 1, 1-1e-1, 1-1e-3, 1+1e-3, 1.5, 2.5. Plotting f(x) might help to understand what happens at different starting values. You can compare your results with MATLAB's fminunc. If f'(x_0)=0, there is not a lot the algorithm can do. A simple remedy is to add a small perturbation to x_0 if this is the case. 

Solution

9 April [6]

Plan: Start covering chapter 3 of the textbook. (From Chapter 3, we will cover only sections 3.1-3.3, 3.5, skip 3.4 and 3.6, and cover 3.2 only very superficially; see lecture notes).

Homework: Exercise 2.16 in the textbook. [Hints: (try without these first; also there are probably other ways of doing this). First use Th. 2.6 in the lecture notes (part I) to show that there are regions where f'(x) has the same sign as f'(x_c) and where f(x) has the same sign as f(x_c). Then use an integral, in a (somewhat) similar way to in the proof of Th. 2.7.1 in the textbook to show what the sign of f(x_c+lambda*d)-f(x_c) is depending on the sign of f(x_c). Finally, use the fact that |a|=a if a>0 and |a|=-a if a<0.]

Solution

16 April

MID-TERM EXAM. 9.30 - 11.00. Same room as lectures. Please get there early so the exam can start on time, without distractions from people arriving late.

Relevant material: section 1.3 of ch. 1, and all of chapter 2. There will be no questions about MATLAB, but there could be questions about the algorithms discussed in chapter 2 of the textbook.

Solution

23 April [7]

Plan: section 4.1 of textbook (we will not cover section 4.2). 

30 April [8]

Plan: sections 4.3, 5.1-5.2, 5.5 (only up to second para. of p. 101) of textbook (we will not cover sections 5.3, 5.4 and 5.6), 6.1-6.2 (until middle of p. 114).

7 May 

No lecture - public holiday. 

14 May [9]

Plan: sections 5.5 (only p. 101-102 about modification of Hessian), 6.3 (until p. 120), 6.3.2, 6.4 (until p. 133), 6.4.2.

21 May [10]

Plan: sections 6.4.3, 6.5. (We did not cover chapter 7 in class, but it might be useful to have a quick look at it, just to be aware of some possible pitfalls regarding scaling etc.)

28 May [11] and

4 June [12]

Plan:

Three student teams (see team member list here) give presentations of length 60-80 minutes on the following topics (one topic per team, relevant textbook sections in parentheses, only readings specified for 14 and 21 May are relevant, for example section 6.4.1 can be ignored by Team 2). (Team x presents topic x, for x=1,2,3)

Dates for presentations

28 May: Team 1 and Team 2

4 June: Team 3

The presentation should have the following features:

Note that the computer in the lecture room does not have MATLAB installed, so you must bring a laptop for your presentation. It is straightforward to connect it to the projector using an RGB cable, available in the lecture room. Check in advance if you need an adapter, which can be purchased in the student centre.

11 June 

FINAL EXAM.

A large part of the exam will be of the form: explain Algorithm X, where you can choose X to be any of topics 1., 2. and 3. for the presentations, so preparing presentations should be very useful exam presentation.