Difficulty manipulating a limit question (secant method)

BomboshMan
Messages
19
Reaction score
0
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∞}\frac{|x<sub>k+1</sub>-x<sub>*</sub>|}{|x<sub>k</sub>-x<sub>*</sub>||x<sub>k-1</sub>-x<sub>*</sub>|} = \frac{|f&#039;&#039;(x<sub>*</sub>)|}{2|f&#039;(x<sub>*</sub>)|},

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{|x<sub>k+1</sub>-x<sub>*</sub>|}{|x<sub>k</sub>-x<sub>*</sub>|<sup>q</sup>} = (\frac{|f&#039;&#039;(x<sub>*</sub>)|}{2|f&#039;(x<sub>*</sub>)|})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 q2 - 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∞} \frac{|x<sub>k+1</sub>-x<sub>*</sub>|}{|x<sub>k</sub>-x<sub>*</sub>|<sup>q</sup>} = \frac{|f&#039;&#039;(x<sub>*</sub>|}{2|f&#039;(x<sub>*</sub>|} x lim_{k\rightarrow∞}\frac{|x<sub>k-1</sub>-x<sub>*</sub>|}{|x<sub>k</sub>-x<sub>*</sub>|<sup>q-1</sup>}

2) I notice that \frac{|...|<sup>q<sup>2</sup></sup>}{|...|<sup>q</sup>|...|} = 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.

Thanks for any help you can give me!
 
Physics news on Phys.org
Fixed your markup so your post is more readable.
BomboshMan said:
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 xk 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 q2 - 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!
 
  • Like
Likes 1 person
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:
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 said:
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?
 
a
 
Last edited:
Jamie Macreigh said:
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.
 
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?
 
Jamie Macreigh said:
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.
 
  • #10
haruspex said:
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??
 
  • #11
Jamie Macreigh said:
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?
 
  • #12
Im not sure what the value of α would be could you shed some light?
 
  • #13
is it 1/β+1 ?
 
  • #14
Jamie Macreigh said:
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.
 
  • #15
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
Jamie Macreigh said:
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##?
 
  • #17
haruspex said:
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
 
  • #18
Jamie Macreigh said:
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?
 
  • #19
haruspex said:
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?
 
  • #20
Jamie Macreigh said:
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.
 
  • #21
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.
 
  • #22
Jamie Macreigh said:
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.
 
  • #23
Jamie Macreigh said:
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 bk 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 bk tend to a limit. That being so, how does the limit of bk relate to the limit of ##b_{k+1}^\alpha b_k##?
 
Back
Top