diff options
Diffstat (limited to 'macros/generic/polexpr/polexpr-examples.tex')
-rw-r--r-- | macros/generic/polexpr/polexpr-examples.tex | 881 |
1 files changed, 881 insertions, 0 deletions
diff --git a/macros/generic/polexpr/polexpr-examples.tex b/macros/generic/polexpr/polexpr-examples.tex new file mode 100644 index 0000000000..fa2f330513 --- /dev/null +++ b/macros/generic/polexpr/polexpr-examples.tex @@ -0,0 +1,881 @@ +% -*- sentence-end-double-space: t -*- +\documentclass[a4paper,svgnames,dvipsnames,dvipdfmx]{article} +\usepackage{geometry} +\usepackage{shortvrb} +\usepackage{xcolor} +\usepackage{graphicx} +\usepackage{polexpr} +\usepackage{hyperref} +\usepackage{bookmark} +% \usepackage{amsmath} +\usepackage{framed} +\usepackage{newtxtext,newtxmath} +\title{\pkg{polexpr} root localization examples} +\author{Jean-François Burnol} +\date{To access the reference documentation:\\ +% faut-il vraiment le ./ ? + \texttt{texdoc} \href{run:./polexpr.html}{polexpr.html}} +%\usepackage{parskip} +\MakeShortVerb{\|} + +% Note 25 juin 2021 et 8 janvier 2022 pour polexpr-examples.tex +% +% Ceci est extrait quasi verbatim de xint.dtx +% +% Le code est pour LaTeX, pas pour Plain TeX. +% Prévu pour latex+dvipdfmx, et j'ai supprimé ajouts spécifiques pour +% pdflatex/xetex/lualatex en ce qui concerne les couleurs et polices. +% +% Regarding latex+dvipdfmx, a document with many more usage +% of everbatim* could run into color stack overflow problems +% Refer to xint.dtx for how this problem is avoided there +% via direct usage of \special rather than \color in the +% \everbatimxprehook + +% verbatim macros and environments +% ================================ +% +% June 2013, then October 2014. +% ----------------------------- +% +\makeatletter +\catcode`_ 11 +% some of my verbatim environments do not make the space active (\lverb e.g.). Then +% \do@noligs must be modified, \char`#1 must be followed by a space token, else, +% the `#1 expansion will swallow one space. +\def\do@noligs #1{% + \catcode`#1\active + \begingroup + \lccode`~`#1\relax + \lowercase{% + \endgroup\def~{\leavevmode\kern\z@\char`#1 }}% +} +% \lowast +% Pas forcément adapté à toutes les polices +\def\lowast{\raisebox{-.25\height}{*}} +\catcode`* 13 +\def\makestarlowast {\let*\lowast\catcode`\*\active}% +\catcode`* 12 + + +%--- straight quotes, added (finally...) Nov 2, 2014 +%--- obsolete with use of newtxtt 1.05, late 2014 +\begingroup\makeatletter + \catcode`\'\active + \catcode`\`\active +\@firstofone {\endgroup + \def\makequotesstraight{% assumes textcomp package +% à propos textcomp est automatique avec pdflatex depuis Février 2020 + \let`\textasciigrave + \let'\textquotesingle + \catcode39\active + \catcode96\active }% +} + +% \verb +% ===== +% Initially, June 2013, then Sep 9, 2014, and Oct 9-12 2014 +% +% pour les short verb |...| + +\def\MicroFont{\ttfamily\makestarlowast\makequotesstraight}% default +\def\verb +{% + \relax \ifmmode\else\leavevmode\null\fi + \bgroup + \let\do\@makeother \dospecials + \@ifstar{\@sverb}% unused + {\MicroFont + \catcode 32 10 \endlinechar 32 % allows to fetch across line breaks + \frenchspacing + \@@jfverb}% +}% +% Note (Oct 12, 2014): in the improbable situation a newlinechar is +% found in the ##1, \scantokens will convert this to an end of line in +% its "write" phase, which will be then ignored in its "read" phase due +% to \endlinechar-1. This also avoids possible creation of \par which +% would defeat \@@jfverb@@. Thus it is good. +\def\@@jfverb #1{% + \ifcat\noexpand#1\noexpand~\catcode`#1\active\fi +% No problem with the EOL for the line where the short verb delimiter stands. + \def\next ##1#1{% + \@vobeyspaces\everyeof{\relax}\endlinechar\m@ne + \expandafter\@@jfverb_a\scantokens\expandafter{##1}}% +% hack with \@empty to prevent brace stripping if catcodes have been +% frozen earlier, like in footnotes. + \next \@empty +} +% We don't want a \discretionary at the very start. +% But then an empty argument is forbidden! +\def\@@jfverb_a #1{#1\@@jfverb_b } + +\def\@@jfverb_b #1{\ifx\relax #1% + \egroup + \else +% \penalty\z@, or rather (Oct 11, 2014) but I then adjust the textwidth +% precisely: + \discretionary{\copy\SoftWrapIcon}{}{}% + #1\expandafter\@@jfverb_b\fi +} +% \SoftWrapIcon box for line-breaking using discretionaries +% ========================================================= +\DeclareFontFamily{U}{MdSymbolC}{} +\DeclareFontShape {U}{MdSymbolC}{m}{n}{<-> MdSymbolC-Regular}{} +\newbox\SoftWrapIcon +% Emacs/AUCTeX uses very strange comment-like highlighting for \usefont{U}... +\def\SetSoftWrapIcon{% + \global\setbox\SoftWrapIcon\hb@xt@\z@ + {\hb@xt@\fontdimen2\font + {\hss{\color{verbsoftwrapiconcolor}% + \usefont{U}{MdSymbolC}{m}{n}\char"97}\hss}% + \hss}% + } +\AtBeginDocument {{\ttfamily\SetSoftWrapIcon}}% + +\catcode`_ 8 +\makeatother + +% everbatim environment +% ===================== + +% October 13-14, 2014 +% Verbatim with an \everypar hook, mainly to have background color, followed by +% execution of the contents (not limited by a group-scope) + +\makeatletter +\catcode`_ 11 + +\def\everbatimtop {\MacroFont\small}% default +\let\everbatimbottom\empty +\let\everbatimhook\empty + +\def\everbatim {\s@everbatim\@everbatim } +\@namedef{everbatim*}{\s@everbatim\expandafter\@everbatimx\expandafter + {\the\newlinechar}} +\let\everbatimbgcolorcmd\empty +\def\everbatimeverypar{\strut + {\everbatimbgcolorcmd\vrule\@width\linewidth }% + \kern-\linewidth + \kern\everbatimindent } +\def\everbatimindent {\z@} +% voir plus loin atbegindocument + +\def\endeverbatim {\if@newlist \leavevmode\fi\endtrivlist } + +\@namedef{endeverbatim*}{\endeverbatim\aftergroup\everbatimundoparskip} +\def\everbatimundoparskip{\vbox{}\kern-\baselineskip\kern-\parskip} +% Note 25 juin 2021 +% On ne peut pas emboîter un everbatim à l'intérieur d'un everbatim +% ou un everbatim* à l'intérieur d'un everbatim*... +\def\s@everbatim {% +% \ineverbtrue + \everbatimtop % put there size changes + \topsep \z@skip + \partopsep \z@skip + \itemsep \z@skip + \parsep \z@skip + \parskip \z@skip + \lineskip \z@skip + \let\do\@makeother \dospecials + \let\do\do@noligs \verbatim@nolig@list + \makestarlowast + \makequotesstraight + \everbatimhook + \trivlist + \@topsepadd \z@skip + \item\relax + \leftskip \@totalleftmargin + \rightskip \z@skip + \parindent \z@ + \parfillskip\@flushglue + \parskip \z@skip + \@@par + \def\par{\leavevmode\null\@@par\pagebreak[1]}% + \everypar\expandafter{\the\everypar \unpenalty + \everbatimeverypar + \everypar \expandafter{\the\everypar\everbatimeverypar}% + }% + \obeylines \@vobeyspaces +} + +\begingroup +\lccode`X 13 +\catcode`X \active +\lccode`Y `* % this is because of \makestarlowast. +% I have to think whether this is useful: obviously if I were to provide +% everbatim and everbatim* in a package I wouldn't do that. +\catcode`Y \active +\catcode`| 0 \catcode`[ 1 \catcode`] 2 \catcode`* 12 +\catcode`{ 12 \catcode`} 12 |catcode`\\ 12 +|lowercase[|endgroup% both freezes catcodes and converts X to active ^^M +|def|@everbatim #1X#2\end{everbatim}% + [#2|end[everbatim]|everbatimbottom ] +|def|@everbatimx #1#2X#3\end{everbatimY}]% + {#3\end{everbatim*}% + \everbatimbottom + \newlinechar 13 +% execution as LaTeX code of contents + \everbatimxprehook + \scantokens {#3}% + \newlinechar #1\relax + \everbatimxposthook +}% + +% L'espace venant du endofline final mis par \scantokens sera inhibé si #3 se +% termine par un % ou un \x, etc... + +\let\everbatimxfgcolorcmd\empty +\def\everbatimxprehook {\colorlet{everbsavedcolor}{.}% + \everbatimxfgcolorcmd + \smallskip % pour polexpr-examples.tex + % à cause de problèmes avec les + % output en "display" + }% + +\def\everbatimxposthook {\color{everbsavedcolor}} + + +\catcode`_ 8 +\makeatother + +\newcommand\pkg[2][]{\if\relax\detokenize{#1}\relax + \href{https://www.ctan.org/pkg/#2}{#2}% + \else + \href{https://www.ctan.org/pkg/#1}{#2}% + \fi + } + +% Colors for \verb and everbatim +% \MacroFont and \MicroFont +% font size in verbatim blocks + +% \verb +%\colorlet{verbcolor}{DarkCyan} +\colorlet{verbcolor}{black} +\colorlet{verbsoftwrapiconcolor}{DarkBlue} +\def\MicroFont{\ttfamily%\color{verbcolor} + \makestarlowast\makequotesstraight}% + +% everbatim/everbatim* +\def\everbatimtop{\MacroFont\small} +% the \small is not in \MacroFont in case of a document with macrocode (doc.sty) +% and some customization is desired +%\colorlet{everbatimfgcolor}{Olive} +\colorlet{everbatimfgcolor}{DarkBlue} +\def\MacroFont{\ttfamily\color{everbatimfgcolor}} + +%\colorlet{everbatimbgcolor}{WhiteSmoke} +\colorlet{everbatimbgcolor}{Ivory} +\def\everbatimbgcolorcmd{\color{everbatimbgcolor}} + +%\colorlet{everbatimxfgcolor}{MidnightBlue} +\colorlet{everbatimxfgcolor}{OliveDrab} +\def\everbatimxfgcolorcmd{\color{everbatimxfgcolor}} + +% Notice that \macrocode uses \macro@font which stores the \MacroFont meaning +% in force at \begin{document}. But doc.sty's verbatim uses current \MacroFont +% not the meaning at \begin{document}. Comprenne qui pourra... + +\begin{document} +\maketitle + + +The package provides a parser |\poldef| of algebraic polynomial +expressions. + +Once defined, a polynomial is usable by its name either as a numerical +function in |\xintexpr/\xinteval|, or for additional polynomial +definitions, or as argument to the package macros. + +% The localization of +% real roots to arbitrary precision as well as the determination of all +% rational roots is implemented via such macros. + +% Since release |0.8|, polexpr extends the \pkg{xintexpr} +% syntax to recognize +% polynomials as a new variable type (and not only as functions). +% Functionality which previously was implemented via macros such as the +% computation of a greatest common divisor is now available directly in +% |\xintexpr|, |\xinteval| or |\poldef| via infix or functional +% syntax. + +This document illustrates root localization via usage of macros such as +|\PolToSturm| and |\PolSturmIsolateZeros| which implement the +\href{https://en.wikipedia.org/wiki/Sturm%27s_theorem}{Sturm theorem}: +\begin{itemize} +\item Root localization based on + \href{https://en.wikipedia.org/wiki/Sturm%27s_theorem}{Sturm theorem} was + added at release |0.4| (2018/02/16). +\item Ability to find all rational roots was added at release |0.7.2| + (2018/12/09). +\end{itemize} +As of |0.8| (2021/03/29), \pkg{polexpr} is usable with Plain \TeX\ and not +only with \LaTeX. The examples here use most of the time a syntax which works +with both. + +Copying-pasting from |pdf| the example source may lose formatting. +Formerly, they were included verbatim in the |html| documentation. Here +they are both rendered verbatim and got executed during the \LaTeX\ run +which created this |pdf| file, with the output shown after the source code. + +% Perhaps future releases will implement other approaches, which are known +% to be generically computationally more efficient, at least in high +% degrees, than the \href{https://en.wikipedia.org/wiki/Sturm%27s_theorem}{Sturm theorem} based approach. This is not +% immediate priority though (perhaps support of multivariate polynomials +% would be more important feature; or localization of complex roots). + +Regarding how polynomial coefficients are printed on the typeset page by +|\PolTypeset|: +\begin{itemize}\def\everbatimtop {\MacroFont}% sans le \small +\item The default for |\PolTypesetOne| is to use |\xintTeXsignedFrac| with + \LaTeX, |\xintTeXsignedOver| with Plain. See the \pkg{xintexpr} + documentation for a description of what these macros do. A sensible + definition is: +\begin{everbatim} + \def\PolTypesetOne#1{\PolDecToString{\xintREZ{#1}}}% +\end{everbatim} +% le \smallskip est ennuyeux ici + It means to use decimal notation, with perhaps a trailing denominator if the + argument is a fraction, and will suppress trailing zeros after the decimal + mark. + +\item + As these are expandable macros, they are usable to redefine + |\PolToExprCmd| as well: +\begin{everbatim} + \def\PolToExprCmd#1{\PolDecToString{\xintREZ{#1}}}% +\end{everbatim} +% le \smallskip est ennuyeux ici + This will customize the output of |\PolToExpr| (which a priori is + destined for writes to external files but may also be used on the typeset + page). +\end{itemize} + +With |\xintverbosetrue| in the \TeX\ source extra information relative +to the internal data manipulated by the macros will be written to the |.log| +file. + +\begin{framed} + Package macros related to root localization create (user-level) new + polynomials, or numeric variables, via a naming scheme using the given + |<sturmname>| as prefix. It is thus advisable to keep this + |<sturmname>| name-space separate from the one used to name polynomial or + scalar variables. +\end{framed} + +\begin{framed} + Regrettably all examples here use the condemnable |\PolToSturm{f}{f}| + practice which means that internally defined polynomials will use as prefix + the original polynomial name. This merge of namespaces may cause + overwriting previously defined data and may lead to hard-to-debug problems. +\end{framed} + + +\section{A first example} + + +In this example the polynomial is square-free. +\begin{everbatim*} + \poldef f(x) := x^7 - x^6 - 2x + 1; + + \PolToSturm{f}{f} + \PolSturmIsolateZeros{f} + The \PolTypeset{f} polynomial has \PolSturmNbOfIsolatedZeros{f} distinct real + roots which are located in the following intervals: + \PolPrintIntervals{f} +\end{everbatim*} + +\begin{everbatim*} + Here is the second root with ten more decimal digits: + \PolRefineInterval[10]{f}{2} + $$\PolSturmIsolatedZeroLeft{f}{2}<Z_2<\PolSturmIsolatedZeroRight{f}{2}$$ +\end{everbatim*} + +\begin{everbatim*} + And here is the first root with twenty digits after decimal mark: + \PolEnsureIntervalLength{f}{1}{-20} + $$\PolSturmIsolatedZeroLeft{f}{1}<Z_1<\PolSturmIsolatedZeroRight{f}{1}$$ +\end{everbatim*} + +\begin{everbatim*} + The first element of the Sturm chain has degree $\PolDegree{f_0}$. As + this is the original degreee $\PolDegree{f}$ we know that $f$ is square free. + Its derivative is up to a constant \PolTypeset{f_1} (in this example + it is identical with it). + \PolToSturm{f_1}{f_1}\PolSturmIsolateZeros{f_1}% + The derivative has \PolSturmNbOfIsolatedZeros{f_1} distinct real + roots: + \PolPrintIntervals[W]{f_1}% + \PolEnsureIntervalLengths{f_1}{-10}% + Here they are with ten digits after decimal mark: + \PolPrintIntervals[W]{f_1} +\end{everbatim*} + +\begin{everbatim*} + \PolDiff{f_1}{f''} + \PolToSturm{f''}{f''} + \PolSturmIsolateZeros{f''} + The second derivative is \PolTypeset{f''}. + It has \PolSturmNbOfIsolatedZeros{f''} distinct real + roots: + \PolPrintIntervals[X]{f''}% + Here is the positive one with 20 digits after decimal mark: + \PolEnsureIntervalLength{f''}{2}{-20}% + $$X_2 = \PolSturmIsolatedZeroLeft{f''}{2}\dots$$ +\end{everbatim*} +%The more mathematically advanced among our dear readers will be able +% to give the exact value for $X_2$! + +\section{A degree four polynomial with nearby roots} + + +Notice that this example is a bit outdated as |0.7| release has +added |\PolSturmIsolateZeros**{<sturmname>}| which would find exactly +the roots. The steps here retain their interest when one is interested +in finding isolating intervals for example to prepare some demonstration +of dichotomy method. + + +\begin{everbatim*} + \PolDef{Q}{(x-1.050001)(x-1.105001)(x-1.110501)(x-1.111051)} + \PolTypeset{Q} + \PolToSturm{Q}{Q} % it is allowed to use same prefix for Sturm chain + \PolSturmIsolateZeros{Q} + \PolPrintIntervals{Q} +\end{everbatim*} + +\begin{everbatim*} + \PolRefineInterval*{Q}{1} + \PolRefineInterval*{Q}{2} + \PolRefineInterval*{Q}{3} + \PolRefineInterval*{Q}{4} + \PolPrintIntervals{Q} +\end{everbatim*} + +\begin{everbatim*} + \PolEnsureIntervalLengths{Q}{-6} + \PolPrintIntervals{Q} + % finds here all roots exactly +\end{everbatim*} + +\section{The degree nine polynomial with 0.99, 0.999, 0.9999 as triple roots} + +Define a user command (\pkg[xint]{xinttools} is loaded automatically by +\pkg{polexpr}): + +\begin{everbatim*} + \def\showmultiplicities#1{% #1 = "sturmname" + \xintFor* ##1 in {\xintSeq{1}{\PolSturmNbOfIsolatedZeros{#1}}}\do{% + The multiplicity is \PolSturmIsolatedZeroMultiplicity{#1}{##1} + \PolSturmIfZeroExactlyKnown{#1}{##1}% + {at the root $x=\PolSturmIsolatedZeroLeft{#1}{##1}$} + {for the root such that + $\PolSturmIsolatedZeroLeft{#1}{##1}<x<\PolSturmIsolatedZeroRight{#1}{##1}$} + \par + }}% +\end{everbatim*} + +\begin{everbatim*} + \PolDef{f}{(x-0.99)^3(x-0.999)^3(x-0.9999)^3} + \def\PolTypesetOne#1{\PolDecToString{\xintREZ{#1}}} + \PolTypeset{f}\par +\end{everbatim*} + +\begin{everbatim*} + \PolToSturm{f}{f}% it is allowed to use "polname" as "sturmname" too + \PolSturmIsolateZerosAndGetMultiplicities{f}% use the "sturmname" here + % or \PolSturmIsolateZeros*{f} which is exactly the same, but shorter.. + + \showmultiplicities{f} +\end{everbatim*} +% In this example, the output will look like this (but using math mode):: + +% x^9 - 8.9667x^8 + 35.73400293x^7 - 83.070418400109x^6 + 124.143648875193123x^5 +% - 123.683070924326075877x^4 + 82.149260397553075617891x^3 +% - 35.07602992699900159127007x^2 + 8.7364078733314648368671733x +% - 0.967100824643585986488103299 + +% The multiplicity is 3 at the root x = 0.99 +% The multiplicity is 3 at the root x = 0.999 +% The multiplicity is 3 at the root x = 0.9999 + +% On first pass, these rational roots were found (due to their relative +% magnitudes, using |\PolSturmIsolateZeros**| was not needed here). But +% multiplicity computation works also with (decimal) roots not yet +% identified or with non-decimal or irrational roots. + +It is fun to modify only a tiny bit the polynomial and see if polexpr +survives: + +\begin{everbatim*} + \PolDef{g}{f(x)+1e-27} + \PolTypeset{g}\par + \PolToSturm{g}{g} + \PolSturmIsolateZeros*{g} + + \showmultiplicities{g} +\end{everbatim*} +% This produces:: + +% x^9 - 8.9667x^8 + 35.73400293x^7 - 83.070418400109x^6 + 124.143648875193123x^5 +% - 123.683070924326075877x^4 + 82.149260397553075617891x^3 +% - 35.07602992699900159127007x^2 + 8.7364078733314648368671733x +% - 0.967100824643585986488103298 + +% The multiplicity is 1 for the root such that 0.98 < x < 0.99 +% The multiplicity is 1 for the root such that 0.9991 < x < 0.9992 +% The multiplicity is 1 for the root such that 0.9997 < x < 0.9998 + +This means that the multiplicity-3 roots each became a real and a pair of +complex ones. Let's see them better: + +\begin{everbatim*} + \PolEnsureIntervalLengths{g}{-10} + + \showmultiplicities{g} +\end{everbatim*} +% which produces:: + +% The multiplicity is 1 for the root such that 0.9899888032 < x < 0.9899888033 +% The multiplicity is 1 for the root such that 0.9991447980 < x < 0.9991447981 +% The multiplicity is 1 for the root such that 0.9997663986 < x < 0.9997663987 + +\section{A degree five polynomial with three rational roots} + +\begin{everbatim*} + \poldef Q(x) := 1581755751184441 x^5 + -14907697165025339 x^4 + +48415668972339336 x^3 + -63952057791306264 x^2 + +46833913221154895 x + -49044360626280925; + + \PolToSturm{Q}{Q} + \def\PolTypesetCmdPrefix#1{\allowbreak\xintiiifSgn{#1}{}{+}{+}}% + $Q_0(x) = \PolTypeset{Q_0}$ + \PolSturmIsolateZeros**{Q} + \PolPrintIntervals{Q} + + $Q_{norr}(x) = \PolTypeset{Q_norr}$ +\end{everbatim*} + +Here, all real roots are rational. Let's get their decimal expansion too: +\begin{everbatim*} +\begingroup + % print decimal expansion of the found roots + \def\PolPrintIntervalsPrintExactZero + {\xintTrunc{20}{\PolPrintIntervalsTheLeftEndPoint}\dots} + \PolPrintIntervals{Q} +\endgroup % we localized the modified \PolPrintIntervalsPrintExactZero +\end{everbatim*} + + + % Z_1 = 3.14159265358107777120... + % Z_2 = 3.14159265358979340254... + % Z_3 = 3.14159292035398230088... + +\section{A Mignotte type polynomial} + + +\begin{everbatim*} + \PolDef{P}{x^10 - (10x-1)^2}% + \PolTypeset{P} % prints it in expanded form + \PolToSturm{P}{P} % we can use same prefix for Sturm chain + \PolSturmIsolateZeros{P} % finds 4 real roots + This polynomial has \PolSturmNbOfIsolatedZeros{P} distinct real roots: + \PolPrintIntervals{P}% +\end{everbatim*} +Let us refine the second and third intervals to separate the corresponding +roots: +\begin{everbatim*} + \PolRefineInterval*{P}{2}% will refine to 0.0999990 < Z_2 < 0.0999991 + \PolRefineInterval*{P}{3}% will refine to 0.100001 < Z_3 < 0.100002 + \PolPrintIntervals{P}% +\end{everbatim*} +Let us now get to know all roots with 10 digits after decimal mark: +\begin{everbatim*} + \PolEnsureIntervalLengths{P}{-10}% + \PolPrintIntervals{P}% now all roots are known 10 decimal digits after mark +\end{everbatim*} +Finally, we display 20 digits of the second root: +\begin{everbatim*} + \PolEnsureIntervalLength{P}{2}{-20}% makes Z_2 known with 20 digits after mark + $$\PolSturmIsolatedZeroLeft{P}{2}<Z_2<\PolSturmIsolatedZeroRight{P}{2}$$ +\end{everbatim*} +% The last line produces:: + +% 0.09999900004999650028 < Z_2 < 0.09999900004999650029 + +\section{The Wilkinson polynomial} + + +See \url{https://en.wikipedia.org/wiki/Wilkinson%27s_polynomial}. + + +\begin{everbatim*} + %\xintverbosetrue % for the curious... + + \poldef f(x) := mul((x - i), i = 1..20); + + \def\PolTypesetCmdPrefix#1{\allowbreak\xintiiifSgn{#1}{}{+}{+}}% + \def\PolTypesetOne#1{\xintDecToString{#1}}% + + \noindent\PolTypeset{f} + + \PolToSturm{f}{f} + \PolSturmIsolateZeros{f} + \PolPrintIntervals{f} + % \vfill\eject + + % This page is commented out because it takes about 30s on a 2GHz CPU + % \poldef g(x) := f(x) - 2**{-23} x**19; + + % \PolToSturm{g}{g} + % \noindent\PolTypeset{g_0}% integer coefficient primitive polynomial + + % \PolSturmIsolateZeros{g} + % \PolEnsureIntervalLengths{g}{-10} + + % \PolPrintIntervals*{g} +\end{everbatim*} + +The first polynomial +% +% f(x) = x**20 +% - 210 x**19 +% + 20615 x**18 +% - 1256850 x**17 +% + 53327946 x**16 +% - 1672280820 x**15 +% + 40171771630 x**14 +% - 756111184500 x**13 +% + 11310276995381 x**12 +% - 135585182899530 x**11 +% + 1307535010540395 x**10 +% - 10142299865511450 x**9 +% + 63030812099294896 x**8 +% - 311333643161390640 x**7 +% + 1206647803780373360 x**6 +% - 3599979517947607200 x**5 +% + 8037811822645051776 x**4 +% - 12870931245150988800 x**3 +% + 13803759753640704000 x**2 +% - 8752948036761600000 x +% + 2432902008176640000 +% +is handled fast enough, but the modified one |f(x) - +2**-23 x**19| takes about 20x longer. + +Its Sturm chain polynomials +have integer coefficients with up to 321 digits, whereas (surprisingly +perhaps) those of the Sturm chain polynomials derived from |f| never +have more than 21 digits ... + +Once the Sturm chain is computed and the zeros isolated, obtaining their +decimal digits is relatively faster. Here are the ten real roots of +|f(x) - 2**-23 x**19| which would be computed by the commented-out code above: +\begin{everbatim} + Z_1 = 0.9999999999... + Z_2 = 2.0000000000... + Z_3 = 2.9999999999... + Z_4 = 4.0000000002... + Z_5 = 4.9999999275... + Z_6 = 6.0000069439... + Z_7 = 6.9996972339... + Z_8 = 8.0072676034... + Z_9 = 8.9172502485... + Z_10 = 20.8469081014... +\end{everbatim} + +\section{The second Wilkinson polynomial} + + +\begin{everbatim*} + \poldef f(x) := mul(x - 2^-i, i = 1..20); + + %\PolTypeset{f} + + \PolToSturm{f}{f} + \PolSturmIsolateZeros**{f} + \PolPrintIntervals{f} +\end{everbatim*} + +This takes more time than the polynomial with 1, 2, .., 20 as roots but +less than the latter modified by the |2**-23| tiny change to one of its +coefficient. + +% Here is the output (with release 0.7.2):: + +% Z_1 = 0.00000095367431640625 +% Z_2 = 0.0000019073486328125 +% Z_3 = 0.000003814697265625 +% Z_4 = 0.00000762939453125 +% Z_5 = 0.0000152587890625 +% Z_6 = 0.000030517578125 +% Z_7 = 0.00006103515625 +% Z_8 = 0.0001220703125 +% Z_9 = 1/4096 +% Z_10 = 1/2048 +% Z_11 = 1/1024 +% Z_12 = 1/512 +% Z_13 = 1/256 +% Z_14 = 1/128 +% Z_15 = 0.015625 +% Z_16 = 0.03125 +% Z_17 = 0.0625 +% Z_18 = 0.125 +% Z_19 = 0.25 +% Z_20 = 0.5 + +There is some incoherence in output format which has its source in the +fact that some roots are found in branches which can only find decimal +roots, whereas some are found in branches which could find general +fractions and they use |\xintIrr| before storage of the found root. +This may evolve in future. + + +\section{The degree 41 polynomial with -2, -1.9, -1.8, ..., 0, 0.1, ..., 1.9, 2 as roots} + + + +\begin{everbatim*} + \PolDef{P}{mul((x-i*1e-1), i=-20..20)}% i/10 is same but less efficient +\end{everbatim*} +In the defining expression we could have used |i/10| but this gives +less efficient internal form for the coefficients (the |10|'s end up +in denominators). + +\begin{everbatim*} +\begingroup + \def\PolToExprCmd#1{\PolDecToString{\xintREZ{#1}}} + \def\PolToExprTermPrefix#1{\newline\xintiiifSgn{#1}{}{+}{+}} + \def\PolToExprTimes{${}\cdot{}$} +\ttfamily +\PolToExpr{P} +\endgroup +\end{everbatim*} + % x^41 + % -28.7*x^39 + % +375.7117*x^37 + % -2975.11006*x^35 + % +15935.28150578*x^33 + % -61167.527674162*x^31 + % +173944.259366417394*x^29 + % -373686.963560544648*x^27 + % +613012.0665016658846445*x^25 + % -771182.31133138163125495*x^23 + % +743263.86672885754888959569*x^21 + % -545609.076599482896371978698*x^19 + % +301748.325708943677229642930528*x^17 + % -123655.8987669450434698869844544*x^15 + % +36666.1782054884005855608205864192*x^13 + % -7607.85821367459445649518380016128*x^11 + % +1053.15135918687298508885950223794176*x^9 + % -90.6380005918141132650786081964032*x^7 + % +4.33701563847327366842552218288128*x^5 + % -0.0944770968420804735498178265088*x^3 + % +0.00059190121813899276854174416896*x + +which shows coefficients with up to 36 significant digits... + +Stress test: not a hard challenge to \pkg{xint} + \pkg{polexpr}, but be a bit +patient! + +\begin{everbatim*} + \PolDef{P}{mul((x-i*1e-1), i=-20..20)}% + \PolToSturm{P}{S} % dutifully computes S_0, ..., S_{41} + % the [1] optional argument limits the search to interval (-10,10) + \PolSturmIsolateZeros[1]{S} % finds *exactly* (but a bit slowly) all 41 roots! + \PolPrintIntervals{S} % nice, isn't it? +% Unfortunately \PolPrintIntervals uses a non-breakable array environment +% But see next section on how to customize \PolPrintIntervals and let it +% allow pagebreaks +\end{everbatim*} + +\begin{quote} + Release |0.5| has \emph{experimental} addition of optional argument |E| to + |\PolSturmIsolateZeros|. It instructs to search roots only in interval + |(-10^E, 10^E)|. Important: the extremities are \emph{assumed to not be roots}. + In this example, the |[1]| in |\PolSturmIsolateZeros[1]{S}| gives some speed + gain; without it, it turns out in this case that \pkg{polexpr} would have + started with |(-10^6, 10^6)| interval. + + Please note that this feature may be removed or modified. +\end{quote} + +\section{Roots of a Chebyshev polynomial} + + +\begin{everbatim*} + \poldef T_0(x) := 1; + \poldef T_1(x) := x; + \catcode`@ 11 + \count@ 2 + \xintloop + \poldef T_\the\count@(x) := + 2x*T_\the\numexpr\count@-1\relax + - T_\the\numexpr\count@-2\relax; + \ifnum\count@<15 + \advance\count@ 1 + \repeat + \catcode`@ 12 + + $$T_{15} = \PolTypeset[X]{T_15}$$ + \PolToSturm{T_15}{T_15} + \PolSturmIsolateZeros*{T_15}% "*" as we will want to confirm multiplicity one + % takes time (each next decimal digit is obtained by dichotomy) + \PolEnsureIntervalLengths{T_15}{-20}% ensure 20 decimal digits for each root +\end{everbatim*} + +Here is now an example of customization. Indeed +|\PolPrintIntervals| default uses |array| and thus does not allow page breaks. +And it uses |Left < Z < Right| as presentation of roots and we would like here +rather |Z = decimal expansion...|. +\begin{everbatim*} +% 0.8.6 adds an internal patch which would allow usage of amsmath environments +% like this: +% \def\PolPrintIntervalsBeginEnv{\begin{align*}} +% \def\PolPrintIntervalsEndEnv{\end{align*}} +% (the problem was that align evaluates twice its contents so global variables +% need a reset at the end of first pass, which is what 0.8.6 took care of) +% +% Let's simply do this: +\def\PolPrintIntervalsBeginEnv{\begingroup\leftskip3cm\relax} +\def\PolPrintIntervalsEndEnv{\par\endgroup} +% +% The rows are separated by \PolPrintIntervalsRowSeparator which defaults to \\ +% with LaTeX and \cr with Plain. (prior to 0.8.6 it was hardcoded) +\def\PolPrintIntervalsRowSeparator{\\[\jot]} +% And we enter math mode manually at each row, copying pasting from package +% defaults with some added mathon/mathoff: +\def\PolPrintIntervalsKnownRoot{% + $\PolPrintIntervalsPrintMultiplicity\quad + \PolPrintIntervalsTheVar_{\PolPrintIntervalsTheIndex}=% + \PolPrintIntervalsPrintExactZero + $ +}% +\def\PolPrintIntervalsUnknownRoot{% + $\PolPrintIntervalsPrintMultiplicity\quad + \xintifSgn{\PolPrintIntervalsTheLeftEndPoint}% + {\xintifSgn{\PolPrintIntervalsTheRightEndPoint} + {\PolPrintIntervalsTheVar_{\PolPrintIntervalsTheIndex}=% + \PolPrintIntervalsPrintRightEndPoint\dots}% + {0>\PolPrintIntervalsTheVar_{\PolPrintIntervalsTheIndex}>% + \PolPrintIntervalsPrintLeftEndPoint}% + {\impossibleA}}% + {\xintifSgn{\PolPrintIntervalsTheRightEndPoint} + {\impossibleB}% + {\impossibleC}% + {0<\PolPrintIntervalsTheVar_{\PolPrintIntervalsTheIndex}<% + \PolPrintIntervalsPrintRightEndPoint}}% + {\xintifSgn{\PolPrintIntervalsTheRightEndPoint} + {\impossibleD}% + {\impossibleE}% + {\PolPrintIntervalsTheVar_{\PolPrintIntervalsTheIndex}=% + \PolPrintIntervalsPrintLeftEndPoint\dots}}% + $ +}% +\PolPrintIntervals{T_15} +\end{everbatim*} +\end{document} + |