OrderBasis - Maple Programming Help

Home : Support : Online Help : Mathematics : Linear Algebra : OrderBasis

OrderBasis

compute an order basis

 Calling Sequence OrderBasis([f1, f2, ..., fn], x, N, [d1, d2, ..., dn])

Parameters

 f1, ..., fn - expressions; represent the functions to be approximated x - variable appearing in the fis N - (optional) non-negative integer; specify the order of approximation. You must specify at least one of N or d1, ..., dn. d1, ..., dn - (optional) non-negative integers; specify the degree bounds. You must specify at least one of N or d1, ..., dn.

Description

 • The OrderBasis([f1, ..., fn], x, N, [d1, ..., dn]) command computes an order basis for the functions f1, ..., fn with respect to the variable x, the degrees d1, ..., dn, and the order N. It finds all polynomial coefficients that provide an identity of the form

$\mathrm{f1}\left(x\right)\mathrm{v1}\left(x\right)+\dots +\mathrm{fn}\left(x\right)\mathrm{vn}\left(x\right)=0$

 up to a certain number of terms and with the degree of each vi bounded. This is similar to what the IntegerRelations[PSLQ] algorithm does for finding integer relations for floating-point numbers.
 • More precisely, given functions fi assumed to have a series expansion about 0, the OrderBasis function returns a matrix whose columns provide a basis for the (mathematical) module defined by

$L=\left\{\left[\mathrm{v1}\left(x\right),...,\mathrm{vn}\left(x\right)\right]|\mathrm{f1}\left(x\right)\mathrm{v1}\left(x\right)+...+\mathrm{fn}\left(x\right)\mathrm{vn}\left(x\right)=\mathrm{O}\left({x}^{N}\right),\mathrm{degree}\left(\mathrm{v1}\right)\le \mathrm{d1},...,\mathrm{degree}\left(\mathrm{vn}\right)\le \mathrm{dn}\right\}$

 • That is, for every vector v of polynomials in L there exist n polynomials $\mathrm{a1},\mathrm{a2},\mathrm{#mo\left(…\right)},\mathrm{an}$

$v=\mathrm{a1}\left(x\right)\mathrm{column}\left(M,1\right)+\mathrm{a2}\left(x\right)\mathrm{column}\left(M,2\right)+\dots +\mathrm{an}\left(x\right)\mathrm{column}\left(M,n\right).$

 Here the degree of $\mathrm{ai}$ is bounded by $\mathrm{di}-\mathrm{degree}\left({M}_{i,i}\right)$.
 • If there are three arguments with the third argument as a positive integer N, that is, OrderBasis([f1, ..., fn], x, N), then the degree bounds d1, ..., dn are assumed to be N, ..., N.
 • If there are three arguments with the third argument as a list, that is, OrderBasis([f1, ..., fn], x, [d1, ..., dn]), then the order is determined by ${\mathrm{dn}}_{1}+\dots +{\mathrm{dn}}_{n}+n-1$.

Examples

 > $F≔\left[1+{x}^{2}-{x}^{7}+{x}^{12},\mathrm{sin}\left(x\right),{ⅇ}^{x}\right]:$
 > $M≔\mathrm{OrderBasis}\left(F,x,8,\left[3,1,2\right]\right)$
 ${M}{≔}\left[\begin{array}{ccc}{{x}}^{{4}}{+}\frac{{68238360}}{{4251353}}{}{{x}}^{{3}}{+}\frac{{511942344}}{{4251353}}{}{{x}}^{{2}}{+}\frac{{971729136}}{{4251353}}{}{x}{-}\frac{{2669976}}{{4251353}}& \frac{{2011699}}{{12754059}}{}{{x}}^{{3}}{-}\frac{{23128}}{{4251353}}{}{{x}}^{{2}}{-}\frac{{4252654}}{{4251353}}{}{x}{+}\frac{{34692}}{{4251353}}& \frac{{5533799}}{{12754059}}{}{{x}}^{{3}}{+}\frac{{17049452}}{{4251353}}{}{{x}}^{{2}}{+}\frac{{33708898}}{{4251353}}{}{x}{-}\frac{{66060}}{{4251353}}\\ \frac{{829819404}}{{4251353}}{+}\frac{{1293611160}{}{x}}{{4251353}}& {{x}}^{{2}}{-}\frac{{141659}}{{8502706}}{}{x}{+}\frac{{8421469}}{{8502706}}& \frac{{68785145}}{{8502706}}{+}\frac{{93799511}{}{x}}{{8502706}}\\ \frac{{2669976}}{{4251353}}{-}\frac{{1804218516}{}{x}}{{4251353}}& {-}\frac{{34692}}{{4251353}}{+}\frac{{153223}{}{x}}{{8502706}}& {{x}}^{{2}}{-}\frac{{136335061}}{{8502706}}{}{x}{+}\frac{{66060}}{{4251353}}\end{array}\right]$ (1)

Each column of $M$ has order 8.

 > $\mathrm{map}\left(\mathrm{series},\mathrm{map}\left(\mathrm{expand},\mathrm{.}\left(\mathrm{Matrix}\left(1,3,F\right),M\right)\right),x,8\right)$
 $\left[\begin{array}{ccc}{O}{}\left({{x}}^{{8}}\right)& {O}{}\left({{x}}^{{8}}\right)& {O}{}\left({{x}}^{{8}}\right)\end{array}\right]$ (2)
 > $\mathrm{map}\left(\mathrm{degree},M,x\right)$
 $\left[\begin{array}{ccc}{4}& {3}& {3}\\ {1}& {2}& {1}\\ {1}& {1}& {2}\end{array}\right]$ (3)

Implies that a basis for all $\left[\mathrm{v1},\mathrm{v2},\mathrm{v3}\right]$ satisfying $\mathrm{v1}{F}_{1}+\mathrm{v2}{F}_{2}+\mathrm{v3}{F}_{3}$ with $\mathrm{degree}\left(\mathrm{v1}\right)\le 3,\mathrm{degree}\left(\mathrm{v2}\right)\le 1,\mathrm{degree}\left(\mathrm{v3}\right)\le 2$ is a constant * column(M,3).

In the next example, OrderBasis(F,x,8) is the same as OrderBasis(F,x,8,[8,8,8]).

 > $M≔\mathrm{OrderBasis}\left(F,x,8\right)$
 ${M}{≔}\left[\begin{array}{ccc}{{x}}^{{3}}{-}\frac{{69384}}{{2011699}}{}{{x}}^{{2}}{-}\frac{{12757962}}{{2011699}}{}{x}{+}\frac{{104076}}{{2011699}}& {-}\frac{{40543788}}{{2011699}}{}{{x}}^{{2}}{-}\frac{{105266112}}{{2011699}}{}{x}{+}\frac{{464712}}{{2011699}}& \frac{{8097740}}{{2011699}}{}{{x}}^{{2}}{+}\frac{{21486216}}{{2011699}}{}{x}{-}\frac{{76416}}{{2011699}}\\ \frac{{12754059}}{{2011699}}{}{{x}}^{{2}}{-}\frac{{424977}}{{4023398}}{}{x}{+}\frac{{25264407}}{{4023398}}& {{x}}^{{3}}{+}\frac{{32425320}}{{2011699}}{}{{x}}^{{2}}{-}\frac{{95498640}}{{2011699}}{}{x}{-}\frac{{30079248}}{{2011699}}& {-}\frac{{5533799}}{{2011699}}{}{{x}}^{{2}}{+}\frac{{22284705}}{{2011699}}{}{x}{+}\frac{{10793304}}{{2011699}}\\ {-}\frac{{104076}}{{2011699}}{+}\frac{{459669}{}{x}}{{4023398}}& {-}\frac{{464712}}{{2011699}}{+}\frac{{135810072}{}{x}}{{2011699}}& {{x}}^{{2}}{-}\frac{{32355936}}{{2011699}}{}{x}{+}\frac{{76416}}{{2011699}}\end{array}\right]$ (4)

Each column of $M$ has order 8.

 > $\mathrm{map}\left(\mathrm{series},\mathrm{map}\left(\mathrm{expand},\mathrm{.}\left(\mathrm{Matrix}\left(1,3,F\right),M\right)\right),x,8\right)$
 $\left[\begin{array}{ccc}{O}{}\left({{x}}^{{8}}\right)& {O}{}\left({{x}}^{{8}}\right)& {O}{}\left({{x}}^{{8}}\right)\end{array}\right]$ (5)

References

 Beckermann, B., and Labahn, G. "Fraction-Free Computation of Matrix Rational Interpolants and Matrix GCDs." SIAM Journal on Matrix Analysis and Applications. Vol. 22 No. 1. (2000): 114-144.
 Beckermann, B. and Labahn, G. "A Uniform Approach for the Fast Computation of Matrix-Type Pade Approximants." SIAM Journal on Matrix Analysis and Applications. Vol. 15 No. 3. (1994): 804-823.