I: Numerical methods flashcards

Topic 10: I: Numerical methods

Locating a root by a change of sign

If f is continuous on [a, b] and f(a) × f(b) < 0, then f(x) = 0 has a root in (a, b).

When can the change-of-sign method fail?

A repeated root or two close roots give no sign change; an asymptote (discontinuity) can give a sign change with no root.

How do you show a root is correct to n decimal places?

Show a change of sign across an interval whose ends both round to that n-decimal-place value (for 1.76 to 2 d.p., use 1.755 and 1.765).

Fixed-point iteration, and staircase and cobweb diagrams

Rearrange f(x) = 0 to x = g(x) and use xₙ₊₁ = g(xₙ). On y = x and y = g(x) the iterates form a staircase (approaching from one side) or a cobweb (alternating sides).

When does fixed-point iteration converge?

From a start close to the root α, it converges when −1 < g′(x) < 1 near α. Otherwise it diverges, and another rearrangement may work.

Newton–Raphson formula

xₙ₊₁ = xₙ − f(xₙ)/f′(xₙ)

Use Newton–Raphson on f(x) = x³ − 5 with x₁ = 2 to find x₂ and x₃.

f′(x) = 3x². x₂ = 2 − 3/12 = 1.75. x₃ = 1.75 − 0.359375/9.1875 = 1.7109 (4 d.p.), approaching ∛5 ≈ 1.7100.

When does Newton–Raphson fail?

When f′(xₙ) = 0 (the tangent is horizontal), or when a start near a stationary point sends the next value far from the root.

Trapezium rule

∫ₐᵇ y dx ≈ (h/2)[y₀ + yₙ + 2(y₁ + … + yₙ₋₁)], h = (b − a)/n, with n strips and n + 1 ordinates.

Is the trapezium rule an overestimate or an underestimate?

Convex curve (bends upwards): overestimate. Concave curve (bends downwards): underestimate. More strips give a better estimate.