text:
Posted by: matheuscmss | February 16, 2009

## Proof of Duarte’s theorem on the abundance of elliptic islands for the standard map

Today we’ll close our current discussion of the standard map with the proof of Duarte’s theorem. As we mentioned earlier, the basic strategy consists into three steps: the construction of a dynamically increasing family of hyperbolic basic sets of saddle-type (“horseshoes”), the existence of a dense set of parameters where  a quadratic tangency is generically unfolded and the construction of elliptic islands from the bifurcation of quadratic tangencies via a conservative version of Newhouse phenomena. More precisely, we are going to show the statements of theorems 1, 2 and 3 of the previous post.

An “increasing” family of hyperbolic basic sets

In order to find hyperbolic sets, we’ll use the well-known invariant cone-field criterion:

Theorem (invariant cone-field criterion). Let $f:M\to M$ be a $C^1$-diffeomorphism. Consider $\Lambda$ a compact $f$-invariant set. Assume that there are $\mu>1>\lambda$, a decomposition $T_{\Lambda}M=E\oplus F$ (not necessarily $Df$-invariant) and two families $C^u\supset F$, $C^s\supset E$ of (closed) cones such that

• $Df(x)(C^u(x))\subset int(C^u(x))$ and $\|Df(x)v^u\|\geq\mu\|v^u\|$ for all $x\in\Lambda$ and $v^u\in C^u(x)$;
• $Df^{-1}(f(x))(C^s(f(x)))\subset int(C^s(x))$ and $\|Df^{-1}(f(x))v^s\|\geq\lambda^{-1}\|v^s\|$ for all $x\in\Lambda$ and $v^s\in C^s(f(x))$.

Then, $\Lambda$ is a hyperbolic set.

Proof. See corollary 6.4.8 of Katok-Hasselblat book. A sketch of proof goes as follows. Fix a point $x\in\Lambda$ and consider the following two sequences of cones on the tangent space $T_xM$: $Df^n(x)\cdot C^u(f^{-n}(x))$ and $Df^{-n}(x)\cdot C^s(f^n(x))$. Our assumptions implies that these two sequences are nested sequences of closed cones, so that the intersections

$E^u=\bigcap\limits_{n\geq 0}Df^n(x)\cdot C^u(f^{-n}(x))$

and

$E^s=\bigcap\limits_{n\geq 0}Df^{-n}(x)\cdot C^s(f^n(x))$

are closed $Df$invariant closed cones. In fact, one can work a bit more (with the facts $Df(x)(C^u(x))\subset int(C^u(x))$ and $Df^{-1}(f(x))(C^s(f(x)))\subset int(C^s(x))$) to see that $E^u$ and $E^s$ are vector subspaces with dimensions $\dim F$ and $\dim E$ resp.. Finally, once we know that $E^u$ and $E^s$ are $Df$-invariant subspaces, our assumptions of expansion (resp. contraction) of vectors belonging to the cone $C^u\supset E^u$ (resp. $C^s\supset E^s$), we see that $E^u$ is the unstable subspace and $E^s$ is the stable subspace. This completes the sketch. $\square$

Proposition 1. Consider the invertible area-preserving map

$f(x,y)=(-y+\phi(x),x)$

of the 2-torus $T^2$ and let $\Lambda$ be a $f$-invariant compact set. Assume that there exists $\lambda>2$ such that $|\phi'(x)|\geq\lambda$ for all $(x,y)\in\Lambda$. Then, $\Lambda$ is a hyperbolic set (of saddle type).

Proof. Note that

$Df = \left(\begin{array}{cc}\phi'(x) & -1 \\ 1 & 0\end{array}\right)\in SL(2,\mathbb{R}).$

In particular, the trace of $Df$ verifies $|tr Df|\geq \lambda>2$ so that the matrices $Df$ are uniformly hyperbolic. In fact, this follows from the fact that the constant cone-field

$C^u(p)\equiv C_{a}^u:=\{(u,v)\in\mathbb{R}^2: |v|\leq a |u|\}$

is an unstable cone-field whenever $1/(\lambda-1) (note that such a choice is possible since $\lambda>2$). Indeed, if we write $Df(u,v):=(u',v')$, we see that

$|v'|= |u|\leq (\lambda-a)^{-1}|\phi'(x)u-v|=(\lambda-a)^{-1}|u'|$

so that $Df(C_a^u)\subset C_{(\lambda-a)^{-1}}^u = C_{\theta a}^u$ where $\theta = \left(a\cdot(\lambda-a)\right)^{-1}<1$ by the choice of the parameter $a$, i.e., $C_a^u$ is $Df$-invariant. Furthermore, denoting by $\|(u,v)\|=\max\{|u|,|v|\}$, we get, for any $(u,v)\in C^u_a$,

$\|Df(u,v)\| = |u'|\geq (\lambda-a)|u| = (\lambda-a)\|(u,v)\|$

with $(\lambda-a)>1$, i.e., $Df$ (uniformly) expands any vector inside $C^u_a$. On the other hand, it is not hard to see that $Df\in SL(2,\mathbb{R})$ implies that the same argument can be applied to $Df^{-1}$ in order to get a stable cone-field. Using the invariant cone-field criterion, the proof is complete. $\square$

An immediate consequence of this proposition is the following result:

Corollary 1. For the standard family

$f_k(x,y)=(-y+2x+k\sin(2\pi x),x):=(-y+\phi_k(x),x)$,

given any $\lambda>2$, the maximal invariant set

$\Lambda_k=\bigcap\limits_{n\in\mathbb{Z}}f_k^{-n}(\{(x,y)\in\mathbb{T}^2: |\phi_k'(x)|\geq\lambda \})$

is hyperbolic.

Remark. It is worth to note that this result gives a clue about the location of the critical region of non-hyperbolicity: for a given $\lambda>2$, the set of points $\{(x,y): |\phi_k'(x)|\leq\lambda\}$  converges to the union of the two circles $\{x=\pm 1/4\}$ when $k\to\infty$.

Of course, this corollary says that the hyperbolic sets $\Lambda_k$ are a family of dynamically increasing basic sets. In fact, it turns out that this can be checked by hand (see section 4.2 of Duarte’s paper), but we’ll skip this fact for sake of brevity of the exposition.

Global dynamical foliations and their tangency lines

After the description of the (“big”) hyperbolic sets $\Lambda_k$ of the standard map $f_k$, we proceed to the study of the tangencies between their invariant foliations. In order to do so, we need to extend these foliations to some uniform neighborhood of $\Lambda_k$ (since we want to perform an analysis for several large parameters) while keeping good estimates of distortion of the holonomy maps. At this point, our first technical problem arises: from the general theory of uniformly hyperbolic sets (see the book of Palis-Takens), we know that $\Lambda_k$ admits some neighborhood $U_k$ so that the stable and unstable foliations of $\Lambda_k$ can be extended to $U_k$ (while keeping good estimates), but a priori the region $U_k$ where the good estimates are ensured can deteriorate when $k\to\infty$. To overcome this problem, Duarte takes the following point of view. Near the critical region $\{x=\pm 1/4\}$, he replaces $\phi_k(x)=2x+k\sin(2\pi x)$ by a function $\psi_k(x)$ having two poles at $x=\pm 1/4$ and he tries to compare the dynamics of $f_k(x,y)=(-y+\phi_k(x),x)$ with the dynamics of the singular diffeomorphism $g_k(x,y) = (-y+\psi_k(x),x)$.

More precisely, $\psi_k(x)=\phi_k(x)+\rho_k(x)$ where $\rho_k(x) = 0$ outside a $2/k^{1/3}$-neighborhood of $x=\pm 1/4$ and $\rho_k(\pm 1/4)=\infty$. Then, after the somewhat tedious work of redoing the theory of invariant manifolds (following the exposition of Hirsch-Pugh-Shub), he checks that $\psi_k$ has global stable and unstable foliations $\mathcal{F}^s, \mathcal{F}^u$ on $\mathbb{T}^2$ verifying uniform distortion estimates (i.e., their holonomy maps have uniformly bounded $C^2$-norm). Here, the uniform control of distortion comes from the choice of $\rho_k$: indeed, assuming that $\psi_k$ coincides with $\phi_k$ outside a $1/k^{\epsilon}$-neighborhood of $x=\pm 1/4$, it is not hard to see that the Schwartzian derivate of $\psi_k$ is bounded from below (in the critical region $|x\mp 1/4|\leq k^{-\epsilon}$) by

$2\left|\frac{\psi_k''(x)^2}{\psi_k'(x)^3}\right|+\left|\frac{\psi_k'''(x)}{\psi'(x)^2}\right|\geq \frac{\pi}{k|\cos(2\pi x)|^3} - \frac{\pi}{k\cos(2\pi x)}\geq k^{3\epsilon-1}$.

In particular, since we want to take $\epsilon>0$ the largest possible so that $\psi_k$ coincides with $\phi_k$ in $|x\mp 1/4|\geq k^{-\epsilon}$ and $\psi_k$ with bounded Schwartzian derivative (because it is well-known that bounded Schwartzian derivative implies bounded distortion), it is natural to take $\psi_k=\phi_k$ outside $|x\mp 1/4|\geq 2k^{-1/3}$ (i.e., $\epsilon=1/3$).

Of course, once we performed this work (which takes 21 pages of Duarte’s paper), we have to compare the dynamics of $f_k$ and $g_k$. However, this is not hard: the maximal invariant set $\Lambda_k$ is the same for both $f_k$ and $g_k$, and, using the strong hyperbolic features of the singular diffeomorphism $g_k$, it is possible to show that the dynamics of $f_k$ and $g_k$ on $\Lambda_k$ are conjugated to a $2n_k$ full (Bernoulli) shift (where $2k(1-32\pi^2/k^{2/3})\leq n_k\leq 2k$); furthermore, $B_{4/k^{1/3}}(\Lambda_k)=\mathbb{T}^2$,  its stable and unstable thickness $\tau^s(\Lambda_k),\tau^u(\Lambda_k)\geq k^{1/3}/9$ (where $\tau^s(\Lambda_k)$, resp. $\tau^u(\Lambda_k)$, is the thickness of the Cantor set obtained by projection of $\Lambda_k$ along the stable, resp. unstable, foliation on an arbitrarily fixed transversal section) and, as a consequence, its Hausdorff dimension $HD(\Lambda_k)$ satisfies $HD(\Lambda_k)\geq 2 \log 2/\log(2+9/k^{1/3})$.

Next, we analyse the relative positions of the ($g_k$-invariant) foliations $\mathcal{F}^s$ and $\mathcal{F}^u$. Applying $f_k$ to $\mathcal{F}^u$, we obtain a new foliation $\mathcal{G}^u := (f_k)_*(\mathcal{F}^u)$ (recall that $\mathcal{F}^u$ is $g_k$-invariant but it is not $f_k$-invariant). It is not hard to see that the set of tangencies between $\mathcal{G}^u$ and $\mathcal{F}^s$ are two circles close to $\{x=\pm 1/4\}$. Moreover, the projection of $\Lambda_k$ along $\mathcal{G}^u$ and $\mathbb{F}^s$ into these two circles gives rise to two Cantor sets $K^u$ and $K^s$ satisfying $\tau(K^u)\geq k^{1/3}/10$ and $\tau(K^s)\geq k^{1/3}/9$ (here we are using the previous thickness estimate and the fact that the application of $f_k$ to the foliation $\mathcal{F}^u$ doesn’t change very much the thickness). The picture below (borrowed from Duarte’s paper) summarizes our discussion about the relative position of $\mathcal{G}^u$ and $\mathcal{F}^s$:

Here $\mathcal{F}^s$ is the almost vertical foliation and $\mathcal{G}^u$ is the foliation folding along the two dotted circles. Now, using the fact that $\tau(K^u)\tau(K^s)\geq k^{2/3}/90\gg 1$ (for any large $k$), we can apply Newhouse’s gap lemma to obtain that $K^u\cap K^s\neq\emptyset$. In other words, we get that $\mathcal{G}^u$ and $\mathcal{F}^s$ exhibits persistent tangencies.

Remark. In proposition 16 of Duarte’s paper, a version of Newhouse’s gap lemma in the circle is wrongly stated: indeed, Duarte claims that the fact that the two Cantor sets are contained in the circle automatically implies that the two Cantor sets are linked. However, this is not correct (as the example of two thick Cantor sets supported by two disjoint compact intervals shows), although this is not a serious problem for this argument: from a careful checking of the geometry of $\Lambda_k$ (via the features of the singular diffeomorphism $g_k$), it is not hard to see that $K^u$ and $K^s$ are linked (this follows from Duarte’s argument in section 4.2 of his paper).

Finally, closing this section, we claim that these persistent tangencies are quadratic and unfold generically with the parameter $k$ (as the picture above indicates). While a complete proof of this result takes 7 pages of technical calculations, we’ll provide a convincingly enough (I hope! :)) heuristic argument. We know that the $\psi_k$-invariant foliations $\mathcal{F}^s$ and $\mathcal{F}^u$ are almost vertical and horizontal (resp.). In particular, it is reasonable to expect that the circles of tangencies between $\mathcal{F}^s$ and $\mathcal{G}^u = (f_k)_*(\mathcal{F}^u)$ are close to the circles of tangencies between the horizontal foliation and the image of the vertical foliation under $f_k$. On the other hand, since $f_k(x,y) = T_k\circ R$ where $R(x,y)=(-y,x)$ is the $\pi/2$ counterclockwise rotation and $T_k(x,y)=(x+\phi_k(y),y)$ is a shear (of variable intensity) along the horizontal foliation, we can compute the image of the vertical foliation under $f_k$ as follows: the image of the horizontal foliation by $R$ is the vertical foliation and the image of the vertical foliation by $T_k$ is a foliation by the family of curves which are parallel to the graph $\{(\phi_k(y),y):y\in\mathbb{T}\}$. In particular, the circle of tangencies between these two foliations are exactly the critical circles $\{(x,\nu_{\pm}): x\in\mathbb{T}, \phi'_k(\nu_{\pm})=0\}$. At such points, the difference between the curvatures is measured by $\phi_k''(\nu_{\pm})=4\pi^2 k$, so that the tangencies between the horizontal foliation and the $f_k$-image of the vertical foliation are quadratic (i.e., locally you are seeing the intersections between straight lines and parabolas) and, a fortiori, the same holds for the tangencies between $\mathcal{G}^u$ and $\mathcal{F}^s$. Also, when the parameter $k$ increases, the $g_k$-invariant foliations $\mathcal{F}^u$ and $\mathcal{F}^s$ doesn’t change very much (they are almost constant), while the $x$-coordinates of the tangency points between $\mathcal{G}^u=(f_k)_*(\mathcal{F}^u)$ and $\mathcal{F}^s$ (which are close to $(x+\phi_k(\nu_{\pm}),\nu_{\pm})$) move with velocity (close to) 1 (indeed, $\nu_{\pm}=\pm 1/4$ implies $\frac{d}{dk}(x+\phi_k(\nu_{\pm}))= \sin(2\pi \nu_{\pm})=1$). Hence, these tangencies are unfolded generically.

At this point, the reader noticed that this discussion gives the theorems 1 and 2 of the previous post. Now, we proceed to discuss the conservative version of the Newhouse phenomena.

-Conservative version of Newhouse phenomena: proof of theorem 3-

Before entering into the proof of the abundance of elliptic islands close to a generically unfolded quadratic tangency, let me review a little bit some facts around the proof of the “classical” Newhouse phenomena.

Given $f_\mu$ a 1-parameter family of surface diffeomorphisms generically unfolding a quadratic homoclinic tangency $q$ associated to a hyperbolic periodic point $p$ of saddle-type (at the parameter $\mu=0$ say), Newhouse manage to define a renormalization scheme near $q$ as follows: for every large $n\in\mathbb{N}$, one can select small boxes near $q$ which are mapped by $f_\mu^n$ near itself  with the shape of a parabola so that their relative positions resembles a horseshoe; next, we compose this dynamics with appropriate rescalings $h_n$ of these boxes in order to put these very small boxes into a fixed scale (e.g., a unit square) so that we obtain the families of dynamical systems given by $h_n\circ f_\mu^n\circ h_n^{-1}$ (these are called the successive renormalizations of the dynamics near the homoclinic tangency). The usefulness of idea is more or less clear: assuming that there exists some limiting object $h_n\circ f_\mu\circ h_n^{-1}\to t_{\mu}$, any stable dynamical property of $t_\mu$ will be shared by $h_n\circ f_\mu\circ h_n^{-1}$ and a fortiori $f_\mu$.  It turns out that Newhouse showed that this renormalization scheme converges (i.e., the limiting object exists) when the periodic point $p$ is dissipative (i.e., $\det|Df_\mu(p)|<1$).  Moreover, the limit $t_\mu$ in this case is the quadratic family

$t_\mu(x,y)=(\mu-x^2,x)$.

Using this information, the existence of sinks near the homoclinic tangency follows directly. A detailed exposition of Newhouse’s argument can be found in the excelent book of Palis and Takens.

After this quick review of Newhouse arguments, let us consider again the situation of the standard map: in the conservative setting, given a family of area-preserving diffeomorphisms generically unfolding a quadratic homoclinic tangency associated to a hyperbolic periodic point, one can repeat the renormalization scheme of Newhouse to get as a limit object the conservative Hénon family

$t_\mu(x,y)=(-y+\mu-x^2,x)$.

Next, it is possible (exercise) to show the presence of elliptic fixed points for this family when $-1<\mu<3$ (with the eigenvalue of this point running from 1 to -1). Because generic (i.e., non-resonant) elliptic periodic point is stable by conservative perturbations (this follows from the so-called KAM theory; see e.g. this monograph of J. Moser), we conclude the existence of (generic) elliptic periodic points nearby the homoclinic tangency. Combining this result with the theorems 1 and 2 proved in the previous sections, we see that, similarly to the proof of Newhouse theorem, the proof of theorem 3 is complete!


text:
# Modern Physics/Addition of Velocities

In classical physics, velocities simply add. If an object moves with speed u in one reference frame, which is itself moving at v with respect to a second frame, the object moves at speed u+v in that second frame.

This is inconsistant with relativity because it predicts that if the speed of light is c in the first frame it will be v+c in the second.

We need to find an alternative formula for combining velocities. We can do this with the Lorentz transform.

Because the factor v/c will keep recurring we shall call that ratio β.

We are considering three frames; frame O, frame O' which moves at speed u with respect to frame O, and frame O" which moves at speed v with respect to frame O'.

We want to know the speed of O" with respect to frame O,U which would classically be u+v.

The transforms from O to O' and O' to O" can be written as matrix equations,

${\displaystyle {\begin{pmatrix}x'\\ct'\end{pmatrix}}=\gamma {\begin{pmatrix}1&-\beta \\-\beta &1\end{pmatrix}}{\begin{pmatrix}x\\ct\end{pmatrix}}\quad {\begin{pmatrix}x''\\t''\end{pmatrix}}=\gamma '{\begin{pmatrix}1&-\beta '\\-\beta '&1\end{pmatrix}}{\begin{pmatrix}x'\\ct'\end{pmatrix}}}$

where we are defining the β's and γ's as

${\displaystyle {\begin{matrix}\beta ={\frac {u}{c}}&\gamma ={\frac {1}{\sqrt {1-\beta ^{2}}}}\\\beta ^{\prime }={\frac {v}{c}}&\gamma ^{\prime }={\frac {1}{\sqrt {1-{\beta ^{\prime }}^{2}}}}\end{matrix}}}$

We can combine these to get the relationship between the O and O" coordinates simply by multiplying the matrices, giving

${\displaystyle {\begin{pmatrix}x''\\ct''\end{pmatrix}}=\gamma \gamma ^{\prime }{\begin{pmatrix}1+\beta \beta '&-(\beta +\beta ')\\-(\beta +\beta ')&1+\beta \beta '\end{pmatrix}}{\begin{pmatrix}x\\ct\end{pmatrix}}\quad (1)}$

This should be the same as the Lorentz transform between the two frames,

${\displaystyle {\begin{pmatrix}x''\\ct''\end{pmatrix}}=\gamma ''{\begin{pmatrix}1&-\beta ''\\-\beta ''&1\end{pmatrix}}{\begin{pmatrix}x\\ct\end{pmatrix}}\quad (2){\mbox{ where }}{\begin{matrix}\beta ''&=&{\frac {U}{c}}\\\gamma ''&=&{\frac {1}{\sqrt {1-{\beta ''}^{2}}}}\end{matrix}}}$

These two sets of equations do look similar. We can make them look more similar still by taking a factor of 1+ββ' out of the matrix in (1) giving#

${\displaystyle {\begin{pmatrix}x''\\ct''\end{pmatrix}}=\gamma \gamma '(1+\beta \beta '){\begin{pmatrix}1&-{\frac {\beta +\beta '}{1+\beta \beta '}}\\-{\frac {\beta +\beta '}{1+\beta \beta '}}&1+\end{pmatrix}}{\begin{pmatrix}x\\ct\end{pmatrix}}}$

This will be identical with equation 2 if

${\displaystyle \beta ''={\frac {\beta +\beta '}{1+\beta \beta '}}{\mbox{ (3a) and }}\gamma ''=\gamma \gamma '(1+\beta \beta '){\mbox{ (3b)}}}$

Since the two equations must give identical results, we know these conditions must be true.

Writing the β's in terms of the velocities equation 3a becomes

${\displaystyle {\frac {U}{c}}={\frac {{\frac {u}{c}}+{\frac {v}{c}}}{1+{\frac {uv}{c^{2}}}}}}$

which tells us U in terms of u and v.

A little algebra shows that this implies equation 3b is also true

Multiplying by c we can finally write.

${\displaystyle U={\frac {u+v}{1+{\frac {uv}{c^{2}}}}}}$

Notice that if u or v is much smaller than c the denominator is approximately 1, and the velocities approximately add but if either u or v is c then so is U, just as we expected.

format: plain


text:
# Solve by factorization: (x-3)/(x+3)-(x+3)/(x-3)=(48)/7,\ \ x!=3,\ \ x!=-3

Updated On: 17-04-2022

Get Answer to any question, just click a photo and upload the photo
and get the answer completely free,

Watch 1000+ concepts & tricky questions explained!

Step by step solution by experts to help you in doubt clearance & scoring excellent marks in exams.

Transcript

Shubh Yahan to solve by factorization equation given to US says x minus 3 upon X + 3 - 4 x + 3 upon x minus 3 is equal to 48 by 7 and the condition given to Asus X not equal to 3 and X not equal to minus 3 so we have identities a + b whole square is equal to a square + b square of Ab and similarly a minus b whole square is equal to a square + b square minus of two AP and capital a square minus of capital b square is equal to a + b into a minus b these are important identities for taking LCM we have X + 3 into x minus 3 and from here x minus 3 into x minus 3 will be equal to X

whole square minus x + 3 into X + 3 is equal to X + 3 whole square is equal to 48 by 7 show solving this a minus b whole square feet equal to a square that is a square b square that is 3 square and minus 2 into X into three that is to ab - of a + b whole square will be equal to a square that is X square + b square is 3 square + 2 of X in 2332 a b upon solving this by cross multiplying we have X into x minus x square x into minus 3 minus 3 X + 3 and + 3 into X + 3 X + 3 into minus 3 minus 19 and this value is equal to 48 by 7 so simplifying this we have X square + 3 square is 9

- of 2 into X into 36 - of opening this bracket we have minus x square - 3 square is 92 that is minus 9 and minus of 2 into X into trees - 6 x denominator if we have x square - 3 x + 3 X will cancel out and minus 9 is equal to 48 by 72 solving this we have + x square minus x square will get cancelled out - 6 x minus 6 x is equal to minus of 12 x + 9 x - 9 x will cancel out so divided by x square - 9 is equal to 48 y71 cross multiply in this we have - 12 x into 7 is equal to 48 into x square - 9 so this

inst wave will be equal to -1 and this 48 will be equal to 4 12 48 so we have - of 7 x is equal to open the bracket we have 4 x square - 9 4036 so taking this term into RHS we have 4 x square + 7 x - 36 is equal to zero so let it be a this b&b in this BC per factorization we have product of a into C is equal to 4 x square into -36 that will be equal to is equal to minus 144 x square so we have to split the sturm in two parts such that their sum will be equal to + 7 x so we have + 16

x minus of 9X the submission will be equal to + 7 x and their multiplication will be equal to minus 44 x square - 144 x square so we have 4 x square and writing + 7 x as + 16 X - 9 x - 36 is equal to zero taking 4x common we have X + 4 - 9 common we have X + 4 is equal to zero 4 - 9 into X + 4 is equal to zero from here we have 4 x minus 9 is equal to zero and from here X + 4 is equal to zero so xy9 by 4 and X will be equal to minus 4


text:
# Basic differential equations help

• Feb 7th 2010, 05:02 PM
lordpikachu
Basic differential equations help
find the general solution for y''[x] = -y'[x]

the answer is y=c1e^(tx1) + c2e^(tx2) where c1, c2, x1, x2 are separate variables/constants...
i don't understand..i keep getting that y=ce^-x but that comes nowhere close to what the real answer is?

If anyone can help me, I would greatly appreciate it (ie worship them forever)

Thanks

ps. should this go in the diffeq forum? i wasn't sure because this is basic diffeq you learn in calc...
• Feb 7th 2010, 06:31 PM
tonio
Quote:

Originally Posted by lordpikachu
find the general solution for y''[x] = -y'[x]

the answer is y=c1e^(tx1) + c2e^(tx2) where c1, c2, x1, x2 are separate variables/constants...
i don't understand..i keep getting that y=ce^-x but that comes nowhere close to what the real answer is?

If anyone can help me, I would greatly appreciate it (ie worship them forever)

Thanks

ps. should this go in the diffeq forum? i wasn't sure because this is basic diffeq you learn in calc...

You are correct: observe that $y''=-y\Longrightarrow \frac{y''}{y'}=-1\Longrightarrow \ln y'=-x+C\Longrightarrow y'=Ke^{-x}\Longrightarrow y=Ke^{-x}$ , integrating twice.

Tonio
• Feb 7th 2010, 06:40 PM
vince
Quote:

Originally Posted by lordpikachu
find the general solution for y''[x] = -y'[x]

the answer is y=c1e^(tx1) + c2e^(tx2) where c1, c2, x1, x2 are separate variables/constants...
i don't understand..i keep getting that y=ce^-x but that comes nowhere close to what the real answer is?

If anyone can help me, I would greatly appreciate it (ie worship them forever)

Thanks

ps. should this go in the diffeq forum? i wasn't sure because this is basic diffeq you learn in calc...

set up the associated characteristic polynomial and solve for the roots. those roots are what appear in the exponents of the exponentials above.
• Feb 7th 2010, 06:52 PM
vince
Quote:

Originally Posted by tonio
You are correct: observe that $y''=-y\Longrightarrow \frac{y''}{y'}=-1\Longrightarrow \ln y'=-x+C\Longrightarrow y'=Ke^{-x}\Longrightarrow y=Ke^{-x}$ , integrating twice.

Tonio

This works. I get $y=c1 + c2e^{-x}$
• Feb 7th 2010, 08:19 PM
lordpikachu
OHHH i get it
Oh wow thanks!! I LOVE YOU GUYS. // thanks a million times.
• Feb 8th 2010, 05:29 AM
HallsofIvy
Quote:

Originally Posted by lordpikachu
find the general solution for y''[x] = -y'[x]

the answer is y=c1e^(tx1) + c2e^(tx2) where c1, c2, x1, x2 are separate variables/constants...
i don't understand..i keep getting that y=ce^-x but that comes nowhere close to what the real answer is?

The general solution is, as you have already been told, $y= c_1+ c_2e^{-t}$ (it is your choice to use t or x as the independent variable since it is not given in the equation). My point is that this is exactly of the form $c_1e^{tx_1}+ c_2e^{tx_2}$ with $x_1= 0$ and $x_2= -1$.

Quote:

If anyone can help me, I would greatly appreciate it (ie worship them forever)
We will forward you an address to send your tithes to. You will have to purchase your own white robes.

Quote:

Thanks

ps. should this go in the diffeq forum? i wasn't sure because this is basic diffeq you learn in calc...


text:
#### Vol. 312, No. 1, 2021

 Recent Issues Vol. 321: 1  2 Vol. 320: 1  2 Vol. 319: 1  2 Vol. 318: 1  2 Vol. 317: 1  2 Vol. 316: 1  2 Vol. 315: 1  2 Vol. 314: 1  2 Online Archive Volume: Issue:
 The Journal Subscriptions Editorial Board Officers Contacts Submission Guidelines Submission Form Policies for Authors ISSN: 1945-5844 (e-only) ISSN: 0030-8730 (print) Special Issues Author Index To Appear Other MSP Journals
Derived decompositions of abelian categories I

### Hongxing Chen and Changchang Xi

Vol. 312 (2021), No. 1, 41–74
##### Abstract

Derived decompositions of abelian categories are introduced in internal terms of abelian subcategories. They are used to construct semiorthogonal decompositions (or in other terminology, Bousfield localizations, or hereditary torsion pairs) in derived categories of abelian categories. A sufficient condition is given for abelian categories to have derived decompositions. This is necessary if abelian categories have enough projectives and injectives. Applications are given to homological ring epimorphisms, localizing subcategories, nonsingular rings and commutative noetherian rings. Moreover, a derived stratification of module categories over commutative noetherian rings of Krull dimension at most $1$ is presented.

We have not been able to recognize your IP address 3.236.24.215 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

or by using our contact form.


text:
Linear independence in a complex vector space

When proving linear independence in a complex vector space can we assume the scalars that we need to show equal to zero are real? i.e then the result would be

If we have $v_1,v_2,...,v_k \in \mathbb{C}$ with scalars $\alpha_1, \alpha_2,...,\alpha_k\in \mathbb{R}$ then $v_1,v_2,...,v_k$ is called linearly independent if $$\sum_{i=1}^{k}\alpha_i v_i=0\Rightarrow \alpha_i=0$$

The example I am stuck on is this

$v_1=(1, -i, 1+i)^t, \;\;\;v_2=(1-i, 1+i,0)^t,\;\;\;v_3=(-1,i,1+i)^t$

Using the definition I get: $$1) \;\; \alpha+\beta-i\beta-\gamma=0$$ $$2)\; -i\alpha+\beta+i\beta +i\gamma=0$$ $$3)\;\; \alpha+i\alpha+\gamma+i\gamma=0$$ Now if it is possible to assume $\alpha,\beta,\gamma$ real then I can equate real and imaginary parts and receive $\beta=0$ just from the first equation. Is this correct? If not how would I go about solving this?

• The usual definition of a complex vector space states that the scalars are arbitrary elements of $\Bbb C$, not $\Bbb R$. – Omnomnomnom Nov 30 '14 at 15:44
• Your definition treats $\Bbb C$ as a (2-dimensional) real vector space – Omnomnomnom Nov 30 '14 at 15:45
• The usual ways of solving a problem like this are Gaussian elimination and computing the determinant. – Omnomnomnom Nov 30 '14 at 15:47
• Thanks for clearly it up, I'll try gaussian – George1811 Nov 30 '14 at 15:48


text:
Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-130 | 7th September 2021 05:11

#### Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case

TR21-130
Authors: Srinivasan Arunachalam, João F. Doriguello
Publication: 9th September 2021 17:48
Keywords:

Abstract:

Hypercontractive inequalities for real-valued functions over the Boolean cube play an important role in theoretical computer science. In this work, we prove a hypercontractive inequality for matrix-valued functions defined over large alphabets, generalizing the result of Ben-Aroya, Regev, de Wolf (FOCS'08) for the Boolean alphabet. To obtain our result we prove a generalization of the powerful $2$-uniform convexity inequality for trace norms of Ball, Carlen, Lieb (Inventiones Mathematicae'94). We give two applications of this hypercontractive inequality.

Locally decodable codes: we present a lower bound for locally decodable codes (LDC) over large alphabets. An LDC $C:\mathbb{Z}_r^n\to \mathbb{Z}_r^N$ is an encoding of $x\in \mathbb{Z}_r^n$ into a codeword $C(x)$ in such a way that one can recover an arbitrary $x_i\in \mathbb{Z}_r$ (with probability at least $1/r+\varepsilon$) by making only a few queries to a corrupted codeword. The main question in LDCs is the trade-off between $N$ and $n$. By using hypercontractivity, we give an exponential lower bound $N= 2^{\Omega(\varepsilon^4 n/r^4)}$ for $2$-query (possibly non-linear) LDCs over $\mathbb{Z}_r$. Previously exponential lower bounds were known for $r=2$ (Kerenidis and de Wolf (JCSS'04)) and for \emph{linear} codes (Dvir and Shpilka (SICOMP'07)).

Streaming algorithms: we present upper and lower bounds for the communication complexity of the Hidden Hypermatching problem when defined over large alphabets, which generalizes the well-known Boolean Hidden Matching problem. We then consider streaming algorithms for approximating the value of Unique Games on a $t$-hyperedge hypergraph: in this direction a simple edge-counting argument gives an $r$-approximation with $O(\log n)$ space. On the other hand, we use our communication lower bound to show that every streaming algorithm in the adversarial model achieving a $(r-\varepsilon)$-approximation of this value requires $\Omega(n^{1-1/t})$ classical space or $\Omega(n^{1-2/t})$ quantum space. In this setting, these results simplify and generalize the seminal work of Kapralov, Khanna and Sudan (SODA'15) and Kapravol and Krachun (STOC'19) for the case $r=2$.

ISSN 1433-8092 | Imprint


text:
Intro to Springs (Hooke's Law) Video Lessons

Concept

# Problem: a) Two springs with spring constants k1 and k2 are connected in parallel. What is the effective spring constant keff? In other words, if the mass is displaced by x, find the keff for which the force equals F= -(keff)x.

###### FREE Expert Solution

Hooke's law:

$\overline{){\mathbf{F}}{\mathbf{=}}{\mathbf{-}}{\mathbf{k}}{\mathbf{x}}}$

(a)

The two springs have the same extension, x.

F1 = -k1x

F2 = -k2x

F = -keqx

84% (45 ratings)
###### Problem Details

a) Two springs with spring constants k1 and k2 are connected in parallel. What is the effective spring constant keff? In other words, if the mass is displaced by x, find the keff for which the force equals F= -(keff)x.


text:
💬 👋 We’re always here. Join our Discord to connect with other students 24/7, any time, night or day.Join Here!

# Evaluate the indefinite integral as a power series. What is the radius of convergence?$\int \frac {t}{1 - t^8} dt$

## $$C+\sum_{n=0}^{\infty} \frac{t^{8 n+2}}{8 n+2}, R=1$$

Sequences

Series

### Discussion

You must be signed in to discuss.
##### Catherine R.

Missouri State University

##### Kristen K.

University of Michigan - Ann Arbor

Lectures

Join Bootcamp

### Video Transcript

evaluate the indefinite integral as a power series. And what is the richest convergence? Okay, so the first gonna expanded as a power series, did he here? So this is tee times from zero to infinity to the power of Aden T T. And it goes to and from zero to infinity teaching power a or 18 plus one DT. We'll exchange the order of salmon Negro. So we're going to integrate these parts. Did he? And this is just so teacher power 18 plus 2/18 plus two. Yeah. So we have relegated indefinitely, grows as a power series, and one is really some convergence. So actually, we expanded for, uh, from this from this step. So this is step one and inquiries The absolute value of T two tower eighth is less than one. So that implies teas from 91 to 1. And the readers of convergence is r equals to one. Okay,

University of Illinois at Urbana-Champaign

#### Topics

Sequences

Series

##### Catherine R.

Missouri State University

##### Kristen K.

University of Michigan - Ann Arbor

Lectures

Join Bootcamp


text:
1. ## Log question

Im pretty sure im meant to be solving this as a logarithim.
Question is:

Find all real solutions if any of:

3^x multiply 27^(2-x) = 9

Very confused...

Thanks.

PS pleaqse include working so i can study it when youre done.

2. ## Re: Log question

Originally Posted by Hooperoo
Im pretty sure im meant to be solving this as a logarithim.
Question is:

Find all real solutions if any of:

3^x multiply 27^(2-x) = 9

Very confused...

Thanks.

PS pleaqse include working so i can study it when youre done.
$3^x \cdot 27^{2-x}=9$

$3^x \cdot 3^{6-3x}=3^2$

$3^{6-2x}=3^2$

$6-2x=2$

$x=2$

3. ## Re: Log question

I use to love problems like this because it would be like one of those hidden things... The first thing that would come into my mind is how are all these numbers kinda related so 3, 9 and 27. All multiples of 3 right... and if we are dealing with exponents then you kind of got to say, "Ok, well... 9 = 3 to the what (3^?)... oh (3^2) = 9" and so on.

Just a quick tip if anyone else is reading


text:
# Merging Two Bubble Sorted Linked Lists (Python)

I'm following a tutorial on merging two bubble-sorted Single Linked Lists in Python.

• merge1 creates a new list and does the merging.

Other than naming conventions which are not the best and I'm just following the tutorial, any feedback would be appreciated. OOP, practical time-complexity, algorithms, and others.

class Node:
# Instantiates the node class
def __init__(self, value):
self.info = value

# Instantiates the single linked list class
def __init__(self):
self.start = None

# Creates the single linked list
def create_list(self):
n = int(input("Enter the number of nodes in the list you wish to create: "))

if n == 0:
return
for i in range(n):
data = int(input("Enter the element to be inserted: "))
self.insert_at_end(data)

# Counts the nodes of the single linked list
def count_nodes(self):
p = self.start
n = 0
while p is not None:
n += 1
print("💚 The number of nodes in single linked list is: " + str(n))

# Searches the x integer in the linked list
def search(self, x):
position =  1
p = self.start
while p is not None:
if p.info == x:
print("💚 YAAAY! We found " + str(x) + " at position " + str(position))
return True

# Increment the position
position += 1
# Assign the next node to the current node
else:
print("💔 Sorry! We couldn't find " + str(x) + " at any position. Maybe, try again later!")
return False

# Displays the list
def display_list(self):
if self.start is None:
print("💛 Single linked list is empty!")
return
else:
print("💚 Single linked list includes: ")
p = self.start
while p is not None:
print(p.info, " ", end=' ')
print()

# Inserts an integer in the beginning of the linked list
def insert_in_beginning(self, data):
temp = Node(data)
self.start = temp

# Inserts an integer at the end of the linked list
def insert_at_end(self, data):
temp = Node(data)
if self.start is None:
self.start = temp
return

p = self.start

# Inserts an integer after the x node
def insert_after(self, data, x):
p = self.start

while p is not None:
if p.info == x:
break

if p is None:
print("💔 Sorry! " + str(x) + " is not in the list.")
else:
temp = Node(data)

# Inserts an integer before the x node
def insert_before(self, data, x):
# If list is empty
if self.start is None:
print("💔 Sorry! The list is empty.")
return
# If x is the first node, and new node should be inserted before the first node
if x == self.start.info:
temp = Node(data)

# Finding the reference to the prior node containing x
p = self.start
break

print("💔 Sorry! " + str(x) + " is not in the list.")
else:
temp = Node(data)

# Inserts an integer in k position of the linked list
def insert_at_position(self, data, k):
# if we wish to insert at the first node
if k == 1:
temp = Node(data)
self.start = temp
return

p = self.start
i = 1

while i < k-1 and p is not None:
i += 1

if p is None:
print("💛 The max position is: " + i)
else:
temp = Node(data)
self.start = temp

# Deletes a node of a linked list
def delete_node(self, x):
# If list is empty
if self.start is None:
print("💔 Sorry! The list is empty.")
return

# If there is only one node
if self.start.info == x:

# If more than one node exists
p = self.start
break

print("💔 Sorry! " + str(x) + " is not in the list.")
else:

# Deletes the first node of a linked list
def delete_first_node(self):
if self.start is None:
return

# Deletes the last node of a linked list
def delete_last_node(self):
# If the list is empty
if self.start is None:
return

# If there is only one node
self.start = None
return

# If there is more than one node
p = self.start

# Increment until we find the node prior to the last node

def reverse_list(self):
prev = None
p = self.start
while p is not None:
prev = p
p = next
self.start = prev

# Bubble sorts the linked list with respect to data
def bubble_sort_exdata(self):
# If the list is empty or there is only one node
if self.start is None or self.start.link is None:
print("💛 The list has no or only one node and sorting is not required.")
end = None

p = self.start
if p.info > q.info:
p.info, q.info = q.info, p.info
end = p

# If the list is empty or there is only one node
if self.start is None or self.start.link is None:
print("💛 The list has no or only one node and sorting is not required.")
end = None

r = p = self.start
if p.info > q.info:
if  p != self.start:
else:
self.start = q
p, q = q, p
r = p
end = p

def merge1(self, list2):
merge_list.start = self._merge1(self.start, list2.start)
return merge_list

def _merge1(self, p1, p2):
if p1.info <= p2.info:
StartM = Node(p1.info)
else:
StartM = Node(p2.info)
pM = StartM

while p1 is not None and p2 is not None:
if p1.info <= p2.info:
else:

# If the second list is finished, yet the first list has some nodes
while p1 is not None:

# If the second list is finished, yet the first list has some nodes
while p2 is not None:

return StartM

# Testing

list1.create_list()
list2.create_list()

list1.bubble_sort_exdata()
list2.bubble_sort_exdata()

print("1⃣  The first list is: ")
list1.display_list()

print("2⃣  The second list is: ")
list2.display_list()

list3 = list1.merge1(list2)

print("The merged list by creating a new list is: ")
list3.display_list()

### Output

1⃣  The first list is:
1   1   1   2   3
2⃣  The second list is:
1   3   6   6
The merged list by creating a new list is:
1   1   1   1   2   3   3   6   6

• where is merge2 ? :( 💔 – dfhwze Aug 27 '19 at 21:14
• Ah ok, I was about to add the comparative review tag, but it's no longer required. By the way, I'm out of votes :s – dfhwze Aug 27 '19 at 21:17

# Docstrings

You should have a docstring at the beginning of every module, class, and method you write. This will allow documentation to identify what your code is supposed to do. You're on the right track, having comments above the classes and methods. Now, just move those comments inside these classes and methods at the very beginning, inside triple quote comments (""" ... """). I've gone and done this for you.

# Meaningful Variable Naming

You have many variables like p, q, x, k, etc. While this may be convenient for sorting algorithms, you should provide more meaningful names for these variables.

# _ for unused loop variable(s)

You have this code:

for i in range(n):
data = int(input("Enter the element to be inserted: "))
self.insert_at_end(data)

You don't use the i at all in this loop. You should use a _ instead. This makes it clear that the loop variable is to be ignored. The loop should now look like this:

for _ in range(n):
data = int(input("Enter the element to be inserted: "))
self.insert_at_end(data)

# String Concatenation / Formatting

You have this code all throughout your program:

print("💚 The number of nodes in single linked list is: " + str(n))
print("💚 YAAAY! We found " + str(x) + " at position " + str(position))
print("💔 Sorry! " + str(x) + " is not in the list.")
...

Changing the type of the variable to a string, then adding it to the string, is unnecessary. You can simply use f"" or "".format() to directly incorporate these variables into your strings, without having to type cast them. Here are both ways:

f""

print(f"💚 The number of nodes in single linked list is: {n}")
print(f"💚 YAAAY! We found {x} at position {position}")
print(f"💔 Sorry! {x} is not in the list.")

"".format()

print("💚 The number of nodes in single linked list is: {}".format(n))
print("💚 YAAAY! We found {} at position {}".format(x, position))
print("💔 Sorry! {} is not in the list.".format(x))

Personally, I go with f"" because it makes the code cleaner, and allows me to see exactly what variables are in the string, without having to call .format() at the end. I use this in the updated version of your code at the bottom of this answer, but you can choose.

# Unreachable Code

Here is your search method:

def search(self, x):
position =  1
p = self.start
while p is not None:
if p.info == x:
print("💚 YAAAY! We found " + str(x) + " at position " + str(position))
return True

# Increment the position
position += 1
# Assign the next node to the current node
else:
print("💔 Sorry! We couldn't find " + str(x) + " at any position. Maybe, try again later!")
return False

After you return True, it exits this method. So, the four lines of code after never get run. Ever. This code should be removed. The else is also unnecessary; I speak on that in the next section.

# Unnecessary else after return

After you return something in a body of an if, you don't need an else. If the if isn't executed, it will automatically go to the next code, which will execute that code. Take your display_list method:

def display_list(self):
if self.start is None:
print("💛 Single linked list is empty!")
return
else:
print("💚 Single linked list includes: ")
p = self.start
while p is not None:
print(p.info, " ", end=' ')
print()

Since you return in the initial if statement, the else is unnecessary. That code won't be run if the if is True, since the method will be exited after the return statement. This method should now look like this:

def display_list(self):
if self.start is None:
print("💛 Single linked list is empty!")
return
print("💚 Single linked list includes: ")
p = self.start
while p is not None:
print(p.info, " ", end=' ')
print()

# Redefining built in keywords

You have a variable named next in your code. Since this is a name of a function in the Python Standard Library, it should be avoided. You shouldn't use built in keywords as variable names. They can cause collision and other errors in your code. You can use a text editor such as Sublime Text 3, which will highlight these words at built in keywords.

# Constant Variable Naming

Constants in your program should be UPPER_CASE, to identify them as such.

Updated Code

"""
Method Docstring
A description of your program goes here
"""

class Node:
"""
Node Class Docstring
A description of this class goes here
"""

def __init__(self, value):
"""
Instantiates the node class
"""
self.info = value

"""
A description of this class goes here
"""

def __init__(self):
"""
Instantiates the single linked list class
"""
self.start = None

def create_list(self):
"""
"""
num_nodes = int(input("Enter the number of nodes in the list you wish to create: "))

if num_nodes == 0:
return
for _ in range(num_nodes):
data = int(input("Enter the element to be inserted: "))
self.insert_at_end(data)

def count_nodes(self):
"""
Counts the nodes of the single linked list
"""
start = self.start
count = 0
while start is not None:
count += 1
print(f"💚 The number of nodes in single linked list is: {count}")

def search(self, number):
"""
Searches the x integer in the linked list
"""
position = 1
start = self.start
while start is not None:
if start.info == number:
print(f"💚 YAAAY! We found {number} at position {position}")
return True
print(f"💔 Sorry! We couldn't find {number} at any position. Maybe, try again later!")
return False

def display_list(self):
"""
Displays the list
"""
if self.start is None:
print("💛 Single linked list is empty!")
return
print("💚 Single linked list includes: ")
start = self.start
while start is not None:
print(start.info, " ", end=' ')
print()

def insert_in_beginning(self, data):
"""
Inserts an integer in the beginning of the linked list
"""
temp = Node(data)
self.start = temp

def insert_at_end(self, data):
"""
Inserts an integer at the end of the linked list
"""
temp = Node(data)
if self.start is None:
self.start = temp
return

start = self.start

def insert_after(self, data, number):
"""
Inserts an integer after the x node
"""
start = self.start

while start is not None:
if start.info == number:
break

if start is None:
print(f"💔 Sorry! {number} is not in the list.")
else:
temp = Node(data)

def insert_before(self, data, number):
"""
Inserts an integer before the x node
"""

# If list is empty
if self.start is None:
print("💔 Sorry! The list is empty.")
return

# If x is the first node, and new node should be inserted before the first node
if number == self.start.info:
temp = Node(data)

# Finding the reference to the prior node containing x
start = self.start
break

print(f"💔 Sorry! {number} is not in the list.")
else:
temp = Node(data)

def insert_at_position(self, data, pos):
"""
Inserts an integer in k position of the linked list
"""
# if we wish to insert at the first node
if pos == 1:
temp = Node(data)
self.start = temp
return

start = self.start
i = 1

while i < pos - 1 and start is not None:
i += 1

if start is None:
print("💛 The max position is: " + i)
else:
temp = Node(data)
self.start = temp

def delete_node(self, node):
"""
Deletes a node of a linked list
"""
# If list is empty
if self.start is None:
print("💔 Sorry! The list is empty.")
return

# If there is only one node
if self.start.info == node:

# If more than one node exists
start = self.start
break

print(f"💔 Sorry! {node} is not in the list.")
else:

def delete_first_node(self):
"""
Deletes the first node of a linked list
"""
if self.start is None:
return

def delete_last_node(self):
"""
Deletes the last node of a linked list
"""
# If the list is empty
if self.start is None:
return

# If there is only one node
self.start = None
return

# If there is more than one node
start = self.start

# Increment until we find the node prior to the last node

def reverse_list(self):
"""
"""
prev = None
start = self.start
while start is not None:
prev = start
start = next_
self.start = prev

def bubble_sort_exdata(self):
"""
Bubble sorts the linked list with respect to data
"""
# If the list is empty or there is only one node
if self.start is None or self.start.link is None:
print("💛 The list has no or only one node and sorting is not required.")
end = None

start = self.start
if start.info > q.info:
start.info, q.info = q.info, start.info
end = start

"""
"""
# If the list is empty or there is only one node
if self.start is None or self.start.link is None:
print("💛 The list has no or only one node and sorting is not required.")
end = None

r = p = self.start
if p.info > q.info:
if  p != self.start:
else:
self.start = q
p, q = q, p
r = p
end = p

def merge1(self, list_two):
"""
"""
merge_list.start = self._merge1(self.start, list_two.start)
return merge_list

def _merge1(self, p1, p2):
"""
A description of this method goes here
"""
if p1.info <= p2.info:
start_m = Node(p1.info)
else:
start_m = Node(p2.info)
p_m = start_m

while p1 is not None and p2 is not None:
if p1.info <= p2.info:
else:

# If the second list is finished, yet the first list has some nodes
while p1 is not None:

# If the second list is finished, yet the first list has some nodes
while p2 is not None:

return start_m

# Testing

if __name__ == '__main__':

LIST_ONE.create_list()
LIST_TWO.create_list()

LIST_ONE.bubble_sort_exdata()
LIST_TWO.bubble_sort_exdata()

print("1⃣  The first list is: ")
LIST_ONE.display_list()

print("2⃣  The second list is: ")
LIST_TWO.display_list()

LIST_THREE = LIST_ONE.merge1(LIST_TWO)

print("The merged list by creating a new list is: ")
LIST_THREE.display_list()


text:
Phorgy Phynance

Network Theory and Discrete Calculus – Edge Algebra

with one comment

This post is part of a series

In my last post, I noted that in following John Baez’ series, I’m finding the need to introduce operators that I haven’t previously used in any applications. In this post, I will introduce another. It turns out that we could get away without introducing this concept, but I think it helps motivate some things I will talk about later.

In all previous applications, the important algebra was a noncommutative graded differential algebra. The grading means that the degree of elements add when you multiply them together. For example, the product of two nodes (degree 0) is a node (degree 0+0), the product of a node (degree 0) and a directed edge (degree 1) is a directed edge (degree 0+1), and the product of a directed edge (degree 1) with another directed edge is a directed surface (degree 1+1).

Note the algebra of nodes is a commutative sub-algebra of the full noncommutative graded algebra.

There is another related commutative edge algebra with corresponding edge product.

The edge product is similar to the product of nodes in that it is a projection given by

$\mathbf{e}_\epsilon^{i,j} \circ \mathbf{e}_{\epsilon'}^{k,l} = \delta_{\epsilon,\epsilon'} \delta_{i,k} \delta_{j,l} \mathbf{e}_\epsilon^{i,j}.$

It is a projection because for an arbitrary discrete 1-form

\begin{aligned}\alpha = \sum_{i,j} \sum_{\epsilon\in [i,j]} \alpha_{i,j}^{\epsilon} \mathbf{e}_\epsilon^{i,j},\end{aligned}

we have

$\mathbf{e}_\epsilon^{i,j} \circ \alpha = \alpha_{i,j}^{\epsilon} \mathbf{e}_\epsilon^{i,j}$

and

$\mathbf{e}_\epsilon^{i,j} \circ \mathbf{e}_\epsilon^{i,j} = \mathbf{e}_\epsilon^{i,j}.$

The product of two discrete 1-forms is

\begin{aligned}\alpha\circ\beta = \sum_{i,j} \sum_{\epsilon\in [i,j]} \alpha_{i,j}^{\epsilon} \beta_{i,j}^{\epsilon} \mathbf{e}_\epsilon^{i,j}\end{aligned}.

I have not yet come across an application where the full edge algebra is needed. When the product does arise, one of the discrete 1-forms is usual the coboundary of a discrete 0-form, i.e.

$\alpha\circ d\phi.$

When this is the case, the edge product can be expressed as a (graded) commutator in the noncommutative graded algebra, i.e.

$\alpha\circ d\phi = [\alpha,\phi].$

An example of this will be seen when we examine electrical circuits.


text:
# zbMATH — the first resource for mathematics

On stability of classes of Lipschitz mappings generated by compact sets of linear mappings. (English. Russian original) Zbl 0959.47008
Sib. Math. J. 41, No. 4, 656-670 (2000); translation from Sib. Mat. Zh. 41, No. 4, 792-810 (2000).
The article is devoted to a further development of the stability theory of classes of Lipschitz mappings in the framework of the concept of $$\omega$$-stability. The main object under study is the class of mappings described below. Suppose that $$G$$ is a nonempty compact subset of the space L$$(\mathbb R^n,\mathbb R^m)$$ of linear mappings from $$\mathbb R^n$$ into $$\mathbb R^m$$. The class of all locally Lipschitz mappings $$g\:\Delta\to\mathbb R^m$$ of domains $$\Delta\subset\mathbb R^n$$, for each of which there is a connected component $$K$$ of $$G$$ such that the differentials $$g'(x)$$ at almost all points $$x\in\text{dom }g$$ belong to $$K$$, is said to be $$(*)$$-generated by $$G$$ and denoted by $$\mathfrak Z(G)$$.
The author starts with proving the theorem claiming that if $$G$$ is a compact convex set then the class $$\mathfrak Z(G)$$ is $$\omega$$-stable. One of the main tools is the theorem about preservation of stability under set-theoretic operations on $$\omega$$-stable classes. As a result, the author completely solves the stability problem for the classes $$\mathfrak Z(G)$$ when either of the dimensions $$n$$ and $$m$$ equals 1. Using these results, the author obtains theorems on stability of classes of Lipschitz solutions to systems of linear partial differential equations and a theorem on $$\omega$$-stability of classes of conformal mappings which may simultaneously contain sense-preserving and sense-reversing mappings.
The author finds a fruitful application of the notion of weak connectedness of sets in vector spaces which was introduced into consideration for studying the structure of the image of the derivative of a differentiable vector-valued mapping.
##### MSC:
 47A55 Perturbation theory of linear operators 47B07 Linear operators defined by compactness properties 47B65 Positive linear operators and order-bounded operators 47F05 General theory of partial differential operators 46G05 Derivatives of functions in infinite-dimensional spaces 46T20 Continuous and differentiable maps in nonlinear functional analysis
Full Text:
##### References:
 [1] Reshetnyak Yu. G., Stability Theorems in Geometry and Analysis [in Russian], Nauka, Novosibirsk (1982). · Zbl 0523.53025 [2] John F., ”Rotation and strain,” Comm. Pure Appl. Math.,14, No. 3, 391–413 (1961). · Zbl 0102.17404 [3] Kopylov A. P., ”On stability of isometric mappings,” Sibirsk. Mat. Zh.,25, No. 2, 132–144 (1984). · Zbl 0546.30019 [4] Kopylov A. P., Stability in theC-Norm of Classes of Mappings [in Russian], Nauka, Novosibirsk, (1990). · Zbl 0772.30023 [5] Egorov A. A., ”On stability of classes of affine mappings,” Sibirsk. Mat. Zh.,36, No. 5, 1080–1095 (1995). · Zbl 0855.53016 [6] Egorov A. A., ”Stability of classes of Lipschitz continuous solutions to systems of first order linear differential equations,” Dokl. Akad. Nauk,356, No. 5, 583–587 (1997). [7] Egorov A. A., ”On stability of classes of Lipschitz continuous solutions to systems of first order linear differential equations,” Sibirsk. Mat. Zh.,40, No. 3, 548–553 (1999). · Zbl 0928.35042 [8] Korobkov M. V., ”On one generalization of connectedness and its application to differential calculus and stability theory,” Dokl. Akad. Nauk,363, No. 5, 590–593 (1998). · Zbl 0959.58006 [9] Korobkov M. V., ”On one generalization of the Darboux theorem to the multidimensional case,” Sibirsk. Mat. Zh.,41, No. 1, 118–133 (2000). · Zbl 0963.26006 [10] Bourbaki N., Varietétés Différentielles et Analytiques. Fascicule de Résultats [Russian translation], Mir, Moscow (1975).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
How to go about solving this first-order nonlinear differential equation?

1. Sep 23, 2012

Yondaime5685

I saw this post at stackexchange:
I ran across this post when trying to solve a homework problem. But I have no idea how he got that solution for that. When I use the Euler-Lagrange, I get this diff eq below.

Here is the simplest form I have managed to get it in:
$\frac{\alpha}{2\pi}=\frac{\eta \quad \dot{\eta}^2}{\sqrt{1+\dot{\eta}^2}}-\sqrt{1+\dot{\eta}^2}$

Where $\alpha$ is a constant. For the simplification, $\eta = (y-y_0)$ & $λ \equiv -2\pi y_0$ is used from the quote above.

I don't know where to even begin to solve this. Any help would be good.

Thanks.

-edit
Some details that I thought I should add.

Since $h=f+\lambda g≠h(x)$, I used the special case of the E-L equation:
$\dot{y}\frac{\partial h}{\partial \dot{y}}-h=const.$

But after the substituions to trim it up the special E-L turns into this:
$\dot{\eta}\frac{\partial h}{\partial \dot{\eta}}-h=const.=\alpha$
Where $h$ now is: $h=2\pi\eta\sqrt{1+\dot{\eta}^2}$

Last edited: Sep 23, 2012
2. Sep 24, 2012

voko

That should be $$\frac{\alpha}{2\pi}=\frac{\eta \dot{\eta}^2}{\sqrt{1+\dot{\eta}^2}}-\eta\sqrt{1+\dot{\eta}^2} = \eta [\frac{\quad \dot{\eta}^2}{\sqrt{1+\dot{\eta}^2}}-\sqrt{1+\dot{\eta}^2}]$$

Then you square the equation: $$(\frac{\alpha}{2\pi})^2= \eta^2 [\frac{\quad \dot{\eta}^4}{1+\dot{\eta}^2} -2 \dot{\eta}^2 + 1 + \dot{\eta}^2] = \eta^2 [\frac{\quad \dot{\eta}^4}{1+\dot{\eta}^2} -\dot{\eta}^2 + 1] \\ (\frac{\alpha}{2\pi})^2= \eta^2 \frac{\quad \dot{\eta}^4 -\dot{\eta}^2(1+\dot{\eta}^2) + (1+\dot{\eta}^2)} {1+\dot{\eta}^2} = \eta^2 \frac{\quad \dot{\eta}^4 -\dot{\eta}^2 - \dot{\eta}^4 + 1+\dot{\eta}^2} {1+\dot{\eta}^2} = \eta^2 \frac{1} {1+\dot{\eta}^2}$$

I assume you can continue from here.

3. Sep 24, 2012

Yondaime5685

Thanks a lot! That made the problem a lot simpler.

I can't believe I didn't carry that $\eta$ over.

Last edited: Sep 24, 2012


text:
# Complex analysis question

http://www.math.harvard.edu/~siu/math113/solution_homework_feb5a.pdf

Can someone explain me the solutions to the questions on page 1.

I am not sure how $|w-z| / |1-w \bar z|<1$ becomes $|w-z|^2 < |1-w\bar z|^2$

and later how the equation once you expand it has wz(bar)

-
For the former, multiply by $|1-w\bar{z}|$. Then square, which you're allowed to do with inequalities if both sides are positive (which absolute values are), since squaring is a monotone function. – fgp Oct 20 '12 at 17:41

It is not that the first inequality "becomes" the second one. What they're saying is: if the second inequality is true then so is the first one. Why? Because

$$|w-z|^2<|1-w\overline z|^2\Longrightarrow\left(\frac{|w-z|}{|1-w\overline z|}\right)^2<1\Longrightarrow \frac{|w-z|}{|1-w\overline z|}<1$$

as everything's positive here.

-


text:
Wednesday, October 7, 2015

# Random Forest with Python

## Introduction

In the article about decision tree we've talked about it's drawbacks of being sensitive to small variations or noise in the data. Today we'll see how to deal with them by introducing a random forest. It belongs to a larger class of machine learning algorithms called ensemble methods, which use multiple learning algorithms to obtain better predictive performance than could be obtained from any of the constituent learning algorithms. So which models does random forest aggregate? You might already know the answer - the decision trees. It fits a number of decision tree classifiers on various sub-samples of the dataset and use averaging to improve the predictive accuracy and control over-fitting.

## Implementation

Scikit-learn provides us with two classes RandomForestClassifier and RandomForestRegressor for classification and regression problems respectively. Let's use the code from the previous example and see how the result will different, using random forest with 100 trees.

...
clf = RandomForestClassifier(n_estimators=100).fit(X, y)
...

As you can see the edges are much smoother, that is less overfitted, than using a single decision tree.

## Conclusion

Despite it's relative simplicity, random forest performs the job remarkably well. According to empirical comparisons, even better than SVMs.


text:
# Floating point representation in IEEE 754 format

The following code takes a decimal number and gives its IEEE 754 floating point representation. However, the code is not complete and I am totally fine because it does the job for me:

1. It does not consider negative numbers.
2. The input number is not a fraction. Its always in the form xx.yy
3. As of now, it does not give representation in 32-bit or 64-bit format, it just gives exponent and significant value.

function toBinary (decimal) {
return decimal.toString(2);
}

function getIntegerPart (binary){
return binary.slice(0, binary.indexOf('.'));
}

function getFractionalPart (binary){
return binary.slice(binary.indexOf('.')+1);
}

function toNormalize (binary) {
var normalizedRep = new Object();
exponentValue = binary.indexOf('.')-1;
floatPosition = binary.indexOf('.');
normalizedRep.floatRep = binary[0]+ '.' + binary.slice(1, floatPosition) + binary.slice(floatPosition+1);
normalizedRep.exponentValue = exponentValue;
normalizedRep.floatPosition = floatPosition;
return normalizedRep;
}

function getSignificand (normalizedRep) {
return normalizedRep.floatRep.slice(normalizedRep.floatRep.indexOf('.')+1);
}

function twosComp() {
var decimal = 15.22;
var binary = toBinary(decimal);
var integerPart = getIntegerPart(binary);
var fractionalPart = getFractionalPart(binary);
var floatPosition = binary.indexOf('.');
var normalizedRep = toNormalize(binary);
var significand = getSignificand(normalizedRep);
var exponentValue = normalizedRep.exponentValue;

console.log(binary);
console.log(floatPosition);
console.log(normalizedRep.floatRep);
console.log(significand);
console.log(exponentValue);
}

I just don't get what you're trying to do. JavaScript does not know of integers, floats or any other numeric type, except for Number.
This data-type just happens to be a 64bit IEEE754 floating point value (or double in most strong-typed languages). This is clearly described in the official language specs

primitive value corresponding to a double-precision 64-bit binary format IEEE 754 value

NOTE A Number value is a member of the Number type and is a direct representation of a number.

So a float representation of a number is the number itself. If you want n number of significant digits, then there's a handy method for that:

var num = 123.321;
console.log(num.toFixed(2));//123.32

If you want the integer part of a non-integer number:

parseInt(num, 10);//123 (best to specify the radix)

If you want the remainder, either one of the following approaches will do:

num - parseInt(num, 10);
//or
num%1//modulo || remainder of division by 1

Note that in this last case, you will see the rounding errors of the IEE754 spec show up, so:

num = 123.321;
//get length of string rep for total number - int length,  -1 for .
var fix = (""+num).length - (""+parseInt(num, 10)).length - 1;
(num%1).toFixed(fix);

Might be required.

As far as the fraction representation of a number is concerned, that is going to take some work. Thankfully, it's all been done before and the code is available on github.

I don't know what you mean by: "It does not consider negative numbers", because, like I said before: there is but one type for numbers in JS, and so it's always signed. Just use the absolute value, and keep track of the what the number was initially (prositive or negative) like so:

function processNumber(num)
{
var sign = !(num > 0);//bool, true if num is negative
var workVal = Math.abs(num);//get absolute value
var returnObj = {};
returnObj.intVal = parseInt(workVal, 10);
returnObj.floatPart = (workVal%1).toFixed((""+workVal).length - (""+returnObj.intVal).length - 1);
returnObj.fixed2 = workVal.toFixed(2);
//and so on...
if (sign === true)
{
for (prop in returnObj)
{
if (returnObj.hasOwnProperty(prop))
{//they're all strings, just prepend the sign...
returnObj[prop] = '-' + returnObj[prop];
}
}
}
return returnObj;

• Seems I should have been clear about my code, apologizes for that. What my code does is, when you give a decimal number as input, it will give you its normalized representation with value of exponent and significand which will be stored in memory. The problem here I am trying to solve is, when you give a decimal number, how it will be stored in memory in IEEE-754 format.
– avi
Oct 31 '13 at 11:23
• @avi: That's exactly why I kicked off my answer with a link to the ECMA specification. All numbers are stored in IEEE-754 64bit numbers. With all quirks this format that entails. Oct 31 '13 at 11:50


text:
]> Ghost update 20110604: Death By Graphs

## Chirp Estimator Behavior: Overview

The process of chirp estimation fits a set of modulated sinusoids to a given audio signal. We pass in initial chirp parameter estimates and the estimator then improves these approximations to a desired level of fit precision. The parameters describing a chirp are the zeroth-order parameters P (phase) and A (amplitude), the first-order parameters W (frequency) and dA (amplitude modulation), and the second-order parameters dW (chirp rate or frequency modulation) and ddA (amplitude modulation squared).

At present, Ghost research uses a specific chirp estimation algorithm we published in 2007, and we'll likely continue using and improving this algorithm until something clearly better comes along. For this reason, it's essential we know what convergence and error to expect from it.

As alluded to in demo 2, the original 2007 paper had little space to devote to detailed algorithm characterization. The few graphs covered specific disjoint cases that were primarily concerned with efficiency as compared to other techniques. This data does not lead to a comprehensive, intuitive undestanding of how the chirp estimation performs given varied input data and operating parameters.

In this update, we concern ourselves with documenting the expected behavior of the chirp estimator, as well as what to expect from several optional improvements alluded to but left unexplored by the 2007 paper. Because chirp estimation is of general use in the field of signal processing, we do not focus only on expected use cases for Ghost. This documentation also serves as a benchmark archive for testing. Future improvments and optimizations can be compared against these known good results.

## Notes on Graph Generation

### code

The reference chirp estimator algorithm as well as code used to generate the graphs can be found in Xiph.Org's SVN at http://svn.xiph.org/trunk/chirptest. The module builds a standalone C application (using libcairo for drawing) named 'chirp' that when run produces all the graphs seen here. The application requires several hours of run time on a 32 core Opteron server to generate the graphs as seen here, so you probably don't want to try it on a netbook.

### errata

Except where noted, graphs are generated using the algorithms as described in the paper linked above. The paper contains an algebraic sign error on Page 11 in Algorithm 2; the 12th line has a '+' which should be a minus. Specifically it should read:

$u k † ← - A ¨ k  sin Φ k - A k  Θ ˙ k  cos Φ k$

### precision

The algorithms are implemented in single precision float arithmetic with the exception of the instantaneous phase calculation in the basis chirp generation. A naive calculation such as cosf(P+(W+dW*i)*i) runs out of bits in the mantissa of the single-precision argument to cosf() as W and i increase. For the sake of simplicity and clarity, the naive calculation is used but implemented and passed in double precision.

### termination and convergence

The termination criteria for convergence is a simple magnitude threshold. The algorithm is declared to have converged when the sum of the squares of the basis projections for each chirp are all less than 1e-12. This value is chosen to be large enough to sit comfortably above numerical noise (between 1e-16 and 1e-14), but small enough to show a substantial amount of the algorithm's depth of precision. The convergence graphs plot the number of iterations required before the final uncounted iteration results in a change below the termination threshold. The error graphs give the worst-case performance for our specific termination criteria across all values of any swept input.

Keep in mind that 'convergence' simply means that the estimation algorithm arrived at a stable solution and halted. It does not mean that the solution is correct or sufficiently accurate. Consult both the convergence and error graphs to determine the trustworthy domain of operation.

## Linear vs Non-linear Operation

### Algorithms in the 2007 paper

The paper offers two variants of the chirp estimation algorithm, linear and non-linear. The linear and non-linear algorithms differ primarily in that the non-linear algorithm 'recenters' the W parameter (frequency) each iteration, that is, it regenerates the basis functions with an updated W estimate each iteration as well as restarting the residual error calculation. Basis generation is a relatively expensive operation, and the nonlinear estimator repeats basis generation for each chirp in each iteration. Thus, although the conceptual difference between the linear and non-linear algorithms is small, the computational cost is potentially substantial.

### Recentering dW

The non-linear algorithm in the paper does not recenter the dW (chirp rate) parameter. In addition, it also assumes an initial dW estimate of 0, thus avoiding the dW term in basis generation completely:

$an,kc = h(n)  cosΘkn , (36) an,ks = h(n)  sinΘkn , (37) an,kd = h(n)  n  cosΘkn , (38) an,kt = h(n)  n  sinΘkn , (39) an,kf = h(n)  n 2  cosΘkn , (40) an,ku = h(n)  n 2  sinΘkn (41)$

This is an intentional optimization to reduce the basis generation and projection complexity; if unchirped, the basis functions show symmetry/antisymmetry about their centers.

We recenter the dW parameter by modifying the basis functions:

$an,kc = h(n)  cos( Θk n + Θ˙k n2 ) , (‡36) an,ks = h(n)  sin( Θk n + Θ˙k n2 ) , (‡37) an,kd = h(n)  n  cos( Θk n + Θ˙k n2 ) , (‡38) an,kt = h(n)  n  sin( Θk n + Θ˙k n2 ) , (‡39) an,kf = h(n)  n2  cos( Θk n + Θ˙k n2 ) , (‡40) an,ku = h(n)  n2  sin( Θk n + Θ˙k n2 ) (‡41)$

This basis modification also requires modifying the dW update step in Algorithm 2:

$Δ Θ ˙ k † ← fk  sk - uk  ck A k 2 , Θ ˙ k † ← Θ ˙ k + Δ Θ ˙ k$

Using and recentering the dW parameter has benefits, improving both convergence range and dW accuracy. We will document the estimator performance both of 'partial' non-linear operation (recentering only W with an unchirped basis as described in the paper) as well as 'full' non-linear operation (recentering both W and dW with chirped basis functions).

### data

The graphs below show behavior of the linear, partial-nonlinear and full-nonlinear estimators across sets of single-chirp input signals. Estimation was performed with a sine input window and other parameters as in the original 2007 paper.

Near DC, convergence and error behavior most strongly depend on chirp center frequency (W); the following graphs show behavior from DC extending to a few bins above DC. In addition, the phase of an input chirp affects behavior at the edge of convergence, so all graphs show the worst-case behavior run over a swept-phase set of inputs. Estimator behavior is exactly anti-symmetric about the center of the spectrum.

Frequency (W) convergence and error behavior

Graph Selection

Iteration type

As expected, the linear algorithm shows reliable convergence behavior but as it does not restart the basis functions or error estimates, error increases steadily above and below Y=0 where the input W estimate already matches the chirp W before iteration. Both the partial- and full-nonlinear algorithms show reduced convergence range but high precision across the domain of frequency convergence making the total domain of useful output much larger than the linear estimator. This comes at the cost of a more expensive algorithm.

Chirp rate (dW) convergence and error behavior

Graph Selection

Iteration type

The linear algorithm shows dW (chirp rate) convergence and error behavior similar to frequency (W) behavior.

The partial-nonlinear algorithm shows error behavior similar to the linear algorithm once there's a significant dW (chirp) component to the input signal. This is not surprising as the partial-nonlinear algorithm is not recentering the basis functions for dW changes and the calculated residual error is also an approximation computed from the basis functions.

The full-nonlinear algorithm shows vastly improved dW behavior similar to W behavior. It gives accurate results across the nearly-complete domain of convergence, which is greatly expanded over the partial-nonlinear algorithm. With the proper window, we can in fact expand the domain of convergence to an arbitrarily large portion of the solution space. More about this later under the section on windowing functions.

A chirp's actual W does not strongly influence the convergence or accuracy of the algorithm once it is more than 5-10 bins above DC (or below Nyquist). W can still affect numerical noise; depending on how the basis and reconstruction chirps are generated, an approach such as cos(W*t) shows a linear loss of precision as |t| or W increases. As such, single-precision basis/reconstruction chirp generation can show noticably more noise near Nyquist than at DC.

## Influence of Windowing Functions

FFT techniques tend not to be particularly sensitive to exact window choice; there's a set of mostly interchangable 'good' windows that give similar performance for most uses. Unless you have a very specific need, the Hanning window covers 95% of what any DSP engineer would ever need for use with Fourier transforms. This is not the case with the chirp estimator. The window function used for input and basis windowing exerts considerable influence on algorithm accuracy and convergence behavior.

• As with the FFT, window mainlobe width and shape influences discrimination ability (the ability to resolve closely spaced sinusoids/chirps).
• Mainlobe slope partially determines convergence speed.
• Mainlobe width determines the convergence range of the nonlinear iterator; it cannot converge to values beyond the first null in the window transfer response. Convergence can also 'hang up' in local maxima in the mainlobe response.
• In that same vein, sidelobes create local maxima away from the mainlobe. The estimator essentially marches 'up' to peaks in the input signal's windowed response, and so local maxima created by sidelobes will also capture convergence.
• Sidelobe leakage, as with the FFT, spreads noise through the spectrum into the results for other sinusoids. The exact behavior is different due to use of Gauss-Seidel fitting, which removes the energy of each fit sinusoid from the error term of all sinusoids. However, unfit energy still exhibits full sidelobe leakage.

This all points to the possibility that a unimodal window without sidelobes could render the nonlinear estimator's solution space substantially convex for single-chirps and indeed this turns out to be the case. The W and dW terms can be made to converge from initial estimates arbitrarily far away from the correct value. This comes at the cost of typically slower convergence (unimodal windows tend to be broader and roll-off more slowly) and some reduction in convergence domain near DC.

A few window functions for testing purposes

Window Selection

### Window functions and linear estimation

Window functions affect linear estimation less profoundly than non-linear estimation. W and dW are not being recentered and as such can't become stuck in local maxima caused by sidelobe leakage. Nonetheless, we expect a window function to influence overall error behavior.

Window effect on linear estimation of W

Graph Selection

Window

In the above graphs we do indeed see improvement in both absolute error performance and convergence speed depending on window selection. The useful range of linear estimation can be enhanced by at least a factor of two with an appropriate choice of window.

### Window functions and non-linear estimation

Non-linear estimation is quite sensitive to the window function in use as the W and dW parameters track along the frequency domain energy contours created by the window's mainlobe and sidelobe. Where the linear estimator is ~guaranteed to converge (once we're away from DC/Nyquist), we've already noticed that the nonlinear estimator does not have an inherently convex solution space. A unimodal window, however, can render the solution space similarly convex.

Also of interest are optimized windows that attempt to deliver wider convergence without loss of convergence speed. Machine optimization has shown a few promising window research directions.

NOTE: the scales on the nonlinear graphs cover a considerably wider range than on the linear graphs.

Window effect on nonlinear estimation of W

Graph Selection

Window

## First- vs Second-Order Operation

The paper states that second-order parameter fits (dW and ddA) are optional to both the linear and nonlinear algorithms. The nonlinear algorithms are also capable of fitting only one of the second order parameters (while clamping the other to zero), such as we've been doing in the nonlinear graphs above, where we fit dW but not ddA.

(Strictly speaking, the same is true of the first-order parameters; we could choose to fit W and not dA for example. However, because of the alternating even/odd orthogonality of the basis functions, fitting only W and not dA has almost no effect on algorithm behavior. This is visible in the first-order nonlinear graphs below. The same is not true of fitting dW but not ddA.)

First and second order estimation behavior

Graph Selection

Algorithm

Order

The linear algorithm does not fit each of the paired parameters separately the way the nonlinear algorithms do. As such we do not plot the 'half orders' for the linear estimator.

## Symmetric Normalization

The chirp estimation algorithm does not use complex math; the four (or six) basis functions used by chirp estimation are all real sequences. However, because the basis functions are quadrature (sine/cosine) pairs, they behave in some ways similarly to the real/imaginary halves of a complex basis.

The linear estimator calculates basis energies once at the beginning of fitting. The nonlinear estimators must recalculate basis and basis energy in each iteration.

If we treat the sine/cosine basis pairs as if they were a single complex basis, the energy of the three complex basis functions is described by:

$energykc,s ← ∑ n=- N-12 N-12 [ h(n)  cosφk,n ] 2 + [ h(n)  sinφk,n ] 2 = ∑ n=- N-12 N-12 h2 (n)  [ cos2 φk,n + sin2 φk,n ] = ∑ n=- N-12 N-12 h2 (n) energykd,t ← ... ... ∑ n=- N-12 N-12 h2 (n)  n2 energykf,u ← ... ... ∑ n=- N-12 N-12 h2 (n)  n4$

Rather than normalizing each of the six real basis projections by the basis energy, we instead normalize by half the 'complex' basis energy. This approximation results in basis energy being determined solely by the window and blocksize, and we can both simplify and move the calculation out of the nonlinear loop.

Effect of symmetric normalization on W (frequency) fit

Parameter fit

Graph Selection

Algorithm

Normalization

Symmetric normalization approximately halves the number of adds and multiplies needed during the basis projection step of the nonlinear algorithms, as normalization energy is not explicitly calculated. That said, the time spent generating new, recentered basis functions each iteration typically swamps the cost of the actual basis projection onto the error vector. As such the time saved by symmetric normalization may be insignificant, depending on the relative expense of basis generation.

The linear algorithm generates basis functions only once and so must compute normalization factors only once. Symmetric normalization may become useful in the event that the linear algorithm is run repeatedly for only a few iterations each time, thus increasing the relative amount of time the linear algorithm would spend calculating normalization factors during initialization.

## dW alpha

Page 10 of the 2007 paper discusses the quantity 'alpha' (α) which is described as an update rate used to scale the update added to the W parameter each iteration:

$Θ k ← Θ k + α  Δ Θ k$

The paper presents a graph that shows the optimal value for alpha is about 1.0. The exact relationship between W convergence speed and alpha is slightly more complex, but 1.0 does hold up as a good value for alpha upon closer inspection. The optimal value of alpha is affected somewhat by window choice.

Effect of alpha on W (frequency) fit

Graph Selection

Window

In the fully nonlinear estimator, a similar update scaling coefficient can be applied to the dW update quantity:

$Θ ˙ k † ← Θ ˙ k + α Δ Θ ˙  Δ Θ ˙ k$

Adjusting the dW alpha parameter (that is, $αΔΘ ˙$) affects speed of convergence for both W and dW.

Effect of dW alpha on W and dW convergence

Parameter fit

Window

The W convergence graph is generated with -60dB of background white noise added to eliminate spurious convergence behavior when the algorithm is operating near the limits of numeric accuracy.

The original W alpha value is affected by window choice, but the dW alpha parameter is much more so. The graphs make it clear that the optimal alpha for dW updates depends strongly on window and that we can do much better than a value of 1.0.

The following graphs replot the near-DC behavior for several windows as presented earlier, but selects a dW alpha appropriate for the window to show the effect on convergence speed and error behavior.

Effect of dW alpha on near-DC behavior

Parameter fit

Graph Selection

Window

dW alpha value

## Noise Behavior

The effect of noise on estimation algorithm behavior is mostly uninteresting. As with the FFT, larger block sizes decrease the relative contribution of noise. Noise energy contribution to the fit parameters is governed primarily by the equivalent noise bandwidth of the window in use.

The graphs below illustrate that noise has little effect on convergence speed and none on stability, and contributes energy to fit parameters as predicted by window characteristics. As with all the graphs here, the plots below use a blocksize of only 256 samples.

Effect of white noise on chirp estimation

Parameter fit

Graph Selection

Window

algorithm

RMS noise level

## Mutliple Chirp Interaction

Two behaviors mostly determine the ability of the chirp estimation algorithm to discriminate and individually resolve closely spaced peaks. The specifics of both are determined by the choice of window function.

### orthogonality limit

Neither the input data chirps nor the basis functions used by the chirp estimator are orthogonal to one another; they are merely usually 'mostly orthogonal'. The farther apart chirps (and chirp estimates) are, the less chirps and fit estimates interact.

Fit accuracy of closely spaced sinusoids and chirps is limited by the effective orthogonality. As with the FFT, the wider the mainlobe of the window in use, the worse the 'in-close' frequency discrimination.

Sinusoid discrimination: accurate estimate

Graph Selection

Window

algorithm

In order to demonstrate orthogonality limits in isolation, the graphs above show an approximately best case situation using an accurate initial estimate (exact W estimate, all other parameters randomized within +/-.1 of correct value and amplitude within +/-.1dB). Additional estimate error does not affect orthogonality limits or behavior, but it can bring main/sidelobe capture into play.

### mainlobe/sidelobe capture

The chirp estimator is essentially a gradient-climbing [non-]linear solver; it walks up the hill of an objective function until it reaches the top. Just like in the FFT, the energy leakage from a strong peak (both mainlobe and sidelobe) can swamp weaker peaks in the immediate vicinity, either moving the apparent maximum or disguising it completely.

The chirp estimator both fits peaks in order of estimated energy and subtracts already-estimated energy from the fitting process. This reduces the apparent energy leakage and unmasks weaker genuine peaks in the same immediate vicinity. The chirp estimator is thus potentially better able to discriminate closely spaced peaks than the FFT when using the same window function.

However, this extra discrimination gain is conditional on a good enough initial estimate. In the nonlinear algorithms, a poor initial estimate allows strong peaks to 'capture' weaker peaks in the first few iterations by deflecting the W and dW estimates of weaker peaks too far toward the stronger peak. Recentering causes them to collapse into the stronger peak. The linear algorithm does not recenter the W (or dW) parameter, and so it does not exhibit main/sidelobe capture.

Though the quality of the initial estimate does not, for the most part, affect the absolute error of the final nonlinear fit, we can see in the graphs below that there is an 'event horizon' beyond which the energy leakage of a strong peak captures the initial estimate of the weaker peak, causing it to converge to the wrong chirp. This event horizon is at the point where leakage energy from a stronger peak is approximately as strong as the weaker peak itself.

Sinusoid discrimination: main/sidelobe capture

Graph Selection

Window

algorithm

The graphs above illustrate sidelobe capture resulting from a poor initial estimate. Each plots the fit of an unchirped sinusoid in the immediate vicinity of a stronger reference sinusoid. Both sinusoids are fit using exact initial estimates but with amplitudes of zero. The weaker sinusoid's estimate is placed first in the list so that without amplitude estimates it is fit first in the initial iteration. As such, the plots show the limits of main/sidelobe capture when the weaker sinusoid is captured by the energy leakage of the stronger sinusoid.

### realistic estimate error

We now graph fit behavior of realistic initial estimates, approximately intended to match the level of accuracy we could reasonably achieve by estimating parameters from an initial FFT. The full-nonlinear algorithm is substantially unaffected by additional estimate uncertainty so long as we avoid main/sidelobe capture. The partial-nonlinear estimate behaves as well so long as the dW estimate is accurate. The linear algorithm requires both an accurate W and dW parameter.

The first graphs plot two unchirped sinusoids, so we see similar excellent behavior from the full- and partial-nonlinear algorithms. The error in the W estimate degrades the linear algorithm's performance.

Sinusoid discrimination: realistic estimate

Graph Selection

Window

algorithm

The graphs above use randomized estimates with A (amplitude) within 6dB, W (frequency) within .5 FFT bins and P (phase) within .1 radians. For purposes of visual presentation, W estimate error is randomized away from the neighboring chirp; this keeps apparent mainlobe width the same. A estimate error is also randomized away from the neighboring chirp's value in order to guarantee that the amplitude sort order remains correct in all trials.

We note that the 'realistic' estimate shows some main/sidelobe capture due to remaining estimate error from the stronger sinusoid. In the region outside of capture, we see that the fit error and convergence behavior are largely unaffected by the additional initial estimate error as expected.

Using the same estimate bounds parameters, the graphs below illustrate the interaction of frequency (W) and chirp rate (dW) when discriminating a test chirp from a central reference sinusoid. Note that no initial estimate is given for the chirp rate (it is zero) as an FFT cannot be used to estimate chirp rate directly.

Chirp discrimination: realistic estimate

Graph Selection

Window

algorithm

test chirp amplitude

As expected, we see continued excellent error performance from the full-nonlinear algorithm. The partial-nonlinear algorithm cannot recenter dW and thus shows degraded performance due to the initial dW estimate of zero. The linear algorithm is doubly hurt by the error in both W and dW.

## In Conclusion....

First and foremost, we finally have a fairly extensive characterization of the behavior we can expect from our chirp estimator. This characterization comes with benchmarking code useful for both optimization and regression testing.

Most of the conclusions from the graphs are nuanced and numeric; they are better presented in visual form than in a text summary. However, a few particularly interesting concepts are worth repeating.

### General points

• The algorithm cannot accurately fit frequencies within a few FFT bins of DC and the Nyquist frequency.
• Convergence shape at DC and Nyquist are antisymmetric about the center of the spectrum.
• The algorithm has an effectively similar behavior when fitting two very closely spaced chirps.
• Noise does not affect convergence or stability beyond adding to final fit uncertainty.
• Fitting fewer parameters speeds convergence and reduces error for the parameters that are fit.
• Although the W 'alpha' update factor appears to always optimally be 1.0, the conceptually analagous 'alpha' factor for dW has a non 1.0 optimal value that depends on input window.

### Linear vs. Nonlinear

• The linear algorithm is very fast. Final fit quality directly depends on initial W and dW estimate quality.
• The partial-nonlinear algorithm is much slower, but final fit is independent of W initial estimate (subject to main/sidelobe capture). Fit quality still depends on initial dW estimate quality.
• The full-nonlinear algorithm (depending on implementation) is slightly slower than the partial-nonlinear algorithm, but final fit quality does not depend on initial estimate (subject to main/sidelobe capture).

### Windows

• Choice of window function is somewhat more important to chirp estimator performance than might be expected by an engineer used to the FFT. The window function affects both speed and domain of convergence.
• With a proper window, the nonlinear algorithms can reliably converge to final fits arbitrarily far from initial estimate.
• Unimodal windows only offer full-range convergence when the input signal is almost free of noise.

As always, happy hacking!

Ghost development work is sponsored by Red Hat Emerging Technologies.