Riassunto esame Elementi di calcolo numerico, Prof. Antonini Mario, libro consigliato Numerical methods for engineers, Chapra, S., Canale, R

Algorithm for polynomial evaluation (monomial basis):

3 [ ( ) ]

() = ∑ = + + +

0 1 2 3

=0

and the p-code of the Horner’s algorithm is:

input: n, x, ai with i=0,...,n

Pv=an

for k=n-1 to 0 by(-1):

Pv=ak+Pv*x

output: Pv: value of P at x

(2)

The computational cost is .

Expressing the interpolating polynomial in different basis

Π

If the monomial basis of is adopted, we need to solve the linear system

=

to get the interpolating polynomial. This has a computational cost which significantly grows

when grows. Π

To solve this issue we adopt different basis of to express the interpolating polynomial.

There are two possibilites:

- the Lagrange basis

- the Newton basis →

= 0,...,

and they both depend on the interpolation abscissaes with this can help us

obtaining the interpolating polynomial in an easier way.

Lagrange basis: −

() = ∏ ℎ = 0,...,

−

,

=0,≠

( + 1) Π

These polynomials belong to since the product is done among linear terms.

They have the following cardinality property:

( )

= 0 ≠

- ,

( )

= 1 =

- ,

, = 0,...,

with .

Example:

= 3 = { 0, 1, 3, 10

}

let and interpolation abscissae.

Then the Lagrange basis are: (−1)(−3)(−10)

() = (0−1)(0−3)(0−10)

0,3 (−3)(−10)

() = (1−0)(1−3)(1−10)

1,3 (−1)(−10)

() = (3−0)(3−1)(3−10)

2,3 (−1)(−3)

() = (10−0)(10−1)(10−3)

3,3

Interpolating polynomial in Lagrange form:

with the Lagrange basis the interpolating polynomial that we already know that it exists and

is unique, can be written as follows:

() = ∑ · ()

,

=0

as the Lagrange form of the interpolating polynomial.

Actually the cardinality property of the Lagrange basis implies that

( ) ( )

= ∑ · =

,

=0

= 0,...,

with .

Algorithm for the evaluation of given in Lagrange form:

input x f

+ 1

(vector with entries equal to the interpolating abscissae), (vector with

xval

+ 1

equal to the values of at the interpolating abscissae), (abscissae where the

polynomial has to be evaluated)

Pval=0

for i=0,...,n

Lval=1 →

for j=0,...,n with (j!=i) product of Lagrange basis

Lval=Lval*(xval-x(j)) / (x(i)-x(j))

Pval=Pval+Lval*f(i)

output Pval

(value of the interpolating polynomial at )

2

( )

[ ( 4 + 2 ) ( + 1 ) ] ∼ 4

The computational cost is .

Conditioning of a problem

The conditioning of a problem is an important preliminary analysis that we apply to

→

approach each mathematical problem in the context of numerical analysis knowledge on

the sensibility of the problem to input perturbation and its outcome in the output.

In each problem we have:

→

- input data output result of

→

- perturbed input data perturbed output result of

The study of the conditioning of consists in determining the relation between the output

perturbation defined as | − |

and the input perturbation defined as ||| |||

−

More precisely we have interest in determining the conditioning number of which is an

amplification factor such that ||| |||

| − | ≤ · −

→

When is small or near 1 we have no amplification of the input perturbation the output

→

perturbation isn’t bigger than the input one in this condition we say that the problem is

well conditioned. Instead when is bigger than 1 we have a big amplification of the input

perturbation. In this case we can’t even ensure that the output perturbation will be in the

same order of magnitude of the input perturbation.

Note that when the relative input and output perturbation are well defined the study is

done with respect to them.

Let’s take for example in exam the case of conditioning of polynomial interpolation.

= 0,...,

Let be the perturbation of with .

Π

Let and be the two polynomials belonging to respectively such that

( )

=

( )

=

with ∈ [

, ]

= 0,...,

for .

Then ||| |||

−

∈[0,]

is the quantity we use to measure the input perturbation.

We are interested in deriving an upper-bound for the output perturbation

| ( ) − ( ) |

∈ [

, ]

holding true for each .

The idea to derive the upper-bound for the output perturbation is to use the Lagrange form.

| ( ) − ( ) |

We can write using the Lagrange form

() = ∑ · ()

,

=0

as

| |

( ) ||| |||

| |

| |

| ( ) − ( ) | = ∑ − () ≤ ∑ − () ⇒

| |

, ,

| |

=0 =0

||| |||λ

| ( ) − ( ) | ≤ − (

)

∈

[

0,

]

∈ [ , ]

with and | |

λ (

) = ∑ ( )

,

=0

is called the Lebesgue function, which is the sum of the absolute values of the Lagrange

polynomials. Because of the cardinality property of the Lagrange polynomials we have

( )

λ = 1

= 0,...,

for . This is due to the fact that all the Lagrange polynomials vanish at the

interpolation abscissae except the ones having the same index of the abscissae we are

evaluating them.

In general though we have

λ () ≥ ∑ () = 1

,

=0

The last inequality ||| |||λ

| ( ) − ( ) | ≤ − (

)

∈

[

0,

]

shows how the output perturbation is upper-bounded by the input perturbation multiplied

λ ()

by the Lebesgue function which, in this case, is the amplification factor .

Thus we can derive the upper-bound to the output perturbation with a form that’s not

depending on : ||| |||Λ

| ( ) − ( ) | ≤ − ∀ ∈ [

, ]

∈

[

0,

]

where | |

Λ = ∑ (

)

∈

[

,

] ,

=0

is called the Lebesgue constant, that is the maximum value that the Lebesgue function can

[ , ]

assume in the interval . This constant depends on but it also depends on the

= 0,..., [ , ]

distribution of the interpolation abscissas with in .

Thus the Lebesgue constant is the conditioning number of the polynomial interpolation

problem. If it is big, input perturbation can be easly amplified on the output.

Λ

It has been proved that diverges at least as a logarithm with respect to and, in the case

of uniform interpolation abscissas, it diverges exponentially with respect to .

Π

The Newton Basis of :

Π + 1

New basis for the space (polynomial of size )

In general it is defined with: () = 1

0

( )

() = () · − = 1,...,

with

−1 −1

This means that the general definition is

( ) ( ) ( )

() = ∏ − = − ·... · − = 1,...,

with

0 −1

<

with the principal coefficient of being equal to 1.

,...,

here is a polynomial with exact degree vanishing at . This implies that the

0 −1

Π

are basis of of incremental type like the monomial basis since each basis is obtained by

multiplying the previous with a constant: ( )

() = () · −

+1

Note that expressing the interpolating polynomial in the Newton basis is useful for dynamic

interpolation. →

Newton form of the interpolating polynomial how to express the interpolating

polynomial using a given function

∈ Π ,...,

Here we denote to be the polynomial interpolating the function at .

0

This means that () ≡ =

0 0 0

and in general we define the polynomial with the recursion

() = () + ()

−1

where ( )

−

−1

= ( )

which is well defined since the interpolation abscissas are distinct.

The demonstration is done by induction on , assuming that interpolates at with

−1

→

≤ − 1 ( ) = ( ) + 0 = ≤ − 1

with . This demonstration implies

−1

the definition of the Newton form of the interpolating polynomial:

() = ∑ ()

=0

which depends on the function and the interpolation abscissas. ,...,

We define the divided differences of order k related to the abscissas :

0

[ ]

= ,...,

0

with the generalization [ ]

,...,

+

The divided differences have several properties:

[ ] ( )

=

- (order 0)

( ) ( )

−

[ ] →

+1

, =

- (order 1) defined