A tangent suggests a step, but does not guarantee one
To solve , start from a point with . The tangent there is . Setting its height to zero gives
This replaces the curve by its local linear approximation. A tangent intercept can be far away; it may even land where the next derivative is zero. Thus the formula alone does not prove convergence. A useful proof establishes that the iterates are defined, remain in a controlled region, and approach a root. A small residual is also not automatically a small error : one needs information about the slope between and the root .
Definition 4.6.1
(Tangent step, residual and error)
Let be differentiable and let be a root of . For a point with , the tangent step is . The residual at is , which can be computed without knowing . The error at is , which is what we actually want to control but cannot compute directly.
The following claim sounds reasonable, and it is false.
Counterexample mode
Nonzero derivative at every step does not give convergence
Claim: if at every step, the tangent iterates approach a root. Take and . Then and , so . Next and , so . The iterates return to and then repeat forever, with equal to or at each step, never zero. The sequence is a cycle, so it converges to nothing, although does have a real root (since ). The repair is to add hypotheses that control where the iterates go, for example a sign condition on the error as in the next section.
Worked example: approximating
For and , the iteration is
The same computation works for any , so we state it once in general form.
Theorem 4.6.2
(Convergence of the square-root iteration)
Let , , and . Then every is positive, the error satisfies
for all , the sequence is decreasing, and .
Proof
(Square identity, monotonicity, then the limit)
Each is the average of the positive numbers and , so all terms are positive by induction. Using ,
so for every . For such ,
so is decreasing and bounded below by . It converges to some . Passing to the limit in the recurrence (legitimate because ) gives , hence , and forces .
Proof X-ray
Where each hypothesis acts in the square-root proof
The proof has three separate jobs, and each uses a different fact. Positivity of keeps every term positive, which is what allows division by and lets us read the sign of the right side of the error identity. The non-obvious move is the identity itself: writing the new error as a square divided by a positive number turns an apparently two-sided quantity into a one-sided one, so after the first step whatever the starting point. That bound is then used twice, once to make , giving monotonicity, and once to give a lower bound for the monotone limit. The argument closes because the limit satisfies : only then may we divide by in the limit equation, and only then does select the positive root. Without the same proof runs with in place of , and a start at breaks the first step.
The theorem covers the first step of the example, since .
Worked example 4.6.3
(Certified bounds for the square root of 3)
With , the theorem gives , and the error identity makes this strict, because and a nonzero error has a nonzero square. The first steps are and . They are upper bounds for , not merely decimal guesses. To get a rational lower bound, note that implies , so
The interval certifies the error of either endpoint without assuming a decimal value of . Moreover satisfies : once the error is small, the next is controlled by its square. This special identity establishes the rate here; the tangent formula by itself does not establish a rate for every function.
Worked example 4.6.4
(Starting below the root: the square root of 2 from 1)
Take and . Then , which is above because . Next and . From we get , so
The starting point may lie below the root, but every later iterate lies above it.
Worked example 4.6.5
(Edge cases: a negative start and a start at the root)
For and the recurrence is odd in , so and the whole sequence is the negative of the one from ; it converges to . The theorem does not apply, because it needs , and the limit step then selects the negative root. If instead then and the sequence is constant, which is consistent with the identity. The start is excluded, because is undefined.
Quick check
(Why is a lower bound for once ?)
Multiply the inequality by a suitable positive quantity.
Solution · Answer
Since , dividing by gives , and . So . The two numbers and have product , so one lies on each side of .
Quick check
(For , suppose . Bound .)
Use and a simple lower bound for .
Solution · Answer
Since , we have , so . The number of correct digits roughly doubles at each step.
Common mistakes
Common mistake
(Reading a small residual as a small error)
For and the residual is , yet the root is and the error is . The curve is nearly flat near the root, so a tiny value of says little about distance. The conversion from residual to error needs a slope lower bound, as in the exercise below.
Common mistake
(Quoting a decimal instead of a bound)
Writing and calling the iterate accurate does not prove anything. A proof gives an interval whose endpoints are computed from rational numbers, as in .
Practice: residual versus error
Exercise 4.6.6
(Let be continuous on , differentiable on , and satisfy and on . Prove there is exactly one root . If and , bound .)
Core
Solution(3)
- 1
Existence of a root
The intermediate value theorem on gives some with .
- 2
Uniqueness
Key step
If lie in , the mean value theorem gives . So is strictly increasing and has only one root.
Because: A positive lower slope bound makes strictly increasing.
- 3
Convert residual to error
If , the mean value theorem on the interval with endpoints yields ; the case is immediate. Thus . Without the lower slope bound this conclusion need not hold.