Simple Fixed Point Iteration for Root-solving

In summary: The fixed point theorem states that a sequence that repeats a certain operation (in my case the square root) will eventually converge to the fixed point of the sequence.
  • #1
Noesis
101
0
I just want to know why in the world this works?

I am speaking about the simple iteration of taking a function, f(x), setting it to 0, f(x) = 0, solving for x in the function and setting it equal to g(x)...and then iterating.

For example the function :f(x) = x^2 +2x - 1

Setting it to 0 and solving for x: x = (1 - 2x)/x

and then you pick a 'guess' and iterate.

Why in the world does the iteration narrow down onto the root? It seems so arbitrary. We just keep plugging in the values, keep iterating on, and it just converges on the root.

Why oh why is this behavior so? Btw, I promise to learn LaTeX soon..so it won't look as funky next time.
 
Physics news on Phys.org
  • #2
Because with each iteration it gets you a bit closer to the root. Even if your guess is inaccurate, iteration will still work, but take longer to converge.The iteration narrows down onto the root because the algorithm in designed to get closer to the root.

Eg Newtons Method to Square Root numbers.

[tex]E=\frac{\frac{N}{E_0} + E_0}{2}[/tex] Where E is the estimate.

The simple theory behind it is, when we divide a number by its root, we get the root again. We when divide it by a number bigger than its root, the result is a number smaller than its square root. When divided by a number smaller than its root, the result is a number bigger than its root.

So the theory is, Say E is less than the root. We divided the number by something less than the root, so we Get a number bigger than the root. By averaging ones bigger and smaller, we get a new approximation, which can be iterated again and again.

It doesn't matter how bad the approximation is, eventually it will converge because the theory behind it is very simple and designs it so.
 
  • #3
If you want to know the arithmetical reasons for all those algorithms to converge to a value, then take a look at:

http://mipagina.cantv.net/arithmetic/rmdef.htm

There you will find the true story about roots solving.

Regards,

Ing. Domingo Gomez
 
Last edited by a moderator:
  • #4
Suppose x is small; do you know an approximate formula for f(a+x)? If you set f(a+x) ~ 0, can you solve for x?

(this may be easier if you forget that you know exactly what f is)
 
  • #5
It doesn't necessarily. For example, if you pick 1/2 as your "estimate", the caculation "blows up" almost immediately. For that to work, your "estimate" must be relatively close to the solution: here that is [itex]-1+\sqrt{2}[/itex] and to work, your initial guess must be larger than 1.

Notice that
[tex]\frac{1-2x}{x}-\frac{1-2y}{y}= \frac{y-2xy-x+2xy}{xy}= \frac{y-x}{xy}[/tex]
As long as xy> 1 (which is certainly true if both x and y are larger than 1), that will be less than y-x. That's a "contraction" map: f(x) is close to f(y) than x is to y. The "Banach fixed point theorem" shows that any sequence iterating a contraction map converges to the fixed point of the map.
 
  • #6
IIRC you must have f'(x) < 1 around your root and initial guess for convergence of the fixed point method.

I "discovered" fixed point iteration by repeatly taking the square root on one of my first calculators.
 

1. What is Simple Fixed Point Iteration?

Simple Fixed Point Iteration is a numerical method used to find the root of a given function. It involves repeatedly applying a fixed transformation to an initial guess until the solution converges to the root.

2. How does Simple Fixed Point Iteration work?

The method involves choosing an initial guess, plugging it into the given function, and then using the resulting value as the next guess. This process is repeated until the difference between two consecutive guesses is within a desired tolerance level, indicating that the solution has converged.

3. What is the convergence criterion for Simple Fixed Point Iteration?

The convergence criterion for this method is that the absolute value of the difference between two consecutive guesses must be less than a certain tolerance level. Typically, this tolerance level is set by the user.

4. What are some advantages of Simple Fixed Point Iteration?

One advantage of this method is its simplicity and ease of implementation. It also converges quickly for well-behaved functions, and it does not require the calculation of derivatives.

5. What are some limitations of Simple Fixed Point Iteration?

This method may fail to converge for certain functions, and the choice of initial guess can greatly affect the convergence rate. It also does not guarantee the convergence to the exact root, only to an approximation within the desired tolerance level.

Similar threads

Replies
1
Views
1K
  • General Math
Replies
1
Views
667
Replies
20
Views
1K
Replies
5
Views
1K
Replies
11
Views
923
Replies
10
Views
877
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
3K
Replies
1
Views
793
Back
Top