Lab 10: Secant and Systems Lab · Numerical Methods

All four methods on the same equation: log of the error against the iteration number. Straight lines are linear convergence; curves bending down are superlinear or quadratic.

Blue and green curves are f₁ = 0 and f₂ = 0; their crossings are the solutions. Change the starting point to reach a different solution.

Secant

Try this

Run it. Compare with the table of Problem 1.
Start from x0 = 0, x1 = 0.5 (same side of the root). Does it still converge?
Count function evaluations and compare with Newton.

All methods

Try this

Run it. Which method needs the fewest iterations? The fewest function evaluations?
Change f to e^x − 3x (and df) with bracket [0, 1] and Newton start 0.5.

Newton for systems

Try this

Run it. How many steps to 1e-10?
Start from (0.5, 2). Which solution do you get?
Change to x² + y = 11, x + y² = 7 from (3.5, 1.5).

Q1 Derive the secant formula from Newton's formula.

Replace

f'(x_n)

by

\frac{f(x_n) - f(x_{n-1})}{x_n - x_{n-1}}

in

x_{n+1} = x_n - f(x_n)/f'(x_n)

, giving

x_{n+1} = x_n - f(x_n)\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}

.

Q2 Find the root of

e^{x} - 3x = 0

near 0.6 by the secant method with

x_0 = 0

,

x_1 = 1

.

x_2 = 0.780203

,

x_3 = 0.496679

,

x_4 = 0.635952

,

x_5 = 0.620560

,

x_6 = 0.619040

,

x_7 = 0.619061

. Root ≈ 0.619061.

Q3 Distinguish the secant method from false position.

Both use the chord formula. False position keeps the pair of points that brackets the root (always converges, may stall); secant always uses the two latest points (no bracket, faster, may diverge).

Q4 Write the Newton iteration for the system

f_1 = x^2 - y - 1 = 0

,

f_2 = x - y^2 + 1 = 0

.

J = \begin{pmatrix} 2x & -1 \\ 1 & -2y\end{pmatrix}

. Solve

J\Delta = -\begin{pmatrix} f_1 \\ f_2\end{pmatrix}

and set

(x, y) \leftarrow (x, y) + \Delta

.

Q5 Which method would you choose, and why: (a)

f

is a noisy measurement; (b)

f

is a polynomial with an easy derivative and a good guess is known; (c)

f

comes from a slow simulation with no derivative?

(a) Bisection: needs only signs, robust to noise. (b) Newton: quadratic,

f'

cheap. (c) Secant (or Brent): no derivative, one evaluation per step, superlinear.