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.

Eżempju maħdum · newton's method on x^2 - 2 from 1

Numerical-Methods · Root-Finding

Newton's method on x^2 - 2

x^{2} - 2

Pass b'pass

  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.

Jiżvelaw it-tweġiba
x \approx 1.41421356

Issa inti Agħżel problema, jew ittajpja jew iġbed tiegħek stess.Kull pass, stampa, it-tweġiba moħbija sakemm inti tistaqsi.

Żomm tiegħek stess li jaħdmu

Kont b'xejn iżid noti fuq kull lezzjoni, rekord ta' dak li lest, problemi solvuti tiegħek f'post wieħed, u għalliem inti tista' tistaqsi dwar din il-paġna.Il-matematika nnifisha hija miftuħa għal kulħadd, log fil jew le.

Irreġistra issa Login

Simboli użati hawnhekk

Taptap kwalunkwe simbolu għad-definizzjoni sħiħa, stampa, u dak li kull ittra fiha tfisser.

Kif għandek tuża: 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.

Mistoqsijiet li n-nies jistaqsu

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.

Aktar fil Numerical Methods

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