Apply iteration to find root

6 The function \(\operatorname { INT } ( C )\) gives the largest integer that is less than or equal to \(C\).
For example: \(\operatorname { INT } ( 4.8 ) = 4 , \operatorname { INT } ( 7 ) = 7 , \operatorname { INT } ( 0.8 ) = 0 , \operatorname { INT } ( - 0.8 ) = - 1 , \operatorname { INT } ( - 2.4 ) = - 3\).
Consider the following algorithm.

1. Apply the algorithm using the inputs \(A = 10\) and \(B = 128\). Record the values of \(A , B , C , D , E\), and \(F\) every time they change. Record the output each time line 60 is reached.
2. Show what happens when the input values are \(A = 10\) and \(B = - 13\).

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.

10 \includegraphics[max width=\textwidth, alt={}, center]{05bec6d6-b526-4b6f-86f3-39aa38cbf5c6-6_405_661_251_703} The diagram shows a sector \(A O B\) of a circle with centre \(O\) and radius 6 cm .
The angle \(A O B\) is \(\theta\) radians.
The area of the segment bounded by the chord \(A B\) and the \(\operatorname { arc } A B\) is \(7.2 \mathrm {~cm} ^ { 2 }\).

1. Show that \(\theta = 0.4 + \sin \theta\).
2. Let \(\mathrm { F } ( \theta ) = 0.4 + \sin \theta\). By considering the value of \(\mathrm { F } ^ { \prime } ( \theta )\) where \(\theta = 1.2\), explain why using an iterative method based on the equation in part (a) will converge to the root, assuming that 1.2 is sufficiently close to the root.
3. Use the iterative formula \(\theta _ { n + 1 } = 0.4 + \sin \theta _ { n }\) with a starting value of 1.2 to find the value of \(\theta\) correct to 4 significant figures.
   You should show the result of each iteration.
4. Use a change of sign method to show that the value of \(\theta\) found in part (c) is correct to 4 significant figures.

10 \includegraphics[max width=\textwidth, alt={}, center]{38b515c2-4764-4b51-a1f5-9b48d46610f0-7_545_659_255_244} The diagram shows a sector \(O A B\) of a circle with centre \(O\) and radius \(O A\). The angle \(A O B\) is \(\theta\) radians. \(M\) is the mid-point of \(O A\). The ratio of areas \(O M B : M A B\) is 2:3.

1. Show that \(\theta = 1.25 \sin \theta\). The equation \(\theta = 1.25 \sin \theta\) has only one root for \(\theta > 0\).
2. This root can be found by using the iterative formula \(\theta _ { n + 1 } = 1.25 \sin \theta _ { n }\) with a starting value of \(\theta _ { 1 } = 0.5\).
   • Write down the values of \(\theta _ { 2 } , \theta _ { 3 }\) and \(\theta _ { 4 }\).
   • Hence find the value of this root correct to \(\mathbf { 3 }\) significant figures.
   • The diagram in the Printed Answer Booklet shows the graph of \(y = 1.25 \sin \theta\), for \(0 \leqslant \theta \leqslant \pi\).
   • Use this diagram to show how the iterative process used in (b) converges to this root.
   • State the type of convergence.
   • Draw a suitable diagram to show why using an iterative process with the formula \(\theta _ { n + 1 } = \sin ^ { - 1 } \left( 0.8 \theta _ { n } \right)\) does not converge to the root found in (b).

4. The curve with equation \(y = 2 + \ln ( 4 - x )\) meets the line \(y = x\) at a single point, \(x = \beta\).
a. Show that \(2 < \beta < 3\) \begin{figure}[h] \end{figure} Figure 2 shows the graph of \(y = 2 + \ln ( 4 - x )\) and the graph of \(y = x\).
A student uses the iteration formula $$x _ { n + 1 } = 2 + \ln \left( 4 - x _ { n } \right) , \quad n \in N ,$$ in an attempt to find an approximation for \(\beta\).
Using the graph and starting with \(x _ { 1 } = 3\),
b. determine whether the or not this iteration formula can be used to find an approximation for \(\beta\), justifying your answer.

1. The curve with equation \(y = \mathrm { f } ( x )\) where

$$f ( x ) = x ^ { 2 } + \ln \left( 2 x ^ { 2 } - 4 x + 5 \right)$$ has a single turning point at \(x = \alpha\)

1. Show that \(\alpha\) is a solution of the equation $$2 x ^ { 3 } - 4 x ^ { 2 } + 7 x - 2 = 0$$ The iterative formula $$x _ { n + 1 } = \frac { 1 } { 7 } \left( 2 + 4 x _ { n } ^ { 2 } - 2 x _ { n } ^ { 3 } \right)$$ is used to find an approximate value for \(\alpha\).
   Starting with \(x _ { 1 } = 0.3\)
2. calculate, giving each answer to 4 decimal places,
   1. the value of \(x _ { 2 }\)
   2. the value of \(x _ { 4 }\) Using a suitable interval and a suitable function that should be stated,
3. show that \(\alpha\) is 0.341 to 3 decimal places.

11 Fig. 11 shows the graph of \(y = x ^ { 2 } - 4 x + x \ln x\). \begin{figure}[h] \end{figure}

1. Show that the \(x\)-coordinate of the stationary point on the curve may be found from the equation \(2 x - 3 + \ln x = 0\).
2. Use an iterative method to find the \(x\)-coordinate of the stationary point on the curve \(y = x ^ { 2 } - 4 x + x \ln x\), giving your answer correct to 4 decimal places.

3. \begin{figure}[h] \end{figure} An algorithm is described by the flow chart shown in Figure 3.

1. Complete the table in the answer book recording the results of each step as the algorithm is applied.
   (Notice that values of \(A , B , C\) and \(D\) are to be given to 3 decimal places, and the values of \(E\) to 1 significant figure.)
2. Write down the output from the algorithm.

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.

8 The diagram shows the curve \(y = \cos ^ { - 1 } x\) for \(- 1 \leqslant x \leqslant 1\). \includegraphics[max width=\textwidth, alt={}, center]{6890a681-2b7f-4853-a5f0-f88b7b435367-4_492_698_1640_671}

1. Write down the exact coordinates of the points \(A\) and \(B\).
2. The equation \(\cos ^ { - 1 } x = 3 x + 1\) has only one root. Given that the root of this equation is \(\alpha\), show that \(0.1 \leqslant \alpha \leqslant 0.2\).
3. Use the iteration \(x _ { n + 1 } = \frac { 1 } { 3 } \left( \cos ^ { - 1 } x _ { n } - 1 \right)\) with \(x _ { 1 } = 0.1\) to find the values of \(x _ { 2 } , x _ { 3 }\) and \(x _ { 4 }\), giving your answers to three decimal places.

3 The equation $$x + ( 1 + 3 x ) ^ { \frac { 1 } { 4 } } = 0$$ has a single root, \(\alpha\).

1. Show that \(\alpha\) lies between - 0.33 and - 0.32 .
2. Show that the equation \(x + ( 1 + 3 x ) ^ { \frac { 1 } { 4 } } = 0\) can be rearranged into the form $$x = \frac { 1 } { 3 } \left( x ^ { 4 } - 1 \right)$$
3. Use the iteration \(x _ { n + 1 } = \frac { \left( x _ { n } ^ { 4 } - 1 \right) } { 3 }\) with \(x _ { 1 } = - 0.3\) to find \(x _ { 4 }\), giving your answer to three significant figures.

2 A curve is defined by the equation \(y = \left( x ^ { 2 } - 4 \right) \ln ( x + 2 )\) for \(x \geqslant 3\).
The curve intersects the line \(y = 15\) at a single point, where \(x = \alpha\).

1. Show that \(\alpha\) lies between 3.5 and 3.6.
2. Show that the equation \(\left( x ^ { 2 } - 4 \right) \ln ( x + 2 ) = 15\) can be arranged into the form $$x = \pm \sqrt { 4 + \frac { 15 } { \ln ( x + 2 ) } }$$ (2 marks)
3. Use the iteration $$x _ { n + 1 } = \sqrt { 4 + \frac { 15 } { \ln \left( x _ { n } + 2 \right) } }$$ with \(x _ { 1 } = 3.5\) to find the values of \(x _ { 2 }\) and \(x _ { 3 }\), giving your answers to three decimal places.
   (2 marks)

1

1. Use Simpson's rule with 7 ordinates (6 strips) to find an estimate for \(\int _ { 0 } ^ { 3 } 4 ^ { x } \mathrm {~d} x\).
2. A curve is defined by the equation \(y = 4 ^ { x }\). The curve intersects the line \(y = 8 - 2 x\) at a single point where \(x = \alpha\).
   1. Show that \(\alpha\) lies between 1.2 and 1.3.
   2. The equation \(4 ^ { x } = 8 - 2 x\) can be rearranged into the form \(x = \frac { \ln ( 8 - 2 x ) } { \ln 4 }\). Use the iterative formula \(x _ { n + 1 } = \frac { \ln \left( 8 - 2 x _ { n } \right) } { \ln 4 }\) with \(x _ { 1 } = 1.2\) to find the values of \(x _ { 2 }\) and \(x _ { 3 }\), giving your answers to three decimal places.
      (2 marks)

1

1. Show that the equation \(x ^ { 3 } - 6 x + 1 = 0\) has a root \(\alpha\), where \(2 < \alpha < 3\).
2. Show that the equation \(x ^ { 3 } - 6 x + 1 = 0\) can be rearranged into the form $$x ^ { 2 } = 6 - \frac { 1 } { x }$$ (1 mark)
3. Use the recurrence relation \(x _ { n + 1 } = \sqrt { 6 - \frac { 1 } { x _ { n } } }\), with \(x _ { 1 } = 2.5\), to find the value of \(x _ { 3 }\), giving your answer to four significant figures.
   (2 marks)

   \includegraphics[max width=\textwidth, alt={}]{b8614dd6-2197-40c3-a673-5bef3e3653a5-2_142_116_2560_157}

   \(\_\_\_\_\) \(\_\_\_\_\) \(\_\_\_\_\)