Solving f(x) = 0: bisection, Newton, fixed point
The three iterative root-finding methods: bisection, Newton's method and fixed-point iteration, with when each one works, when it fails, how fast it converges and when to stop.
- 28 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Understand
A few cards from the deck
Bisection method: what is it?
Show the answer
A method that brackets a root of a continuous function in an interval where it changes sign, cuts that interval in two and keeps the half where the sign change remains.
Each pass halves the length of the interval: after n passes it is (b − a)/2ⁿ. The method always converges, but slowly: one more binary digit per pass.
What does this Newton program show for f(x) = x³ − 2x + 2?
```python
def f(x): return x**3 - 2*x + 2
def df(x): return 3*x**2 - 2
x = 0
for _ in range(4):
x = x - f(x) / df(x)
print(x)`- It alternates between 1.0 and 0.0, never converging
- It converges to the real root of f in four passes
- It diverges: the printed values grow at every pass
- It stops on a ZeroDivisionError on the second pass
Show the answer
It alternates between 1.0 and 0.0, never converging
The program prints 1.0, 0.0, 1.0, 0.0. From 0 the tangent crosses the axis at 1; from 1 it crosses back at 0: a cycle. No f′ vanishes here, and another starting point would have worked.
Bisection requires a … function whose values at a and b have …; after n passes, the interval has length ….
Show the answer
Bisection requires a continuous function whose values at a and b have opposite signs; after n passes, the interval has length (b − a)/2ⁿ.
The sign guarantees a root is present (intermediate values), continuity makes the guarantee valid, and each pass halves the length.
Newton's method: what is it?
Show the answer
An iteration that replaces the function by its tangent at the current point and takes as the next iterate the abscissa where that tangent crosses the x-axis: xₙ₊₁ = xₙ − f(xₙ)/f′(xₙ).
Near a simple root, the number of correct digits roughly doubles at each pass, but you need f′ and a starting point close enough to the root.