Confronto grafico dell'ordine del metodo

[Indrjo Dedej]

Ciao.

Ho da confrontare graficamente il metodo di Newton e quello modificato. Allora io ho fatto disegnare gli incrementi ad ogni passo dell'iterazione in un grafico.

Codice:

format long;

% Dati del problema.
f = @(x) (x-1)*log(x);
df = @(x) log(x)+(x-1)/x;
x0 = 1.5;
tol = 1e-6;
itmax = 100;

% Grafico della funzione.
fplot(f, [-2, 2], "LineWidth", 2);
grid on;
print graph2.png

% Collezione degli incrementi e relativi grafici.
[errs1] = newton_errors(f, df, x0, 1, tol, itmax);
[errs2] = newton_errors(f, df, x0, 2, tol, itmax);
semilogy(errs1, "red", "LineWidth", 2);
hold on;
semilogy(errs2, "blue", "LineWidth", 2);
hold off;
title(["[rosso] m=1, " "[blu] m=2"]);
xlabel("n");
ylabel("|x_{n+1}-x_n|");
print convergences.png


dove:

Codice:

function [errs] = newton_errors(f, df, a, m, tol, itmax)
  % INPUT:
  %   f     : funzione di cui cercare le radici
  %   df    : derivata prima della funzione f
  %   a     : punto da cui far partire il metodo
  %   m     : molteplicità della radice attesa
  %   tol   : sulla soluzione trovata
  %   itmax : numero massimo di iterazioni disposti
  %            a fare per l'approssimazione
  % OUTPUT:
  %   errs  : lista degli errori commessi da un passo
  %           al successivo
  iter = 0;
  delta = tol+1; % per innescare il loop
  while iter < itmax && abs(delta) > tol
    iter = iter+1;
    delta = m * f(a)/df(a);
    a = a-delta;
    errs(iter) = abs(delta);
  end
end


La prof chiede: come faccio graficamente a stabilire l'ordine del metodo? Io non ho capito (e ad ora non sembra aver letto la risposta). Ho interpretato male la richiesta?

[apatriarca]

L'ordine del metodo corrisponde alla pendenza con cui l'errore decresce nel tuo grafico logaritmico.

EDIT: Mi sono un po' confuso qui. Hai bisogno di fare il grafico logaritmico del logaritmo dell'errore per vederlo come pendenza.

[Indrjo Dedej]

Non ho capito tanto bene dove vuoi arrivare...

Mi sa che ho raccolto gli scarti sbagliati. Rivedendo la definizione sul libro, il metodo di Newton dà una successione \((x_n \mid n \in \mathbb N)\) convergente a \(\alpha\) tale che per qualche \(C > 0\) si ha \(\lvert x_{n+1} - \alpha \rvert \le C \lvert x_n - \alpha \rvert\) definitivamente. Se è modificato, allora \(\lvert x_n - \alpha \rvert^2\) al secondo membro. Un confronto potrebbe farsi in questo senso, ma in pratica non saprei se ha del senso.

E poi nello studio dei criteri d'arresto per i metodi di iterazione di punto fisso c'è una stima dell'errore commesso \[e_n = \alpha - x_n \approx \frac1{1-\phi'(\alpha)} (x_{n+1}-x_n)\] dove \(\phi\) è la funzione di iterazone di punto fisso, in questo caso \(\phi'(\alpha) = 1-\frac1m\) con \(m\) molteplicità della radice.

[apatriarca]

L'ordine di convergenza di un metodo iterativo è l'esponente nella formula che hai scritto. Cioè il \(q\) in \(|x_{n+1} - \alpha| \leq C|x_n - \alpha|^q\). Se \(q=1\) si dice che il metodo converge linearmente e se è \(q=2\) allora la convergenza è quadratica. L'ordine può essere qualsiasi valore, non necessariamente intero... La convergenza del metodo di Newton è più complicata di quello che hai scritto e in molti casi è quadratica (anche senza la modifica). La modifica è necessaria per migliorare la convergenza nel caso particolare di uno zero con molteplicità maggiore di uno. In alcuni casi l'ordine di convergenza del metodo può essere maggiore di 2 e in altri può non convergere affatto. Esistono modifiche per assicurare la convergenza come il "mescolare" il metodo di Newton e quello di bisezione.

Sia in ogni caso \(\epsilon_n = \log|x_n - \alpha|\) (quello che stai visualizzando nel tuo grafico che fa uso di semilogy). Se hai una convergenza lineare allora hai una retta. Infatti ottieni
\[ \epsilon_n \leq \log(C) + \epsilon_{n-1} \leq \dots \leq n\log(C) + \epsilon_0 \]
Se la convergenza è quadratica hai invece un esponenziale
\[ \epsilon_n \leq \log(C) + 2\epsilon_{n-1} \leq (1 + 2)\log(C) + 4\epsilon_{n-2} \leq \dots \leq 2^n(\epsilon_0 - \log(C)) - \log(C). \]
In generale se l'ordine è \(q\) si ottiene
\[\epsilon_n \leq \frac{1 - q^n}{1 - q}\log(C) + q^n\epsilon_0. \]
Quindi graficamente avrai diversi esponenziali e in base alla base di questo esponenziale avrai un ordine diverso.

EDIT: Corretto le uguaglianze con disuguaglianze.

[Indrjo Dedej]

Non dovrebbero essere disuguaglianze?

[apatriarca]

Ho corretto, tuttavia il discorso non cambia in modo sostanziale. Funzionano in modo simile alla complessità computazionale.