Numerical methods: Newton-Raphson, iteration, bisection
Most equations have no formula for their roots, so we close in on them step by step. Compare three ways of doing it, see how fast each one gets there, and see how each one can fail.
只想算个结果？ 函数图像计算器
Error against step (log scale)
读数
发生了什么
Newton-Raphson starts at a guess x₀, draws the tangent there and takes the point where it meets the x-axis as the next guess: xₙ₊₁ = xₙ − f(xₙ)/f'(xₙ). Near a simple root it converges quadratically: each error is roughly the square of the one before, so the number of correct digits roughly doubles. It fails if a tangent is horizontal (f'(xₙ) = 0) and it can fall into a cycle.
Fixed-point iteration rearranges f(x) = 0 as x = g(x) and repeats xₙ₊₁ = g(xₙ). On the graph that is up to the curve, across to y = x, and again: a staircase when g' is positive and a cobweb when it is negative. Each step multiplies the error by about |g'(α)| at the root α, so it converges only if |g'(α)| < 1.
Bisection needs only a change of sign: if f(a) and f(b) have opposite signs, a continuous f has a root between them, and testing the midpoint halves the interval every step. It never fails, but it gains just one digit every 3.3 steps.
- Newton-Raphsonxₙ₊₁ = xₙ − f(xₙ) / f'(xₙ)
- Fixed-point iterationxₙ₊₁ = g(xₙ), converges if |g'(α)| < 1
- How fast the error shrinksNewton: eₙ₊₁ ≈ C eₙ² iteration: eₙ₊₁ ≈ |g'(α)| eₙ
考试大纲
- A-Level Maths AQA, Edexcel, OCRlocating roots by change of sign, fixed-point iteration with staircase and cobweb diagrams, the Newton-Raphson method and how each one fails
- First-year numerical analysisorder of convergence
挑战
Predict first: Newton-Raphson on x² − 2 = 0 from x₀ = 1. What are x₁ and x₂, and how many correct digits of √2 does x₄ have? Type your x₁ into the box, check it, then step on.
x₁ = 1 − (1 − 2)/2 = 1.5, x₂ = 17/12 = 1.41667, x₃ = 577/408 = 1.414215686 and x₄ = 1.41421356237469, against √2 = 1.41421356237310. The correct digits go 1, 3, 6, 12: they double each step, which is quadratic convergence. Fixed-point iteration with g(x) = x − (x² − 2)/4 gains only about half a digit a step, because |g'(√2)| = 0.29.
系统地学
GCSE Maths 中讲这个主题的课：先看分步讲解，再做考试风格的题目，每次数字都不同。 课程为英文。
常见问题
How do I use the Newton-Raphson method?
Differentiate f, pick a starting value x₀ close to the root, then repeat xₙ₊₁ = xₙ − f(xₙ)/f'(xₙ) until two successive values agree to the accuracy you need. For x² − 2 from x₀ = 1 the values are 1.5, 1.41667, 1.414216, 1.41421356.
When does Newton-Raphson fail?
When f'(xₙ) = 0 the tangent is horizontal and never meets the x-axis, so the method stops; this happens if you start at a stationary point. Starting near one sends the next value far away. It can also cycle: for x³ − 2x + 2 from x₀ = 0 the values go 0, 1, 0, 1 for ever. A different starting value usually fixes it.
How can I tell whether x = g(x) will converge?
Work out g'(x) near the root. If |g'(α)| < 1 the iteration converges for starting values close enough, a staircase if g'(α) is positive and a cobweb if it is negative. If |g'(α)| > 1 it moves away from the root, however close you start. The smaller |g'(α)|, the faster it converges.
How many steps does bisection need?
Each step halves the interval, so after n steps it has width (b − a)/2ⁿ. To get the root to within 10⁻⁶ from an interval of width 1 you need 2ⁿ > 10⁶, so n = 20 steps. That is about 3.3 steps for each extra decimal place, much slower than Newton but guaranteed whenever there is a change of sign.
How many bisection steps get a root of x³ − x − 1 = 0 on [1, 2] to within 0.001?
After n steps the interval has width 1/2ⁿ. You need 1/2ⁿ ≤ 0.001, so 2ⁿ ≥ 1000 and n ≥ log₂ 1000 ≈ 9.97, which means 10 steps. In Solve for, Bisection steps does this for any a, b and tolerance, and runs the steps on the graph.