Difficulty manipulating a limit question (secant method)

[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.

Homework Statement

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

lim[itex]_{k\rightarrow∞}[/itex][itex]\frac{|x_k+1-x_*|}{|x_k-x_*||x_k-1-x_*|}[/itex] = [itex]\frac{|f''(x_*)|}{2|f'(x_*)|}[/itex],

where x_k are the approximations produced by the secant method.

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

lim[itex]_{k\rightarrow∞}[/itex] [itex]\frac{|x_k+1-x_*|}{|x_k-x_*|^q}[/itex] = ([itex]\frac{|f''(x_*)|}{2|f'(x_*)|}[/itex])^q-1,

where q = (1 + [itex]\sqrt{5}[/itex])/2

Homework Equations

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

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[itex]_{k\rightarrow∞}[/itex] [itex]\frac{|x_k+1-x_*|}{|x_k-x_*|^q}[/itex] = [itex]\frac{|f''(x_*|}{2|f'(x_*|}[/itex] x lim[itex]_{k\rightarrow∞}[/itex][itex]\frac{|x_k-1-x_*|}{|x_k-x_*|^q-1}[/itex]

2) I notice that [itex]\frac{|...|^q2}{|...|^q|...|}[/itex] = 1, where ... is for example x_k - 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.

Thanks for any help you can give me!

 

[vela]

Fixed your markup so your post is more readable.

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.

Homework Statement

We're given that, if ##x_*## is the zero of f then (we don't need to prove this),
$$\lim_{k\rightarrow\infty} \frac{\lvert x_{k+1}-x_* \rvert}{\lvert x_k-x_*\rvert \lvert x_{k-1}-x_*\rvert } = \frac{\lvert f''(x_*) \rvert}{2\lvert f'(x_*) \rvert},$$ where x_k are the approximations produced by the secant method.

Assuming the limit on the left hand side exists, show that:
$$\lim_{k\rightarrow\infty} \frac{\lvert x_{k+1}-x_*\rvert}{\lvert x_{k}-x_*\rvert^q} = \left(\frac{\lvert f''(x_*)\rvert}{2\lvert f'(x_*)\rvert}\right)^{q-1},$$ where ##q = (1 + \sqrt{5})/2##.

Homework Equations

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

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\infty} \frac{\lvert x_{k+1}-x_*\rvert}{\lvert x_k-x_*\rvert^q} = \frac{\lvert f''(x_*\rvert}{2|f'(x_*)\rvert} \times \lim_{k\rightarrow\infty} \frac{\lvert x_{k-1}-x_*\rvert}{\lvert x_k-x_*\rvert^{q-1}}$$

2) I notice that
$$\frac{\lvert\dots\rvert^{q^2}}{\lvert\dots|^q\rvert\dots|} = 1,$$ where ... is, for example, ##x_k - 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.

Thanks for any help you can give me!

 

[vela]

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.

 

[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##.

 

[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##.

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?

 

[Jamie Macreigh]

a

 

[haruspex]

Im not sure what the value of β is. Could you shed some light on this?

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

 

[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?

 

[haruspex]

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?

Please try to use Latex:
##\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.

 

[Jamie Macreigh]

Please try to use Latex:
##\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.

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

 

[haruspex]

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

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?

 

[Jamie Macreigh]

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

 

[Jamie Macreigh]

is it 1/β+1 ?

 

[haruspex]

is it 1/β+1 ?

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.

 

[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.

 

[haruspex]

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

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##?

 

[Jamie Macreigh]

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##?

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

 

[haruspex]

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

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

 

[Jamie Macreigh]

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

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?

 

[haruspex]

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?

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.

 

[Jamie Macreigh]

Sorry to be a hassle but i really don't see how this is fundamentally going to answer the question which is proving that the limit equals (∣f″(x∗)∣/2∣f′(x∗)∣))^q−1.

 

[haruspex]

Sorry to be a hassle but i really don't see how this is fundamentally going to answer the question which is proving that the limit equals (∣f″(x∗)∣/2∣f′(x∗)∣))^q−1.

Sorry, out of time for the moment. Will respond in about six hours.

 

[haruspex]

Sorry to be a hassle but i really don't see how this is fundamentally going to answer the question which is proving that the limit equals (∣f″(x∗)∣/2∣f′(x∗)∣))^q−1.

We have expressed ##\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##, agreed?
And b_k looks very like the expression inside the limit on the LHS of
##\lim_{k\rightarrow\infty} \frac{\lvert x_{k+1}-x_*\rvert}{\lvert x_{k}-x_*\rvert^q} = \left(\frac{\lvert f''(x_*)\rvert}{2\lvert f'(x_*)\rvert}\right)^{q-1}##, yes?
You are told to assume the limit exists, so the b_k tend to a limit. That being so, how does the limit of b_k relate to the limit of ##b_{k+1}^\alpha b_k##?