Problem 135 - Thomas Calculus

Question

Sequences generated by Newton's method Newton's method, applied to a differentiable function \(f(x)\) , begins with a starting value \(x_{0}\) and constructs from it a sequence of numbers \(\left\\{x_{n}\right\\}\) that under favorable circumstances converges to a zero of \(f .\) The recursion formula for the sequence is $$x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)}$$ a. Show that the recursion formula for \(f(x)=x^{2}-a, a>0\) can be written as \(x_{n+1}=\left(x_{n}+a / x_{n}\right) / 2 .\) b. Starting with \(x_{0}=1\) and \(a=3,\) calculate successive terms of the sequence until the display begins to repeat. What number is being approximated? Explain.

Step-by-Step Solution

Answer

The sequence approximates \( \sqrt{3} \), converging to approximately 1.73205.

Step 1: Identify Function and Its Derivative

The function given is \( f(x) = x^2 - a \). The derivative of this function is \( f'(x) = 2x \).

Step 2: Use Newton's Method Formula

According to Newton's Method, the recursion formula is \( x_{n+1} = x_{n} - \frac{f(x_n)}{f'(x_n)} \).

Step 3: Substitute Function and Derivative into Formula

Substitute \( f(x_n) = x_n^2 - a \) and \( f'(x_n) = 2x_n \) into the formula: \[x_{n+1} = x_n - \frac{x_n^2 - a}{2x_n} \].

Step 4: Simplify the Expression

Simplify the expression: \[ x_{n+1} = x_n - \frac{x_n^2 - a}{2x_n} = \frac{2x_n^2 - (x_n^2 - a)}{2x_n} = \frac{x_n^2 + a}{2x_n} = \frac{x_n + \frac{a}{x_n}}{2} \].

Step 5: Verify the Formula

We've shown that the Newton's method formula for \( f(x) = x^2 - a \) simplifies to \( x_{n+1} = \frac{x_n + a/x_n}{2} \).

Step 6: Initialize Variables for Sequence Approximation

Start with an initial value \( x_0 = 1 \) and \( a = 3 \). We'll iteratively calculate the sequence values.

Step 7: Calculate Successive Terms Until Repetition

Evaluate: - \( x_1 = \frac{1 + 3/1}{2} = 2 \)- \( x_2 = \frac{2 + 3/2}{2} = 1.75 \) - \( x_3 = \frac{1.75 + 3/1.75}{2} \approx 1.73214 \) - \( x_4 = \frac{1.73214 + 3/1.73214}{2} \approx 1.73205 \) - \( x_5 = \frac{1.73205 + 3/1.73205}{2} \approx 1.73205 \)These values are repeating, indicating convergence.

Step 8: Determine the Approximated Value

The sequence converges to approximately 1.73205, indicating that it approximates \( \sqrt{3} \).

Key Concepts

Sequences

In mathematics, a sequence is a set of numbers arranged in a particular order. Newton's Method involves creating a sequence

• First, you start with an initial guess, called the starting value, often denoted by \(x_0\).
• From this starting point, you generate new numbers by applying a specific formula repeatedly.
• In the case of Newton's Method, the sequence \(\{x_n\}\) represents numbers getting closer to a desired solution.

Sequences are fundamental because they form the backbone of iterative processes like Newton's Method. By observing how the numbers change, you can tell if you're getting closer to the solution.

Derivatives

Derivatives play a key role in Newton's Method.

• A derivative is a mathematical tool that measures how a function changes as its input changes - essentially, it's the function's rate of change.
• In formulas, the derivative of a function \(f\) is usually denoted as \(f'(x)\) or \(\frac{df}{dx}\).
• In Newton's Method, the derivative helps adjust the sequence to make it converge faster to a solution.

For instance, given the function \(f(x) = x^2 - a\), its derivative \(f'(x) = 2x\) tells us how steeply \(f(x)\) is rising or falling at any point \(x\). This steepness guides our step size in each iteration of the sequence, optimizing the path to finding the root.

Convergence

Convergence refers to the behavior of a sequence as it progresses.

• When a sequence converges, its terms get closer and closer to a specific value.
• This specific value is often the solution we seek, such as the square root of a number.
• In Newton's Method, the sequence \(\{x_n\}\) converges to a root of the function \(f(x) = x^2 - a\) under suitable conditions.

Once you notice that the terms are repeating or are getting insignificantly small in difference, you have likely reached convergence. During the execution of Newton's Method, noticing convergence is crucial for stopping the iteration process and arriving at an accurate solution.

Square Root Approximation

Square root approximation is a common use for Newton's Method. This process is useful for finding square roots without a calculator.

• The method uses an iterative approach to approximate the square root of a number \(a\).
• The special form of Newton's Method for square roots is \(x_{n+1} = \frac{x_n + a/x_n}{2}\).
• Starting with a guess such as \(x_0 = 1\), successive iterations bring you closer to \(\sqrt{a}\).

For example, when approximating \(\sqrt{3}\), the sequence quickly converges to the value 1.73205, which is a highly accurate estimate of \(\sqrt{3}\). This method efficiently and rapidly calculates the square roots accurately when done correctly.