From: "Dann Corbit" Subject: Re: Looking for the ugliest possible root-finding problems. Date: Tue, 21 Sep 1999 14:44:39 -0700 Newsgroups: sci.math.num-analysis Steve Stevenson wrote in message news:uuu2oot2ie.fsf@merlin.cs.clemson.edu... > > I would like to collect really nasty root finding problems to test > some ideas on. I know high order polynomials are nasty, but are there > any other standard problems? Functions with lots of local minima that are not roots. [e.g. sin(1e6*x)+1.05 - ((x-a)+.05) Functions which oscillate rapidly [sin(1/x) {near zero is interesting}] Functions which are zero at +/- infinity [e^x, e^(-x)] Functions with really expensive evaluation {roll your own - something that takes more than one second per call} Functions with repeated roots [e.g. f(x) = (x-a)^13 for some root a.] Functions with many roots in close proximity [(x-a)*(x-a+dx)*(x-a+dx)*(x-a+2*dx)*(x-a+3*dx)... for some small dx] -- C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html "The C-FAQ Book" ISBN 0-201-84519-9 C.A.P. Newsgroup http://www.dejanews.com/~c_a_p C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm ============================================================================== From: kovarik@mcmail.cis.McMaster.CA (Zdislav V. Kovarik) Subject: Re: Looking for the ugliest possible root-finding problems. Date: 21 Sep 1999 20:03:16 -0400 Newsgroups: sci.math.num-analysis :Steve Stevenson wrote: : :> I would like to collect really nasty root finding problems to test :> some ideas on. I know high order polynomials are nasty, but are there :> any other standard problems? In article <37E811C6.A7108D3B@ix.netcom.com>, Charles Bond wrote: :It's fairly easy to construct functions which osculate at a solution :point, or functions which are only real at certain points. These make :good test cases for root finders. Realistically, polynomials with :multiple roots constitute one of the best classes of problems. Worse yet: polynomials with near-multiple roots, and other roots away from them (so that the cluster can be seen "in perspective"). Examples; I will list only the coefficients, starting from the top power, so that they can be cut-and-pasted into MATLAB, for example. I did so, to test my typing. (And I invite everyone to find out how I concocted them): [1, -610, 92752, 83326] [44488151, 9324726, -31655387, 8354641] [1950773, 7551423, -1682934, 137445, -4961, 67] [297571, -735878, 682423, -281268, 43473] With geometrically motivated problems, try to find the length of the chord that separates ("scratches") from a unit circular disk one-billionth of the area. Also, find the area of the spherical cap that can be seen from the eye level 1 centimeter above the surface of a perfect sphere of radius 1000 kilometers. The rootfinding is nasty, too, for a different reason. The classic Wilkinson's book "Rounding errors in ..." (I forgot the rest of the title) contains "Wilkinson's Monster", the product of (x-j) for j from 1 to 20, expanded into power form, where tiny perturbations of the huge coefficients mess up the roots, including making some of them complex. There are examples of matrices (20 by 20) whose eigenvalues behave like continuous spectrum under very small perturbations: every number from a solid interval is an eigenvalue of a nearby matrix. And Conte & de Boor have an example of dozens of false roots of the polynomial (x-1)^6, represented by its binomial expansion. Have fun, ZVK(Slavek). ============================================================================== From: Lynn Killingbeck Subject: Re: Looking for the ugliest possible root-finding problems. Date: Tue, 21 Sep 1999 17:30:32 -0500 Newsgroups: sci.math.num-analysis Steve Stevenson wrote: > > I would like to collect really nasty root finding problems to test > some ideas on. I know high order polynomials are nasty, but are there > any other standard problems? > > Best regards, > > steve > -- > Steve (really "D. E.") Stevenson Assoc Prof > Department of Computer Science, Clemson, (864)656-5880.mabell > Support V&V mailing list: ivandv@cs.clemson.edu Try equation 3.0.1 in the 2nd edition of 'Numerical Recipes in C' by Press et al. It clearly goes to infinity as x-->infinity (both + and -), clearly goes to -infinity for x=PI, and clearly is continuous everywhere except at x=PI. So, there are at least two roots, at PI+ and PI-. I have not tried it myself, but seem to recall seeing something like "... negative only in the ridiculously small interval..." Anyway, give it a look. Also, Figure 9.2.3. Lynn Killingbeck ============================================================================== From: gay_nospam@sfu.ca (Ian Gay) Subject: Re: Looking for the ugliest possible root-finding problems. Date: Tue, 21 Sep 99 23:02:49 GMT Newsgroups: sci.math.num-analysis In article , Steve Stevenson wrote: > >I would like to collect really nasty root finding problems to test >some ideas on. I know high order polynomials are nasty, but are there >any other standard problems? > >Best regards, > >steve Suppose you have a root-finding algorithm that works well on smooth functions. I know the algorithm, so given S(x), a smooth function on which your algorithm succeeds, I know all the x values at which your algorithm will evaluate S(x) [and possibly its derivatives]. If I construct U(x) = S(x) + a.sin(bx)exp(-c(x-xo)^2) then by making xo not close to one of the points your algorithm uses on S(x), and making c large, I can make U(x) look like S(x) as far as your algorithm is concerned. If in addition I make a and b large, I can cause U(x) to have many zeroes near xo which your algorithm will not find. *** To reply by e-mail, remove _nospam from address *** ============================================================================== From: Lorenzo Ciampolini Subject: Re: Looking for the ugliest possible root-finding problems. Date: Wed, 22 Sep 1999 10:31:52 +0200 Newsgroups: sci.math.num-analysis Ian Gay wrote: > Suppose you have a root-finding algorithm that works well on smooth functions. I > know the algorithm, so given S(x), a smooth function on which your algorithm > succeeds, I know all the x values at which your algorithm will evaluate S(x) > [and possibly its derivatives]. If I construct > U(x) = S(x) + a.sin(bx)exp(-c(x-xo)^2) then by making xo not close to one of the > points your algorithm uses on S(x), and making c large, I can make U(x) look > like S(x) as far as your algorithm is concerned. If in addition I make a and b > large, I can cause U(x) to have many zeroes near xo which your algorithm will > not find. > That's cute. A general, cute way to measure the algorithm resolution. I would better write down U(x) as (it's just the same with some little more work added) U(x) = S(x) - 2S(xo)cos(b(x-xo))exp(-(x-xo)^2/(2s^2)) Then reduce s until the algorithm fails (because there _must_ be an s for which the algorithm fails) ...Tricks like this are thought to force the best-ever-imagined algorithms to degenerate into brute force hacks ;-) -- Lorenzo Ciampolini Integrated Systems Laboratory Swiss Federal Institute of Technology Zurich Switzerland ============================================================================== From: George Russell Subject: Re: Looking for the ugliest possible root-finding problems. Date: Fri, 24 Sep 1999 12:27:28 +0200 Newsgroups: sci.math.num-analysis Steve Stevenson wrote: > > I would like to collect really nasty root finding problems to test > some ideas on. I know high order polynomials are nasty, but are there > any other standard problems? The following polynomial caused me difficulties some years ago. It has a complete set of real roots between -3 and 3, but you need multiprecision arithmetic to find them all: x**70+10*x**69-53*x**68-840*x**67+556*x**66+33094*x**65+34984*x**64-810448* x**63-1710413*x**62+13762598*x**61+41118204*x**60-170674342*x**59-669408301* x**58+1575702246*x**57+8139304421*x**56-10665563706*x**55-77502451611*x**54+ 48034398976*x**53+594109876080*x**52-71251547216*x**51-3731024648889*x**50- 1001178053674*x**49+19413444795813*x**48+11446048979968*x**47-84277052106156* x**46-73543361870794*x**45+306297652383302*x**44+349025891130844*x**43- 932078784132483*x**42-1315351237260886*x**41+2366040737135922*x**40+ 4054845874713330*x**39-4964744498283827*x**38-10369987468767286*x**37+ 8453136340643513*x**36+22145393335883690*x**35-11223789393426556*x**34- 39564934181149558*x**33+10446958631762445*x**32+59043676220027924*x**31- 3854845422485012*x**30-73250566923653846*x**29-7616116768206834*x**28+ 74930173627345276*x**27+19101242458794555*x**26-62402855648467230*x**25- 24841364734316544*x**24+41498191901443534*x**23+22686040707821384*x**22- 21354816776113940*x**21-15461896367433292*x**20+8022431870339006*x**19+ 7937894514378461*x**18-1902246979654422*x**17-3024034551607022*x**16+ 111526490121324*x**15+823748712357945*x**14+103340846739642*x**13- 149083766521312*x**12-41589180373690*x**11+15031165664405*x**10+7511739940974* x**9-281713434883*x**8-656009832886*x**7-90445245735*x**6+16964659584*x**5+ 6022975080*x**4+598960824*x**3+16371852*x**2-388080*x