04. Cap2 - Rezolvarea numerica a ecuatiilor algebrice

download 04. Cap2 - Rezolvarea numerica a ecuatiilor algebrice

If you can't read please download the document

  • date post

    28-Jun-2015
  • Category

    Documents

  • view

    540
  • download

    11

Embed Size (px)

Transcript of 04. Cap2 - Rezolvarea numerica a ecuatiilor algebrice

REZOLVAREA NUMERIC A ECUAIILOR ALGEBRICE*Pn la ecuaiile de gradul patru, algebra dispune de metode i formule pentru calculul soluiilor acestora. Pentru ecuaiile de grad mai mare ca patru, cu rdcini iraionale, determinarea acestora se poate face numai prin aproximaii. Calculul rdcinilor unei ecuaii se face n dou etape: 1) separarea rdcinilor, 2) calculul lor cu o eroare impus.

2

2.1. SEPARAREA RDCINILOR[ Considerm funcia f :[a , b] R, x a ,b ] i ecuaia algebric f(x) =0 . (2.1) Separarea rdcinilor unei ecuaii f ( x ) = 0 const n determinarea unor intervale n domeniul de definiie al funciei, n care s existe o singur rdcin real. Pentru separarea rdcinilor reale exist mai multe metode dintre care amintim: metoda irului lui Rolle, metoda irului lui turm i metoda lui Budan-Fourier. 2.1.1. METODA IRULUI LUI ROLLEAceast metod se bazeaz pe o consecin a teoremei lui Rolle care afirm c: ntre dou rdcini consecutive ale derivatei f ' ( x ) = 0 exist cel mult o rdcin real a ecuaiei f ( x ) = 0 . Exist cu siguran o soluie ntre rdcinile consecutive ale derivatei f ' ( x ) =0 , dac produsul valorilor funciei pentru cele dou rdcini consecutive ale derivatei este negativ . Considerm x1 < x2 < x3 < ... < xn , rdcinile ecuaiei f ' ( x ) =0 . Se construiete irul lui Rolle: f ( a ), f ( x1 ), f ( x2 ), ..., f ( x n ), f ( b ) (2.2) Numrul de variaii de semn din irul lui Rolle reprezint numrul de rdcini reale ale ecuaiei f ( x ) = 0 , iar rdcinile consecutive ale derivatei pentru care avem variaia de semn a irului reprezint intervalele n care exist o rdcin real a ecuaiei (2.1). Dac f ( x ) este definit pe ntreaga ax real, R , irul lui Rolle conine _____________________________ *) Bibliografie: [3],[6],[7],[11],[21]. i termenii cu valorile funciei la + i - :

16f ( - ,f ( x1 ) ,f ( x2 ) , ... , f )

Metode numerice n electronic

( xn ) , f (+) .

(2.3) 0..Pentru aplicarea acestei metode trebuie s determinm soluiile ecuaiei f ' ( x ) =0 . Pentru ecuaii de grad mai mic metoda este avantajoas, dar pentru ecuaii de grad mare rezolvarea ecuaiei derivatei poate deveni tot att de dificil ca i rezolvarea ecuaiei date f ( x ) = 0 .

2.1.2. METODA IRULUI LUI TURMConsiderm funcia definit n (2.1) care ndeplinete condiiile de continuitate i [ derivabilitate pentru x a, b ] . Definiia 2.1 irul de funcii f 0 , f1, f 2 ,..., f m continue pe [a , b] care satisfac condiiile: 1) f 0 ( x ) = f ( x ); [ 2) f m ( x ) 0 pentru x a , b] ; [ 3) dac f i ( x ) = 0 , 1 i m-1 i x a, b ] , atunci f i 1 ( x ) f i +1 ( x ) < 0 ;

' ( 4) dac f 0 ( x ) = 0 pentru x a , b ) , atunci f0(x) f1 ( x ) >0 se numete ir turm asociat funciei f ( x ) . Numrul rdcinilor ecuaiei f ( x ) n intervalul [a , b] este dat de urmtoarea teorem Teorema 2.1. Fie irul turm f 0 ,f 1 ,f 2 ,...,f m , ataat funciei f ( x ) cu f ( a ) 0 i f ( b) 0 , atunci numrul de rdcini ale ecuaiei f ( x ) = 0 condiiile n intervalul [a , b] este dat de diferena numrului de variaii de semn ale irurilor: f 0 ( a ) , f 1 ( a ) , ... , f m ( a ) (2.4)

f 0 ( b) , f 1 ( b) ,... , f

m

( b)

(2.5) n cazul funciei

polinom P( x ) care este definit pe R, teorema (2.1) devine: Teorema 2.2 Fie P , P , P ,..., P un ir de polinoame construit astfel 0 1 2 m 1 P + este restul mpririi lui P la P luat cu semn P0= P, P1= P , iar i 1 i 1 i schimbat, pentru 2 i m . Atunci numrul de rdcini ale ecuaiei P( x ) = 0 este egal cu diferena dintre numrul de schimbri de semn ale irurilor: P ( ) ,P1 ( ) ,P2 ( ) , , Pm ( ) (2.6) 0 (2.7) Demonstraie. Trebuie s artm c irul format este un ir turm. Condiiile irului lui turm sunt ndeplinite. Prima condiie este ndeplinit din construcia irului. A doua condiie este ndeplinit deoarece considerm c polinomul nu are rdcini multiple, deci P( x ) i P' ( x ) nu au rdcini multiple. Construim termenii irului folosind algoritmul lui Euclid. Se schimb doar semnul restului.P ( ,P1 ( ,P2 ( , ,Pm ( ) ) ) ) 0

Rezolvarea numeric a ecuaiilor algebriceP 1 ( x ) = P ( x ). Qi ( x ) P +1 ( x ) ; i = 1, 2,..., m 1 i i i

17

(2.8) Aplicnd algoritmul, obinem: ( P ( x ), P ( x )) = P ( x ) =constant 0, deoarece 0 1 m P ( x ) i P ( x ) sunt prime ntre ele. Pentru P ( x ) = 0 din relaia (2.8) se vede c 0 1 i este ndeplinit i condiia 3 din definiia irului lui turm. Dac P( x ) =0 pentru x R, deoarece P( x ) i P' ( x ) nu au rdcini comune, rezult c :P' ( x ) = P' ( x ) = P ( x ) 0 P' ( x ) P ( x ) = P 2 ( x ) > 0 , 0 1 0 1 1

expresie care arat ndeplinirea condiiei 4 din definiia irului lui turm. Pe baza teoremei 2.1, teorema este demonstrat. n cazul cnd P( x ) are rdcini multiple, polinomul P ( x ) va fi cel mai mare m divizor al polinoamelor: P( x ) i P' ( x ) . irul obinut se mparte la P ( x ) i se m obine irul turm cruia i putem aplica teorema 2.2 . Dup relaia de recuren (2.8) s-a realizat un algoritm pentru obinerea unui ir turm ataat unui polinom de gradul n. Algoritmul determin resturile cu semn schimbat din algoritmul lui Euclid aplicat polinomului i derivatei lui. Dac polinomul i derivata lui sunt prime, ultimul rest este o constant iar n caz contrar este cel mai mare divizor al lor.

2.1.2.1. Algoritmul 2.1{Variabile grad:gradul polinomului, ntreg); P1:vectorul coeficienilor polinomului; P2:vectorul coeficienilor derivatei polinomului; Rez:vectorul coeficienilor restului; C1,C2:coeficienii pentru calculul coeficienilor restului, reali; { pentru i=grad-1 pn la 0 calculeaz P2[i]=(i+1)P1[i+1]; { dac grad=0 atunci Rez(0)=P1(0)-P1(1) /* Restul are gradul grad-2 */ altfel { calculeaz C1:=P1[grad]/P2[grad-1]; calculeaz C2:=(P1[grad-1]-C1*P2[grad-2])/P2[grad-1]; pentru i=grad-2 pn la 1 calculeaz Rez[i]=P1[i]-C1*P2[i-1]-C2*P2[i]; calculeaz Rez[0]=P1[0]=P1-C2*P2[0]; }

}Tiprete coeficienii restului cu semnul schimbat; } }

18

Metode numerice n electronic

2.1.2.2. Implementarea algoritmului 2.1/ *Funcia care implementeaz calculul coeficienilor primei derivate a polinomului. */ void DerPoli( int grad, double *coef, double *rez) { int i; For (i=grad-1;i>=0;i--) rez[i]=(i+1)*coef[i+1]; } /* Funcia care implementeaz termenii irului lui turm pentru polinom Funcia ntoarce 0 dac nu se poate realiza irul 1 dac se realizeaz irul */ int Divi( int grad, double *p1, double *p2, double *rez) { double const1,const2; int i; if (grad= = 1) { rez[0]=p1[0]-p1[1]; return 1; } else { const1=p1[grad]/p2[grad-1]; const2=(p1[grad-1]-const1*p2[grad-2])/p2[grad-1]; for (i=grad-2;i>=1;i--)rez[i]=p1[i]-const1*p2[i-1]-const2*p2[i]; rez[0]=p1[0]=p1-const2*p2[0]; return 0; }

2.1.3. METODA BUDAN-FOURIERAceast metod se bazeaz pe teorema lui Budan - Fourier i determin numrul rdcinilor reale ale ecuaiei polinomiale cu coeficieni reali . Teorema 2.3 Fie polinomul P( x ) = a0 x n + a1 x n-1 + ... + an cu a 0 0 i irul derivatelor lui: P( x ) , P ' ( x ) , P '' ( x ) ,... , P ( n ) ( x )= 0 n! a (2.9)

Rezolvarea numeric a ecuaiilor algebrice

19

Numrul rdcinilor ecuaiei P( x ) = 0 n intervalul ( a , b), a , b R este dat de N ( a, b ) = N ( a ) N ( b) sau difer de acesta cu un numr par N ( a , b ) = N ( a ) N ( b ) 2 m , unde N ( a ) este numrul inferior de schimbri de semn al irului derivatelor pentru x = a i N ( b) este numrul superior de schimbri de semn al irului derivatelor pentru x = b . Numrul inferior de schimbri de semn al irului este numrul de schimbri de semn al subirului termenilor diferii de zero, iar numrul superior de schimbri de semn al irului este numrul de schimbri al irului unde termenii nuliP(b) ) = P(b) ( (g g +1) g +k +1) = = P(b) =0 (

se nlocuiesc cu elementelek-j g+j sign P( (b) ) = ( 1)

P ( g+j ) j = g +k sign P( b) ) (

( P(( )

g 1) b

g +k 0 ; P ( (b) ) 0

),

0 , 1, ... , k-1 crora li se atribuie semnul

Aceast metod are dezavantajul c nu determin precis numrul de rdcini reale ale ecuaiei polinomiale . Dintre toate metodele de separare a rdcinilor reale ale unei ecuaii algebrice cea mai utilizat este metoda irului lui turm, iar pentru ecuaii de grad mai mic ca patru se poate utiliza cu mult succes i metoda irului lui Rolle .

2.2. CALCULUL RDCINILOR REALE ALE ECUAIEI ALGEBRICEPentru calculul rdcinilor reale ale unei ecuaii algebrice se utilizeaz mai multe metode numerice dintre care amintim: metoda biseciei (bipartiiei), metoda aproximaiilor succesive, metoda lui Newton - Raphson, metoda lui Lobacevski i metoda lui Bairstow.

2.2.1. METODA BISECIEI (BIPARTIIEI)Fie funcia continu f : [a , b] R i ecuaia f ( x ) = 0 care are soluie unic pe intervalul [a , b] . Pentru condiiile date funcia satisface inecuaia f ( a ) f ( b) 0 . Se pune problema determinrii soluiei a ecuaiei f ( x ) = 0 pe intervalul [a , b] (fig. 2.1), cu o anumit eroare . Metoda const n a verifica dac a sau b sunt soluii ale ecuaiei f ( x ) = 0 . Dac a i b nu sunt soluii, se trece la njumtirea intervalului [a , b] i se determin valoarea xm = ( a + b) / 2 . Se verific dac xm este soluie a ecuaiei. Aceast verificare poate fi fcut prin compararea | f ( x m )| < sau compararea | bn a n | < , unde este eroarea de calcul a soluiei ecuaiei. Dac x m este soluie a ecuaiei, problema s-a rezolvat; n caz contrar se evalueaz f ( a ), f ( x m ) i se verific dac produsul f ( a ) f ( x n ) < 0. Dac inegalitatea este satisfcut

20

Metode numerice n electronic

b1 = x m i a = a1 i soluia se caut n intervalul [a1 , b1 ] . Dac inegalitatea nu este satisfcut, a1 = x m i b = b1 i soluia se afl n intervalul [a1 , b1 ] . Procedeul continu i se obin dou iruri convergente: unul monoton cresctor mrginit superior de b i altul monoton descresctor mrginit inferior de a : a < a1 < a2 b2 >...> bn >... (2.10) irul lungimilor intervalelor care se obin prin njumtire este: b1 a1 = (b a)/2 , b 2 a2 = (b a)/2 2 , ... , bn an = (b