Numeric Algorithms
Download
Report
Transcript Numeric Algorithms
Calculating Polynomials
• We will use a generic polynomial form
of:
n
n1
p( x) an x an1x
a1xa0
where the coefficient values are known
constants
• The value of x will be the input and the
result is the value of the polynomial
using this x value
1
Standard Evaluation Algorithm
result = a[0] + a[1]*x
xPower = x
for i = 2 to n do
xPower = xPower * x
result = result + a[i]*xPower
end for
return result
2
Analysis
• Before the loop, there is
– One multiplication
– One addition
• The for loop is done N-1 times
– There are two multiplications in the loop
– There is one addition in the loop
• There are a total of
– 2N – 1 multiplications
– N additions
3
Horner’s Method
• Based on the factorization of a polynomial
• The generic equation is factored as:
p( x) an xan1 * xan2 * xa2 * xa1 * xa0
• For example, the equation:
p( x) x35 x 2 7 x4
• would be factored as:
p( x) x5* x7* x4
4
Horner’s Method Algorithm
result = a[n]
for i = n - 1 down to 0 do
result = result * x
result = result + a[i]
end for
return result
5
Analysis
• The for loop is done N times
– There is one multiplication in the loop
– There is one addition in the loop
• There are a total of
– N multiplications
– N additions
• Saves N – 1 multiplications over the
standard algorithm
6
Preprocessed Coefficients
• Uses a factorization of a polynomial
based on polynomials of about half the
original polynomial’s degree
• For example, where the standard
algorithm would do 255 multiplications
to calculate x256, we could square x and
then square the result seven more times
to get the same result
7
Preprocessed Coefficients
• Used with polynomials that are monic
(an=1) and have a highest power that is
one less than a power of 2
• If the polynomial has highest power that
is 2k – 1, we can factor it as:
p( x) x j b * q( x) r ( x)
where j = 2k-1
8
Preprocessed Coefficients
• If we choose b so that it is aj-1 – 1, q(x)
and r(x) will both be monic, and so the
process can be recursively applied to
them as well
9
Preprocessed Coefficients Example
• For the example equation of:
p( x) x35 x 2 7 x4
because the highest degree is 3 = 22 –1,
j would be 21 = 2, and b would have a
value of a1 – 1 = 6
• This makes one factor x2 + 6, and we
divide p(x) by this polynomial to find q(x)
and r(x)
10
Preprocessed Coefficients Example
• The division is:
x2 6
x5
x3 5 x 2 7 x 4
x3 5 x 2 6 x 30
x 26
which gives
p( x) x 2 6 * x5x26
11
Analysis
• We analyze preprocessed coefficients
by developing recurrence relations for
the number of multiplications and
additions
• In the factorization, we break the
polynomial up into two smaller
polynomials and do one additional
multiplication and two additional
additions
12
Analysis
• Because we required that N = 2k – 1, we
get:
M(1) = 0
M(k) = 2M(k–1) + 1
A(1) = 0
A(k) = 2A(k–1) + 2
• Solving these equations gives about N/2
multiplications and (3N – 1)/2 additions
• We need to include the k – 1 (or lg N)
multiplications needed to calculate the
series of values x2, x4, x8, …
13
Polynomial Algorithm Comparison
• For the example polynomial:
– Standard algorithm:
• 5 multiplications and 3 additions
– Horner’s method
• 3 multiplications and 3 additions
– Preprocessed coefficients
• 2 multiplications and 4 additions
14
Polynomial Algorithm Comparison
• In general, for a polynomial of degree N:
– Standard algorithm:
• 2N – 1 multiplications and N additions
– Horner’s method
• N multiplications and N additions
– Preprocessed coefficients
• N/2 + lg N multiplications and (3N – 1)/2 additions
15
Linear Equations
• A system of linear equations is a
set of N equations in N unknowns:
a11x1 + a12x2 + a13x3 + … + a1NxN = b1
a21x1 + a22x2 + aa3x3 + … + a2NxN = b2
aNx1 + aN2x2 + aN3x3 + … + aNNxN = bN
16
Linear Equations
• When these equations are used, the
coefficients (a values) are constants
and the results (b values) are typically
input values
• We want to determine the x values that
satisfy these equations and produce the
indicated results
17
Linear Equation Example
• An example set of linear equations with
three unknowns is:
2x1 – 4x2 + 6x3 = 14
6x1 – 6x2 + 6x3 = 24
4x1 + 2x2 + 2x3 = 18
18
Solving Linear Equations
• One method to determine a solution
would be to substitute one equation into
another
• For example, we solve the first equation
for x1 and then substitute this into the
rest of the equations
• This substitution reduces the number of
unknowns and equations
19
Solving Linear Equations
• If we repeat this, we get to one
unknown and one equation and can
then back up to get the values of the
rest
• If there are many equations, this
process can be time consuming, prone
to error, and is not easily computerized
20
Gauss-Jordan Method
• This method is based on the previous idea
• We store the equation constants in a
matrix with N rows and N+1 columns
• For the example, we would get:
2 -4 6 14
6 -6 6 24
4 2 2 18
21
Gauss-Jordan Method
• We perform operations on the rows until
we eventually have the identity matrix in
the first N columns and then the
unknown values will be in the final
column:
1 0 0 x1
0 1 0 x2
0 0 1 x3
22
Gauss-Jordan Method
• On each pass, we pick a new row and
divide it by the first element that is not
zero
• We then subtract multiples of this row
from all of the others to create all zeros
in a column except in this row
• When we have done this N times, each
row will have one value of 1 and the last
column will have the unknown values
23
Example
• Consider the example again:
2 -4 6 14
6 -6 6 24
4 2 2 18
• We begin by dividing the first row by 2,
and then subtract 6 times it from the
second row and 4 times it from the third
row
24
Example
1
0
0
-2 3
7
6 -12 -18
10 -10 -10
• Now, we divide the second row by 6,
and then subtract -2 times it from the
first row and 10 times it from the third
row
25
Example
1
0
0
0
1
0
-1 1
-2 -3
10 20
• Now, we divide the third row by 10, and
then subtract -1 times it from the first
row and -2 times it from the second row
26
Example
• This gives the result of:
1
0
0
0
1
0
0
0
1
3
1
2
• And we have that x1 = 3, x2 = 1, and
x3 = 2
27