Metode numerice pentru rezolvarea ecuat iilor algebrice

Octavian Cira 25 Octombrie 2005

Cuprins
Lista figurilor. . . . . . . . . . . . . . . . . . . . . . . . . . . IX Lista tabelelor . . . . . . . . . . . . . . . . . . . . . . . . . . XII Prefat a. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .XIII Capitolul 1. Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 1.1. Preliminarii. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Polinoamele cu coeficient i complec si . . . . . . . . . . . . . . Capitolul 2.

1.3. Polinoamele cu coeficient i reali . . . . . . . . . . . . . . . . . 15 Marginile r ad acinilor . . . . . . . . . . . . . . . . . . . . . . 22 2.1. Marginile r ad acinilor polinoamelor . . . . . . . . . . . . . . . 22 2.2. Polinoamelor cu coeficient i complec si . . . . . . . . . . . . . . 22 2.3. Polinoamelor cu coeficient i reali. . . . . . . . . . . . . . . . . 24 Capitolul 3. Metode clasice . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1. Metoda Ruffini . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.2. Metoda Lagrange . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3. Metoda Gr affe . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4. Metoda Bernoulli. . . . . . . . . . . . . . . . . . . . . . . . . 31 3.5. Metoda bisect iei . . . . . . . . . . . . . . . . . . . . . . . . . 34 Capitolul 4. Metode de separare . . . . . . . . . . . . . . . . . . . . . . . 36 4.1. Separarea r ad acinilor reale la polinoame cu coeficient i reali . . 36 4.2. Separarea r ad acinilor la polinoame cu coeficient i complec si . . 40 4.3. Convergent a metodei Lehmer-Schur . . . . . . . . . . . . . . 47 4.4. Evaluarea erorilor la metoda Lehmer-Schur . . . . . . . . . . 48 4.5. Noua metod a Lehmer-Schur . . . . . . . . . . . . . . . . . . . 48 4.6. Metoda Weyl . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.6.1. Simplific ari ale testului de proximitate. . . . . . . . . . . 60 4.6.2. Testul de proximitate Turan . . . . . . . . . . . . . . . . 61 4.6.3. Testul de proximitate Kakeya . . . . . . . . . . . . . . . 62

CUPRINS
Capitolul 5.

VI
Metode de factorizare . . . . . . . . . . . . . . . . . . . . . 65

5.1. Elemente de analiz a n -dimensional a . . . . . . . . . . . . . . 65 5.2. Metoda Lin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 5.3. Metode de factorizare de ordinul 2 . . . . . . . . . . . . . . . 72 5.3.1. Metoda Bairstow-Newton. . . . . . . . . . . . . . . . . . 72 5.3.2. Convergent a metodei Bairstow-Newton . . . . . . . . . . 75 5.3.3. Metoda Bairstow-secant a . . . . . . . . . . . . . . . . . . 78 5.3.4. Metoda Bairstow-Steffensen . . . . . . . . . . . . . . . . 81 5.3.5. Convegent a metodelor Bairstow-secant a si Bairstow-Steffensen . . . . . . . . . . . . . . . . . . . . . . 84 5.3.6. Metoda Bairstow-Fridman . . . . . . . . . . . . . . . . . 85 5.3.7. Convergent a metodei Bairstow-Fridman . . . . . . . . . . 86 5.3.8. Dimensiunea fractal a . . . . . . . . . . . . . . . . . . . . 92 5.4. Metode de factorizare de ordinul 3 . . . . . . . . . . . . . . . 95 5.4.1. Metoda Bairstow-Newton. . . . . . . . . . . . . . . . . . 95 5.4.2. Metoda Bairstow-secant a . . . . . . . . . . . . . . . . . . 100 5.4.3. Metoda Bairstow-Fridman . . . . . . . . . . . . . . . . . 104 Capitolul 6. Metode de tip Newton . . . . . . . . . . . . . . . . . . . . . 107 6.1. Convergent a local a . . . . . . . . . . . . . . . . . . . . . . . . 107 6.2. Metoda Newton . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.3. Metoda parabolei tangent a . . . . . . . . . . . . . . . . . . . 115 6.4. Metoda Ostrowski . . . . . . . . . . . . . . . . . . . . . . . . 117 6.5. Metoda parabolei osculatoare . . . . . . . . . . . . . . . . . . 119 6.6. Metoda parabolei . . . . . . . . . . . . . . . . . . . . . . . . 122 6.7. Metoda Laguerre . . . . . . . . . . . . . . . . . . . . . . . . . 126 6.8. Metoda Chebyshev de ordinul 1 . . . . . . . . . . . . . . . . . 128 6.9. Metoda Chebyshev de ordinul 2 . . . . . . . . . . . . . . . . . 130 6.10. Metoda Halley . . . . . . . . . . . . . . . . . . . . . . . . . 132 6.11. Familie de metode . . . . . . . . . . . . . . . . . . . . . . . 134 6.12. Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 Capitolul 7. Metode multipas . . . . . . . . . . . . . . . . . . . . . . . . 136 7.1. Metoda coardei. . . . . . . . . . . . . . . . . . . . . . . . . . 136 7.2. Metoda secantei . . . . . . . . . . . . . . . . . . . . . . . . . 142 7.3. Metoda Steffensen . . . . . . . . . . . . . . . . . . . . . . . . 144 7.4. Metoda Muller . . . . . . . . . . . . . . . . . . . . . . . . . . 147

VII
Capitolul 8.

CUPRINS
Metode simultane . . . . . . . . . . . . . . . . . . . . . . . . 149

8.1. Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 8.2. Metoda Durand-Kerner . . . . . . . . . . . . . . . . . . . . . 152 8.3. Metoda Ehrlich-Aberth . . . . . . . . . . . . . . . . . . . . . 155 8.4. Metoda Ehrlich-Aberth cu factori de corect ie Newton . . . . . 159 8.5. Metoda B orsch-Supan . . . . . . . . . . . . . . . . . . . . . . 160 8.6. Metoda B orsch-Supan cu factori de corect ie Weierstrass . . . 162 8.7. Metoda Tanabe . . . . . . . . . . . . . . . . . . . . . . . . . 163 8.8. Metoda r ad acinii p atrate . . . . . . . . . . . . . . . . . . . . 166 8.9. Metoda Wang-Zheng . . . . . . . . . . . . . . . . . . . . . . . 167 8.10. Noua metod a Newton . . . . . . . . . . . . . . . . . . . . . 169 8.11. Familie de metode . . . . . . . . . . . . . . . . . . . . . . . 176 Capitolul 9. Teoria estim arii punctului . . . . . . . . . . . . . . . . . . . 178 9.1. Estim ari ale punctului pentru metoda Newton . . . . . . . . . 178 9.2. Estim ari ale punctului pentru metode cu convergent a 2 . . . . 194 9.3. Estim ari ale punctului pentru metode cu convergent a 3 . . . . 197 9.4. Dezvolt ari ale estim arii punctului pentru metoda Newton. . . 201 9.5. Metode mixte . . . . . . . . . . . . . . . . . . . . . . . . . . 209 9.5.1. Metoda Lehmer-Schur-Newton . . . . . . . . . . . . . . . 209 9.5.2. Metoda Lehmer-Schur-Euler-Chebyshev . . . . . . . . . . 213 9.5.3. Metoda Lehmer-Schur-Halley. . . . . . . . . . . . . . . . 214 9.6. Estimarea punctului pentru metoda Durand-Kerner . . . . . . 214 Capitolul 10. Metode simultane de incluziune . . . . . . . . . . . . . . . 231 10.1. Elemente de algebr a liniar a . . . . . . . . . . . . . . . . . . 231 10.1.1. Polinom caracteristic . . . . . . . . . . . . . . . . . . . 231 10.1.2. Valori si vectori proprii . . . . . . . . . . . . . . . . . . 232 10.1.3. Discuri de incluziune. . . . . . . . . . . . . . . . . . . . 236 10.1.4. Intervalul complex aritmetic . . . . . . . . . . . . . . . 244 10.2. Teorema general a de convergent a . . . . . . . . . . . . . . . 248 10.3. Metoda Durand-Kerner. . . . . . . . . . . . . . . . . . . . . 253 10.4. Metoda B orsch-Supan . . . . . . . . . . . . . . . . . . . . . 264 10.5. Metoda Tanabe . . . . . . . . . . . . . . . . . . . . . . . . . 273 10.6. Familie de metode . . . . . . . . . . . . . . . . . . . . . . . 280 10.7. Metoda Ehrlich-Aberth. . . . . . . . . . . . . . . . . . . . . 292 10.8. Metoda Ehrlich-Aberth cu corect ii cu factori Newton . . . . 302 10.9. Metoda B orsch-Supan cu corect ii cu factori Weierstrass . . . 312

CUPRINS

VIII
10.10. Metoda Wang-Zheng . . . . . . . . . . . . . . . . . . . . . 324 10.11. Metode de tip Halley . . . . . . . . . . . . . . . . . . . . . 340 10.12. Condit ia general a de convergent a . . . . . . . . . . . . . . . 361

Capitolul 11. Metode pentru polinoame cu zerouri multiple . . . . . . 365 11.1. Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 11.2. Metode de incluziune ce au la baz a polinoamele Bell . . . . . 368 11.3. Metoda de incluziune Newton . . . . . . . . . . . . . . . . . 373 11.4. Metoda de incluziune Wang-Zheng . . . . . . . . . . . . . . 386 11.5. Metoda simultan a Ehrlich-Kjurkchiev . . . . . . . . . . . . . 400 Capitolul A. Bibliografia McNamee . . . . . . . . . . . . . . . . . . . . . 404 A.1. Metodele Bernoulli si QD . . . . . . . . . . . . . . . . . . . . 404 A.2. Metoda Graeffe . . . . . . . . . . . . . . . . . . . . . . . . . 410 A.3. Metoda Lehmer . . . . . . . . . . . . . . . . . . . . . . . . . 416 A.4. Metodele Lin si Bairstow . . . . . . . . . . . . . . . . . . . . 420 A.5. Metoda Newton . . . . . . . . . . . . . . . . . . . . . . . . . 425 A.6. Metode simultane . . . . . . . . . . . . . . . . . . . . . . . . 446 A.7. Metode de incluziune . . . . . . . . . . . . . . . . . . . . . . 455 Capitolul B. Indexuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 B.1. Index de notat ii . . . . . . . . . . . . . . . . . . . . . . . . . 461 B.2. Index de subiecte . . . . . . . . . . . . . . . . . . . . . . . . 462 B.3. Index de nume . . . . . . . . . . . . . . . . . . . . . . . . . . 468 Bibliografie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470 Contents. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485

Lista figurilor
Figura 1.1: Coroana C (0, k, K ). . . . . . . . . . . . . . . . . . . . . . . . . . . . Figura 1.2: Coroana C (0, m2 , M2 ). . . . . . . . . . . . . . . . . . . . . . . . . . Figura 1.3: Discurile de raz aR si R . . . . . . . . . . . . . . . . . . . . . . . . . 5 6 8

Figura 1.4: Exemple pentru programul Schur. . . . . . . . . . . . . . . . . . . . 12 Figura 1.5: Grace pentru programul Schur(Comp).. . . . . . . . . . . . . . . . 14 Figura 1.6: V (m1 M1 (c)T , Sturm(c, 1012 )) = 3. . . . . . . . . . . . . . . . . . . 21 Figura 1.7: V (m2 M2 (c)T , Sturm(c, 1012 )) = 3. . . . . . . . . . . . . . . . . . . 21 Figura 1.8: V (Kakeya(c)T , Sturm(c, 1012 )) = 3. . . . . . . . . . . . . . . . . . 21 Figura 2.1: Coroana C (0, m, M ) determinat cu algoritmul Alg1. . . . . . . . . . 24 Figura 2.2: Coroana C (0, m, M ) pentru algoritmul Alg2. . . . . . . . . . . . . . 25 Figura 4.1: Coroana C (0, m, M ) pentru algoritmul Alg3. . . . . . . . . . . . . . 39 Figura 4.2: Acoperirea coroanei circulare cu discuri.. . . . . . . . . . . . . . . . 41 Figura 4.3: Suprafat a util a din discul de acoperire. . . . . . . . . . . . . . . . . 42 Figura 4.4: Gracul funct iei 4.4. . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Figura 4.5: Gracul descre sterii razelor discurilor de acoperire. . . . . . . . . . . 48 Figura 4.6: Graficul erorilor absolute. . . . . . . . . . . . . . . . . . . . . . . . 49 Figura 4.7: Graficul funct iei 4.5.1. . . . . . . . . . . . . . . . . . . . . . . . . . 49 Figura 4.8: Acoperirea C (0, 1.5r, r) cu 12 discuri. . . . . . . . . . . . . . . . . . 50 Figura 4.9: Graficul erorilor absolute. . . . . . . . . . . . . . . . . . . . . . . . 54 Figura 4.10: Algoritmul Weyl.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Figura 5.1: Bazinul de atract ie al r ad acinii x = 5. . . . . . . . . . . . . . . . . 72 Figura 5.2: Bazinele de atract ie pentru metoda B-N. . . . . . . . . . . . . . . . 78 Figura 5.3: Bazinele de atract ie pentru metoda B-N n sect iunea p = 1. . . . . 79 Figura 5.4: Bazinele de atract ie pentru metoda B-s. . . . . . . . . . . . . . . . . 82

IX

LISTA FIGURILOR

Figura 5.5: Bazinele de atract ie pentru metoda B-S. . . . . . . . . . . . . . . . 84 Figura 5.6: Bazinele de atract ie pentru metoda Baistow-Fridman. . . . . . . . . 86 Figura 5.7: Descompunere n triunghiuri.. . . . . . . . . . . . . . . . . . . . . . 93 Figura 6.1: Metoda Newton n R1 . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Figura 6.2: Bazinele de atract ie pentru contract ia z P (z )/P z ) . . . . . . . . . 113 Figura 6.3: Bazinele de atract ie pentru MN. . . . . . . . . . . . . . . . . . . . . 114 Figura 6.4: Bazinele de atract ie pentru MTP. . . . . . . . . . . . . . . . . . . . 117 Figura 6.5: Bazinele de atract ie pentru MO. . . . . . . . . . . . . . . . . . . . . 119 Figura 6.6: Bazinele de atract ie pentru MOP. . . . . . . . . . . . . . . . . . . . 121 Figura 6.7: Gracul funct iei |f (z )|. . . . . . . . . . . . . . . . . . . . . . . . . . 123 Figura 6.8: Metoda MP n R1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Figura 6.9: Bazinele de atract ie pentru MP. . . . . . . . . . . . . . . . . . . . . 126 Figura 6.10: Bazinele de atract ie pentru MC1. . . . . . . . . . . . . . . . . . . . 129 Figura 6.11: Bazinele de atract ie pentru MC2. . . . . . . . . . . . . . . . . . . . 131 Figura 6.12: Bazinele de atract ie pentru MH. . . . . . . . . . . . . . . . . . . . 133 Figura 7.1: Metoda coardei. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Figura 7.2: Monotonia sirului generat de metoda coardei.. . . . . . . . . . . . . 139 Figura 7.3: Aplicarea metodei coardei. . . . . . . . . . . . . . . . . . . . . . . . 140 Figura 7.4: Metoda secantei. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Figura 7.5: Bazinele de atract ie pentru metoda secantei. . . . . . . . . . . . . . 144 Figura 7.6: Metoda Steffensen. . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Figura 9.1: Testul cu valoarea S (8).. . . . . . . . . . . . . . . . . . . . . . . 193 Figura 9.2: Testul cu valoarea W . . . . . . . . . . . . . . . . . . . . . . . . . 194 Figura 9.3: Funct ia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 Figura 9.4: Graficul condit iei (9.40). . . . . . . . . . . . . . . . . . . . . . . . . 222 Figura 9.5: Graficul condit iei (9.41). . . . . . . . . . . . . . . . . . . . . . . . . 222 Figura 10.1: Discuri Smith. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 Figura 10.2: Discuri Braess-Hadeler. . . . . . . . . . . . . . . . . . . . . . . . . 238 Figura 10.3: Discuri Gerschgorin. . . . . . . . . . . . . . . . . . . . . . . . . . . 243 Figura 10.4: Funct ile g si 1/(2(n)). . . . . . . . . . . . . . . . . . . . . . . . . 258 Figura 10.5: Funct ia si . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 Figura 10.6: Funct iile f si . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 Figura 10.7: Funct iile h, f si g . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285

XI

LISTA FIGURILOR

Figura 10.8: Funct iile h si f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 Figura 10.9: Funct ia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 Figura 10.10: Funct iile h si . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 Figura 10.11: Funct ile si . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 Figura 10.12: Funct ile si . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 Figura 10.13: Funct ile si .. . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 Figura 10.14: Funct ile si . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 Figura 10.15: Funct ile h si h . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 Figura 10.16: Funct ia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 Figura 11.1: Discul de incluziune D(a,R). . . . . . . . . . . . . . . . . . . . . . 386

Lista tabelelor
Tabelul 1.1: Variat ia semnului c and Q este cresc ator. . . . . . . . . . . . . . . . 16 Tabelul 1.2: Variat ia semnului c and Q este descresc ator. . . . . . . . . . . . . . 16 Tabelul 1.3: Variat ia funct iei V . Cazul 1. . . . . . . . . . . . . . . . . . . . . . 18 Tabelul 1.4: Variat ia funct iei V . Cazul 2. . . . . . . . . . . . . . . . . . . . . . 18 Tabelul 1.5: Variat ia funct iei V . Cazul 3. . . . . . . . . . . . . . . . . . . . . . 19 Tabelul 1.6: Variat ia funct iei V . Cazul 4. . . . . . . . . . . . . . . . . . . . . . 19 Tabelul 5.1: Dimensiunea fractal a. . . . . . . . . . . . . . . . . . . . . . . . . . 95 Tabelul 6.1: Dimensiunea fractal a pentru metode cu convergent a p atratic a. . . . 135 Tabelul 6.2: Dimensiunea fractal a pentru metode cu convergent a cubic a. . . . . 135 Tabelul 9.1: Intervale [0, rn ). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 Tabelul 9.2: Valorile constantei S (n). . . . . . . . . . . . . . . . . . . . . . . . 191 Tabelul 9.3: Convergent a p atratic a a metodei MN. . . . . . . . . . . . . . . . . 192 Tabelul 9.4: Valorile 1 (n). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 Tabelul 9.5: Testul 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 Tabelul 10.1: R ad acinile pozitive ale ecuat iei xn x 3 = 0. . . . . . . . . . . . 342

XII

Prefat a
Studiul r ad acinilor polinoamelor algebrice a fost unul din cele mai prolifice subiecte n istoria milenar a a matematicii. Determinarea valorii pentru care polinomul algebric se anuleaz a a fost n atent ia a mii de matematicieni. John Michael McNamee a publicat o bibliografie pe aceast a tem a n patru edit ii [110], [111], [112] si [113], ultima cont ine cont ine 32 de capitole n cadrul a peste 300 de pagini, av and aproximativ 10 000 de titluri, unde apar doar rezultatele publicate n limbile de larg a circulat ie internat ional a (englez a, fracez a si german a), n reviste si edituri de prestigiu. O lucrarea de referint a pentru tema prezentat a n aceast a carte este volumul VIII, Numerical Solution of Polynomial Equations din seria Handbook of Numerical Analysis [161], tip arit a sub egida Elsevier Science. Teoria matematic a a ecuat iilor algebrice este un capitol ncheiat al algebrei nc a de la sf ar situl secolului al XVIII-lea odat a cu demonstrarea, de c atre Gauss (1799), a teoremei fundamentale a algebrei. A r amas deschis a problema determin arii practice a solut iilor ecuat iilor algebrice. Odat a cu ideea genial a a lui Isac Newton (1669) [116] de a aproxima r ad acina unui polinom cu punctul de intersect ie al tangentei cu axa OX, s-a deschis o nou a cale de determinare a solut iilor ecuat iilor. Niels Abel a demonstrat (1826) c a formulele de calcul a r ad acinilor cu radicali pot fi folosite numai pentru ecuat ii algebrice de grad cel mult 4. Din acest moment era clar c a determinarea solut iilor ecuat iilor algebrice de grad mai mare dec at 4 se va putea face numai cu metode de aproximare. Multe cercet ari au fost efectuate pentru a determina marginile r ad acinilor polinoamelor. Exist a o multitudine de constante care majoreaz a si, respectiv, minoreaz a marginea superioar a si marginea inferioar a ale r ad acinilor polinomului. In cele mai multe cazuri majorarea sau minorarea este grosier a. Prezent am, n aceast a carte, algoritmi de determinare a unui majorant si, respectiv, minorant ce aproximeaz a marginile superioar a si, respectiv, inferioar a a r ad acinilor polinomului cu o precizie dat a [31]. Problema are important a ei pentru c a permite delimitarea c at mai exact a XIII

Capitolul 0. Prefat a

XIV

a coroanei circulare n care se g asesc toate r ad acinile complexe si segmentele de pe axa real a care cont in toate r ad acinile reale. Mult i matematicieni au considerat metode noi pentru aproximarea solut iilor ecuat iilor algebrice: Bernoulli [55], [81], Sturm [171], Euler si Chebyshev [158], Laguerre [100], Weierstrass [185], Bairstow [10], Muller [115], Lehmer [102], Docev [49], Durand [50], B orsch-Supan [13], [14], Kerner [87], Ehrlich [51], Jenkins si Traub [83], Aberth [3], Halley [68], [158], [97], [11], Tanabe [174], Wang si Zheng [182] etc. Incep and cu anul 1937, Ostrowski [122] public a mai multe articole prin care demonstreaz a convergent a local aa metodei Newton n cazul funct iilor de o variabil a real a. Rezultatul lui Kantorovich din 1948 [85], care demonstreaz a convergent a p atratic a a metodei Newton n spat ii generale Banach, este fundamental. Acest rezultat domin a literatura de specialitate, ap ar and mii de articole pe aceast a tem a. Dup a modelul dat de Kantorovich, trei probleme se pun n leg atur a cu metodele de aproximare a r ad acinilor polinomului: convergent a, ordinul de convergent a si estimarea erorii. Pe l ang a aceste direct ii de cercetare referitor la metodele numerice pentru ecuat iile algebrice, exit a multe alte teme de interes. Problematica stabilit a tii Routh-Hurwitz a metodelor numerice [76], [155] este, ncep and cu secolul XX, o problem a intens studiat a judec and dup a impresionanta bibliografie [113, capitolul Stability Questions (criteriul Routh-Hurwitz etc.)] pe aceast a tem a. Bairstow [10] a considerat o metod a de factorizare a polinoamelor n termeni de ordinul 2. Metoda Bairstow s-ar putea chema Bairstow-Newton pentru c a sistemul neliniar ce intervine n deducerea procesului iterativ este rezolvat cu metoda Newton. In aceast a carte vom prezenta metode de tip Bairstow de ordinul 2 si 3 pentru factorizarea polinomului care au fost numite Bairstow-secant a, Bairstow-Steffensen, Bairstow-Fridman [28], [29], [30], dup a cum pentru deducerea procesului iterativ, ce se face prin rezolvarea unui sistem neliniar de ordinul doi sau trei, s-a folosit metoda secantei, metoda Steffensen [170] sau metoda Fridman [60]. Mult mai t arziu s-a pus problema iterat iei de start, de aici rezult and problema bazinelor de atract ie a metodelor [32], [33], [34], [45], [40]. Foarte interesant este faptul c a bazinele de atract ie pentru metode de tip Newton au o str ans a leg atur a cu teoria Fatou-Julia a fractalilor sau mai bine zis a atractorilor. Aceast a observat ie s-a f acut n anul 1985 c and s-a reprezentat prima dat a grafic mult imea punctelor, dintr-un p atrat, din care metoda Newton converge pentru ecuat ia z 3 1 = 0 [54]. Algoritmul Lehmer-Schur [102] este o metod a de separare a r ad acinilor polinomului cu coeficient i complec si, care are un neajuns importat, cu c at o

XV r ad acin a este separat a mai t arziu, cu at at cre ste incertitudinea fat a de precizia separ arii. Vom prezenta o variant a proprie a acestei metode care evit a acest neajuns [31]. Metoda Weyl [127] este o metod a de separare, fiind o generalizare a algoritmului de bisect ie din R, n planul complex, unde intervalul complex este considerat p atratul. Metoda Weyl, cunoscut a si sub denumirea de construct ia Quadtree [125], este una din metodele cu cea mai mic a complexitatea a calculului, fapt ce face s a fie un algoritm foarte atr ag ator. In 1981 Smale [167] define ste not iunea de zero aproximativ, not iune care st a la baza teoriei estim arii punctului [141]. Aceast a teorie permite definirea apriori a bazinelor de atract ie pentru solut iile ecuat iei algebrice n funct ie de metoda folosit a. Se remarc a dezvoltarea deosebit a a metodelor simultane de determinare a tuturor r ad acinilor ecuat iei algebrice [50], [49], [13], [87], [51], [3], [174], [182] etc. In leg atur a cu aceste metode s-au dezvoltat metodele de incluziune care folosesc o aritmetic a a intervalului complex si discurile de incluziune Gerschgorin [53], unde intervalul complex este discul. O lucrare fundamental a pentru metodele de incluziune o dator am lui Petkovi c [133], acela si autor n anul 2002 elaboreaz a o lucrare de sintez a ce cuprinde ultimele rezultate referitoare la metodele de incluziune [137]. La ora actual a se fac eforturi importante n direct ia paraleliz arii algoritmilor si a folosirii calculelor n precizii extinse pentru a rezolva ecuat ii cu grad mare (> 100) si a obt ine r ad acini cu precizii nalte. Nu este necesar s a avem un polinom de grad mare pentru a avea probleme de determinare a r ad acinilor cu o acuratet e mare, este suficient un polinom r au condit ionat sau cu r ad acini multiple pentru ca s a avem dificult a ti de determinare a r ad acinilor. Sunt interesante metodele mixte, n care se combin a o metod a de separare a r ad acinilor, n faza init ial a a algoritmului, cu o metod a rapid convergent a, n partea a doua a algoritmului. La aceste metode este important criteriul prin care renunt am la metoda de separare si lu am n considerare metoda rapid convergent a. Teoria estim arii punctului joac a un rol hot ar ator din acest punct de vedere [35], [41], [39], [36], [38]. Datorit a dezvolt arii tehnologice hard si soft s-a ajus la performant e remarcabile. Determinarea tuturor r ad acinilor pentru ecuat iile algebrice de grad 99 nu mai constituie o problem a de timp CPU si acuratet e de determinare. La ora actual a exist a pachete de calcul stiint ific (Mathcad [104], [37], [44], Matematica, Maple, Matlab, . . . ), sau biblioteci de programe stiint ifice (IMSL [1], NAG [2], DROOTS, . . . ) care furnizeaz a funct ii sau programe de rezolvare a ecuat iilor algebrice de grad mare cu precizii de 15, 24 sau 32 de cifre zecimale. Apel and la calculul simbolic se pot furniza r ad acini exacte sau cu un num ar mare de zecimale exacte (100250 cifre zecimale). Pentru a vedea ultimele probleme referitoare la r ad acinile polinoamelor se poate consulta excelentul

Capitolul 0. Prefat a

XVI

articol a lui Burgnano si Trigiante [18]. In aceast a carte se prezint a peste 50 de metode de aproximare a r ad acinilor ecuat iilor algebrice, unde s-au avut n vedere construct ia metodei, convergent a, ordinul de convergent a, estimarea erorii, bazinele de atract ie ale metodei, iar n unele cazuri s-au f acut referiri si la complexitatea calculului. Rezultatele teoretice sunt urmate de prezentarea algoritmilor, a programelor si a exemplelor rezolvate. Toate exemplele si programele au fost realizate n Mathcad 2001 [37], [44]. Consider am c a aceast a carte cont ine multe programe ce pot constitui un suport de nv a tare a program arii n Mathcad. In exemplele date s-au preferat polinoame cu r ad acini numere ntregi sau cu r ad acini complexe ce au partea real a si partea imaginar a ntreag a pentru a se evident ia u sor erorile de aproximare. Cartea se adreseaz a programatorilor, cercet atorilor, cadrelor didactice din nv a t am antul superior, student iilor care sunt familiarizat i cu analiza numeric a. Se prezint a suportul teoretic pentru metodele numerice si algoritmii ce stau la baza programelor performante de rezolvare numeric a a ecuat iilor algebrice. Demonstrat iile teoremelor si propozit iilor, n multe cazuri, nu pot fi parcurse si verificate f ar a a avea la ndem an a un soft (Mathcad, Maple, Matematica, Scientific Word, ...) ce asigur a calcul simbolic si rutine pentru rezolvarea ecuat ilor algebrice, pentru a verifica calcule complexe si a rezolva ecuat ii algebrice de grad mare. Consider am c a acest fapt este o noutate important a n literatura stiint ific a din Rom ania. Autorul det ine toate documentele Mathcad versiunea 11.0 (148 de siere MCD si un sier [Link]) pentru demonstrat iile n detaliu a teoremelor si propozit iilor prezentate, acestea pot fi accesate de pe CD-ul ata sat c art ii. Mult umesc tuturor celor care au fost al aturi de mine pentru scrierea acestei c art i. Arad, 08 Februarie 2005 Autorul

Bibliograe
[1] ***. IMSL Users Manual, 1987. Version 1.0, chapter 7. [2] ***. NAG Fortran Library Manual, volume 1. Mark 13, 1988. [3] O. Aberth. Iteration methods nding all zeros of polynomial simultaneously. Math. Comp., 27:339344, 1973. [4] F. S. Acton. Numerical Methods that Work. Harper and Row, New York, 1970. [5] A. C. Aitken. On the factorization of polynomials by iterative methods, chapter Studies in Practical Mathematics VI, pages 174191. Proc. Roy. Soc. Edinburgh 63, 1951. [6] A. C. Aitken. On the theory of methods of factoring polynomials by iterated division, chapter Studies in Practical Mathematics VII, pages 326335. Proc. Roy. Soc. Edinburgh 63, 1952. [7] A. C. Aitken. Note on the acceleration of lins process of iterated penultimate remainder. Quart. J. Mech. Appl. Math., 8:251258, 1955. [8] A. C. Aitken. On the the iterative methods of Lin and Fridman for factorizing polynomials, chapter Studies in Practical Mathematics VIII, pages 190199. Proc. Roy. Soc. Edinburgh 64, 1956. [9] G. Alefeld and J. Herzberger. Introduction to Interval Computation. Academic Press, New York, 1983. [10] L. Bairstow. Investigations Relating to the Stability of the Aeroplane, pages 5164. Reports and Memoranda No 154 of Advisory Committee for Aeronautics, 1914. [11] H. Bateman. Halleys methods for solving equations. Amer. Math. Monthly, 45:1117, 1938. [12] E. T. Bell. Exponential polynomials. Math. Ann., 35:258277, 1934. 470

471

BIBLIOGRAFIE

rsch-Supan. A posteriori error bounds for the zeros of polyno[13] W. Bo mials. Numer. Math., 5:380398, 1963. rsch-Supan. Reiduenabsch [14] W. Bo atzung fur Polynom nullstellen mittels Lagrange-Interpolation. Numer. Math., 14:287296, 1970. [15] D. Braess and K. P. Hadeler. Simultaneous inclusion of the zeros of polynomial. Numer. Math., 21:161165, 1973. nescu and O. Sta na . Matematici speciale. Ed. All, [16] V. Br nza sila Bucure sti, a II-a edit ie, 1998. [17] L. Brugnano. Numerical implementation of a new algorithm for polynomials with multiple roots. Journal of Difference Equations and Applications, 1:187207, 1995. [18] L. Brugnano and D. Trigiante. Polynomial roots: the ultimate answer? Linear Algebra Appl., 225:207219, 1995. [19] C. Carstensen. Anwendungen von Begleitmatrizen. Z. Angew. Math. Mech., 71:809812, 1991. [20] C. Carstensen. Inclusion of the roots of a polynomial based on Gerschgorins theorem. Numer. Math., 59:349360, 1991. [21] C. Carstensen. On quadratic-like convergence of the means for two methods for simultaneous rootfinding of polynomials. BIT, 33:6473, 1993. . On iteration methods without [22] C. Carstensen and M. S. Petkovic derivatives for the simultaneous determination of polynomial zeros. J. Comput. Appl. Math., 45:251266, 1993. [23] J. L. Chabert. Methods of False Position Ch. 3 in A History of Algorithms: From the Pebble to the Microchip. Springer-Verlag, New York, 1999. pp. 83-112. [24] C. F. Chen and M. M. Chen. Performing Lins method via Routh-type algorithms or Hurwitz-type determinants. Proc. IEEE, 68:14471449, 1980. [25] C. F. Chen and M. H. Lin. A generalization of Lins method for polynomial factorization. J. Franklin Inst., 326:849860, 1989. [26] P. Chen. Approximate zeros of quadratically convergent algorithms. Math. Comp., 63:247270, 1994.

BIBLIOGRAFIE

472

[27] O. Cira. Algorithm for the simultaneous determination of all real zeros of the polynomial from R[x]. In Proceedings of the third Symposium of Mathematics and its Applications, pages 233242. Timi soara Research of the Rom ania Academy and Politehnica University of Timi soara, 3-4 November 1989. [28] O. Cira. Metoda Bairstow. In Proceedings of the fifth Symposium of Mathematics and its Applications, pages 5764. Timi soara Research of the Rom ania Academy and Politehnica University of Timi soara, 29-30 October 1993. [29] O. Cira. Bairstow methods of order 3. In Proceedings of the Seventh Symposium of Mathematics and its Applications, pages 7984. Timi soara Research of the Rom ania Academy and Politehnica University of Timi soara, 6-9 November 1997. [30] O. Cira. Iterative methods for the determination of polynomial factors. In Bulletins for Applied and Computing Mathematics, Pannonian Applied Mathematical Meetings, Interuniversity Network in Central Europe, number 1494 in BAM, pages 183190. Caretaken by the PAMM-Centre at the Technical University of Budapest, September 1998. [31] O. Cira. Rezolvarea numeric a a ecuat iilor algebrice. PhD thesis, West University of Timi soara, 1998. [32] O. Cira. The attraction basins for iterative method. In Proceedings of the Eighth Symposium of Mathematics and its Applications, pages 3946. Timi soara Research of the Rom ania Academy and Politehnica University of Timi soara, 4-7 November 1999. [33] O. Cira. Convergence domain of the iterative methods. In Bulletins for Applied and Computing Mathematics, Pannonian Applied Mathematical Meetings, Interuniversity Network in Central Europe, number 1630 in BAM, pages 124132. Caretaken by the PAMM-Centre at the Technical University of Budapest, January 1999. [34] O. Cira. Numerical experiments for convergence domain. In Bulletins for Applied and Computing Mathematics, Pannonian Applied Mathematical Meetings, Interuniversity Network in Central Europe, number 1646 in BAM, pages 129146. Caretaken by the PAMM-Centre at the Technical University of Budapest, August 1999. [35] O. Cira. Algoritmul Lehmer-Schur-Newton de rezolvare a ecuat iilor algebrice. In Conferint a de Informatic a Teoretic a si Tehnologii Informatice, Tehnologii informatice pentru anii 2000. pag. 21-28. Facultatea

473

BIBLIOGRAFIE de Matematic a si Informatic a a Universit a tii Ovidius din Constant a si Institutul Nat ional de Cercetare-Dezvoltare n Informatic a din Bucure sti, 25-27 May 2000.

[36] O. Cira. Approximate zeros of algebraic polynomials with higer convergence order mixture methods. In Bulletins for Applied and Computing Mathematics, Pannonian Applied Mathematical Meetings, Interuniversity Network in Central Europe, number 1732 in BAM, pages 2736. Caretaken by the PAMM-Centre at the Technical University of Budapest, June 2000. [37] O. Cira. Lect ii de Mathcad. Ed. Albastr a, Cluj-Napoca, 2000. [38] O. Cira. Lehmer-Schur-Euler-Chebyshev method for approximation all zeros of algebraic polynomials. In Bulletins for Applied and Computing Mathematics, Pannonian Applied Mathematical Meetings, Interuniversity Network in Central Europe, number 1773 in BAM, pages 4756. Caretaken by the PAMM-Centre at the Technical University of Budapest, August 2000. [39] O. Cira. Lehmer-Schur-Newton algorithm for solving the algebraic equation. In Bulletins for Applied and Computing Mathematics, Pannonian Applied Mathematical Meetings, Interuniversity Network in Central Europe, number 1723 in BAM, pages 6978. Caretaken by the PAMM-Centre at the Technical University of Budapest, April 2000. [40] O. Cira. Numerical experiments on attraction basin. Advanced Modeling and Optimization (AMO), 2(3):122134, 2001. [41] O. Cira. Polyzeros-hybdrid method for algebraic equations solving. In Symbolic and Numeric Algorithms for Scientific Computing SYNACS 01, number 01-20 in RISC-Linz Report Series, pages 182196. Research Institute for Symbolic Computation, Johannes Kepler University of Linz, Austria and West University of Timi soara, 2-5 October 2001. [42] O. Cira. Some new aspects regarding the parabola method. In Bulletins for Applied and Computing Mathematics, Pannonian Applied Mathematical Meetings, Interuniversity Network in Central Europe, number 1854 in BAM, pages 153164. Caretaken by the PAMM-Centre at the Technical University of Budapest, May-June 2001. [43] O. Cira. Parabola method-polynomial rootfinder. In Symbolic and Numeric Algorithms for Scientific Computing SYNACS 02, RISC-Linz

BIBLIOGRAFIE

474

Report Series, pages 7688. Research Institute for Symbolic Computation, Johannes Kepler University of Linz, Austria and West University of Timi soara, 09-12 October 2002. [44] O. Cira. Lect ii de Mathcad 2001 Professional. Ed. Albastr a, ClujNapoca, 2003. [45] O. Cira and D. Bucerzan. Graphics reprezentation of attraction basins for iterative method of approximating the roots to nonlinear equations. In Symbolic and Numeric Algorithms for Scientific Computing SYNACS 2000, number 01-20 in RISC-Linz Report Series, pages 6972. Research Institute for Symbolic Computation, Johannes Kepler University of Linz, Austria and West University of Timi soara, 4-6 October 2000. [46] J. H. Curry. On zero nding methods of higher order from data at one point. J. Complexity, 5:219237, 1989. [47] J. C. Daubisse. Sur une m ethode de r esolution numerique d equations alg ebriques en particulier dans le cas de racines multiples, volume Fak. Ser. Mat. Fiz. of 498-541, pages 163166. Univ. Beograd Publ., 1975. [48] B. P. Demidovich and I. A. Maron. Computational Mathematics. Mir Publishers, Moscow, 1976. [49] K. Docev. An alternative method of Newton for simultaneous calculation of all the roots of a given algebraic equation ( n bulgar a). Phys. Math. J. Bulgar. Acad. Sci., 5(2):136139, 1962. [50] I. E. Durand. Solutions Num erique des Equations Alg ebriques. Equations du Type F(x)=0; Racines dune Polyn ome, volume 1, pages 279 281. Masson, Paris, 1960. [51] L. W. Ehrlich. A modified Newton method for polynomials. Comm. ACM, 10:107108, 1967. [52] G. H. Ellis and L. T. Watson. A paralell algorithm for simple roots of polynomials. Comput. Math. Appl., 2:107121, 1984. [53] L. Elsner. Remark on simultaneous inclusion of the zeros of a polynomial by Gerschgorins theorem. Numer. Math., 21:425427, 1973. [54] B. Epureanu and H. Greenside. Fractal basins of attraction associated with a damped Newtons method. SIAM Rev., 40(1):102109, March 1998. [55] L. Euler. Introductio in Analysii Infinitorum, volume 1, Chapter 17. Berlin, 1748.

475

BIBLIOGRAFIE

[56] K. Falconer. Fractal Geometry. Mathematical Foundation and Applicationa. John Wiley and Sons, 1990. [57] W. H. Flannery, S.A. Teukolsky, and W. T. Vetterling. The Art of Scientific Computing. Cambridge University Press, Cambridge, 2 edition, 1992. [58] J. B. J. Fourier. Oeuvres de Fourier, volume II, pages 249250. Gauthier-Villars, Paris, 1890. [59] P. Fraigniaud. The Durand-Kerner polynomial root finding method in case of multiple roots. BIT, 31:112123, 1991. [60] A. M. Fridman. Proceduri iterative cu eroare minim a pentru ecuat ii operatoriale neliniare ( n rus a). Dokl. Acad. Nauk., 139:10631066, 1960. [61] M. Frontini and E. Sormani. Modified Newtons method with third-order convergence and multiple roots. J. Comp. Appl. Math., 156(2):345354, 15 July 2003. [62] I. Gargantini. Parallel Laguerre iterations: Complex case. Numer. Math., 26:317323, 1976. [63] I. Gargantini. Further application of circular arithmetic: Schr oder-like algorithms with error bound for finding zeros of polynomials. SIAM J. Numer. Anal., 15:497510, 1978. [64] I. Gargantini and P. Henrici. Circular arithmetic and the determination of polynomial zeros. Numer. Math., 18:305320, 1972. [65] S. K. Godunov and V. S. Reabenki. Scheme de calcul cu diferent e finite. Editura Tehnic a, Bucure sti, 1977. [66] G. H. Golub and T. N. Robertson. A generalized Bairstow algorithm. Communications of the ACM, 10(6):371373, June 1967. [67] W. Gregg and R. Tapia. Optimal error bounds for Newton-Kantorovich theorem. SIAM J. Numer. Anal., 11:1013, 1974. [68] E. Halley. A new, exact, and easy method of nding the roots of any equations generally, and that without any previous reduction ( n latin a). Philos. Trans. Roy. Soc. London, 18:136148, 1694. [69] E. Hansen and M. Patrick. A family of root nding methods. Numer. Math., 27:257269, 1977.

BIBLIOGRAFIE

476

[70] P. Henrici. Applied and Computational Complex Analysis. John Wiley, New York, 1974. [71] P. Henrici. Applied and Computational Complex Analysis, volume I. John Wiley and Sons, New York, 1977. [72] D. Herceg. An algorithm for localization of polynomial zeros, volume Proc. of VIII Conference on Logic and Computer Science Lira97, pages 6775. Eds. R. To si c and Z. Budimac, Institute of Mathematics Novi Sad, September 1-4 1997. [73] J. Hertzberger and L. Metzner. On the Q-order and R-order of convergence for coupled sequences arising in iterative numerical processes, volume Mathematical Research, Vol. 89, chapter Numerical methods and error bounds, pages 120131. Akademie Verlang, Berlin, Alefeld, G., Hertzberger, J. edition, 1996. [74] H. H. H. Homeier. A modified Newton method for rootfinding with cubic convergence. J. Comp. Appl. Math., 157(1):227230, 1 August 2003. [75] Z. Huang. On the approximate zero of Newton method. Journal Zhejiang University SIENCE, 4(1):8085, 2003. [76] A. Hurwitz. Uber die Bedingungen, unter welchen eine Gleichung nur Wurzeln mit negativen reelen Teilen besitze. Math. Ann., 45:273284, 1895. , M. S. Petkovic , and D. Herceg. A note on Babylonia square[77] S. Ilic root algorithm and related variants. Novi Sad JOM, 26:155162, 1996. and L. Ranc ic . On the fourth order zero-finding methods [78] S. M. Ilic for polynomials. Filomat, 17:3546, 2003. [79] A. Iliev. A generalization of Obreshkoff-Ehrlich method for multiple roots of polynomial equations. C. R. Acad. Bulg. of Sci., 49(5):2326, 1996. [80] A. Iliev. Generalization of Ehrlich-Kjurkchiev method for multiple roots of algebraic equations. Technical report, University of Plovdiv, Faculty of Mathematics and Informatics, Department of Numerical Methods, Plovdiv, Bulgaria, 2003. [Link] [81] G. Jacobi. Observatiunculae ad theoriam aequationum pertnentes. J. Reine Angew. Math., 3:340352, 1835.

477

BIBLIOGRAFIE

[82] F. H. Jelinek and E. Fernandez. Neurons and fractals: how reliable and useful are calculations of fractal dimensions? Journal of Neuroscience Methods, 81:918, 1998. [83] M. A. Jenkins and J. F. Traub. A three-stage algorithm for real polynomials using quadratic iteration. SIAM J. Numer. Anal., 7:545 566, 1970. [84] S. Kanno, N. Kjurkchiev, and Yamamoto T. On some methods for the simultaneous determination of polynomial zeros. Japan J. Indust. Appl. Math., 13(2):267288, 1996. [85] L. V. Kantorovich. Functional analysis in applied mathematics ( n rus a). Uspekhi Mat. Nauk., 3:89135, 1948. [86] L. V. Kantorovich and G. Akilov. Functional Analysis in Normed Spaces. MacMillan, New York, 1964. [87] I. O. Kerner. Simultaneous displacement of polynomial roots if real and simple. Comm. ACM, 9:273, 1966. [88] M. Kim. On approximate zeros and rootfinding for a complex polynomial. Math. Comp., 51:707719, 1988. [89] N. Kjurkchiev. On some modifications of Ehrlichs method for simultaneous solving of algebraic equations ( n rus a). Pliska Stud. Math. Bulg., 5:4350, 1983. [90] N. Kjurkchiev. Some remarks on Weierstrass root-finding method. C. R. Acad. Bulgare Sci., 46:1720, 1993. [91] N. Kjurkchiev. Initial aproximations in Euler-Chebyshev method. J. Comput. Appl. Math., 58:233236, 1995. [92] N. Kjurkchiev and K. Mahdi. A note on remarks on the divergent starting points for Euler-Chebyshevs type methods. Facta Universitatis, 9:9598, 1994. [93] N. Kjurkchiev and K. Mahdi. Some remarks on Dvorcuk root-finding method. BIT, 34:319322, 1994. [94] N. Kjurkchiev and S. Markov. Two interval methods for algebraic equations with real roots. Pliska, 5:118131, 1983. [95] D. E. Knuth. The Art of Programming, volume 2. Addison-Wesley, New York, 1969.

BIBLIOGRAFIE

478

[96] D. E. Knuth. Tratat de programare a calculatoarelor (Algoritmi seminumerici). Ed. Tehnic a, Bucure sti, 1983. [97] E. Kobald. Notice concerned with the calculation of roots of numerical equations ( n german a). Monatsh. Math. und Physik, 2:331332, 1891. [98] A. Korganoff. M ethodes de Calcul Num erique. Alg` ebre nonlin eaire. Dunod, Paris, 1961. [99] W. Krandick. Trees and jumps and real roots. J. Comp. Appl. Math., 162(1):5155, 1 January 2004. [100] E. N. Laguerre. Sur la r esolution des equations num eriques. Nouv. Ann. Math., 17(2):2025, 1878. [101] E. N. Laguerre. Sur une formule nouvelle permettant dobtenir,... les racines dune equation..., volume 1. Oeuvres, Gauthier-Villars, Paris, 1898. [102] D. H. Lehmer. A machine method for solving polynomial equation. Journal of the ACM, 8(2):151162, 1961. [103] S. Lin. A method for finding roots of algebraic equations. J. Math. Phys., 22:6077, 1943. [104] P. Lorczak. The Mathcad Treasury. Mathsoft E-book, Cambridge: Mathsoft, Inc., 2002. [105] C. Maclaurin. A treatise of algebra. Oxford, London, 1796. [106] V. H. Maehly. Zur iterativen Aufl osung algebraischer Gleichungen. Z. Angew. Math. Phys., 5:260263, 1954. rus [107] S . Ma ter. Metode numerice n rezolvarea ecuat iilor neliniare. Ed. Tehnic a, 1981. rus [108] S . Ma ter. Numerical experiments on attraction basin for tangent method in several variables. Seminar Informatics and Computational Mathematics, 1(1):4755, February 2001. rus [109] S . Ma ter. On the tangent parabola method for nonlinear equations in one variable. Seminar Informatics and Computational Mathematics, 1(1):19, February 2001. [110] J. M. McNamee. A bibliography on roots of polynomials. J. Comput. Appl. Math., 47:391394, 1993. [Link] /sac/cam/mcnamee.

479

BIBLIOGRAFIE

[111] J. M. McNamee. A supplementary bibliography on roots of polynomials. J. Comput. Appl. Math., 78:1, 1997. [112] J. M. McNamee. An updated supplementary bibliography on roots of polynomials. J. Comput. Appl. Math., 110:305306, 1999. http:// [Link]/mcnamee/[Link]. [113] J. M. McNamee. A 2003 update of the supplementary bibliography on roots of polynomials. J. Comput. Appl. Math., 140:12, 2003. [Link] /[Link]. ileanu. Istoria Matematicii. volumul 2. Ed. S [114] N. Miha tiint ific a si Enciclopedic a, Bucure sti, 1981. [115] D. E. Muller. A method for solving algebraic equations using an automatic computer. Math. Tables Aids Comput., 10:208215, 1956. [116] I. Newton. Methodus Fluxionum et Serierum Infinitarum. Oxford, 1669. [117] A. W. M. Nourein. An iteration formula for the simultaneous determination of the Zeroes of a Polynomial. J. Comput. Appl. Math., 4:251254, 1975. [118] A. W. M. Nourein. An improvement on Noureins method for simultaneous determination of the zeroes of polynomial (an algotithm). J. Comput. Appl. Math., 3:109110, 1977. [119] A. W. M. Nourein. An improvement on two iteration methods for simultaneous determination of the zeros of polynomial. J. Comput. Math., 6:241252, 1977. [120] J. M. Ortega and W. C. Rheinboldt. Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York, San Francisco and London, 1970. [121] J. M. Ortega and W. C. Rheinboldt. Iterative Solution of Nonlinear Equations in Several Variables. PA:SIAM, Philadelphia, 2000. [122] A. M. Ostrowski. Uber die Konvergenz und die Abrundungsfestigkeit des Newtonschen Verfahrens. Rec. Math., 2:254258, 1937. [123] A. M. Ostrowski. Solution of Equation and Systems of Equations. Academic Press, New York, 1966.

BIBLIOGRAFIE

480

[124] A. M. Ostrowski. Solution of Equations in Euclidian and Banach Space. Academic Press, New York, 1973. [125] V. Y. Pan. On approximating polynomial zeros: Modified quadtree (Weyls) construction and improved Newtons iteration. Technical Report Research report 2894, INRIA, Sophia-Antipolis, France, 1996. [126] V. Y. Pan. Optimal and nearly optimal algorithms for approximating polynomial zeros. Comput. Math. Appl., 31:97138, 1996. [127] V. Y. Pan. Solving a polynomial equation: Some history and recent progress. SIAM, 39(2):187220, June 1997. [128] L. Pasquini and A. Trigiante. A globally convergent method for simultaneously finding polynomial roots. Math. Comp., 44:135149, 1985. [129] H. O. Peitgen and P. H. Richter. The Beauty of Fractals. SpringerVerlag, 1986. . On a gneralization of the root iterations for polynomial [130] M. S. Petkovic complex zeros in circular interval arithmetic. Computing, 27:3755, 1981. . On an iteration method for simultaneous inclusion of [131] M. S. Petkovic polynomial complex zeros. J. Comput. Appl. Math., 8:5156, 1982. . Some interval iterations for finding a zero of a poly[132] M. S. Petkovic nomial with error bounds. Comput. Math. Appl., 14:479495, 1987. . Iterative Methods for Simultaneous Inclusion of Poly[133] M. S. Petkovic nomial Zeros. Springer-Verlag, Berlin, 1989. . On the Halley-like algorithms for the simultaneous [134] M. S. Petkovic approximation of polynomial complex zeros. SIAM J. Numer. Anal., 26:740763, 1989. . On initial conditions for the convergence of simulta[135] M. S. Petkovic neous root finding methods. Computing, 57:163177, 1996. . Halley-like method with corrections for the inclusion [136] M. S. Petkovic of polynomial zeros. Computing, 62:6988, 1999. . Comments on some recent methods for simultane[137] M. S. Petkovic ous determination of polynomial zeros. Journal of Computational and Applied Mathematics, 145(2):519524, 15 August 2002. , C. Carstensen, and M. Trajkovic . Weierstrass [138] M. S. Petkovic formula and zerofinding methods. Numer. Math., 69:353372, 1995.

481

BIBLIOGRAFIE

and D. Herceg. Point estimation and safe convergence [139] M. S. Petkovic of root-finding simultaneous methods. Scientific Review, 21-22:117130, 1996. and D. Herceg. B [140] M. S. Petkovic orsch-Supan-like methods: Point estimation and parallel implementation. Intern. J. Comput. Math., 64:327341, 1997. , D. Herceg, and S. Ilic . Point Estimation Theory [141] M. S. Petkovic and its Applications. Institute of Mathematics, Novi Sad, 1997. , D. Herceg, and S. Ilic . Point estimation and some [142] M. S. Petkovic applications to iterative methods. BIT, 38:111126, 1998. , D. Herceg, and S. Ilic . Safe convergence of simulta[143] M. S. Petkovic neous methods for polynomial zeros. Numerical Algorithms, 17:313332, 1998. and S. Ilic . Point estimation and the convergence [144] M. S. Petkovic of the Ehrlich-Aberth method. Publications de lInstitut Math ematique, 62:141149, 1997. , S. Ilic , and S. B. Tric kovic . A family of simultane[145] M. S. Petkovic ous zero-finding methods. Comput. Math. Appl., 34:4959, 1997. , M. Mignotte, and M. Trajkovic . The root sep[146] M. S. Petkovic aration of polynomials and some applications. Z. Angew. Math. Mec., 75:551561, 1995. , L. Petkovic , and D. Zivkovic . Laguerre-like meth[147] M. S. Petkovic ods for the simultaneous approximation of polynomial zeros, volume Topics in numerical analysis of Comput. Suppl. 15, pages 189209. Springer, Vienna, 2001. , S. Tric kovic , and D. Herceg. On Euler-like meth[148] M. S. Petkovic ods for the simultaneous approximation of polynomial zeros. Japan J. Indust. Appl. Math., 15:295315, 1998. and S. B. Tric kovic . Tchebychev-like method for [149] M. S. Petkovic simultaneous finding zeros of analytic functions. Comput. Math. Appl., 31:8593, 1996. and Vranic D. V. The convergence of Euler-like [150] M. S. Petkovic method for the simultaneous inclusion of polynomial zeros. Computers and Mathematics with Applications, 39(7-8):95105, April 2000.

BIBLIOGRAFIE

482

[151] P. Popovici and O. Cira. Rezolvarea numeric a a ecuat iilor neliniare. Ed. SigNata, Timi soara, 1992. [152] L. Rall. A note on the convegence of Newtons method. SIAM J. Numer. Anal., 11:3436, 1974. [153] J. Riordan. Combinatorial Identities. John Wiley and Sons, New YorkLondon-Sydney, 1968. [154] F. Rouillier and P. Zimmermann. Efficient isolation of polynomial ss real roots. J. Comp. Appl. Math., 162(1):3350, 1 January 2004. [155] E. J. Routh. Stability of a dynamical system with two independent motions. Proc. London Math. Soc., 5:9799, 1874. [156] S. M. Rump. Ten methods to bound multiple roots of polynomials. J. Comput. Appl. Math., 156:403, July 2003. [157] T. R. Scavo and J. B. Thoo. On the geometry of Halleys method. The American Mathematical Monthly, 102:417426, 1995. der. Uber [158] E. Schro unendlich viele Algorithmen zur Aufl osung der Gleichungen. Math. Ann., 2:317365, 1870. [159] I. Schur. Uber Potenzreihen, die im Innern des Einheitskreises beschr ankt sind. J. Reine Angew Math., 147:205232, 1917. [160] I. Schur. Uber Potenzreihen, die in Innern des Einheitskreises beschr ankt sind. J. Reine Angew Math., 148:122145, 1918. [161] B. Sendov, A. Andreev, and N. Kjurkchiev. Numerical Solution of Polynomial Equations (Handbook of Numerical Analysis), volume VIII. Elsevier Science, New York, 1994. [162] B. Sendov and V. Popov. Numerical Methods ( n bulgar a), volume I. Nauka i Izkustvo, Sofia, 1976. [163] R. S erban. Algoritmi de optimizare unidimensional a. Stud. Cercet. Cal. Eco. Ciber. Eco., 22:5367, 1987. [164] M. Shub and S. Smale. Computational complexity: on the Geometry of polynomials and a theory of costs. I. Ann. Sci. Ecole Norm. Sup., 18:107142, 1985. [165] M. Shub and S. Smale. Computational complexity: on the geometry of polynomials and a theory of costs. II. SIAM J. Comput., 15:145161, 1986.

483

BIBLIOGRAFIE

[166] G. Siret chi. Calculul diferent ial si integral, not inui fundamentale. volumul I. Ed. S tiint ific a si Encicloppedic a, Bucure sti, 1985. [167] S. Smale. The fundamental theorem of algebra and complexity theory. Bull. Amer. Math. Soc., 4:135, 1981. [168] S. Smale. The Merging Disciplines: New Directions in Pure, Applied and Computational Mathematics, chapter Newtons Method Estimates from Data at One Point, pages 185196. R. E. Ewing, K. I. Gross and C. F. Martin, Springer-Verlag, New York, 1986. [169] B. T. Smith. Error bounds for zeros of a polynomial based upon Gerschgorins theorem. J. Assoc. Comput. Mach., 17:661674, 1970. [170] J. Steffensen. Remarks on iteration. Skand. Aktuarietidskr, 16:6472, 1933. [171] C. Sturm. M emoire sur la r esolution des equations num eriques. M em. Savants Etrangers, 6:271318, 1835. [172] Z. Szabo. Uber gleinchungslosende Iterationen ohne Divergenzpunkt. Publ. Math. Debrecen., 20:223233, 1973. [173] Z. Szabo. Newton-parabola combined method for solving equations. Computational and Applied Mathematics I (North-Holland, Amsterdam), pages 447452, 1992. [174] K. Tanabe. Behavior of the sequences around multiple zeros generated by some simultaneous methods for solving algebraic equations ( n japonez a). Teh. Rep. Inf. Procces. Numer. Anal., 4(2):16, 1983. [175] J. F. Traub. Iterative Methods for the Solution of Equations. PrenticeHall, New Jersey, 1964. [176] J. F. Traub and H. Wozniakowski. Convergence and complexity of Newton iteration for operator equations. J. Assoc. Comp. Mach., 29:250258, 1979. [177] P. Turan. On the approximate solution of algebraic functions. Comm. Math. Phys. Class Hung. Acad., XVIII:223236, 1968. [178] P. Turan. The power sum method and approximative solution of algebraic equations. Math. Comp., 29:311318, 1975. [179] A. Van der Sluis. Upper bounds for roots of polynomials. Numer. Math., 15:250262, 1970.

BIBLIOGRAFIE

484

[180] D. Wang and F. Zhao. The theory of Smales point estimation and its applications. J. Comput. Appl. Math., 60:253269, 1995. [181] X. Wang and D. Han. On dominating sequence method in the point estimate and Smales theorem. Scientia Sinica Ser. A, 1:905913, 1989. [182] X. Wang and S. Zheng. A family of parallel and interval iterations for nding all roots a polynomial simultaneously with rapid convergence (i). J. Comput. Math., 1:7076, 1984. [183] X. Wang and S. Zheng. The quasi-Newton method in parallel circular iteration. J. Comput. Math., 4:305309, 1984. [184] X. Wang and S. Zheng. A family of parallel and interval iterations for finding all roots of polynomial simultaneously with rapid convergence (II) ( n chinez a). J. Comput. Math., 4:433444, 1985. [185] K. Weierstrass. Neuer Beweis des Satzes, dass jede ganze rationale Funktion einer Ver anderlichen dargestellt werden kann als ein Product aus linearen Funktionen dertelben Ver andelichen. Ges. Werke, 3:251 269, 1903. [186] W. Werner. Iterative Solution of Nonlinear Systems of Equations, chapter On the Simultaneous Determination of Polynomial Roots, pages 188202. Springer-Verlag, Berlin, 1982. [187] H. Weyl. Randbemerkungen zu Hauptproblemen der Mathematik, II, Fundamentalsatz der Algebra and Grundlagen der Mathematik. Math. Z., 20:131151, 1924. [188] H. S. Wilf. A global bisection algorithm for computing the zeros of polynomials in the complex plane. J. Assoc. Comput. Mach., 25:415 420, 1978. [189] T. Yamamoto, S. Kanno, and L. Atanasova. Topics in Validated Computations, chapter Validated Computation of Polynomial Zeros by the Durand-Kerner Method. J. Herzberger, B. V. Amsterdam, Elsevier Science edition, 1994. [190] F. Zhao and D. Wang. The theory of Smales point estimation and convergence of Durand-Kerner program ( n chinez a). Math. Numer. Sinica, 15:196206, 1993. [191] S. Zheng and F. Sun. Some simultaneous iterations for finding all zeros of polynomial with high order of convergence. Appl. Math. Comput., 99(1-2):233240, 1999.