More on the Bisection Method

Error analysis and convergence for bisection method

Ok here is a basic summary of the error analysis associated with the bisection method. Let $$\delta$$ be the required tolerance and let $$e_{n}$$ be the error after the nth iteration.
Then as the bisection method  reduces the error by 1/2 at each iteration  interval, we have the basic recurrence relation $$e_{n+1}=\frac{1}{2}e_{n}$$



As this is linearly dependent  on the previous error the convergence is linear (unlike Newton Rhapshon) and can be comparatively slow to higher order methods as hopefully I will be able to show when I consider the Newton Rhapshon method.

So in terms of the original error e = |a-b|  (where a and b) are the points of the original interval, we have after n iterations
$$e_{n+1}=\frac{|a-b|}{2^n}$$    (2)
Now if $$\delta$$  is the desired tolerance then we can use equation 2 to get an estimate of how many iterations it will take to reach the tolerance call this N. So we have
$$\delta > \frac{|a-b|}{2^N}$$
Rearranging gives
$$2^N >\frac{|a-b|}{\delta}$$
Taking logarithms (it doesn't matter which)
gives$$N log2 > log|a-b| - log{\delta}$$ or
$$N>log|a-b|-log{\delta}$$
So if |a-b| = 1 say and $$\delta=0.5 . 10^{-5}$$
then $$N >\frac{log1-log{\delta}}{log2}$$
or N > 17.6

Hence the number of iterations it takes to converge to less than $$\delta$$  is 18.
I checked this for various intervals and amazingly it worked each time.
I love the way in this method it's the interval that determines the convergence it has nothing to do with the function at all. Simple and Brilliant.

Cambridge Computing Projects 1 Root finding Bisection Method

This is just a short post on the current status of the Cambridge projects, there are about 18 members so far and counting. Four are active and others are just lurking for now which is fine.

We have started to look at the first project, automated root search, ie to find where f(x) = 0 , and their associated errors. There are three methods:

1) Bisection
2) Direct Iteration (which we have covered in MS221)
3) Newton Rhapshon (again which we have covered in MS221)

In this post I will discuss the method of Bisection. This  is really quite clever and simple. If an interval [a,b]
brackets a root of a function f(x0),  then f(a) and f(b) must have different signs, so that the product f(a)f(b) is less than zero. Let c lie half way  between a and b ie c = 1/2(a+b), Then evaluate the function at c

Now if f(a)f(c) < 0 then the root lies in the interval [a,c], else it lies in the interval [c,b]. Replace a or b accordingly and then bisect the new interval. Keep doing this until the error |a-b| is less than a predefined tolerance, then f(c) is the root of the function within that defined tolerance.

The convergence of the error is linear, as can be seen as follows. Given that the method guarantees that the root lies within a given interval, then the error for a given interval must be no greater than

                          e < |a-b|

As the error is halved for each interval, we must have the error at the n+1 th step is given by

                      e(n+1) = 1/2e(n).                       

 As this is linearly dependent on the previous error, the convergence is said to be linear. Whilst the method is guaranteed to work, provided the intial interval brackets the root,  it is in fact much preferable to have faster convergence. Of the techniques described above the Newton Rhapshon method has quadratic convergence provided the root is simple. I shall discuss this later, in the mean time I was able to write a simple programme to implement the method. The initial guess, being enabled, by getting the code to plot out the function before selecting the interval. Anyway a good start, I've nearly finished the Direct iteration method and I'll post the results of that next week, Looks like I'm in a good position to finish the initial project by the end of September.

This weekend I also completed the 6th TMA for M208 this was relatively straightforward the topics covered were as follows:

1) A question on limits and continuity including a basic question on the epsilon delta definition of continuity which I'm begining to like mainly via practice.

2) Questions on differentiability from the definition. Found the first part a bit tricky as it was a quotient and applying the definition directly led to a complete mess, so I was forced to follow the derivation of the differentiability of the quotient rule. Got there in the end but can't help think that there was an easier way.

3) Questions on partitions and lower and upper sums for a discontinuous function, alright provided you take care as to where the function is defined. Then (at last) some real calculus involving integration by substitution and derivation of a recurrence relation.

4) Questions on Taylor series, prior to embarking on the Cambridge Computing projects, this would have seemed a bit dry, but given that Taylor expansions form the basis of most numerical techniques, it has taken on a whole new interest. Those of my fellow students who are bored with Taylor series and haven't already enrolled on the Cambridge projects might like to enlist even just as a lurker.

Anyway really must get to grips with TMA04 for Complex Variables over the next week, I'm giving myself Monday and Tuesday of the week after next off, so hopefully will have finished it by then.

Also started to read Hume's enquiry in preparation for my Edinburgh Philosophy course, he has an interesting phrase for applied maths which he calls mixed maths. It's a joy to read and I'm looking forward to studying it in depth.



  

M337 TMA03 Back and Plans for next year

Got my third TMA for M337 back up in the higher end of grade 2 so consistent with my other TMA's. Just couldn't see how to do a question on analytic continuation, my tutor has given me some clues so I'll try and do that question again. Nearly finished TMA06 for M208 hopefully I'll polish it off over the weekend and I want to get stuck in to the final TMA for M337 which I hope to finish by the end of next week.

Anyway plans for next year have crystallised As already stated I'll be doing
M338 Topology
M336 Group theory and Geometry

and also
MS324 Waves, Diffusion and  Variational Principles

Also I'll be doing a little philosophy I'm registered for a course on David Hume at Edinburgh University Dept Continuing Education this courses counts for 10 CATS points and so is equivalent to 10 OU points.

Next year I'll be doing two more philosophy courses from Oxford University dept continuing education

http://www.conted.ox.ac.uk/courses/results.php?Category=100#rightcontent

Namely Epistemology and Philosophy of science again these are 10 points.

Come October I shall be doing

M381 Number theory and Logic
MST326 Fluid Dynamics and Mathematical methods
and the OU Philosophy of mind course.

So by June 2013 I should have finished my undergraduate studies in both Philosophy and Mathematics and then we'll see. I want to do the MSc in maths but I haven't quite worked out how to continue my philosophy studies. The Open University is not the only university to change it's course structure. Lampeter University has now been amalgamated into St Davids university and their philosophy courses have changed their structure they now offer three courses:

An MA in European philosophy (Kant, Nietszche, Foucault, the Frankfurt school etc). An MA in general philosopy and  an MA in Applied Philosophy. I'm leaning towards the European philosophy course,

http://www.trinitysaintdavid.ac.uk/en/courses/postgraduatecourses/maeuropeanphilosophy/

as St David's have a large track record of providing distance learning MA's and PhD's it would seem the best place to do philosophy. That would take 3-4 years alongside the 4 years I envisage to do the MSc in maths

I feel that whilst Contintental philosophy is usually frowned upon by most Anglo - American philosophy as it's supposed to be nonsense eg A J Ayer once dismissed Existentialism as a misuse of the verb to be. It deals with more concrete issues than current analytic philosophy. Also I get the feeling that Analytic philosophy suffers from 'Science envy' it's trying to do science without actually being scientific.

Also, it's not clear to me that analytic philosophy is immune from nonsense,. There is a large school of thought stemming from Lewis that takes the idea of all possible worlds having an existence. This has had (in my view) a pernicious influence in the philosophy of science especially enshrined in the Many Worlds interpretation of quantum mechanics. I find incredible that this idea is taken seriously however that is the current state of play.

I'm not convinced that I can understand mathematics or the foundations of physics better by studying the philosophy of it any more than I'm doing now. Also I want philosphy to represent another side of my personality.

 Given the current failure of capitalism it seems to me that the insights of the Critical school be it either French (Foucault etc) or German (Habermas, Adorno, Horkheimer etc) have something to offer and it would be worth trying to understand their ideas. 

In the next post I'll talk about the Cambridge Computing project which has about 12 recruits. Hopefully on Sunday evening

And now for something Completely different, Shakespeare (King John)

As a break from TMA's and maths I have decided to try and watch all the Shakespeare plays over the next year. An exercise I first did about 5 years ago when I invested in the superlative BBC TV series, first broadcast in the 1980's which covered all the then known Shakespeare plays  and which got me hooked when they were first broadcast. At the risk of sounding like Polonius from Hamlet I have grouped the plays as follows and this will be the order in which I watch them

History Part 1            (Comical Historical As Polonius would say)
King John
Richard II
Henry IV Part I
Henry IV Part II
The Merry Wives of Windsor
Henry V


Early Comedies                        (Just Comical)
Two Gentlemen of Verona
The Taming of the Shrew
The Comedy of Errors
Loves Labours Lost
A Midsummer Nights Dream

Early Tragedies (What Polonious would call Tragical Comical)
Titus Androndicus
Romeo and Juliet
Merchant of Venice (I refuse to class this as a comedy as was originally done)
Timon of Athens

History Part II                (Whilst this is the Chronological Order it should be noted that Shakespeare wrote  these before Richard II - Henry V )
Henry VI part 1
Henry VI part II
Henry VI part III
Richard III
Henry VIII.

Later Comedies                   
Much Ado about Nothing
As You like it
Twelfth Night

The 'Problem Plays' (Comical Problematical as Polonius might have said)
Troilus and Cressida
Measure for Measure
All's Well that Ends Well

The Roman Tragedies (Classical Historical as Polonius might have said)
Coriolanius
Julius Caesar
Anthony and Cleopatra

The Major Tragedies (The Big 4)
Macbeth
Othello
Hamlet
King Lear

The Pastoral (Autumnal) Plays
Pericles Prince of Tyre
A Winters Tale
Cymbeline
The Tempest.

Since the series was produced, Two Noble Kinsman, has now been attributed to Shakespeare.
Anyway last night I watched King John with Leonard Rossiter (Best known for his comedy series The rise and fall of Reggie Perrin) in the title role Despite this background there is no hint of comedy in this role at all. An unusual and not particularly well known play wirtten in about 1595.

It opens with King John being told that his claim to the throne is under threat from France (where else). He is asked to intervene in a dispute between two brothers the younger of which claims the inheritance as the elder is illegitmate. It turns out that the Elders father was no less than Richard the Lionheart, he (Faulconbridge) is persuaded to give up his claim and Join with John in the wars against France. Faulconbridge then becomes a 'chorus' commenting on the action to the audience as the play develops.

The second Act begins outside the walls of Angiers with John facing the King of France (Philip). Philip has been persuaded to take up the cause of Constance who's son Arthur (A young boy) has a claim to the English Crown as he is the son of John's other elder brother. The leader of Angiers says he will  swear allegience to whoever wins the battle. After two inconclusive battles John and Philp are persuaded by Faulconbridge to turn their arms against Angiers and then resume their fight. After some deft thinking the leader of Angiers persuades Philip and John to let John's niece Blanche and Philip's son the Dauphin marry thus sealing a lasting peace between France and England (and thus dissolving Arthurs claim to the throne). Blanche and the Dauphin are married and all seems well until a Papal legate enters the scene. The Pope is annoyed that King John has not appointed the Popes chosen bishop as Archbishop of Canterbury. John's reply to the Pope is quite amazing and worth quoting

                            " Thou canst not Cardinal, devise a name
                               So slight, unworthy, and ridiculous
                               To charge me to an answer, as the Pope.
                               Tell him this tale, and from the mouth of England
                               Add this more: that no Italian priest
                               Shall tithe or toll in our dominions
                               ...
                               So tell the Pope, all reverence set apart
                               To him and his usurped authority "

(It's a shame that David Cameron didn't cite that during the recent Pope's visit I digress)
Anyway to cut a long story short John is excommunicated, England and France resume their war with England winning. John takes away Arthur as a prisoner and persuades one of his lords, Hubert, to make sure he dies Act III ends with the Cardinal persuading the Dauphin that the way lies open for him to take the throne of England.

Act IV begins with Arthur in Prison and Hubert threatening to put out his eyes and murder him. However he relents and heads back to John to try and persuade him that Arthur is indeed dead. The lords revolt especially when the rumour abounds that Arthur has indeed been murdered. John in order to save his skij upbraids Hubert as he believes wrongly that he has murdered eventually Hubert tells John the truth that he has put the boy in hiding. John then persuades the Lords to see for themselves, but alas in the intervening period Arthur has tried to escape and killed himself by jumping from the Tower. The Lords think he has been murdered War ensues and the Dauphin lands on the shore of England. In the meantime John asks the Cardinal for forgiveness and John's excommunication is revoked.  The Cardinal withdraws his support from the Dauphin who has lost all his supplies. He begins to withdraw, but news arrives that John has been poisoned by a monk and the play ends with Johns death.

An interesting play, the context is obviously the continued threat of invasion from Spain, hence the Anti Catholic sentiment. There has been a recent attempt by some scholars to make out that Shakespeare was a closet Catholic I find this hard to believe especially given the Anti-Catholic sentiment in this play
Unlike other of Shakespeares histories (Richard II - Henry V) there is no comic relief and it is highly unlikely that the play is an accurate representation of history. Indeed it is surprising that no mention is made of the Magna Carta or Robin Hood.

Still as one rarely performed it is interesting to see it now and again. I remembered hardly any of this play since I last saw it so obviously not a show stopper. For those 'completists' like myself it is worth seeing but not the best introduction to Shakespeare and probably best got out the way quickly. Richard II next which should be much better I'll keep you informed.

M208 TMA05 Back

Well I was dreading this but I got one of my highest scores so far. I do think my tutor Alan has been quite generous to my astonishment I only dropped 1 mark on the last question. Still my rant against the emphasis on visualisation seems to have sparked off some interest in other people who have been inspired to come up with a non visual way of dealing with rotating flags etc.

The essence appears to be

1) Work out the effects of the symmetry operation of the group in terms of permutations of the areas

2) A colouring can be seen as a mapping from each square to the set of N colours {B,W...}

3) So and this has yet to be clearly defined the number of fixed objects is related to the cycle stucture of the permutation raised to the power of the colours. But you must include all the cycles.

4) One of the guys on the M208 forum Toby has suggested that the nmber of fixed points for a given symmetry operation is
$$ |C|^{nc}$$
where |C| is the number of cycles associatied with each permutation and nc is the number of colours others have been trying to prove or disprove this. My mate Neil thinks he's close to finding a general algorithm
Whatever  the outcome, it's good that people are 'playing' with the Maths and not just desparately trying to find answers to TMA questions.  

M337 Complex Variables TMA03 Away

Well posted the third TMA for M337 Complex Variables and just like the fifth TMA for M208 there were bits in the last question which had me stumped. Anyway a brief resume

1) Questions on Calculus of residues to solve Integrals and series
     Relatively straightforward and a joy to do

2) Questions on zero's, maxima of functions and Inverse Taylor series

     Again tricky but quite straightforward

3) a) A question showing that two series are direct analytic continuations of each other
        What you have to do is show that if the two series have a common region and they take the same values on the region then the series with the larger region can be seen as a diect analytic continuation of each other. However whilst I could see that they had a common region pages and pages of scribbling failed to convince me that the two series were equal on this region.

b) A straightforward application of the residue theorem to solve an Integral

c) The use of Wierstrass's theorem to show that a series is convergent
    Again the method is to a) show that the series is bounded by a sequence of positive terms
                                       b) show that the sequence of positive terms is convergent
   a) was straightforward but I couldn't show that the series of positive terms was convergent it failed as far as
I could see the ratio test and the comparison test.

d) Some straightforward questions on the Gamma function

So should be close to getting full marks for 1 and 2 and about half the avaiable marks for question 3. As there are only three questions I should just scrape a grade two pass.

So I'll give myself a week off to concentrate on
                     a) Cambridge Computing projects
                     b) The variational method in General relativity and it's application to the Robertson
                         Walker metric
                     c) Cubics, quartics and quintics
    I;ve found (yet another) book on Galois theory which takes a nice historical perspective and doesn't get to bogged down in formal detail until the end

http://www.galois-theorie.de/galois-theory.htm

I would probably reccomend this book as the best starting point.

Finally so far have got 8 recruits to the shared activity forum on the Cambridge Computing projects forum