maths.free › Numerical Methods › Root finding: bisection and Newton's method

Root finding: bisection and Newton's method

Finding where f(x) = 0 to any accuracy, and how fast each method gets there.

Bisection halves an interval that brackets a root: slow but unfailing. Newton follows the tangent line to the axis, quadratic convergence when it works. Picture it: each tangent line landing closer to the root; the points x₀, x₁, x₂ are marked on the graph. Think it: Newton is a fixed-point iteration of x − f/f′, and its speed comes from that map having zero derivative at the root.

Àwọn ààtò àwọn ìṣàmúlò-ètò · newton's method on x^2 - 2 from 1

Numerical-Methods · Root-Finding

Newton's method on x^2 - 2

x^{2} - 2

Àwọn ìṣàmúlò-ètò

f(x) = x^{2} - 2,\quad x_0 = 1
Newton's method: x_{n+1} = x_n − f(x_n)/f′(x_n). Follow the tangent line down to the axis, repeat.
f'(x) = 2 x
Differentiate once; the same derivative serves every iteration.
x_{1} = 1.0 - \frac{-1.0}{2.0} = 1.5
Iteration 1.
x_{2} = 1.5 - \frac{0.25}{3.0} = 1.41666667
Iteration 2.
x_{3} = 1.41666667 - \frac{0.00694444}{2.83333349} = 1.41421569
Iteration 3.
x_{4} = 1.41421569 - \frac{6.01 \cdot 10^{-6}}{2.82843161} = 1.41421356
Iteration 4.
x_{5} = 1.41421356 - \frac{0.0}{2.82842731} = 1.41421356
Iteration 5.
x_{6} = 1.41421356 - \frac{0.0}{2.82842731} = 1.41421356
Iteration 6.
\text{converged}
The iterates have stopped changing to 12 decimal places.
x \approx 1.41421356
Quadratic convergence: the number of correct digits roughly doubles each step.

Fi àwọn àgbèwọlé hàn

x \approx 1.41421356

Nígbà yìí Yan àwọn àkóónú kan, tàbí tẹ̀ àtí kọ́ àwọn àkóónú rẹ̀. Àwọn ìṣàmúlò-ètò gbogbo, àwòrán, àwọn à

Fi iṣẹ́ rẹ̀ pamọ́

A free account adds notes on every lesson, a record of what you have finished, your solved problems in one place, and a tutor you can ask about this page. The maths itself is open to everyone, signed in or not.

Fikún Àwọn Ìṣàmúlò-ètò

Àwọn àmì-ìwé tí a lo níbẹ̀

Tẹ àwọn àmì-ìwé fún ìṣàfarawé fún àwọn ìṣàmúlò-ètò, àwòrán, àti àwọn àmì-ìwé àwọn àmì-ìwé.

Bii o ṣe le: Root finding: bisection and Newton's method

Bracket the root: find a and b with f(a) and f(b) of opposite sign.
For bisection, halve the interval keeping the sign change; each step gains one bit.
For Newton, start inside the bracket and iterate x − f(x)/f′(x).
Stop when successive iterates agree to the precision you need, and confirm f is tiny there.

Àwọn Àtòjọ-ẹ̀yàn

Why not just solve exactly?

Most equations have no closed-form solution at all, and many that do are unusable in practice. A numerical method delivers as many correct digits as you need, and a good one tells you how many that is.

Why can Newton's method fail?

If it starts where the tangent is nearly flat it shoots far away; near a repeated root it slows to a crawl; and with several roots it may land on the wrong one. A bracketing method like bisection is slower but cannot fail.

Diẹ̀ nínú Numerical Methods

Numerical integration: trapezoid and Simpson Interpolation and Taylor approximation Floating point and error