Newton’s method and pseudocode: VCE Mathematical Methods Units 3 & 4

Loav · VCE Mathematical Methods · Units 3 & 4

D06 · Differential calculus · Current curriculum

Use a tangent to improve a root estimate, trace the iteration accurately, and explain what an algorithm’s stopping rule actually establishes.

1. Turn the equation into a root problem

Newton’s method is a numerical procedure for solving f(x) = 0. If the original equation is g(x) = h(x), define f(x) = g(x) − h(x) first. The derivative in the iteration must be the derivative of that entire difference. A numerical answer should ultimately be checked in the original equation, especially if rearrangement or domain restrictions could introduce misleading candidates.

The method starts from an estimate x₀ and repeatedly constructs a new estimate. It often converges quickly when the starting point is suitably close to an appropriate root, but this is not guaranteed. The initial estimate, the function’s shape and its domain all matter. Graphical information can help locate a suitable starting region; it does not replace verifying the final numerical result.

2. Derive the update from the tangent

At the current estimate xₙ, the tangent to y = f(x) passes through (xₙ, f(xₙ)) and has gradient f′(xₙ). Its equation is y − f(xₙ) = f′(xₙ)(x − xₙ). Newton’s method takes the x-intercept of this tangent as the next estimate. Set y = 0 and solve for x, assuming the gradient is non-zero.

The correction f(xₙ)/f′(xₙ) combines the current vertical discrepancy with the tangent’s slope. If the function is well approximated by that tangent near the root, the intercept is a better estimate. The curve’s actual root and the tangent’s intercept are not generally identical, so the process repeats. This geometric interpretation also explains why a horizontal tangent creates a problem: it has no useful intercept unless it already lies on the axis.

All values in a single update must use the same current estimate. Calculate f(xₙ) and f′(xₙ), form their quotient and then replace xₙ. Accidentally updating x before evaluating the denominator produces a different algorithm. Writing a separate variable named next is a clear way to keep the sequencing correct.

3. Trace iterations without premature rounding

An iteration table should identify the index n, the current estimate xₙ and, when useful, the residual f(xₙ). The starting value is row zero; x₁ is the result of one update. If a question asks for three iterations, distinguish x₃ from a table containing three displayed rows including the starting value. Off-by-one counting is an algorithmic error even when each arithmetic step is correct.

Retain internal precision and round only displayed values or the final answer. Feeding a rounded table entry back into the next update changes the sequence and can stop its improvement. On a calculator, use a stored variable or previous-answer value rather than repeatedly typing a shortened decimal. When exact fractions are manageable, they can document early steps precisely before switching to numerical evaluation.

4. Read pseudocode as an exact sequence of instructions

Pseudocode describes an algorithm without depending on a particular programming language. Assignment, such as x ← next, replaces the stored value of x; it is not a permanent algebraic equation. A loop repeats a group of instructions, while a condition determines whether to continue. Trace the stored values in their execution order rather than treating all displayed statements as simultaneous equations.

A fixed-count loop is suitable when a question requests a specified number of Newton updates. A tolerance-based loop is suitable when it requests a stopping condition. In either case, the function and derivative must be defined before use. The following version assumes a positive tolerance and a non-negative integer maximum_passes. It checks the residual, guards against a zero derivative and prevents an unlimited loop. Domain means the domain on which the chosen function and required derivative can be evaluated.

input x, tolerance, maximum_passes
passes ← 0
repeat
    if x is outside the valid domain
        output "Invalid estimate" and stop
    end if
    if |f(x)| ≤ tolerance
        output x, passes, "Residual condition met" and stop
    end if
    if passes = maximum_passes
        output "Iteration limit reached" and stop
    end if
    if f′(x) = 0
        output "Zero derivative" and stop
    end if
    next ← x − f(x)/f′(x)
    x ← next
    passes ← passes + 1
end repeat

The residual test comes before division, so an exact root is accepted even if its derivative also happens to be zero. The count increases after each update. If the next estimate leaves the domain, the next pass stops before trying to evaluate the function there. A practical implementation should also detect numerical overflow or non-finite values rather than treating them as ordinary estimates.

5. Understand what the stopping rule measures

The residual |f(x)| measures how close the function value is to zero. The step |xₙ₊₁ − xₙ| measures how much the estimate changed. Neither is automatically the actual input error |x − α|, where α is the true root. A problem may specify one of these tests; implement the given condition exactly and describe the result in the corresponding terms.

A small residual can coexist with a substantial input error when the function is very flat or scaled by a small constant. A tiny step can indicate successful convergence, but it can also reflect limited numerical precision. Checking both the residual and the stability of displayed digits is useful evidence, while an interval known to contain the root can provide an additional accuracy check. Do not turn a numerical stopping rule into a stronger proof than it supplies.

When a condition is |f(x)| > ε, a negative residual of large magnitude must still trigger another iteration. Using f(x) > ε alone would wrongly accept many estimates lying below the axis. Equivalent logical wording is f(x) > ε or f(x) < −ε. The absolute-value form is usually shorter and less error-prone.

6. Newton’s method can fail without the equation failing

A zero derivative makes the update undefined unless the current point already satisfies the root condition. A very small derivative can create a large jump. An estimate can move outside a logarithm’s or square root’s domain, approach the wrong root, move away from a root or cycle between values. These outcomes describe the chosen iteration, not necessarily whether the original equation has a solution.

7. Report the equation, method and checked conclusion

A complete solution states f and f′, the starting value, the update rule and enough iterations to justify the reported approximation or stopping condition. Finish with the requested rounding and domain. If the run fails, name the observed failure and explain why the update cannot continue or converge as required. Avoid reporting the last displayed estimate as a root merely because an iteration limit was reached.

Technology can automate repeated substitution, but it does not choose the intended root, interpret the original context or certify every displayed decimal on its own. Check the result against the original equation and any contextual restrictions. These steps make a numerical method a mathematical solution rather than just a sequence of calculator outputs.

Practice: seven original questions

1. For f(x) = x² − 11 and x₀ = 3, write the Newton update and find x₁ and x₂ exactly.
2. For f(x) = x³ − x − 3 and x₀ = 1.5, find the first Newton estimate exactly and approximately.
3. For ln x = 1 with x₀ = 2, derive the update, calculate x₁ and state the domain restriction.
4. Explain what happens when Newton’s method is started at x₀ = 0 for x³ − 4 = 0. Does this prove that no real root exists?
5. An algorithm repeats while f(x) > 0.001. Explain why this can stop incorrectly and write a suitable absolute-residual condition.
6. Apply Newton’s method to x³ − 5 = 0 from x₀ = 2. Stop at the first estimate satisfying |f(x)| ≤ 0.01. State the number of updates and the stopping estimate.
7. For f(x) = 10⁻⁶(x − 1000), the estimate x = 0 satisfies |f(x)| < 0.01. Explain why this does not mean the input estimate is accurate to 0.01.