Does This Sequence Converge to the Fixed Point?

In summary, Homework Equations attempts to find a function which when graphed has a fixed point at the given point. It is easy to prove that the function has a fixed point if the equation for the given point is replaced by x_{n+1} and alpha.
  • #1
GregA
210
0
[SOLVED] Proof of convergence

Homework Statement


Let [itex] \alpha[/tex] be a fixed point of [tex]x = g(x)[/tex] and let [tex](x_n)[/tex] be the sequence generated by the fixed point iteration scheme. Using the first two terms of the Taylor series for
[tex]g(x)[/tex] about [itex]\alpha[/tex] we can get an approximation for [tex]g(x_n)[/tex]:
[itex]g(x_n) = g(\alpha) + (x_n - \alpha)g'(\alpha)[/tex]
(Assuming the terms in the sequence are close to α we have neglected non-
linear terms.)

Show that [itex]|x_n - \alpha| = |x_0 - \alpha||g'(\alpha)|^{n}[/tex] for all n [tex] \geq 1[/tex] hence show that the sequence [tex](x_n)[/tex] converges to [itex]\alpha[/tex] for [tex]g'(x)< 1[/tex]

Homework Equations


The Attempt at a Solution


I'm not so worried about the proving second part (looks obvious if the first part is true) but before trying to prove the first I want to try a couple of examples and see what's happening if I can.
If I suppose that my function [tex] g(x) = \sqrt{x+1}[/tex] then the value of a fixed point [itex] \alpha = \frac{1+\sqrt{5}}{2}[/tex]
Now if I let [tex]x_0 = 2[/tex] and set n = 1 then [tex]x_1 = \sqrt{2+1}[/tex] and I am under the impression that I can now show:
[itex]|\sqrt{3} - \alpha| = |2 -\alpha||\frac{1}{2}(\frac{1}{\sqrt{\alpha+1}})|[/tex]
[tex]\Rightarrow |\sqrt{3} - \frac{1+\sqrt{5}}{2}| = |2 - \frac{1+\sqrt{5}}{2}||\frac{1}{2}(\frac{1}{\sqrt{\frac{1+\sqrt{5}}{2}+1}})|[/tex]
But this is false!...How am I misinterpreting the given statement or what have I done wrong?
Please don't prove the problem for me.
 
Last edited:
Physics news on Phys.org
  • #2
You are right, it is not true- it is only approximately true. After all, you neglected powers higher than the first in the Taylor expansion.

Proving [itex]|x_n- \alpha|=|x_0- \alpha||g'(\alpha)^n[/itex], to first order, by induction, is pretty easy if you replace [itex]g(x_n)[/itex] and [itex]g(\alpha)[/itex] in [itex]g(x_n) = g(\alpha) + (x_n - \alpha)g'(\alpha)[/itex] by [itex]x_{n+1}[/itex] and [itex]\alpha[/itex].
 
Last edited by a moderator:
  • #3
Cheers for that HallsofIvy, it was the presence of an equals sign, not approximately equals that was throwing me; I couldn't see why it should have been true :redface:
 

Related to Does This Sequence Converge to the Fixed Point?

What is "Proof of Convergence: Solved!"?

"Proof of Convergence: Solved!" is a scientific concept that refers to the ability to prove that a system or process will eventually reach a desired outcome or state.

Why is "Proof of Convergence: Solved!" important?

It is important because it allows scientists to predict and understand the behavior of complex systems and processes, which can have real-world applications in fields such as physics, engineering, and computer science.

What are the key components of "Proof of Convergence: Solved!"?

The key components of "Proof of Convergence: Solved!" are a defined starting point or initial conditions, a set of rules or equations that govern the system's behavior, and a proven method or algorithm for reaching the desired outcome.

How is "Proof of Convergence: Solved!" different from "Proof of Convergence"?

The addition of "Solved!" indicates that a solution or method for proving convergence has been found, whereas "Proof of Convergence" simply refers to the concept itself.

What are some real-world examples of "Proof of Convergence: Solved!"?

Some examples include the proof of convergence for the Newton-Raphson method in mathematics, the proof of convergence for the Jacobi method in linear algebra, and the proof of convergence for the gradient descent algorithm in machine learning.

Similar threads

  • Calculus and Beyond Homework Help
Replies
14
Views
657
  • Calculus and Beyond Homework Help
Replies
2
Views
938
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
Replies
1
Views
684
  • Calculus and Beyond Homework Help
Replies
6
Views
380
  • Calculus and Beyond Homework Help
Replies
10
Views
741
  • Calculus and Beyond Homework Help
Replies
13
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
437
  • Calculus and Beyond Homework Help
Replies
2
Views
849
Back
Top