Math Is Fun Forum

Au101

Member

Registered: 2010-12-01

Posts: 353

Numerical Methods

Hi guys, I have a question regarding how the iterative method actually works - I don't really understand the mathematical theory behind why it works and I would be really grateful if anybody could explain.

In C3 (Core Mathematics 3 - a British mathematics course studied when we are usually in our final year of pre-university education, or, sometimes our penultimate year) we are taught that:

"To solve an equation of the form:

By an iterative method, rearrange:

Into a form:

And use the iterative formula:

(From 'Heinemann Modular Mathematics for Edexcel AS and A-Level)

So, to exemplify how this works, a question may be something like:

(a) Show that the equation:

Can be arranged in the form:

,

Stating the value of the constant q.

(b) Using the iteration formula:

With:

And the value of q found in part (a), find:

.

Give the value of:

,

To 4 decimal places.

Please note that I know how to do the question - I simply substitute 0.2 into the formula and then substitute the result back in until I reach the required result. My question is not about the question itself - I just thought that it might help you to understand the method, my question is why, mathematically, does this work. I don't understand why this formula should converge on the root of the equation.

If anybody can offer an explanation, I would, as ever, be very grateful .

Many thanks .

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Numerical Methods

Hi Au101;

That form of iteration is very powerful. To do a simple one:

One possible iterative form is:

Which we can treat as a recursive formula.

The first step to see what is happening is to plot the LHS and the RHS and to see where they intersect. That is where the iterative process will finish , hopefully.

To see a plot of this, known as a cobweb plot because of the shape look here:

http://mathworld.wolfram.com/WebDiagram.html

That is a different function than mine but the principle is the same. Notice how the boxes center around the point of intersection.( the root of the equation)

Here is what is happening in that animation.

http://www.math.montana.edu/frankw/ccp/ … /learn.htm

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,583

Re: Numerical Methods

hi AU101,

Not all re-arrangements of an equation do work.  Sometimes the values converge to a point; sometimes they don't.

If you plot y = x and y = g(x) on a graph (a sketch will probably do if it shows gradients reasonably well) you can choose an x as a starting value; go up the the curve g(x) then across to y = x then up to the curve then across ... to see what happens. (for 'up' you may need to substitute 'down' depending on the curve)

If the trace is a staircase approaching the point where the line and curve cross, or a spiral in towards such a point, then the iteration is succeeding.  Otherwise try another re-arrangement.

It is possible to determine whether the rearrangement will converge by checking the gradient of g(x) in the vicinity  of the intersection.  I've forgotten the rules but it has to do with whether dg/dx is > 1 or < 1.  If you sketch a few curves you can work them out for yourself.

Basically what you are doing is

(i)  Choose x1.

(ii) Go up (or down) to find y1 =g(x1).

(iii) Go horizotally to find x2 = y1 on the line y = x.

(iv) Use x2 as the new value and repeat from step (ii), y2 = g(x2) etc ...

If the iterative process gets you nearer to the solution to x = g(x) then 'bingo' you get to it.  If the process diverges, try again with a new re-arrangement.

From memory I think your text book has some examples where one rearrangement works and another doesn't.

Bob

Last edited by Bob (2011-04-17 22:33:19)

---

Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob

Au101

Member

Registered: 2010-12-01

Posts: 353

Re: Numerical Methods

Hmmm thank you very much both of you. I think I've got it now .

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Numerical Methods

Hi Au101;

Glad you got some of it. The most famous iterative form is of course Newton's. It is also the most overused.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.