Equazioni non lineari

Equazioni non lineari

Antonino Polimeno

Universit`a degli Studi di Padova

Equazioni non lineari - 1

Dato il sistema di n equazioni in n incognite (reali o complesse) f(x) = 0

si vogliono trovare una o pi`u soluzioni, cio`e vettori x che verifichino il sistema.

Equazioni non lineari - 2

I Le soluzioni, se esistono, si possono trovare con metodi numerici

I Il caso dei sistemi di equazioni lineari `e stato gi`a considerato

I Le difficolt`a intrinseche del problema di trovare le soluzioni (o

’radici’) del sistema sono diverse se il problema `e

monodimensionale (una sola equazione) o multidimensionale.

I Nel primo caso `e possibile praticamente sempre trovare soluzioni accurate in una dato intervallo [a, b]

I Nel secondo la ricerca di alcune delle possibili radici in un dominio generico D pu`o essere molto complicata e computazionalmente ’difficile’.

Titolo

Esempi:

I Determinazione delle propriet`a di una sostanza data una funzione di stato

I Calcolo delle attivit`a delle specie chimiche in un reattore in cui siano presenti uno o pi`u processi stechiometrici indipendenti

I Determinazione dei luoghi dei punti nodali (punti, piani etc.) di orbitali elettronici o molecolari

I richiede il calcolo degli zeri delle funzioni che descrivono le funzioni d’onda orbitaliche

Esempio 1

Calcolo del volume occupato da 1 mole di CO₂, descritta dall’equazione di van der Waals, ad 1 atm e 300 K.

L’equazione:

V_m³ −RT + pb

p V_m² +a

pV_m−ab p = 0 ammette tre soluzioni.

I polinomiale di III grado risolvibile analiticamente

I una sola soluzione `e reale e coincide con il volume molare. Per i parametri dati si ottiene Vm= 23.98 L mol⁻¹.

Esempio 2

Calcolo del pH di un acido debole monoprotico HA, di molarit`a m<sub>A</sub> per un volume VA mescolato a un volume VB di una soluzione acquosa di una base debole B, di molarit`a mB.

HA + H₂O −−*)−− A⁻+ H₃O⁺ KA= ^[A

−][H₃O⁺] [HA]

B + H₂O −−*)−− BH⁺+ OH⁻ KB = ^[BH+][OH

−] [B]

2 H₂O −−*)−− H3O⁺+ OH⁻ K_w = [H₃O⁺][OH⁻]

I Valgono i bilanci di massa rispetto alle specie A e B, (VA+ VB)([HA] + [A⁻]) = VAmA

(V_A+ V_B)([B] + [BH⁺]) = V_Bm_B

I la soluzione deve essere elettricamente neutra [H₃O⁺] + [BH⁺] = [A⁻] + [OH⁻]

I sistema di sei equazioni in sei incognite, che si pu`o risolvere ottenendo [H₃O⁺] e quindi il pH = − log[H₃O⁺].

Polinomio

Equazione polinomiale di grado n

p(x ) = anxⁿ+ an−1xⁿ⁻¹+ · · · + a2x²+ a1x + a0 = 0

I Il teorema fondamentale dell’algebra stabilisce che l’equazione ha un numero di radici complesse pari al grado del polinomio p(x ), contate con la loro molteplicit`a.

I Il teorema di Abel stabilisce che le soluzioni si possono trovare mediante quadrature in funzione dei coefficienti a₀, . . . a_n solo se il grado `e inferiore a cinque.

I E quindi possibili scrivere soluzioni analitiche esatte in termini` di operazioni elementari per le equazioni lineari, quadratiche, cubiche e quartiche.

Quadratiche

Per n = 2, l’equazione `e

ax²+ bx + c = 0

dove a, b, c sono numeri reali; si definisce il discriminante

∆ = b²− 4ac tale che se

∆ > 0: l’equazione ammette due soluzioni distinte reali

∆ = 0: l’equazione ammette una soluzione doppia reale

∆ < 0: l’equazione ammette due soluzioni complesse coniugate

Le radici in generale sono ottenute come x_k = −b + u_k√

∆ 2a

con k = 1, 2; u₁ = 1, u₂ = −1 sono le due radici quadratiche dell’unit`a, e con√

∆ si intende una delle due radici quadrate in senso complesso di ∆.

Cubiche

Per n = 3, l’equazione `e

ax³+ bx²+ cx + d = 0

dove a, b, c, d sono numeri reali; si definisce il discriminante

∆ = 18abcd − 4b³d + b²c²− 4ac³− 27a²d² tale che se

∆ > 0: l’equazione ammette tre soluzioni distinte reali

∆ = 0: l’equazione ammette una soluzione tripla reale

∆ < 0: l’equazione ammette una soluzione reale e due soluzioni complesse coniugate

Le radici in generale sono ottenute come xk = − 1

2a



b + ukC + ∆0

u_kC



con k = 1, 2, 3; u1= 1, u2 = ⁻¹⁺ⁱ

√3

2 , u3 = ⁻¹⁻ⁱ

√3

2 sono le tre radici cubiche dell’unit`a, C = ³

q∆1+√

∆²₁−4∆³₀

2 e

∆0 = b²− 3ac, ∆₁= 2b³− 9abc + 27a²d .

Metodi numerici - 1

f (x ) = 0

Scriviamo f (x ) = g (x ) − x , cio`e x = g (x ); sia a un punto di partenza e generiamo la successione

1. sia x₁ = a 2. sia x₂ = g (x₁) 3. torna allo step 2

quindi xk+1 = g (xk). Se g (x ) ha una derivata in modulo minore di 1 in un intorno della soluzione ξ ed a `e scelto in questo intorno, la successione converge a ξ.

Metodi numerici - 2

Metodo dicotomicoo di bisezione: nell’intervallo [a, b], l’equazione ammetta una radice semplice ξ, cio`e un’unica soluzione f (ξ) = 0, e che f (a)f (b) < 0.

Il metodo pi`u semplice per trovare una soluzione `e di costruire la successione

1. siano x1 = a, y1= b

2. definiamo z1= ^x1+y₂ ¹, e scegliamo x2, y2 secondo la regola: se f (x1)f (z1) < 0 allora x2 = x1, y2 = z1, altrimenti se

f (z₁)f (y₁) < 0 allora x₂ = z₁, y₂ = y₁ 3. torna allo step 2.

La successione z1, z2, . . . converge a ξ (e naturalmente se ad un certo step f (z_k) = 0, z_k = ξ).

il metodo dicotomico converge sempre, ma in modo relativamente lento (lineare) ad una soluzione.

Metodi numerici - 3

Metodo di Newton: generiamo una successione di punti x_k che convergano per k → ∞ a ξ. Ad ogni iterazione f (x_k + δx ) = 0 dove δx `e una quantit`a incognita; al primo ordine in δx possiamo per`o espandere in serie di potenze la funzione f ottenendo

f (x_k + δx ) = f (x_k) + δxf⁰(x_k)

dove f⁰(xk) = f⁰(x )|x =xk; quindi una scelta corretta di δx `e -f (x_k)/f⁰(x_k);

1. sia x1 = a

2. sia x2 = x1− _f^{f (x}0(x¹1⁾)

3. torna allo step 2

ad ogni iterazione x_k+1 = x_k −_f^{f (x}0(x^kk⁾). Il metodo di Newton converge quasi sempre, ma non in ogni caso; la convegenza `e quadratica.

Metodi numerici - 4

Regula falsi: il metodo di Newton richiede la valutazione della derivata prima della funzione oltre che della funzione stessa ad ogni iterazione. Un’alternativa `e data dal metodo della secante variabile o regula falsi, in cui la derivata f (x<sub>k</sub>) `e calcolata come il rapporto incrementale nei punti x_k, x_k−1, x_k+1= x_k − f (x_k)_{f (x}^xk−xk−1

k)−f (xk−1). 1. siano x0 = a, x1 = b

2. sia x2 = x1− f (x₁)_{f (x}^x1−x0

1)−f (x0)

3. torna allo step 2

La regula falsi converge pi`u lentamente del metodo di Newton, ma pi`u velocemente del metodo dicotomico.

Metodi numerici - 5

I Il metodo dicotomico `e implementato in varie routine di calcolo di soluzione sotto forma di algoritmo di Brent.

I La maggior parte delle librerie di calcolo disponibili combinano spesso i vari metodi, accoppiando per esempio il metodo di Brent (per individuare un’approssimazione abbastanza vicina alla soluzione) con il metodo di Newton o regula falsi (per una raffinamento ulteriore dell’approssimazione)

I routine brent (in C), dfzero (in Fortran, del pacchetto NMS), root (in Fortran, del pacchetto Napack), tutte accessibili da gams.nist.gov;funzione fzero di Matlab

I Per le equazioni polinomiali si possono sempre trovare tutte le radici: una volta trovata una radice a, si divide il polinomio per il binomio x − a (regola di Ruffini) e si trova una radice del polinomio quoziente etc.; funzione roots di Matlab

Sistemi di equazioni - 1

I il problema dell’individuazione delle soluzioni di un sistema di equazioni non lineari `e molto pi`u complesso del caso di una sola variabile.

I Se non si dispone di una buona approssimazione di partenza ad una specifica soluzione, ammesso che questa esista, non esistono metodi numerici sufficientemente robusti per risolvere il problema

I Approccio quasi-Newton: generalizzazione a pi`u dimensioni del metodo di Newton o della regula falsi.

I hybrid della libreria Minpack, libreria HOMPACK, routine quasi della libreria NAPACK (in Fortran); funzione fsolve di Matlab

Sistemi di equazioni - 2

Possiamo generalizzare il metodo di Newton in pi`u dimensioni generando la successione di vettori

x_k+1 = x_k − J(x_k)⁻¹f(x_k) dove J(x_k) `e la matrice jacobiana

J(x) =















∂f₁

∂x₁

∂f₂

∂x₁ . . . ∂f_n

∂x₁

∂f1

∂x2

∂f2

∂x2 . . . ∂fn

∂x2

. . . .

∂f1

∂xn

∂f2

∂xn . . . ∂fn

∂xn















calcolata nel punto x_k. Nei metodi quasi-Newton in pratica si sostituisce la matrice J con qualche opportuna approssimazione, per evitare il calcolo delle derivate prime.