p03.dvi

Size: px

Start display at page:

Download "p03.dvi"

あやかみやくぼ
4 years ago
Views:

1 301 3 : 1

2 (1) f(x) = 0 f(x) x.,, z. : 2

3 (2) z f(z) = a 0 z n +a 1 z n 1 + +a n 1 z +a n f(z) = 0 ( ),. a 0, a n. : 3

4 (3),, B(s) = b 0s m +b 1 s m 1 + +b 0 A(s) s n +a 1 s n 1 +a n, (s n +a 1 s n 1 +a n = 0 ). : 4

5 (4),. n.. : 5

6 (5) Scilab, roots() ( 48 ). Scilab factors() : 6

7 Scilab Scilab.. : 7

8 (1) 2 x 2 Newton. Bairstow (1920 ) : 8

9 (2) Newton, Bairstow,.,. : 9

10 (3) scilab roots() Jenkins & Traub (1970 ) ( )., Bairstow, Scilab roots(), MATLAB roots(), Mathematica NSolve[]. : 10

11 (4) ( ). 1, [ 1,1] 1000,. : 11

12 (5) Scilab5.5.2forWindows64bit MATLAB R2015b for Windows 64bit Intel Core i GHz, 32GB of Memory, Windows7 Professional 64bit Service Pack 1 Mathematica: Mathematica for Microsoft Windows (64-bit), Intel(R) Core(TM) i5-2500k CPU 3.30GHz, 16.0GB of Memory, Windows7 Professional 64Bit Service Pack 1 : 12

13 (6) Scilab, Bairstow roots() Bairstow 10, 20 ( ) Scilab 100 : 13

14 (7) 10 Bairstow roots() f(x) : 14

15 (8) 20 20, Bairstow (?). roots(), 100,. : 15

16 (9) f(x) 10 3 x,,, f(x),, f(x). : 16

17 (10) 20,50,100 roots() roots() f(x) % 0.004% 0.316% f(x) :

18 (11) f(x) = 0, f(x) : 18

19 (12) %, 3 1. : 19

20 (13) MATLAB( ( 75000, 4990 )) Mathematica( ( )) :

21 (14) 100 ( 1, [ 1,1] ) MATLAB roots(), Mathematica NSolve[] : 21

22 (15) Scilab MATLAB Mathematica f(x) 0.316% 0.288% 0.197% f(x) : 22

23 (16).. (Bairstow ) : 23

24 (17)?(1),.,. : 24

25 (18)?(2). ( ),. : 25

26 (19), : 26

27 (20) Mathematica,.,,. Mathematica NSolve[] WorkingPrecision-> ,. : 27

28 (21) Mathematica Mathematica f(x) % 0% f(x) : 28

29 (1). Mathematica (Maple ). : 29

30 (2),. : 30

31 (1) Scilab roots() factors(). fsolve(),.,. : 31

32 (2) Newton. 2 Newton, 1 Newton.. : 32

33 (3) deff( [y]=f(x), y=x^2+1 ); deff( [y]=df(x), y=2*x ); x0=0.9*%i; //, %i x=x0;maxitr=100;smallth=1e-8; for itr=1:maxitr x=x-f(x)/df(x); if(abs(f(x))<smallth) break(); end end : 33

34 (4) x=x-f(x)/df(x) 1.. f df.. : 34

35 (5) 56 58,. Bairstow.,. : 35

36 deff( [y]=f(x), y=x^4-29*x^2-90*x-350 ); deff( [y]=df(x), y=4*x^3-58*x-90 ); x0list=[-8,10,-2+2*%i,-2-2*%i]; x=x0list; maxitr=100;smallth=1e-8; for i=1:length(x) for itr=1:maxitr x(i)=x(i)-f(x(i))/df(x(i)); if(abs(f(x(i)))<smallth) break(); end end end : 36

37 (6) Newton.,,. : 37

38 (7) Scilab Jenkins & Traub. (Durand Kerner Ehrlich Aberth ).. : 38

39 (8) Newton,, ( 1967 ).. : 39

40 (1) Taylor : 40

41 (2) p(z) = a 0 z n +a 1 z n 1 + +z n, p(z) = 0. z 0, p(z 0 +ζ) z 0 Taylor n p (k) (z 0 ) p(z 0 +ζ) = p(z 0 )+ ζ k k! k=1 : 41

42 (3) p(z 0 +ζ) = p(z 0 )+ n p (k) (z 0) k=1 ζ k k! k = 1,2,...,n, Taylor k p(k) (z 0 ) ζ k p(z k! 0 +ζ),.,. p(z 0 +ζ) p(z 0 )+ p(k) (z 0 ) ζ k k! : 42

43 (4) p(z 0 + ζ) = 0, 0 = p(z 0 ) + p (k) (z 0 ) ζ k, k! ( ζ(k) = k!p(z ) 1/k 0) p (k) (z 0 ) k (k ). : 43

44 (5) ζ(1),ζ(2),...,ζ(n). ζ(1),ζ(2),...,ζ(n), z 0 : z 0 = z 0 +ζ(k) ( ζ(k) ζ(1),ζ(2),...,ζ(n). : 44

45 (6), backtracking ( ), p(z 0 + µζ(k)) p(z 0 ),ζ(k) µ. ζ(k), p(z 0 +ζ). : 45

46 (7),, p(z 0 ). p(z) = 0,. : 46

47 (8) : z β, λ ( 0 < β < 1, λ > 1). : p(z). 1. µ=1. ( 1/k 2. k 1,...,n, ζ(k) = µ k!p(z0) p (z0)). (k) 3. {ζ(1),...,ζ(n)} ζ(s) ( ). 4. ζ(s) {ξ1,...,ξs}. { p(z+ξ1),..., p(z+ξs) } p(z+ξt). 5. p(z+ξt) < (1 (1 β)µ)p(z) z = z +ξt. µ = µ/λ 2. : 47

48 (9),,,, 1994.,., Jenkins & Traub. : 48

49 Horner (1),.,. Horner ( ). : 49

50 Horner (2),,, 1994., p(z) = a 0 z 3 +a 1 z 2 +a 2 z+a 3, z c.. 2 Horner. : 50

51 Horner (3) c 1 ( ) a 0 1 = a 1 a 0 2 = a 2 a 0 3 = a 3 a 1 0 = a 0 a 1 1 = a1 0 c+a0 1 a 1 2 = a1 1 c+a0 2 a 1 3 = a1 2 c+a0 3 a 2 0 = a 0 a 2 1 = a2 0 c+a1 1 a 2 2 = a2 1 c+a1 2 a 3 0 = a 0 a 3 1 = a 3 0c+a 2 1 a 4 0 = a 0 : 51

52 Horner (4) a 1 a 2 a 3 a 0 a 0 c+a 1 a 0 c 2 +a 1 c+a 2 a 0 c 3 +a 1 c 2 +a 2 c+a 3 a 0 2a 0 c+a 1 3a 0 c 2 +2a 1 c+a 2 a 0 3a 0 c+a 1 a 0 p(z) = a 0 z 3 +a 1 z 2 +a 2 z +a 3 : 52

53 Horner (5) a 1 a 2 a 3 a 0 a 0 c+a 1 a 0 c 2 +a 1 c+a 2 p(c) a 0 2a 0 c+a 1 p (c) 1 a 0 2! p (c) 1 3! p (c) : 53

54 Horner (6)., c. : 54

-1-1 1 1 1 1 12 31 2 2 3 4

2007 -1-1 1 1 1 1 12 31 2 2 3 4 -2-5 6 CPU 3 Windows98 1 -3-2. 3. -4-4 2 5 1 1 1 -5- 50000 50000 50000 50000 50000 50000 50000 50000 50000 50000-6- -7-1 Windows 2 -8-1 2 3 4 - - 100,000 200,000 500,000