Apply iteration to find root (pure fixed point)

7 \includegraphics[max width=\textwidth, alt={}, center]{c473f577-1e96-4d11-a0d5-cdfa4873c295-12_650_720_260_708} A curve has equation \(y = \mathrm { f } ( x )\) where \(\mathrm { f } ( x ) = x ^ { 4 } - 5 x ^ { 3 } + 6 x ^ { 2 } + 5 x - 15\). As shown in the diagram, the curve crosses the \(x\)-axis at the points \(A\) and \(B\) with coordinates \(( a , 0 )\) and \(( b , 0 )\) respectively.

1. Use the factor theorem to show that \(( x - 3 )\) is a factor of \(\mathrm { f } ( x )\).
2. By first finding the quotient when \(\mathrm { f } ( x )\) is divided by \(( x - 3 )\), show that $$a = - \sqrt { \frac { 5 } { 2 - a } } .$$
3. Use an iterative formula, based on the equation in part (b), to find the value of \(a\) correct to 3 significant figures. Give the result of each iteration to 5 significant figures.
   If you use the following lined page to complete the answer(s) to any question(s), the question number(s) must be clearly shown.

1. $$g ( x ) = x ^ { 6 } + 2 x - 1000$$

1. Show that \(\mathrm { g } ( x ) = 0\) has a root \(\alpha\) in the interval [3,4] Using the iteration formula $$x _ { n + 1 } = \sqrt [ 6 ] { 1000 - 2 x _ { n } } \quad \text { with } x _ { 1 } = 3$$
2. 1. find, to 4 decimal places, the value of \(x _ { 2 }\)
   2. find, by repeated iteration, the value of \(\alpha\). Give your answer to 4 decimal places.

1. A curve has equation \(y = \mathrm { f } ( x )\) where

$$\mathrm { f } ( x ) = x ^ { 2 } - 5 x + \mathrm { e } ^ { x } \quad x \in \mathbb { R }$$

1. Show that the equation \(\mathrm { f } ( x ) = 0\) has a root, \(\alpha\), in the interval [1,2] The iterative formula $$x _ { n + 1 } = \sqrt { 5 x _ { n } - \mathrm { e } ^ { x _ { n } } }$$ with \(x _ { 1 } = 1\) is used to find an approximate value for the root \(\alpha\).
2. 1. Find the value of \(x _ { 2 }\) to 4 decimal places.
   2. Find, by repeated iteration, the value of \(\alpha\), giving your answer to 4 decimal places.

1. $$f ( x ) = 2 x ^ { 3 } + x - 10$$

1. Show that the equation \(\mathrm { f } ( x ) = 0\) has a root \(\alpha\) in the interval \([ 1.5,2 ]\) The only real root of \(\mathrm { f } ( x ) = 0\) is \(\alpha\) The iterative formula $$x _ { n + 1 } = \left( 5 - \frac { 1 } { 2 } x _ { n } \right) ^ { \frac { 1 } { 3 } } , \quad x _ { 0 } = 1.5$$ can be used to find an approximate value for \(\alpha\)
2. Calculate \(x _ { 1 } , x _ { 2 }\) and \(x _ { 3 }\), giving your answers to 4 decimal places.
3. By choosing a suitable interval, show that \(\alpha = 1.6126\) correct to 4 decimal places.

1. \begin{figure}[h] \end{figure} Figure 1 shows part of the curve with equation \(y = - x ^ { 3 } + 2 x ^ { 2 } + 2\), which intersects the \(x\)-axis at the point \(A\) where \(x = \alpha\). To find an approximation to \(\alpha\), the iterative formula $$x _ { n + 1 } = \frac { 2 } { \left( x _ { n } \right) ^ { 2 } } + 2$$ is used.

1. Taking \(x _ { 0 } = 2.5\), find the values of \(x _ { 1 } , x _ { 2 } , x _ { 3 }\) and \(x _ { 4 }\). Give your answers to 3 decimal places where appropriate.
2. Show that \(\alpha = 2.359\) correct to 3 decimal places.

2. \(\quad \mathrm { f } ( x ) = x ^ { 3 } - 2 x - 5\).

1. Show that there is a root \(\alpha\) of \(\mathrm { f } ( x ) = 0\) for \(x\) in the interval \([ 2,3 ]\). The root \(\alpha\) is to be estimated using the iterative formula $$x _ { n + 1 } = \sqrt { \left( 2 + \frac { 5 } { x _ { n } } \right) } , \quad x _ { 0 } = 2$$
2. Calculate the values of \(x _ { 1 } , x _ { 2 } , x _ { 3 }\) and \(x _ { 4 }\), giving your answers to 4 significant figures.
3. Prove that, to 5 significant figures, \(\alpha\) is 2.0946.

3 The equation \(2 x ^ { 3 } + 4 x - 35 = 0\) has one real root.

1. Show by calculation that this real root lies between 2 and 3 .
2. Use the iterative formula $$x _ { n + 1 } = \sqrt [ 3 ] { 17.5 - 2 x _ { n } }$$ with a suitable starting value, to find the real root of the equation \(2 x ^ { 3 } + 4 x - 35 = 0\) correct to 2 decimal places. You should show the result of each iteration.

8 The iteration \(x _ { n + 1 } = \frac { 1 } { \left( x _ { n } + 2 \right) ^ { 2 } }\), with \(x _ { 1 } = 0.3\), is to be used to find the real root, \(\alpha\), of the equation \(x ( x + 2 ) ^ { 2 } = 1\).

1. Find the value of \(\alpha\), correct to 4 decimal places. You should show the result of each step of the iteration process.
2. Given that \(\mathrm { f } ( x ) = \frac { 1 } { ( x + 2 ) ^ { 2 } }\), show that \(\mathrm { f } ^ { \prime } ( \alpha ) \neq 0\).
3. The difference, \(\delta _ { r }\), between successive approximations is given by \(\delta _ { r } = x _ { r + 1 } - x _ { r }\). Find \(\delta _ { 3 }\).
4. Given that \(\delta _ { r + 1 } \approx \mathrm { f } ^ { \prime } ( \alpha ) \delta _ { r }\), find an estimate for \(\delta _ { 10 }\).

9 The equation \(10 x - 8 \ln x = 28\) has a root \(\alpha\) in the interval [3,4]. The iteration \(x _ { n + 1 } = \mathrm { g } \left( x _ { n } \right)\), where \(\mathrm { g } ( x ) = 2.8 + 0.8 \ln x\) and \(x _ { 1 } = 3.8\), is to be used to find \(\alpha\).

1. Find the value of \(\alpha\) correct to 5 decimal places. You should show the result of each step of the iteration to 6 decimal places.
2. Illustrate this iteration by means of a sketch.
3. The difference, \(\delta _ { r }\), between successive approximations is given by \(\delta _ { r } = x _ { r + 1 } - x _ { r }\). Find \(\delta _ { 3 }\).
4. Given that \(\delta _ { n + 1 } \approx \mathrm {~g} ^ { \prime } ( \alpha ) \delta _ { n }\), for all positive integers \(n\), estimate the smallest value of \(n\) such that \(\delta _ { n } < 10 ^ { - 6 } \delta _ { 1 }\). \section*{OCR}

3 Complete this table to show the next 3 values of the iteration $$x _ { n + 1 } = k x _ { n } \left( 1 - x _ { n } \right)$$ in the case when \(k = 3.2\) and \(x _ { 0 } = 0.5\). Give your answers to calculator accuracy.

12 JANUARY 2005
Afternoon
1 hour 30 minutes

• This insert should be used to answer Questions 4 and 7.
• Write your name, centre number and candidate number in the spaces provided at the top of this page.
• Write your answers to Questions 4 and 7 in the spaces provided in this insert, and attach it to your answer booklet.

4

1. 	\(A\)	\(B\)	C	D	\(E\)	\(F\)	G	\(H\)
   A	-	4	2	3	-	-	-	-
   \(B\)	4	-	1	-	3	-	-	-
   C	2	1	-	2	-	6	5	-
   \(D\)	3	-	2	-	-	-	4	-
   E	-	3	-	-	-	8	-	7
   \(F\)	-	-	6	-	8	-	-	8
   \(G\)	-	-	5	4	-	-	-	9
   \(H\)	-	-	-	-	7	8	9	-

2. B \(E\) \(C\) F
   • \(H\) \(A\) •
   • \({ } ^ { \text {F } }\)
   H D
   G
3. \(\_\_\_\_\)
4. \(\_\_\_\_\)
5. \(\_\_\_\_\) 7
   1. 1. \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_191_1179_269_482} Do not cross out your working values (temporary labels) \includegraphics[max width=\textwidth, alt={}, center]{197624b2-ca67-4bad-9c2c-dc68c10be0fd-11_871_1557_612_335} Shortest route from \(A\) to \(E =\) \(\_\_\_\_\) Length = \(\_\_\_\_\) Shortest route from \(A\) to \(J =\) \(\_\_\_\_\) Length = \(\_\_\_\_\)
      2. Length of route \(=\) \(\_\_\_\_\) Vertices visited in order \(\_\_\_\_\)
      3. Explanation \(\_\_\_\_\)
   2. \(\_\_\_\_\) Length = \(\_\_\_\_\)

1 The flow chart shows an algorithm for which the input is a three-digit positive integer. \includegraphics[max width=\textwidth, alt={}, center]{43fe5fd5-4b98-4c3a-90ca-a1bd5cf065fe-2_1294_1493_356_328}

1. Trace through the algorithm using the input \(A = 614\) to show that the output is 297 . Write down the values of \(A , B , C\) and \(D\) in each pass through the algorithm.
2. What is the output when \(A = 616\) ?
3. Explain why the counter \(C\) is needed.

5 Consider the following algorithm which is to be applied to a list of numbers.

1. Apply the algorithm to this list. $$\begin{array} { l l l l l } 3 & 6 & 5 & 7 & 3 \end{array}$$ Record in a table the values of \(X , N , T\) and \(S\) at each pass through Step 3 and give the output values.
2. Write down the number of additions and the number of multiplications that are done in Step 3 for a list of five numbers. Hence find the total number of arithmetic operations (additions, multiplications, divisions, subtractions and square roots) that are done in Step 3 and Step 5 when applying the algorithm to a list of five numbers.
3. Find an expression for the total number of arithmetic operations that are done in applying the algorithm to a list of \(n\) numbers.
4. The total number of arithmetic operations can be used as a measure of the run-time for the algorithm. If it takes approximately 2 seconds to apply the algorithm to a list of 1000 numbers, approximately how long will it take to apply the algorithm to a list of 5000 numbers?

2 Consider the following algorithm.
STEP 1 Input a number \(N\) STEP 2 Calculate \(R = N \div 2\) STEP 3 Calculate \(S = ( ( N \div R ) + R ) \div 2\) STEP 4 If \(R\) and \(S\) are the same when rounded to 2 decimal places, go to STEP 7
STEP 5 Replace \(R\) with the value of \(S\) STEP 6 Go to STEP 3
STEP 7 Output the value of \(R\) correct to 2 decimal places

1. Work through the algorithm starting with \(N = 16\). Record the values of \(R\) and \(S\) each time they change and show the value of the output.
2. Work through the algorithm starting with \(N = 2\). Record the values of \(R\) and \(S\) each time they change and show the value of the output.
3. What does the algorithm achieve for positive inputs?
4. Show that the algorithm fails when it is applied to \(N = - 4\).
5. Describe what happens when the algorithm is applied to \(N = - 2\). Suggest how the algorithm could be improved to avoid this problem, without imposing a restriction on the allowable input values.

3 Holly has written an algorithm.

1. Work through Holly's algorithm using the input values \(A = 30\) and \(B = 18\). Set out your working using the table in the answer book. Use one row for each step where any values change and only write down values when they change. Write down the values that are printed.
2. Describe what happens when \(A = 18\) and \(B = 30\). You need only record enough rows of the table to be able to show what happens.
3. Without doing further working, state the output values of \(F\) and \(M\) when \(A = 12\) and \(B = 8\).

3 The following algorithm finds two positive integers for which the sum of their squares equals a given input, when this is possible. The function \(\operatorname { INT } ( X )\) gives the largest integer that is less than or equal to \(X\). For example: \(\operatorname { INT } ( 6.9 ) = 6\), \(\operatorname { INT } ( 7 ) = 7 , \operatorname { INT } ( 7.1 ) = 7\).

1. Apply the algorithm to the input \(N = 500\). You only need to write down values when they change and there is no need to record the use of lines \(30,60,70\) or 90 .
2. Apply the algorithm to the input \(N = 7\).
3. Explain why lines 70 and 110 are needed. The algorithm has order \(\sqrt { N }\).
4. If it takes 0.7 seconds to run the algorithm when \(N = 3000\), roughly how long will it take when \(N = 12000\) ?

4 [Answer this question on the insert provided.]
An algorithm involves the following steps.
Step 1: Input two positive integers, \(A\) and \(B\).
Let \(C = 0\) Step 2: If \(B\) is odd, replace \(C\) by \(C + A\).
Step 3: If \(B = 1\), go to step 6.
Step 4: Replace \(A\) by \(2 A\).
If \(B\) is even, replace \(B\) by \(B \div 2\), otherwise replace \(B\) by ( \(B - 1\) ) ÷ 2 .
Step 5: Go back to step 2.
Step 6: Output the value of \(C\).

1. Demonstrate the use of the algorithm for the inputs \(A = 6\) and \(B = 13\).
2. When \(B = 8\), what is the output in terms of \(A\) ? What is the relationship between the output and the original inputs?

3 The following algorithm (J. M. Oudin, 1940) claims to compute the date of Easter Sunday in the Gregorian calendar system.
The algorithm uses the year, y, to give the month, m, and day, d, of Easter Sunday.
All variables are integers and all remainders from division are dropped. For example, 7 divided by 3 is 2 remainder 1 . The remainder is dropped, giving the answer 2. $$\begin{aligned} & c = y / 100 \\ & n = y - 19 \times ( y / 19 ) \\ & k = ( c - 17 ) / 25 \\ & i = c - ( c / 4 ) - ( c - k ) / 3 + ( 19 \times n ) + 15 \\ & i = i - 30 \times ( i / 30 ) \\ & i = i - ( i / 28 ) \times ( 1 - ( i / 28 ) \times ( 29 / ( i + 1 ) ) \times ( ( 21 - n ) / 11 ) ) \\ & j = y + ( y / 4 ) + i + 2 - c + ( c / 4 ) \\ & j = j - 7 \times ( j / 7 ) \\ & p = i - j \\ & m = 3 + ( p + 40 ) / 44 \\ & d = p + 28 - 31 \times ( m / 4 ) \end{aligned}$$ For example, for 2008: \(\mathrm { y } = 2008\) \(\mathrm { c } = 2008 / 100 = 20\) \(n = 2008 - 19 \times ( 2008 / 19 ) = 2008 - 19 \times ( 105 ) = 13\), etc.
Complete the calculation for 2008.

2 The following algorithm computes the number of comparisons made when Prim's algorithm is applied to a complete network on \(n\) vertices ( \(n > 2\) ). Step 1 Input the value of \(n\) Step 2 Let \(i = 1\) Step 3 Let \(j = n - 2\) Step 4 Let \(k = j\) Step 5 Let \(i = i + 1\) Step 6 Let \(j = j - 1\) Step 7 Let \(k = k + ( i \times j ) + ( i - 1 )\) Step 8 If \(j > 0\) then go to Step 5
Step 9 Print \(k\) Step 10 Stop

1. Apply the algorithm when \(n = 5\), showing the intermediate values of \(i , j\) and \(k\). The function \(\mathrm { f } ( n ) = \frac { 1 } { 6 } n ^ { 3 } - \frac { 7 } { 6 } n + 1\) gives the same output as the algorithm.
2. Showing your working, check that \(\mathrm { f } ( 5 )\) is the same value as your answer to part (i).
3. What does the structure of \(\mathrm { f } ( n )\) tell you about Prim's algorithm?

3 The following algorithm computes an estimate of the square root of a number which is between 0 and 2.
Step 1 Subtract 1 from the number and call the result \(x\) Step 2 Set oldr = 1
Step 3 Set \(i = 1\) Step 4 Set \(j = 0.5\) Step 5 Set \(k = 0.5\) Step 6 Set change \(= x ^ { i } \times k\) Step 7 Set newr \(=\) oldr + change
Step 8 If \(- 0.005 <\) change < 0.005 then go to Step 17
Step 9 Set oldr = newr
Step 10 Set \(i = i + 1\) Step 11 Set \(j = j - 1\) Step 12 Set \(k = k \times j \div i\) Step 13 Set change \(= x ^ { i } \times k\) Step 14 Set newr \(=\) oldr + change
Step 15 If \(- 0.005 <\) change < 0.005 then go to Step 17
Step 16 Go to Step 9
Step 17 Print out newr

1. Use the algorithm to find an estimate of the square root of 1.44 , showing all of the steps.
2. Consider what happens if the algorithm is applied to 0.56 , and then use your four values of change from part (i) to calculate an estimate of the square root of 0.56 .

2 In this question INT( \(m\) ) means the integer part of \(m\). Thus INT(3.5) \(= 3\) and INT(4) \(= 4\).
A game for two players starts with a number, \(n\), of counters. Players alternately pick up a number of counters, at least 1 and not more than half of those left. The player forced to pick up the last counter is the loser. Arif programs his computer to play the game, using the rule "pick up INT(half of the remaining counters), or the last counter if forced".

1. You are to play against Arif's computer with \(n = 5\) and with Arif's computer going first. What happens at each turn?
2. You are to play against Arif's computer with \(n = 6\) and with Arif's computer going first. What happens at each turn?
3. Now play against Arif's computer with \(n = 7\) and with Arif's computer going first. Describe what happens.

2 This question concerns the following algorithm which operates on a given function, f. The algorithm finds a point between A and B at which the function has a minimum, with a maximum error of 0.05 .

1. Working correct to three decimal places, perform two iterations of the algorithm for \(\mathrm { f } ( x ) = 2 x ^ { 2 } - 15 x + 30\), when \(\mathrm { A } = 3\) and \(\mathrm { B } = 4\). Start at Step 1 and stop when you reach Step 8 for the second time.
2. The \(\left( \frac { \sqrt { 5 } - 1 } { 2 } \right)\) factor in Step 3 ensures that either the new ' \(L\) ' is equal to the old ' \(R\) ', or vice versa. Why is this important?
3. This algorithm is used when the function is not known explicitly, but where its value can be found for any given input. Give a practical example of where it might be used.

2 The following algorithm operates on the equations of 3 straight lines, each in the form \(y = m _ { i } x + c _ { i }\).

1. Run the algorithm for the straight lines \(y = 2 x + 8 , y = 2 x + 5\) and \(y = 4 x + 3\) using the table given in your answer book. The first five steps have been completed, so you should continue from Step 6. [7]
2. Describe what the algorithm achieves.

5. \begin{figure}[h] \end{figure} An algorithm is described by the flowchart shown in Figure 4.

1. Given that \(\mathrm { S } = 25000\), complete the table in the answer book to show the results obtained at each step when the algorithm is applied. This algorithm is designed to model a possible system of income tax, T, on an annual salary, £S.
2. Write down the amount of income tax paid by a person with an annual salary of \(\pounds 25000\).
3. Find the maximum annual salary of a person who pays no tax.

1. \begin{figure}[h] \end{figure} Hero's algorithm for finding a square root is described by the flow chart shown in Figure 1.
Given that \(\mathrm { N } = 72\) and \(\mathrm { E } = 8\),

1. use the flow chart to complete the table in the answer book, working to at least seven decimal places when necessary. Give the final output correct to seven decimal places. The flow chart is used with \(\mathrm { N } = 72\) and \(\mathrm { E } = - 8\),
2. describe how this would affect the output.
3. State the value of E which cannot be used when using this flow chart.