5.3    Fixed point iteration

Given a function f (①) = e-① - cos(①). we want to ind a root T such that f (T) = O.

(a).  First show that there is a root inside the interval [1.1）1.6].

(b). Next, we try to locate this root by aixed point iteration. we observe that f (①) = O is equivalent to

① = g1 (①)）     where       g1 (①) = f (①) + ①.

set up the corresponding ixed point iteration scheme. Then, choose the starting point ①0  = 1.6, and perform 4 iterations to compute the values ① 1）①2）①3）①4 .  what do you observe？Does the method converge？ why？

(c). we now observe that f (①) = O is also equivalent to

① = g2 (①)）     where       g2 (①) = ① - f (①).

Based on this new function, setup the corresponding ixed point iteration.  choose again ①0  = 1.6 as your starting point , and perform 4 iterations to compute the values ① 1）①2）①3）①4. what is your result？ How diferent is it from part (b)？ Does the method converge？ why？

5.4 More on ixed point iteration.

consider the iteration scheme：

①n+1  = ①n + ） ①0 = 1

(a). If the iteration converges, what is  limny…①n？

(b).  Does the method converge？ why？

5.5 Newton,s method

As you have seen in Example 5.7 in section 5.4, the computation of ^R can be carried out by inding the root of f (①) = ①2  - R using Newton,s method.

(a).  check that in this case Newton,s iteration scheme is

①n+1  = ①n + .

(b).  show that the sequence (①”)”Σ1 satisies

①”(2)+1 - R = 2 .

Interpret this equation in terms of quadratic convergence.

Remark:  The quantity ①”(2) - R  =  f (①”)  is also called the  Tesidual.   It  gives  a

measure of the error in the approximation ①”.

(c).  Now we test the iterations for R = 10.  choose ①0 = 3, and compute ① 1 , ①2 ①3  and ①4. use 8 digits in your computation. comment on your result.

5.6    on Newton,s Method

Each of the following function has ^3R as a zero for any positive real number R. Deter- mine the formulas for Newton,s method for each and any necessary restrictions on the choice for ①0 .

(a). a(①) = ①3  - R

(b).  b(①) = ①2  - R/①

(c). c(①) = 1 - R/①3

(d). d(①) = 1/①2  - ①/R

5.7 Newton,s Method in Matlab

preparation: use“help fprintf”in Matlab to understand how to use“fprintf” to display the data. Here is an example:

fprintf（,Ⅰ have n=xd  and  x=xg    but  f=xf.\n,,2,1.22,  1.22）

This will give the following result in Matlab:

Ⅰ  have  n=2  and  x=1.22    but  f=1.220000 .

The problem: write a Matlab function for Newton,s method. your ile mynewton.m should start with:

function x=mynewton（f,df,x0,tol,nmax）

Among the input variables, f,df are the function f and its derivative f地 , x0 is the initial guess, tol is the error tolerance, and nmax is the maximum number of iterations.  The output variable x is the result of the Newton iterations.  use  sprintf and“disp”to display your result in each iteration so you can check the convergence along the way.

First, test your function with Example 5.7 in section 5.4, computing^2.

Then, use your Matlab function to ind a root of f (①) = e-π  - cos(①) on the interval [1.1）1.6].  use tol=1e-12 and nmax=10.  You  should choose an initial guess ①0   on the interval [1.1）1.6]. what is your answer？

what to hand in: submit your iles mynewton.m, iles for functions f (①) and f地 (①), script ile, test result for the example of ^2 and for the root off (①) = e-π  - cos(①).

5.8 when Newton,s Method Does not work well.

(i). Let m be a positive integer and consider the function

f (①) = (① - 1)m.

It is clear that T = 1 is a root (indeed, it is a root with multiplicity m). we now try to ind this root by Newton,s iteration, for m = 8.

(a).  set up the iteration scheme.

(b).  use ①0  = 1.1 as your initial guess (note that this is very close to the root T = 1). complete 4 iterations to compute the values ① 1）①2）①3）①4 .

(c).  How does the method work for this problem？ Do we still have quadratic conver- gence？ can you explain what is causing this？

(d). If m = 2o (or with any large value of m), can you predict the behavior of Newton,s iteration？ what type of convergence will you get？ Explain in detail.

(ii). use Newton,s method to solve the equation

o = + ①2  - ① sin(①) - cos(2①)）with ①0  = .

Iterate using Newton,s method until an accuracy of 1o-3  is obtained. Explain why the result seems unusual for Newton,s method.

5.9    some Modiied Newton,s Methods； Bonus

(a) To avoid computing the derivative at each step in Newton,s method, it has been proposed to replace f\ (①n) by f\ (①0), i.e.,

f (①n)

①n+1 = ①n - f\ (①0) .

Derive the rate of convergence for this method.

(b) If the root  T of f (①)  =  O is  a double root,  i.e.,  f (T)  =  O  and  f\ (T)  =  O,  but

f\\ (T) O, the Newton,s method can be accelerated by using

①n+1 = ①n - 2 .

show that this method is quadratically convergent. If the general case is hard to prove, the prove it for the example f (①) = ① (① - 1)2  where T = 1 is a double root.

Run a Matlab simulation with this method for a test case of your choice.  observe the convergence and comment on your results.

5.10    The secant method

a).  calculate an approximate value for 43/5  using the secant method with ①0 = 3 and ① 1  = 2.  Make 3 steps, and compute the values ①2）①3）①4. comment on your result.

b).  use secant method to ind the root for f (①) = ①3 - 2①+ 1 with ①0  = 4 and ① 1 = 2. compute the values ①2）①3  and ①4 .  Does the method converge？ (you can easily check that ① = 1 is a root.)

c).  consider the iteration scheme

①n+1  = ①n + (2 - e①π )(①n - ①n-1 )/(e①π - e①π - 1 )） ①0  = O） ① 1 = 1.

If the iteration converges, what is limn一凯①n ？

5.11 The secant Method in Matlab

write a Matlab function to locate a root by the secant method.  your function should

be put in the ile mysecant.m, and should be called as

x=mysecant（f,xo,x1,tol,nmax）