Newton’s Method: Learn It 3

Lumen Learning

Newton’s Method: Learn It 3

Other Iterative Processes

As mentioned earlier, Newton’s method is a type of iterative process. We now look at an example of a different type of iterative process.

Consider a function $F$ and an initial number $x_0$ . Define the subsequent numbers $x_n$ by the formula $x_n=F(x_{n-1})$ .

This process is an iterative process that creates a list of numbers $x_0,x_1,x_2, \cdots ,x_n, \cdots$ . This list of numbers may approach a finite number $x^{*}$ as $n$ gets larger, or it may not.

In the next example, we see an example of a function $F$ and an initial guess $x_0$ such that the resulting list of numbers approaches a finite value.

Let $F(x)=\frac{1}{2}x+4$ and let $x_0=0$ . For all $n \ge 1$ , let $x_n=F(x_{n-1})$ . Find the values $x_1,x_2,x_3,x_4,x_5$ . Make a conjecture about what happens to this list of numbers $x_1,x_2,x_3, \cdots,x_n, \cdots$ as $n\to \infty$ . If the list of numbers $x_1,x_2,x_3, \cdots$ approaches a finite number $x^*$ , then $x^*$ satisfies $x^*=F(x^*)$ , and $x^*$ is called a fixed point of $F$ .

If $x_0=0$ , then

\begin{array}{l} x_{1} = \frac{1}{2} (0) + 4 = 4 \\ x_{2} = \frac{1}{2} (4) + 4 = 6 \\ x_{3} = \frac{1}{2} (6) + 4 = 7 \\ x_{4} = \frac{1}{2} (7) + 4 = 7.5 \\ x_{5} = \frac{1}{2} (7.5) + 4 = 7.75 \\ x_{6} = \frac{1}{2} (7.75) + 4 = 7.875 \\ x_{7} = \frac{1}{2} (7.875) + 4 = 7.9375 \\ x_{8} = \frac{1}{2} (7.9375) + 4 = 7.96875 \\ x_{9} = \frac{1}{2} (7.96875) + 4 = 7.984375 \end{array}

$\begin{array}{l} x_1=\frac{1}{2}(0)+4=4 \\ x_2=\frac{1}{2}(4)+4=6 \\ x_3=\frac{1}{2}(6)+4=7 \\ x_4=\frac{1}{2}(7)+4=7.5 \\ x_5=\frac{1}{2}(7.5)+4=7.75 \\ x_6=\frac{1}{2}(7.75)+4=7.875 \\ x_7=\frac{1}{2}(7.875)+4=7.9375 \\ x_8=\frac{1}{2}(7.9375)+4=7.96875 \\ x_9=\frac{1}{2}(7.96875)+4=7.984375 \end{array}$

From this list, we conjecture that the values $x_n$ approach 8.

Figure 6 provides a graphical argument that the values approach 8 as $n\to \infty$ .

The function F(x) = (1/2)x + 4 is graphed along with y = x. From x0, which appears to be at the origin, a line is drawn to the function F(x) at x1 = F(x0). Then a line is drawn to the right from here to the line y = x, at which point a line is drawn up to x2 = F(x1). Then a line is drawn to the right from here to the line y = x, at which point a line is drawn up to x3 = F(x2). Continuing this process would converge on the two lines’ intersection point at x* = 8. — Figure 6. This iterative process approaches the value $x^*=8$ .

Starting at the point $(x_0,x_0)$ , we draw a vertical line to the point $(x_0,F(x_0))$ . The next number in our list is $x_1=F(x_0)$ . We use $x_1$ to calculate $x_2$ . Therefore, we draw a horizontal line connecting $(x_0,x_1)$ to the point $(x_1,x_1)$ on the line $y=x$ , and then draw a vertical line connecting $(x_1,x_1)$ to the point $(x_1,F(x_1))$ . The output $F(x_1)$ becomes $x_2$ .

Continuing in this way, we could create an infinite number of line segments. These line segments are trapped between the lines $F(x)=\frac{x}{2}+4$ and $y=x$ . The line segments get closer to the intersection point of these two lines, which occurs when $x=F(x)$ .

Solving the equation $x=\frac{x}{2}+4$ , we conclude they intersect at $x=8$ . Therefore, our graphical evidence agrees with our numerical evidence that the list of numbers $x_0,x_1,x_2, \cdots$ approaches $x^*=8$ as $n\to \infty$ .

Watch the following video to see the worked solution to this example.

For closed captioning, open the video on its original page by clicking the Youtube logo in the lower right-hand corner of the video display. In YouTube, the video will begin at the same starting point as this clip, but will continue playing until the very end.

You can view the transcript for this segmented clip of “4.9 Newton’s Method” here (opens in new window).

Consider the function $F(x)=\frac{1}{3}x+6$ . Let $x_0=0$ and let $x_n=F(x_{n-1})$ for $n \ge 2$ . Find $x_1,x_2,x_3,x_4,x_5$ . Make a conjecture about what happens to the list of numbers $x_1,x_2,x_3, \cdots, x_n, \cdots$ as $n\to \infty$ .

Consider the point where the lines $y=x$ and $y=F(x)$ intersect.

$x_1=6, \, x_2=8, \, x_3=\frac{26}{3}, \, x_4=\frac{80}{9}, \, x_5=\frac{242}{27}; \, x^*=9$