Algoritmi liniari

În acest capitol vom demonstra optimalitatea unor algoritmi ce intervin (sau pot fi formulati) în calculul matricial.

Notiunea de algoritm liniar

Fie K un corp comutativ. Un algoritm liniar este un ansamblu format din:

o multime de nedeterminate a₁,...,a_n ce nu apartin lui K, numite intrari;

o multime finita de (nume de) variabile, distincte de intrari si de elementele lui K

o secventa finita de pasi de forma a b c, unde:

a este o variabila care nu a aparut în pasii precedenti;

b si c sunt fie intrari, fie variabile ce au primit valoare (au aparut în st 151h76b ânga semnului ) în pasii precedenti.

Vom scrie prescurtat a b si a -b în loc de a 0+b, respectiv a 0-b

Algoritmii liniari se executa pas cu pas, începând cu primul si terminând cu ultimul.

Pentru a putea preciza rezultatul executarii unui algoritm, vom introduce notiunea de valoare v(a) a unei intrari sau variabile a astfel:

v(a)=a daca a este intrare;

v(a)=v(b) v(c) daca unicul pas în care a primeste valoare este a b c

Rezulta ca v(a) K[a₁,...,a_n], unde K[a₁,...,a_n] este inelul polinoamelor peste K în a₁,...,a_n si este spatiu vectorial peste K

Spunem ca un algoritm liniar calculeaza E K[a₁,...,a_n] daca pentru orice e E, exista  în algoritm o variabila f cu v(f)=e

Exemplul 1. Fie K=R. Un algoritm liniar ce calculeaza produsul (a+bi)(c+di)=ac-bd + i(ad+bc) a doua numere complexe este urmatorul:

f₁ a * c v(f₁)=ac

f₂ b * d v(f₂)=bd

f₃ f₁ - f₂ v(f₃)=ac-bd

f₄ a * d v(f₄)=ad

f₅ b * c v(f₅)=bc

f₆ f₄ + f₅ v(f₆)=ad+bc

deoarece calculeaza E= R[a,b,c,d]

Un alt algoritm liniar pentru aceeasi problema este urmatorul:

f₁ a * c v(f₁)=ac

f₂ b * d v(f₂)=bd

f₃ f₁ - f₂ v(f₃)=ac-bd

f₄ a + d v(f₄)=a+b

f₅ c + d v(f₅)=c+d

f₆ f₄ * f₅ v(f₆)=(a+b)(c+d)

f₇ f₆ - f₁ v(f₇)=ad+bc+bd

f₈ f₇ - f₂ v(f₈)=ad+bc

care foloseste însa doar 3 înmultiri.

Observatie. Multe calcule se pot reprezenta ca produsul dintre o matrice si un vector. De exemplu produsul de numere complexe de mai sus se poate scrie:

Ne vom îndrepta atentia asupra numarului de înmultiri, deoarece efectuarea unei înmultiri necesita mai mult timp decât o adunare; în plus, în exemplele tratate, numarul de adunari/scaderi nu va depasi numarul de înmultiri.

Fie K un corp comutativ si fie K^m[a₁,...,a_n] spatiul vectorial al vectorilor cu m componente din K[a₁,...,a_n]

Fie v₁,...,v_k K^m[a₁,...,a_n]. Spunem ca v₁,...,v_k sunt liniar independenti (modulo K^m) daca "a a_k K cu a v₁+...+a_kv_k K^m a a_k

Fie M_l,c(K[a₁,...,a_n]) spatiu vectorial peste K al matricilor cu l linii si c coloane. Cum elementele unor astfel de matrici apartin unui inel si nu unui corp, rangul pe linii nu coincide neaparat cu cel pe coloane. De exemplu matricea:

are rangul pe linii egal cu 2, iar rangul pe coloane egal cu 3.

Fie si doua multimi disjuncte de nedeterminate ce nu fac parte din K

Fie M M_l,c(K[a₁,...,a_n]) si fie x vectorul coloana x=(x₁,...,x_c)^T. Ne punem problema determinarii numarului de înmultiri necesare calculului produsului Mx

Rangul pe linii al matricilor

Teorema 1. Daca rangul pe linii al lui M este r, atunci orice algoritm liniar ce calculeaza produsul Mx necesita cel putin r pasi de înmultire.

Vom numara numai înmultirile în care nici un factor nu este din K. Presupunem ca primele linii din M sunt liniar independente. Fie M' matricea formata din primele l linii ale lui M. Cum orice algoritm ce calculeaza Mx calculeaza si M'x, putem presupune ca l=r

Fie e₁,...,e_s K[a₁,...,a_n,x₁,...,x_c] rezultatele pasilor de înmultire efectuati în calculul produsului Mx. Vom arata ca s r

Mx se poate scrie Mx=Ne+f, unde N M_l,s(K), iar f are ca elemente functii liniare în a₁,...,a_n,x₁,...,x_c

Sa presupunem ca r>s. Atunci matricea N, cu elemente în corpul K, are mai multe linii decât coloane, deci liniile sale sunt liniar dependente. Rezulta ca exista y₁,...,y_r K nu toti nuli, cu y^TN=0^T

y^TMx = y^TNe + y^Tf = y^Tf

Cum y^Tf, deci si (y^TM)x este liniar în a₁,...,a_n,x₁,...,x_c, rezulta ca elementele vectorului y^TM sunt din K, adica liniile lui M sunt liniar dependente. Contradictie, deoarece rangul pe linii al lui M este r

Rangul pe coloane al matricilor

Lema. Fie v₁,...,v_k K^m[a₁,...,a_n] dintre care cel putin p sunt liniar independenti (modul K^m). Fie v'_i=v_i+b_iv₁ cu b_i K, "i=2,...,k. Atunci în apar cel putin p-1 vectori liniar independenti.

Deosebim doua cazuri:

Daca v₁ apare printre cei p vectori liniar independenti.

Fie v₁,...,v_p vectorii liniar independenti. Aratam ca v'₂,...,v'_p sunt liniar independenti.

Fie a a_p K cu a v'₂+...+a_pv'_p K^m

a v₂+...+a_pv_p+(a b₂+...+a_pb_p)v₁ K^m a a_p

Daca v₂,...,v_p+1 sunt liniar independenti.

Daca v'₂,...,v'_p sunt liniar independenti, s-a obtinut rezultatul dorit.

În caz contrar, exista a a_p K nu toti nuli, cu a v'₂+...+a_pv'_p K^m

Fie w=a v₁+a v₂+...+a_pv_p K^m, unde a a b₂+...+a_pv_p

Sa observam ca a , pentru ca daca a , atunci v₂,...,v_p ar fi liniar independenti.

Atunci v₁ = a [w-(a v₂+...+a_pv_p)]

si putem presupune ca a

Daca v'₃,...,v'_p+1 sunt liniar independenti, s-a obtinut rezultatul dorit.

În caz contrar, exista b b_p+1 K nu toti nuli, cu b v'₃+...+b_p+1v'_p+1 K^m

Fie w'=β₁v₁+ β₃v₃ +...+ β_p+1v_p+1 K^m, unde β₁=β₃b₃+...+a_pv_p

Sa observam ca , pentru ca daca , atunci v₃,...,v_p+1 ar fi liniar independenti.

Atunci v₁ = β₁^-1 [w'-(β₃v₃+...+ β_p+1v_p+1)] (2)

Egalam cele doua expresii ale lui v₁ din (1) si (2) si înmultim cu a

β₁w-β₁(a v₂+...+a_pv_p) = a w'-a (β₃v₃+...+ β_p+1v_p+1)

Rezulta ca o combinatie liniara a vectorilor v₂,...,v_p+1, în care coeficientul lui v₂ este a , este egala cu β₁w-a w' K^m. Contradictie, deoarece v₂,...,v_p+1 sunt liniar independenti.

În continuare vom întelege prin înmultire activa o înmultire în care un factor contine o nedeterminata x_i, iar celalalt factor nu este din K

Altfel spus, A^.B este înmultire activa daca v(A) K[a₁,...,a_n] si v(B) K (sau invers).

De exemplu ax_i βa_i a_ia_j cu a b K nu sunt active (deci în esenta o înmultire activa presupune o înmultire dintr-un x_i si un a_j

Teorema 2. Daca rangul pe coloane al lui M este r, atunci orice algoritm ce calculeaza Mx+y, unde y K^l[a₁,...,a_n], necesita cel putin r înmultiri active.

Facem demonstratia prin inductie dupa r

Pentru r=1, din ipoteza rezulta ca exista m_ij K[a₁,...,a_n]\K. Atunci:

(Mx+y)_i = m_i1x₁+...+m_ijx_j+...+m_icx_c+y_i contine înmultirea activa m_ijx_j

Presupunem proprietatea din enunt adevarata pentru r si o demonstram pentru r+1

Fie A un algoritm ce calculeaza Mx+y. Punem în evidenta prima înmultire activa f g^.h cu:

cu g , iar v(h) K

Observam ca pentru (*)

obtinem v(g)=0, deci v(f)=0

Construim un nou algoritm A' astfel:

prima instructiune este (*);

urmeza A în care f g^.h se înlocuieste cu f

În A' apare o multime activa în minus. Este suficient sa arat ca ceea ce calculeaza A' necesita cel putin r-1 înmultiri active.

A' calculeaza Mx'+y, unde x'=(,x₂,...,x_c)

Putem scrie Mx'+y=N+y', unde:

N=M, iar y'=M+y

Se observa ca în y' nu apar x₁,...,x_c

Fie n₁,...,n_l liniile lui N

n_i=-m_i1g g x₂+...+g_cx_c)+m_i2x₂+...+m_icx_c

n_i=(m_i2-g g m_i1)x₂+...+(m_c-g g m₁)x_c

Daca notam prin m₁,...,m_c coloanele lui M, atunci:

N=(m₂-g g m₁)x₂+...+(m_c-g g m₁)x_c

Deci putem scrie N=M'(x₂,...,x_c)^T, unde M' are l linii si c-1 coloane.

Conform lemei de mai sus, rezulta ca M' are cel putin r-1 coloane liniar independente. Deducem ca A' necesita cel putin r-1 înmultiri active, deci A necesita cel putin r înmultiri active.

Consecinta 1. Fie A o matrice cu m linii si n coloane, iar x un vector cu n elemente. Atunci produsul Ax necesita cel putin m^.n înmultiri.

Produsul Ax mai poate fi scris si sub forma:

unde rangul pe coloane al noii matrici ce intervine în produs este m^.n

Consecinta 2 Schema lui Horner este optima ca numar de înmultiri.

stim ca schema lui Horner calculeaza valoarea unui polinom de grad n

P(x)=a₀+a₁x+...+a_nxⁿ

folosind n înmultiri. Dar P(x) se mai poate scrie:

P(x)=(1 x ... xⁿ)(a₀ a₁ ... a_n)^T

Cum rangul pe coloane al matricii (1 x ... xⁿ) este n, rezulta ca sunt necesare cel putin n înmultiri.

Propozitie. Schema lui Horner este optima si ca numar de adunari/scaderi.

Fie A un algoritm liniar ce calculeaza P(x). Consideram algoritmul A'   în care:

prima instructiune este s

urmeaza algoritmul A în care x este înlocuit cu s

A' calculeaza a₀+...+a_n

Aratam prin inductie dupa n ca A' necesita cel putin n adunari/scaderi.

Pentru n=1, calculul a₀+a₁ necesita cel putin o adunare, deoarece în caz contrar putem calcula doar expresii de forma

Presupunem afirmatia din enunt adevarata pentru n-1 si demonstram ca este adevarata si pentru n

Deoarece în A' nu e posibil ca în toate adunarile sa apara numai termeni din K, rezulta ca va exista un pas la care apare cu a . Putem presupune ca apare a_n. Daca înlocuim pe a_n cu , noul algoritm va calcula a₀+...+a_n-1 si are o adunare/scadere mai putin.

Rangul pe linii si coloane al matricilor

Teorema 3 Fie S M_m,d(K[a₁,...,a_n]) o submatrice a lui M astfel încât:

daca pentru "u K^m si v K^d cu u^TSv K u=0 sau v=0

atunci orice algoritmul liniar ce calculeaza Mx necesita cel putin m+d-1 înmultiri.

Printr-o permutare de linii si coloane, putem presupune ca M are forma:

l

Putem neglija ultimele l-m linii si atunci M are forma:

cu l=m linii.

Vom întelege în continuare prin înmultiri numai produsele în care nici un factor nu este din K

Fie A un algoritm liniar ce calculeaza Mx si fie:

e₁,...,e_s K[a₁,...,a_n,x₁,...,x_c]

rezultatele (în ordinea calculului lor) a celor s pasi de înmultire.

Atunci putem scrie Mx=Ne+f unde N M_l,s(K), iar elementele lui f sunt liniare în a₁,...a_n,x₁,...,x_c

Daca l>s, atunci liniile matricii N sunt liniar dependente, deci exista y K^l cu y^TN=0. Atunci y^TMx=y^Tf, ceea ce este posibil doar daca y^TM are toate elementele în K. Aleg atunci z=(1,...,1,0,...,0)^T cu d de si l de si obtinem y^TSz K cu y≠0 si z≠0. Contradictie.

Rezulta ca l≤s. Atunci N are forma:

Notând prin e' primele s-l+1, iar prin e" ultimele l-1 elemente din e, putem scrie Mx=N₁e'+N₂e"+f

Cum liniile din N₂ sunt liniar dependente, exista y K^l cu y^TN₂=0. Atunci y^TMx=y^TN₁e'+y^Tf. Fie M'=y^TM. Deci M'x poate fi calculata folosind |e'|=s-l+1 pasi de înmultire (conform modului în care au fost alese e₁,...,e_s

Daca am sti ca d dintre coloanele (elementele) lui M' sunt liniar independente, ar rezulta ca pentru calculul lui M'x sunt necesare cel putin d înmultiri, ar rezulta ca s-l+1 d, deci s l+d-1=m+d-1, ceea ce trebuia demonstrat.

Aratam ca primele d coloane ale lui M' sunt liniar independente. Ele sunt:

, j=1,...d

Daca aceste coloane ar fi liniar dependente, ar exista z K^d cu , adica y^TSz K. Contradictie.

Aplicatie. Produsul (a+bi)(c+di) necesita cel putin 3 înmultiri de numere reale.

Calculul produsului revine la înmultirea de matrici:

Aratam ca matricea joaca rolul matricii S din Teorema 3.

Fie y₁,y₂,z₁,z₂ R cu:

R

Atunci y₁(az₁-bz₂)+y₂(by₁+az₂) R cu a,b nedeterminate. Obtinem sistemul omogen în z₁,z₂

y₁z₁+y₂z₂=0

y₂z₁-y₁z₂=0

Determinantul este D=-(y₁²+y₂²)

Daca D atunci y₁=y₂=0

Daca D atunci z₁=z₂=0 (sistemul este omogen).

Conform Teoremei 3, rezulta ca sunt necesare cel putin 3 înmultiri. Amintim ca la începutul capitolului am prezentat un algoritm liniar ce calculeaza produsul a doua numere complexe folosind 3 înmultiri (de numere reale); deci acel algoritm este optim.