Partial Fraction Decomposition by Repeated Synthetic Division

Show more

Received 23 May 2016; accepted 24 June 2016; published 27 June 2016

1. Introduction

The case when the denominator is a power of a single linear factor has been treated in [2] and [5] .

Our method is built on top of their methods with the observation that when the denominator is of the form the partial fraction decomposition is trivial. The method does not use any derivatives and the computation involves only simple algebraic operations associated with repeated synthetic division. So the method is applicable to both hand and machine calculuations.

2. Partial Fraction Decomposition

We separate the case when from the case when. We will assume the factors in the denominator are monic since we can always factor out leading coefficients if necessary. We also assume that the degree of the numerator is less than the degree of the denominator for simplicity of presentation. However the method works in such a case with a little modification (by adding an extra step of back substitution in the end).

Case 1: The denominator is a product of and.

(1)

In this case, we find the constants backward from down to recursively using Heaviside cover-up method and synthetic division. By the Heaviside cover-up method, we get

Then we subtract the last term from Equation (1) to get

where is the quotient when is divided by, which is obtained by synthetic division with zero remainder. We repeat the process recursively to get all B_{i}’s.

where f_{i}'s are successive quotients from synthetic division. In the end, a function of the form is left. The

coefficient of are exactly.

Example 1. We demonstrate how to decompose the following function.

By the Heaviside cover-up method,

and subtract from, then we have

The numerator is divisible by, so we apply synthetic division to simplify the function and get

Repeat the process to get and, and we are left with

Then, and the answer is

The whole process can be done as shown in Table 1.

Remark 1. The remainder theorem says that the evaluation of can be done by synthetic division as it is equal to the remainder when is divided by. The method is also known as Horner's rule. For example, in Example 1 can be evaluated as follows.

Case 2: The denominator is a product of and with.

(2)

In this case, we take two steps. The first step is to make a substitution and expand in. Then the problem is reduced to Case 1. The second step is to solve the reduced problem.

We substitute the linear factor with a higher degree because it would reduce the amount of work in the second step.

We can get the coefficients of expanded in through repeated synthetic division [2] as

Note that is the remainder when is divided by, and is the remainder when the quotient is divided by, and so on.

The algorithm for this case is presented below for implementation in a computer.

Table 1. Synthetic Division for Example 1.

Algorithm

Input: numerator, denominator with

Output: partial fraction constants as in Equation (2)

Procedure: Step 1. Substitution

for to k

for to i

end for

end for

Step 2. Partial Fraction Decomposition

for to

for to i

end for

end for

for

Example 2. We show how the method works for the following function.

Let. We expand the numerator in to convert the problem to

Then apply the method in Case 1 to get the answer

The whole process is described in Table 2.

Table 2. Synthetic Division for Example 2.

Case 3. The denominator is a product of and with.

(3)

The method presented above also works when one of the factors in the denominator is a power of an irreducible quadratic function even though the computation could be challenging when it is done by hand.

The first step is to make a substitution. The next step is to find the constants B_{i}’s and C_{i}’s backward. It can be done using the quadratic divisor version of synthetic division. Once all constants are found, we get the solution by back substitution.

Let us elaborate on how to find and assuming. Multiplying both sides of Equation (3) by the denominator, we get

We reduce the right hand side modulo by sending it to the field . Modulo,

We reduce to a linear form using the quadratic version of synthetic division. The inverse of x is

and can be reduced to a linear form by expanding using

the repeated squaring method. Then we multiply two linear forms and reduce it again to finally get and. The same technique is described in examples in [4] when the denominator has factors of exponents 1 or 2.

Example 3. We demonstrate how the method works for the following function.

Let and. Then

The inverse of in is computed as follows.

Then the constants of the partial fractions are obtained as in Table 3 and give us

We get the final answer when we replace for u.

3. Computational Complexity

We count the number of operations required for the method described in this article as follows. The synthetic division requires n multiplications and n additions where n is the degree of the polynomial. In the substitution step, we perform

Table 3. Synthetic Division for Example 3.

multiplications and additions. In the second step of partial fraction decomposition, we use less number of synthetic divisions. For the evaluation of functions through synthetic division, the cost is the same. Therefore, the total computational cost is.

This method is not the best algorithm in terms of asymptotic speed as the algorithm in [8] is performed in steps. However, this method is still intersting because it uses only one technique (synthetic division) in the whole process and hand calculation is straightforward.

Acknowledgements

We thank the Editor and the referee for their comments.

References

[1] Ma, Y., Yu, J. and Wang, Y. (2014) Efficient Recursive Methods for Partial Fraction Expansion of General Rational Functions. Journal of Applied Mathematics, 2014, Article ID: 895036.

[2] Kung, S.H. (2006) Partial Fraction Decomposition by Division. The College Mathematics Journal, 37, 132-134.

http://dx.doi.org/10.2307/27646303

[3] Man, Y.K. (2007) A Simple Algorithm for Computing Partial Fraction Expansions with Multiple Poles. International Journal of Mathematical Education in Science and Technology, 38, 247-251.

http://dx.doi.org/10.1080/00207390500432337

[4] Man, Y.K. (2012) A Cover-Up Approach to Partial Fractions with Linear or Irreducible Quadratic Factors in the Denominators. Applied Mathematics and Computation, 219, 3855-3862.

http://dx.doi.org/10.1016/j.amc.2012.10.016

[5] Rose, D.A. (2007) Partial Fractions by Substitution. The College Mathematics Journal, 38, 145-147.

[6] Słota, D. and Wituła, R. (2005) Three Bricks Method of the Partial Fraction Decomposition of Some Type of Rational Expression. Lecture Notes in Computer Science, 3516, 659-662.

http://dx.doi.org/10.1007/11428862_89

[7] Wituła, R. and Słota, D. (2008) Partial Fractions Decompositions of Some Rational Functions. Applied Mathematics and Computation, 197, 328-336.

http://dx.doi.org/10.1016/j.amc.2007.07.048

[8] Kung, H.T. and Tong, D.M. (1977) Fast Algorithms for Partial Fraction Decomposition. SIAM: SIAM Journal on Computing, 6, 582-593.

http://dx.doi.org/10.1137/0206042