i have a math project
WhatsApp Image 2021-02-21 at 12.59.26 AM.jpeg
5903312.pdf
Bisection Method
Steps for employing Bisection Method:
Theorem
An equation 0)( xf , where )(xf is a real continuous function, has at least one root between x
and u
x if 0)()( u
xfxf (See Figure 1).
Note that if 0)()( u
xfxf , there may or may not be any root between x and ux
(Figures 2 and 3). If 0)()( u
xfxf , then there may be more than one root between x and ux
(Figure 4). So the theorem only guarantees one root between x and ux .
Bisection method
Bisection Method
Since the method is based on finding the root between two points, the method falls under
the category of bracketing methods.
Since the root is bracketed between two points, x and ux , one can find the mid-point, mx
between x and ux . This gives us two new intervals
1. x and mx , and
2. m
x and u
x .
Figure 1 At least one root exists between the two points if the function is real, continuous, and
changes sign.
f (x)
xℓ xu
x
f (x)
xℓ xu x
Bisection Method
Figure 2 If the function )(xf does not change sign between the two points, roots of the
equation 0)( xf may still exist between the two points.
5903337.pdf
Finishing off the report:
1. when you have finished your coursework, you should read it through carefully to make sure
that you have included everything required and that it is all done correctly. You may find it
helps to print it out to do this.
2. Make sure you have numbered the pages!
3. Read through carefully for typos and to make sure that what you have written makes sense
and things are in the correct order. It’s easy to muddle things up when cutting and pasting a
lot. Make sure all the formulae have printed out correctly.
4. Make sure you have stated the equation in the form …… = 0 that you are trying to find a root
of, for every method (including in the failure cases)and again in the comparison.
5. You may refer to your function, e.g. f(x) = x3 – 3x + 1 but make sure you don’t call that an
equation!
6. Make sure that all your graphs are fully annotated:
i. Axes should be labelled.
ii. Curves should be labelled. (y = f(x) is fine provided it is clear in the text what your
f(x) is.)
iii. Positions of x0 to at least x2 should usually be labelled. (It may only be possible to
show x0 and x1 in the failure of g(x).)
iv. Tangents should be labelled.
7. You should have explained how each method works.
8. All roots found should be stated clearly: x = … with a maximum error of ±0.000005. For the
iterative methods, the x value has 5 d.p. but for decimal search it has 6 digits after the
decimal point, the last of which is a 5 (because you took a midpoint).
9. Make sure you have used correct subscripts on all the x’s in your iterative formulae.
10. Make sure that you marked your own work following the marking criteria guidelines.
5903335.pdf
Advanced Pure Maths Group Project Marking Criteria The Task: Students will investigate the solution of equations using the following three methods:
i. Systematic search of sign using: decimal search bisection method.
ii. Fixed point iteration after rearranging the equation f(x )= 0 in the form x = g (x).
iii. Fixed point iteration using the Newton Raphson method.
Project title Date
Student’s Name Student’s Number
Marking Criteria: Total Mark: Section
Available Marks
Description Mark Awarded
Assessor comment
1. Change of sign method (7 marks).
3 The method is applied successfully to find one root of an equation.
2 Error bounds are stated and the method is illustrated graphically.
2 An example is given of an equation where one of the roots cannot be found by the chosen method. There is an illustrated example of why this is the case.
2. The iteration method Rearranging f(x) = 0 in the form x= g(x)
(9 marks).
3 A rearrangement is applied successfully to find a root of a second equation.
2 Convergence of this rearrangement to a root is demonstrated graphically and the magnitude of g’(x) is discussed.
2 A rearrangement of the same equation is applied in a situation where the iteration fails to converge to the required root.
2 This failure is demonstrated graphically and the magnitude of g’(x) is discussed.
3. Newton Raphson method
(11 marks).
3 The method is applied successfully to find all the roots of a third equation.
2 All roots are found.
2 The method is illustrated graphically for one root.
2 Error bounds are established for one of the roots.
2 An example is given of an equation where this method fails to find a particular root, despite a starting value close to it. There is an illustrated explanation why this has happened.
4. Comparison of methods
(7 marks).
3 One of the equations used above is selected and the other two methods are applied successfully to find the same root.
2 There is a sensible comparison of the relative merits of the three methods in terms of speed of convergence.
2 There is a sensible comparison of the relative merits of the three methods in terms of ease of use with available hardware and software.
5. Real life application of Numerical methods.
3 An understanding of the application of one numerical method in the real life. The student produced A4 page contains no more than 500 words. Good illustration of the application of the method is shown.
A: Written communication ------------------- B: Oral communication
3 Correct notation and terminology are used. Presentation □ Please tick at least one and
give a brief comment.
Interview □
Discussion □
5903314.pdf
Newton Raphson Method
Steps for employing Newton Raphson Method
The steps of the Newton-Raphson method to find the root of an equation 0xf are
1. Evaluate xf symbolically 2. Use an initial guess of the root,
i x , to estimate the new value of the root,
1i x , as
i
i ii
xf
xf = xx
1
3. Find the absolute relative approximate error a
as
010 1
1
i
ii
a x
xx =
4. Compare the absolute relative approximate error with the pre-specified relative error
tolerance, s
. If a
> s
, then go to Step 2, else stop the algorithm. Also, check if the
number of iterations has exceeded the maximum number of iterations allowed. If so, one needs to terminate the algorithm and notify the user.
Figure 1 Geometrical illustration of the Newton-Raphson method.
f (x)
f (xi)
f (xi+1)
xi+2 xi+1 xi x
θ
[xi, f (xi)]
5909591.pdf
Steps for employing the fixed point iteration method:
5903330.pdf
Applications of Mathematics to the modern world.
Learning objectives:
The learner will be able to write down written solutions to complex mathematical
problems, explaining their methods clearly using English. The learner will be able to write a range of mathematical proofs using clear and concise language.
The learner will have a detailed knowledge of the applications of mathematics to engineering, business and society and be able to convey this knowledge to a non- mathematician in a coherent and understandable way.
The learner will be able to use problem solving skills to break down and solve complicated problems, including those which are unstructured. The learner will appreciate that there can be more than one approach to solving a problem and will usually select the most efficient and effective method.
Important dates
• Topic explained WC 8/2/2021.
• Brief of project released WC 15/2/2021.
• Final report to be uploaded onto Turnitin 5.00pm Friday the 5th of March 2021.
Applications of Mathematics Numerical methods
The task Students will investigate the solution of equations using the
following three methods:
i. Systematic search of sign using: decimal search bisection method.
ii. Fixed point iteration after rearranging the equation f(x )= 0 in the form x = g (x).
iii. Fixed point iteration using the Newton Raphson method.
General Guidelines for the project
To solve equations using numerical methods.
A different equation must be used for each method.
You must investigate three different numerical methods and will be given 3 equations to do so.
You must show full calculations including steps, tabulated iterations, final root/s value/s and all relevant graph/s for each method.
You must show full calculations including where you demonstrate an example of each method failing.
When you compare the methods, it is how efficiently the calculations work that you are comparing, not how easy it was to draw the different illustrations on the program used.
It is important that you understand and use correctly the mathematical language associated with this work. Consequently, there is marks allocated specifically for correct notation and terminology.
In your project, each equation can be written f(x) = 0, where you define your f(x) each time.
General Guidelines for the project
In your project, each equation can be written f(x) = 0, where you define your f(x) each time. The roots of this are the x-values of the points where the curve y = f(x) cuts the x-axis. A common mistake is to call the equation y = f(x), or even just f(x), rather than f(x) = 0.
In your project you will fully solve an equation with the Newton-Raphson method finding all roots, but just find one root of an equation with the other two methods.
The total number of pages of the report should not exceed 5 pages of A4 using font size 12 (maximum 500 words per page excluding graphs and equations).
General Guidelines for the project
5903331.pdf
Applications of Mathematics to the modern world.
Learning objectives:
The learner will be able to write down written solutions to complex mathematical
problems, explaining their methods clearly using English. The learner will be able to write a range of mathematical proofs using clear and concise language.
The learner will have a detailed knowledge of the applications of mathematics to engineering, business and society and be able to convey this knowledge to a non- mathematician in a coherent and understandable way.
The learner will be able to use problem solving skills to break down and solve complicated problems, including those which are unstructured. The learner will appreciate that there can be more than one approach to solving a problem and will usually select the most efficient and effective method.
Important dates
• Topic explained WC 8/2/2021.
• Brief of project released WC 15/2/2021.
• Final report to be uploaded onto Turnitin 5.00pm Friday the 5th of March 2021.
1. Bisection Method
Description of the task
Systematic Search for a Change of Sign (Decimal Search) Bisection Method: Description of task:
1. State the equation you are trying to find a root of, which is f(x) = 0, where you define what your f(x) is. (There should be a different f(x) used for each method.)
2. Show the graph of y = f(x), indicating the root you are trying to find.
3. Describe how the method works, referring to your calculations and your zoomed- in graph illustrations.
i. Do this for the first row of calculations (with x values to 1 d.p.) with its corresponding zoomed-in image,
ii. Then for the second row and the second zoom. iii. You then paste in the final rows (up to x values with 5 d.p.).
4. You must tabulate your iterations showing the low value, high value , middle value and percentage error for each iteration.
5. Take the midpoint of the final interval. State the value of the root you have found: x = …… with a maximum error of ±0.000005.
6. You must work out and show the error bounds for the root.
7. This method will sometimes fail to find a root of an equation. An example of how this might happen must be included in your project report.
i. Repeat the steps 1. and 2. from above, but this time for an equation where the method fails to find the root.
ii. Describe why the method fails to work, referring to your calculations and your zoomed-in graph illustration.
iii. Do this for the first row of calculations (with x values to 1 d.p.) with its corresponding zoomed-in image.
2. Fixed Point Iteration, x = g(x) Method
Description of the task
Fixed Point Iteration, x = g(x) Method Description of task:
Fixed Point Iteration, x = g(x) Method Description of task:
3. Newton Raphson Method
3. Newton Raphson Method
Description of task 1. This is a method which involves using an iterative formula.
2. State the equation you are trying to solve, which is f(x) = 0, where you define what your f(x) is. (There should be a different f(x) used for each method.)
3. You must find all the roots using this method.
4. Show how you differentiated your f(x) to get f ’(x) to put into the Newton-Raphson iterative formula but with your f (𝑥𝑟 ) and f ’ (𝑥𝑟 ) substituted in the appropriate places.
5. Show a graph of your y = f(x), pointing out the roots that you are trying to find.
6. Show your calculations, and clearly state the integer near the root that you have chosen to be your 𝑥° values.
7. Show a zoomed-in graph showing the tangents used in this method (it looks like a zig-zag, or saw- tooth), with the first three x values labelled (𝑥° to 𝑥2).
8. Describe how the iterations are performed and the 𝑥𝑟 values converge to the root, referring to both your calculations table and your zoomed-in graph illustration.
9. Perform a change of sign check by looking at f(x) for x values 0.000005 above and below your root. Explain why you had to do this.
10. State that your root is x = …… with a maximum error of ±0.000005
11.Repeat steps 4, 7 and 8 for all the other roots. (You do not need to illustrate these, but you must show full calculations.)
12. Repeat steps 1. to 4. then explain why the iterative formula was not able to produce a value for x1.
13. Show a graph of your f(x) with a tangent drawn at (𝑥° (this should be parallel to the x-axis) and use this to illustrate graphically why the method has failed to locate the root in this case.
Newton Raphson Method Description of task:
5906258.pdf
Applications of Mathematics to the modern world.
Learning objectives:
The learner will be able to write down written solutions to complex mathematical
problems, explaining their methods clearly using English. The learner will be able to write a range of mathematical proofs using clear and concise language.
The learner will have a detailed knowledge of the applications of mathematics to engineering, business and society and be able to convey this knowledge to a non- mathematician in a coherent and understandable way.
The learner will be able to use problem solving skills to break down and solve complicated problems, including those which are unstructured. The learner will appreciate that there can be more than one approach to solving a problem and will usually select the most efficient and effective method.
Important dates
• Topic explained WC 8/2/2021.
• Brief of project released WC 15/2/2021.
• Final report to be uploaded onto Turnitin 5.00pm Friday the 5th of March 2021.
Applications of Mathematics Numerical methods
The task Students will investigate the solution of equations using the
following three methods:
i. Systematic search of sign using: decimal search bisection method.
ii. Fixed point iteration after rearranging the equation f(x )= 0 in the form x = g (x).
iii. Fixed point iteration using the Newton Raphson method.
Comparison of methods Description of task:
• Comparison of Methods: 1. State the equation you are trying to find a root of, which is f(x) = 0, where you
define what your f(x) is. This should be an equation you have already found a root of with one of the three methods.
2. Say which method you already used to find this root earlier and paste in your tables of calculations (including the change of sign check and your iterative formula if appropriate). State the root you found: x = …… with a maximum error of ±0.000005.
3. Find the same root with the other two methods, using the same 𝑥° starting integer for the two iterative methods and using this 𝑥° as the integer at one end of the first row of the decimal search tables.
4. Show all the tables you use and your iterative formula. For each method, state the root: x = …… with a maximum error of ±0.000005. They should all have the same error bounds (the Iterative Formulae will produce x values with 5 digits after the decimal point, the Decimal Search will produce an x value with 6 digits after the decimal point, the last of which is a 5 as you took a midpoint, but all three ways of finding the root should have the same error bounds).
5. Compare the three methods in terms of speed of convergence, that is, how quickly they found the root. You can make a direct comparison of the number of iterations for the two iterative methods, but the decimal search does not have iterations! 6. Compare the three methods in terms of ease of use with the available hardware and software . 7. You are required to give some detail and depth to your discussion, so you could give examples of some of the formulae you had to type into the software and how much you could make use of the click-and-drag copying tools for each method. 8. You are comparing how well the methods performed to find the root of your equation, but you may also write about other considerations you may have if you were asked to solve different types of equations, or if a different level of accuracy were required.
Comparison of methods Description of task:
5. Applications of numerical methods in real life
5. Applications of numerical methods in real life
Description of task:
• Carry out a research into the a real life application of on of the methods used in the project
• Explain the application giving a real life mathematical example.
• This should not exceed a one page (font size 12- about 500 words ).
Important dates
• Topic explained WC 8/2/2021.
• Brief of project released WC 15/2/2021.
• Final report to be uploaded onto Turnitin 5.00pm Friday the 5th of March 2021.
5855319.pdf
Numerical methods: Fixed point Iteration Method
Fixed-point iterations
• Learning objectives:
• Evaluate the location of roots.
• Apply the iteration method to obtain approximate solutions to mathematical
problems.
• Derive the iteration method for various mathematical operations and tasks,
2
Fixed-point iterations
N u m
e ri
c a l M
e th
o d
s F
P I
Fixed-Point Iteration---- Successive Approximation
Many problems also take on the specialised
form: g(x)=x, where we seek, x, that satisfies
this equation.
In the limit, f(xk)=0, hence xk+1=xk
f(x)=x
g(x)
N u m
e ri
c a l M
e th
o d
s F
P I
x xg
or
xxg
or
xxg
xxxxf
2 1)(
2)(
2)(
02)(
2
2
Example:
N u m
e ri
c a l M
e th
o d
s F
P I
Iterative Solution
1. Start with a guess say x1=1,
2. Generate
a) x2=e -x1
= e -1= 0.368
b) x3=e -x2= e-0.368 = 0.692
c) x4=e -x3= e-0.692=0.500
In general:
After a few more iteration we will get
nx
n ex
1
5670 5670
. .
e
Find the root of
f(x) = e-x – x
N u m
e ri
c a l M
e th
o d
s F
P I
Problem
Find a root near x=1.0 and x=2.0
Solution:
Starting at x=1, x=0.292893 at 15th iteration
Starting at x=2, it will not converge
Why? Relate to g'(x)=x. for convergence g'(x) < 1
Starting at x=1, x=1.707 at iteration 19
Starting at x=2, x=1.707 at iteration 12
Why? Relate to
142 2 xxxf
41 2
2 1 xxgx
212 xxgx
2 1
2 12
xxg
N u m
e ri
c a l M
e th
o d
s F
P I
Examples
N u m
e ri
c a l M
e th
o d
s F
P I
Fixed Point Iteration
The equation f(x) = 0, where f(x) = x3 7x + 3, may be re-arranged
to give x = (x3 + 3)/7.
-4
-3
-2
-1
0
1
2
3
4
-5 -4 -3 -2 -1 0 1 2 3 4 5
y
x
y = x
y = (x3 + 3)/7
Intersection of the graphs of y = x and y = (x3 + 3)/7 represent
roots of the original equation x3 7x + 3 = 0.
N u m
e ri
c a l M
e th
o d
s F
P I
The rearrangement x = (x3 + 3)/7 leads to the iteration
To find the middle root a, let initial approximation x0 = 2.
Fixed Point Iteration
The iteration slowly converges to give a = 0.441 (to 3 s.f.)
...,3,2,1,0, 7
3 3
1
n
x x n
n
57143.1 7
32
7
3 33
0 1
x
x
etc.
98292.0 7
357143.1
7
3 33
1 2
x
x
56423.0 7
398292.0
7
3 33
2 3
x
x
45423.0 7
356423.0
7
3 33
3 4
x
x
N u m
e ri
c a l M
e th
o d
s F
P I
The rearrangement x = (x3 + 3)/7 leads to the iteration
For x0 = 2 the iteration will converge on the middle root a, since g’(a)
< 1.
0
0.5
1
1.5
2
0 0.5 1 1.5 2
y
x
Fixed Point Iteration
n x n
0 2
1 1.57143
2 0.98292
3 0.56423
4 0.45423
5 0.44196
6 0.4409
7 0.44082
8 0.44081
a = 0.441 (to 3 s.f.)
a x0 x2 x1
...,3,2,1,0, 7
3 3
1
n
x x n
n
x3
y = (x3 + 3)/7
y = x
N u m
e ri
c a l M
e th
o d
s F
P I
Fixed Point Iteration - breakdown
The rearrangement x = (x3 + 3)/7 leads to the iteration
For x0 = 3 the iteration will diverge from the upper root a.
n x n
0 3
1 4.28571
2 11.6739
3 227.702
4 1686559
5 6.9E+17 0
2
4
6
8
10
0 2 4 6 8 10
y
x
The iteration diverges because g’(a) > 1.
a x0 x1
...,3,2,1,0, 7
3 3
1
n
x x n
n
N u m
e ri
c a l M
e th
o d
s F
P I
Example: fixed point problems
N u m
e ri
c a l M
e th
o d
s F
P I
Examples: FPI
N u m
e ri
c a l M
e th
o d
s F
P I
Example: FPI
N u m
e ri
c a l M
e th
o d
s F
P I
Convergence of Fixed-Point Iteration
N u m
e ri
c a l M
e th
o d
s F
P I
Simple Fixed-Point Iteration Convergence
Fixed-point iteration converges if :
( ) 1 (slope of the line ( ) )g x f x x
• When the method converges, the
error is roughly proportional to or less
than the error of the previous step,
therefore it is called “linearly
convergent.”
N u m
e ri
c a l M
e th
o d
s F
P I
Simple Fixed-Point Iteration-Convergence N
u m
e ri
c a l M
e th
o d
s F
P I
19
More on Convergence
Graphically the solution is at the
intersection of the two curves. We
identify the point on y2 corresponding
to the initial guess and the next guess
corresponds to the value of the
argument x where y1 (x) = y2 (x).
Convergence of the simple fixed-point
iteration method requires that the
derivative of g(x) near the root has a
magnitude less than 1.
a) Convergent, 0≤g’<1
b) Convergent, -1<g’≤0
c) Divergent, g’>1
d) Divergent, g’<-1
N u m
e ri
c a l M
e th
o d
s F
P I
Fixed Point Iteration
1. Use an initial guess x =1.5 and y =3.5
2. The iteration formulae:
xi+1=(10-xi 2)/yi and yi+1=57-3xiyi
2
3. First iteration,
x=(10-(1.5)2)/3.5=2.21429
y=(57-3(2.21429)(3.5)2=-24.37516
4. Second iteration:
x=(10-2.214292)/-24.37516=-0.209
y=57-3(-0.209)(-24.37516)2=429.709
5. Solution is diverging so try another iteration formula
N u m
e ri
c a l M
e th
o d
s F
P I
Summary
Method Pros Cons
Bisection - Easy, Reliable, Convergent - One function evaluation per iteration
- No knowledge of derivative is needed
- Slow
- Needs an interval [a,b] containing the root, i.e., f(a)f(b)<0
Newton - Fast (if near the root) - Two function evaluations per iteration
- May diverge
- Needs derivative and an initial guess x0 such that f’(x0) is nonzero
N u m
e ri
c a l M
e th
o d
s F
P I
5855320.pdf
Numerical methods: Newton- Raphson method.
Newton- Raphson method
• Learning objectives:
• Evaluate the location of roots.
• Apply the Newton- Raphson method to obtain approximate solutions to
mathematical problems.
• Derive the Newton- Raphson method for various mathematical operations
and tasks,
2
HIGH-DEGREE
POLYNOMIALS
For a quadratic equation ax2 + bx + c = 0, there
is a well-known formula for the roots.
For third- and fourth-degree equations,
there are also formulas for the roots.
However, they are extremely complicated. If f is a polynomial of
degree 5 or higher, there is
no such formula.
N u m
e ri
c a l M
e th
o d
s F
P I
Likewise, there is no formula that
will enable us to find the exact roots
of a transcendental equation such as
cos x = x.
TRANSCENDENTAL EQUATIONS
N u m
e ri
c a l M
e th
o d
s F
P I
We can find an approximate solution
by plotting the left side of the equation.
Using a graphing device, and after experimenting with
viewing rectangles, we produce the graph below.
APPROXIMATE SOLUTION
N u m
e ri
c a l M
e th
o d
s F
P I
We see that, in addition to the solution
x = 0, which doesn’t interest us, there is
a solution between 0.007 and 0.008
Zooming in shows
that the root is
approximately
0.0076
If we need more accuracy,
we could zoom in
repeatedly. That becomes
tiresome, though.
N u m
e ri
c a l M
e th
o d
s F
P I
A faster alternative is to use a numerical
rootfinder on a calculator or computer
algebra system.
If we do so, we find that the root, correct to
nine decimal places, is 0.007628603
How do those numerical rootfinders work?
They use a variety of methods.
Most, though, make some use of Newton- Raphson
method,
also called the Newton-Raphson method.
NUMERICAL ROOTFINDERS
N u m
e ri
c a l M
e th
o d
s F
P I
The geometry behind Newton- Raphson
method is shown here.
The root that we
are trying to find
is labeled r. N u m
e ri
c a l M
e th
o d
s F
P I
Newton- Raphson method:
We start with a first approximation x1,
which is obtained by one of the following
methods:
Guessing
A rough sketch
of the graph of f
A computer-
generated graph
of f
N u m
e ri
c a l M
e th
o d
s F
P I
Newton- Raphson method
Consider the tangent line L to the curve
y = f(x) at the point (x1,f(x1)) and look at
the x-intercept of L, labeled x2.
N u m
e ri
c a l M
e th
o d
s F
P I
Here’s the idea behind the method.
The tangent line is close to the curve.
So, its x-intercept, x2 , is close to the x-intercept
of the curve
(namely, the root r
that we are seeking).
As the tangent is
a line, we can easily
find its x-intercept.
N u m
e ri
c a l M
e th
o d
s F
P I
To find a formula for x2 in terms of x1,
we use the fact that the slope of L is f’(x1).
So, its equation is:
y - f(x1) = f’(x1)(x - x1)
N u m
e ri
c a l M
e th
o d
s F
P I
As the x-intercept of L is x2, we set y = 0
and obtain: 0 - f(x1) = f’(x1)(x2 - x1)
If f’(x1) ≠ 0, we can solve this equation for x2:
We use x2 as a second approximation to r.
SECOND APPROXIMATION
1 2 1
1
( )
'( )
f x x x
f x
N u m
e ri
c a l M
e th
o d
s F
P I
Next, we repeat this procedure with x1
replaced by x2, using the tangent line at
(x2,f(x2)).
This gives a third approximation:
3 2
2
2
( )
'( )
f x x x
f x
N u m
e ri
c a l M
e th
o d
s F
P I
Newton- Raphson method
If we keep repeating this process,
we obtain a sequence of approximations
x1, x2, x3, x4, . . .
SUCCESSIVE APPROXIMATIONS
N u m
e ri
c a l M
e th
o d
s F
P I
In general, if the nth approximation is xn
and f’(xn) ≠ 0, then the next approximation
is given by:
1
( )
'( )
n n n
n
f x x x
f x
Equation/Formula 2 SUBSEQUENT APPROXIMATION
N u m
e ri
c a l M
e th
o d
s F
P I
If the numbers xn become closer and
closer to r as n becomes large, then
we say that the sequence converges to r
and we write: lim
n n
x r
CONVERGENCE
N u m
e ri
c a l M
e th
o d
s F
P I
The sequence of successive approximations
converges to the desired root for functions of
the type illustrated in the previous figure.
However, in certain circumstances, it may
not converge.
CONVERGENCE
N u m
e ri
c a l M
e th
o d
s F
P I
Consider the situation shown here.
You can see that x2 is a worse approximation
than x1.
This is likely to be
the case when
f’(x1) is close to 0.
NON-CONVERGENCE
N u m
e ri
c a l M
e th
o d
s F
P I
It might even happen that an approximation
falls outside the domain of f, such as x3.
Then, Newton- Raphson method fails.
In that case,
a better initial
approximation x1
should be chosen.
NON-CONVERGENCE
N u m
e ri
c a l M
e th
o d
s F
P I
Starting with x1 = 2, find the third
approximation x3 to the root of
the equation
x3 – 2x – 5 = 0
Example 1
N u m
e ri
c a l M
e th
o d
s F
P I
We apply Newton- Raphson method with
f(x) = x3 – 2x – 5 and f’(x) = 3x2 – 2
Newton himself used this equation to illustrate
his method.
He chose x1 = 2 after some experimentation
because f(1) = -6, f(2) = -1 and f(3) = 16
Example 1
N u m
e ri
c a l M
e th
o d
s F
P I
Equation 2 becomes:
3
2
2 5 1
3 2
n n n n
n
x x x x
x
Example 1 N
u m
e ri
c a l M
e th
o d
s F
P I
With n = 1, we have:
Example 1
3
1 1 2 1 2
1
3
2
2 5
3 2
2 2(2) 5 2
3(2) 2
2.1
x x x x
x
N u m
e ri
c a l M
e th
o d
s F
P I
With n = 2, we obtain:
It turns out that this third approximation x3 ≈ 2.0946
is accurate to four decimal places.
Newton- Raphson METHOD Example 1
3
2 2 3 2 2
2
3
2
2 5
3 2
2.1 2(2.1) 5 2.1
3(2.1) 2
2.0946
x x x x
x
N u m
e ri
c a l M
e th
o d
s F
P I
The figure shows the geometry behind the
first step in Newton- Raphson method in the example.
As f’(2) = 10, the tangent line to y = x3 - 2x - 5 at (2, -1)
has equation
y = 10x – 21
So, its x-intercept
is x2 = 2.1
N u m
e ri
c a l M
e th
o d
s F
P I
Suppose that we want to achieve a given
accuracy—say, to eight decimal places—
using Newton- Raphson method.
How do we know when to stop? N u m
e ri
c a l M
e th
o d
s F
P I
The rule of thumb that is generally used is that
we can stop when successive approximations
xn and xn+1 agree to eight decimal places.
N u m
e ri
c a l M
e th
o d
s F
P I
Notice that the procedure in going from n to
n + 1 is the same for all values of n.
It is called an iterative process.
This means that the method is particularly convenient
for use with a programmable calculator or a computer.
ITERATIVE PROCESS
N u m
e ri
c a l M
e th
o d
s F
P I
Use Newton- Raphson method to find
correct to eight decimal places.
First, we observe that finding is equivalent to
finding the positive root of the equation x6 – 2 = 0
So, we take f(x) = x6 – 2
Then, f’(x) = 6x5
Example 2 Newton- Raphson METHOD
6 2
6 2
N u m
e ri
c a l M
e th
o d
s F
P I
So, Formula 2 (Newton- Raphson
method)
becomes:
6
1 5
2
6
n n n
n
x x x
x
Example 2
N u m
e ri
c a l M
e th
o d
s F
P I
Choosing x1 = 1 as the initial approximation,
we obtain:
As x5 and x6 agree to eight decimal places, we
conclude that to eight decimal places.
2
3
4
5
6
1.16666667
1.12644368
1.12249707
1.12246205
1.12246205
x
x
x
x
x
Example 2
6 2 1.12246205
N u m
e ri
c a l M
e th
o d
s F
P I
Find, correct to six decimal places,
the root of the equation cos x = x.
We rewrite the equation in standard form: cos x – x = 0
Therefore, we let f(x) = cos x – x
Then, f’(x) = –sinx – 1
Example 3 Newton- Raphson METHOD
N u m
e ri
c a l M
e th
o d
s F
P I
So, Formula 2 becomes:
1
cos
sin 1
cos
sin 1
n n n n
n
n n n
n
x x x x
x
x x x
x
Example 3
N u m
e ri
c a l M
e th
o d
s F
P I
To guess a suitable value for x1, we sketch
the graphs of y = cos x and y = x.
It appears they intersect at a point whose x-coordinate
is somewhat less than 1.
Example 3
N u m
e ri
c a l M
e th
o d
s F
P I
So, let’s take x1 = 1 as a convenient first
approximation.
Then, remembering to put our calculator
in radian mode, we get:
As x4 and x5 agree to six decimal places (eight, in fact),
we conclude that the root of the equation, correct to
six decimal places, is 0.739085
2
3
4
5
0.75036387
0.73911289
0.73908513
0.73908513
x
x
x
x
Example 3
N u m
e ri
c a l M
e th
o d
s F
P I
Instead of using this rough sketch to get
a starting approximation for the method in
the example, we could have used the more
accurate graph that a calculator or computer
provides.
Newton- Raphson METHOD
N u m
e ri
c a l M
e th
o d
s F
P I
This figure suggests that we use
x1 = 0.75 as the initial approximation.
N u m
e ri
c a l M
e th
o d
s F
P I
Then, Newton- Raphson method gives:
So we obtain the same answer as before—but
with one fewer step.
2
3
4
0.73911114
0.73908513
0.73908513
x
x
x
N u m
e ri
c a l M
e th
o d
s F
P I
If only one or two decimal places of accuracy
are required, then indeed the method is
inappropriate and a graphing device suffices.
However, if six or eight decimal places
are required, then repeated zooming
becomes tiresome.
Newton- Raphson
VS.
GRAPHING DEVICES
N u m
e ri
c a l M
e th
o d
s F
P I
It is usually faster and more efficient
to use a computer and the method in
tandem.
You start with the graphing device and finish
with the method.
N u m
e ri
c a l M
e th
o d
s F
P I
Newton- Raphson
VS.
GRAPHING DEVICES
5855969.pdf
The Bisection Method
The Bisection Method
• Learning objectives:
• Evaluate the location of roots.
• Apply the bisection method to obtain approximate solutions to mathematical
problems.
• Derive the bisection method for various mathematical operations and tasks,
2
Why do we need numerical methods?
or there’s no ‘algebraic’ expression at all! (involving roots, logs, sin, cos, etc.)
Exact solution not expressible ?
?
Root
?
Slide 4
Why a numerical method ? An equation f(x) = 0, where f(x) = x3 - 7x + 3, has 3 real roots, but there is no simple analytical method of finding them.
The table and graph suggest first approximations to the roots of the equation x3 - 7x + 3 = 0.
x f(x )
-4 -33
-3 -3
-2 9
-1 9
0 3
1 -3
2 -3
3 9
4 39
-30
-20
-10
0
10
20
30
-4 -3 -2 -1 0 1 2 3 4
f( x
)
x
Graph of y = x^3 - 7x + 3
The lower root lies in the interval -3 < x < - 2
The middle root lies in the interval 0 < x < 1
The upper root lies in the interval 2 < x < 3
Slide 5
Change of Sign - Decimal Search To find the upper root a of f(x) = 0, where f(x) = x3 - 7x + 3. Tabulate f(x) for 2 < x < 3, in steps of 0.1:
x f(x )
2 -3
2.1 -2.439
2.2 -1.752
2.3 -0.933
2.4 0.024
2.5 1.125
2.6 2.376
2.7 3.783
2.8 5.352
2.9 7.089
3 9
-6
-4
-2
0
2
4
6
8
10
2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 3.0
f( x
)
x
Graph of y = x^3 - 7x + 3
Upper root a lies in the interval 2.3 < x < 2.4
Slide 6
To find the upper root a of f(x) = 0, where f(x) = x3 - 7x + 3. Tabulate f(x) for 2.39 < x < 2.40, in steps of 0.001:
Upper root a lies in the interval 2.397 < x < 2.398
x f(x )
2.390 -0.07808
2.391 -0.06794
2.392 -0.05778
2.393 -0.04761
2.394 -0.03742
2.395 -0.02722
2.396 -0.017
2.397 -0.00678
2.398 0.003469
2.399 0.013727
2.400 0.024
Graph of y = x ^3 - 7x + 3
-0.1
-0.08
-0.06
-0.04
-0.02
0
0.02
0.04
2.390 2.391 2.392 2.393 2.394 2.395 2.396 2.397 2.398 2.399 2.400
x
f( x
)
Change of Sign - Decimal Search
Slide 7
Since we now know that the upper root a lies in the interval
2.397 < x < 2.398
we have obtained the upper root correct to 3 s.f., a = 2.40
There is a change of sign over the interval since
f(2.397) = -0.00678 and f(2.398) = 0.00347
hence 2.397 and 2.398 act as error bounds
for the upper root a for 3 s.f. accuracy
Change of Sign - Decimal Search
Slide 8
Decimal search - repeated roots - no change of sign Sometimes the method of decimal search fails to find a root because there is no change of sign either side of the root.
Consider finding the upper (repeated) root of f(x) = 0, where f(x) = x4 - 4x3 - 4x2 + 16x + 16.
x f(x )
-3 121
-2 16
-1 1
0 16
1 25
2 16
3 1
4 16
5 121
Graph of y = x^4 - 4x^3 - 4x^2 + 16x + 16
-10
0
10
20
30
40
50
-3 -2 -1 0 1 2 3 4 5
x
f( x
)
The upper root lies in the interval 3 < x < 4
Slide 9
Decimal search - repeated roots - no change of sign From the graph the positive root satisfies 3 < x < 4, but a closer look reveals no change of sign.
x f(x )
3 1
3.1 0.3481
3.2 0.0256
3.3 0.0841
3.4 0.5776
3.5 1.5625
3.6 3.0976
3.7 5.2441
3.8 8.0656
3.9 11.628
4 16
Graph of y = x^4 - 4x^3 - 4x^2 + 16x + 16
-4
-2
0
2
4
6
8
10
12
3 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 4
x
f( x
)
The change of sign method has broken down
Topic Overview
1:: Locating Roots
In your previous studies you should have covered ‘iteration’, which allowed you to find successfully better approximations to the solutions of an equation. We’ll revisit this, but also see a more powerful method for approximating solutions.
3:: The Newton-Raphson Method
Proving a solution lies in a range (change of sign method)
Bro Exam Tip: In the mark scheme they’re looking for: 1. Finding the
function output for the two values.
2. Referring to a ‘change in sign’.
?
…but only if the function is continuous
Carlos says:
A function is continuous if the line does not ‘jump’. A root is only guaranteed with a sign change if the function is continuous, as otherwise the line can skip past 0 (in this case due to a vertical asymptote.
Why is Carlos wrong?
…and no sign change doesn’t mean there isn’t a root
Beware! Just because there isn’t a sign change, doesn’t mean there’s no root in that interval.
root root
The sign change method fails to detect a root if there were an even number of roots in that interval.
• Bisection Method:
• Bisection Method = a numerical method in
Mathematics to find a root of a given function
N u m
e ri
c a l M
e th
o d
s F
P I
The Bisection Method
• The Bisection Method is a successive approximation method
that narrows down an interval that contains a root of the
function f(x)
• The Bisection Method is given an initial interval [a..b] that
contains a root (We can use the property sign of f(a) ≠ sign of
f(b) to find such an initial interval)
• The Bisection Method will cut the interval into 2 halves and
check which half interval contains a root of the function
• The Bisection Method will keep cut the interval in halves until
the resulting interval is extremely small
The root is then approximately equal to any value in the final
(very small) interval.
N u m
e ri
c a l M
e th
o d
s F
P I
Bisection Method
• Based on the fact that the function will
change signs as it passes thru the root. • f(a)*f(b) < 0
• Once we have a root bracketed, we simply
evaluate the mid-point and halve the
interval.
N u m
e ri
c a l M
e th
o d
s F
P I
The Bisection Method (cont.)
• In the above example, we have changed the end point b to
obtain a smaller interval that still contains a root
In other cases, we may need to changed the end point b to
obtain a smaller interval that still contains a root
N u m
e ri
c a l M
e th
o d
s F
P I
Bisection Method
• c=(a+b)/2
a b c
f(a)>0
f(b)<0
f(c)>0
N u m
e ri
c a l M
e th
o d
s F
P I
Bisection Method
• Guaranteed to converge to a root if one
exists within the bracket.
c b a
a = c
f(a)>0
f(b)<0 f(c)<0
N u m
e ri
c a l M
e th
o d
s F
P I
You can solve equations of the form f(x)
= 0 using interval bisection
Use Interval Bisection to find √11 to 1
decimal place
Set this up as an equation:
2A
𝑥 = 11
𝑥2 = 11
𝑥2 − 11 = 0
Square
both sides
Subtract 11
𝑓 𝑥 = 𝑥2 − 11
𝑓 3 = (3)2 − 11
= −2
𝑓 4 = (4)2 − 11
= 5
Sub in integers
until we find a
change of sign
Numerical solutions of equations
You can solve equations of the form f(x)
= 0 using interval bisection
Use Interval Bisection to find √11 to 1
decimal place
So a solution lies between 3 and 4.
Now we set up a table, subbing these 2
values into f(x), as well as the midpoint
of these
When you have found the midpoint and
substituted it in, choose the positive
and negative answers closest to 0
The answer will be between these. Now
repeat the process for these 2 numbers
2A
𝑓 𝑥 = 𝑥2 − 11
𝒇 𝒂 + 𝒃
𝟐
𝒂 + 𝒃
𝟐 𝒂 𝒃 𝒇(𝒂) 𝒇(𝒃)
3 4 3.5 −2 5 1.25
𝑓 𝑥 = 𝑥2 − 11
3 3.5 1.25 −2 3.25 −0.438
3.25 −0.438 3.5 1.25 3.375 0.391
3.25 −0.438 3.375 0.391 3.3125 −0.027
3.3125 −0.027 3.375 0.391 3.34375 0.181
Our answer must be between 3.3125 and 3.34375
To one decimal place, the answer therefore must
be 3.3!
You can solve equations of the form f(x)
= 0 using interval bisection
Show that a root of the equation:
lies between 0 and 1
Use interval bisection 4 times to find an
approximation for this root
2A
𝑥3 − 5𝑥 + 3 = 0
𝑓 𝑥 = 𝑥3 − 5𝑥 + 3
𝑓 0 = (0)3 − 5(0) + 3
= 3
𝑓 1 = (1)3 − 5(1) + 3
= −1
Sub in 0 and 1 to
show the sign of the
answer changes
As the sign has changed, a solution must
lie between 0 and 1…
You can solve equations of the form f(x)
= 0 using interval bisection
Show that a root of the equation:
lies between 0 and 1
Use interval bisection 4 times to find an
approximation for this root
2A
𝑥3 − 5𝑥 + 3 = 0
𝒇 𝒂 + 𝒃
𝟐
𝒂 + 𝒃
𝟐 𝒂 𝒃 𝒇(𝒂) 𝒇(𝒃)
0 1 0.5 3 −1 0.625
𝑓 𝑥 = 𝑥3 − 5𝑥 + 3
0.5 0.625 1 −1 0.75 −0.328
0.75 −0.328 0.5 0.625 0.625 0.119
0.625 0.119 0.75 −0.328 0.6875 −0.113
Our approximation is the final bisection
0.6875 (or round if necessary)