Fundamentele Algebrice Ale Informaticii

download Fundamentele Algebrice Ale Informaticii

of 328

  • date post

    16-Feb-2015
  • Category

    Documents

  • view

    146
  • download

    4

Embed Size (px)

Transcript of Fundamentele Algebrice Ale Informaticii

UNIVERSITATEA TITU MAIORESCUFacultatea de tiina i Tehnologia Informaiei

Conf. univ. dr.

VALENTIN GRBANLect. univ. dr.

Asist. univ.drd.

SIBICEANU MARIANA

ZANFIR VERONICA

Curs pentru nvmntul la distan

BUCURETI 2008

UNIVERSITATEA Titu MAIORESCU BUCURETI Facultatea tiina i Tehnologia Informaiei nvmnt la Distan

ALGEBR I GEOMETRIEAlgebra este una din disciplinele de pregtire fundamental care, pentru profilul INFORMATIC, este impus de ctre Agenia Naional pentru Asigurarea Calitii n nvmntul Superior (ARACIS) ca esenial pentru pregtirea studenilor i pentru depirea procedurilor de evaluare i acreditare. Modul de prezentare a acestui material are n vedere particularitile nvmntului la distan, la care studiul individual este determinant. Pentru orice nelmuriri fa de acest material v rugm s contactai tutorele de disciplin care are datoria s v ajute oferindu-v toate explicaiile necesare. Disciplina de Algebr (semestrul I) i propune urmtoarele obiective specifice: Formarea la studeni a capacitilor de a raiona modern matematic; Identificarea corect a tuturor dimensiunilor unei probleme matematice precum i a procedurilor ce pot fi utilizate pentru rezolvarea acestora; O comparaie critic a metodelor de rezolvare evideniind, eventual, calea optim de soluionare; Stabilirea de conexiuni cu celelalte discipline de factur matematic att n faza de formulare- reformulare a problemei ct i n ceeace privete modalitile de rezolvare. V precizm de asemenea c, din punct de vedere al verificrilor i al notrii, cu adevrat important este capacitatea pe care trebuie s o dobndii i s o probai de a rezolva toat tipologia de probleme aplicative aferente materialului teoretic prezentat n continuare. De aceea v recomandm s parcurgei cu atenie toate problemele rezolvate, s rezolvai problemele propuse i de asemenea s nu ocolii testele de autoevaluare; fii convini c examenul final apeleaz la tipurile de probleme prezente n seciunile menionate anterior. SUCCES! Coordonator disciplin: Conf. univ. dr. Valentin GRBAN Tutore: Asist. univ. drd. Veronica ZANFIR

2

MODULUL I SISTEME DE ECUAII LINIAREn acest modul vei dobndi cunotine referitoare la: Sisteme algebrice liniare neomogene; Sisteme algebrice liniare omogene; Compatibilitatea sistemelor algebrice liniare; Proceduri de rezolvare a sistemelor algebrice liniare; Cazurile de nedeterminare i modul de obinere a soluiei optime; Utilizarea calculatoarelor numerice pentru soluionarea sistemelor algebrice liniare; Cunoaterea i utilizarea programelor de calcul dedicate soluionrii sistemelor de ecuaii liniare. Materialul trebuie parcurs n ordinea sa fireasc prezentat n continuare, inclusiv n poriunea referitoare la aplicaii. Metoda de studiu trebuie s fie cea specific disciplinelor matematice, cu utilizarea expres a adnotrilor fcute cu creionul pe tot parcursul textului. V recomandm s v constituii un caiet de probleme i, pentru fiecare tip de exerciiu, s v fixai algoritmul de rezolvare pe etape. Rezolvai ct mai complet problemele propuse i cele coninute n testul de autoevaluare. Timpul minim pe care trebuie s-l acordai acestui modul este de 6 ore.

3

LECIA I.1 DEFINIREA SISTEMELOR DE ECUAII LINIARE. METODE FUNDAMENTALE DE REZOLVAREn aceast lecie vei dobndi cunotine referitoare la: Definirea sistemelor algebrice liniare; Forme echivalente de scriere a sistemelor algebrice liniare; Conexiuni ntre diversele reprezentri ale sistemelor algebrice liniare; Proceduri fundamentale de rezolvare a sistemelor algebrice liniare; Algoritmizarea procedurilor de soluionare a sistemelor algebrice liniare; Timpul minim pe care trebuie s-l acordai acestui modul este de 3 ore.

LI.1.1. MODURI DE SCRIERE A SISTEMELOR. DEFINIIIForma desfurat de scriere a unui sistem de m ecuaii cu n necunoscute este urmtoarea:a11 x1 + a12 x2 + ... + a1n xn = b1 a x + a x + ... + a x = b 21 1 22 2 2n n 2 ............................................ am1 x1 + am 2 x2 + ... + amn xn = bm

n care aij , bi cu i = 1,2,..., m i j = 1,2,..., n sunt elemente dintr-un corp comutativ K. Corpul K poate fi, de exemplu, corpul R al numerelor reale, corpul Q al numerelor raionale, corpul C al numerelor complexe, corpul Z p al claselor de4

resturi n raport cu numrul prim p etc. Elementele aij se numesc coeficienii necunoscutelor, iar bi se numesc termenii liberi. Anume, aij este coeficientul lui x j din ecuaia i, iar bi este termenul liber al ecuaiei i. Forma concentrat de scriere este:

aij x j = bi ;j =1

n

i = 1,2,..., m

Sistemul se poate scrie i sub forma matriceal: A X = B n care: a11 a A = 21 ... a m1 a12 a22 ... am 2 a1n b1 x1 ... a2 n ; X = x2 ; B = b2 ... ... ... ... b x ... amn m n ...

Elementele x1 , x2 ,..., xn se numesc necunoscutele sistemului, care urmeaz a se gsi n corpul K, pe cnd aij i bi , aflate tot n K, se consider cunoscute.0 0 0 Numim soluie a sistemului un ir ordonat de elemente din K: x1 , x2 ,..., xn care puse n locul necunoscutelor x1 , x2 ,..., xn , fac ca toate ecuaiile sistemului s fie satisfcute. Rezult urmtoarea clasificare a sistemelor: Un sistem se numete compatibil dac are cel puin o soluie. n acest caz el se zice compatibil i determinat dac are o singur soluie i compatibil i nedeterminat dac are cel puin dou soluii. Sistemul se numete incompatibil dac nu are nici-o soluie. De exemplu urmtorul sistem este incompatibil:

2x + 3 y = 1 . 4 x + 6 y = 5

Rezolvarea unui sistem nseamn a stabili dac este compatibil sau incompatibil, iar n caz de compatibilitate rezolvarea sistemului presupune gsirea tuturor soluiilor sale. Printre metodele de rezolvare menionm metoda lui Cramer, explicat n manualul de algebr de clasa a-XI-a. Aceast metod se aplic n cazul particular cnd sunt ndeplinite urmtoarele condiii: n scrierea matriceal a sistemului, A X = B , matricea A este ptratic (deci numrul de ecuaii este egal cu numrul de necunoscute) i determinantul matricei A este nenul. n acest caz, dup cum se tie, sistemul este compatibil i determinat.

5

LI.1.2. METODA ELIMINRII SUCCESIVE PENTRU REZOLVAREA SISTEMELOR LINIARES considerm mai nti urmtorul sistem: a1 x1 = b1 a x = b 2 2 2 ... an xn = bn

( )

;

a1 a2 ... an 0 ,

care este, bineneles, compatibil i determinat, avnd soluia: x1 = b b1 b , x2 = 2 ,..., xn = n . a1 a2 an

Pe de alt parte s remarcm c asupra unui sistem se pot efectua o serie de transformri care nu-i schimb mulimea de soluii. Astfel de transformri sunt numite transformri echivalente. Menionm trei tipuri de transformri echivalente care vor fi folosite n cele ce urmeaz: Schimbarea ordinii ecuaiilor. I. nmulirea unei ecuaii cu un factor nenul. II. III. nmulirea unei ecuaii cu un factor oarecare (nul sau nenul) spre a se aduna la o alt ecuaie. Este evident c transformrile enumerate mai sus nu schimb mulimea de soluii, adic sunt transformri echivalente. Importana lor este relevat n urmtoarea: Teorem Printr-un ir de transformri de tipul I, II, III, orice sistem liniar poate fi adus la o form asemntoare cu sistemul (*). Demonstraie Admitem pentru nceput ipoteza c a11 , coeficientul lui x1 din prima ecuaie, este nenul. Pentru rolul pe care-l va avea acest element, l numim pivot. Aplicm sistemului transformri de tipul I, II sau III prin care vom face ca x1 , care apare n prima ecuaie, deoarece coeficientul su, a11 , este nenul, s nu mai apar n celelalte ecuaii. De exemplu, pentru a face ca x1 s nu mai apar n a doua ecuaie, se nmulete ecuaia a doua cu a11 , (transformare de tipul II deoarece a11 este nenul), apoi se nmulete prima ecuaie cu ( a21 ) spre a o aduna la a doua (transformare de tipul II). n general, pentru a face s dispar x1 din ecuaia i, se nmulete ecuaia i cu a11 apoi se nmulete prima ecuaie cu ai1 spre a o aduna la ecuaia i. Transformnd astfel toate ecuaiile sistemului, el va cpta forma:

6

a11(1) x1 + a12(1) x2 + ...+ a1 j (1) x j + ...+ a1n (1) xn = b1(1) a22(1) x2 + ... + a2 j (1) x j + ... + a2 n (1) xn = b2(1) ........................................................................ ai 2(1) x2 + ...+ aij (1) x j + ...+ ain (1) xn = bi (1) ........................................................................ am 2(1) x2 + ... + amj (1) x j + ... + amn (1) xn = bm (1)

S-au marcat cu indicele superior (1) noii coeficieni i termeni liberi ai ecuaiilor. Dei prima ecuaie a rmas neschimbat, pentru uniformitate, au fost marcai la fel i coeficienii i termenul liber ai acestei ecuaii. Spunem c am realizat prima iteraie asupra sistemului. n principiu n aceast nou form sistemul se reduce la cel format din ultimele m 1 ecuaii: dac se rezolv acesta din urm atunci prima ecuaie servete la determinarea lui x1 . Se poate stabili nu numai formula, dar i o regul simpl de calculare a coeficienilor i termenilor liberi pentru noua form a sistemului, n afar de cei din prima ecuaie, care aa cum am menionat, rmn neschimbai. a11 x1 + a12 x2 + ... + a1 j x j + ...+ a1n xn = b1 ( ai1 ) a21 x1 + a22 x2 + ... + a2 j x j + ...+ a2 n xn = b2 + ................................................................ ai1 x1 + ai 2 x2 + ... + aij x j + ...+ ain xn = bi a11 ................................................................ am1 x1 + am 2 x2 +...+ amj x j + ...+ amn xn = bm Deoarece ecuaia i se nmulete cu a11 urmnd apoi s se adune acesteia prima ecuaie nmulit cu ( ai1 ) rezult c noul coeficient al lui x j n ecuaia i se poate calcula cu formula: aij (1) = a11aij ai1a1 j . Se observ urmtoarea regul de calculare a lui aij (1) : ducnd o sgeat care unete pivotul a11 cu elementul aij care urmeaz a fi transformat, aceast sgeat este diagonala dreptunghiului marcat n figur; potrivit formulei, cu ajutorul acestui dreptunghi, se poate calcula aij (1) ca diferena dintre produsul elementelor de pe diagonala care conine pivotul i produsul