CHILD ABUSE, CHILDHOOD & HISTORY
4 star(s)
Change of sign method --- interval bisection method
Extracts from this document...
Introduction
Winnie Zheng
Pure Mathematics 2 Coursework
Change of sign method --- interval bisection method
Introduction:
When I am looking for the roots of the equation, actually what I want is the values of x for which the graph y=f(x) crosses the x-axis. As the graph f(x) crosses the x-axis, there is going to be a sign change of y value on the two sides of the root. Hence provided the function gives a continuous graph, if there is a sign change in a located interval, I will know that the interval contains one root.
For interval bisection method, what I am actually going to do is to divide the interval into two parts, then take the half which contains sign changes of y.
Y=(x-2)(x-4)(x-6)+1
From the graph we can see that there are three roots lying in the interval (1,2); (4,5); (5,6). I am going to focus on the root lying in the interval (1,2)
I will show the steps on a spreadsheet:
a | b | (a+b)/2 | f(x) | error | |
1 | 1.00000000 | 2.00000000 | 1.50000000 | -4.62500000 | 0.50000000 |
2 | 1.50000000 | 2.00000000 | 1.75000000 | -1.39062500 | 0.25000000 |
3 | 1.75000000 | 2.00000000 | 1.87500000 | -0.09570313 | 0.12500000 |
4 | 1.87500000 | 2.00000000 | 1.93750000 | 0.47631836 | 0.06250000 |
5 | 1.87500000 | 1.93750000 | 1.90625000 | 0.19644165 | 0.03125000 |
6 | 1.87500000 | 1.90625000 | 1.89062500 | 0.05191422 | 0.01562500 |
7 | 1.87500000 | 1.89062500 | 1.88281250 | -0.02150679 | 0.00781250 |
8 | 1.88281250 | 1.89062500 | 1.88671875 | 0.01530045 | 0.00390625 |
9 | 1.88281250 | 1.88671875 | 1.88476563 | -0.00307896 | 0.00195313 |
10 | 1.88476563 | 1.88671875 | 1.88574219 | 0.00611680 | 0.00097656 |
11 | 1.88476563 | 1.88574219 | 1.88525391 | 0.00152043 | 0.00048828 |
12 | 1.88476563 | 1.88525391 | 1.88500977 | -0.00077889 | 0.00024414 |
13 | 1.88500977 | 1.88525391 | 1.88513184 | 0.00037087 | 0.00012207 |
14 | 1.88500977 | 1.88513184 | 1.88507080 | -0.00020399 | 0.00006104 |
15 | 1.88507080 | 1.88513184 | 1.88510132 | 0.00008345 | 0.00003052 |
16 | 1.88507080 | 1.88510132 | 1.88508606 | -0.00006027 | 0.00001526 |
17 | 1.88508606 | 1.88510132 | 1.88509369 | 0.00001159 | 0.00000763 |
18 | 1.88508606 | 1.88509369 | 1.88508987 | -0.00002434 | 0.00000381 |
The formulae I used in the spreadsheet are shown below:
a | b | (a+b)/2 | f(x) | error | |
1 | 1 | 2 | =1/2*(B2+C2) | =(D2-2)*(D2-4)*(D2-6)+1 | =1/2*(C2-B2) |
2 | =IF(E2<0,D2,B2) | =IF(E2<0,C2,D2) | =1/2*(B3+C3) | =(D3-2)*(D3-4)*(D3-6)+1 | =1/2*(C3-B3) |
3 | =IF(E3<0,D3,B3) | =IF(E3<0,C3,D3) | =1/2*(B4+C4) | =(D4-2)*(D4-4)*(D4-6)+1 | =1/2*(C4-B4) |
4 | =IF(E4<0,D4,B4) | =IF(E4<0,C4,D4) | =1/2*(B5+C5) | =(D5-2)*(D5-4)*(D5-6)+1 | =1/2*(C5-B5) |
5 | =IF(E5<0,D5,B5) | =IF(E5<0,C5,D5) | =1/2*(B6+C6) | =(D6-2)*(D6-4)*(D6-6)+1 | =1/2*(C6-B6) |
6 | =IF(E6<0,D6,B6) | =IF(E6<0,C6,D6) | =1/2*(B7+C7) | =(D7-2)*(D7-4)*(D7-6)+1 | =1/2*(C7-B7) |
7 | =IF(E7<0,D7,B7) | =IF(E7<0,C7,D7) | =1/2*(B8+C8) | =(D8-2)*(D8-4)*(D8-6)+1 | =1/2*(C8-B8) |
8 | =IF(E8<0,D8,B8) | =IF(E8<0,C8,D8) | =1/2*(B9+C9) | =(D9-2)*(D9-4)*(D9-6)+1 | =1/2*(C9-B9) |
9 | =IF(E9<0,D9,B9) | =IF(E9<0,C9,D9) | =1/2*(B10+C10) | =(D10-2)*(D10-4)*(D10-6)+1 | =1/2*(C10-B10) |
10 | =IF(E10<0,D10,B10) | =IF(E10<0,C10,D10) | =1/2*(B11+C11) | =(D11-2)*(D11-4)*(D11-6)+1 | =1/2*(C11-B11) |
11 | =IF(E11<0,D11,B11) | =IF(E11<0,C11,D11) | =1/2*(B12+C12) | =(D12-2)*(D12-4)*(D12-6)+1 | =1/2*(C12-B12) |
12 | =IF(E12<0,D12,B12) | =IF(E12<0,C12,D12) | =1/2*(B13+C13) | =(D13-2)*(D13-4)*(D13-6)+1 | =1/2*(C13-B13) |
13 | =IF(E13<0,D13,B13) | =IF(E13<0,C13,D13) | =1/2*(B14+C14) | =(D14-2)*(D14-4)*(D14-6)+1 | =1/2*(C14-B14) |
14 | =IF(E14<0,D14,B14) | =IF(E14<0,C14,D14) | =1/2*(B15+C15) | =(D15-2)*(D15-4)*(D15-6)+1 | =1/2*(C15-B15) |
15 | =IF(E15<0,D15,B15) | =IF(E15<0,C15,D15) | =1/2*(B16+C16) | =(D16-2)*(D16-4)*(D16-6)+1 | =1/2*(C16-B16) |
16 | =IF(E16<0,D16,B16) | =IF(E16<0,C16,D16) | =1/2*(B17+C17) | =(D17-2)*(D17-4)*(D17-6)+1 | =1/2*(C17-B17) |
17 | =IF(E17<0,D17,B17) | =IF(E17<0,C17,D17) | =1/2*(B18+C18) | =(D18-2)*(D18-4)*(D18-6)+1 | =1/2*(C18-B18) |
18 | =IF(E18<0,D18,B18) | =IF(E18<0,C18,D18) | =1/2*(B19+C19) | =(D19-2)*(D19-4)*(D19-6)+1 | =1/2*(C19-B19) |
Middle
0.000000
-11.937282
-0.916521
0.000000
-11.937282
The formula I used in the spreadsheet are shown below:
x | f(x) | f'(x) |
-1 | =3*(B3-1)*(B3+1)*(B3+3)+1 | =9*B3^2+18*B3-3 |
=B3-C3/D3 | =3*(B4-1)*(B4+1)*(B4+3)+1 | =9*B4^2+18*B4-3 |
=B4-C4/D4 | =3*(B5-1)*(B5+1)*(B5+3)+1 | =9*B5^2+18*B5-3 |
=B5-C5/D5 | =3*(B6-1)*(B6+1)*(B6+3)+1 | =9*B6^2+18*B6-3 |
From the results I get from the spreadsheet, I can see the root lying between the interval (-1,0) is -0.916521.
2) For the root lying between the interval (0,1):
x | f(x) | f'(x) |
1.000000 | 1.000000 | 24.000000 |
0.958333 | 0.031033 | 22.515625 |
0.956955 | 0.000033 | 22.467057 |
0.956954 | 0.000000 | 22.467005 |
The formula I used in the spread sheet are shown below:
x | f(x) | f'(x) |
1 | =3*(B3-1)*(B3+1)*(B3+3)+1 | =9*B3^2+18*B3-3 |
=B3-C3/D3 | =3*(B4-1)*(B4+1)*(B4+3)+1 | =9*B4^2+18*B4-3 |
=B4-C4/D4 | =3*(B5-1)*(B5+1)*(B5+3)+1 | =9*B5^2+18*B5-3 |
=B5-C5/D5 | =3*(B6-1)*(B6+1)*(B6+3)+1 | =9*B6^2+18*B6-3 |
From the results I get from the spreadsheet, I can see the root lying between the interval (0,1) is 0.956954.
Problems with Newton-Raphson method:
There are some cases in which the Newton-Raphson method does not work:
- The function is discontinuous, for example:
y=-1/x +2
If the graph is discontinuous, and unfortunately I’ve chosen a starting point near the edge of one part of the graph, using the Newton-Raphson method, the next guess will go to the other side of the graph, getting further and further away from the root we are looking for.
2) Poor choice of starting value. If my initial value is quite far way from a root, the iteration may be divergent, i.e. moving away from the root. For example:
y= x(x-1)(x-2)+1
Using Newton-Raphson method with the first guess x=0.5, from the graph below we can see that actually our second guess is getting further away from the chosen root, so this method failed.
- if my initial value is near a turning point of y=f(x), the iteration will diverge as well. For example:
y=(x-2)(x-1)x+1
For this equation, there is a station point of maximum at around x=0.5; if my first guess is 0.4 then the gradient of the tangent at that point is actually nearly zero, i.e. horizontal to the x-axis, hence out next guess will be very far from out first guess and the root we are looking for. If out first guess is actually at the turning point, the tangent will be horizontal to the x-axis, it will never cut the x-axis by any chance. In both of the cases, the Newton-Raphson method fails.
Rearranging f(x)=0 in the form x=g(x)
Introduction:
This method is actually finding a single value or point of an estimate value of the root rather than identifying the interval in which the root lies.
The method involves rearranging the function f(x)=0 in the form x=g(x). Drawing the graphs y=x and y=g(x) on the same graph:
The root of the function f(x)=0 is indeed the intersection of the two lines.
The iteration I am going to use in this method is actually based on:
xn+1=g(xn)
Presenting the iteration graphically, we will have either a ‘staircase’ or a ‘cobweb’ diagram.
For the equation: f(x)=y=x³+6x²+9x+1
rearrange f(x)=0, I get x=-(x³+6x²+1)/9
drawing y=x and g(x)=y=-(x³+6x²+1)/9 on the same graph, I get the graph below:
By using the rearranging f(x)=0 into x=g(x) method, it provides the iterative formula xn+1=(-xn³-6xn²-1)/9. It is shown in the purple line in the graph below.
I chose x=-4 as my starting point, find the corresponding value of g(-4). Next, we take this value g(-4) as the next guess, this means that x2=g(-4) and move the point horizontally towards the right to the line y=x and find the value of g(x2), this process continues until both x and g(x) are the same value.
Showing the method on a spreadsheet:
n | x | g(x) |
1 | -4.0000000000 | -3.6666666667 |
2 | -3.6666666667 | -3.5967078189 |
3 | -3.5967078189 | -3.5655250877 |
4 | -3.5655250877 | -3.5499338288 |
5 | -3.5499338288 | -3.5417564282 |
6 | -3.5417564282 | -3.5373669161 |
7 | -3.5373669161 | -3.5349823162 |
8 | -3.5349823162 | -3.5336786021 |
9 | -3.5336786021 | -3.5329633716 |
10 | -3.5329633716 | -3.5325702506 |
11 | -3.5325702506 | -3.5323539521 |
12 | -3.5323539521 | -3.5322348755 |
13 | -3.5322348755 | -3.5321693010 |
14 | -3.5321693010 | -3.5321331835 |
15 | -3.5321331835 | -3.5321132887 |
16 | -3.5321132887 | -3.5321023293 |
17 | -3.5321023293 | -3.5320962919 |
18 | -3.5320962919 | -3.5320929660 |
18 | -3.5320929660 | -3.5320911338 |
The formula I used in the spreadsheet are as follows:
n | x | g(x) |
1 | -4 | =-(B2^3+6*B2^2+1)/9 |
2 | =C2 | =-(B3^3+6*B3^2+1)/9 |
3 | =C3 | =-(B4^3+6*B4^2+1)/9 |
4 | =C4 | =-(B5^3+6*B5^2+1)/9 |
5 | =C5 | =-(B6^3+6*B6^2+1)/9 |
6 | =C6 | =-(B7^3+6*B7^2+1)/9 |
7 | =C7 | =-(B8^3+6*B8^2+1)/9 |
8 | =C8 | =-(B9^3+6*B9^2+1)/9 |
9 | =C9 | =-(B10^3+6*B10^2+1)/9 |
10 | =C10 | =-(B11^3+6*B11^2+1)/9 |
11 | =C11 | =-(B12^3+6*B12^2+1)/9 |
12 | =C12 | =-(B13^3+6*B13^2+1)/9 |
13 | =C13 | =-(B14^3+6*B14^2+1)/9 |
14 | =C14 | =-(B15^3+6*B15^2+1)/9 |
15 | =C15 | =-(B16^3+6*B16^2+1)/9 |
16 | =C16 | =-(B17^3+6*B17^2+1)/9 |
17 | =C17 | =-(B18^3+6*B18^2+1)/9 |
18 | =C18 | =-(B19^3+6*B19^2+1)/9 |
18 | =C19 | =-(B20^3+6*B20^2+1)/9 |
Conclusion
=B5^3-12*B5^2+44*B5-47
=3*B5^2-24*B5+44
5
=B5-C5/D5
=B6^3-12*B6^2+44*B6-47
=3*B6^2-24*B6+44
6
=B6-C6/D6
=B7^3-12*B7^2+44*B7-47
=3*B7^2-24*B7+44
From the table I get the root of f(x)=0 is x=1.88509246
- using the rearranging f(x)=0 in the form x=g(x) method;
for this method, I am going to rearrange f(x) = x3-12x2+44x-47=0 in the form x=(-x3+12x2+47)/44, i.e. g(x)= (-x3+12x2+47)/44
draw y=x and y=g(x)= (-x3+12x2+47)/44 on the same graph, I get the following:
using the iteration xn+1=g(xn), doing on the spreadsheet with a starting point x=3 I got the following table:
n | x | g(x) |
1 | 3 | 2.909090909 |
2 | 2.909090909 | 2.816696264 |
3 | 2.816696264 | 2.724052084 |
4 | 2.724052084 | 2.632540869 |
5 | 2.632540869 | 2.543614417 |
6 | 2.543614417 | 2.458694812 |
7 | 2.458694812 | 2.379066113 |
8 | 2.379066113 | 2.305774054 |
9 | 2.305774054 | 2.23955144 |
10 | 2.23955144 | 2.180782149 |
11 | 2.180782149 | 2.129507776 |
12 | 2.129507776 | 2.085471395 |
13 | 2.085471395 | 2.048185863 |
14 | 2.048185863 | 2.017011601 |
15 | 2.017011601 | 1.991230661 |
16 | 1.991230661 | 1.970108315 |
17 | 1.970108315 | 1.952938344 |
18 | 1.952938344 | 1.939072123 |
19 | 1.939072123 | 1.927933996 |
20 | 1.927933996 | 1.919026346 |
21 | 1.919026346 | 1.911927722 |
22 | 1.911927722 | 1.906286852 |
23 | 1.906286852 | 1.901814605 |
24 | 1.901814605 | 1.89827533 |
25 | 1.89827533 | 1.895478454 |
26 | 1.895478454 | 1.89327079 |
27 | 1.89327079 | 1.891529794 |
28 | 1.891529794 | 1.890157808 |
29 | 1.890157808 | 1.889077232 |
30 | 1.889077232 | 1.888226552 |
31 | 1.888226552 | 1.887557093 |
32 | 1.887557093 | 1.887030397 |
33 | 1.887030397 | 1.886616109 |
34 | 1.886616109 | 1.886290296 |
35 | 1.886290296 | 1.886034098 |
36 | 1.886034098 | 1.885832661 |
37 | 1.885832661 | 1.885674295 |
38 | 1.885674295 | 1.885549798 |
39 | 1.885549798 | 1.885451931 |
40 | 1.885451931 | 1.885375002 |
41 | 1.885375002 | 1.885314533 |
42 | 1.885314533 | 1.885267004 |
43 | 1.885267004 | 1.885229646 |
44 | 1.885229646 | 1.885200282 |
The formulae I used in the spreadsheet are as follows:
n | x | g(x) |
1 | 3 | =(-B2^3+12*B2^2+47)/44 |
2 | =C2 | =(-B3^3+12*B3^2+47)/44 |
3 | =C3 | =(-B4^3+12*B4^2+47)/44 |
4 | =C4 | =(-B5^3+12*B5^2+47)/44 |
5 | =C5 | =(-B6^3+12*B6^2+47)/44 |
6 | =C6 | =(-B7^3+12*B7^2+47)/44 |
7 | =C7 | =(-B8^3+12*B8^2+47)/44 |
8 | =C8 | =(-B9^3+12*B9^2+47)/44 |
9 | =C9 | =(-B10^3+12*B10^2+47)/44 |
10 | =C10 | =(-B11^3+12*B11^2+47)/44 |
11 | =C11 | =(-B12^3+12*B12^2+47)/44 |
12 | =C12 | =(-B13^3+12*B13^2+47)/44 |
13 | =C13 | =(-B14^3+12*B14^2+47)/44 |
14 | =C14 | =(-B15^3+12*B15^2+47)/44 |
15 | =C15 | =(-B16^3+12*B16^2+47)/44 |
16 | =C16 | =(-B17^3+12*B17^2+47)/44 |
17 | =C17 | =(-B18^3+12*B18^2+47)/44 |
18 | =C18 | =(-B19^3+12*B19^2+47)/44 |
19 | =C19 | =(-B20^3+12*B20^2+47)/44 |
20 | =C20 | =(-B21^3+12*B21^2+47)/44 |
21 | =C21 | =(-B22^3+12*B22^2+47)/44 |
22 | =C22 | =(-B23^3+12*B23^2+47)/44 |
23 | =C23 | =(-B24^3+12*B24^2+47)/44 |
24 | =C24 | =(-B25^3+12*B25^2+47)/44 |
25 | =C25 | =(-B26^3+12*B26^2+47)/44 |
26 | =C26 | =(-B27^3+12*B27^2+47)/44 |
27 | =C27 | =(-B28^3+12*B28^2+47)/44 |
28 | =C28 | =(-B29^3+12*B29^2+47)/44 |
29 | =C29 | =(-B30^3+12*B30^2+47)/44 |
30 | =C30 | =(-B31^3+12*B31^2+47)/44 |
31 | =C31 | =(-B32^3+12*B32^2+47)/44 |
32 | =C32 | =(-B33^3+12*B33^2+47)/44 |
33 | =C33 | =(-B34^3+12*B34^2+47)/44 |
34 | =C34 | =(-B35^3+12*B35^2+47)/44 |
35 | =C35 | =(-B36^3+12*B36^2+47)/44 |
36 | =C36 | =(-B37^3+12*B37^2+47)/44 |
37 | =C37 | =(-B38^3+12*B38^2+47)/44 |
38 | =C38 | =(-B39^3+12*B39^2+47)/44 |
39 | =C39 | =(-B40^3+12*B40^2+47)/44 |
40 | =C40 | =(-B41^3+12*B41^2+47)/44 |
41 | =C41 | =(-B42^3+12*B42^2+47)/44 |
42 | =C42 | =(-B43^3+12*B43^2+47)/44 |
43 | =C43 | =(-B44^3+12*B44^2+47)/44 |
44 | =C44 | =(-B45^3+12*B45^2+47)/44 |
According to the spreadsheet above, I got the root of f(x) =0 x=1.885229646
This student written piece of work is one of many that can be found in our AS and A Level Core & Pure Mathematics section.
Found what you're looking for?
- Start learning 29% faster today
- 150,000+ documents available
- Just £6.99 a month
