C3 Coursework

C3 Coursework Numerical Methods In this coursework I am going to investigate numerical methods of solving equations. The methods I will use are: 1. Change of sign method, for which I am going to use decimal search 2. Fixed point iteration using x = g(x) method 3.

Fixed point iteration using Newton-Raphson method I will then compare the methods in terms of speed of convergence and ease of use with hardware/software Contents Change of sign | |Decimal search |3 | |Failure of change of sign method |7 | | | | x = g(x) | |x = g(x) method |8 | |Failure of x = g(x) method |12 | | | |Newton-Raphson | |Newton-Raphson method |13 | |Failure of Newton-Raphson method |16 | | | |Comparison of methods |17 | Change of sign method I have chosen the function of x, f(x) = 4x? 5x? + 4x – 1 and I am going to find one root using decimal search. I have plotted the graph y = 4x? + 5x? + 4x – 1 below, and it can be seen that the root lies between 0 and 1. Firstly, I am going to increase x by 0. 1 each time between 0 and 1 and work out the value of the function for each value of x. |x |f(x) | |0 |-1 | |0. 1 |-0.

546 | |0. 2 |0. 032 | |0. 3 |0. 758 | |0.

4 |1. 656 | |0. 5 |2. 75 | |0. 6 |4. 064 | |0.

7 |5. 622 | |0. 8 |7. 448 | |0. 9 |9.

566 | 1 |12 | We can see from the table that there is a change of sign between 0. 1 and 0. 2; therefore the root must lie between 0. 1 and 0. 2. I have plotted the graph below to illustrate this.

Since we now know that the root lies between 0. 1 and 0. 2, I am going to use this as my new interval and find the value of the function for each value of x. |x |f(x) | |0. 1 |-0. 546 | |0.

11 |-0. 494176 | |0. 12 |-0. 441088 | |0.

13 |-0. 386712 | |0. 14 |-0. 331024 | |0.

15 |-0. 274 | |0. 16 |-0. 215616 | |0. 7 |-0. 155848 | |0.

18 |-0. 094672 | |0. 19 |-0. 032064 | |0.

2 |0. 032 | We can see that there is a change of sign between 0. 19 and 0. 2.

I am going to illustrate this using a graph once more. Since we now know that the root lies between 0. 19 and 0. 2, I am going to use this as my new interval and find the value of the function for each value of x. |x |f(x) | |0. 19 |-0.

032064 | |0. 191 |-0. 025723516 | |0. 192 |-0.

019368448 | |0. 193 |-0. 012998772 | |0. 194 |-0. 06614464 | |0.

195 |-0. 0002155 | |0. 196 |0. 006198144 | |0. 197 |0.

012626492 | |0. 198 |0. 019069568 | |0. 199 |0. 025527396 | |0. 2 |0.

032 | We can see that there is a change of sign between 0. 195 and 0. 196, so the root lies between these two points. I am going to plot a graph to illustrate this. We can see that there is a change of sign between 0.

195 and 0. 196 and so the estimate of the root is (0. 195+0. 196) ? 2 which is equal to 0. 1955 with a maximum error of ± 0.

0005 Failure of change of sign methodI am now going to show an example where the change of sign method fails to find a root. I have chosen the function of x, f(x) = 45x? -24x? -28x+16 From the graph above, it can be seen that there is a root in the interval 0 and 1. However, because it is a repeated root, the change of sign method fails as there is no change of sign either side of the root . This is a failure of the change of sign method. x = g(x) method Another way of finding a root is using the x = g(x) method. I have chosen the function of x, f(x) = 2x? + x? -5x+1, the graph of the function looks like the following: From the graph, it can be seen that there are roots in the interval [-2,-1], [0,1] and [1,2].

The roots are when f(x) = 0, so if we use the equation 2x? + x? -5x+1 = 0, we can rearrange it into the form x = g(x) and find one of the roots. 2x? + x? -5x+1 = 0 2x? + x? +1 = 5x x = 2x? + x? +1 = g (x)5 Using this, we can find the roots by plotting both parts of the function and where they cross is where a root is. Graphically, both lines plotted on the same graph looks like the graph below. Therefore if I plot x = 2x? + x? +1 and x = g(x) on one graph we can find one of the roots. 5 I want to find the root between 0 and 1. For this method to work, I need to take an initial estimate.

I take an initial estimate of 0. I put in the rearranged formula into a spreadsheet. r |Xr | |1 |0 | |=A2+1 |=(2*B2^3+B2^2+1)/5 | |=A3+1 |=(2*B3^3+B3^2+1)/5 | |=A4+1 |=(2*B4^3+B4^2+1)/5 | |=A5+1 |=(2*B5^3+B5^2+1)/5 | |=A6+1 |=(2*B6^3+B6^2+1)/5 | |=A7+1 |=(2*B7^3+B7^2+1)/5 | |=A8+1 |=(2*B8^3+B8^2+1)/5 | |=A9+1 |=(2*B9^3+B9^2+1)/5 | |=A10+1 |=(2*B10^3+B10^2+1)/5 | |=A11+1 |=(2*B11^3+B11^2+1)/5 | |=A12+1 |=(2*B12^3+B12^2+1)/5 | |=A13+1 |=(2*B13^3+B13^2+1)/5 | The results show that the iterative process converges to the root 0. 2129 to 5 significant figures.

|r |Xr | |1 |0 | |2 |0. 2 | |3 |0. 2112 | |4 |0. 212689356 | |5 |0.

212895903 | |6 |0. 212924707 | |7 |0. 212928727 | |8 |0. 12929288 | |9 |0.

212929367 | |10 |0. 212929378 | |11 |0. 212929379 | |12 |0. 212929379 | |13 |0. 212929379 | If we use Autograph to illustrate this, we can see that it is a staircase diagram I am now going to establish the accuracy of the root using decimal search. I am trying to find the root between 0 and 1; therefore I take this as my first interval.

|x |f(x) | |0 |1 | |0. 1 |0. 512 | |0. 2 |0. 056 | |0. 3 |-0.

356 | |0. 4 |-0. 12 | |0. 5 |-1 | |0. 6 |-1.

208 | |0. 7 |-1. 324 | |0. 8 |-1. 336 | |0.

9 |-1. 232 | |1 |-1 | We can see from the table that there is a change of sign between 0. 2 and 0. 3. I am going to use this as my new interval. |x |f(x) | |0.

2 |0. 056 | |0. 21 |0. 012622 | |0.

22 |-0. 030304 | |0. 23 |-0. 072766 | |0. 24 |-0.

114752 | |0. 25 |-0. 15625 | |0. 26 |-0. 97248 | |0. 27 |-0.

237734 | |0. 28 |-0. 277696 | |0. 29 |-0. 317122 | |0. 3 |-0.

356 | We can see from the table that there is a change of sign between 0. 21 and 0. 22. I am going to use this as my new interval.

|x |f(x) | |0. 21 |0. 012622 | |0. 211 |0. 008308862 | |0.

212 |0. 004000256 | |0. 213 |-0. 000303806 | |0. 214 |-0.

004603312 | |0. 215 |-0. 00889825 | |0. 216 |-0.

013188608 | |0. 217 |-0. 17474374 | |0. 218 |-0. 021755536 | |0. 219 |-0.

026032082 | |0. 22 |-0. 030304 | We can see from the table that there is a change of sign between 0. 212 and 0. 213.

I am going to use this as my new interval. |x |f(x) | |0. 212 |0. 004000256 | |0. 2121 |0. 003569645 | |0.

2122 |0. 00313908 | |0. 2123 |0. 00270856 | |0.

2124 |0. 002278085 | |0. 2125 |0. 001847656 | |0. 2126 |0.

001417273 | |0. 2127 |0. 000986935 | |0. 2128 |0.

00556642 | |0. 2129 |0. 000126395 | |0. 213 |-0. 000303806 | We can see from the table that there is a change of sign between 0.

2129 and 0. 213. So the estimate of the root is (0. 2129+0. 213) ? 2 which is equal to 0. 21295 with a maximum error of ± 0.

00005 Failure of x = g(x) method Now I want to find the root between 1 and 2 However, because the gradient of g(x) is greater than 1, i. e. steeper than the gradient of y=x, the sequence does not converge to the root, hence the method fails to find the root. Newton-Raphson method Another numerical method of solving equations is the Newton-Raphson method.I am going to use this method to find a root in the function of x, f(x) = 2x4 - x? - 2 The graph looks like the following: This method works by taking an estimate of the root. I want to find the root between 1 and 2 so my initial estimate is 1.

Using the gradient of the function, If I draw a tangent to the curve at x=1, then where the tangent crosses the x-axis is a better estimate of the root. The method is repeated, and the value of x gets closer and closer to the actual root. Below is a graph to illustrate this. The Newton-Raphson iterative formula is: We can use this to work out the value of the root.

I am going to set up a spreadsheet to do this. r |Xr | |1 |2 | |=A2+1 |=B2-(2*B2^4-B2^3-2)/(8*B2^3-3*B2^2) | |=A3+1 |=B3-(2*B3^4-B3^3-2)/(8*B3^3-3*B3^2) | |=A4+1 |=B4-(2*B4^4-B4^3-2)/(8*B4^3-3*B4^2) | |=A5+1 |=B5-(2*B5^4-B5^3-2)/(8*B5^3-3*B5^2) | |=A6+1 |=B6-(2*B6^4-B6^3-2)/(8*B6^3-3*B6^2) | |=A7+1 |=B7-(2*B7^4-B7^3-2)/(8*B7^3-3*B7^2) | |=A8+1 |=B8-(2*B8^4-B8^3-2)/(8*B8^3-3*B8^2) | |=A9+1 |=B9-(2*B9^4-B9^3-2)/(8*B9^3-3*B9^2) | |=A10+1 |=B10-(2*B10^4-B10^3-2)/(8*B10^3-3*B10^2) | The results show that the iterative process converges to the root 1. 153 to 4 significant figures. r |Xr | |1 |2 | |2 |1. 576923077 | |3 |1. 307337757 | |4 |1.

181211035 | |5 |1. 153941053 | |6 |1. 152778625 | |7 |1. 152776581 | |8 |1. 152776581 | |9 |1. 152776581 | |10 |1.

152776581 |I am now going to establish the accuracy of the root using decimal search. I am trying to find the root between 1 and 2; therefore I take this as my first interval. |x |f(x) | | 1 |-1 | |1. 1 |-0. 4028 | |1. 2 |0.

4192 | |1. 3 |1. 5152 | |1. 4 |2. 9392 | |1.

5 |4. 75 | |1. 6 |7. 0112 | |1.

7 |9. 7912 | |1. 8 |13. 1632 | |1. 9 |17. 2052 | |2 |22 | We can see from the table that there is a change of sign between 1.

1 and 1. 2; therefore I am going to use this as my new interval. x |f(x) | |1. 1 |-0. 4028 | |1.

11 |-0. 33149 | |1. 12 |-0. 25789 | |1.

13 |-0. 18195 | |1. 14 |-0. 10362 | |1. 15 |-0.

02286 | |1. 16 |0. 060383 | |1. 17 |0. 146161 | |1.

18 |0. 234524 | |1. 19 |0. 325519 | |1. 2 |0. 4192 | From the table we can see that there is a change of sign between 1.

15 and 1. 16, therefore I am going to use this as my new interval. |x |f(x) | |1. 15 |-0.

02286 | |1. 151 |-0. 01465 | |1. 152 |-0. 0641 | |1.

153 |0. 001848 | |1. 154 |0. 010135 | |1. 155 |0.

018447 | |1. 156 |0. 026783 | |1. 157 |0. 035145 | |1. 158 |0.

043533 | |1. 159 |0. 051945 | |1. 16 |0.

060383 | We can see from the table that there is a change of sign between 1. 152 and 1. 153; therefore I take this as my new interval. So the estimate of the root is (0. 152+0.

153) ? 2 which is equal to 0. 1525 with a maximum error of ± 0. 00005 Failure of Newton-Raphson method I am going to use the following function; f(x) = x? -3x? +3. It looks like the following plottedI want to find the root between 2 and 3; therefore I take an initial estimate of 2. I put this into the Newton-Raphson iterative formula and get the following: X1 = 2 – = undefined This occurs because the gradient of the tangent x=2 is 0.

As a result, the tangent will never cross the x-axis; therefore, there will never be a new value of x. Thus, the iteration process fails to converge to the root, and hence no root is found. This is a failure of the Newton-Raphson method. Comparison of methods To compare the three methods, I am going to use the function of x, f(x) = 2x? +x? -5x+1, that which I used in the x = g(x) method.

I shall be comparing them in terms of speed of convergence and ease of use with hardware/software.The graph of the function looks like the following: I am going to find the root between 1 and 2 |r |Change of sign method |x = g(x) method |Newton-Raphson method | |1 (initial estimate) |[0,1] |0 |0 | |2 |0. 2 |0. 2 |0.

2 | |3 |0. 21 |0. 2112 |0. 212844037 | |4 |0. 12 |0.

212689356 |0. 212929376 | |5 |0. 2129 |0. 212895903 |0. 212929379 | |6 |0. 21292 |0.

212924707 |0. 212929379 | |7 |0. 212929 |0. 212928727 |  | |8 |0. 2129293 |0.

212929288 |  | |9 |0. 1292937 |0. 212929367 |  | |10 |0. 212929379 |0. 212929378 |  | |11 |0. 212929379 |0.

212929379 |  | |12 |  |0. 212929379 |  | In terms of speed of convergence, it is clear from the results that the Newton-Raphson method involves the least iterations/calculations, therefore converges to the root the fastest.In terms of ease of use with hardware/software, the x=g(x) method (once you rearrange the formula) and the Newton-Raphson method (once you find the derivative of f(x)) take less time to find a root when using a spreadsheet because their formula are iterative. However, the change of sign method takes a bit longer because you have to change the interval each time, until you reach a degree of accuracy you are happy with. On the whole, I feel the change of sign method is the least complex and most reliable, however takes longer. The Newton-Raphson method converges the fastest, but is more difficult as you have to find the derivative of f(x) first.

I feel the x = g(x) method is the least effective because it involves the most iterations/calculations and requires you to rearrange the function of x first, whereas the change of sign method does not. ----------------------- Here is the root I am going to find using decimal search. It lies between 0 and 1. We can see that the root lies between 0. 1 and 0. 2 From the graph, we can see that the root lies between 0.

19 and 0. 2 We can see that the root lies between 0. 195 and 0. 196 It is a repeated root; therefore the change of sign method fails y = x y = 2x? + x? +1 5 y = 2x? + x? +1 5 y = x y = g(x) y = x 2? -3(2)? +3 3(2)? -6(2)