Idea Transcript
Numerical Methods – Lecture 3 Nonlinear Equations
by Pavel Ludvík
Introduction
Definition (Root or zero of a function) A root (or a zero) of a function f is a solution of an equation f (x) = 0. We learn several root-finding methods: the bisection method, false position, the secant method, the Newton–Raphson method.
Numerical Methods – Lecture 3
by Pavel Ludvík
2 / 24
Introduction
Definition (Root or zero of a function) A root (or a zero) of a function f is a solution of an equation f (x) = 0. We learn several root-finding methods: the bisection method, false position, the secant method, the Newton–Raphson method.
Numerical Methods – Lecture 3
by Pavel Ludvík
2 / 24
Introduction General Root-Finding Strategy 1.
Bracket the roots, i.e. find the disjoint intervals containing the individual roots.
2.
Set the initial approximation(s).
3.
Repeat applying the iterative formula until the stopping criterion is met.
Numerical Methods – Lecture 3
by Pavel Ludvík
3 / 24
Introduction General Root-Finding Strategy 1.
Bracket the roots, i.e. find the disjoint intervals containing the individual roots.
2.
Set the initial approximation(s).
3.
Repeat applying the iterative formula until the stopping criterion is met.
Differences Between Methods the number of starting values, the guarantee, or otherwise, of convergence, the speed of convergence, the cost, in terms of the work to be done per iteration.
Numerical Methods – Lecture 3
by Pavel Ludvík
3 / 24
Bisection Method - Description
The bisection method is the simplest of all the methods for finding a root of a nonlinear equation. We start with an interval containing a root and divide it into a left and a right half.We decide which of the two halves contains a root and proceed with a further division of that half. We do this repeatedly until the interval containing a root is sufficiently narrowed down to meet the level of accuracy required. If we take the mid-point of the latest interval to be an approximation to a root, we can say that this is accurate to within ± half the width of the interval.
Numerical Methods – Lecture 3
by Pavel Ludvík
4 / 24
Bisection Method - Algorithm Theorem Let f be a continuous function on an interval [a, b] and f (a)f (b) < 0. Then there exists a number c ∈ (a, b) that f (c) = 0. Algorithm for solving f (x) = 0 by Bisection Method 1.
Find an interval [a, b] in which f (x) = 0.
2.
Set x∗ to
3.
Test for convergence: Find out if
4.
Calculate f (x∗ ).
5.
If f (x∗ ) and f (b) have opposite sign set a to x∗ , otherwise set b to x∗ .
6.
Repeat from step 2.
a+b 2 . b−a 2
6 ε.
Numerical Methods – Lecture 3
by Pavel Ludvík
5 / 24
Example Find a root of the equation 8 − 4.5(x − sin x) = 0 with a tolerance less than ε = 0.01. Solution 1.
2.
3.
We define a function f (x) = 8 − 4.5(x − sin x), plot its graph and find out the solution is between x = 2 and x = 3. Hence we choose a0 = 2 and b0 = 3. 0 = 2.5 and the current We compute the midpoint c0 = a0 +b 2 b0 −a0 error value Error0 = 2 = 0.5 which is bigger than the tolerance 0.01.
We have to carry out a next step. We need to answer the question: "Is the root in the interval [a0 , c0 ] = [2, 2.5] or [c0 , b0 ] = [2.5, 3]?"If f (2)f (2.5) < 0 then the root is in [2, 2.5], if f (2.5)f (3) < 0 then in [2.5, 3], if none of it is truth then necessarily 2.5 is a root itself. We compute that f (2)f (2.5) < 0 and hence we set a1 = 2, b1 = 2.5. Numerical Methods – Lecture 3
by Pavel Ludvík
6 / 24
Solution 4.
We repeat the algorithm until the error is smaller or equal to ε.
5.
See the results in a table: n 0 1 2 3 4 5 6
6.
an 2 2 2.25 2.375 2.375 2.40625 2.421875
cn 2.5 2.25 2.375 2.4375 2.40625 2.421875 2.429688
bn 3 2.5 2.5 2.5 2.4375 2.4375 2.4375
Error 0.5 > 0.01 0.25 > 0.01 0.125 > 0.01 0.0625 > 0.01 0.03125 > 0.01 0.015625 > 0.01 0.007813 6 0.01
The conclusion is: Root = 2.429688 ± 0.01 Numerical Methods – Lecture 3
by Pavel Ludvík
7 / 24
Bisection Method - Matlab
Exercise A Write an M-File for one step of the Bisection Method. Input: Function f and limitpoints of an interval [an , bn ]. Output: Limitpoints of an interval [an+1 , bn+1 ]. Exercise B Create an M-File for the Bisection Method. The program should stop before doing 24 iterations.
Numerical Methods – Lecture 3
by Pavel Ludvík
8 / 24
Answers
Answer A
p = (a+b)/2; if f(a)*f(p) ε 0.00002549598350 6 ε
The conclusion is: Root = 2.4305 ± 10−4 Numerical Methods – Lecture 3
by Pavel Ludvík
15 / 24
The Secant Method – Matlab
f = ; % the function formula epsilon = ; % the precision maxn = ; % limitation on the number of steps x(1) = ; x(2) = ; % initial approximation for n = 3 : maxn x(n) = x(n-1) - f(x(n-1))*(x(n-1)-x(n-2))/(f(x( n-1))-f(x(n-2))); if abs(x(n)-x(n-1)) ε 0.054185 > ε 0.000521 > ε 0.000000 6 ε
The conclusion is: Root = 2.43046574172363 ± 10−6
Numerical Methods – Lecture 3
by Pavel Ludvík
22 / 24
The Newton-Raphson Method – Matlab
f = @(x) ; % the function formula %%%%%%%%%%%%% SYMBOLIC TOOLBOX REQUIRED syms x ; % creating the symbolic variable ’x’ symdf = diff(f(x)); % the derivative df = matlabFunction(symdf); % conversion %%%%%%%%%%%%%OTHERWISE COMPUTE DERIVATIVE MANUALLY epsilon = ; % the precision maxn = ; % limitation on the number of steps clear x; x(1) = ; % clearing ’x’ as a symbolic variable; setting initial approximation for n = 2 : maxn x(n) = x(n-1) - f(x(n-1))/df(x(n-1)); if abs(x(n)-x(n-1))