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.

Радни пример · newton's method on x^2 - 2 from 1

Numerical-Methods · Root-Finding

Newton's method on x^2 - 2

x^{2} - 2

Корак по корак

  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.

Откриј одговор.
x \approx 1.41421356

Сада ти Изаберите проблем или куцајте или нацртајте своје. Сваки корак, слику, одговор скривен док не питате.

Задржи свој посао.

Бесплатни налог додаје белешке о свакој лекцији, запису о томе шта сте завршили, решавању проблема на једном месту и тутору који можете да питате о овој страници. Сама математика је отворена за све, потписана или не.

Упиши се Пријављивање

Симболи који се овде користе

Додирните било који симбол за пуну дефиницију, слику, и шта значи свако слово у њој.

Како да: 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.

Питања људи постављају

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.

Више у Numerical Methods

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