# Difficulty manipulating a limit question (secant method)

1. Dec 8, 2013

### BomboshMan

Hey, I'm really struggling with this 'show that' question regarding the secant method, I just keep going in circles and I think I may be heading in completely in the wrong direction because I'm not getting anywhere.

1. The problem statement, all variables and given/known data

We're given that, if x* is the zero of f then (we don't need to prove this),

lim$_{k\rightarrow∞}$$\frac{|xk+1-x*|}{|xk-x*||xk-1-x*|}$ = $\frac{|f''(x*)|}{2|f'(x*)|}$,

where xk are the approximations produced by the secant method.

Assuming the limit on the left hand side exists, show that:

lim$_{k\rightarrow∞}$ $\frac{|xk+1-x*|}{|xk-x*|q}$ = ($\frac{|f''(x*)|}{2|f'(x*)|}$)q-1,

where q = (1 + $\sqrt{5}$)/2

2. Relevant equations

We're given the hint: Use the algebra of limits and the fact that q satisfies q2 - q - 1 = 0

3. The attempt at a solution

I've been going in circles (showing that 1=1 a lot haha) for hours. I haven't been using anything of the secant method, I've just been trying to get from the given limit to the 'show that' limit by algebraically manipulating it, and I haven't been using anything to do with the secant method because it gets very messy when I introduce f into the limit.

The only ideas I have had are:

1) lim$_{k\rightarrow∞}$ $\frac{|xk+1-x*|}{|xk-x*|q}$ = $\frac{|f''(x*|}{2|f'(x*|}$ x lim$_{k\rightarrow∞}$$\frac{|xk-1-x*|}{|xk-x*|q-1}$

2) I notice that $\frac{|...|q2}{|...|q|...|}$ = 1, where ... is for example xk - x*, so we can multiply this by anything without affecting it, as a 'manipulating tool'. Have no idea whether this is useful or not but it uses the hint so thought it might be.

2. Dec 8, 2013

### vela

Staff Emeritus

3. Dec 11, 2013

### vela

Staff Emeritus
Are you allowed to assume that you know the order of convergence for the secant method? In other words, is it already established that you know that
$$\lim_{k \to \infty} \frac{\lvert x_{k+1}-x_* \rvert}{\lvert x_{k}-x_*\rvert^q}$$ is finite and non-zero for the given q? You assumed this fact when you wrote down your first idea.

If you're allowed to do this, try using the fact that
$$\lim_{k\to\infty} \frac{\lvert x_{k-1}-x_*\rvert}{\lvert x_k - x_* \rvert^{q-1}} = \lim_{k\to\infty} \frac{\lvert x_{k}-x_*\rvert}{\lvert x_{k+1} - x_* \rvert^{q-1}}.$$ This is just reindexing the sequence so that $k \to k+1$, which doesn't matter in the limit $k \to \infty$. I don't know if this'll help. It's just a suggestion.

Last edited: Dec 11, 2013
4. Dec 11, 2013

### haruspex

See if you can write
$$\frac{\lvert x_{k+1}-x_* \rvert}{\lvert x_{k}-x_*\rvert \lvert x_{k-1}-x_*\rvert}$$ in the form $b_{k+1}^\alpha b_k$ for some constant $\alpha$.

5. Dec 12, 2013

### haruspex

I guess my hint wasn't strong enough.
Hint 2:
Multiply top and bottom of $$\frac{\lvert x_{k+1}-x_* \rvert}{\lvert x_{k}-x_*\rvert \lvert x_{k-1}-x_*\rvert}$$ by $\lvert x_{k}-x_*\rvert^\beta$. Can you find a value of β that achieves my first hint?

6. Dec 1, 2014

### Jamie Macreigh

a

Last edited: Dec 1, 2014
7. Dec 1, 2014

### haruspex

Do what I said in Hint 2, post #5. Post what you get.

8. Dec 1, 2014

### Jamie Macreigh

I get (∣xk+1−x∗∣*∣xk−x∗∣^β) / (∣xk−x∗∣^β+1)*(∣xk−1−x∗∣)

But I'm not sure where to go from there. Could you assist?

9. Dec 1, 2014

### haruspex

$\frac{∣x_{k+1}−x_∗∣*∣x_k−x_∗∣^β}{ ∣x_k−x_∗∣^{β+1}*∣x_{k−1}−x_∗∣}$
To get that I put \frac{∣x_{k+1}−x_∗∣*∣x_k−x_∗∣^β}{ ∣x_k−x_∗∣^{β+1}*∣x_{k−1}−x_∗∣} inside pairs of hashes, like
HH latex HH​
where H stands for a hash symbol (#).
Look at the two terms (above and below the line) on the right. Suppose you increase k by 1 in each of these. It makes them look a bit like the two terms on the left. Find a value of beta that makes them look very alike.

10. Dec 1, 2014

### Jamie Macreigh

Im afraid im not sure what the value of beta would be. How can the value of β be made to look like the value of β+1??

11. Dec 1, 2014

### haruspex

I didn't say it should look like β+1.
Separate the expression out into two factors as I indicated - the two left hand terms in one, the two right hand in the other.
Increase k by 1 in the right hand factor.
I gave another hint in post #4: now apply a power $\alpha$ to the right hand factor. What value of $\alpha$ turns the right hand factor into the left hand factor?

12. Dec 1, 2014

### Jamie Macreigh

Im not sure what the value of α would be could you shed some light?

13. Dec 1, 2014

### Jamie Macreigh

is it 1/β+1 ?

14. Dec 1, 2014

### haruspex

Do you mean 1/(β+1). If that's what you get then maybe you raised the left hand factor to the power of α to make it look like the right hand? Please post your working.
Anyway, you should get two equations. You need the top right factor to become like the top left, and the lower right factor to become like the lower left. These two equations give specific values for α and β, and the equations should look like that for the given q.

15. Dec 1, 2014

### Jamie Macreigh

To get the top right to look like the top left you raise it to the power 1/β
To get the bottom right to look like the bottom left you raise to the power β+1

Im failing to see how this helps to answer the question though.

16. Dec 1, 2014

### haruspex

Right, but you want it to be the same power in order to apply my first hint in the thread. What does that tell you about $\beta$?

17. Dec 1, 2014

### Jamie Macreigh

Right I see so 1/β is equal to β+1 and therefore β^2+β-1=0

18. Dec 1, 2014

### haruspex

Yes. That makes a very simple relationship between beta and q. Can you proceed from there?

19. Dec 1, 2014

### Jamie Macreigh

I think i still need further help. I get that β= -((1+root5)/2) and 0.61803

What does that mean the relationship between β and q is?

20. Dec 1, 2014

### haruspex

I see you're not familiar with the Golden Section.
β= (1-root5)/2. Invert and simplify. Compare with the roots of the equation for q.