Fixed Point Iteration

2 A student is using a shuttle sort algorithm to rearrange a set of numbers into ascending order. Her correct solution for the first three passes is as follows.

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.

6 The equation \(0.5 \ln x - x ^ { 2 } + x + 1 = 0\) has two roots \(\alpha\) and \(\beta\), such that \(0 < \alpha < 1\) and \(1 < \beta < 2\).

1. Use the Newton-Raphson method with \(x _ { 0 } = 1\) to obtain \(\beta\) correct to \(\mathbf { 6 }\) decimal places. Fig. 6.1 shows part of the graph of \(y = 0.5 \ln x - x ^ { 2 } + x + 1\). \begin{figure}[h]
   \includegraphics[alt={},max width=\textwidth]{945883ad-c153-4c51-83d3-978e4c769ed5-06_1112_1156_529_354} \captionsetup{labelformat=empty} \caption{Fig. 6.1}
   \end{figure}
2. On the copy of Fig. 6.1 in the Printed Answer Booklet, illustrate the Newton-Raphson method working to obtain \(x _ { 1 }\) from \(x _ { 0 } = 1\). Beth is trying to find \(\alpha\) correct to 6 decimal places.
3. Suggest a reason why she might choose the Newton-Raphson method instead of fixed point iteration. Beth tries to find \(\alpha\) using the Newton-Raphson method with a starting value of \(x _ { 0 } = 0.5\). Her spreadsheet output is shown in Fig. 6.2. \begin{table}[h]

   \(r\)	\(\mathrm { x } _ { \mathrm { r } }\)
   0	0.5
   1	- 0.40343
   2	\#NUM!

   \captionsetup{labelformat=empty} \caption{Fig. 6.2}
   \end{table}
4. Explain how the display \#NUM! has arisen in the cell for \(x _ { 2 }\). Beth decides to use the iterative formula $$x _ { n + 1 } = g \left( x _ { n } \right) = \sqrt { 0.5 \ln \left( x _ { n } \right) + x _ { n } + 1 }$$
5. Determine the outcome when Beth uses this formula with \(x _ { 0 } = 0.5\).
6. Use the relaxed iteration \(\mathrm { x } _ { \mathrm { n } + 1 } = ( 1 - \lambda ) \mathrm { x } _ { \mathrm { n } } + \lambda \mathrm { g } \left( \mathrm { x } _ { \mathrm { n } } \right)\) with \(\lambda = - 0.041\) and \(x _ { 0 } = 0.5\) to obtain \(\alpha\) correct to \(\mathbf { 6 }\) decimal places.

3 The curve with equation $$y = 5 x - 2 \tan 2 x$$ has exactly one stationary point in the interval \(0 \leqslant x < \frac { 1 } { 4 } \pi\).
Find the coordinates of this stationary point, giving each coordinate correct to 3 significant figures.

6 The curve \(y = \frac { \ln x } { x + 1 }\) has one stationary point.

1. Show that the \(x\)-coordinate of this point satisfies the equation $$x = \frac { x + 1 } { \ln x }$$ and that this \(x\)-coordinate lies between 3 and 4 .
2. Use the iterative formula $$x _ { n + 1 } = \frac { x _ { n } + 1 } { \ln x _ { n } }$$ to determine the \(x\)-coordinate correct to 2 decimal places. Give the result of each iteration to 4 decimal places.

3 The curve with equation $$y = 5 x - 2 \tan 2 x$$ has exactly one stationary point in the interval \(0 \leqslant x < \frac { 1 } { 4 } \pi\).
Find the coordinates of this stationary point, giving each coordinate correct to 3 significant figures.

5

1. Given that \(2 \ln ( x + 1 ) + \ln x = \ln ( x + 9 )\), show that \(x = \sqrt { \frac { 9 } { x + 2 } }\).
2. It is given that the equation \(x = \sqrt { \frac { 9 } { x + 2 } }\) has a single root. Show by calculation that this root lies between 1.5 and 2.0.
3. Use an iterative formula, based on the equation in part (b), to find the root correct to 3 significant figures. Give the result of each iteration to 5 significant figures.

2 \includegraphics[max width=\textwidth, alt={}, center]{faf83d93-40b6-4557-bfd5-f94c67470dfa-2_449_639_388_753} The diagram shows the curve \(y = x ^ { 4 } + 2 x - 9\). The curve cuts the positive \(x\)-axis at the point \(P\).

1. Verify by calculation that the \(x\)-coordinate of \(P\) lies between 1.5 and 1.6.
2. Show that the \(x\)-coordinate of \(P\) satisfies the equation $$x = \sqrt [ 3 ] { \left( \frac { 9 } { x } - 2 \right) }$$
3. Use the iterative formula $$x _ { n + 1 } = \sqrt [ 3 ] { \left( \frac { 9 } { x _ { n } } - 2 \right) }$$ to determine the \(x\)-coordinate of \(P\) correct to 2 decimal places. Give the result of each iteration to 4 decimal places.

7 \includegraphics[max width=\textwidth, alt={}, center]{b9556031-871d-4dd3-9523-e3438a41339f-3_655_685_262_730} The diagram shows the curve \(y = x \mathrm { e } ^ { 2 x }\) and its minimum point \(M\).

1. Find the exact coordinates of \(M\).
2. Show that the curve intersects the line \(y = 20\) at the point whose \(x\)-coordinate is the root of the equation $$x = \frac { 1 } { 2 } \ln \left( \frac { 20 } { x } \right)$$
3. Use the iterative formula $$x _ { n + 1 } = \frac { 1 } { 2 } \ln \left( \frac { 20 } { x _ { n } } \right)$$ with initial value \(x _ { 1 } = 1.3\), to calculate the root correct to 2 decimal places, giving the result of each iteration to 4 decimal places.

7

1. Given that \(\int _ { 1 } ^ { a } \frac { \ln x } { x ^ { 2 } } \mathrm {~d} x = \frac { 2 } { 5 }\), show that \(a = \frac { 5 } { 3 } ( 1 + \ln a )\).
2. Use an iteration formula based on the equation \(a = \frac { 5 } { 3 } ( 1 + \ln a )\) to find the value of \(a\) correct to 2 decimal places. Use an initial value of 4 and give the result of each iteration to 4 decimal places.

3 It is given that \(\int _ { 0 } ^ { a } \left( 3 \mathrm { e } ^ { 2 x } - 1 \right) \mathrm { d } x = 12\), where \(a\) is a positive constant.

1. Show that \(a = \frac { 1 } { 2 } \ln \left( 9 + \frac { 2 } { 3 } a \right)\).
2. Use an iterative formula, based on the equation in (a), to find the value of \(a\) correct to 4 significant figures. Use an initial value of 1 and give the result of each iteration to 6 significant figures. [3]

6. $$\mathrm { f } ( x ) = x - [ x ] , \quad x \geq 0$$ where \([ x ]\) is the largest integer \(\leq x\). For example, \(f ( 3.7 ) = 3.7 - 3 = 0.7 ; f ( 3 ) = 3 - 3 = 0\).

1. Sketch the graph of \(y = \mathrm { f } ( x )\) for \(0 \leq x < 4\).
2. Find the value of \(p\) for which \(\int _ { 2 } ^ { p } \mathrm { f } ( x ) \mathrm { d } x = 0.18\). Given that $$\mathrm { g } ( x ) = \frac { 1 } { 1 + k x } , \quad x \geq 0 , \quad k > 0$$ and that \(x _ { 0 } = \frac { 1 } { 2 }\) is a root of the equation \(\mathrm { f } ( x ) = \mathrm { g } ( x )\),
3. find the value of \(k\).
4. Add a sketch of the graph of \(y = \mathrm { g } ( x )\) to your answer to part (a). The root of \(\mathrm { f } ( x ) = \mathrm { g } ( x )\) in the interval \(n < x < n + 1\) is \(x _ { n }\), where \(n\) is an integer.
5. Prove that $$2 x _ { n } ^ { 2 } - ( 2 n - 1 ) x _ { n } - ( n + 1 ) = 0$$
6. Find the smallest value of \(n\) for which \(x _ { n } - n < 0.05\).

2

1. By sketching a suitable pair of graphs, show that the equation \(\cot 2 x = \sec x\) has exactly one root in the interval \(0 < x < \frac { 1 } { 2 } \pi\).
2. Show that if a sequence of real values given by the iterative formula $$x _ { n + 1 } = \frac { 1 } { 2 } \tan ^ { - 1 } \left( \cos x _ { n } \right)$$ converges, then it converges to the root in part (a).

6

1. By sketching a suitable pair of graphs on the same diagram, show that the equation $$\ln x = 2 \mathrm { e } ^ { - x }$$ has exactly one root.
2. Verify by calculation that the root lies between 1.5 and 1.6.
3. Show that if a sequence of values given by the iterative formula $$x _ { n + 1 } = \mathrm { e } ^ { 2 \mathrm { e } ^ { - x _ { n } } }$$ converges, then it converges to the root of the equation in part (a).
4. Use the iterative formula in part (c) to determine the root correct to 3 significant figures. Give the result of each iteration to 5 significant figures.

10 \includegraphics[max width=\textwidth, alt={}, center]{c1fbc9ef-2dc6-43c3-bc58-179f683c9acf-18_471_686_276_717} The curve \(y = x \sqrt { \sin x }\) has one stationary point in the interval \(0 < x < \pi\), where \(x = a\) (see diagram).

1. Show that \(\tan a = - \frac { 1 } { 2 } a\).
2. Verify by calculation that \(a\) lies between 2 and 2.5.
3. Show that if a sequence of values in the interval \(0 < x < \pi\) given by the iterative formula \(x _ { n + 1 } = \pi - \tan ^ { - 1 } \left( \frac { 1 } { 2 } x _ { n } \right)\) converges, then it converges to \(a\), the root of the equation in part (a). [2]
4. Use the iterative formula given in part (c) to determine \(a\) correct to 2 decimal places. Give the result of each iteration to 4 decimal places.
   If you use the following lined page to complete the answer(s) to any question(s), the question number(s) must be clearly shown.

3

1. By sketching a suitable pair of graphs, show that the equation $$x ^ { 3 } = 11 - 2 x$$ has exactly one real root.
2. Use the iterative formula $$x _ { n + 1 } = \sqrt [ 3 ] { } \left( 11 - 2 x _ { n } \right)$$ to find the root correct to 4 significant figures. Give the result of each iteration to 6 significant figures.

5

1. By sketching a suitable pair of graphs, show that the equation $$\ln x = 2 - x ^ { 2 }$$ has exactly one root.
2. Verify by calculation that the root lies between 1.0 and 1.4 .
3. Use the iterative formula $$x _ { n + 1 } = \sqrt { } \left( 2 - \ln x _ { n } \right)$$ to determine the root correct to 2 decimal places, showing the result of each iteration.

5

1. By sketching a suitable pair of graphs, show that the equation \(\operatorname { cosec } x = 1 + \mathrm { e } ^ { - \frac { 1 } { 2 } x }\) has exactly two roots in the interval \(0 < x < \pi\).
2. The sequence of values given by the iterative formula $$x _ { n + 1 } = \pi - \sin ^ { - 1 } \left( \frac { 1 } { \mathrm { e } ^ { - \frac { 1 } { 2 } x _ { n } } + 1 } \right)$$ with initial value \(x _ { 1 } = 2\), converges to one of these roots.
   Use the formula to determine this root correct to 2 decimal places. Give the result of each iteration to 4 decimal places.

4 The sequence of values given by the iterative formula $$x _ { n + 1 } = \frac { 2 x _ { n } ^ { 2 } + x _ { n } + 9 } { \left( x _ { n } + 1 \right) ^ { 2 } }$$ with \(x _ { 1 } = 2\), converges to \(\alpha\).

1. Find the value of \(\alpha\) correct to 2 decimal places, giving the result of each iteration to 4 decimal places.
2. Determine the exact value of \(\alpha\).

5 The sequence of values given by the iterative formula \(x _ { n + 1 } = \frac { 6 + 8 x _ { n } } { 8 + x _ { n } ^ { 2 } }\) with initial value \(x _ { 1 } = 2\) converges to \(\alpha\).

1. Use the iterative formula to find the value of \(\alpha\) correct to 4 significant figures. Give the result of each iteration to 6 significant figures.
2. State an equation satisfied by \(\alpha\) and hence determine the exact value of \(\alpha\).

2 The sequence of values given by the iterative formula $$x _ { n + 1 } = \frac { 1 } { 5 } \left( 4 x _ { n } + \frac { 306 } { x _ { n } ^ { 4 } } \right)$$ with initial value \(x _ { 1 } = 3\), converges to \(\alpha\).

1. Use this iterative formula to find \(\alpha\) correct to 3 decimal places, showing the result of each iteration.
2. State an equation satisfied by \(\alpha\), and hence show that the exact value of \(\alpha\) is \(\sqrt [ 5 ] { 306 }\).

4 \includegraphics[max width=\textwidth, alt={}, center]{76371b0f-0145-4cc4-a147-27bcd749816a-2_339_1395_1089_374} The diagram shows a semicircle \(A C B\) with centre \(O\) and radius \(r\). The tangent at \(C\) meets \(A B\) produced at \(T\). The angle \(B O C\) is \(x\) radians. The area of the shaded region is equal to the area of the semicircle.

1. Show that \(x\) satisfies the equation $$\tan x = x + \pi$$
2. Use the iterative formula \(x _ { n + 1 } = \tan ^ { - 1 } \left( x _ { n } + \pi \right)\) to determine \(x\) correct to 2 decimal places. Give the result of each iteration to 4 decimal places.

6 \includegraphics[max width=\textwidth, alt={}, center]{8580dddb-cc72-4745-9e0f-1ac641c6506d-2_355_601_1562_772} The diagram shows a sector \(A O B\) of a circle with centre \(O\) and radius \(r\). The angle \(A O B\) is \(\alpha\) radians, where \(0 < \alpha < \pi\). The area of triangle \(A O B\) is half the area of the sector.

1. Show that \(\alpha\) satisfies the equation $$x = 2 \sin x$$
2. Verify by calculation that \(\alpha\) lies between \(\frac { 1 } { 2 } \pi\) and \(\frac { 2 } { 3 } \pi\).
3. Show that, if a sequence of values given by the iterative formula $$x _ { n + 1 } = \frac { 1 } { 3 } \left( x _ { n } + 4 \sin x _ { n } \right)$$ converges, then it converges to a root of the equation in part (i).
4. Use this iterative formula, with initial value \(x _ { 1 } = 1.8\), to find \(\alpha\) correct to 2 decimal places. Give the result of each iteration to 4 decimal places.

6 \includegraphics[max width=\textwidth, alt={}, center]{326d0ea0-8060-4439-8043-3301b281a30f-3_551_519_260_813} In the diagram, \(A\) is a point on the circumference of a circle with centre \(O\) and radius \(r\). A circular arc with centre \(A\) meets the circumference at \(B\) and \(C\). The angle \(O A B\) is equal to \(x\) radians. The shaded region is bounded by \(A B , A C\) and the circular arc with centre \(A\) joining \(B\) and \(C\). The perimeter of the shaded region is equal to half the circumference of the circle.

1. Show that \(x = \cos ^ { - 1 } \left( \frac { \pi } { 4 + 4 x } \right)\).
2. Verify by calculation that \(x\) lies between 1 and 1.5.
3. Use the iterative formula $$x _ { n + 1 } = \cos ^ { - 1 } \left( \frac { \pi } { 4 + 4 x _ { n } } \right)$$ to determine the value of \(x\) correct to 2 decimal places. Give the result of each iteration to 4 decimal places.

5 The equation of a curve is \(y = x \ln ( 8 - x )\). The gradient of the curve is equal to 1 at only one point, when \(x = a\).

1. Show that \(a\) satisfies the equation \(x = 8 - \frac { 8 } { \ln ( 8 - x ) }\).
2. Verify by calculation that \(a\) lies between 2.9 and 3.1.
3. Use an iterative formula based on the equation in part (i) to determine \(a\) correct to 2 decimal places. Give the result of each iteration to 4 decimal places.

6 A curve has equation \(y = x ^ { 3 } \mathrm { e } ^ { 0.2 x }\) where \(x \geqslant 0\). At the point \(P\) on the curve, the gradient of the curve is 15 .

1. Show that the \(x\)-coordinate of \(P\) satisfies the equation \(x = \sqrt { \frac { 75 \mathrm { e } ^ { - 0.2 x } } { 15 + x } }\).
2. Use the equation in part (a) to show by calculation that the \(x\)-coordinate of \(P\) lies between 1.7 and 1.8.
3. Use an iterative formula, based on the equation in part (a), to find the \(x\)-coordinate of \(P\) correct to 4 significant figures. Give the result of each iteration to 6 significant figures.

9 \includegraphics[max width=\textwidth, alt={}, center]{ccadf73b-16f5-463a-8f69-1394839d5325-3_481_483_1434_831} The diagram shows the curves \(y = x \cos x\) and \(y = \frac { k } { x }\), where \(k\) is a constant, for \(0 < x \leqslant \frac { 1 } { 2 } \pi\). The curves touch at the point where \(x = a\).

1. Show that \(a\) satisfies the equation \(\tan a = \frac { 2 } { a }\).
2. Use the iterative formula \(a _ { n + 1 } = \tan ^ { - 1 } \left( \frac { 2 } { a _ { n } } \right)\) to determine \(a\) correct to 3 decimal places. Give the result of each iteration to 5 decimal places.
3. Hence find the value of \(k\) correct to 2 decimal places.

2 Solve, correct to 3 significant figures, the equation $$\mathrm { e } ^ { x } + \mathrm { e } ^ { 2 x } = \mathrm { e } ^ { 3 x }$$

5

1. By sketching a suitable pair of graphs, show that the equation \(2 + \mathrm { e } ^ { - 0.2 x } = \ln ( 1 + x )\) has only one root.
2. Show by calculation that this root lies between 7 and 9 . \includegraphics[max width=\textwidth, alt={}, center]{656df2a8-fc4d-49f3-a649-746103b4576e-08_2716_40_109_2009}
3. Use the iterative formula $$x _ { n + 1 } = \exp \left( 2 + \mathrm { e } ^ { - 0.2 x _ { n } } \right) - 1$$ to determine the root correct to 2 decimal places. Give the result of each iteration to 4 decimal places. \(\left[ \exp ( x ) \right.\) is an alternative notation for \(\left. \mathrm { e } ^ { x } .\right]\) \includegraphics[max width=\textwidth, alt={}, center]{656df2a8-fc4d-49f3-a649-746103b4576e-10_481_789_262_639} The diagram shows the curve \(y = \sin 2 x ( 1 + \sin 2 x )\), for \(0 \leqslant x \leqslant \frac { 3 } { 4 } \pi\), and its minimum point \(M\). The shaded region bounded by the curve that lies above the \(x\)-axis and the \(x\)-axis itself is denoted by \(R\).

4 You are given the equation \(( 2 x - 1 ) ^ { 2 } - \mathrm { e } ^ { x } = 0\).

1. Verify that 0 is a root of the equation. There are also two other roots, \(\alpha\) and \(\beta\), where \(0 < \alpha < \beta\).
2. The iterative formula \(x _ { r + 1 } = \ln \left( 2 x _ { r } - 1 \right) ^ { 2 }\) is to be used to find a root of the equation.
   (a) Sketch the line \(y = x\) and the curve \(y = \ln ( 2 x - 1 ) ^ { 2 }\) on the same axes, showing the roots \(0 , \alpha\) and \(\beta\).
   (b) By drawing a 'staircase' diagram on your sketch, starting with a value of \(x\) that is between \(\alpha\) and \(\beta\), show that this iteration does not converge to \(\alpha\).
   (c) Using this iterative formula with \(x _ { 1 } = 3.75\), find the value of \(\beta\) correct to 3 decimal places.
3. Using the Newton-Raphson method with \(x _ { 1 } = 1.6\), find the root \(\alpha\) of the equation \(( 2 x - 1 ) ^ { 2 } - \mathrm { e } ^ { x } = 0\) correct to 5 significant figures. Show the result of each iteration.

6

1. By sketching a suitable pair of graphs, show that the equation $$\cot x = 2 - \cos x$$ has one root in the interval \(0 < x \leqslant \frac { 1 } { 2 } \pi\).
2. Show by calculation that this root lies between 0.6 and 0.8 .
3. Use the iterative formula \(x _ { n + 1 } = \tan ^ { - 1 } \left( \frac { 1 } { 2 - \cos x _ { n } } \right)\) to determine the root correct to 2 decimal places. Give the result of each iteration to 4 decimal places.

4 The equation \(x ^ { 3 } - x - 3 = 0\) has one real root, \(\alpha\).

1. Show that \(\alpha\) lies between 1 and 2 . Two iterative formulae derived from this equation are as follows: $$\begin{aligned} & x _ { n + 1 } = x _ { n } ^ { 3 } - 3 \\ & x _ { n + 1 } = \left( x _ { n } + 3 \right) ^ { \frac { 1 } { 3 } } \end{aligned}$$ Each formula is used with initial value \(x _ { 1 } = 1.5\).
2. Show that one of these formulae produces a sequence which fails to converge, and use the other formula to calculate \(\alpha\) correct to 2 decimal places. Give the result of each iteration to 4 decimal places.

6 The curve with equation \(y = \frac { 6 } { x ^ { 2 } }\) intersects the line \(y = x + 1\) at the point \(P\).

1. Verify by calculation that the \(x\)-coordinate of \(P\) lies between 1.4 and 1.6.
2. Show that the \(x\)-coordinate of \(P\) satisfies the equation $$x = \sqrt { } \left( \frac { 6 } { x + 1 } \right)$$
3. Use the iterative formula $$x _ { n + 1 } = \sqrt { } \left( \frac { 6 } { x _ { n } + 1 } \right)$$ with initial value \(x _ { 1 } = 1.5\), to determine the \(x\)-coordinate of \(P\) correct to 2 decimal places. Give the result of each iteration to 4 decimal places.

2 The equation \(x ^ { 3 } - 8 x - 13 = 0\) has one real root.

1. Find the two consecutive integers between which this root lies.
2. Use the iterative formula $$x _ { n + 1 } = \left( 8 x _ { n } + 13 \right) ^ { \frac { 1 } { 3 } }$$ to determine this root correct to 2 decimal places. Give the result of each iteration to 4 decimal places.