Metodi matematici e numerici - parte 3

(K)

PROP autovettore

✗ 1

Per K-O ¼ autovalore di modulo max

8'"

Dim Supponiamo A diagonaliz. e sia ✗ =L ☒ m) matrice di autovettori di A

1 (formano una base)

⇒ 9'" = È, di Xi

Ora 7"" = A.gl"-1) A"! q" = A"È di Xi -È di -✗ i =

k

" α:( i

= di ✗ i

¼ (✗ e + 21 (K)

1

2

1 di ¼:[✗ i

✗ "

"= 2 α,

1=2

Quindi: de di (X, + YCK')

9ᵗʰ' 2- "

"

112111112 = /del 1111" 11×1 + Y'

"112

Si nota che: essendo di

y "

"= È, 2:(÷)? ✗

i " µ < 1

K-> A

⇒ per (autovettore "normalizzato")

g (K) α ✗ 1

11×1112

K → A

Infine: ✗

I 11 ✗ 1 = di Xt te

s'"= (9111)! A. (k) ser ✗ e#A ✗ 1 Il ✗ 1112

Il Xell?

K > a Il ✗

ella'

9 (K) , 1

dove 11×1112 = 1 ✓

11×1112

DEF QA (X) = ✗ * • UOZIENTE DI RAYLEIGH

✗ è detto

Il ✗ 112 ☆ AEC" " ∀ ✗ EG"" 31/10

VELOCITÀ DI CONVERGENZA 91K) K

(K) la

⇒ 11 7ᵗʰ xelli ≤ e

∃ C > 0 (numero) E. C. posto § - α" 11

1

velocità di convergenza data dal rapporto tra dadi, cioè + il gap è alto più velocem. è la convergenza

Dim scegliamo un autovalore ✗ e t.ci. Il ✗

ella = 1 k.­ ✗ autovettore­

ee

(K)

9ᵗʰ ← + È

e osserviamo che • ✗ EVILI

✗ 1 I ✗ i

di

¼ "

✗

.-¥11

In particolare posso scegliere ∀; il Xill, = 1 I

11×111 = 11×

e vale che 11g""-✗ 1112 = Il ✗ "

"1122 11×11

K

i • Il ✗ illa

≤.È α. = 1

21 11

n K

- di i

- È 21 11 K - ch" ✓

≤" di 2

È 21 11 C (> 0 poiché somma di moduli)

METODO HOUSEHOLDER (o QR) per il calcolo di tutti gli autovalori

Ci chiediamo come trovare tutti gli autovalori

sia AE È" e scomponiamo come segue:

A- Q'"- R'" = T'°'

unitaria triangolare sup

Costruisco la matrice: + (1) = R". q"' DEF ∃ D invertibile t.ci

sono motrici

05s T' "e T" SIMILI T"' = D'1. T'°! D

Se Q"" *. T'°' = q"' * '°' 120' = R"'

⇒ T'

"= R'" Q" Q"" T'"Q"= 5' T'"D

1? -1

R'

"= (Q'91T"

Da T'% '

"R"'⇒ def MATRICI SIMILI

Q"

'

Osserviamo che MATR. SIMILI hanno gli stessi autovalori

(T'0,7'" hanno gli stessi autovalori di A)

RIFATTORIZZO

Posso iterare +" = R'°' '°' al" R"

- ① (2) 212)

+ (2) (1) ① (1)

R

+ (3) TIKI} che sono simili

Sto costruendo una sequenza e che hanno

gli stessi autovalori e autovettori della matrice iniziale di T'" - A .

finale è trovare T'" per cui il calcolo degli autovalori

L'obiettivo

più

sia semplice che per A.

Nel caso dei REALI IR (converg. del metodo householder)

A E R" " 1 del > 1 di/ > / 131 > _. _> 1dm/ autovalori distinti

Si dimostra che: di tela O - T(A)

te'

(K)

lim T

K-> O O antii. (A)

a

sono

i cui autovalori (sulla diagonale) 1- tu, -- , In = tnn

Oss (a) se AE 6"" allora * è sempre simile ad una motrice in

forma di Hessemberg ah 0

a:

Ay = 0 anima.'mi

(b) A simmetrica o Hermitiana ⇒ A è simile ad una tridiagonale

CAP 3- RISOLUZIONE DI EQ. NI NON LINEARI

3. 1) ZERI DI FUNZIONI

Consideriamo funzioni f:[0,5]- A e assumiamo il problema di

trovare ✗ ∈ [2,5] t.ci. fCX)-0 , che sono detti ZERI dif

ES (i) flax + b) lineari

⇒ fai-0 ½

(2) fix) - loga) ⇒ flx) =D ⇔ log (x)-0 ✗ =/

In generale eq. mi non lineari sono risolvibili solo tramite metodi ITERATIVI

L'obiettivo è costruire una sequenza ✗ '

" t.ci.

KEIN

lim e f. (d) = 0 con LE [a, b]

✗

' " '=D

K-> A

DEFINIZ. di convergenza per tali problemi

è detta CONVERGENTE se:

Una success ione {×'"/KEN

∀ K > È [> 0 f. c. , ✗ (Rte)-α / ≤ c

∃ ✗

' "121'

l

LEIN ORDINE DI CONVERGENZA (≥ 1) E IRT

In tal caso p è detto

• Nel caso p-1 si ha convergenza solo per CL1.

Consideriamo il problema associato

FIX, d) = O ⇒ FCX, d) = 6/×)-1=0

FIX)

In tal caso: K (d) = Idl no di condizionamento

121/ 84211

1 n° di condizionamento

Kabsld) = 8' call assoluto

Si hanno 3 casi

I) Kabs 21 1 ~ e ⇔ 181121/21

18 'call

fla) ACX) buona corrispondenza tra

l'errore nel dato e nella soluzione

(avranno stesso ordine)

II) Kass» 1 cioè al limite 1 → 1 ⇔ / fica)/≈ o

181211

Cattiva corrispondenza!

FIX)

If '

(2)

1=0 Piccoli errori nei dati

grandi errori nella soluzione

ci sembra che siamo vicini alla soluz.

ma in realtà siamo lontani da α

#) Kass ≈ 0 ⇔ 1 - ◦ ⇔ 18421/≈ + a

18'

CLIT

Δ situazione intermedia

Grandi errori nei dati non

modifica sensibilmente la soluzione

sembra di essere lontani

dalla soluz., invece siamo abbastanza

vicini ad α

PROBLEMA MAL CONDIZIONATO: RICERCA DI RADICI MULTIPLE

Sia 1:[a. b) → R e LE C" [a, b] . Sia MCK m

DERIVATA

poniamo fief , gh'=p' 1121=8", _ , f.

'm'= f'""

I

DEF Un p.to LE [a, b] è detta una radice di molteplicità m

se: 8º (a) = f' " (α) = - f'"-" (a) =D

- ~

e f" (L) ≠ 0

ESEMPIO - Sia f(✗ 1=12

allora: '

fix)-2x derivata prima di fix) = ×' ⇒ f'

(O) = O

f. (a) = 0 " (x) = 2 ≠ 0

8

⇒ ⇔

OSS α è RADICE MULTIPLA in fix) = 0

per il problema equivalente 4 (X) =D

α è radice multipla

ora = U(✗ + Sx) =

di Sd sviluppo in serie di Taylor per d-

×

= via) + È "

'

" (α) (✗ + Sx-a)

"+ ◦ (Sam)

k!

tutte le altre 442) fino a m-1 sono nulle! Solo 4%)

d + Sd = d + " " "

(a) (821m

⇒ ⇒

m!

ai:

⇒ Sd = Fm

(821m ↔ Sa = m! Sd

m! cià

3. 1) METODO DI BISEZIONE - Approccio geometrico ✗ la ricerca di radici

sia f:[a. b) → R continua

TEOR: Se f. è continua e feat- f. (b) LO allora

∃ E ∈ 30,5 [ te. f (E) =D

STEP 0 → Si scelgono a e b t.ci. fla). f(b) LO ✗

⇒ 2'" = a ; b'E b ; ✗ 'a) = a'°' + b'" 1

2 0º 6º

p.to medio

Si hanno 3 casi: O

1. fCX'") = O ⇔ > Fine algoritmo

✗ è lo zero cercato

2. fla") - f/×") co ⇒ a'" = a/0) ⇒ Tra ② °) e (o) ci sarà

b'" = ✗ COI radice

(I

1)

3. f/ ✗ °) - f/ 5º) co ⇒ al" = ✗ '°' ⇒ Tra ✗ '°' e b'" ci sarà

radice

b. ' "= b"

Iterando la procedura → Metodo globalmente conveniente

✗ ' " a" + b"

" ma lento

2

" FIK)/ 310)- a")

l

(K) =

= [a"', b 1 = b'k'-a'" 2kt I

2

per K-> A III O

L'errore: /e'"/ = /✗ '

"1- 2/ ⇐ b'"-×"

= 6'") ACRI - SIK)

b"? _acri faccio a metà i nuovi estremi

2 oppure

b"?-a 101 → faccio a metà

2kt/ gli estremi di partenza

pertanto li:>, / E'

"/ ✗

'

"I α sempre

=D ⇒ Lim

K-> A

Sia f:[a. b) → f ∈ C' [a, b] e sia α ETAS]: fla)-o

per un noto teorema = O

∃ ∈ [9,5] / fix/= fla) + L' (E) (×-α)

Σ

quindi fix) = 8' (E) (x-a) ⇒ α = ×- 1"

L'

(E)

Assumiamo che la successione E' " approssimi Ee in modo che

fix"/= 8'/E'

"/(✗ "

"-α) Forma generale di

✗ '

"+ "= ×'½ 8/×'") iterazione non lineare

8' (E'")

= 4 (×'") L' (EIN)

Ma si deve avere che ×'" → α ⇒ devo definire

3. 1. 2) METODO DELLE CORDE (9" fisso non dipende. dall'iteraz.)

f'/E'") = 8lb)-fla)

9'"- (a, feat)

b- a y

coeff angolare della retta ✗ '°)

per la, flat) e (b, feb)) ✗

b

fa'")

L'iterazione è: (b, f (b))

(KM)

✗ (K) b- a . f. (x'Kl)

8lb)-fa,

METODO DELLE SECANTI

91" = 841" )-f(✗ CK-11)

✗ (K) - ✗ (K-1)

In questo caso 9'"' (il coeff. angolare) varia nelle iterazioni.

cui far passare la 1ª

Bisogna scegliere 2 p. ti iniziali ×"" e ✗

'

"da retta

L'iteraz. sarà ✗ (Rte) ✗ (K) /(K) (K-11

A/×'")-fece-1, & (×")

Se f(×'") - f (×"-11) > o raggiungere convergenza è difficile

TEOR Sia f. ∈ È [aib], f" (2) ≠ 0 e Xo, Xi sono

abbastanza vicini ad α , allora il metodo converge

ad α di ordine p - 4 = 1+55 = 1,61_..

2

METODO DELLA FALSA POSIZIONE

È una modifica al metodo delle secanti

Supponiamo la) - f(b) Lo allora introduciamo

f

∀ ✗ "

" un valore ✗ ' "

"arbitrario per cui

f (×'") -f (✗

'1K' ) co

e quindi definisco: 8 (✗ "1) - f (✗ (k)

91kt _ ✗ (K) - \, (k)

Il metodo converge sempre di ordine p = 1

METODO DI NEWTON ◦ delle Tangenti

9""= f' (✗ CM)

Iterazione (KH) (K) 1

7

'cin, fixing

Se converge, questo metodo è + veloce risp a gli altri

La convergenza diventa p = 2

METODI A PUNTO FISSO UCX) -d

Siamo da FCx, d) = o =D

partiti (⇒ FCA)

Un problema si dice DI PUNTO Fisso se è della forma

① (X)