Find the Approximate Value of the Smallest Possitive Solution

The Structures of Ring and Field

Maurice R. Kibler , in Galois Fields and Galois Rings Made Easy, 2017

1.2.7 Characteristic of a field

The definition of the characteristic of a unitary ring applies to a field since a field is a particular unitary ring. In terms of field, we have the following formulation.

1.2.7.1 Characteristic

Definition 1.20

The characteristic of a field ( $\mathbb{K}$ , +, ×) is the smallest positive integer p (p  ≥   2) such that

$\forall x\in \mathbb{K}:p\times x=0\iff 1+1+\cdots +1=0$

where the sum contains p terms. If $1+1+\cdots +1\ne 0$ whatever the number of 1 in the sum is, then the field is said to be of characteristic 0.

1.2.7.2 Example: ${\mathbb{Z}}_p$ , with p prime

The field ${\mathbb{Z}}_p$ (p prime) is a field of characteristic p. We will see that there are other fields of characteristic p.

1.2.7.3 Example: $\mathbb{Q},\mathbb{R},\mathbb{C}$ and $\mathbb{H}$

The field of rational numbers $\mathbb{Q}$ , the field of real numbers $\mathbb{R}$ , the field of complex numbers $\mathrm{ℂ}$ and the field of quaternions $\mathbb{H}$ are fields of characteristic 0.

1.2.7.4 Possible values of the characteristic of a field

Proposition 1.8

The characteristic of a field is either zero (for infinite fields) or a prime number (for finite fields).

In other words, if a field has a non-vanishing characteristic, then its characteristic is a prime number and the field is finite. A field of characteristic 2 is called a binary field (the field ${\mathbb{F}}_2$ is the smallest of the binary fields).

1.2.7.5 Characteristic of two isomorphic fields

Proposition 1.9

Two isomorphic fields have the same characteristic.

1.2.7.6 Characteristic of a sub-field

Proposition 1.10

Let $\mathbb{J}$ be a proper sub-field of a field $\mathbb{K}$ . The fields $\mathbb{J}$ and $\mathbb{K}$ have the same characteristic.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9781785482359500014

Random Matrices

In Pure and Applied Mathematics, 2004

1.3.1 Level Density

As the excitation energy increases, the nuclear energy levels occur on the average at smaller and smaller intervals. In other words, level density increases with the excitation energy. The first question we might ask is how fast does this level density increase for a particular nucleus and what is the distribution of these levels with respect to spin and parity? This is an old problem treated by Bethe (1937). Even a simple model in which the nucleus is taken as a degenerate Fermi gas with equidistant single-particle levels gives an adequate result. It amounts to determining the number of partitions Λ(n) of a positive integer n into smaller positive integers v ₁, v ₂, …

$\begin{array}{ll}n=v_1+v_2+\cdots +v_{\ell },\hfill & v_1⩾v_2\hfill \end{array}⩾\cdots ⩾v_{\ell }>0.$

For large n this number, according to the Hardy-Ramanujan formula, is given by

$\lambda (n)\sim \exp \left[{(\theta {\pi }^{2}n/3)}^{1/2}\right],$

where θ is equal to 1 or 2 according to whether the v_i are all different or whether some of them are allowed to be equal. With a slight modification due to later work (Lang and Lecouteur, 1954; Cameron, 1956). Bethe's result gives the level density as

$\rho (E,j,\pi )\propto (2j+1){(E-\Delta )}^{-5/4}\exp \left[-j(j+1)/2{\sigma }^2\right]\exp \left[2a{(E-\Delta )}^{1/2}\right],$

where E is the excitation energy, j is the spin and π is the parity. The dependence of the parameters σ, a and Δ on the neutron and proton numbers is complicated and only imperfectly understood. However, for any particular nucleus a few measurements will suffice to determine them all; the formula will then remain valid for a wide range of energy that contains thousands and even millions of levels.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S0079816904800916

Ordinary differential equations

Brent J. Lewis , ... Andrew A. Prudil , in Advanced Mathematics for Engineering Students, 2022

Method of undetermined coefficients

Similar to Section 2.2.5 for second-order differential equations, this method gives $y_p$ for the constant coefficient equation

(2.81)

In fact, the only difference from Section 2.2.5 concerns the modification rule since now the characteristic equation of the present homogeneous equation

(2.82)

can have multiple roots (that is, greater than simple or double roots). The basic rules are summarized as follows:

(a)

Basic rule as in Section 2.2.5 with Table 2.4.

(b)

Modification rule. If the choice for $y_p$ is also a solution of the homogeneous Eq. (2.82), then multiply $y_p(x)$ by $x^k$ , where k is the smallest positive integer such that no term of $x^k{y}_p(x)$ is a solution of Eq. (2.82).

(c)

Sum rule as in Section 2.2.5 with Table 2.4.

Example 2.3.5

(rule b) Solve $y^{‴}+6y^{″}+12y^{\prime }+8y=6e^{-2x}$ .

Solution.

(i) The characteristic equation ${\lambda }^3+6{\lambda }^2+12\lambda +8={(\lambda +2)}^3=0$ has a triple root $\lambda =-2$ . Hence by Section 2.3 (Case III), $y_h=c_1{e}^{-2x}+c_{2}x{e}^{-2x}+c_3{x}^2{e}^{-2x}$ .

(ii) With $y_p=C{e}^{-2x}$ , one obtains $-8C+24C-24C+8C=6$ (that is, there is no solution). Therefore, by rule (b) choose $y_p=C{x}^3{e}^{-2x}$ . As such, $y_p^{\prime }=C(-2x^3+3x^2)e^{-2x}$ , $y_p^{″}=C(4x^3-12x^2+6x)e^{-2x}$ , and $y_p^{‴}=C(-8x^3+36x^2-36x+6)e^{-2x}$ . Substituting these expressions into the differential equation gives $(-8x^3+36x^2-36x+6)C+6(4x^3-12x^2+6x)C+12(-2x^3+3x^2)C+8x^{3}C=6$ . Simplifying, one obtains $C=1$ . Thus, the general solution is given by $y=y_h+y_p=(c_1+c_{2}x+c_3{x}^2)e^{-2x}+x^3{e}^{-2x}$ . [answer]

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128236819000101

LINEAR STATE-SPACE MODELS AND SOLUTIONS OF THE STATE EQUATIONS

BISWA NATH DATTA , in Numerical Methods for Linear Control Systems, 2004

5.3.5 Evaluating an Integral with the Matrix Exponential

We have discussed methods for computing the matrix exponential. We now present a method due to Van Loan (1978) to compute integrals involving exponential matrices.

The method can be used, in particular, to compute the state-space solution (5.3.3) of the Eq. (5.3.1), and the controllability and observability Grammians, which will be discussed in the next chapter.

The method uses diagonal Padé approximation discussed in the last section.

Let

$\begin{array}{cc}H(\Delta )={\int }_0^{\Delta }{e}^{As}Bds,& M(\Delta )={\int }_0^{\Delta }{e}^{A^{Ts}}QH(s)ds,\\ N(\Delta )={\int }_0^{\Delta }{e}^{A^{Ts}}Q{e}^{As}ds,& W(\Delta )={\int }_0^{\Delta }H{(s)}^{T}QH(s)ds\end{array}$

where A and B are matrices of order n and n × m, respectively, and Q is a symmetric positive semidefinite matrix.

Algorithm 5.3.3.

An Algorithm for Computing Integrals involving Matrix Exponential.

Inputs.

A—The n × n state matrix

B—An n × m matrix

Q—A symmetric positive semidefinite matrix.

Outputs. F, H, Q, M, and W which are, respectively, the approximations to e ^AΔ, H(Δ), N(Δ), M(Δ), and W(Δ).

Step 1.

Form the (3n + m) × (3n + m) matrix

$\hat{C}=\left(\begin{array}{cccc}-A^{\text{T}}& l& 0& 0\\ 0& -A^{\text{T}}& Q& 0\\ 0& 0& A& B\\ 0& 0& 0& 0\end{array}\right).$

Find the smallest positive integer j such that $(|\left|\hat{C}\Delta \right|{|}_{\text{F}}/2^j)\le \frac{1}{2}$ . Set t ₀ = (Δ/2 ^j ).

Step 2.

For some q ⩾ 1, compute

$Y_0=R_{qq}\left(\frac{\hat{C}\Delta }{2^j}\right),$

where R _qq is the (q, q) Padé approximant to e ^z :

$\begin{array}{cc}{R}_{qq}(z)=\frac{{\Sigma }_{k=0}^z{c}_k{z}^k}{{\Sigma }_{k=0}^q{c}_k{(-z)}^k},& where{c}_k=\frac{(2q-k)!q!}{(2q)!k!(q-k)!}\end{array}.$

Write

$Y_0=\left(\begin{array}{cccc}{F}_1(t_0)& G_1(t_0)& H_1(t_0)& K_1(t_0)\\ 0& F_2(t_0)& G_2(t_0)& H_2(t_0)\\ 0& 0& F_3(t_0)& G_3(t_0)\\ 0& 0& 0& F_4(t_0)\end{array}\right)$

and set

$\begin{array}{l}\begin{array}{ll}{F}_0=F_3(t_0)\hfill & M_0=F_3{(t_0)}^{\text{T}}{H}_2(t_0)\hfill \\ H_0=G_3(t_0)\hfill & W_0=[B^{\text{T}}{F}_3{(t_0)}^{\text{T}}{K}_1(t_0)]+{(B^{\text{T}}{F}_3{(t_0)}^{\text{T}}{K}_1(t_0)]}^{\text{T}}.\hfill \end{array}\\ Q_0=F_3(t_0){}^{\text{T}}{G}_2(t_0).\end{array}$

Step 3.

For k = 0, 1,…, j − 1 do

$\begin{array}{l}{W}_{k+1}=2W_k+H_k^T{M}_k+M_k^T{H}_k+H_k^T+H_k^T{Q}_k{H}_k\\ M_{k+1}=M_k+F_k^{\text{T}}[Q_k{H}_k+M_k]\\ Q_{k+1}=Q_k+F_k^{\text{T}}{Q}_k{F}_k\\ H_{k+1}=H_k+F_k{H}_k\\ F_{k+1}=F_k^2\end{array}$

End

Step 4.

Set F ≡ F _j , H ≡ H _j , Q ≡ Q _j , M ≡ M _j , and W ≡ W _j .

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780122035906500094

Stream Ciphers and Number Theory

In North-Holland Mathematical Library, 2004

3.2 Two Basic Problems from Stream Ciphers

For sequences of period N over the field GF(q), their linear and sphere complexity are closely related with the factorization of cyclotomic polynomials Q _n (x) over GF(q) for all factors n of N. Proposition 3.1.1 says that Q _n (x) factors into ϕ(n)/d distinct monic irreducible polynomials in GF(q) of the same degree d, where d is the least positive integer such that q ^d ≡ 1 (mod n). It follows that, to design sequences with both large linear and sphere complexity, we should find pairs (N, q) such that

1.

N has as few factors as possible; and

2.

for each factor n of N, d = ord _n (q) should be as large as possible.

This leads to the following two basic problems in designing cryptographic sequences for certain applications.

Basic Problem 1

Find large positive integers N and small positive integers q which are powers of primes such that

1.

gcd(N, q) = 1;

2.

ord _n (q) = ϕ(n) for any factor n ≠ 1 of N.

Basic Problem 2

Find large positive integers N and small positive integers q, q a power of a prime, such that

1.

gcd(N, q) = 1;

2.

N has few factors;

3.

ord _n (q), a factor of ϕ(n), is as large as possible for any factor n ≠ 1 of N.

An integer q is said to be a primitive root of (or modulo) n if ord _n (q) = ϕ(n). If g ≡ g' (mod N), then g' is a primitive root of N if and only if g' is a primitive root of N. So for our cryptographic purposes, we discuss here and hereafter primitive roots modulo N only in the range between 2 and N − 1. To study the two problems further, we need the following important result of Gauss whose proof can be found in most books about number theory.

Proposition 3.2.1

If p is a prime, then there exist ϕ(p − 1) primitive roots of p. The only integers having primitive roots are p ^e , 2p ^e , 1, 2 and 4, with p being an odd prime.

This proposition shows that Basic Problem 1 has a solution if and only if N = r ^k , or 2r ^k , with r being an odd prime. We shall investigate this basic problem in detail in Sections 3.4 and 3.5.

Before dealing with Basic Problem 2, we present some basic results about the order of integers modulo n. If gcd(a, n) = 1, Euler's theorem states that a ^ϕ(n) ≡ (mod n). This implies that ord _n (a) divides ϕ(n). The order of a has a close relation to the Carmichael function λ(n), which is defined by

$\begin{array}{l}\text{λ}\left(1\right)=1,\text{λ}\left(2\right)=1,\text{λ}\left(4\right)=2,\\ \text{λ}\left(2^r\right)=2^{r-2}\left(\text{for}r\ge 3\right)\cdot \\ \text{λ}\left(p^r\right)=p^{r-1}\left(p-1\right)=\varphi \left(p^r\right)\text{for}\text{any}\text{odd}\text{prime}p\text{and}r\ge 1,\\ \text{λ}\left(2^r{p}_1^{r_1}{p}_2^{r_2}\cdots p_s^{r_s}\right)=\text{lcm}\left(\text{λ}\left(2^r\right),\text{λ}\left(p_1^{r_1}\right),\cdots ,\text{λ}\left(p_s^{r_s}\right)\right),\end{array}$

where lcm denotes the least common multiple. It is not difficult to see that the order of a modulo n is at most equal to λ(n), and that λ(n) divides ϕ(n).

It seems difficult to solve Basic Problem 2 completely. However, for those N's which are a product of two distinct primes, it is possible to find the associated q's such that (N, q) is a solution of Basic Problem 2. We shall deal with this problem in Section 3.8.

Before ending this section, we make some preparations for the following two sections. Specifically, we introduce now the concept of negative order of an integer a modulo an integer N, and discuss the relation of the negative order with the order.

Definition 3.2.2

Let N and a be positive integers. If there is a positive integer m such that a ^m ≡ −1 (mod N), then we call the smallest such m the negative order of a modulo N (we coin the word "negord" to denote the negative order), and denote it as nord _N (a).

An integer a may have a negord modulo an integer N or not. As an example, we consider N = 23. It is easily checked that 1, 2, 4, 8, 16, 9, 18, 13, 36 and 12 have no negord, but 17, 11, 22, 21, 19, 15, 7 and 14 have a negord. It is for the purpose of investigating the order that we introduce the concept of the negord.

The relation of the order and negord is stated in the following theorem.

Theorem 3.2.3

Let N be a positive integer. If an integer a, where 1 ≤ a ≤ N − 1 and gcd(a, N) = 1, has a negord modulo N, then

${\text{ord}}_N\left(a\right)=2{\text{nord}}_N\left(a\right)\cdot$

Proof: By definition a ^{nord _N (a)} = −1 (mod N). It follows that a ^{2nord _N (a)} ≡ 1 (mod N). Hence, ord _N (a) divides 2nord _N (a). We now prove that ord _N (a) ≥ 2nord _N (a). If not so, then there are two possibilities: ord _N (a) < nord _N (a) and nord _N (a) < ord _N (a) < 2nord _N (a). It is easily verified that in both cases there must exist an integer l, where 1 ≤ l < nord _N (a), such that a ^l ≡ −1 (mod N). This is contrary to the minimality of the negord of a modulo N. Thus, ord _N (a) must be equal to 2nord _N (a).

A simple property of negord, which is similar to that of order, is the following conclusion.

Theorem 3.2.4

If a ^m ≡ −1 (mod N) for a positive integer m, then nord _N (a)|m and m/nord _N (a) is odd.

Proof: Let m = novd _N (a)h+l, where 0 ≤ l <nord _N (a). We first prove that h must be odd. From a ^m ≡ (a ^{nord _N (a)}) ^h a ^l (mod N) we get a ^l ≡ (−1) ^h+1 (mod N). By the definition of the negord h is odd.

If l ≠ 0, then l ≥ 1. The equation a ^l ≡ 1 (mod N) gives that ord _N (a) < nord _N (a), which is contrary to Theorem 3.2.3. Therefore, l = 0. This completes the proof.

Now we give a characterization of primitive roots in terms of negord. This characterization is useful in searching for primitive roots.

Theorem 3.2.5

Let N be a positive integer > 4 which has primitive roots. Then a is a primitive root modulo N if and only nord _N (a) = ϕ(N)/2.

Proof: If a is a primitive root modulo N, by Proposition 3.2.1 N must be of the form p ^e or 2p ^e , where p is an odd prime. Thus ϕ(N) must be even. Since a ^ϕ(N) ≡ 1 (mod N), we get

$\left(a^{\varphi \left(N\right)/2}+1\right)\left(a^{\varphi \left(N\right)/2}-1\right)\equiv 0\left(\mathrm{mod}N\right)\cdot$

This gives a ^ϕ(N)/2 ≡ −1 (mod N). Thus, the negord of a modulo N exists. Now by Theorem 3.2.3 we have nord _N (a) = ϕ(N)/2. The remaining part then follows from Theorem 3.2.3.

This theorem shows that a necessary condition for a to be a primitive root is a ^ϕ(N)/2 ≡ −1 (mod N). It can be used as a criterion for primitivity. As an example, we take N = 43. Then we have 2^ϕ(N)/2 = 2^{(N − ½)} = 2^{3 × 7} = −1 (mod N). But 2 is not a primitive root of 43. This is because nord₄₃(2) = 7 ≠ 21.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/S0924650904800059

Cellular Automata

Jean-Paul Allouche , ... Gencho Skordev , in Encyclopedia of Physical Science and Technology (Third Edition), 2003

V Cellular Automata as Dynamical Systems

We can also consider cellular automata as dynamical systems. A topological dynamical system (X, f) consists of a compact set X, together with a continuous map f: X  → X. We will restrict our attention to compact metric spaces. In the previous section, we saw that a cellular automaton on Z ⁿ can be considered as a continuous map on the (compact metric) space of configurations.

We shall discuss cellular automata in the context of classical topological dynamics, focusing particularly on the "repetitiveness" properties, such as the existence of periodic points, chain recurrence, nonwandering sets, center of the dynamical system, and so on, as well as the properties of "attracting" or "repelling" invariant sets, which are related to stability properties of the dynamical system.

V.A Periodic Points

Let (X, f) be a dynamical system. A point x ₀  ∈ X is periodic if there exists a positive integer n such that f ⁿ (x ₀)   = x ₀. If this is the case, the orbit of x ₀ under f, that is, the set {f ^k (x ₀); k  ≥   0}, is finite. Its cardinality is called the period of the point x ₀. A point x ₀  ∈ X is ultimately periodic if there exist two integers k  ≥   0 and n  ≥   1 such that f ^n+k (x ₀)   = f ^k (x ₀). Then the orbit of x ₀ is finite. The transient part of the orbit of x ₀ is the set {f ^j(x ₀); 0   ≤ j  ≤ k−1}, where k is the smallest non-negative integer such that for some positive integer n, f ^n+k (x ₀)   = f ^k (x ₀ ). The smallest positive integer n associated with this k is called the period of x ₀.

Periodic points and their generalizations (almost periodic points and recurrent points) for dynamical systems arising from cellular automata were studied by Hedlund and others. Periodic points of cylindrical cellular automata, that is, cellular automata defined on the Cayley graph of the integers modulo m, and relations between spatial and temporal periods were studied by Martin et al. (1984).

V.B Attractors

Intuitively, an attractor of a topological dynamical system (X, f) is a compact invariant set which "attracts" all the points in some neighborhood, in the sense that iterating the map f from any one of these points gives points that converge to the attractor. Such an attractor is Lyapunov stable; that is, every orbit under the map f starting sufficiently close to the attractor remains in a neighborhood of the attractor. These orbits ultimately converge to the attractor. Formally, a set A  ⊂ X is an attractor of the dynamical system (X, f) if there is an open neighborhood U of A such that $\text{f}\left(\bar{\text{U}}\right)\subset$ ⊂ U and

$\text{A}=\underset{\text{n}=0}{\overset{\infty }{\cap }}{\text{f}}^{\text{n}}\left(\text{U}\right),$

where $\bar{\text{U}}$ is the closure of U. The open set,

$\text{B}\left(\text{A}\right):=\underset{\text{n}=0}{\overset{\infty }{\cup }}{\text{f}}^{-\text{n}}\left(\text{U}\right)$

is called the basin of attraction of A.

It follows from the definition that the set A is compact and the basin B(A) is also the set of points x such that all limit points in their orbits belong to A. In other words B(A) does not depend on the choice of the open set U.

Although complete descriptions of all attractors are rare in the theory of dynamical systems, the following result of Hurley (1990) holds for cellular automata.

Theorem.

A cellular automaton on Z ⁿ , considered as a dynamical system, satisfies exactly one of the following conditions:

•

There exists a unique minimal attractor contained in every attractor.

•

There is a unique minimal quasi-attractor (that is, an intersection ${\cap }_{\text{n}=1}^{\infty }{\text{A}}_{\text{n}}$ of a sequence of attractors) contained in every attractor.

•

There exist two disjoint attractors. In this case, the dynamical system associated with the cellular automaton has uncountably many minimal quasi-attractors.

V.C Expansiveness and Permutivity

In the remainder of this section, we shall only consider topological dynamical systems whose topology is induced by a metric or distance. This is always the case for the cellular automata under consideration.

A topological dynamical system (X, f) is expansive at a point x ₀ in X if there exists a positive real constant δ, called the constant of expansiveness at x ₀, with the property that for every point y not equal to x ₀, there exists a non-negative integer k such that the distance between f ^k (y) and f ^k (x ₀) is at least δ. The dynamical system is called expansive if it is expansive at every point x in X. The concept of μ-expansivity for a topological dynamical system (X,f,μ) with a measure μ on X is defined analogously by replacing "for every point y" with "for μ-almost every point y".

For example, the one-dimensional shift on a finite set A defined on the set of two-sided sequences on A by:

${\left({\text{u}}_{\text{n}}\right)}_{\text{n}\in \text{Z}}\mapsto {\left({\text{u}}_{\text{n}+1}\right)}_{\text{n}\in \text{Z}}$

is expansive. Indeed, the following theorem, due to Hedlund, shows that expansive maps are "close" to shifts.

Theorem.

If the topological dynamical system (X, f) is expansive, then it is isomorphic to a subshift; that is, there exists a one-dimensional shift σ and an imbedding ι from X to A ^Z such that the set ι(X) is shift invariant, and σ ∘ ι   =   ι ∘ f.

A cellular automaton is permutive if its local function depends "in an essential way" on the values of the leftmost and the rightmost neighbors. For permutive cellular automata, there is a more precise result due to Gilman (1998).

Theorem.

Any permutive cellular automaton is expansive. Furthermore, the corresponding dynamical system is isomorphic to a one-dimensional, one-sided shift; that is, the dynamical system (A ^N , σ), where A is a finite set, and σ is the map defined on A ^N by:

${\left({\text{u}}_{\text{n}}\right)}_{\text{n}\ge 0}\mapsto {\left({\text{u}}_{\text{n}+1}\right)}_{\text{n}\ge 0}$

When n  ≥   2, n-dimensional cellular automata are never expansive.

V.D Equicontinuity or Lyapunov Stability

A topological dynamical system (X, f) is equicontinuous or Lyapunov stable at the point x ₀ in X if, for every positive real number ε, there exists a neighborhood of x ₀ such that for every y in this neighborhood, all iterations f ⁱ (x ₀) and f ⁱ (y) are ε-close. The dynamical system is called equicontinuous if it is equicontinuous at every x  ∈ X. For a cellular automaton with values in a finite set A, the uniform Bernoulli measure μ on the configuration space is the product measure defined on A by μ({x})   =   1/# A (where # A is the number of elements in A) for each value x in A. The following theorem about equicontinuity in cellular automata is due to Gilman (1988).

Theorem.

Every cellular automaton with values in a finite set A satisfies one of the following conditions (where μ is the uniform Bernoulli measure): Either for every ε   >   0, there exists a compact shift-invariant subset Y _ε of the set of configurations such that μ(Y _ε)   >   1   −   ε and the dynamical system obtained by restricting the cellular automaton to Y _ε is equicontinuous, or the cellular automaton is μ-expansive.

V.E Sensitivity and Transitivity

A topological dynamical system (X, f) is sensitive at a point x ₀ in X if it is not equicontinuous at x ₀. It is sensitive if it is sensitive for all x  ∈ X. If a dynamical system is sensitive, it is, in some sense, "chaotic." Another property associated with a chaotic behavior is (topological) transitivity. A topological dynamical system (X, f) is transitive or topologically mixing if for every pair of non-empty open subsets U and V of X, some iteration f ^k (U) of the set U intersects V. There are several different definitions of a "chaotic" dynamical system. One definition is due to Devaney. A topological dynamical system (X, f) is chaotic if it is transitive and sensitive and if the set of all periodic points is dense in X It can be proved that sensitivity follows from the other two properties. Sensitivity, transitivity, and other properties for cellular automata seen as dynamical systems have been studied.

V.F Cellular Automata as Measurable Dynamical Systems

A measurable dynamical system is a triple (X, μ, f) consisting of a set X with a probability measure μ, and a function f: X  → X which is measure preserving; that is, for all Y  ⊂ X, μ(Y)   =   μ(f ⁻¹(Y)). A measurable dynamical system is ergodic if every subset of X invariant under f has measure 0 or 1. The following is another theorem of Hedlund.

Theorem.

The dynamical system associated with a one-dimensional cellular automaton equipped with the Bernoulli measure is a measurable dynamical system if and only if it is surjective.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B0122274105000910

Inferring the Topology of Gene Regulatory Networks: An Algebraic Approach to Reverse Engineering

Brandilyn Stigler , Elena Dimitrova , in Mathematical Concepts and Methods in Modern Biology, 2013

3.6 Discretization

For reasons explained at the beginning of Section 3.2, we have been assuming that the experimental data we use for reverse engineering have already been discretized into a (small) finite number of states. Typically, however, experimental measurements come to us represented by computer floating point numbers and consequently data discretization is in fact part of the modeling process and can be viewed as a preprocessing step. We will use the definition of discretization presented in [35].

Definition 3.11

A discretization of a real-valued vector $\mathbf{v}=(v_1\text{,}\dots \text{,}{v}_N)$ is an integer-valued vector $\mathbf{d}=(d_1\text{,}\dots \text{,}{d}_N)$ with the following properties:

1.

Each element of $\mathbf{d}$ is in the set $0\text{,}1\text{,}\dots \text{,}D-1$ for some (usually small) positive integer D, called the degree of the discretization.

2.

For all $1\le i\text{,}j\le N$ , we have $d_i\le d_j$ if and only if $v_i\le v_j$ .

Without loss of generality, assume that $\mathbf{v}$ is sorted, i.e., for all $i<j\text{,}{v}_i⩽v_j$ . Spanning discretizations of degree D satisfy the additional property that the smallest element of $\mathbf{d}$ is equal to 0 and that the largest element of $\mathbf{d}$ is equal to $D-1$ .

There is no universal way for data discretization that works for all data sets and all purposes. Sometimes discretization is a straightforward process. For example, if a gene expression time series has a sigmoidal shape, e.g., $(0.1\text{,}1.2\text{,}2\text{,}23.04\text{,}26)$ , it is reasonable to discretize it as $(0\text{,}0\text{,}0\text{,}1\text{,}1)$ . More complicated expression profiles may be easy to discretize too and it is often true that the human eye is the best discretization "tool" whose abilities to discern patterns cannot be reproduced by any software. Large data sets, on the other hand, do require some level of automatization in the discretization process. Regardless of the particular situation, it is good practice to look at the data first and explore for any patterns that may help with the discretization before inputting the data into any discretization algorithm. Afterwards, the way you choose to discretize your data, which includes selecting the number of discrete states, should depend on the type and amount of data and the specific reason for discretization. Below we present several possible approaches which by no means comprise a complete list.

Binary discretizations are the simplest way of discretizing data, used, for instance, for the construction of Boolean network models for gene regulatory networks [36,37]. The expression data are discretized into only two qualitative states as either present or absent. An obvious drawback of binary discretization is that labeling real-valued data according to a present/absent scheme may cause the loss of large amounts of information.

Interval discretizations divide the interval $[v_1\text{,}{v}_N]$ into k equally sized bins, where k is user-defined. Another simple method is quantile discretization which places $N/k$ (possibly duplicated) values in each bin [38]. Any method based on those two approaches would suffer from problems that make it inappropriate for some data sets. Interval discretizations are very sensitive to outliers and may produce a strongly skewed range [39]. In addition, some discretization levels may not be represented at all which may cause difficulties with their interpretation as part of the state space of a discrete model.

On the other hand, quantile discretizations depend only on the ordering of the observed values of $\mathbf{v}$ and not on the relative spacing values. Since distance between the data points is often the only information that comes with short time series, losing it is very undesirable. A shortcoming, common for both interval and quantile, as well as for most other discretization methods, is that they require the number of discrete states, k, to be user-provided.

A number of entropy-based discretization methods deserve attention. An example of those is Hartemink's Information-Preserving Discretization (IPD) [35]. It relies on minimizing the loss of pairwise mutual information between each two real-valued vectors (variables). The mutual information between two random variables X and Y with joint distribution $p(X\text{,}Y)$ and marginal distributions $p(x)$ and $p(y)$ is defined as

$I(X\text{;}Y)={\displaystyle \sum _x}{\displaystyle \sum _y}p(x\text{,}y)\mathit{log}\frac{p(x\text{,}y)}{p(x)p(y)}\text{.}$

Note that if X and Y are independent, by definition of independence $p(x\text{,}y)=p(x)p(y)$ , so $I(X\text{;}Y)=0$ . Unfortunately, when modeling regulatory networks and having as variables, for instance, mRNA, protein, and metabolite concentrations, the joint distribution function is rarely known and it is often hard to determine whether two variables are independent.

Another family of discretization techniques is based on clustering [40]. One of the most often used clustering algorithms is the k-means [41]. It is a non-hierarchical clustering procedure whose goal is to minimize dissimilarity in the elements within each cluster while maximizing this value between elements in different clusters. Many applications of the k-means clustering such as the MultiExperiment Viewer [42] start by taking a random partition of the elements into k clusters and computing their centroids. As a consequence, a different clustering may be obtained every time the algorithm is run. Another inconvenience is that the number k of clusters to be formed has to be specified in advance. Although there are methods for choosing "the best k" such as the one described in [43], they rely on some knowledge of the data properties that may not be available.

Another method is single-link clustering (SLC) with the Euclidean distance function. SLC is a divisive (top-down) hierarchical clustering that defines the distance between two clusters as the minimal distance of any two objects belonging to different clusters [40]. In the context of discretization, these objects will be the real-valued entries of the vector to be discretized, and the distance function that measures the distance between two vector entries v and w will be the one-dimensional Euclidean distance $|v-w|$ . Top-down clustering algorithms start from the entire data set and iteratively split it until either the degree of similarity reaches a certain threshold or every group consists of one object only. For the purpose of data analysis, it is impractical to let the clustering algorithm produce clusters containing only one real value. The iteration at which the algorithm is terminated is crucial since it determines the degree of the discretization. SLC with the Euclidean distance function has one major advantage: very little starting information is needed (only distances between points). In addition, being a hierarchical clustering procedure it lends itself to adjustment in case that clusters need to be split or merged. It may result, however, in a discretization where most of the points are clustered into a single partition if they happen to be relatively close to one another. Another problem with SLC is that its direct implementation takes D, the desired number of discrete states, as an input. However, we would like to choose D as small as possible, without losing information about the system dynamics and the correlation between the variables, so that an essentially arbitrary choice is unsatisfactory.

In [44], a hybrid method for discretization of short time series of experimental data into a finite number of states was introduced. It is a modification of the SLC algorithm: it begins by discretizing a vector in the same way as SLC does but instead of providing D as part of the input, the algorithm contains termination criteria which determine the appropriate value of D. After that each discrete state is checked for information content and if it is determined that this content can be considerably increased by further discretization, then the state is separated into two states in a way that may not be consistent with SLC.

If more than one vector is to be discretized, the algorithm discretizes each vector independently. (For details on multiple vector discretization, see [44]). If the vector contains m distinct entries, a complete weighted graph on m vertices is constructed, where a vertex represents an entry and an edge weight is the Euclidean distance between its endpoints. The discretization process starts by deleting the edge(s) of highest weight until the graph gets disconnected. If there is more than one edge labeled with the current highest weight, then all of the edges with this weight are deleted. The order in which the edges are removed leads to components, in which the distance between any two vertices is smaller than the distance between any two components, a requirement of SLC. We define the distance between two components G and H to be $\mathrm{dist}(G\text{,}H)=\min \{|g-h||g\in G\text{,}h\in H\}$ .The output of the algorithm is a discretization of the vector, in which each cluster corresponds to a discrete state and the vector entries that belong to one component are discretized into the same state.

Example 3.12

Suppose that vector $\mathbf{v}=(1\text{,}2\text{,}7\text{,}9\text{,}10\text{,}11)$ is to be discretized. The diagram obtained by the SLC algorithm is given in Figure 3.3. The complete weighted graph in Figure 3.4 corresponds to iteration 0 of the diagram.

Figure 3.3. Diagram representing the SLC algorithm applied to the data of Example 3.12. The column on the right gives the corresponding Shannon's entropy increasing at each consecutive level.

Figure 3.4. The complete weighted graph constructed from vector entries 1, 2, 7, 9, 10, 11. Only the edge weights of the outer edges are given.

Having disconnected the graph, the next task is to determine if the obtained degree of discretization is sufficient; if not, the components need to be further disconnected in a similar manner to obtain a finer discretization. A component is further disconnected if, and only if, both (1) and (2) below hold:

1.

The minimum vertex degree of the component is less than the number of its vertices minus 1. The contrary implies that the component is a complete graph by itself, i.e., the distance between its minimum and maximum vertices is smaller than the distance between the component and any other component.

2.

One of the following three conditions is satisfied ("disconnect further" criteria):

a.

The average edge weight of the component is greater than half the average edge weight of the complete graph.

b.

The distance between its smallest and largest vertices is greater than or equal to half this distance in the complete graph. For the complete graph, the distance is the graph's highest weight.

c.

Finally, if the above two conditions fail, a third one is applied: disconnect the component if it leads to a substantial increase in the information content carried by the discretized vector.

The result of applying only the first two criteria is analogous to SLC clustering with the important property that the algorithm chooses the appropriate level to terminate. Applying the third condition, the information measure criterion may, however, result in a clustering which is inconsistent with any iteration of the SLC.

Exercise 3.18

Consider the following vector ${\mathbf{v}}_{\mathbf{1}}=(1.3\text{,}2.1\text{,}7.2\text{,}9.05\text{,}10.5\text{,}11.00)$ . Plot the vector entries on the real number line and propose an appropriate discretization based on your intuition. How did you decide on the number of discrete states? Would your decision change if the entry 4.6 is added?   □

Exercise 3.19

Discretize vector ${\mathbf{v}}_{\mathbf{1}}$ from Problem 3.18 using the specified method.

1.

Interval.

2.

Quantile.

3.

The hybrid method presented in this section.

  □

Exercise 3.20

If you know that the experimental data is very noisy, would you be willing to use a smaller or a larger number of discrete states?   □

Exercise 3.21

Suppose a second vector, ${\mathbf{v}}_{\mathbf{2}}=(0.8\text{,}1.8\text{,}3.1\text{,}8.0\text{,}9.5\text{,}10.7)$ , is to be discretized and it is known that ${\mathbf{v}}_{\mathbf{1}}$ and ${\mathbf{v}}_{\mathbf{2}}$ are strongly correlated (assume Spearman rank correlation). How would you discretize ${\mathbf{v}}_{\mathbf{2}}$ based on your discretization of ${\mathbf{v}}_{\mathbf{1}}$ ?   □

Project 3.7

Use the principle of relationship discretization that is behind Hartemink's information-preserving discretization method to discretize ${\mathbf{v}}_{\mathbf{1}}$ and ${\mathbf{v}}_{\mathbf{2}}$ .   □

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B978012415780400003X

Quantum Algorithms and Methods

Ivan B. Djordjevic , in Quantum Information Processing, Quantum Computing, and Quantum Error Correction (Second Edition), 2021

5.12 Problems

1.

By using mathematical induction, prove that the following circuit can be used to implement the Deutsch–Jozsa algorithm, that is, to verify whether the mapping {0,1} ⁿ → {0,1} is constant or balanced.

2.

By using mathematical induction, prove that the following circuit can be used to calculate the FT for arbitrary n:

3.

Assume that a unitary operator U has an eigneket |u〉 with eigenvalue exp(j2πφ _u ). The goal of phase estimation is to estimate the phase φ _u . Describe how the quantum FT can be used for phase estimation.

4.

This problem is related to the shift-invariance property of quantum FT. Let G be a group and H be a subgroup of G. If a function f on G is constant on cosets of H, then the FT of f is invariant over cosets of H. Prove the claim.

5.

The quantum circuit to perform the Grover search for n  =   3 was shown in Fig. 5.11. Provide a quantum circuit that can be used to perform the Grover search for arbitrary n. Explain the operation principle and prove that this circuit can indeed be used for any n.

6.

Provide a quantum circuit to implement Shor's factorization algorithm for n  =   15. Describe the operation principle of this circuit.

7.

This problem is devoted to quantum discrete logarithms. Let us consider the following function: $f\left(x_1,x_2\right)=a^{b{x}_1+x_2}\mathrm{mod}N,$ where all variables are integers. Let r be the smallest positive integer for which a ^r mod N  =   1; this integer can be determined by using the order-finding algorithm. Clearly, this function is periodic as f(x ₁ + i,x ₂ − ib)   = f(x ₁,x ₂), where i is an integer. The discrete logarithm problem can be formulated as follows: given a and c  = a ^b , determine b. This problem is important in cracking the RSA encryption protocol as discussed in Section 5.5. Your task is to provide a quantum algorithm that can solve this problem by using one query of a quantum block U that performs the following unitary mapping: U|x ₁〉|x ₂〉|y〉 → |x ₁〉|x ₂〉|y ⊕ f(x ₁,x ₂)〉.

8.

In Problem 6 you were asked to provide a quantum circuit to implement Shor's factorization algorithm for n  =   15. By using Simon's algorithm, describe how to perform the same task. Provide the corresponding quantum circuit. Analyze the complexity of both algorithms.

9.

Suppose that the list of numbers x ₁,…,x _n is stored in quantum memory. How many memory accesses are needed to determine the smallest number in the list with a success probability of ≥1/2?

10.

Provide the quantum circuit to perform the following mapping:

$|m〉\to \frac{1}{\sqrt{p}}\sum _{n=0}^{p-1}{e}^{j2\pi mn/p}|n〉,$

where p is a prime.

11.

Design a quantum circuit to perform the following mapping: |x〉→ |x  + c mod 2 ⁿ 〉, where x ∈ [0,2 ^n–1] and c is the constant, by using quantum FT.

12.

The following circuit can be used to perform addition:

Describe the operation principle, and provide the result of addition. Can you generalize this addition problem?

13.

The following problem is related to Kitaev's algorithm, which represents an alternative way to estimate the phase. Let us observe the following quantum circuit:

where |u〉 is an eigneket of U with eigenvalue exp(j2πφ _u ). Show that the result of the measurement 0 appears with a probability of p  =   cos²(πφ). Since the eigenket is insensitive to measurement the operator U can be replaced with U ^m , where m is an arbitrary positive integer. Show that by repeating this circuit appropriately we can obtain the arbitrary precision of p and consequently estimate the phase φ with desired precision. Compare the complexity of Kitaev's algorithm with respect to that from Problem 3.

14.

The state ket after application of Hadamard gates of the following circuit:

can be written in the following form:

$|\psi 〉=\frac{1}{N^{1/2}}\sum _x{a}_x^{\left(0\right)}|x〉,a_x^{\left(0\right)}=1.$

The application of operator GO on |ψ〉 leads to the following ket:

$|\psi 〉=\frac{1}{N^{1/2}}\sum _x{a}_x^{\left(1\right)}|x〉.$

Establish the connection between $a_x^{\left(1\right)}$ and $a_x^{\left(0\right)}.$

15.

This problem is related to quantum simulation. When the Hamiltonian H that can be represented as the sum of polynomial many terms H _m , namely H  =   ∑ _m H _m , each of which can be efficiently implemented, we can efficiently simulate the evolution operator $\exp \left(-\frac{j}{\hslash }Ht\right)$ and approximate the evolution of state $|\psi \left(t\right)〉=\exp \left(-\frac{j}{\hslash }Ht\right)|\psi \left(0\right)〉.$ . If for all m,n [H _m ,H _n ]   =   0, then we can write $\exp \left(-\frac{j}{\hslash }Ht\right)=\prod _k{e}^{-\frac{j}{\hslash }{H}_{k}t}.$ However, if [H _m ,H _n ] ≠ 0, then the previous equation is not valid. The following formula, known as the Trotter formula, can be used for approximations leading to quantum simulation algorithms: $\underset{n\to \infty }{\lim }\left(e^{j{U}_{1}t/n}{e}^{j{U}_{2}t/n}\right)=e^{j\left(U_1+U_2\right)t},$ where U ₁ and U ₂ are Hermitian operators. Prove the Trotter formula. Prove also the following useful approximations:

$e^{j\left(U_1+U_2\right)\Delta t}=e^{j{U}_1\Delta t}{e}^{j{U}_2\Delta t}+O\left(\Delta t^2\right),e^{j\left(U_1+U_2\right)\Delta t}=e^{j{U}_1\Delta t/2}{e}^{j{U}_2\Delta t}{e}^{j{U}_1\Delta t/2}+O\left(\Delta t^3\right).$ Finally, the following approximation, known as the Baker–Campbell–Hausdorf formula, is also useful in quantum simulation: $e^{\left(U_1+U_2\right)\Delta t}=e^{U_1\Delta t}{e}^{U_2\Delta t}{e}^{-[U_1,U_2]\Delta t^2/2}+O\left(\Delta t^3\right).$ Prove it. Consider now a single particle living in 1D potential V(x), governed by Hamiltonian: H  = p ²/(2m) + V(x). Perform the computation |ψ(t)〉   = exp(−jHt/ℏ)|ψ(0)〉 by using the foregoing approximations.

16.

Construct the quantum circuit to simulate the Hamiltonian H  = Z ₁ Z ₂ … Z _n , performing the unitary transform |ψ(t)〉   = exp(−jHt/ℏ)|ψ(0)〉for arbitrary Δt.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B978012821982900006X

Fuzzy Measures of Molecular Shape and Size

PAUL G. MEZEY , in Fuzzy Logic in Chemistry, 1997

XIV FUZZY SET GENERALIZATIONS OF ZPA FOLDING-UNFOLDING CONTINUOUS SYMMETRY MEASURES BASED ON THE FUZZY FSNDSM METRIC AND FUZZY HAUSDORFF-TYPE METRICS

The fuzzy average F _fav of a family of crisp or fuzzy sets F ₁, F ₂,…,F _m has a much simpler construction ²⁹ than the average of crisp sets used in Section XIII and that also simplifies the extension of ZPA-type folding-unfolding continuous symmetry measures to both crisp continua and fuzzy sets, using dissimilarity metrics designed for fuzzy sets and used as the actual measures of symmetry deficiency. Here we shall follow the technique ²⁹ based on the fuzzy membership function μ _{F fav} (x) of the fuzzy average F _fav, as defined earlier by Eq. (199).

Consider a crisp or fuzzy subset A of the Euclidean space X, a (possibly approximate) symmetry element R, and the associated symmetry operator R. A fixed point of R is chosen as a reference point c ∈ X, and a local Cartesian coordinate system of origin c is specified, with coordinate axes oriented according to the usual conventions with respect to the symmetry operator R, as described for crisp sets in Section XIII.

Choose m as the smallest positive integer that satisfies the condition R ^m = E of Eq. (171) and take the powers R ⁰= E, R, R ²,…,R ^{m − 1} of the symmetry operator R. Following the technique described in Section XIII, partition the Euclidean space X into m segments X ₀, X ₁,…,X _{m − 1}, where the union of these segments generates the space X,

(236) $X={{\displaystyle \underset{{}_{j=0,m-1}}{\cup }}}^{\text{}}{X}_i$

and where segments of subsequent indices are related to one another by the symmetry operation

(237) $\text{R}{X}_j=X_{(j+1)modm}$

The interpretation of these segments and the notation P for the convention used for the positioning of R with respect to set A and for the partitioning X ₀, X ₁,…, X _{m − 1} of the space X are the same as those used for crisp sets, described in Section XIII.

The segment A _j of the crisp or fuzzy set A is defined as

(238) $A_j=A\cap X_j$

and the "folded" version of the jth segment A _j of the crisp or fuzzy set A, according to the (m − j)th power R ^{m − j} of the (possibly only approximate) symmetry operator R is denoted by

(239) $B_j={\text{R}}^{m-j}{A}_j$

For the family S _A of segments A ₀, A _l, A ₂,…,A _{m − 1}, the corresponding folded sets A ₀, R ^{m − 1} A ₁, R ^{m − 2} A ₂,…,R ^{m − j} A _j,…,R A _{m − 1} are obtained, that is, the family S _B of sets B ₀, B ₁, B ₂,…,B _{m − 1} is generated.

The fuzzy folded set A _ffold is the fuzzy average S _Bfav of these B _j sets, defined by the fuzzy membership function μ _{S Bfav}(x) as follows:

(240) ${\mu }_{A_{ft\circ 1d}}(x)={\mu }_{{\text{S}}_{B\downarrow 4V}}(x)=\left[{{\displaystyle \sum _{k=0,m-1}}}^{\text{}}{\mu }_{B_k}(x)\right]/m$

The "unfolding" of the fuzzy folded set A _ffold is obtained using the appropriate inverse powers of symmetry operator R generating the following sets: A _ffold,R ^{1 − m} A _ffold,R ^{2 − m} A _ffold,…,R ^{j − m} A _ffold,…,R ⁻¹ A _ffold. The fuzzy union of all these sets is the folded-unfolded fuzzy set A_{ff, uf, R, P} of crisp or fuzzy set A, generated according to symmetry element R and the actual partitioning P:

(241) $A_{ff.\text{uf},\text{R},P}=\underset{j=0,m-1}{{{\displaystyle \cup }}^{\text{}}}{\text{R}}^{-j}{A}_{f\text{fold}}.$

The folded-unfolded set A _{ff, uf, R, F} of crisp or fuzzy set A is a fuzzy R set, by construction.

Fuzzy dissimilarity measures, such as the fuzzy FSNDSM metric fs(A, B), and any one of the fuzzy Hausdorff-type dissimilarity metrics, for example, f(A, B), can be applied to the pair of set A and the folded-unfolded set A _{ff, uf, R, P} . These fuzzy dissimilarity measures generate fuzzy symmetry deficiency measures analogous to the ZPA continuous symmetry measure of discrete point sets.

If the FSNDSM metric fs(A, B) is selected, then the corresponding symmetry deficiency measure is defined as d _fs(A, A _{ff, uf, R, P} ). The measure d _fs(A, A _{ff, uf, R, P} ) describes the fuzzy FSNDSM "shape distance" between the crisp or fuzzy set A and the fully R-symmetric, fuzzy, folded-unfolded set A _{ff, uf, R, P} of the original set A. By analogy with the case of crisp sets discussed in Section XIII, the d _fs(A, A _{ff, uf, R, P} ) symmetry deficiency measure is P-dependent, that is, it depends on the positioning P of R with respect to A and on the choice of the corresponding partitioning of the underlying Euclidean space X and that of the original crisp or fuzzy set A.

By taking the infimum for all the allowed choices of P, a symmetry deficiency measure of crisp or fuzzy set A is obtained that is independent of positioning and partitioning. The corresponding d _fs(A, A _{ff, uf, R} ) measure is defined as the infimum of d _fs(A, A _{ff, uf, R P} ) generated over all the allowed positionings and partitionings:

(242) $d_{\mathrm{fs}}(A,A_{ff},uf.\text{R})={\inf }_P\left\{d_{f\text{S}}(A{A}_{ff,uf,\text{R},P})\right\}$

Using any one of the versions of the fuzzy Hausdorff-type metrics for the dissimilarity of sets A and A _{ff, uf, R, P} , for example, the "commitment weighted" fuzzy Hausdorff-type dissimilarity metric f(A, B), one obtains another generalization of the ZPA continuous symmetry measure of discrete point sets to crisp or fuzzy sets. The corresponding symmetry deficiency measure f(A, A _{ff, uf, R, P} ) provides a measure for the symmetry aspect R for crisp or fuzzy set A, with reference to the given positioning P of R with respect to A and to the choice of the associated partitioning of A.

For a symmetry deficiency measure of set A, independent of positioning and partitioning, the infimum of f(A, A _{ff, uf, R, P} ) can be taken over all the allowed positionings and partitionings P. This measure, f(A, A _{ff, uf, R} ), is defined as

(243) $f(A,A_{ff.uf,\text{R}})={\inf }_P\{f(A,A_{ff,uf,\text{R},P})\}$

Following the principles of the ZPA approach, these symmetry deficiency measures are generalizations of the folding-unfolding approach, equally applicable to crisp continuum sets and fuzzy sets, for example, to entire electron density distributions of molecules and various molecular fragments representing fuzzy functional groups.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B978012598910750007X

Higher Order Equations

Martha L. Abell , James P. Braselton , in Introductory Differential Equations (Fourth Edition), 2014

Undetermined Coefficients

In the special case that the corresponding homogeneous equation has constant coefficients and the forcing function is a linear combination of functions of the form

(4.23) $\begin{array}{l}1,t,,t^2,\dots ,\\ e^{\alpha t},t{e}^{\alpha t},t^2{e}^{\alpha t},\dots ,\\ cos\beta t,sin\beta t,tcos\beta t,tsin\beta t,& \\ t^{2}cos\beta t,t^{2}sin\beta t,\dots \\ \text{or}\\ e^{\alpha t}cos\beta t,e^{\alpha t}sin\beta t,t{e}^{\alpha t}cos\beta t,t{e}^{\alpha t}sin\beta t,\\ t^2{e}^{\alpha t}cos\beta t,t^2{e}^{\alpha t}sin\beta t,\dots ,\end{array}$

then the method of undetermined coefficients can be used to determine the form of a particular solution of the nonhomogeneous equation in the same way as that discussed in Section 4.2.

Example 4.6.2

Solve y ⁽⁵⁾ + 4y‴ = 48t − 6 − 10e^−t .

Solution

The corresponding homogeneous equation is y ⁽⁵⁾ + 4y‴ = 0, which has characteristic equation r ⁵ + 4r ³ = r ³(r ² + 4) = 0 so r _1,2,3 = 0 has multiplicity three and r _4,5 = ±2i each have multiplicity one. Thus, a fundamental set for the corresponding homogeneous equation is $S=\left\{1,t,t^2,cos2t,sin2t\right\}$ and a general solution of the corresponding homogeneous equation is $y_h=c_1+c_{2}t+c_3{t}^2+c_{4}cos2t+c_{5}sin2t$ .

For the forcing function, f(t) = 48t − 6 − 10e^−t we have two associated sets:

$F_1=\left\{e^{-t}\right\}\text{and}{F}_2=\left\{t,1\right\},$

corresponding to the terms − 10e^−t and 48t − 6, respectively, in the forcing function. Note that no element of F ₁ is a solution of the corresponding homogeneous equation. On the other hand, functions in F ₂ are solutions to the corresponding homogeneous equation. So, following the outline in Section 4.2, we multiply F ₂ by t ⁿ where n is the smallest positive integer so that no function in t ⁿ F ₂ is a solution of the corresponding homogeneous equation. In this case, we multiply F ₂ by t ³ to obtain $t^3{F}_2=\left\{t^4,t^3\right\}$ .

Thus, we assume that a particular solution to the nonhomogeneous equation has the form y _p = At ⁴ + Bt ³ + Ce^−t . Differentiating we have,

$\begin{array}{l}{y}_p^{\prime }=4A{t}^3+3B{t}^2-C{e}^{-t},\\ y_p^{″}=12A{t}^2+6Bt+C{e}^{-t},\\ y_p^{‴}=24A+C{e}^{-t}\text{and}{y}_p^{(4)}=-C{e}^{-t}.\end{array}$

Substituting into the nonhomogeneous equation, simplifying the result, and equating coefficients gives us

$24B+96At-5C{e}^{-t}=48t-6-10e^{-t},$

so 24B = −6, 96A = 48, and − 5C = −10. Thus, A = 1/2, B = −1/4, and C = 2 so a particular solution of the nonhomogeneous equation is $y_p=\frac{1}{2}{t}^4-\frac{1}{4}{t}^3+2e^{-t}$ .

A general solution of the nonhomogeneous equation is then given by

$\begin{array}{l}y=y_h+y_p=c_1+c_{2}t+c_3{t}^2+c_{4}cos2t\\ +c_{5}sin2t+\frac{1}{2}{t}^4-\frac{1}{4}{t}^3+2e^{-t}.\end{array}$

What is the form of a particular solution of $y^{(5)}+4y^{‴}=tcos2t$ ?

To solve an IVP, first determine a general solution and then use the initial conditions to solve for the unknown constants in the general solution.

Example 4.6.3

Solve the IVP

$4y^{‴}+4y^{″}+65y^{\prime }=e^{-t∕3}\left(-\frac{286}{3}cos2t+\frac{577}{27}sin2t\right),$

y(0) = 4/3, y′(0) = −5/2, y″(0) = −173/12.

Solution

The corresponding homogeneous equation is 4y‴ + 4y″ + 65y′ = 0 with characteristic equation 4r ³ + 4r ² + 65r = r(4r ² + 4r + 65) = 0 so r ₁ = 0 and using the quadratic formula to solve 4r ² + 4r + 65 = 0 gives us $r_{2,3}=-\frac{1}{2}\pm 4i$ . Thus, a fundamental set of solutions for the corresponding homogeneous equation is $S=\{1,e^{-t∕2}cos4t,e^{-t∕2}sin4t\}$ and a general solution of the corresponding homogeneous equation is $y_h=c_1+e^{-t∕2}(c_{2}cos4t+c_{3}sin4t)$ .

The associated set of functions for the forcing function

$g(t)=e^{-t∕3}\left(-\frac{286}{3}cos2t+\frac{577}{27}sin2t\right)$

is $F=\left\{e^{-t∕3}cos2t,e^{-t∕3}sin2t\right\}$ . No function in F is a solution of the corresponding homogeneous equation so we assume that a particular solution of the nonhomogeneous equation has the form $y_p=A{e}^{-t∕3}cos2t+B{e}^{-t∕3}sin2t$ , where a and b are constants to be determined. Differentiating y _p three times gives us

$\begin{array}{l}{y}_p^{\prime }=\left(-\frac{1}{3}A+2B\right)e^{-t∕3}cos2t\\ +\left(2A-\frac{1}{3}B\right)e^{-t∕3}sin2t,\\ y_p^{″}=\left(-\frac{35}{9}A-\frac{4}{3}B\right)e^{-t∕3}cos2t\\ +\left(\frac{4}{3}A-\frac{35}{9}\right)e^{-t∕3}sin2t,\\ \text{and}\\ y_p^{‴}=\left(\frac{107}{27}A-\frac{22}{3}B\right)e^{-t∕3}cos2t\\ +\left(\frac{22}{3}A+\frac{107}{27}B\right)e^{-t∕3}sin2t.\end{array}$

Substituting y _p and its derivatives into the nonhomogeneous equation and simplifying the result gives us

When algebra becomes unusually cumbersome, we usually use a computer algebra system to assist in checking our calculations.

$\begin{array}{l}4y_p^{‴}+4y_p^{″}+65y_p^{\prime }=\left(-\frac{577}{27}A+\frac{286}{3}B\right)e^{-t∕3}cos2t\\ +\left(-\frac{286}{3}A-\frac{577}{27}B\right)e^{-t∕3}sin2t\\ =e^{-t∕3}\left(-\frac{286}{3}cos2t+\frac{577}{27}sin2t\right).\end{array}$

Equating coefficients gives us the system

$\begin{array}{l}-\frac{577}{27}A+\frac{286}{3}B=-\frac{286}{3}\\ -\frac{286}{3}A-\frac{577}{27}B=\frac{577}{27},\end{array}$

which has solution A = 0 and B = −1. Thus, $y_p=-e^{-t∕3}sin2t$ and a general solution of the nonhomogeneous equation is $y=y_h+y_p=c_1+e^{-t∕2}(c_{2}cos4t+c_{3}sin4t-e^{-t∕3}sin2t$ (see Figure 4.11(a)).

Figure 4.11. (a) Various solutions of the nonhomogeneous equation. (b) The solution of the nonhomogeneous equation that satisfies the initial conditions y(0) = 4/3, y ^′ (0) = −5/2, and y ^″(0) = −173/12.

To solve the IVP, we first differentiate Y twice resulting in

$\begin{array}{l}{y}^{\prime }=\left(-\frac{1}{2}{c}_2+4c_3\right)e^{-t∕2}cos4t\\ +\left(4c_2-\frac{1}{2}{c}_3\right)e^{-t∕2}sin4t-2e^{-t∕3}cos2t\\ +\frac{1}{3}{e}^{-t∕3}sin2t\\ \text{and}\\ y^{″}=\left(-\frac{63}{4}{c}_2+4c_3\right)e^{-t∕2}cos4t\\ +\left(4c_2-\frac{63}{4}{c}_3\right)e^{-t∕2}sin4t+\frac{4}{3}{e}^{-t∕3}cos2t\\ +\frac{35}{9}{e}^{-t∕3}sin2t.\end{array}$

Evaluating at t = 0 gives us the system of equations

$\begin{array}{l}y(0)=c_1+c_2=\frac{4}{3}\\ y^{\prime }(0)=-2-\frac{1}{2}{c}_2+4c_3=-\frac{5}{2}\\ y^{″}(0)=\frac{22}{3}+\frac{191}{8}{c}_2-61c_3=-\frac{173}{12},\end{array}$

which has solution c ₁ = 1/3, c ₂ = 1, and c ₃ = 0 so the solution to the IVP is $y=\frac{1}{3}+e^{-t∕2}cos4t-e^{-t∕3}sin2t$ (see Figure 4.11(b)).

What is the form of a particular solution of 4y‴ + 4y″ + 65y′ = t² + te^-t/3 cos2t?

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124172197000041

Find the Approximate Value of the Smallest Possitive Solution

Source: https://www.sciencedirect.com/topics/mathematics/smallest-positive-integer

Share :