Zeros of functions with Matlab: Fixed point iteration

(1)

Emma Perracchione

Corso di Calcolo Numerico per Ingegneria Meccanica - Matr. PARI (Univ. PD)

Gli esercizi sono presi dal libro: S. De Marchi, D. Poggiali, Exercices of numerical calculus with solutions in Matlab/Octave.

A.A. 2018/2019

(2)

Materiale

TUTTO IL MATERIALE SI TROVA AL SEGUENTE LINK E VERRA’

AGGIORNATO AD OGNI LEZIONE.

https://www.math.unipd.it/~emma/CN1819.html OPUURE VEDASI

https://elearning.unipd.it/dii/course/view.php?id=1720

(3)

Zeros of functions with Matlab: Fixed point iteration Remarks

Introduction

Finding the zeros of a function means finding:

¯

x : f (¯ x ) = 0.

We already know two approaches to solve such problem:

1

bisection method,

2

Newton.

In this lecture we will see the fixed point iteration.

It is based on building {x _k } _k≥1 converging to the fixed-point of an

auxiliary function g (x ) = x − f (x ).

(4)

Remarks

Bisection

Property

Given a continuous function f : [a, b] −→ R such that f (a)f (b) < 0 then

∃ ¯ x ∈ (a, b) so that f (¯ x ) = 0.

Thus, at the first step of the bisection method, we evaluate the mid point m ₁ of [a, b] = [a ₁ , b ₁ ]. If f (m ₁ )f (a) < 0 then

[a 2 , b 2 ] = [a 1 , m 1 ], else

[a ₂ , b ₂ ] = [m ₁ , b ₁ ].

We proceed in this way until a stopping criterion is satisfied, such as

f (m _k ) < τ , for a fixed tolerance τ , at a certain step k.

(5)

Newton

Theorem (Convergence of Newton’s method)

Let f (x ) ∈ C ² ([a, b]). Suppose f (¯ x ) = 0 and f

⁰

(¯ x ) 6= 0 for some

x ∈ (a, b). Then, there exists δ ∈ R, δ > 0 such that for x ¯ 0 ∈ [¯ x − δ, ¯ x + δ]

the iterations via Newton’s method x _k+1 = x _k − f (x _k )

f ⁰ (x k ) , k = 1, 2, . . . , converges quadratically to ¯ x .

The main drawback is that with Newton’s method we need to start

with an initial condition sufficiently close to the zeros of functions.

(6)

Exercises

Exercise 0

Exercise

Modify the script Newton for multiple zeros. Call it NewtonMod.

Hint

The iteration becomes

x k+1 = x k − m f (x k )

f ⁰ (x _k ) , k = 1, 2, . . . ,

where m is the multiplicity of the zero.

(7)

Fixed point

We want to find ¯ x so that f (¯ x ) = 0 or equivalently the fixed point of g (x ) = x , for f (x ) = x − g (x ) = 0.

Theorem

Let us consider x ^(k+1) = g (x ^(k) ), for k ≥ 0, with x ⁽⁰⁾ given. If

1

g : [a, b] → [a, b];

2

g ∈ C ¹ ([a, b]);

3

∃K < 1 such that |g

⁰

(x )| < K ∀x ∈ [a, b];

then g has a unique fixed point ¯ x in [a, b] and {x ^(k) } _k>1 converges to

¯

x ∈ [a, b].

(8)

Exercises

Exercise 1

Exercise

Write a Matlab function called fixedpoint for computing the zeros of functions with the fixed point iteration.

Hint

Use an exit criterion in case the method does not converge.

For the fixed point iteration the inputs that we need are g,x0,tol,maxiter.

Fix the stopping criterion for the fixed point as abs(x1-x0)<tol, where

x1,x0 are two successive iterations.

(9)

Zeros of functions with Matlab: Fixed point iteration Exercises

Exercise 2

Exercise

Take the function f (x ) = x ² − log(x ² + 2) of which we want to compute its zeros. Write a script called Esercizio2 so that:

By plotting the graph of f , individuates the two real roots of f (x ) = 0 and the corresponding separation intervals, I ₁ e I ₂ .

Find two convergent iterative methods, with iteration functions g _i (x ), i = 1, 2. For each one of them determines the number of necessary iterations. Consider k max = 50, as max number of iterations and, for the test on the relative error tol = 1.e − 6.

Zeros of functions with Matlab: Fixed point iteration

Zeros of functions with Matlab: Fixed point iteration

Emma Perracchione

Corso di Calcolo Numerico per Ingegneria Meccanica - Matr. PARI (Univ. PD)

Gli esercizi sono presi dal libro: S. De Marchi, D. Poggiali, Exercices of numerical calculus with solutions in Matlab/Octave.

A.A. 2018/2019

Materiale

TUTTO IL MATERIALE SI TROVA AL SEGUENTE LINK E VERRA’

AGGIORNATO AD OGNI LEZIONE.

https://www.math.unipd.it/~emma/CN1819.html OPUURE VEDASI

https://elearning.unipd.it/dii/course/view.php?id=1720

Introduction

Finding the zeros of a function means finding:

¯

x : f (¯ x ) = 0.

We already know two approaches to solve such problem:

bisection method,

Newton.

In this lecture we will see the fixed point iteration.

It is based on building {x k } k≥1 converging to the fixed-point of an

auxiliary function g (x ) = x − f (x ).

Bisection

Property

Given a continuous function f : [a, b] −→ R such that f (a)f (b) < 0 then

∃ ¯ x ∈ (a, b) so that f (¯ x ) = 0.

Thus, at the first step of the bisection method, we evaluate the mid point m 1 of [a, b] = [a 1 , b 1 ]. If f (m 1 )f (a) < 0 then

[a 2 , b 2 ] = [a 1 , m 1 ], else

[a 2 , b 2 ] = [m 1 , b 1 ].

We proceed in this way until a stopping criterion is satisfied, such as

f (m k ) < τ , for a fixed tolerance τ , at a certain step k.

Newton

Theorem (Convergence of Newton’s method)

Let f (x ) ∈ C 2 ([a, b]). Suppose f (¯ x ) = 0 and f

(¯ x ) 6= 0 for some

x ∈ (a, b). Then, there exists δ ∈ R, δ > 0 such that for x ¯ 0 ∈ [¯ x − δ, ¯ x + δ]

the iterations via Newton’s method x k+1 = x k − f (x k )

f 0 (x k ) , k = 1, 2, . . . , converges quadratically to ¯ x .

The main drawback is that with Newton’s method we need to start

with an initial condition sufficiently close to the zeros of functions.

Exercise 0

Exercise

Modify the script Newton for multiple zeros. Call it NewtonMod.

Hint

The iteration becomes

x k+1 = x k − m f (x k )

f 0 (x k ) , k = 1, 2, . . . ,

where m is the multiplicity of the zero.

Fixed point

We want to find ¯ x so that f (¯ x ) = 0 or equivalently the fixed point of g (x ) = x , for f (x ) = x − g (x ) = 0.

Theorem

Let us consider x (k+1) = g (x (k) ), for k ≥ 0, with x (0) given. If

g : [a, b] → [a, b];

g ∈ C 1 ([a, b]);

∃K < 1 such that |g

(x )| < K ∀x ∈ [a, b];

then g has a unique fixed point ¯ x in [a, b] and {x (k) } k>1 converges to

¯

x ∈ [a, b].

Exercise 1

Exercise

Write a Matlab function called fixedpoint for computing the zeros of functions with the fixed point iteration.

Hint

Use an exit criterion in case the method does not converge.

For the fixed point iteration the inputs that we need are g,x0,tol,maxiter.

Fix the stopping criterion for the fixed point as abs(x1-x0)<tol, where

x1,x0 are two successive iterations.

Exercise 2

Exercise

Take the function f (x ) = x 2 − log(x 2 + 2) of which we want to compute its zeros. Write a script called Esercizio2 so that:

By plotting the graph of f , individuates the two real roots of f (x ) = 0 and the corresponding separation intervals, I 1 e I 2 .

Find two convergent iterative methods, with iteration functions g i (x ), i = 1, 2. For each one of them determines the number of necessary iterations. Consider k max = 50, as max number of iterations and, for the test on the relative error tol = 1.e − 6.

Compare the results with the ones obtained with fzero.

It is based on building {x _k } _k≥1 converging to the fixed-point of an

Thus, at the first step of the bisection method, we evaluate the mid point m ₁ of [a, b] = [a ₁ , b ₁ ]. If f (m ₁ )f (a) < 0 then

[a ₂ , b ₂ ] = [m ₁ , b ₁ ].

f (m _k ) < τ , for a fixed tolerance τ , at a certain step k.

Let f (x ) ∈ C ² ([a, b]). Suppose f (¯ x ) = 0 and f

the iterations via Newton’s method x _k+1 = x _k − f (x _k )

f ⁰ (x k ) , k = 1, 2, . . . , converges quadratically to ¯ x .

f ⁰ (x _k ) , k = 1, 2, . . . ,

Let us consider x ^(k+1) = g (x ^(k) ), for k ≥ 0, with x ⁽⁰⁾ given. If

g ∈ C ¹ ([a, b]);

then g has a unique fixed point ¯ x in [a, b] and {x ^(k) } _k>1 converges to

Take the function f (x ) = x ² − log(x ² + 2) of which we want to compute its zeros. Write a script called Esercizio2 so that:

By plotting the graph of f , individuates the two real roots of f (x ) = 0 and the corresponding separation intervals, I ₁ e I ₂ .

Find two convergent iterative methods, with iteration functions g _i (x ), i = 1, 2. For each one of them determines the number of necessary iterations. Consider k max = 50, as max number of iterations and, for the test on the relative error tol = 1.e − 6.