Back to the on-screen lesson ·
Replacing the tangent by a chord through the last two points, and the exponent that says how fast a method's error falls — with what it does and does not measure.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to take a secant step, define the order of convergence of a method, read an order off a plot of successive errors, and compare two methods by what they achieve per function evaluation rather than per step.
You can run Newton's method and you know its speed comes from the tangent matching the curve to first order. This lesson asks what happens when the tangent is not available, and gives the vocabulary for comparing the answers.
A method has order $r$ when $|e_{k+1}| \approx C|e_k|^{r}$ near the root. Order $1$ with $C < 1$ is linear, order $2$ is quadratic, and anything strictly between is superlinear. A secant is the straight line through two points of the curve; the difference quotient $\dfrac{f(x_1) - f(x_0)}{x_1 - x_0}$ is its slope, and it is an estimate of $f'$.
Newton's method needs $f'$. Replace it by the slope of the line through the last two points and you get the secant method: $x_{k+1} = x_k - \dfrac{f(x_k)(x_k - x_{k-1})}{f(x_k) - f(x_{k-1})}$. It needs no derivative and only one new evaluation per step, because $f(x_{k-1})$ is already in hand. Its errors satisfy $e_{k+1} \approx C e_k e_{k-1}$ — a product of two errors rather than a square of one — and the exponent $r$ that makes that self-consistent solves $r^{2} = r + 1$: the golden ratio, about $1.618$. That number is the order of convergence, the exponent in $|e_{k+1}| \approx C|e_k|^{r}$. Order is a statement about the rate, so three things it is not: it is not accuracy (a fast method started badly is behind a slow one started well), it is not cost (a step is not a unit of work), and it is not a guarantee of anything at all until the method is close enough for the asymptotic statement to apply. Measure it in practice by plotting $\log|e_{k+1}|$ against $\log|e_k|$: the slope of that line is $r$.
Another way: picture
Draw the chord through your last two points and slide down it to the axis. When the two points are close, the chord is nearly the tangent and the step is nearly Newton's; when they are far apart, it is a cruder model, which is exactly why the method is slower at the start and catches up near the end.
Another way: steps
The most expensive confusion in this lesson is between order and accuracy. A method of order $2$ is not 'more accurate' than one of order $1.6$; it reduces the error faster per step once it is close. Which reaches a tolerance first depends on where each started, on the constant $C$ in front, and above all on what a step costs. The comparison that matters is digits per function evaluation, and on that measure the lower-order method here wins.
$f(x) = x^{2} - 2$ with $x_0 = 1$, $x_1 = 2$ gives $x_2 = \dfrac{1 \times 2 + 2}{1 + 2} = \dfrac43$.
The step for $x^{2} - c$ simplifies.
Then $x_3 = \dfrac{\frac43 \times 2 + 2}{\frac43 + 2} = \dfrac{7}{5}$, and $x_4 = \dfrac{58}{41}$.
Closing in on $1.41421\ldots$
Four steps, four evaluations, five correct digits — and no derivative was ever needed.
Compare: Newton would have used eight.
Successive errors come out as $10^{-2}$, $10^{-4}$, $10^{-8}$.
Each exponent doubles.
So $\log|e_{k+1}| = 2\log|e_k|$, and the slope of that line is $2$.
Order two, measured rather than assumed.
Had they come out $10^{-2}$, $10^{-3}$, $10^{-4}$, the slope would be $1$ and the method linear, whatever the theory promised.
This is the check that catches a double root.
The relation is $e_{k+1} \approx C e_k e_{k-1}$ — a product, not a square.
So the next error is about $10^{-5}$, taking $C$ to be near $1$.
Newton from the same $10^{-3}$ would have given $10^{-6}$ — better, for twice the work.
The secant method is run on $f(x) = x^{2} - 9$ from $x_0 = 2$ and $x_1 = 5$. Fill in the function values, the next iterate, and the value there. Give fractions where a value is not a whole number.
| Point | Value of f there | |
|---|---|---|
| First point | 2 | |
| Second point | 5 | |
| The step's result |
Method A has order of convergence $1.6$ and method B has order $2$. Both are run $5$ steps on the same problem. Which statement is right?
Each method below is run $4$ steps near the root it is converging to. Match each to its order.
| Order 1, with the factor exactly one half whatever the function | Order 2, so the correct digits double each step | Order 1, because the derivative vanishes along with the function | Order about 1.6, for one new evaluation a step | |
|---|---|---|---|---|
| Bisection | ||||
| Newton's method at a simple root | ||||
| Newton's method at a double root | ||||
| The secant method at a simple root |
The secant method on $f(x) = x^{2} - 18$ has $x_0 = 1$ and $x_1 = 3$. What is $x_2$? Give a fraction.
Answer:
The secant method has order $\dfrac{8}{5}$ and uses one new function evaluation a step; Newton's method has order $2$ and uses two, since it also evaluates $f'$. Two secant steps therefore cost exactly what one Newton step costs. What is the effective order of two secant steps? Give a decimal.
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A linearly convergent method divides the error by $2^{2}$ each step, starting from an error of $2^{1}$. The points of $\log_{2}(\text{error})$ against step number lie on a straight line. Give its slope and its value at step zero.
Slope of the line:
Value at step zero:
You can run the secant method, state the order of each root finder you have met, and measure an order from a run. Say in your own words why a higher order does not make a method more accurate.
8. Your turn: the secant method's next error, from errors of $10^{-2}$ and $10^{-3}$, step 3