Metode numericepentru

rezolvarea ecuatiiloralgebrice

Octavian Cira

25 Octombrie 2005

Cuprins

Lista figurilor. . . . . . . . . . . . . . . . . . . . . . . . . . . IX

Lista tabelelor . . . . . . . . . . . . . . . . . . . . . . . . . . XII

Prefata. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .XIII

Capitolul 1. Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1. Preliminarii. . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2. Polinoamele cu coeficienti complecsi . . . . . . . . . . . . . . 2

1.3. Polinoamele cu coeficienti reali . . . . . . . . . . . . . . . . . 15

Capitolul 2. Marginile radacinilor . . . . . . . . . . . . . . . . . . . . . . 22

2.1. Marginile radacinilor polinoamelor . . . . . . . . . . . . . . . 22

2.2. Polinoamelor cu coeficienti complecsi . . . . . . . . . . . . . . 22

2.3. Polinoamelor cu coeficienti reali. . . . . . . . . . . . . . . . . 24

Capitolul 3. Metode clasice . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1. Metoda Ruffini . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.2. Metoda Lagrange . . . . . . . . . . . . . . . . . . . . . . . . 29

3.3. Metoda Graffe . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.4. Metoda Bernoulli. . . . . . . . . . . . . . . . . . . . . . . . . 31

3.5. Metoda bisectiei . . . . . . . . . . . . . . . . . . . . . . . . . 34

Capitolul 4. Metode de separare . . . . . . . . . . . . . . . . . . . . . . . 36

4.1. Separarea radacinilor reale la polinoame cu coeficienti reali . . 36

4.2. Separarea radacinilor la polinoame cu coeficienti complecsi . . 40

4.3. Convergenta metodei Lehmer-Schur . . . . . . . . . . . . . . 47

4.4. Evaluarea erorilor la metoda Lehmer-Schur . . . . . . . . . . 48

4.5. Noua metoda Lehmer-Schur . . . . . . . . . . . . . . . . . . . 48

4.6. Metoda Weyl . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.6.1. Simplificari ale testului de proximitate. . . . . . . . . . . 60

4.6.2. Testul de proximitate Turan . . . . . . . . . . . . . . . . 61

4.6.3. Testul de proximitate Kakeya . . . . . . . . . . . . . . . 62

V

CUPRINS VI

Capitolul 5. Metode de factorizare . . . . . . . . . . . . . . . . . . . . . 65

5.1. Elemente de analiza n-dimensionala . . . . . . . . . . . . . . 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. Convergenta metodei Bairstow-Newton . . . . . . . . . . 75

5.3.3. Metoda Bairstow-secanta . . . . . . . . . . . . . . . . . . 78

5.3.4. Metoda Bairstow-Steffensen . . . . . . . . . . . . . . . . 81

5.3.5. Convegenta metodelor Bairstow-secanta siBairstow-Steffensen . . . . . . . . . . . . . . . . . . . . . . 84

5.3.6. Metoda Bairstow-Fridman . . . . . . . . . . . . . . . . . 85

5.3.7. Convergenta metodei Bairstow-Fridman . . . . . . . . . . 86

5.3.8. Dimensiunea fractala . . . . . . . . . . . . . . . . . . . . 92

5.4. Metode de factorizare de ordinul 3 . . . . . . . . . . . . . . . 95

5.4.1. Metoda Bairstow-Newton. . . . . . . . . . . . . . . . . . 95

5.4.2. Metoda Bairstow-secanta . . . . . . . . . . . . . . . . . . 100

5.4.3. Metoda Bairstow-Fridman . . . . . . . . . . . . . . . . . 104

Capitolul 6. Metode de tip Newton . . . . . . . . . . . . . . . . . . . . . 107

6.1. Convergenta locala . . . . . . . . . . . . . . . . . . . . . . . . 107

6.2. Metoda Newton . . . . . . . . . . . . . . . . . . . . . . . . . 111

6.3. Metoda parabolei tangenta . . . . . . . . . . . . . . . . . . . 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 CUPRINS

Capitolul 8. 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 corectie Newton . . . . . 159

8.5. Metoda Borsch-Supan . . . . . . . . . . . . . . . . . . . . . . 160

8.6. Metoda Borsch-Supan cu factori de corectie Weierstrass . . . 162

8.7. Metoda Tanabe . . . . . . . . . . . . . . . . . . . . . . . . . 163

8.8. Metoda radacinii patrate . . . . . . . . . . . . . . . . . . . . 166

8.9. Metoda Wang-Zheng. . . . . . . . . . . . . . . . . . . . . . . 167

8.10. Noua metoda Newton . . . . . . . . . . . . . . . . . . . . . 169

8.11. Familie de metode . . . . . . . . . . . . . . . . . . . . . . . 176

Capitolul 9. Teoria estimarii punctului . . . . . . . . . . . . . . . . . . . 178

9.1. Estimari ale punctului pentru metoda Newton . . . . . . . . . 178

9.2. Estimari ale punctului pentru metode cu convergenta 2 . . . . 194

9.3. Estimari ale punctului pentru metode cu convergenta 3 . . . . 197

9.4. Dezvoltari ale estimarii 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 algebra liniara . . . . . . . . . . . . . . . . . . 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 generala de convergenta . . . . . . . . . . . . . . . 248

10.3. Metoda Durand-Kerner. . . . . . . . . . . . . . . . . . . . . 253

10.4. Metoda Borsch-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 corectii cu factori Newton . . . . 302

10.9. Metoda Borsch-Supan cu corectii cu factori Weierstrass . . . 312

CUPRINS VIII

10.10. Metoda Wang-Zheng . . . . . . . . . . . . . . . . . . . . . 324

10.11. Metode de tip Halley . . . . . . . . . . . . . . . . . . . . . 340

10.12. Conditia generala de convergenta. . . . . . . . . . . . . . . 361

Capitolul 11. Metode pentru polinoame cu zerouri multiple . . . . . . 365

11.1. Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

11.2. Metode de incluziune ce au la baza polinoamele Bell . . . . . 368

11.3. Metoda de incluziune Newton . . . . . . . . . . . . . . . . . 373

11.4. Metoda de incluziune Wang-Zheng . . . . . . . . . . . . . . 386

11.5. Metoda simultana 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 notatii . . . . . . . . . . . . . . . . . . . . . . . . . 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). . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

Figura 1.2: Coroana C(0,m2,M2). . . . . . . . . . . . . . . . . . . . . . . . . . 6

Figura 1.3: Discurile de raza R si R′. . . . . . . . . . . . . . . . . . . . . . . . . 8

Figura 1.4: Exemple pentru programul Schur. . . . . . . . . . . . . . . . . . . . 12

Figura 1.5: Grafice pentru programul Schur(Comp).. . . . . . . . . . . . . . . . 14

Figura 1.6: V (m1M1(c)T , Sturm(c, 10−12)) = 3. . . . . . . . . . . . . . . . . . . 21

Figura 1.7: V (m2M2(c)T , Sturm(c, 10−12)) = 3. . . . . . . . . . . . . . . . . . . 21

Figura 1.8: V (Kakeya(c)T , Sturm(c, 10−12)) = 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: Suprafata utila din discul de acoperire. . . . . . . . . . . . . . . . . 42

Figura 4.4: Graficul functiei 4.4. . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Figura 4.5: Graficul descresterii razelor discurilor de acoperire. . . . . . . . . . . 48

Figura 4.6: Graficul erorilor absolute. . . . . . . . . . . . . . . . . . . . . . . . 49

Figura 4.7: Graficul functiei 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 atractie al radacinii x∗ = 5. . . . . . . . . . . . . . . . . 72

Figura 5.2: Bazinele de atractie pentru metoda B-N. . . . . . . . . . . . . . . . 78

Figura 5.3: Bazinele de atractie pentru metoda B-N ın sectiunea p = −1. . . . . 79

Figura 5.4: Bazinele de atractie pentru metoda B-s. . . . . . . . . . . . . . . . . 82

IX

LISTA FIGURILOR X

Figura 5.5: Bazinele de atractie pentru metoda B-S. . . . . . . . . . . . . . . . 84

Figura 5.6: Bazinele de atractie 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 atractie pentru contractia z − P (z)/Pz) . . . . . . . . . 113

Figura 6.3: Bazinele de atractie pentru MN. . . . . . . . . . . . . . . . . . . . . 114

Figura 6.4: Bazinele de atractie pentru MTP. . . . . . . . . . . . . . . . . . . . 117

Figura 6.5: Bazinele de atractie pentru MO. . . . . . . . . . . . . . . . . . . . . 119

Figura 6.6: Bazinele de atractie pentru MOP. . . . . . . . . . . . . . . . . . . . 121

Figura 6.7: Graficul functiei |f(z)|. . . . . . . . . . . . . . . . . . . . . . . . . . 123

Figura 6.8: Metoda MP ın R1. . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

Figura 6.9: Bazinele de atractie pentru MP. . . . . . . . . . . . . . . . . . . . . 126

Figura 6.10: Bazinele de atractie pentru MC1. . . . . . . . . . . . . . . . . . . . 129

Figura 6.11: Bazinele de atractie pentru MC2. . . . . . . . . . . . . . . . . . . . 131

Figura 6.12: Bazinele de atractie 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 atractie 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: Functia ϕ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

Figura 9.4: Graficul conditiei (9.40). . . . . . . . . . . . . . . . . . . . . . . . . 222

Figura 9.5: Graficul conditiei (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: Functile g si 1/(2φ(n)). . . . . . . . . . . . . . . . . . . . . . . . . 258

Figura 10.5: Functia β si Φ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

Figura 10.6: Functiile f si λ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

Figura 10.7: Functiile h, f si g. . . . . . . . . . . . . . . . . . . . . . . . . . . . 285

XI LISTA FIGURILOR

Figura 10.8: Functiile h si f . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295

Figura 10.9: Functia τ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

Figura 10.10: Functiile h si φ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

Figura 10.11: Functile γ si φ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

Figura 10.12: Functile φ si γ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

Figura 10.13: Functile τ si τφ.. . . . . . . . . . . . . . . . . . . . . . . . . . . . 321

Figura 10.14: Functile φ si λ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

Figura 10.15: Functile h si hλ. . . . . . . . . . . . . . . . . . . . . . . . . . . . 330

Figura 10.16: Functia τ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354

Figura 11.1: Discul de incluziune D(a,R). . . . . . . . . . . . . . . . . . . . . . 386

Lista tabelelor

Tabelul 1.1: Variatia semnului cand Q este crescator. . . . . . . . . . . . . . . . 16

Tabelul 1.2: Variatia semnului cand Q este descrescator. . . . . . . . . . . . . . 16

Tabelul 1.3: Variatia functiei V . Cazul 1. . . . . . . . . . . . . . . . . . . . . . 18

Tabelul 1.4: Variatia functiei V . Cazul 2. . . . . . . . . . . . . . . . . . . . . . 18

Tabelul 1.5: Variatia functiei V . Cazul 3. . . . . . . . . . . . . . . . . . . . . . 19

Tabelul 1.6: Variatia functiei V . Cazul 4. . . . . . . . . . . . . . . . . . . . . . 19

Tabelul 5.1: Dimensiunea fractala. . . . . . . . . . . . . . . . . . . . . . . . . . 95

Tabelul 6.1: Dimensiunea fractala pentru metode cu convergenta patratica. . . . 135

Tabelul 6.2: Dimensiunea fractala pentru metode cu convergenta cubica. . . . . 135

Tabelul 9.1: Intervale [0, rn). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

Tabelul 9.2: Valorile constantei αS(n). . . . . . . . . . . . . . . . . . . . . . . . 191

Tabelul 9.3: Convergenta patratica a metodei MN. . . . . . . . . . . . . . . . . 192

Tabelul 9.4: Valorile η1(n). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

Tabelul 9.5: Testul η1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

Tabelul 10.1: Radacinile pozitive ale ecuatiei xn − x − 3 = 0. . . . . . . . . . . . 342

XII

Prefata

Studiul radacinilor polinoamelor algebrice a fost unul din cele mai prolifi-ce subiecte ın istoria milenara a matematicii. Determinarea valorii pentru carepolinomul algebric se anuleaza a fost ın atentia a mii de matematicieni. JohnMichael McNamee a publicat o bibliografie pe aceasta tema ın patru editii[110], [111], [112] si [113], ultima contine contine 32 de capitole ın cadrul apeste 300 de pagini, avand aproximativ 10 000 de titluri, unde apar doar rezul-tatele publicate ın limbile de larga circulatie internationala (engleza, fracezasi germana), ın reviste si edituri de prestigiu. O lucrarea de referinta pen-tru tema prezentata ın aceasta carte este volumul VIII, Numerical Solution ofPolynomial Equations din seria Handbook of Numerical Analysis [161], tiparitasub egida Elsevier Science.

Teoria matematica a ecuatiilor algebrice este un capitol ıncheiat al alge-brei ınca de la sfarsitul secolului al XVIII-lea odata cu demonstrarea, de catreGauss (1799), a teoremei fundamentale a algebrei. A ramas deschisa problemadeterminarii practice a solutiilor ecuatiilor algebrice.

Odata cu ideea geniala a lui Isac Newton (1669)[116] de a aproxima radacina unui polinom cu punctul deintersectie al tangentei cu axa OX, s-a deschis o noua calede determinare a solutiilor ecuatiilor. Niels Abel a demon-strat (1826) ca formulele de calcul a radacinilor cu radi-cali pot fi folosite numai pentru ecuatii algebrice de gradcel mult 4. Din acest moment era clar ca determinareasolutiilor ecuatiilor algebrice de grad mai mare decat 4 seva putea face numai cu metode de aproximare.

Multe cercetari au fost efectuate pentru a determinamarginile radacinilor polinoamelor. Exista o multitudine de constante caremajoreaza si, respectiv, minoreaza marginea superioara si marginea inferioaraale radacinilor polinomului. In cele mai multe cazuri majorarea sau mino-rarea este grosiera. Prezentam, ın aceasta carte, algoritmi de determinare aunui majorant si, respectiv, minorant ce aproximeaza marginile superioara si,respectiv, inferioara a radacinilor polinomului cu o precizie data [31].

Problema are importanta ei pentru ca permite delimitarea cat mai exacta

XIII

Capitolul 0. Prefata XIV

a coroanei circulare ın care se gasesc toate radacinile complexe si segmentelede pe axa reala care contin toate radacinile reale.

Multi matematicieni au considerat metode noi pentru aproximareasolutiilor ecuatiilor algebrice: Bernoulli [55], [81], Sturm [171], Euler si Cheby-shev [158], Laguerre [100], Weierstrass [185], Bairstow [10], Muller [115],Lehmer [102], Docev [49], Durand [50], Borsch-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. Incepand cu anul 1937, Ostrowski[122] publica mai multe articole prin care demonstreaza convergenta locala ametodei Newton ın cazul functiilor de o variabila reala.

Rezultatul lui Kantorovich din 1948 [85], care de-monstreaza convergenta patratica a metodei Newton ınspatii generale Banach, este fundamental. Acest rezul-tat domina literatura de specialitate, aparand mii de arti-cole pe aceasta tema. Dupa modelul dat de Kantorovich,trei probleme se pun ın legatura cu metodele de aproxi-mare a radacinilor polinomului: convergenta, ordinul deconvergenta si estimarea erorii. Pe langa aceste directii decercetare referitor la metodele numerice pentru ecuatiilealgebrice, exita multe alte teme de interes.

Problematica stabilitatii Routh-Hurwitz a metodelornumerice [76], [155] este, ıncepand cu secolul XX, o problema intens studiatajudecand dupa impresionanta bibliografie [113, capitolul Stability Questions(criteriul Routh-Hurwitz etc.)] pe aceasta tema.

Bairstow [10] a considerat o metoda de factorizare a polinoamelor ıntermeni de ordinul 2. Metoda Bairstow s-ar putea chema Bairstow-Newtonpentru ca sistemul neliniar ce intervine ın deducerea procesului iterativ esterezolvat cu metoda Newton. In aceasta carte vom prezenta metode de tipBairstow de ordinul 2 si 3 pentru factorizarea polinomului care au fost numiteBairstow-secanta, Bairstow-Steffensen, Bairstow-Fridman [28], [29], [30], dupacum pentru deducerea procesului iterativ, ce se face prin rezolvarea unui sistemneliniar de ordinul doi sau trei, s-a folosit metoda secantei, metoda Steffensen[170] sau metoda Fridman [60].

Mult mai tarziu s-a pus problema iteratiei de start, de aici rezultandproblema bazinelor de atractie a metodelor [32], [33], [34], [45], [40]. Foarteinteresant este faptul ca bazinele de atractie pentru metode de tip Newton auo stransa legatura cu teoria Fatou-Julia a fractalilor sau mai bine zis a atracto-rilor. Aceasta observatie s-a facut ın anul 1985 cand s-a reprezentat prima datagrafic multimea punctelor, dintr-un patrat, din care metoda Newton convergepentru ecuatia z3 − 1 = 0 [54].

Algoritmul Lehmer-Schur [102] este o metoda de separare a radacinilorpolinomului cu coeficienti complecsi, care are un neajuns importat, cu cat o

XV

radacina este separata mai tarziu, cu atat creste incertitudinea fata de pre-cizia separarii. Vom prezenta o varianta proprie a acestei metode care evitaacest neajuns [31]. Metoda Weyl [127] este o metoda de separare, fiind o ge-neralizare a algoritmului de bisectie din R, ın planul complex, unde intervalulcomplex este considerat patratul. Metoda Weyl, cunoscuta si sub denumireade constructia Quadtree [125], este una din metodele cu cea mai mica com-plexitatea a calculului, fapt ce face sa fie un algoritm ”foarte atragator”.

In 1981 Smale [167] defineste notiunea de ”zero aproximativ”, notiunecare sta la baza teoriei estimarii punctului [141]. Aceasta teorie permitedefinirea apriori a bazinelor de atractie pentru solutiile ecuatiei algebrice ınfunctie de metoda folosita.

Se remarca dezvoltarea deosebita a metodelor simultane de determinarea tuturor radacinilor ecuatiei algebrice [50], [49], [13], [87], [51], [3], [174],[182] etc. In legatura cu aceste metode s-au dezvoltat metodele de incluzi-une care folosesc o aritmetica a intervalului complex si discurile de incluziuneGerschgorin [53], unde intervalul complex este discul. O lucrare fundamen-tala pentru metodele de incluziune o datoram lui Petkovic [133], acelasi autorın anul 2002 elaboreaza o lucrare de sinteza ce cuprinde ultimele rezultatereferitoare la metodele de incluziune [137].

La ora actuala se fac eforturi importante ın directia paralelizarii algorit-milor si a folosirii calculelor ın precizii extinse pentru a rezolva ecuatii cu gradmare (> 100) si a obtine radacini cu precizii ınalte.

Nu este necesar sa avem un polinom de grad mare pentru a avea problemede determinare a radacinilor cu o acuratete mare, este suficient un polinomrau conditionat sau cu radacini multiple pentru ca sa avem dificultati de de-terminare a radacinilor.

Sunt interesante metodele mixte, ın care se combina o metoda de separarea radacinilor, ın faza initiala a algoritmului, cu o metoda rapid convergenta,ın partea a doua a algoritmului. La aceste metode este important criteriulprin care renuntam la metoda de separare si luam ın considerare metoda rapidconvergenta. Teoria estimarii punctului joaca un rol hotarator din acest punctde vedere [35], [41], [39], [36], [38].

Datorita dezvoltarii tehnologice hard si soft s-a ajus la performante re-marcabile. Determinarea tuturor radacinilor pentru ecuatiile algebrice de grad99 nu mai constituie o problema de timp CPU si acuratete de determinare. Laora actuala exista pachete de calcul stiintific (Mathcad [104], [37], [44], Mate-matica, Maple, Matlab, . . . ), sau biblioteci de programe stiintifice (IMSL [1],NAG [2], DROOTS, . . . ) care furnizeaza functii sau programe de rezolvare aecuatiilor algebrice de grad mare cu precizii de 15, 24 sau 32 de cifre zecimale.Apeland la calculul simbolic se pot furniza radacini exacte sau cu un numarmare de zecimale exacte (100–250 cifre zecimale). Pentru a vedea ultimeleprobleme referitoare la radacinile polinoamelor se poate consulta excelentul

Capitolul 0. Prefata XVI

articol a lui Burgnano si Trigiante [18].In aceasta carte se prezinta peste 50 de metode de aproximare a ra-

dacinilor ecuatiilor algebrice, unde s-au avut ın vedere constructia metodei,convergenta, ordinul de convergenta, estimarea erorii, bazinele de atractie alemetodei, iar ın unele cazuri s-au facut referiri si la complexitatea calculului.Rezultatele teoretice sunt urmate de prezentarea algoritmilor, a programelorsi a exemplelor rezolvate. Toate exemplele si programele au fost realizate ınMathcad 2001 [37], [44]. Consideram ca aceasta carte contine multe programece pot constitui un suport de ınvatare a programarii ın Mathcad. In exem-plele date s-au preferat polinoame cu radacini numere ıntregi sau cu radacinicomplexe ce au partea reala si partea imaginara ıntreaga pentru a se evidentiausor erorile de aproximare.

Cartea se adreseaza programatorilor, cercetatorilor, cadrelor didacticedin ınvatamantul superior, studentiilor care sunt familiarizati cu analiza nu-merica. Se prezinta suportul teoretic pentru metodele numerice si algoritmiice stau la baza programelor performante de rezolvare numerica a ecuatiiloralgebrice.

Demonstratiile teoremelor si propozitiilor, ın multe cazuri, nu pot fi par-curse si verificate fara a avea la ındemana un soft (Mathcad, Maple, Matemat-ica, Scientific Word, ...) ce asigura calcul simbolic si rutine pentru rezolvareaecuatilor algebrice, pentru a verifica calcule complexe si a rezolva ecuatii al-gebrice de grad mare. Consideram ca acest fapt este o noutate importanta ınliteratura stiintifica din Romania.

Autorul detine toate documentele Mathcad versiunea 11.0 (148 de fisiereMCD si un fisier README.txt) pentru demonstratiile ın detaliu a teoremelorsi propozitiilor prezentate, acestea pot fi accesate de pe CD-ul atasat cartii.

Multumesc tuturor celor care au fost alaturi de mine pentru scriereaacestei carti.

Arad, 08 Februarie 2005 Autorul

Bibliografie

[1] ***. IMSL User’s Manual, 1987. Version 1.0, chapter 7.

[2] ***. NAG Fortran Library Manual, volume 1. Mark 13, 1988.

[3] O. Aberth. Iteration methods finding all zeros of polynomial simulta-neously. Math. Comp., 27:339–344, 1973.

[4] F. S. Acton. Numerical Methods that Work. Harper and Row, NewYork, 1970.

[5] A. C. Aitken. On the factorization of polynomials by iterative methods,chapter Studies in Practical Mathematics VI, pages 174–191. Proc. Roy.Soc. Edinburgh 63, 1951.

[6] A. C. Aitken. On the theory of methods of factoring polynomials byiterated division, chapter Studies in Practical Mathematics VII, pages326–335. Proc. Roy. Soc. Edinburgh 63, 1952.

[7] A. C. Aitken. Note on the acceleration of lin’s process of iteratedpenultimate remainder. Quart. J. Mech. Appl. Math., 8:251–258, 1955.

[8] A. C. Aitken. On the the iterative methods of Lin and Fridman forfactorizing polynomials, chapter Studies in Practical Mathematics VIII,pages 190–199. Proc. Roy. Soc. Edinburgh 64, 1956.

[9] G. Alefeld and J. Herzberger. Introduction to Interval Computa-tion. Academic Press, New York, 1983.

[10] L. Bairstow. Investigations Relating to the Stability of the Aeroplane,pages 51–64. Reports and Memoranda No 154 of Advisory Committeefor Aeronautics, 1914.

[11] H. Bateman. Halley’s methods for solving equations. Amer. Math.Monthly, 45:11–17, 1938.

[12] E. T. Bell. Exponential polynomials. Math. Ann., 35:258–277, 1934.

470

471 BIBLIOGRAFIE

[13] W. Borsch-Supan. A posteriori error bounds for the zeros of polyno-mials. Numer. Math., 5:380–398, 1963.

[14] W. Borsch-Supan. Reiduenabschatzung fur Polynom nullstellen mit-tels Lagrange-Interpolation. Numer. Math., 14:287–296, 1970.

[15] D. Braess and K. P. Hadeler. Simultaneous inclusion of the zeros ofpolynomial. Numer. Math., 21:161–165, 1973.

[16] V. Brınzanescu and O. Stanasila. Matematici speciale. Ed. All,Bucuresti, a II-a editie, 1998.

[17] L. Brugnano. Numerical implementation of a new algorithm for poly-nomials with multiple roots. Journal of Difference Equations and Ap-plications, 1:187–207, 1995.

[18] L. Brugnano and D. Trigiante. Polynomial roots: the ultimate an-swer? Linear Algebra Appl., 225:207–219, 1995.

[19] C. Carstensen. Anwendungen von Begleitmatrizen. Z. Angew. Math.Mech., 71:809–812, 1991.

[20] C. Carstensen. Inclusion of the roots of a polynomial based on Ger-schgorin’s theorem. Numer. Math., 59:349–360, 1991.

[21] C. Carstensen. On quadratic-like convergence of the means for twomethods for simultaneous rootfinding of polynomials. BIT, 33:64–73,1993.

[22] C. Carstensen and M. S. Petkovic. On iteration methods withoutderivatives for the simultaneous determination of polynomial zeros. J.Comput. Appl. Math., 45:251–266, 1993.

[23] J. L. Chabert. “Methods of False Position” Ch. 3 in A History ofAlgorithms: From the Pebble to the Microchip. Springer-Verlag, NewYork, 1999. pp. 83-112.

[24] C. F. Chen and M. M. Chen. Performing Lin’s method via Routh-typealgorithms or Hurwitz-type determinants. Proc. IEEE, 68:1447–1449,1980.

[25] C. F. Chen and M. H. Lin. A generalization of Lin’s method for poly-nomial factorization. J. Franklin Inst., 326:849–860, 1989.

[26] P. Chen. Approximate zeros of quadratically convergent algorithms.Math. Comp., 63:247–270, 1994.

BIBLIOGRAFIE 472

[27] O. Cira. Algorithm for the simultaneous determination of all real zerosof the polynomial from R[x]. In Proceedings of the third Symposium ofMathematics and its Applications, pages 233–242. Timisoara Research ofthe Romania Academy and “Politehnica” University of Timisoara, 3-4November 1989.

[28] O. Cira. Metoda Bairstow. In Proceedings of the fifth Symposium ofMathematics and its Applications, pages 57–64. Timisoara Research ofthe Romania Academy and “Politehnica” University of Timisoara, 29-30October 1993.

[29] O. Cira. Bairstow methods of order 3. In Proceedings of the SeventhSymposium of Mathematics and its Applications, pages 79–84. TimisoaraResearch of the Romania Academy and “Politehnica” University ofTimisoara, 6-9 November 1997.

[30] O. Cira. Iterative methods for the determination of polynomial factors.In Bulletins for Applied and Computing Mathematics, Pannonian Ap-plied Mathematical Meetings, Interuniversity Network in Central Europe,number 1494 in BAM, pages 183–190. Caretaken by the PAMM-Centreat the Technical University of Budapest, September 1998.

[31] O. Cira. Rezolvarea numerica a ecuatiilor algebrice. PhD thesis, WestUniversity of Timisoara, 1998.

[32] O. Cira. The attraction basins for iterative method. In Proceedingsof the Eighth Symposium of Mathematics and its Applications, pages39–46. Timisoara Research of the Romania Academy and “Politehnica”University of Timisoara, 4-7 November 1999.

[33] O. Cira. Convergence domain of the iterative methods. In Bulletins forApplied and Computing Mathematics, Pannonian Applied MathematicalMeetings, Interuniversity Network in Central Europe, number 1630 inBAM, pages 124–132. Caretaken by the PAMM-Centre at the TechnicalUniversity of Budapest, January 1999.

[34] O. Cira. Numerical experiments for convergence domain. In Bulletinsfor Applied and Computing Mathematics, Pannonian Applied Mathe-matical Meetings, Interuniversity Network in Central Europe, number1646 in BAM, pages 129–146. Caretaken by the PAMM-Centre at theTechnical University of Budapest, August 1999.

[35] O. Cira. Algoritmul Lehmer-Schur-Newton de rezolvare a ecuatiiloralgebrice. In Conferinta de Informatica Teoretica si Tehnologii Infor-matice, Tehnologii informatice pentru anii 2000. pag. 21-28. Facultatea

473 BIBLIOGRAFIE

de Matematica si Informatica a Universitatii ”Ovidius” din Constantasi Institutul National de Cercetare-Dezvoltare ın Informatica din Bu-curesti, 25-27 May 2000.

[36] O. Cira. Approximate zeros of algebraic polynomials with higer conver-gence order mixture methods. In Bulletins for Applied and ComputingMathematics, Pannonian Applied Mathematical Meetings, Interuniver-sity Network in Central Europe, number 1732 in BAM, pages 27–36.Caretaken by the PAMM-Centre at the Technical University of Bu-dapest, June 2000.

[37] O. Cira. Lectii de Mathcad. Ed. Albastra, Cluj-Napoca, 2000.

[38] O. Cira. Lehmer-Schur-Euler-Chebyshev method for approximation allzeros of algebraic polynomials. In Bulletins for Applied and ComputingMathematics, Pannonian Applied Mathematical Meetings, Interuniver-sity Network in Central Europe, number 1773 in BAM, pages 47–56.Caretaken by the PAMM-Centre at the Technical University of Bu-dapest, August 2000.

[39] O. Cira. Lehmer-Schur-Newton algorithm for solving the algebraicequation. In Bulletins for Applied and Computing Mathematics, Pan-nonian Applied Mathematical Meetings, Interuniversity Network in Cen-tral Europe, number 1723 in BAM, pages 69–78. Caretaken by thePAMM-Centre at the Technical University of Budapest, April 2000.

[40] O. Cira. Numerical experiments on attraction basin. Advanced Modelingand Optimization (AMO), 2(3):122–134, 2001.

[41] O. Cira. Polyzeros-hybdrid method for algebraic equations solving. InSymbolic and Numeric Algorithms for Scientific Computing SYNACS01, number 01-20 in RISC-Linz Report Series, pages 182–196. ResearchInstitute for Symbolic Computation, Johannes Kepler University of Linz,Austria and West University of Timisoara, 2-5 October 2001.

[42] O. Cira. Some new aspects regarding the parabola method. In Bulletinsfor Applied and Computing Mathematics, Pannonian Applied Mathe-matical Meetings, Interuniversity Network in Central Europe, number1854 in BAM, pages 153–164. Caretaken by the PAMM-Centre at theTechnical University of Budapest, May-June 2001.

[43] O. Cira. Parabola method-polynomial rootfinder. In Symbolic andNumeric Algorithms for Scientific Computing SYNACS 02, RISC-Linz

BIBLIOGRAFIE 474

Report Series, pages 76–88. Research Institute for Symbolic Computa-tion, Johannes Kepler University of Linz, Austria and West Universityof Timisoara, 09-12 October 2002.

[44] O. Cira. Lectii de Mathcad 2001 Professional. Ed. Albastra, Cluj-Napoca, 2003.

[45] O. Cira and D. Bucerzan. Graphics reprezentation of attraction basinsfor iterative method of approximating the roots to nonlinear equations.In Symbolic and Numeric Algorithms for Scientific Computing SYNACS2000, number 01-20 in RISC-Linz Report Series, pages 69–72. ResearchInstitute for Symbolic Computation, Johannes Kepler University of Linz,Austria and West University of Timisoara, 4-6 October 2000.

[46] J. H. Curry. On zero finding methods of higher order from data at onepoint. J. Complexity, 5:219–237, 1989.

[47] J. C. Daubisse. Sur une methode de resolution numerique d’equationsalgebriques en particulier dans le cas de racines multiples, volume Fak.Ser. Mat. Fiz. of 498-541, pages 163–166. Univ. Beograd Publ., 1975.

[48] B. P. Demidovich and I. A. Maron. Computational Mathematics. MirPublishers, Moscow, 1976.

[49] K. Docev. An alternative method of Newton for simultaneous calcu-lation of all the roots of a given algebraic equation (ın bulgara). Phys.Math. J. Bulgar. Acad. Sci., 5(2):136–139, 1962.

[50] I. E. Durand. Solutions Numerique des Equations Algebriques. Equa-tions du Type F(x)=0; Racines d’une Polynome, volume 1, pages 279–281. Masson, Paris, 1960.

[51] L. W. Ehrlich. A modified Newton method for polynomials. Comm.ACM, 10:107–108, 1967.

[52] G. H. Ellis and L. T. Watson. A paralell algorithm for simple rootsof polynomials. Comput. Math. Appl., 2:107–121, 1984.

[53] L. Elsner. Remark on simultaneous inclusion of the zeros of a polyno-mial by Gerschgorin’s theorem. Numer. Math., 21:425–427, 1973.

[54] B. Epureanu and H. Greenside. Fractal basins of attraction asso-ciated with a damped Newton’s method. SIAM Rev., 40(1):102–109,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 Appli-cationa. John Wiley and Sons, 1990.

[57] W. H. Flannery, S.A. Teukolsky, and W. T. Vetterling. TheArt of Scientific Computing. Cambridge University Press, Cambridge,2 edition, 1992.

[58] J. B. J. Fourier. Oeuvres de Fourier, volume II, pages 249–250.Gauthier-Villars, Paris, 1890.

[59] P. Fraigniaud. The Durand-Kerner polynomial root finding methodin case of multiple roots. BIT, 31:112–123, 1991.

[60] A. M. Fridman. Proceduri iterative cu eroare minima pentru ecuatiioperatoriale neliniare (ın rusa). Dokl. Acad. Nauk., 139:1063–1066, 1960.

[61] M. Frontini and E. Sormani. Modified Newton’s method withthird-order convergence and multiple roots. J. Comp. Appl. Math.,156(2):345–354, 15 July 2003.

[62] I. Gargantini. Parallel Laguerre iterations: Complex case. Numer.Math., 26:317–323, 1976.

[63] I. Gargantini. Further application of circular arithmetic: Schroder-likealgorithms with error bound for finding zeros of polynomials. SIAM J.Numer. Anal., 15:497–510, 1978.

[64] I. Gargantini and P. Henrici. Circular arithmetic and the determi-nation of polynomial zeros. Numer. Math., 18:305–320, 1972.

[65] S. K. Godunov and V. S. Reabenki. Scheme de calcul cu diferentefinite. Editura Tehnica, Bucuresti, 1977.

[66] G. H. Golub and T. N. Robertson. A generalized Bairstow algorithm.Communications of the ACM, 10(6):371–373, June 1967.

[67] W. Gregg and R. Tapia. Optimal error bounds for Newton-Kanto-rovich theorem. SIAM J. Numer. Anal., 11:10–13, 1974.

[68] E. Halley. A new, exact, and easy method of finding the roots of anyequations generally, and that without any previous reduction (ın latina).Philos. Trans. Roy. Soc. London, 18:136–148, 1694.

[69] E. Hansen and M. Patrick. A family of root finding methods. Numer.Math., 27:257–269, 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, volumeProc. of VIII Conference on Logic and Computer Science Lira’97, pages67–75. Eds. R. Tosic and Z. Budimac, Institute of Mathematics NoviSad, September 1-4 1997.

[73] J. Hertzberger and L. Metzner. On the Q-order and R-order of con-vergence for coupled sequences arising in iterative numerical processes,volume Mathematical Research, Vol. 89, chapter Numerical methodsand error bounds, pages 120–131. Akademie Verlang, Berlin, Alefeld,G., Hertzberger, J. edition, 1996.

[74] H. H. H. Homeier. A modified Newton method for rootfinding withcubic convergence. J. Comp. Appl. Math., 157(1):227–230, 1 August2003.

[75] Z. Huang. On the approximate zero of Newton method. Journal Zhe-jiang University SIENCE, 4(1):80–85, 2003.

[76] A. Hurwitz. Uber die Bedingungen, unter welchen eine Gleichung nurWurzeln mit negativen reelen Teilen besitze. Math. Ann., 45:273–284,1895.

[77] S. Ilic, M. S. Petkovic, and D. Herceg. A note on Babylonia square-root algorithm and related variants. Novi Sad JOM, 26:155–162, 1996.

[78] S. M. Ilic and L. Rancic. On the fourth order zero-finding methodsfor polynomials. Filomat, 17:35–46, 2003.

[79] A. Iliev. A generalization of Obreshkoff-Ehrlich method for multipleroots of polynomial equations. C. R. Acad. Bulg. of Sci., 49(5):23–26,1996.

[80] A. Iliev. Generalization of Ehrlich-Kjurkchiev method for multiple rootsof algebraic equations. Technical report, University of Plovdiv, Facultyof Mathematics and Informatics, Department of Numerical Methods,Plovdiv, Bulgaria, 2003. http://www.pu.acad.bg.

[81] G. Jacobi. Observatiunculae ad theoriam aequationum pertnentes. J.Reine Angew. Math., 3:340–352, 1835.

477 BIBLIOGRAFIE

[82] F. H. Jelinek and E. Fernandez. Neurons and fractals: how reliableand useful are calculations of fractal dimensions? Journal of Neuro-science Methods, 81:9–18, 1998.

[83] M. A. Jenkins and J. F. Traub. A three-stage algorithm for realpolynomials using quadratic iteration. SIAM J. Numer. Anal., 7:545–566, 1970.

[84] S. Kanno, N. Kjurkchiev, and Yamamoto T. On some methods forthe simultaneous determination of polynomial zeros. Japan J. Indust.Appl. Math., 13(2):267–288, 1996.

[85] L. V. Kantorovich. Functional analysis in applied mathematics (ınrusa). Uspekhi Mat. Nauk., 3:89–135, 1948.

[86] L. V. Kantorovich and G. Akilov. Functional Analysis in NormedSpaces. MacMillan, New York, 1964.

[87] I. O. Kerner. Simultaneous displacement of polynomial roots if realand simple. Comm. ACM, 9:273, 1966.

[88] M. Kim. On approximate zeros and rootfinding for a complex polyno-mial. Math. Comp., 51:707–719, 1988.

[89] N. Kjurkchiev. On some modifications of Ehrlich’s method for si-multaneous solving of algebraic equations (ın rusa). Pliska Stud. Math.Bulg., 5:43–50, 1983.

[90] N. Kjurkchiev. Some remarks on Weierstrass root-finding method. C.R. Acad. Bulgare Sci., 46:17–20, 1993.

[91] N. Kjurkchiev. Initial aproximations in Euler-Chebyshev method. J.Comput. Appl. Math., 58:233–236, 1995.

[92] N. Kjurkchiev and K. Mahdi. A note on remarks on the divergentstarting points for Euler-Chebyshev’s type methods. Facta Universitatis,9:95–98, 1994.

[93] N. Kjurkchiev and K. Mahdi. Some remarks on Dvorcuk root-findingmethod. BIT, 34:319–322, 1994.

[94] N. Kjurkchiev and S. Markov. Two interval methods for algebraicequations with real roots. Pliska, 5:118–131, 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 semi-numerici). Ed. Tehnica, Bucuresti, 1983.

[97] E. Kobald. Notice concerned with the calculation of roots of numericalequations (ın germana). Monatsh. Math. und Physik, 2:331–332, 1891.

[98] A. Korganoff. Methodes de Calcul Numerique. Algebre nonlineaire.Dunod, Paris, 1961.

[99] W. Krandick. Trees and jumps and real roots. J. Comp. Appl. Math.,162(1):51–55, 1 January 2004.

[100] E. N. Laguerre. Sur la resolution des equations numeriques. Nouv.Ann. Math., 17(2):20–25, 1878.

[101] E. N. Laguerre. Sur une formule nouvelle permettant d’obtenir,... lesracines d’une 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):151–162, 1961.

[103] S. Lin. A method for finding roots of algebraic equations. J. Math.Phys., 22:60–77, 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 Auflosung algebraischer Gleichungen. Z.Angew. Math. Phys., 5:260–263, 1954.

[107] S. Maruster. Metode numerice ın rezolvarea ecuatiilor neliniare. Ed.Tehnica, 1981.

[108] S. Maruster. Numerical experiments on attraction basin for tangentmethod in several variables. Seminar Informatics and ComputationalMathematics, 1(1):47–55, February 2001.

[109] S. Maruster. On the tangent parabola method for nonlinear equationsin one variable. Seminar Informatics and Computational Mathematics,1(1):1–9, February 2001.

[110] J. M. McNamee. A bibliography on roots of polynomials. J. Comput.Appl. Math., 47:391–394, 1993. http://www.elsevier.com/homepage/sac/cam/mcnamee.

479 BIBLIOGRAFIE

[111] J. M. McNamee. A supplementary bibliography on roots of polynomi-als. J. Comput. Appl. Math., 78:1, 1997.

[112] J. M. McNamee. An updated supplementary bibliography on rootsof polynomials. J. Comput. Appl. Math., 110:305–306, 1999. http://www.atkinson.yorku.ca/mcnamee/BIBLIOG4.html.

[113] J. M. McNamee. A 2003 update of the supplementary bibliog-raphy on roots of polynomials. J. Comput. Appl. Math., 140:1–2,2003. http://www.elsevier.com/homepage/sac/cam/mcnamee/2002/index.html.

[114] N. Mihaileanu. Istoria Matematicii. volumul 2. Ed. Stiintifica si En-ciclopedica, Bucuresti, 1981.

[115] D. E. Muller. A method for solving algebraic equations using an au-tomatic computer. Math. Tables Aids Comput., 10:208–215, 1956.

[116] I. Newton. Methodus Fluxionum et Serierum Infinitarum. Oxford,1669.

[117] A. W. M. Nourein. An iteration formula for the simultaneous determi-nation of the Zeroes of a Polynomial. J. Comput. Appl. Math., 4:251–254,1975.

[118] A. W. M. Nourein. An improvement on Nourein’s method for simul-taneous determination of the zeroes of polynomial (an algotithm). J.Comput. Appl. Math., 3:109–110, 1977.

[119] A. W. M. Nourein. An improvement on two iteration methods for si-multaneous determination of the zeros of polynomial. J. Comput. Math.,6:241–252, 1977.

[120] J. M. Ortega and W. C. Rheinboldt. Iterative Solution of Nonlin-ear Equations in Several Variables. Academic Press, New York, SanFrancisco and London, 1970.

[121] J. M. Ortega and W. C. Rheinboldt. Iterative Solution of NonlinearEquations in Several Variables. PA:SIAM, Philadelphia, 2000.

[122] A. M. Ostrowski. Uber die Konvergenz und die Abrundungsfestigkeitdes Newtonschen Verfahrens. Rec. Math., 2:254–258, 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 BanachSpace. Academic Press, New York, 1973.

[125] V. Y. Pan. On approximating polynomial zeros: Modified quadtree(Weyl’s) construction and improved Newton’s iteration. Technical Re-port Research report 2894, INRIA, Sophia-Antipolis, France, 1996.

[126] V. Y. Pan. Optimal and nearly optimal algorithms for approximatingpolynomial zeros. Comput. Math. Appl., 31:97–138, 1996.

[127] V. Y. Pan. Solving a polynomial equation: Some history and recentprogress. SIAM, 39(2):187–220, June 1997.

[128] L. Pasquini and A. Trigiante. A globally convergent method for si-multaneously finding polynomial roots. Math. Comp., 44:135–149, 1985.

[129] H. O. Peitgen and P. H. Richter. The Beauty of Fractals. Springer-Verlag, 1986.

[130] M. S. Petkovic. On a gneralization of the root iterations for polynomialcomplex zeros in circular interval arithmetic. Computing, 27:37–55, 1981.

[131] M. S. Petkovic. On an iteration method for simultaneous inclusion ofpolynomial complex zeros. J. Comput. Appl. Math., 8:51–56, 1982.

[132] M. S. Petkovic. Some interval iterations for finding a zero of a poly-nomial with error bounds. Comput. Math. Appl., 14:479–495, 1987.

[133] M. S. Petkovic. Iterative Methods for Simultaneous Inclusion of Poly-nomial Zeros. Springer-Verlag, Berlin, 1989.

[134] M. S. Petkovic. On the Halley-like algorithms for the simultaneousapproximation of polynomial complex zeros. SIAM J. Numer. Anal.,26:740–763, 1989.

[135] M. S. Petkovic. On initial conditions for the convergence of simulta-neous root finding methods. Computing, 57:163–177, 1996.

[136] M. S. Petkovic. Halley-like method with corrections for the inclusionof polynomial zeros. Computing, 62:69–88, 1999.

[137] M. S. Petkovic. Comments on some recent methods for simultane-ous determination of polynomial zeros. Journal of Computational andApplied Mathematics, 145(2):519–524, 15 August 2002.

[138] M. S. Petkovic, C. Carstensen, and M. Trajkovic. Weierstrass’formula and zerofinding methods. Numer. Math., 69:353–372, 1995.

481 BIBLIOGRAFIE

[139] M. S. Petkovic and D. Herceg. Point estimation and safe convergenceof root-finding simultaneous methods. Scientific Review, 21-22:117–130,1996.

[140] M. S. Petkovic and D. Herceg. Borsch-Supan-like methods: Pointestimation and parallel implementation. Intern. J. Comput. Math.,64:327–341, 1997.

[141] M. S. Petkovic, D. Herceg, and S. Ilic. Point Estimation Theoryand its Applications. Institute of Mathematics, Novi Sad, 1997.

[142] M. S. Petkovic, D. Herceg, and S. Ilic. Point estimation and someapplications to iterative methods. BIT, 38:111–126, 1998.

[143] M. S. Petkovic, D. Herceg, and S. Ilic. Safe convergence of simulta-neous methods for polynomial zeros. Numerical Algorithms, 17:313–332,1998.

[144] M. S. Petkovic and S. Ilic. Point estimation and the convergenceof the Ehrlich-Aberth method. Publications de l’Institut Mathematique,62:141–149, 1997.

[145] M. S. Petkovic, S. Ilic, and S. B. Trickovic. A family of simultane-ous zero-finding methods. Comput. Math. Appl., 34:49–59, 1997.

[146] M. S. Petkovic, M. Mignotte, and M. Trajkovic. The root sep-aration of polynomials and some applications. Z. Angew. Math. Mec.,75:551–561, 1995.

[147] M. S. Petkovic, L. Petkovic, and D. Zivkovic. Laguerre-like meth-ods for the simultaneous approximation of polynomial zeros, volume Top-ics in numerical analysis of Comput. Suppl. 15, pages 189–209. Springer,Vienna, 2001.

[148] M. S. Petkovic, S. Trickovic, and D. Herceg. On Euler-like meth-ods for the simultaneous approximation of polynomial zeros. Japan J.Indust. Appl. Math., 15:295–315, 1998.

[149] M. S. Petkovic and S. B. Trickovic. Tchebychev-like method forsimultaneous finding zeros of analytic functions. Comput. Math. Appl.,31:85–93, 1996.

[150] M. S. Petkovic and Vranic D. V. The convergence of Euler-likemethod for the simultaneous inclusion of polynomial zeros. Comput-ers and Mathematics with Applications, 39(7-8):95–105, April 2000.

BIBLIOGRAFIE 482

[151] P. Popovici and O. Cira. Rezolvarea numerica a ecuatiilor neliniare.Ed. SigNata, Timisoara, 1992.

[152] L. Rall. A note on the convegence of Newton’s method. SIAM J.Numer. Anal., 11:34–36, 1974.

[153] J. Riordan. Combinatorial Identities. John Wiley and Sons, New York-London-Sydney, 1968.

[154] F. Rouillier and P. Zimmermann. Efficient isolation of polynomialssreal roots. J. Comp. Appl. Math., 162(1):33–50, 1 January 2004.

[155] E. J. Routh. Stability of a dynamical system with two independentmotions. Proc. London Math. Soc., 5:97–99, 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 Halley’s method.The American Mathematical Monthly, 102:417–426, 1995.

[158] E. Schroder. Uber unendlich viele Algorithmen zur Auflosung derGleichungen. Math. Ann., 2:317–365, 1870.

[159] I. Schur. Uber Potenzreihen, die im Innern des Einheitskreisesbeschrankt sind. J. Reine Angew Math., 147:205–232, 1917.

[160] I. Schur. Uber Potenzreihen, die in Innern des Einheitskreisesbeschrankt sind. J. Reine Angew Math., 148:122–145, 1918.

[161] B. Sendov, A. Andreev, and N. Kjurkchiev. Numerical Solution ofPolynomial Equations (Handbook of Numerical Analysis), volume VIII.Elsevier Science, New York, 1994.

[162] B. Sendov and V. Popov. Numerical Methods (ın bulgara), volume I.Nauka i Izkustvo, Sofia, 1976.

[163] R. Serban. Algoritmi de optimizare unidimensionala. Stud. Cercet.Cal. Eco. Ciber. Eco., 22:53–67, 1987.

[164] M. Shub and S. Smale. Computational complexity: on the Geometryof polynomials and a theory of costs. I. Ann. Sci. Ecole Norm. Sup.,18:107–142, 1985.

[165] M. Shub and S. Smale. Computational complexity: on the geometryof polynomials and a theory of costs. II. SIAM J. Comput., 15:145–161,1986.

483 BIBLIOGRAFIE

[166] G. Siretchi. Calculul diferential si integral, notinui fundamentale. volu-mul I. Ed. Stiintifica si Encicloppedica, Bucuresti, 1985.

[167] S. Smale. The fundamental theorem of algebra and complexity theory.Bull. Amer. Math. Soc., 4:1–35, 1981.

[168] S. Smale. The Merging Disciplines: New Directions in Pure, Appliedand Computational Mathematics, chapter Newton’s Method Estimatesfrom Data at One Point, pages 185–196. R. E. Ewing, K. I. Gross andC. F. Martin, Springer-Verlag, New York, 1986.

[169] B. T. Smith. Error bounds for zeros of a polynomial based upon Ger-schgorin’s theorem. J. Assoc. Comput. Mach., 17:661–674, 1970.

[170] J. Steffensen. Remarks on iteration. Skand. Aktuarietidskr, 16:64–72,1933.

[171] C. Sturm. Memoire sur la resolution des equations numeriques. Mem.Savants Etrangers, 6:271–318, 1835.

[172] Z. Szabo. Uber gleinchungslosende Iterationen ohne Divergenzpunkt.Publ. Math. Debrecen., 20:223–233, 1973.

[173] Z. Szabo. Newton-parabola combined method for solving equations.Computational and Applied Mathematics I (North-Holland, Amster-dam), pages 447–452, 1992.

[174] K. Tanabe. Behavior of the sequences around multiple zeros gener-ated by some simultaneous methods for solving algebraic equations (ınjaponeza). Teh. Rep. Inf. Procces. Numer. Anal., 4(2):1–6, 1983.

[175] J. F. Traub. Iterative Methods for the Solution of Equations. Prentice-Hall, New Jersey, 1964.

[176] J. F. Traub and H. Wozniakowski. Convergence and complexityof Newton iteration for operator equations. J. Assoc. Comp. Mach.,29:250–258, 1979.

[177] P. Turan. On the approximate solution of algebraic functions. Comm.Math. Phys. Class Hung. Acad., XVIII:223–236, 1968.

[178] P. Turan. The power sum method and approximative solution of alge-braic equations. Math. Comp., 29:311–318, 1975.

[179] A. Van der Sluis. Upper bounds for roots of polynomials. Numer.Math., 15:250–262, 1970.

BIBLIOGRAFIE 484

[180] D. Wang and F. Zhao. The theory of Smale’s point estimation and itsapplications. J. Comput. Appl. Math., 60:253–269, 1995.

[181] X. Wang and D. Han. On dominating sequence method in the pointestimate and Smale’s theorem. Scientia Sinica Ser. A, 1:905–913, 1989.

[182] X. Wang and S. Zheng. A family of parallel and interval iterations forfinding all roots a polynomial simultaneously with rapid convergence (i).J. Comput. Math., 1:70–76, 1984.

[183] X. Wang and S. Zheng. The quasi-Newton method in parallel circulariteration. J. Comput. Math., 4:305–309, 1984.

[184] X. Wang and S. Zheng. A family of parallel and interval iterations forfinding all roots of polynomial simultaneously with rapid convergence(II) (ın chineza). J. Comput. Math., 4:433–444, 1985.

[185] K. Weierstrass. Neuer Beweis des Satzes, dass jede ganze rationaleFunktion einer Veranderlichen dargestellt werden kann als ein Productaus linearen Funktionen dertelben Verandelichen. Ges. Werke, 3:251–269, 1903.

[186] W. Werner. Iterative Solution of Nonlinear Systems of Equations,chapter On the Simultaneous Determination of Polynomial Roots, pages188–202. Springer-Verlag, Berlin, 1982.

[187] H. Weyl. Randbemerkungen zu Hauptproblemen der Mathematik, II,Fundamentalsatz der Algebra and Grundlagen der Mathematik. Math.Z., 20:131–151, 1924.

[188] H. S. Wilf. A global bisection algorithm for computing the zeros ofpolynomials in the complex plane. J. Assoc. Comput. Mach., 25:415–420, 1978.

[189] T. Yamamoto, S. Kanno, and L. Atanasova. Topics in ValidatedComputations, chapter Validated Computation of Polynomial Zeros bythe Durand-Kerner Method. J. Herzberger, B. V. Amsterdam, ElsevierScience edition, 1994.

[190] F. Zhao and D. Wang. The theory of Smale’s point estimation and con-vergence of Durand-Kerner program (ın chineza). Math. Numer. Sinica,15:196–206, 1993.

[191] S. Zheng and F. Sun. Some simultaneous iterations for finding all zerosof polynomial with high order of convergence. Appl. Math. Comput.,99(1-2):233–240, 1999.