Capitole Speciale de Informatica˘ -...

transcript

Capitole Speciale de InformaticaIntroductere în Calculul Simbolic

Mircea Marinmmarin@info.uvt.ro

10 octombrie 2011

Mircea Marin mmarin@info.uvt.ro Capitole Speciale de Informatica

Aspecte organizatorice

Prezentator si TA: Mircea MarinPagina web a cursului: http://web.info.uvt.ro/ mmarin/lectures/CSI/

materiale de curs, laborator, etc.Subiectul cursului: Capitole speciale din calculul simbolic.

Evaluare: Probleme si exercitii indicate la sfârsitulfiecarui curs (50%), folosind sistemulMathematica.Examen scris final.

Despre acest curs

Algoritmi de manipulare a expresiilor matematice(polinoame, functii trigonometrice, integrale, etc.) siformule simbolice (ecuatii, inecuatii, însumari simbolice ,etc.)Algoritmi referitori la: aritmetica multi-precizie, calculul cupolinoame (factorizare, rezolvarea sistemelor de ecuatiipolinomiale, etc.), integrare, etc.Experimente în Mathematica cu implementari concrete alealgoritmilor prezentati în curs, folosind Mathematica.

Despre acest curs

Algoritmi de manipulare a expresiilor matematice(polinoame, functii trigonometrice, integrale, etc.) siformule simbolice (ecuatii, inecuatii, însumari simbolice ,etc.)

Algoritmi referitori la: aritmetica multi-precizie, calculul cupolinoame (factorizare, rezolvarea sistemelor de ecuatiipolinomiale, etc.), integrare, etc.Experimente în Mathematica cu implementari concrete alealgoritmilor prezentati în curs, folosind Mathematica.

Despre acest curs

Algoritmi de manipulare a expresiilor matematice(polinoame, functii trigonometrice, integrale, etc.) siformule simbolice (ecuatii, inecuatii, însumari simbolice ,etc.)Algoritmi referitori la: aritmetica multi-precizie, calculul cupolinoame (factorizare, rezolvarea sistemelor de ecuatiipolinomiale, etc.), integrare, etc.

Experimente în Mathematica cu implementari concrete alealgoritmilor prezentati în curs, folosind Mathematica.

Despre acest curs

Algoritmi de manipulare a expresiilor matematice(polinoame, functii trigonometrice, integrale, etc.) siformule simbolice (ecuatii, inecuatii, însumari simbolice ,etc.)Algoritmi referitori la: aritmetica multi-precizie, calculul cupolinoame (factorizare, rezolvarea sistemelor de ecuatiipolinomiale, etc.), integrare, etc.Experimente în Mathematica cu implementari concrete alealgoritmilor prezentati în curs, folosind Mathematica.

Surse bibliografice

1 F. Winkler. Polynomial Algorithms in Computer Algebra.Springer-Verlag 1996.

2 J. von zur Gaten, J. Gerhard. Modern Computer Algebra.Cambridge University Press 2003.

3 J. Grabmeier, E. Kaltofen, V. Weispfenning. ComputerAlgebra Handbook. Springer-Verlag 2003.

IntroductionCe este calculul simbolic?

Calcul cu expresii si formule simbolice, folosind de regula uncalculator.Probleme tipice:

√4 + 2

√3 +

√4− 2

Simplific−−−−−→?∫ 12

x2−adx Calculeaz−−−−−−→?∑n

k·(k+1)Calculeaz−−−−−−→?{

x4 + 3 x2 y = 0x2 + y2 = 1

Rezolv−−−−→ (x , y) =?

(∀x)(∃y)(x2 + y2 − 4 > 0 ∧ y2 − 2 x + 2 < 0) Decide−−−−→ adevarat sau fals?

Obiectiv:

designul si implementarea de algoritmi pentru aceste tipuride probleme.

⇒ automatizarea muncii de rutina a inginerilor,matematicienilor, etc.

√4 + 2

√3 +

√4− 2

x4 + 3 x2 y = 0x2 + y2 = 1

Rezolv−−−−→ (x , y) =?

Obiectiv:designul si implementarea de algoritmi pentru aceste tipuride probleme.

√4 + 2

√3 +

√4− 2

x4 + 3 x2 y = 0x2 + y2 = 1

Rezolv−−−−→ (x , y) =?

Obiectiv:designul si implementarea de algoritmi pentru aceste tipuride probleme.

Calculul simbolic: domenii de cercetare

Logica computatonala: demonstrarea automata ateoremelor, programarea logica, etc.Algebra computationala: calculul cu expresii matematice înformat simbolic.

Vom prezenta doar subiecte legate de legate de algebracomputationala.

Caracteristicile algebrei computationale (CA)

Manipuleaza expresii simbolice si calculeaza solutii generice.Difera de calculus numeric, care opereaza preponderent cunumere iar rezultatele sunt adesea aproximative.

Rezultatele sunt exacte, fara erori de aproximare.

Example (Calcul simbolic versus Calcul numeric)

{x4 + 2x2y2 + 3x2y + y4 − y3 = 0

x2 + y2 − 1 = 0solutie exacta: (

√3/2,−1/2);

solutie aproximativa (numerica): (0.86602 . . . ,−0.5).

2∫ x

x2−a dx = ln |x2−a|2 → rezultat parametric∫ 1

xx2−1 dx = 0.1438 . . . → aproximare numerica

2 + 1− 1√2−1

→{≈ 4.44089E−16

Simplify−−−−−→ 0.

Manipuleaza expresii simbolice si calculeaza solutii generice.Difera de calculus numeric, care opereaza preponderent cunumere iar rezultatele sunt adesea aproximative.Rezultatele sunt exacte, fara erori de aproximare.

{x4 + 2x2y2 + 3x2y + y4 − y3 = 0

√3/2,−1/2);

2∫ x

2 + 1− 1√2−1

→{≈ 4.44089E−16

{x4 + 2x2y2 + 3x2y + y4 − y3 = 0

√3/2,−1/2);

2∫ x

2 + 1− 1√2−1

→{≈ 4.44089E−16

{x4 + 2x2y2 + 3x2y + y4 − y3 = 0

√3/2,−1/2);

2∫ x

2 + 1− 1√2−1

→{≈ 4.44089E−16

{x4 + 2x2y2 + 3x2y + y4 − y3 = 0

√3/2,−1/2);

2∫ x

2 + 1− 1√2−1

→{≈ 4.44089E−16

Algebra ComputationalaAlte avantaje

De multe ori este benefic sa se simplifice o expresiealgebrica înainte de a o evalua numeric⇒ calcul mai scurtsi cu mai putine erori de aproximare numerica.

algoritmii CA pot produce rezultate în forma algebrica înloc sa calculeze valori numerice pentru puncte specifice deevaluare.Example:

∫ xx2−a dx = ln |x2−a|

Algoritmi de decizie pentru: factorizarea of polinoamelor;echivalenta expresiilor algebrice (de ex.,√

2 + 1 = 1/(√

2− 1)); integrarea simbolica a unorexpresii, etc.

De multe ori este benefic sa se simplifice o expresiealgebrica înainte de a o evalua numeric⇒ calcul mai scurtsi cu mai putine erori de aproximare numerica.algoritmii CA pot produce rezultate în forma algebrica înloc sa calculeze valori numerice pentru puncte specifice deevaluare.Example:

2 + 1 = 1/(√

De multe ori este benefic sa se simplifice o expresiealgebrica înainte de a o evalua numeric⇒ calcul mai scurtsi cu mai putine erori de aproximare numerica.algoritmii CA pot produce rezultate în forma algebrica înloc sa calculeze valori numerice pentru puncte specifice deevaluare.Example:

2 + 1 = 1/(√

Computer AlgebraLimitari

1 Algoritmii de algebra computationala sunt de obicei multimai complecsi (comsumatori de timp si memorie) decâtalgoritmii numerici. Uneori, calculul unei solutii simboliceexacte este foarte costisitor.

2 Exista probleme pe care înca nu stim cum sa le rezolvamsimbolic.

3 Unele probleme nu pot fi rezolvate simbolic.

Exemplu

În general, doar polinoamele de grad ≤ 4 pot fi rezolvatesimbolic (prin radicali).

Exemplu

Aplicatii

"Problema mutarii pianului": sa se gaseasca o cale care vapermite mutarea unui corp B de la o pozitie initiala a opozitie destinatie dorita, în asa fel încât sa nu se loveascanici un obstacol.

J.T. Schwartz, M. Sharir. On the “Piano Movers” Problem.II. General Techniques for computing topological propertiesof real algebraic manifolds. Adv. Appl. Math. 4:298-351.1983.

Applicatii"Mutarea pianului"

Ideea de baza: se reprezinta pozitiile posibile aleobiectului B ca o multime semi-algebrica L în spatiul Rm –reuniune, intersectie sau diferenta de multimi{(x1, . . . , xm)|p(x1, . . . , xm) ∼ 0}, pentru care p este unpolinom cu coeficienti rationali si ∼∈ {=, <,>}.

Problema devine: “Pot fi conectate doua puncte P1, P2 aleunei semi-varietati algebrice L cu o cale, adica, fac eleparte din aceeasi componenta conexa a lui L?”Algoritmul CAD al lui Collins de eliminare a cuantificatorilorîn câmpuri reale închise poate fi folosit pentru a aflaraspunsul.

Ideea de baza: se reprezinta pozitiile posibile aleobiectului B ca o multime semi-algebrica L în spatiul Rm –reuniune, intersectie sau diferenta de multimi{(x1, . . . , xm)|p(x1, . . . , xm) ∼ 0}, pentru care p este unpolinom cu coeficienti rationali si ∼∈ {=, <,>}.Problema devine: “Pot fi conectate doua puncte P1, P2 aleunei semi-varietati algebrice L cu o cale, adica, fac eleparte din aceeasi componenta conexa a lui L?”

Algoritmul CAD al lui Collins de eliminare a cuantificatorilorîn câmpuri reale închise poate fi folosit pentru a aflaraspunsul.

Ideea de baza: se reprezinta pozitiile posibile aleobiectului B ca o multime semi-algebrica L în spatiul Rm –reuniune, intersectie sau diferenta de multimi{(x1, . . . , xm)|p(x1, . . . , xm) ∼ 0}, pentru care p este unpolinom cu coeficienti rationali si ∼∈ {=, <,>}.Problema devine: “Pot fi conectate doua puncte P1, P2 aleunei semi-varietati algebrice L cu o cale, adica, fac eleparte din aceeasi componenta conexa a lui L?”Algoritmul CAD al lui Collins de eliminare a cuantificatorilorîn câmpuri reale închise poate fi folosit pentru a aflaraspunsul.

Demonstrarea teoremelor geometrice

Piciorul perpendicularei pe ipotenuza unui triunghi dreptunghicsi mijloacele laturilor triunghiului sunt puncte conciclice.

Demonstrarea teoremelor geometrice (continuare)

The hypotheses and conclusion of this geometricstatement are polynomial equations in the coordinates ofthe points in the figure.

Hypotheses:h1 ≡ 2y3 − y1 = 0 (E is the midpoint of AC)h2 ≡ (y7 − y3)

2 + y28 − (y7 − y4)

2 − (y8 − y5)2 = 0 (EM = FM)

...hm ≡ . . .

Conclusion: EM = HMc ≡ (y7 − y3)

2 + y28 − (y7 − y9)

2 − (y8 − y10)2 = 0

We must show h1 = 0 ∧ . . . ∧ hm = 0⇒ c = 0.

This kind of questions can be answered by a Gröbnerbasis computation.

The hypotheses and conclusion of this geometricstatement are polynomial equations in the coordinates ofthe points in the figure.Hypotheses:h1 ≡ 2y3 − y1 = 0 (E is the midpoint of AC)h2 ≡ (y7 − y3)

2 + y28 − (y7 − y4)

2 − (y8 − y5)2 = 0 (EM = FM)

...hm ≡ . . .

2 + y28 − (y7 − y9)

2 − (y8 − y10)2 = 0

We must show h1 = 0 ∧ . . . ∧ hm = 0⇒ c = 0.

2 + y28 − (y7 − y4)

2 − (y8 − y5)2 = 0 (EM = FM)

...hm ≡ . . .

2 + y28 − (y7 − y9)

2 − (y8 − y10)2 = 0

We must show h1 = 0 ∧ . . . ∧ hm = 0⇒ c = 0.

2 + y28 − (y7 − y4)

2 − (y8 − y5)2 = 0 (EM = FM)

...hm ≡ . . .

2 + y28 − (y7 − y9)

2 − (y8 − y10)2 = 0

We must show h1 = 0 ∧ . . . ∧ hm = 0⇒ c = 0.

2 + y28 − (y7 − y4)

2 − (y8 − y5)2 = 0 (EM = FM)

...hm ≡ . . .

2 + y28 − (y7 − y9)

2 − (y8 − y10)2 = 0

We must show h1 = 0 ∧ . . . ∧ hm = 0⇒ c = 0.This kind of questions can be answered by a Gröbnerbasis computation.

Analysis of algebraic varieties

Algebraic variety: set of points determined by a system ofpolynomial equations.

Example (tacnode curve)

f (x , y) = 2x4 − 3x2y + y4 − 2y3 + y2 = 0.

1 How can we draw this curve? -2 -1 0 1 20.0

2 How can we compute the singular points? (Singularpoint=point where branches intersect)

f (x , y) = 2x4 − 3x2y + y4 − 2y3 + y2 = 0.

Analysis of algebraic varieties (cont.)

Singular points are the solutions of the system of equations:

f (x , y) = 2 x4 − 3 x2y + y4 − 2 y3 + y2 = 0,∂f∂x

(x , y) = 8 x3 − 6 x y = 0,

∂f∂y

(x , y) = 4 y3 − 3 x2 − 6 y2 + 2 y = 0.

A Gröbner basis computation can transform this system into anequivalent one that is easier to solve:

3x2 + 2y2 − 2y = 0x y = 0x3 = 0

⇒ singular points (0,0) and (0,1).

Analysis of algebraic varieties (cont.)

Singular points are the solutions of the system of equations:

f (x , y) = 2 x4 − 3 x2y + y4 − 2 y3 + y2 = 0,∂f∂x

(x , y) = 8 x3 − 6 x y = 0,

∂f∂y

(x , y) = 4 y3 − 3 x2 − 6 y2 + 2 y = 0.

A Gröbner basis computation can transform this system into anequivalent one that is easier to solve:

3x2 + 2y2 − 2y = 0x y = 0x3 = 0

⇒ singular points (0,0) and (0,1).

Analysis of algebraic varieties (cont.)How to draw algebraic varieties?

Implicit representation: f (x , y) = 0⇓

Parametric representation: x = x(t), y = y(t) (t is a parameter)such that f (x(t), y(t)) = 0 for all t .

Example (tacnode curve and circle)1 tacnode

f (x , y) = 0⇒

{x(t) = t3−6t2+9t−2

2t4−16t3+40t2−32t+9y(t) = t2−4t+4

2t4−16t3+40t2−32t+9

(t ∈ R)

2 circle x2 + y2 = 1⇒{

x(t) = cos(t)y(t) = sin(t)

(t ∈ [0,2π))

It is possible to compute a rational parametrization of thetacnode:

x(t) =t3 − 6t2 + 9t − 2

2t4 − 16t3 + 40t2 − 32t + 9

y(t) =t2 − 4t + 4

2t4 − 16t3 + 40t2 − 32t + 9Mircea Marin mmarin@info.uvt.ro Capitole Speciale de Informatica

Modelling in science and technology

Very often, problems in these fields are posed as integrationproblems or systems of differential equations.

−6∂q∂x

(x) +∂2p∂x2 (x)− 6 sin(x) = 0,

6∂2q∂x2 (x) + a2 ∂p

∂x− 6 cos(x) = 0

with initial values p(0) = 0, q(0) = 1, p′(0) = 0, q′(0) = 1.CA methods can find the generic solution

p(x) = −12 sin(a x)a(a2 − 1)

− 6 cos(a x)a2 +

12 sin(x)a2 − 1

+6a2 ,

q(x) =sin(a x)

a− 2 cos(a x)

a2 − 1+

(a2 + 1) cos(x)a2 − 1

for a 6∈ {−1,0,1}.

Sisteme de calcul algebric

Started to appear in the 1950s.

Most CA systems are designed for specific fields ofapplications: high energy physics, celestial mechanics,general relativity, algebraic geometry, etc.Computer-algebra systems for the general user:implement most of the important computer algebraalgorithms and which are of interest to a general user.

Maple, Mathematica, Axiom, Macsyma, Reduce, Magma,Aldor

In this course you can learn about the computer algebrasystem Mathematica (version 6), and how to use it.

Started to appear in the 1950s.Most CA systems are designed for specific fields ofapplications: high energy physics, celestial mechanics,general relativity, algebraic geometry, etc.

Computer-algebra systems for the general user:implement most of the important computer algebraalgorithms and which are of interest to a general user.

Started to appear in the 1950s.Most CA systems are designed for specific fields ofapplications: high energy physics, celestial mechanics,general relativity, algebraic geometry, etc.Computer-algebra systems for the general user:implement most of the important computer algebraalgorithms and which are of interest to a general user.

Capitole Speciale de Informatica˘ -...

Documents