mm-2319 === Subject: Finding an Elliptic Paraboloid verte How many points are necessary to determine a paraboloid with axis parallel to the z axis? Is there an easy formula that link its vertex to the coordinates of the given points? My idea was that starting from the standard paraboloid formula z = A x^2 + B y^2 (A = 1/a^2, B = 1/b^2) and applying a generic rototranslation, we get 6 parameters (A, B, x0, y0, z0, theta), therefore 6 points should be necessary and sufficient. OTOH, deriving the formula for x0, y0, z0 (the values I'm interested in, given the 6 points) seems to involve square roots and alike, so I'm probably doing something wrong. Am I re-inventing the wheel, or should I keep on trying? i.e is there some known formulas to obtain the paraboloid from n points? -- Giuseppe Oblomov Bilotta I weep for our generation -- Charlie Brown === Subject: Re: Finding an Elliptic Paraboloid verte >How many points are necessary to determine a paraboloid with axis >parallel to the z axis? > >Is there an easy formula that link its vertex to the coordinates of >the given points? > >My idea was that starting from the standard paraboloid formula > >z = A x^2 + B y^2 > >(A = 1/a^2, B = 1/b^2) and applying a generic rototranslation, we get >6 parameters (A, B, x0, y0, z0, theta), therefore 6 points should be >necessary and sufficient. OTOH, deriving the formula for x0, y0, z0 >(the values I'm interested in, given the 6 points) seems to involve >square roots and alike, so I'm probably doing something wrong. > >Am I re-inventing the wheel, or should I keep on trying? i.e is there >some known formulas to obtain the paraboloid from n points? > >-- >Giuseppe Oblomov Bilotta > >I weep for our generation -- Charlie Brown you got already the advice how to deal with the interpolation problem. but I guess that in truth your data points are noisy and you have more than 6. then indeed using the interpolation approach may lead to a nonconvex surface as you was afraid of. in that case you have the choice either to introduce nonlinear constraints: model z= 0.5*A*x^2+B*x*y +0.5*C*y^2+D*x+E*y*F A>=eps>0 A*C-B^2>=eps>0 or directly to write it as a nonlinear problem replacing A,B, C by the Cholesky decomposition of [ A B ] [ L11 0 ] [ L11 L21 ] = [ B C ] [ L21 L22] [ 0 L22 ] i.e. replacing 0.5*A*x^2+B*x*y +0.5*C*y^2 by (L11*x+L21*y)^2+L22^2*y^2 and then using a nonlinear u n c o n s t r a i n e d or (even better, if you want uniqueness and strict positive definiteness: bound constraint L11>=eps>0, L22>=eps>0) least squares solver. hth peter === Subject: Re: Finding an Elliptic Paraboloid verte > you got already the advice how to deal with the interpolation problem. > but I guess that in truth your data points are noisy and you have more than 6. > then indeed using the interpolation approach may lead to a nonconvex surface as > you was afraid of. in that case you have the choice > either to introduce nonlinear constraints: > model > z= 0.5*A*x^2+B*x*y +0.5*C*y^2+D*x+E*y*F > A>=eps>0 > A*C-B^2>=eps>0 > or directly to write it as a nonlinear problem replacing A,B, C by the Cholesky > decomposition of > [ A B ] [ L11 0 ] [ L11 L21 ] > = > [ B C ] [ L21 L22] [ 0 L22 ] > i.e. replacing > 0.5*A*x^2+B*x*y +0.5*C*y^2 > by > (L11*x+L21*y)^2+L22^2*y^2 > and then using a nonlinear u n c o n s t r a i n e d or (even better, if you > want uniqueness and strict positive definiteness: bound constraint > L11>=eps>0, L22>=eps>0) least squares solver. convex function, so I expect the result to behave well. I'll keep the suggestion in mind though. Do you per chance know of references to extensions of the parabolic interpolation method for minimum search? -- Giuseppe Oblomov Bilotta I weep for our generation -- Charlie Brown === Subject: Re: Finding an Elliptic Paraboloid verte >> you got already the advice how to deal with the interpolation problem. >> but I guess that in truth your data points are noisy and you have more than 6. >> then indeed using the interpolation approach may lead to a nonconvex surface as >> you was afraid of. in that case you have the choice >> either to introduce nonlinear constraints: >> model >> z= 0.5*A*x^2+B*x*y +0.5*C*y^2+D*x+E*y*F >> A>=eps>0 >> A*C-B^2>=eps>0 >> or directly to write it as a nonlinear problem replacing A,B, C by the Cholesky >> decomposition of >> [ A B ] [ L11 0 ] [ L11 L21 ] >> = >> [ B C ] [ L21 L22] [ 0 L22 ] >> i.e. replacing >> 0.5*A*x^2+B*x*y +0.5*C*y^2 >> by >> (L11*x+L21*y)^2+L22^2*y^2 >> and then using a nonlinear u n c o n s t r a i n e d or (even better, if you >> want uniqueness and strict positive definiteness: bound constraint >> L11>=eps>0, L22>=eps>0) least squares solver. > >convex function, so I expect the result to behave well. I'll keep the >suggestion in mind though. > >Do you per chance know of references to extensions of the parabolic >interpolation method for minimum search? > >-- >Giuseppe Oblomov Bilotta > >I weep for our generation -- Charlie Brown yes, of course. -> uobyqa (powell) -> newuoa (powell) -> dfo (conn,scheinberg,toint) see under no derivatives in http://plato.la.asu.edu/topics/problems/nlounres.html hth peter === Subject: Re: Finding an Elliptic Paraboloid verte > >Do you per chance know of references to extensions of the parabolic > >interpolation method for minimum search? > >-- > >Giuseppe Oblomov Bilotta > >I weep for our generation -- Charlie Brown yes, of course. > -> uobyqa (powell) > -> newuoa (powell) > -> dfo (conn,scheinberg,toint) > see under no derivatives in > http://plato.la.asu.edu/topics/problems/nlounres.html -- Giuseppe Oblomov Bilotta I'm never quite so stupid as when I'm being smart --Linus van Pelt === Subject: Re: Finding an Elliptic Paraboloid verte >How many points are necessary to determine a paraboloid with axis >parallel to the z axis? Six. (I will interpret determine in the same sense you do.) >Is there an easy formula that link its vertex to the coordinates of >the given points? My idea was that starting from the standard paraboloid formula z = A x^2 + B y^2 (A = 1/a^2, B = 1/b^2) and applying a generic rototranslation, we get >6 parameters (A, B, x0, y0, z0, theta), therefore 6 points should be >necessary and sufficient. OTOH, deriving the formula for x0, y0, z0 >(the values I'm interested in, given the 6 points) seems to involve >square roots and alike, so I'm probably doing something wrong. You're going to let a little thing like square roots drive you away? Write your paraboloid in the form z = A x^2 + 2C xy + B y^2 + D x + E y + F. Use six points (x_i, y_i, z_i) selected at random to solve for A through F. Set the gradient equal to zero to find x0 y0 z0. Use A,B,C to determine theta. dave === Subject: Re: Finding an Elliptic Paraboloid verte >How many points are necessary to determine a paraboloid with axis >>parallel to the z axis? Six. (I will interpret determine in the same sense you do.) >Is there an easy formula that link its vertex to the coordinates of >>the given points? >>My idea was that starting from the standard paraboloid formula >>z = A x^2 + B y^2 >>(A = 1/a^2, B = 1/b^2) and applying a generic rototranslation, we get >>6 parameters (A, B, x0, y0, z0, theta), therefore 6 points should be >>necessary and sufficient. OTOH, deriving the formula for x0, y0, z0 >>(the values I'm interested in, given the 6 points) seems to involve >>square roots and alike, so I'm probably doing something wrong. You're going to let a little thing like square roots drive you away? Write your paraboloid in the form z = A x^2 + 2C xy + B y^2 + D x + E y + F. > Use six points (x_i, y_i, z_i) selected at random to solve for A through F. > Set the gradient equal to zero to find x0 y0 z0. > Use A,B,C to determine theta. What I was in doubt of was if that equation was indeed guaranteed to be an elliptic paraboloid. That's why I was trying to go the hard -- Giuseppe Oblomov Bilotta Hic manebimus optime === Subject: Correct way to handle sigma=0 in Levenberg Marquardt I am implementing the LEvenberg Marquardt method as detailed in Numerical Recipes. However, I'm wondering what to do when the error associated with a given data point is zero. This gives a signular matrix in the Gauss Jordan elimination step, and also causes a divide-by-zero when calculating chi-squared. Such data points could easily arise in any situation where Poissonian statistics occur, and no events were observed (sqrt(0.0) is zero). Am I being really dumb and missing something obvious? Jonathan. === Subject: Re: Correct way to handle sigma=0 in Levenberg Marquardt > >I am implementing the LEvenberg Marquardt method as detailed in >Numerical Recipes. However, I'm wondering what to do when the error >associated with a given data point is zero. This gives a signular >matrix in the Gauss Jordan elimination step, and also causes a >divide-by-zero when calculating chi-squared. Such data points could >easily arise in any situation where Poissonian statistics occur, and no >events were observed (sqrt(0.0) is zero). Am I being really dumb and >missing something obvious? > >Jonathan. > you already got the answer that your assumptions are incorrect. but if in some situation you indeed have sigma=0 (exact relation, no noise) then this means that you have a least squares problem with linear equality side constraints. there are several software solutions for this, see e.g. http://plato.la.asu.edu/topics/problems/nlolsq.html hth peter === Subject: Re: Correct way to handle sigma=0 in Levenberg Marquardt I am implementing the LEvenberg Marquardt method as detailed in >Numerical Recipes. However, I'm wondering what to do when the error >associated with a given data point is zero. This gives a signular >matrix in the Gauss Jordan elimination step, and also causes a >divide-by-zero when calculating chi-squared. Such data points could >easily arise in any situation where Poissonian statistics occur, and no >events were observed (sqrt(0.0) is zero). Am I being really dumb and >missing something obvious? Jonathan. > I don't have a solution, but I do have some comments: 1. In the case you mention, Poisson statistics, the error is never really zero. Just because no events were observed, it doesn't mean that, if the experiment were continued indefinitely, you would never see any events. 2. Strictly speaking, sigma should be estimated from the theoretical curve instead of from the experimental measurements. 3. Least-squares assumes Gaussian (normal) error at each point, which a Poisson distribution approximates if N is sufficiently large. Some (e.g. Louis Lyons, Statistics bins so that N is always greater than 5. Olin Perry Norton === Subject: Linearizing a nonlinear equation (damped oscillation) y = A*exp(-B*x)*sin(C*x) + D Is there any way to linearize the above expression, which I'd like to use in a quick and dirty fitting procedure? In general, are there any techniques that one can use for transforming one's problem? Obviously one can log when there's an exp but for more complicated expressions it's not clear. === Subject: Re: Linearizing a nonlinear equation (damped oscillation) > y = A*exp(-B*x)*sin(C*x) + D Is there any way to linearize the above expression, which I'd like to > use in a quick and dirty fitting procedure? In general, are there any > techniques that one can use for transforming one's problem? Obviously > one can log when there's an exp but for more complicated expressions > it's not clear. Not sure whether it works very well... Your equation resembles much the solution of a linear recurrence of order 2: y(n) = a*y(n-1) + b*y(n-2) + c You can find a,b,c by linear regression, then solve the recurrence (very easy). Maybe you won't find exactly the same formula as above (I would expect a cosine, too). === Subject: Re: Linearizing a nonlinear equation (damped oscillation) >y = A*exp(-B*x)*sin(C*x) + D Is there any way to linearize the above expression, which I'd like to >use in a quick and dirty fitting procedure? In general, are there any >techniques that one can use for transforming one's problem? Obviously >one can log when there's an exp but for more complicated expressions >it's not clear. I don't know of any way to linearize it. But, here is a way you might perform a quick & dirty fitting: 1. First, estimate D. If your data series is long enough to see the complete decay of the damped oscillation, you should be able to determine D from the constant value of y that remains. Even if this is not true, if you have many cycles of the oscillation, then the average value of y should be close to D. 2. Then, subtract D from your signal. Now, you should be able to use a FFT to find the dominant frequency, which will give you an estimate of C. 3. Now, we need to estimate the A*exp(-B*x) term. This is called the envelope. Basically, what you want to does. (Someone who knows about digital signal processing would be a good person to talk with.) One way to do this is to take the Hilbert transform of your data, and generate the quadrature signal. (The quadrature signal is 90 degrees out of phase with the original; hence, the quadrature signal for cos(x) is sin(x), and (sin(x))^2+(cos(x))^2=1, so by squaring and adding the original signal and the quadrature signal, you can recover the envelope A*exp(-B*x). 4. Then, you should be able to take the logarithm and fit the exponential decay envelope to find A and B. 5. If these estimates aren't good enough, maybe they'll at least be close enough that you can get some nonlinear fitting procedure to converge at the right answer, using these values as a starting point. I believe that this quick and dirty method assumes that the exponential damping is slow enough that several cycles of is the audio signal, which can be assumed to be a sum of sine and cosine waves. In that case, it is important that the carrier frequency is much higher than the audio frequencies that are present.) By all means I would plot my data, and then plot the results of this fitting procedure. It's not going to be infallible. This method should work if your oscillation is underdamped, and your data record is long enough to contain a number of oscillation cycles. The Hilbert transform referred to here is the convolution of the signal with the function 1/t. As a convolution, it is most efficiently computed in Fourier transform space, but you already have the Fourier transform of your signal, so you're halfway done already. Information on this Hilbert transform can be found in: Bendat, Julius S. and Piersol, Allan G., Random Data; Analysis and Measurement Procedures, 2nd edition, Wiley-Interscience, 1986, pp. 484-516. I have also seen the name Hilbert associated with a completely different integral transform, so watch out. Olin Perry Norton === Subject: Re: Linearizing a nonlinear equation (damped oscillation) Suggestion from a non-specialist : Assuming you've got enough measurement data, here is a quick and dirty fitting : 1/ mean(data(large x)) gives you D 2/ first non zero solution x0 of y=D gives you C=pi/x0 3/ linear regression of log(A)-B*x against log((y-D)/sin(c*x)) gives you A and B v.a. === Subject: Re: Linearizing a nonlinear equation (damped oscillation) > y = A*exp(-B*x)*sin(C*x) + D Is there any way to linearize the above expression, which I'd like to > use in a quick and dirty fitting procedure? In general, are there any > techniques that one can use for transforming one's problem? Obviously > one can log when there's an exp but for more complicated expressions > it's not clear. As the function is not linear it is not clear what you want to do. However, two suggestions: 1) You can linearise it near any point (x0,y0) with a Taylor Series expansion about that point, just retaining the constant and linear term. y = y0 + (x-x0)*dy/dx(x0) 2) If you want a linear approximation in an interval find the two-point Gaussian integration points in that interval, x1 and x2, and put a straight line through (x1,y1) and (x2,y2). === Subject: Statistical Time Series Analysis Toolbox Update Harmonic Software has announced the release of version 2 of STSA, The Statistical Time Series Analysis Toolbox for O-Matrix. This release includes a significant number of additions and enhancements. STSA v2 includes new functions for filtering, optimization, random number generation, and specialized statistics. For more details on what's new see the O-Matrix home page at: http://www.omatrix.com/stsaV2.html The STSA toolbox is a collection of O-Matrix functions for analyzing time-dependent observations (time series). The functions can be used to perform a large variety of different types of analysis, including descriptive and graphical analysis, model identification, fitting and forecasting, residual diagnostic checking, spectral analysis, filtering and smoothing, optimization etc. The functions of the toolbox combine breadth of applications, ease of use and the speed and computing power of O-Matrix to provide you with an integrated working environment for analyzing your time series data. The functions can be easily incorporated into other functions by the user thus limiting the time needed for writing programs or prototyping new routines. The STSA toolbox has functions that cover most of standard time series analysis plus a number of related functions not directly found in the main O-Matrix distribution or related products. The distribution includes numerous examples using real-world and simulated data that is provided and can be used as a starting point for immediately using the power of STSA. Pricing and detailed product information for STSA is available on the O-Matrix home page, http://www.omatrix.com/stsa.html === Subject: Double Logistic Regression I look for any programs or explanations on double logistic regression. === Subject: Interpolation of discrete Chebsyhev polynomials. For my research I need to evaluate Cheb. polynomials. Say, I have a number of these polynomials,p_n, (0,...,n-1) evaluated an a uniform grid (0,...,N-1). This is done not directly by expanding the recurrence equation in n because this becomes unstable. I do this by also using a recurrence expression in x. This gives me the true values of all p_n's at all grid points. If I want to know the value of p_n(x) where x is not on the grid, I can linear interpolate the unkown value between the two neighbouts that are on the grid. But it might be possible to use a more accurate interpolation based on maybe the recurrence equations (in x as in n) and/or the Rodrigues equation. Can some one help me? Gr, Maurice === Subject: Re: Interpolation of discrete Chebsyhev polynomials. Le 29/06/05 13:54, dans a7227$42c28c04$82a1bc06$8575@news1.tudelft.nl, .82æMaurice van de Rijzenæé a .8ecritæ: For my research I need to evaluate Cheb. polynomials. > Say, I have a number of these polynomials,p_n, (0,...,n-1) evaluated an > a uniform grid (0,...,N-1). > This is done not directly by expanding the recurrence equation in n > because this becomes unstable. I do this by also using a recurrence > expression in x. This gives me the true values of all p_n's at all grid > points. > If I want to know the value of p_n(x) where x is not on the grid, I can > linear interpolate the unkown value between the two neighbouts that are > on the grid. But it might be possible to use a more accurate > interpolation based on maybe the recurrence equations (in x as in n) > and/or the Rodrigues equation. > Can some one help me? Gr, > Maurice If it isn't too expensive, you could use cos(n*acos(t)) for |t| < 1, cosh(n*acosh(t)) for t > 1, and (-1)^n*cosh(n*acosh(-t)) for t < -1. === Subject: Re: Interpolation of discrete Chebsyhev polynomials. > >Le 29/06/05 13:54, dans a7227$42c28c04$82a1bc06$8575@news1.tudelft.nl, >.82æMaurice van de Rijzenæé a .8ecritæ: > >> >> For my research I need to evaluate Cheb. polynomials. > Say, I have a number of these polynomials,p_n, (0,...,n-1) evaluated an >> a uniform grid (0,...,N-1). >> This is done not directly by expanding the recurrence equation in n >> because this becomes unstable. I do this by also using a recurrence >> expression in x. This gives me the true values of all p_n's at all grid >> points. >> If I want to know the value of p_n(x) where x is not on the grid, I can >> linear interpolate the unkown value between the two neighbouts that are >> on the grid. But it might be possible to use a more accurate >> interpolation based on maybe the recurrence equations (in x as in n) >> and/or the Rodrigues equation. >> Can some one help me? >> >> Gr, >> Maurice > >If it isn't too expensive, you could use cos(n*acos(t)) for |t| < 1, >cosh(n*acosh(t)) for t > 1, and (-1)^n*cosh(n*acosh(-t)) for t < -1. > this might indeed be the fastest method (if n is large, say >=20 ) but it will be unstable. for example t near -1 , n=100 . what do you hope for? using the recurrence relation costs you n multiplications and additions, hence is as fast as Horners scheme and faster than using say Nevilles algorithm (for N>=n)for interpolation. or will you be happy with a cruder aproximation? then interpolation in a table offers you all possibilities to vary the degree and the precision. hth peter === Subject: Re: Interpolation of discrete Chebsyhev polynomials. this might indeed be the fastest method (if n is large, say >=20 ) > but it will be unstable. for example t near -1 , n=100 . > what do you hope for? using the recurrence relation costs you n multiplications > and additions, hence is as fast as Horners scheme and faster than using say > Nevilles algorithm (for N>=n)for interpolation. Becasue of the number of grid-points (200-2000) and the number of orders (up to 25). the coefficients ,a,b,c and in th recurrence equation: p_n(x) = a*x*p_n_1(x) + b*p_n_1(x) + c*p_n_1(x) will become very small and the evalutaions of the monomial terms in the polynomials will become very large (2000^25). So using this directly will be very unstable. Using the book of Nikoforov, also a recurrence equation can be formulated in the x-variable. Doing this the problem of really evaluating terms like 2000^25 will be prevented. The problem, however, is that the functions are then only known on the grid points and need to be interpolated. > or will you be happy with a cruder aproximation? > then interpolation in a table offers you all possibilities to vary the degree > and the precision. A simple linear table-interpolation will be insufficient for the accuracy (I think). Therefore I'm lookfing for better accurate methods. I'm not familier with Neville's algorithm but I will look into it. > hth > peter Gr, Maurice === Subject: Re: Interpolation of discrete Chebsyhev polynomials. > this might indeed be the fastest method (if n is large, say >=20 ) >> but it will be unstable. for example t near -1 , n=100 . >> what do you hope for? using the recurrence relation costs you n multiplications >> and additions, hence is as fast as Horners scheme and faster than using say >> Nevilles algorithm (for N>=n)for interpolation. >Becasue of the number of grid-points (200-2000) and the number of orders >(up to 25). the coefficients ,a,b,c and in th recurrence equation: >p_n(x) = a*x*p_n_1(x) + b*p_n_1(x) + c*p_n_1(x) will become very small >and the evalutaions of the monomial terms in the polynomials will become >very large (2000^25). So using this directly will be very unstable. >Using the book of Nikoforov, also a recurrence equation can be >formulated in the x-variable. Doing this the problem of really >evaluating terms like 2000^25 will be prevented. The problem, however, >is that the functions are then only known on the grid points and need to >be interpolated. order<=25 ? why not using this: t0=1; t1=x; zx=x+x; for {i=2; i<=n; i++} t2=zx*t1-t0; t0=t1; t1=t2; } #cheby_one_n(x)=t2; this is perfectly fast and stable. tabulating 2000 points for representing a polynomial of degree 25, isn't this wasting time and memory? and, of course, use these only for x in [-1,1]. but by a simple linear transformation any compact interval can be transformed to [-1,1] and problems involving polynomial approximations therefore can always be treated taking place in [1,1]. hth peter >> or will you be happy with a cruder aproximation? >> then interpolation in a table offers you all possibilities to vary the degree >> and the precision. >A simple linear table-interpolation will be insufficient for the >accuracy (I think). Therefore I'm lookfing for better accurate methods. >I'm not familier with Neville's algorithm but I will look into it. >> hth >> peter Gr, >Maurice === Subject: Re: The factoring problem > It's not clear what would constitute a satisfactory answer > to such a why?. I suppose that a proof that factoring is > in the class NP-complete would be accepted by many as such > an answer, because that would mean that as the factors are > made arbitrarily large, the amount of work expected for > factoring the product would become larger at such a rate > that it would be impossible to accomplish on any classical > computing device (assuming P!=NP). However, so far as I > know there has never been an accepted proof that factoring > has that asymptotic complexity class, and judging from > progress in factoring algorithms recently it doesn't feel > like an NP-complete problem. In fact, it is believed to be somewhere between 'NP' and 'P': the Number Field Sieve method has complexity O(e^{c(log n)^{1/3}(log log n)^{2/3}}). So as far as we know, factoring is easier than NP-complete problems. Of course, NP = P might still hold anyway :-) See http://mathworld.wolfram.com/NumberFieldSieve.html Jan === Subject: Re: The factoring problem Nntp-Posting-Host: apps.cwi.nl > >> Douglas A. Gwyn a .8ecrit : > I rather doubt that any intuitionist really holds > that a step function is continuous at the steps. >> No : what they say is that step functions have no reality > > Define S(x) as 1 if x >= 0, or 0 if x < 0. > What's unreal about that? > > The problem is not reality - nothing is that real in mathematics - but > constructive proof. I think the problem here is the disctinction between constructionism and intuitionism. They are not exactly the same. In intuitionism the law of the excluded middle is abandoned, but that is all. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: The factoring problem > I think the problem here is the disctinction between constructionism and > intuitionism. They are not exactly the same. In intuitionism the law > of the excluded middle is abandoned, but that is all. However, there is a connection. Without excluded middle, existential quantifiers become problematic, thus so do theorems involving infinities. To prove: There exists an x in S such that P Proof: Assume there is no such x in S; then ... contradiction. Therefore there must be such an x (law of excluded middle on P). === Subject: Re: The factoring problem > I think the problem here is the disctinction between constructionism and > intuitionism. They are not exactly the same. In intuitionism the law > of the excluded middle is abandoned, but that is all. > > However, there is a connection. Without excluded middle, > existential quantifiers become problematic, thus so do > theorems involving infinities. Not all, there are theorems about infinities that do not require such quantifiers. I think the theorem that |P(S)| is strictly larger than |S| is fully constructive (but that depends on the kind of constructivism you are talking about). On the other hand, there are intuitionists that add axioms for some of those cases (and those axioms may violate the law of the excluded middle). And with one of those axioms all functions from R into R become differentiable everywhere, also step functions (I think). I am just reading a book about it, it is pretty informative because it surrects, in a way, the original dx and dy notation, but now with good foundation. -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131 home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ === Subject: Re: The factoring problem Archive: no >> I think the problem here is the disctinction between constructionism and >> intuitionism. They are not exactly the same. In intuitionism the law >> of the excluded middle is abandoned, but that is all. However, there is a connection. Without excluded middle, > existential quantifiers become problematic, thus so do > theorems involving infinities. > To prove: There exists an x in S such that P > Proof: Assume there is no such x in S; then ... > contradiction. Therefore there must be > such an x (law of excluded middle on P). Wrong. The problem ist to proof when we can exclude middle or not. For example: This sentence is wrong. It's wrong exactly when it's right. Solution: The truth of this sentence cannot be expressed within the language of formal logic. -- Dieser Schrieb stellt eine private Meinungs.8au€erung des Verfassers im Sinne der gesetzlich garantierten Meinungsfreiheit dar. Wem das nicht passt, der wende sich an das Bundesverfassungsgericht. Viel Erfolg! Key: 0xA0E28D18 FP: 83AE 1136 1E2B 9767 8FB2 7594 4128 1A9E A0E2 8D18 === Subject: question about zeroes of polynomials dear all, I have the following problem. We have a polynomial Q(x) of degree 3+N in x: Q(x):= x^(3+N)-rho*3*x^(2+N)+rho*3*x^(1+N)-rho*x^N + rho*(x-1)^3*P(x) with P(x) any polynomial of degree N-1 and rho a real number. If N=2 for instance, P(x) looks like P(x)=a*x+b, and we obtain that Q is of degree 5. If N=1, P(x) is just a nonzero constant. If N=0, P(x)=0. Now it is easy to see that if rho=1, 1 is a triple root of Q (3 of the 3+N roots are equal to 1). The question I have now is what happens with these three special roots if we perturb rho a little bit towards zero. So if rho is not 1 but 1-delta (with delta real, positive and approximately 0, so f.i.0.0000001). Of course, these three roots that were originally 1 might become complex then, such as 1.0000010201193+0.1846304081e-5*I. The thing I would really like to prove is that at least one of these three roots (that were 1 if rho was 1), becomes larger than 1 in absolute value (modulus) if rho is slightly perturbed in the way described above. I thought it should be possible to prove this using some kind of perturbation on rho or the roots (where we write f.i. rho=1+delta and can then neglect some higher order terms in delta) but I do not seem to get this kind of formulation right. Can anyone help me out? Christophe === Subject: Re: question about zeroes of polynomials >I have the following problem. We have a polynomial Q(x) of degree 3+N in x: Q(x):= x^(3+N)-rho*3*x^(2+N)+rho*3*x^(1+N)-rho*x^N + rho*(x-1)^3*P(x) with P(x) any polynomial of degree N-1 and rho a real number. If N=2 >for instance, P(x) looks like P(x)=a*x+b, and we obtain that Q is of >degree 5. If N=1, P(x) is just a nonzero constant. If N=0, P(x)=0. Now it is easy to see that if rho=1, 1 is a triple root of Q (3 of the >3+N roots are equal to 1). The question I have now is what happens with >these three special roots if we perturb rho a little bit towards zero. >The thing I would really like to prove is that at least one of these >three roots (that were 1 if rho was 1), becomes larger than 1 in >absolute value (modulus) if rho is slightly perturbed in the way >described above. I think that's automatic, at least if P(1) isn't equal to -1. With P and N fixed, you've got an algebraic curve here, defined by the equation Q(x,rho) = 0. As you point out, there's a singular point at (x,rho) = (1,1), and near this point Q expands to (1 + P(1)) (x-1)^3 - (rho-1) + higher-order terms. So you can solve for x in terms of rho locally using a Puiseux series: (x-1) = [1/(1+P(1))]^(1/3) (rho-1)^(1/3) + ... (It's an infinite series in powers of (rho-1)^(1/3) .) There are three possible complex cube roots of rho-1 of course, so there are three branches to this curve --- once you pick a branch of the cube root to use, you can continuously deform rho away from 1 and you will get a corresponding value for x also moving away from 1. But the point is that if you do as you say, deforming rho along the real axis towards 0, the corresponding values of x in the complex plane will trace out three curves which not only start at x=1 but they initially head out in the directions of the three cube roots of 1/(1+P(1)). If P(1) > -1, then one of these x's will be increasing along the real axis, and in particular will become larger than 1 in modulus. If instead P(1) < -1, then the real root is decreasing but the two complex roots are heading away from the real number x=1 towards the north-east or south-west (+- 60 degrees from the real axis, actually) and in particular are passing out of the circle of modulus 1. So in this case the two complex roots are increasing in magnitude, at least for small changes in rho . The case P(1)=-1 is special; in that case the lowest-order terms of the expansion of Q at (1,1) are (N+P'(1))(x-1)^4 - (rho-1), so that (unless P'(1) = - N ) there will be four values of x for each rho near 1, namely x-1 ~ ( (rho-1)/(N+P'(1)) )^(1/4) . If N + P'(1) > 0 this will mean the values of x will form four curves as rho decreases to 0, the four curves forming an X shape at the complex point 1; in particular, two of them will be heading outside the circle. If instead N + P'(1) < 0 , one curve will head outside the unit circle along the real axis, one will head inside, and the other two will share a tangent with the circle -- it would be hard to decide whether those two roots are increasing or decreasing in magnitude. You can consider the remaining special cases yourself (P(1)+1=P'(1)+N=0, etc.) dave === Subject: Re: question about zeroes of polynomials >dear all, > >I have the following problem. We have a polynomial Q(x) of degree 3+N in x: > >Q(x):= x^(3+N)-rho*3*x^(2+N)+rho*3*x^(1+N)-rho*x^N + rho*(x-1)^3*P(x) > >with P(x) any polynomial of degree N-1 and rho a real number. If N=2 >for instance, P(x) looks like P(x)=a*x+b, and we obtain that Q is of >degree 5. If N=1, P(x) is just a nonzero constant. If N=0, P(x)=0. > >Now it is easy to see that if rho=1, 1 is a triple root of Q (3 of the >3+N roots are equal to 1). The question I have now is what happens with >these three special roots if we perturb rho a little bit towards zero. >So if rho is not 1 but 1-delta (with delta real, positive and >approximately 0, so f.i.0.0000001). Of course, these three roots that >were originally 1 might become complex then, such as >1.0000010201193+0.1846304081e-5*I. > >The thing I would really like to prove is that at least one of these >three roots (that were 1 if rho was 1), becomes larger than 1 in >absolute value (modulus) if rho is slightly perturbed in the way >described above. > >I thought it should be possible to prove this using some kind of >perturbation on rho or the roots (where we write f.i. rho=1+delta and >can then neglect some higher order terms in delta) but I do not seem to >get this kind of formulation right. > >Can anyone help me out? > > >Christophe write rho=1+eps. then you can develop the zeroes near one of the form 1+deltaz with deltaz a (complex) power series in the powers of eps^(1/3), one of them real of course. now the coefficient in front of eps^{1/3} will tell you whether you are right. this will clearly depend also on the coeffs of P(x). the book of Wilkinson: rounding erros in algebraic processes has a nice account for this problem, showing how to proceed and giving impressive examples. the general framework is algebraic functions, a branch in the theory of functions of one complex argument. hth peter