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.

Umzekelo osebenzelayo · newton's method on x^2 - 2 from 1

Numerical-Methods · Root-Finding

Newton's method on x^2 - 2

x^{2} - 2

Inyathelo ngenyathelo

  1. 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.

  2. f'(x) = 2 x

    Differentiate once; the same derivative serves every iteration.

  3. x_{1} = 1.0 - \frac{-1.0}{2.0} = 1.5

    Iteration 1.

  4. x_{2} = 1.5 - \frac{0.25}{3.0} = 1.41666667

    Iteration 2.

  5. x_{3} = 1.41666667 - \frac{0.00694444}{2.83333349} = 1.41421569

    Iteration 3.

  6. x_{4} = 1.41421569 - \frac{6.01 \cdot 10^{-6}}{2.82843161} = 1.41421356

    Iteration 4.

  7. x_{5} = 1.41421356 - \frac{0.0}{2.82842731} = 1.41421356

    Iteration 5.

  8. x_{6} = 1.41421356 - \frac{0.0}{2.82842731} = 1.41421356

    Iteration 6.

  9. \text{converged}

    The iterates have stopped changing to 12 decimal places.

  10. x \approx 1.41421356

    Quadratic convergence: the number of correct digits roughly doubles each step.

Bonisa impendulo
x \approx 1.41421356

ngoku Khetha ingxaki, okanye ubhale okanye uzobe yakho. Inyathelo ngalinye, umfanekiso, impendulo ifihlakele de ubuze.

Ukugcina umsebenzi wakho

I akhawunti ekhululekileyo idibanisa amaphetshana kwi ncwadi nganye, irekhodi lento ogqibe ngayo, iingxaki zakho ezisoliweyo kwindawo enye, nomfundi onokuthi ubuze malunga nale phepha. IiMathematiki ngokwazo zivuliwe kubo bonke, bangeniswe okanye hayi.

Bhalisa Igama elithile

Iimpawu ezisetyenziswa apha

Nqakraza nasiphi na isibonakaliso sokuqonda okupheleleyo, umfanekiso, nokuba iileta zonke zithetha ntoni.

Indlela yokusebenza: Root finding: bisection and Newton's method

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

Imibuzo abantu bebuza

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.

IiNkqubo Numerical Methods

Numerical integration: trapezoid and SimpsonInterpolation and Taylor approximationFloating point and error