Numerical Analysis/The Secant Method

From testwiki
Jump to navigation Jump to search

The Secant Method

The secant method is an algorithm used to approximate the roots of a given function f. The method is based on approximating f using secant lines.

The Algorithm

The secant method algorithm requires the selection of two initial approximations x 0 and x 1, which may or may not bracket the desired root, but which are chosen reasonably close to the exact root.

Secant Method Algorithm
Given f(x)=0:

Let x0 and x 1 be initial approximations.
Then
Template:Center topxn=xn−1−f(xn−1)xn−1−xn−2f(xn−1)−f(xn−2) Template:Center bottom
where xn is a better approximation of the exact root, assuming convergence.

Repeat iterative step until either

  1. The total number of iterations N is met
  2. A sufficient degree of accuracy, ϵ, is achieved.

Order of Convergence

We would like to be able to find the order of convergence, p, for the secant method. Hence, we want to find some p so that |xn+1−x|≈Cp|xn−x| where C is a constant.

Given a function f, let x be such that f(x)=0 and let xn-1 and xn be approximations to x. Assume x is a simple root and f is twice continuously differentiable (from the assumptions leading to convergence noted on Wikipedia). Let the error at the nth step be denoted by en: en=xn-x. Then we have:

en+1=xn+1−x=xn−f(xn)xn−xn−1f(xn)−f(xn−1)−x=(xn−1−x)f(xn)−(xn−x)f(xn−1)f(xn)−f(xn−1)=en−1f(xn)−enf(xn−1)f(xn)−f(xn−1)=enen−1(f(xn)en−f(xn−1)en−1f(xn)−f(xn−1)).

Since f(x)=0 and recalling that en=xn-x, we can rewrite the last line above as: Template:NumBlk

Next, let's just consider the numerator in (Template:EquationNote). Let F(ω)=f(ω)−f(x)ω−x where ω=...xn−1,xn,xn+1,.... Thus Template:NumBlk

According to the Mean Value Theorem, on [xn-1,xn], there exists some ζn between xn-1 and xn such that F′(ζn)=F(xn)−F(xn−1)xn−xn−1 Template:NumBlk

Now using a Taylor expansion of f(x) around ω, we have Template:NumBlk

Next, we can combine equations (Template:EquationNote), (Template:EquationNote), and (Template:EquationNote) to show that F(xn)−F(xn−1)=(xn−xn−1)2f″(νn).

Returning to (Template:EquationNote), we now have: Template:NumBlk

Again applying the Mean Value Theorem, there exists some ξn in [xn-1,xn] such that f′(ξn)=f(xn)−f(xn−1)xn−xn−1. Then (Template:EquationNote) becomes:

en+1=enen−1f″(νn)2f′(ξn)≈enen−1f″(x)2f′(x).

Next, recall that we have convergence of order p when limn→∞|xn+1−x||xn−x|p=limn→∞|en+1||en|p=μ for some constant μ>0. Our goal is to figure out what p is for the secant method.

Let Sn=|en+1||enp|
⇔|en+1|=Sn|en|p=Sn(Sn−1|en−1p|)p=SnSn−1p|en−1|p2.

Then we have: |en+1||en||en−1|=SnSn−1p|en−1|p2Sn−1|en−1|p|en−1|=SnSn−1p−1|en−1|p2−p−1.

We want limn→∞(SnSn−1p−1|en−1|p2−p−1)=μ, again where μ is some constant. Since Sn and Sn−1p−1 are constants and limn→∞en=0 (assuming convergence) we must have p2−p−1=0. Thus p=1+52≈1.618.[1]

A Numerical Example

The function f(x)=sin⁡x+xex has a root between -3 and -4. Let's approximate this root accurate to four decimal places.

Let x0 = -3 and x1 = -4. Next, using our recurrence formula where
Template:Center topf(x0)=f(−3)=sin⁡(−3)−3e−3≈−0.2905 Template:Center bottom
and Template:Center topf(x1)=f(−4)=sin⁡(−4)−4e−4≈0.6835,Template:Center bottom
we have: Template:Center topx2=x1−f(x1)x1−x0f(x1)−f(x0)=−4−.6835(−4+3.6835+.2905)≈−3.2983.Template:Center bottom

In the next iteration, we use f(x1) = .6835 and f(x2) = .0342 and see that
Template:Center topx3=x2−f(x2)x2−x1f(x2)−f(x1)=−3.2983−.0342(−3.2983+4.0342−.6835)≈−3.2613.Template:Center bottom

Similarly, we can compute x4 and x5. These calculations have been organized in the table below:

i 0 1 2 3 4 5
xi -3 -4 -3.2983 -3.2613 -3.2665 -3.2665

Hence the iterative method converges to -3.2665 after 4 iterations.

Pseudo Code

Below is pseudo code that will perform iterations of the secant method on a given function f. 

Input: x0 and x1
Set y0=f(x0) and y1=f(x1)
Do 
   x=x1-y1*(x1-x0)/(y1-y0)
   y=f(x)
   Set x0=x1 and x1=x
   Set y0=y1 and y1=y
Until |y1|<tol

Exercises

Exercise 1

Find an approximation to 5 correct to four decimal places using the secant method on f(x)=x2−5.

Solution:

We know 5=2.2361.
Let x0 = 2 and x1 = 3. Then f(x0) = f(2) = -1 and f(x1) = f(3) = 4.
In our first iteration, we have:

x2=x1−f(x1)x1−x0f(x1)−f(x0)=3−4(3−24+1)=2.2

In the second iteration, f(x1) = 4, f(x2) = -0.16 and we thus have

x3=x2−f(x2)x2−x1f(x2)−f(x1)=2.2+.16(2.2−3−.16−4)≈2.2333.

Similarly, x3 and x4 can be calculated, and are shown in the table below:

i 0 1 2 3 4 5
xi 2 3 2.2 2.2333 2.2361 2.2361

Thus after 4 iterations, the secant method converges to 2.2361, an approximation to 5 correct to four decimal places.

Exercise 2

Find a root of f(x)=x+ex by performing five iterations of the secant method beginning with x0 = -1 and x1 = 0.

Solution:

1st Iteration: x0 = -1, x1 = 0, f(x0) = -0.63212, and f(x1) = 1. Then
Template:Center topx2=x1−f(x1)x1−x0f(x1)−f(x0)=(−11+.63212)=−.6127Template:Center bottom
2nd Iteration: x1 = 0, x2 = -.6127, f(x1) = 1, and f(x2) = -.07081. Then
Template:Center topx3=x2−f(x2)x2−x1f(x2)−f(x1)=−.6127+.07081(−.6127−.07081−1)=−.57218Template:Center bottom
3rd Iteration: x2 = -.6127, x3 = -.57218, f(x2) = -.07081, and f(x3) = -.00789. Then
Template:Center topx4=x3−f(x3)x3−x2f(x3)−f(x2)=−.57218+.00789(−.57218+.6127−.00789+.07081)=−.5671Template:Center bottom
4th Iteration: x3 = -.57218, x4 = -.5671, f(x3) = -.00789, and f(x4) = 6.7843*10-5. Then
Template:Center topx5=x4−f(x4)x4−x3f(x4)−f(x3)=−.5671−6.7843×10−5(−.5671+.572186.7843×10−5+.00789)=−.56714Template:Center bottom
5th Iteration: x4 = -.5671, x5 = -.56714, f(x4) = 6.7843*10-5, and f(x5) = 5.1565*10-6. Then
Template:Center topx6=x5−f(x5)x5−x4f(x5)−f(x4)=−.56714−5.1565×10−6(−.56714+.56715.1565×10−6−6.7843×10−5)=−.56714Template:Center bottom
Thus after 5 iterations, the method converges to -.56714 as one of the roots of f(x)=x+ex.

Quiz

The following is a quiz covering information presented on the associated secant method page on Wikipedia as well as the current page.

<quiz display=simple> {True or False: The secant method converges faster than the bisection method. |type="()"} + TRUE. - FALSE.

{True or False: The secant method converges faster than Newton's method. |type="()"} - TRUE. + FALSE.


{Check all that apply: The secant method may be less computationally expensive than Newton's method because... |type="[]"} + Newton's method requires evaluating the given function f and its derivative f'. - The secant method requires evaluating the given function f and its derivative f'. - The secant method requires only one new function evaluation in each iteration. - Newton's method requires only one new function evaluation in each iteration.

{Given the function f(x)=x4−x−8, perform 1 iteration of the secant method starting with x0 = 1 and x1 = 2. Then x2 is equal to: |type="()"} - 1.2311 + 1.5714 - 1.6231 - 1.7312

</quiz>

References

Template:Reflist

Template:CourseCat

  1. ↑ http://www.radford.edu/~thompson/Fall10/434/Chapter4/secant_convergence.pdf
Retrieved from "https://en.wikiversity.beta.math.wmflabs.org/w/index.php?title=Numerical_Analysis/The_Secant_Method&oldid=1309"