Appunti di Calcolo numerico

NON

EQUAZIONI

Metodi per calcolo degli zeri di una funzione soluzioni

-2

f(x) Xxe[a b] soluzioni

Do

es

0

ovvero = -

↑ p

· i

, . soluzione

b

a a

a -

Teorema degli zeri 7 x c(a

f(x) (f(a) b))f(x4)

f(b)

continua > 0

<0 =

=

se · ,

di

dimostrazione elementare

riduzione

metodo

il (0 di binezional

can b

bi

chiamiano an a

= =

,

f)

ab

c = (Tob] se f(a) fac e

.

= Tan an] se f(ar) f(x) so

, .

a b x

c [b] refa) fano

= ·

- [a2 22] f(az) f(x) <0

x

, ·

: f(cr) *

xx

0 ck

=

= =

=

[anibr] [Cbr) se f(a) f(c)0

f)

-scr = + ·

Tar r] ref(a) f(x) so

·

M

N be

C

C2

j ·

I A

Ce

as P -

bz

ac A A

b3

a3 i

tolleranza *

tex-x

finché I

importe

si si eseguono k passeggi

& e

una br-ax [ (br ax-1)

fare In(b

(buz

perché a)

-an)

si pro =

=

= =

- -

... ,

1

- e a

fare

=an+ ban

ban e stabile miglice -

Cr nas e

= ,

I

può produrre un punto di

mezzo esterno all'intervallo Se

e

* cr+b)

br] -St(br-

cretan (Cr-S

étale che an

x I

: *

p

,

. Cx =

allora, fissata una tolleranza τ, il numero di passi necessari per ottenere un'approssimazione

c della soluzione x* con precisione τ è dato da:

k

10k *-8((bx I

((b

In a)

(b

ar) a)

x = =

- - -

- =

, simbolo: più piccolo intero superiore

-

· Flag

(c + (

a) t

(b k

x +

- -

- ,

= così so a priori quanti

approssimazione di x* passi devo fare

a meno di τ

If(c)l I

= di

dimostrazione il metodo Newton taugentil

delle

(o

can

f(x) b)

[a

=

x

0

= , Xr-

dato di Newton

metodo

12

0

xo Xnxi perk =

= , ...

,

#

la forwula

ricavare

x ing tangente

Mette

.

x2)

f(xk)(x

)

f(

ex

y =

- - f(x)

f(xx)(x

(3 f(x) xx)

=

- - f(xx)(x xx)

f(x)

=o xx

x

- =

=

- -

- f(xx)

0

y Il

= *

W

Xk 1

+ perché x è il punto

di intersezione

es :

t

(1 f(xx))

, funziona

qua

- vol

qua

-

N converge

-

f(x Frg(x) Xf(YT ocldx

* #

* *

g(=

0 x can

con

= - 1

/

problema del

punto fisso *,

*

g(x) *

fx4=

izero dif * *

* ) auto fine

d(x g(x dig

x x

sex x =

= = - Il

-

f(x)

* fissodig )f(x4)

* dif

quato =*d(x zere

e x

0

x 0 =

= = -

*

/ Xx-0(Xf(x)

P(x) convergente

g(x)

Xkte sia

cioe

cerco xx

= =

metade Nauton

di

del Ap

localet I

* derivabile

continua

= g(x)

g(x)

convergenza xx x

se

: +=

· ,

de angI )

xe(x *

* -y x

,

! 7y0((g(x))

) Xxe[x y]

* *

g(x *

0 1 +

x

= y

= ,

d(x)f(x) b(x)f(x)

↳ b(x)f(x)g(x)

g(x) 1

la funzione che soddisfa x =

= - -

- verificata

il teorema della è

- se

-

*

) )f(x)-

** #El

x P

g( )

*

convergenza locale è: 1- 4(x)=

Nendo

= e

)

*

(

I " ì-

xx-

X -

g(x)

Xen = f(x)f()

f(x)

f()g(x)

g(x) x =

= - -

f(x)2

e dunque, le ipotesi del teorema di convergenza locale del metodo delle

approssimazioni successive sono soddisfatte se: generati dal

iterati xx Neutou

metada di

Jycol Xxo[x

Ix ]

*

f(x) 3

di *

* soluzione 0 x

-f

↓ = ,

2"([x 9])

fe *

Hr *

2) x

-g **

(

+ x] x

,

. xx

x 9 -

=> - ,

Xxe[x ,

]

f(x)=0 * *

3) x +

-g , {xx} *

g(x) 0 e x

- con

converge

= a

velocità di convergenza

quadzatica

f"(x)

C

col Ix

= -

*

di

ordine convergenza

· {X ] ha

convergente ordine

*,

successione di Pre

convergente

x

a

*

IXk+ P

lim 0 < 1

x =

per

- C

-

x*Po >1

-01xx

k per

- basintotica

detta dell'errore

é a

a {xr] velocità di fineare

P ha

dice che

1 convergenza

= (Pradati

e

di

velocità

{x2}

che lineare

P dice ha convergenza

1 nupen 1

(

{En}, re {*3 *

*

10 x

2

P 0

C S 1

es 0 x =

=

= = =

-

-

= o -

. .

.

quadratica

lin e e i

ent e

c

= 1)

2 103

(0

102

en S S 0

0

S =

S

0 1 0

0 .

= .

= . .

= .

. .

.

. . 10-3= 18-3

Ec

lo

102) (S

(S

E 1 25

0 S

S

2 0

S

0 0 = .

. .

= = -

-

. . .

z . .

. . 10-

12 s lo-"

103) (1

(2 7

1 S 8

0 25

25

= 0 S S .

= =

= .

-

. .

- .

. . .

.

. 20

ên

10-3 -

0 10

3

en 6 25

= = .

: .

. 4, h2

10-3 10-

es 6

=

125 4

3

= e -

- .

.

I I

l'errore riduce la

velocemente quadratica

si più couvergenza

per

- ex ·

Li (del Neutou)

globale metodo di

convergenza

· intangenti

["([a

H siafe b) a

, ~ f(b))

(b

f(a)c0f(b)>

1) .

0

f(x)+0 b] P

xc[a

2) 8

, b

fatt int

concava No {xr3

Ux Nel

[a b]

. . ,

["([a

Ho siafe b)

,

f(a)c0f(b)>

1) 0

f(x)+0 b]

xc[a

2) ,

fatto int

convesse

wo

esempio un'applicazione del risultato di convergenza globale del metodo di Newton

è il calcolo di una radice quadrata di un numero.

Sia r tale numero, dobbiamo calcolare x*=√r. Avremo allora che x* è la

soluzione dell'equazione non lineare

~ il grafico di ƒ(x) è

Frc0x ⑲ l'arco di parabola

0

x = r =

- i (si conisdera solo

x>0) e a positivo,

f(x) molto vicino a 0

x r

= - f(al <0

f(b) 0

b >

allf(a))

If(a))- (b a

+

=

- I f(all

- +

x

Xkt x

Ea(ran-micara il diventa

rettangdo quadrato

più

· sempre con

un

tenderanno ad

ilati lunghezza

stessa

la di

avere K-b

r per co

* 1

k +

Metodo di Newton per il calcolo degli estremi liberi di una funzione

il metodo di Newton si può usare anche per minimi e massimi

.....

↳

⑧ e

E

⑧

CN ordine

privo

feC

sia f(x

* )

*

mim

x 0

se =

=

CN ordine

secondo

fe

sia f(x

f(x ) * )=0

* *

min D 0

x

se =

= ,

ordine

econdo

CS e

feC

sia fix f"(x

/ >0

*

)

* * minimo

x

cia x

0

x =

= ,

f(x) min(-f(x))

max =

f(x) mex( f(x)

min = - 3

2 - la del

Soddisfa

x CN

x 1° 20

↳ · e

la del

CS 20

· W and non

⑧

f 3x2 x3

2x 4

f 1272

6X

2 -f(x) 0

=

-

l'equazione del metodo di Newton per il calcolo di un punto di stazionarietà di ƒ è allora:

f(x)

Xx

Xx+ = - "(xx)

f CAPITOLO 6

MATRICI

Matrici, vettori e array: definizioni

matrice A di m righe e n colonne

X mxm

A ,

.

se m = n, si dice che la matrice è rettangolare

⑧ se m = n, si che la matrice è quadrata e di ordine n

⑳ i

[ais]

A l

= M

....,

per

=

· , =e

= m

....

A

I

elemento della A

matzica

3)

(i .

se tutti gli elementi sono nulli allora la matrice si dice nulla,

⑧ altrimenti si indica A 0

=

positiva se tutti gli elementi sono positivi ALO

dis>0 -

non negativa se tutti gli elementi sono positivi o nulli Al

ais ! 0 O

-

negativa se A co

dij0 -

non positiva se A

ais 0 0

b

-

se n = 1 si che che A è un vettore colonna a m componenti

X -

in generale, si chiama un vettore di n componenti, una n-pla

ordinata di numeri disposti su una colonna

X si chiama matrice trasposta di una matrice A (m x n) la matrice rettangolare n x m ottenuta

da A scambiando le righe con le colonne. AT- i

as S

per 1 1

=

: = m

m

..., ...,

In particolare, il vettore trasposto di un vettore colonna

è un vettore riga, che si indica con x T

- *

sia A una matrice m x n e sia k il più piccolo dei numeri m e n; k = min{m,n}. Gli elementi con

X indici uguali a , a , …, a formano la diagonale di A e si chiamano elementi diagonali di A. Se

11 22 kk

A è una matrice quadrata di ordine n, gli elementi diagonali a11, a22, …, a costituiscono la

nn

diagonale principale

assegnata una matrice A, m x n, si richiede di evidenziare alcune sue righe e colonne.

X La tabella costruita con gli elementi di A che giacciono sull'intersezione di queste righe e colonne è

ancora una matrice; tale matrice si chiama sottomatrice di A.

n e è una sottomatrice

ottenuta da A

-

-

sia considerando le

esempio -

- rige 2 e 4 e le

colonne 2, 3 e 5

-

L

data una matrice A, m x n, una sottomatrice composta dalle prime r righe e r colonne di A

⑳ con r ≤ min{m,n} si dice sottomatrice principale di A

una matrice A di dimensione m e n può essere scritta

X nella forma partizionata per colonne

oppure nella forma partizionata per righe

dove con a si è indicata la colonna di indice j di A

j

T

i

e con (a ) si è indicata la riga di indice i di A

X I

una matrice diagonale D di ordine n è una matrice i cui elementi d con i=j sono uguali a

ij

zero.

Gli elementi diagonali d si possono definire mediante un solo indice come d , per i=1, …, n,

ii i

dunque, una matrice diagonale D si può scrivere D=diag{d , d , …, d }

1 2 n

una particolare matri