{VERSION 6 0 "SUN SPARC SOLARIS" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 256 40 "Solving un ivariate polynomial equations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 60 "Consider a polynomial in 1 variable. What are the solutions?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f:=x ^3+x+1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fG,(*$)%\"xG\"\"$\"\"\" F*F(F*F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "r1, r2, r3 := solve(f,x); # Solutions are nested radicals" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>6%%#r1G%#r2G%#r3G6%,&*&\"\"'!\"\",&\"$3\"\"\"\"*&\"#7F /\"#$*#F/\"\"#F/#F/\"\"$F,*&F4F/F-#F,F6F/,(*&F1F,F-F5F/*&F/F/*$)F-#F/F 6F/F,F,*(^#F3F/F6F3,&*&F+F,F-F5F,*&F4F/F-F8F,F/F/,(*&F1F,F-F5F/F;F,*(^ ##F,F4F/F6F3FAF/F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "s:=fs olve(f,x); # Solutions are floating point real numbers." }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%\"sG$!+Q!yK#o!#5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "Digits:=20; s:=fsolve(f,x); Digits:=10;" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%'DigitsG\"#?" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%\"sG$!5PF$>!GQ!yK#o!#?" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'Digit sG\"#5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "t1,t2,t3 := fsolv e(f,x,complex); # Solutions are floating point complex numbers" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>6%%#t1G%#t2G%#t3G6%$!+Q!yK#o!#5^$$\"+ >!R;T$F+$!++9ah6!\"*^$F-$\"++9ah6F1" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 90 "u := RootOf(f,x); # unspecified root of f. Computatio n with Q(u) is done as with Q[x]/(f)." }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"uG-%'RootOfG6#,(*$)%#_ZG\"\"$\"\"\"F-F+F-F-F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 85 "with(padic): v1,v2,v3:=rootp(f,47,10); # Approximations of roots in 47-adic numbers." }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>6%%#v1G%#v2G%#v3G6%,8\"#M\"\"\"*&\"#YF+-%!G6#\"#ZF+F+* &\"#DF+)F.\"\"#F+F+*&\"#EF+)F.\"\"$F+F+*&\"#FF+)F.\"\"%F+F+*&\"\")F+)F .\"\"&F+F+*&\"#TF+)F.\"\"'F+F+*&FCF+)F.\"\"(F+F+*&\"#WF+)F.F?F+F+*&\"# =F+)F.\"\"*F+F+-%\"OG6#*$)F.\"#5F+F+,8F3F+F.F+*&FHF+F4F+F+*&\"#;F+F8F+ F+*&F*F+F F+FNF+F+FPF+,8\"#NF+*&\"#XF+F.F+F+*&\"#8F+F4F+F+*&F=F+F8F+F+*&\"#KF+F< F+F+*&FaoF+F@F+F+*&F-F+FDF+F+*&\"#LF+FGF+F+*&\"#IF+FKF+F+*&F?F+FNF+F+F PF+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 82 "for i in [r1,r2,r3,s,t1,t2,t3] do simplify(s ubs(x=i,f)) od; # all =0 or close to 0" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+++++5!# >" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+++++5!#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$!+++++5!#>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$!+++++5 !#>" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 106 "for i in [v1,v2,v3] do evalp(subs(x=i,f),47,12) od; # All close to 0, i.e. divisible by h igh powers of 47:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$*&\"#E\"\"\")-% !G6#\"#Z\"#5F&F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$*&\"\"(\"\"\")-% !G6#\"#Z\"#5F&F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$*&\"#7\"\"\")-%! G6#\"#Z\"#5F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 141 "As you can see, there are differe nt kind of solutions, so it is not so clear a priori what it means to \+ compute the solutions of a polynomial." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 153 "r1,r2,r3 are solutions expressed as \+ nested radicals (we take n'th roots of expressions that can also conta in m'th roots or that contain nested radicals)." }}{PARA 0 "" 0 "" {TEXT -1 57 "Disadvantages of expressing solutions as nested radicals: " }}{PARA 0 "" 0 "" {TEXT -1 142 "R1) the expressions can be large, an d that makes them hard to handle, the computation can be slow if we wo rk with solutions of f in this form." }}{PARA 0 "" 0 "" {TEXT -1 94 "R 2) Galois theory tells us that not all polynomials can be solved in te rms of nested radicals." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 323 "s, and t1,t2,t3 are approximations of real solutio ns and complex solutions of f. For any polynomial of degree n, we can \+ always compute (counted with multiplicity) n complex solutions up to s ome given accuracy. So we don't have disadvantage R2), and if we don't take many decimals then we don't have disadvantage 1) either." }} {PARA 0 "" 0 "" {TEXT -1 14 "Disadvantages:" }}{PARA 0 "" 0 "" {TEXT -1 558 "T1) Some questions become difficult when the numbers are not e xact. Suppose you have a polynomial a*x^2+b*x+c and you wonder if it h as 2 roots, or just 1 double root, you wonder if the discriminant equa ls 0. If a,b,c are floating point numbers, then you can not determine \+ the discriminant exactly but only approximately. But if the discrimina nt you compute is 0.12*10^(-5) is that then 0 or not? That is not easy to say. It is also not possible to prove that a certain number equals 0 this way, because that's hard to say when you just have an approxim ation." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 1145 "u is also a solution of f. It has none of the disadvantages R1, \+ R2, T1 mentioned above. That is why in computer algebra this is the pr eferred method to compute with a root of a polynomial. We can do exact computations with it, we can say exactly when an expression equals ze ro or not, and it is not too big like the radicals r1,r2,r3. If we lat er want to switch to another form, floating points or radicals, we can always substitute that for u. Even if at the end we want, say, radica ls, there are still advantages of using RootOf's during most of the co mputation and then substituting r1,r2,r3 at the end. Suppose for examp le we want to do a certain computation COMP (e.g. a determinant comput ation, or a resultant computation) for all roots of f. Say we want to \+ compute COMP(r1), COMP(r2), COMP(r3) where COMP stands for a computati on in which the roots of f are used (think of COMP as a Maple procedur e). Now it can take a lot of computation time to do COMP(r1), COMP(r2) and COMP(r3) because r1,r2,r3 are big expressions. It is usually much faster to do: COMP(u). And, if we really did want to have the result \+ in radicals, then we could do: " }}{PARA 0 "" 0 "" {TEXT -1 11 "A:=COM P(u);" }}{PARA 0 "" 0 "" {TEXT -1 43 "seq( simplify(subs(u=i,A)), i=[r 1,r2,r3] );" }}{PARA 0 "" 0 "" {TEXT -1 97 "and we obtain the same res ult, but probably much faster than doing: COMP(r1), COMP(r2), COMP(r3) ." }}{PARA 0 "" 0 "" {TEXT -1 71 "So we see that in some sense the ste p COMP(u) does the computation for " }{TEXT 257 9 "all roots" }{TEXT -1 42 " of f, because it did the computation for " }{TEXT 258 20 "one \+ unspecified root" }{TEXT -1 331 " u, which can still be specified late r on to each of the roots. But when we have specified roots (i.e. root s where we really do say which root it is), like r1,r2,r3 or approxima tions t1,t2,t3 then we have to compute with all three of them because \+ when we do COMP(r1) or COMP(t1) we can't get COMP(r2) or COMP(t2) by a substitution." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 14 "Disadvantages:" }}{PARA 0 "" 0 "" {TEXT -1 583 "U1) u sta nds for just one root, but an unspecified root, of f. As we've seen th is is often enough to handle all roots of f at the same time, but not \+ always. It is enough whenever we only need to compute with one root of f at a time. Like COMP(r1), COMP(r2), COMP(r3), in there we had a com putation that uses only one of the r1,r2,r3 at a time. But if you have a different kind of computation ComP that uses all roots at the same \+ time, say ComP(r1,r2,r3) then it gets harder, then we can't do that an ymore with just u, we would need another root as well. In that case we 'd have to do:" }}{PARA 0 "" 0 "" {TEXT -1 15 "u:=RootOf(f,x);" }} {PARA 0 "" 0 "" {TEXT -1 19 "evala(Factor(f,u));" }}{PARA 0 "" 0 "" {TEXT -1 120 "Now take an irreducible factor but not x-r. In this exam ple we have the factors x-r and a factor of degree 2. Then take:" }} {PARA 0 "" 0 "" {TEXT -1 37 "u2:=RootOf( of that degree 2 factor)." }} {PARA 0 "" 0 "" {TEXT -1 14 "Then do again:" }}{PARA 0 "" 0 "" {TEXT -1 24 "evala(Factor(f,\{u,u2\}));" }}{PARA 0 "" 0 "" {TEXT -1 206 "The n we get the factors x-u and x-u2, take the root u3 of the remaining f actor which has degree 1. So that root will be some expression in u an d u2. This way you do have all three roots of f simultaneously." }} {PARA 0 "" 0 "" {TEXT -1 142 "In short, disadvantage U1 is the followi ng: it is hard to do computations using RootOf's when you need more th an 1 root of f at the same time." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 17 "p-adic solutions:" }}{PARA 0 "" 0 "" {TEXT -1 258 "The solutions v1,v2,v3 do not have disadvantage U1, but \+ they do have disadvantage T1 because we compute the solutions only up \+ to some finite accuracy. However, approximate p-adic solutions are som etimes easier to deal with than approximate complex solutions." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 2 "f;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*$)%\"xG\"\"$\"\"\"F(F&F(F(F(" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 15 "u:=RootOf(f,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"uG-%'RootOfG6#,(*$)%#_ZG\"\"$\"\"\"F-F+F-F-F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "evala(Factor(f,u));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&,&%\"xG\"\"\"-%'RootOfG6#,(*$)%#_ZG\"\"$F&F&F-F& F&F&!\"\"F&,**$)F%\"\"#F&F&*&F'F&F%F&F&F&F&*$)F'F3F&F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "%/(x-u);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,**$)%\"xG\"\"#\"\"\"F(*&-%'RootOfG6#,(*$)%#_ZG\"\"$F(F (F0F(F(F(F(F&F(F(F(F(*$)F*F'F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "u2:=RootOf(%,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %#u2G-%'RootOfG6#,**$)%#_ZG\"\"#\"\"\"F-*&-F&6#,(*$)F+\"\"$F-F-F+F-F-F -F-F+F-F-F-F-*$)F/F,F-F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "evala(Factor(f,\{u,u2\}));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#*(,(%\" xG\"\"\"-%'RootOfG6#,(*$)%#_ZG\"\"$F&F&F-F&F&F&F&-F(6#,**$)F-\"\"#F&F& *&F'F&F-F&F&F&F&*$)F'F4F&F&F&F&,&F%F&F/!\"\"F&,&F%F&F'F9F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "%/(x-u)/(x-u2);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#,(%\"xG\"\"\"-%'RootOfG6#,(*$)%#_ZG\"\"$F%F%F,F%F%F%F %-F'6#,**$)F,\"\"#F%F%*&F&F%F,F%F%F%F%*$)F&F3F%F%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "u3:=RootOf(%,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#u3G,&-%'RootOfG6#,(*$)%#_ZG\"\"$\"\"\"F.F,F.F.F.!\" \"-F'6#,**$)F,\"\"#F.F.*&F&F.F,F.F.F.F.*$)F&F5F.F.F/" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "(x-u)*(x-u2)*(x-u3);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#*(,(%\"xG\"\"\"-%'RootOfG6#,(*$)%#_ZG\"\"$F&F&F-F&F&F&F &-F(6#,**$)F-\"\"#F&F&*&F'F&F-F&F&F&F&*$)F'F4F&F&F&F&,&F%F&F/!\"\"F&,& F%F&F'F9F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "evala(Expand( %));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*$)%\"xG\"\"$\"\"\"F(F&F(F(F (" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 1 0" 0 } {VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }