Celem tego artykułu jest prezentacja metod rozwiązywania równań wielomianowych postaci f(X) = A, gdzie X jest niewiadomą macierzą, A macierzą kwadratową stopnia 2, a f(x) wielomianem o współczynnikach zespolonych.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We consider the problem of obtaining parameterized lower bounds for the size of arithmetic circuits computing polynomials with the degree of the polynomial as the parameter. We consider the following special classes of multilinear algebraic branching programs: 1) Read Once Oblivious Branching Programs (ROABPs), 2) Strict interval branching programs, 3) Sum of read once formulas with restricted ordering. We obtain parameterized lower bounds (i.e., nΩ(t(k)) lower bound for some function t of k ) on the size of the above models computing a multilinear polynomial that can be computed by a depth four circuit of size g (k)n0(1) for some computable function g. Further, we obtain a parameterized separation between ROABPs and read-2 ABPs. This is obtained by constructing a degree k polynomial that can be computed by a read-2 ABP of small size such that the rank of the partial derivative matrix under any partition of the variables is large.
Podczas każdego kursu matematyki na pierwszym roku studiów technicznych studenci wielokrotnie spotykaj¡ się z równaniami i nierównościami wymiernymi, których rozwiązanie jest jednym z etapów analizy różnych problemów. Nierówności wymierne są omawiane w szkole średniej tylko na matematyce na poziomie rozszerzonym, jest zatem spora grupa studentów, którzy nie nabyli umiejętności ich rozwiązywania. Mamy nadzieję, że niniejszy artykuł nie tylko pomoże studentom w uzupełnieniu wiedzy, ale przyda się również do powtórki lub podczas przygotowania do matury z matematyki na poziomie rozszerzonym. Artykuł przedstawia algorytmiczne podejście do rozwiązywania tego typu nierówności. W dwóch metodach zaprezentowano krok po kroku, co należy zrobić, aby znaleźć wszystkie liczby rzeczywiste spełniające rozwiązywaną nierówność wymierną. Kolejne kroki wyróżnione zostały pogrubioną czcionką (bold) w celu łatwiejszego zapamiętania jak należy postępować. Jednak warto, aby Czytelnik nie ograniczył się tylko do zapamiętania „jak”, lecz wnikliwie zapoznał się z dalszą częścią opisu tłumaczącą, dlaczego i po co wykonywane są kolejne przekształcenia. Zrozumienie metody (a nie tylko jej zapamiętanie) umożliwi czytelnikom modyfikację prezentowanych algorytmów lub całkowitą zmianę postępowania, tak aby podobne zadanie rozwiązać sprytniej i szybciej. Pozwoli to odejść od algorytmicznego sposobu myślenia i wzbogacić warsztat matematyczny.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Integrating an arbitrary polynomial function f of degree D over a general simplex in dimension n is well-known in the state of the art to be NP-hard when D and n are allowed to vary, but it is time-polynomial when D or n are fixed. This paper presents an efficient algorithm to compute the exact value of this integral. The proposed algorithm has a time-polynomial complexity when D or n are fixed, and it requires a reasonable time when the values of D and n are less than 10 using widely available standard calculators such as desktops.
We prove that the holomorphic differential equation ϕ’’(ϕ+c) = γ(ϕ’)² (ϕ:C→C be a holomorphic function and (γ, c) ϵ C²) plays a classical role on many problems of real and complex convexity. The condition exactly γ ϵ [wzór] (independently of the constant c) is of great importance in this paper. On the other hand, let n ≥ 1, (A₁, A₂) ϵ C² and g₁, g₂ : Cᵑ → C be two analytic functions. Put u(z, w) = │A ₁w - g₁(z) │² + │A₂w - g₂(z) │²v(z,w) = │A₁w - g₁(z) │² + │ A₂w - g₂(z) │², for (z,w) ϵ Cᵑ x C. We prove that u is strictly plurisubharmonic and convex on Cᵑ x C if and only if n = 1, (A₁, A₂) ϵ C² \{0} and the functions g₁ and g₂ have a classical representation form described in the present paper. Now v is convex and strictly psh on Cᵑ x C if and only if (A₁, A₂) ϵ C² \{0}, n ϵ {1,2} and and g₁, g₂ have several representations investigated in this paper.
6
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this work we study a rational extension SROEL(⊓, x)R T of the low complexity description logic SROEL(⊓, x), which underlies the OWL EL ontology language. The extension involves a typicality operator T, whose semantics is based on Lehmann and Magidor’s ranked models and allows for the definition of defeasible inclusions. We consider both rational entailment and minimal entailment. We show that deciding instance checking under minimal entailment is in general ∏2P -hard, while, under rational entailment, instance checking can be computed in polynomial time. We develop a Datalog calculus for instance checking under rational entailment and exploit it, with stratified negation, for computing the rational closure of simple KBs in polynomial time.
7
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We provide the first algorithm with a polynomial time complexity, O((m + n)2n2), for computing the largest bisimulation-based auto-comparison of a labeled graph in the setting with counting successors, where m is the number of edges and n is the number of vertices. This setting is like the case with graded modalities in modal logics and qualified number restrictions in description logics. Furthermore, by using the idea of Henzinger et al. for computing simulations, we give an efficient algorithm, with complexity O((m + n)n), for computing the largest bisimulation-based auto-comparison and the directed similarity relation of a labeled graph in the setting without counting successors. We also adapt our former algorithm for computing the simulation pre-order of a labeled graph in the setting with counting successors.
The aim of this study was to investigate the curve fitting and model selection problem of the torque–velocity relationship of elbow flexors and extensors in untrained females. The second goal was to determine the optimal models in different function classes and the best, among the optimal ones. Lastly, test the best models to predict the torque were tested. Methods: Using the polynomials (second – fourth degree) and Boltzmann sigmoid functions, and a different presentation of data points (averages, a point cloud, etc.), we determined the optimal models by both error criteria: minimum residual sum of squares and minimum of the maximal absolute residue. To assess the best models, we applied Akaike and Bayesian information criteria, Hausdorff distance and the minimum of the smallest maximal absolute residue and the predictive torque–velocity relationships of the best models with torque values, calculated beyond the experimental velocity interval. Results: The application of different error and model selection criteria showed that the best models in the majority of cases were polynomials of fourth degree, with some exceptions from second and third degree. The criteria values for the optimal Boltzmann sigmoids were very close to those of the best polynomial models. However, the predicted torque–velocity relationships had physiological behavior only in Boltzmann’s sigmoid functions, and their parameters had a clear interpretation. Conclusion: The results obtained suggest that the Boltzmann sigmoid functions are suitable for modeling and predicting of the torque–velocity relationship of elbow flexors and extensors in untrained females, as compared to polynomials, and their curves are physiologically relevant.
Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. When d ≥2, these devices characterize the class of context-free languages. In this paper we consider restricted versions of these models which we call strongly limited automata, where rewrites, head reversals, and state changes are allowed only at certain points of the computation. Those restrictions are inspired by a simple algorithm for accepting Dyck languages on 2-limited automata. We prove that the models so defined are still able to recognize all context-free languages. We also consider descriptional complexity aspects. We prove that there are polynomial transformations of context-free grammars and pushdown automata into strongly limited automata and vice versa.
11
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The main purpose of this paper is to study the controllability of solutions of the differential equation [...] In fact, we study the growth and oscillation of higher order differential polynomial with meromorphic coefficients in the unit disc [...] generated by solutions of the above kth order differential equation.
12
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
We show that a constant amount of space is sufficient to simulate a polynomial-space bounded Turing machine by P systems with active membranes. We thus obtain a new characterisation of PSPACE, which raises interesting questions about the definition of space complexity for P systems. We then propose an alternative definition, where the size of the alphabet and the number of membrane labels of each P system are also taken into account. Finally we prove that, when less than a logarithmic number of membrane labels is available, moving the input objects around the membrane structure without rewriting them is not enough to even distinguish inputs of the same length.
13
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this paper, a generalization of a result on the uniform best approximation of αcosnx+βsinnx by trigonometric polynomials of degree less than n is considered and its relationship with a well-known polynomial inequality of C. Visser is indicated.
14
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
By applying computer algebra tools (mainly, Maple and C++), given the Dynkin diagram ∆ = An, with n > 2 vertices and the Euler quadratic form q∆ : Zn → Z, we study the problem of classifying mesh root systems and the mesh geometries of roots of A (see Section 1 for details). The problem reduces to the computation of the Weyl orbits in the set Mor∆ ⊆ Mn(Z) of all matrix modifications A of q∆, i.e., the non-singular matrices A ∈ Mn(Z) such that (i) q∆ (v) = v A vtr, for all v ∈ Zn, and (ii) the Coxeter matrix CoxA := —A A-tr lies in Gl(n, Z). The Weyl group W∆ ⊆ Gl(n, Z) acts on MorA and the determinant det A ∈ Z, the order cA > 2 of CoxA (i.e. the Coxeter number), and the Coxeter polynomial coxA(t) := det(t E — CoxA) ∈ Z[t] are W∆ -invariant. The problem of determining the W∆ -orbits Orb(A) of MorA and the Coxeter polynomials coxA(t), with A e MorA, is studied in the paper and we get its solution for n < 8, and A = [aij] ∈ MorAn, with [aij] | < 1. In this case, we prove that the number of the W∆ - orbits Orb(A) and the number of the Coxeter polynomials coxA(t) equals two or three, and the following three conditions are equivalent: (i) Orb(A) = Orb(A'), (ii) coxA(t) = coxA> (t), (iii) cA det A = cA det A!. We also construct: (a) three pairwise different W∆ -orbits in Mor∆, with pairwise different Coxeter polynomials, if ∆ = A2m-i and m > 3; and (b) two pairwise different W∆ -orbits in Mor∆, with pairwise different Coxeter polynomials, if ∆ = A2m and m > 1.
In this paper we present the modular computing structures (MCS) defined on the set of polynomials over finite rings of integers. This article is a continuation of research on the development of modular number systems (MNS) on arbitrary mathematical structures such as finite groups, rings and Galois fields [1-7].
16
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The main result says in particular that if t(ζ):=∑..[formula] is a trigonometric polynomial of degree n having all its zeros in the open upper half-plane such that |t(ξ)|≥μ on the real axis and cn/=0, then |t′(ξ)|≥μn for all real ξ.
In the presence of white Gaussian noises at the input and the output of a system Kalman filters provide a minimum-variance state estimate. When part of the measurements can be regarded as noise-free, the order of the filter is reduced. The filter design can be carried out both in the time domain and in the frequency domain. In the case of full-order filters all measurements are corrupted by noise and therefore the design equations are regular. In the presence of noise-free measurements, however, they are not regular so that standard software cannot readily be applied in a time-domain design. In the frequency domain the spectral factorization of the non-regular polynomial matrix equation causes no problems. However, the known proof of optimality of the factorization result requires a regular measurement covariance matrix. This paper presents regular (reduced-order) design equations for the reduced-order discrete-time Kalman filter in the time and in the frequency domains so that standard software is applicable. They also allow to formulate the conditions for the stability of the filter and to prove the optimality of the existing solutions.
Reduced-order Kalman filters yield an optimal state estimate for linear dynamical systems, where parts of the output are not corrupted by noise. The design of such filters can either be carried out in the time domain or in the frequency domain. Different from the full-order case where all measurements are noisy, the design equations of the reduced-order filter are not regular. This is due to the rank deficient measurement covariance matrix and it can cause problems when using standard software for the solution of the Riccati equations in the time domain. In the frequency domain the spectral factorization of the non-regular polynomial matrix equation does not cause problems. However, the known proof of optimality of the factorization result also requires a regular measurement covariance matrix. This paper presents regular (reduced-order) design equations for reduced-order Kalman filters in the time and in the frequency domains for linear continuous-time systems. They allow to use standard software for the design of the filter, to formulate the conditions for the stability of the filter and they also prove that the existing frequency domain solutions obtained by spectral factorization of a non-regular polynomial matrix equation are indeed optimal.
19
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this paper the tensor interpolation by polynomials of several variables is considered. The effective formulas for polynomial coefficients for arithmetical case were obtained.
20
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Let R be a prime ring with extended centroid C and characteristic different from 2, d a nonzero derivation of R, f(x1,..., xn) a nonzero multilinear polynomial over C such that [d2(f(x1,... , xn)),d(f(x1,... ,xn))]k = 0 for all x1,... ,xn in some nonzero right ideal [...] of R, where k is a fixed positive integer. If d(p) p [..]0, then pC = eRC for some idempotent e in the socle of RC and /(x1,..., xn) is central-valued on eRCe.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.