Appunti di calcolo numerico

Metodo di Newton

• Sia f una funzione derivabile su [a, b], considero quindi l'equazione della tangente di f in x_k, ovvero:

y = f(x_k) + (x - x_k) · f'(x_k)

• Come punto x_k+1 considero il punto di intersezione delle rette tangente con l'asse delle ascisse.
• Imponendo questa condizione si ottiene la formula del metodo di Newton

x_k+1 = x_k - f(x_k) / f'(x_k)

e quindi per approssimare f in x_k+1

Condizioni per la convergenza globale del metodo di Newton

Teorema?: sia f ∈ C²[a, b], intervallo chiuso e limitato, inoltre

1. f(a)·f(b) < 0
2. f'(x) ≠ 0    ∀x ∈ [a, b]
3. f''(x) > 0    oppure    f''(x) < 0    ∀x ∈ [a, b]

|f(a) / f'(a)| < b - a   e   |f(b) / f'(b)| < b - a

• Allora il metodo converge all'unica soluzione ξ ∈ [a, b], ξ ∈ [a, b]

• Se x₀ è preso "sufficientemente" vicino alla radice α, con f'(α) ≠ 0, allora
• il metodo converge almeno quadraticamente e si ha

lim_{k → ∞} (x_k+1 - α) / (x_k - α)² = f''(α) / 2f'(α)

• se f''(α) ≠ 0    Il metodo converge quadraticamente
• se f''(α) = 0    Il metodo converge con ordine maggiore di 2

Metodo di Newton per funzioni con radici multiple

• funzione del tipo f(x)=(x-a)^mh(x) m=molteplicità

si ha: g'(x)=¹/_{1-m·(h(x)^'(x-a)+h(x)}

quindi g'(x)=1-^ψ(x)/_ψ'(x)

con x=a ottengo: g'(a)=1-¹/_m

• se m=1 ➜ g'(a)=0
• se m>1 ➜ g'(a)=1-¹/_m≠0

e infine si ha g(x)=x-m^f(x)/_f'(x)

!

se x_k con k≥2

• x_k=^x_k-x_k-1/_xk-1-xk-2

Esempio: calcolo di radice quadrata

• f(x)=x²-q, x>0, x∈R⁺ ➜ ha soluzione x=√q

x_k+1=^x_k2-q/_2xk

• Nel caso generale

x= q^1/n