Zeros of functions with Matlab: Bisection and Newton methods
Zeros of functions with Matlab: Bisection and Newton methods
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: Bisection and Newton methods Remarks
Introduction
Finding the zeros of a function means finding:
¯
x : f (¯ x ) = 0.
In the lecture we will see two approaches:
1
bisection method,
2
Newton’s method.
The first one is the simplest approach. It divides iteratively the searching interval into two subsets with respect to the midpoint.
The second one is the faster one provided that we take an initial
condition close to the zero.
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 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.
Zeros of functions with Matlab: Bisection and Newton methods Remarks
Newton
Theorem (Convergence of Newton’s method)
Let f (x ) ∈ C 2 ([a, b]). Suppose f (¯ x ) = 0 and f
0(¯ 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.
Matlab
Built-in routines: roots, fzero and fsolve.
1
roots computes the zeros (also complex ones) of polynomials. Call it as roots(a), with a the vector of the polynomial coefficients from the coefficient of higher order to that of the constant term.
2
fzero can be called in the following way: x=fzero(fun,x0,opt) with fun specified using the symbol @. For example,
f = @(x,c) sin(xˆ3/c); x0 =2; sol = fzero(f,x0,[],9),
here 9 is the value of the parameter c and [] is for the options.
3
fsolve is more general since it works on systems of non linear equations. A typical call is x = fsolve(fun,x0) where fun can be specified using @. For example,
x = fsolve(@myfun,[2 3 4]),
where myfun is a Matlab function such as:
function F = myfun(x)
F = sin(x);
Zeros of functions with Matlab: Bisection and Newton methods Exercises
Exercise 1
Exercise
Write two Matlab functions called bisection and newton for computing the zeros of functions with the bisection and Newton methods.
Hint
Use an exit criterion in case the methods do not converge.
For the bisection method the inputs that we need are f,a,b,tol,maxiter.
Fix the stopping criterion for the bisection as abs(f(c))<tol, where c is the midpoint of the k-th interval.
The inputs that we need for Newton are f,fp,x0,tol,maxiter.
Fix the stopping criterion as abs(f(x0))<tol, where x0 is the k-th
approximation.
Exercises