Zeros of functions with Matlab: Accelerating convergence
Zeros of functions with Matlab: Accelerating convergence
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
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
Zeros of functions with Matlab: Accelerating convergence Remarks
Introduction
Finding the zeros of a function means finding:
¯
x : f (¯ x ) = 0.
We already know three approaches to solve such problem:
1
bisection method,
2
fixed-point iteration,
3
Newton’s method.
In this lecture we will see the Aitken’s method.
It is used to accelerate the convergence of iterative methods.
Exercises
Exercise 1
Exercise
Take the function
f (x ) = x 2 − c,
c ≥ 0, and the following two fixed point iteration functions:
1
g 1 (x ) = x − x 2 − c 2x .
2
g 2 (x ) = x − x 2 − c 2x −
x − x 2 − c 2x
2
− c
2
x − x 2 − c 2x
.
Study the convergence of these two iterative methods. In particular take
c = 2 or c = 3 and write a Matlab script called Esercizio1 for testing
the claims.
Zeros of functions with Matlab: Accelerating convergence Remarks
Aitken
Given x = g (x ), from the fixed point iteration theorem, we know that lim
k→∞
x k − ¯ x
x k−1 − ¯ x = g
0(¯ x ), (1) and we also know that
λ k = x k − x k−1
x k−1 − x k−2 ≈ g
0(¯ x ),
Then, by (1) we have
x k − x k+1
x k−1 − x k+1 ≈ λ k .
By solving such equation for x k+1 , we have:
Remarks
Aitken
x k+1 = x k − λ k x k−1
1 − λ k = x k − λ k x k + λ k x k − λ k x k−1
1 − λ k =
= x k + λ k (x k − x k−1 ) 1 − λ k .
Then, by replacing the value of λ k , we obtain the Aitken’s iteration:
x k+1 = x k − (x k − x k−1 ) 2 x k − 2x k−1 + x k−2 .
Property
Let x k+1 = g (x k ) an iterative fixed point method of order p ≥ 1. If p = 1
Aitken converges to the simple root ¯ x with order 2, if p ≥ 2 then its
convergence order is 2p − 1.
Zeros of functions with Matlab: Accelerating convergence Exercises
Exercise 2
Exercise
Take the function f (x ) = x 2 − log(x 2 + 2) of which we want to compute the positive zero. For that use bisection, Newton, Aikten (alredy in your folder!) and fixed point with the iteration function g (x ) = plog(x 2 + 2).
Are the convergence hypothesis for the fixed point and Newton methods satisfied? On a script called Esercizio2 do the following
plot (semilogy) the absolute errors showing the different
convergence orders of the methods (fix the tolerance as 1.e − 10).
Hint
It is reasonable to think that the slower one is bisection. Let us say that it
needs n iteration. Then, for nmax = 1, . . . , n evaluate the errors of the
different methods using as reference solution the one given by fzero.
Exercises
