Métodos do tipo gradiente são métodos iterativos que tentam aproximar a solução do problema inverso

$$Ax = b, \ \ \ \ \| b - b^\delta\| \leq \delta,$$

a partir de um chute inicial x₀.

A completa compreensão das ideias apresentadas a seguir depende de conhecimentos prévios de análise.

Para facilitar a compreensão, vamos supor que A:X→Y seja um operador linear contínuo agindo entre espaços de Hilbert.

Direção de descida

Considere um funcional

$$\varphi : X \rightarrow \mathbb{R}$$

e fixe x∈X. Dizemos que o vetor v∈X é uma direção de descida a partir de x, se existe t₀ > 0 tal que, para 0 < t < t₀ , vale a desigualdade

$$\varphi(x + t v) < \varphi (x).$$

Suponha agora que φ seja diferenciável em x e que ∇φ(x)≠0. Vamos provar que o vetor v =-∇φ(x) é uma direção de descida a partir de x. De fato,

$$\lim_{t \rightarrow 0^+} \frac{\varphi(x + tv)- \varphi(x)}{t} = \langle \nabla \varphi (x), v\rangle =  - \|\nabla \varphi (x)\|^2 <0.$$

Logo, existe t₀ > 0 tal que se 0 < t < t₀ então

$$\frac{\varphi(x + tv)- \varphi(x)}{t} < 0$$

e portanto,

$$\varphi(x + tv) < \varphi(x), \ \ \ \ \text{para todo} \ \ \ \ 0 < t < t_0,$$

o que prova a afirmação.

Métodos do tipo gradiente

O funcional do resíduo do problema inverso descrito anteriormente é definido por

$$\varphi(x) = \frac{1}{2}\|Ax - b^\delta\|^2.$$

Na k-ésima iteração desse tipo de método, o gradiente do funcional do resíduo, ∇φ, é calculado no ponto corrente x_k. Agora, a direção oposta ao gradiente de φ é uma direção de descida desse funcional. Portanto, se λ é um número real positivo e pequeno suficiente, então o vetor x_k - λ∇φ(x_k) possui um resíduo menor do que x_k .

A iteração de um método do tipo gradiente é portanto definida da seguinte forma:

1. Escolha um chute inicial x₀∈X e defina k = 0;
2. Escolha o passo λ_k > 0;
3. Defina x_k+1 = x_k - λ_k∇φ(x_k);
4. Substitua k+1 por k e retorne ao passo 2.

A iteração acima é executada até que um critério de parada apropriado seja atingido.

Para provar-se propriedades de convergência e estabilidade dos métodos do tipo gradiente, é essencial que se escolha o tamanho do passo λ_k > 0 de maneira adequada. Regras diferentes para a escolha do passo resultam em métodos diferentes. As principais regras conhecidas resultam nos seguintes métodos: Método de Landweber, Máxima Descida e Erro mínimo. Esses são casos particulares de métodos do tipo gradiente com erro decrescente (veja a Seção abaixo: Principais métodos do tipo gradiente).

Cálculo do gradiente

A partir de agora vamos determinar o gradiente do funcional do resíduo φ num ponto qualquer fixado x∈X. O gradiente de φ, calculado em x e aplicado no vetor v∈X, é igual a derivada direcional de φ no ponto x e na direção de v. Assim,

$$\langle\nabla \varphi(x),v \rangle = \lim_{t \rightarrow 0}\frac{\varphi(x + tv) - \varphi(x)}{t}.$$

Mas como A é linear, tem-se

$$\varphi(x+tv) = \frac{1}{2}\|A(x+tv) - b^\delta\|^2 = \frac{1}{2}\|(Ax - b^\delta) + tAv\|^2.$$

Agora, como  X é um espaço de Hilbert,

$$\frac{1}{2}\|(Ax - b^\delta) + tAv\|^2 = \frac{1}{2}\|Ax - b^\delta \|^2 + t\langle Ax - b^\delta, Av\rangle + \frac{t^2}{2}\|Av\|^2.$$

Daí

$$\langle\nabla\varphi(x),v\rangle = \lim_{t\rightarrow 0}\Big{(}\langle Ax - b^\delta,Av\rangle + \frac{t}{2} \|Av\|^2\Big{)} = \langle A^*(Ax - b^\delta),v\rangle,$$

onde A*:Y→X é a adjunta de A. Daí,

$$\nabla \varphi (x) = A^*(Ax - b^\delta)$$

é o gradiente do funcional do resíduo. Desse modo, a iteração dos métodos do tipo gradiente pode ser reescrita como

$$x_{k+1} = x_k - \lambda_k A^*(Ax_k - b^\delta).$$

Escolha do passo

Vamos nos ocupar agora em determinar o tamanho do passo λ_k > 0. Para facilitar a compreensão, vamos assumir temporariamente que não há ruídos nos dados, isto é, δ = 0, e portanto, b^δ = b. Usaremos o chamado critério do erro decrescente. Suponha que x⁺ é uma solução do problema inverso, isto é, Ax⁺ = b. A diferença de dois erros de iteração consecutivos é dada por

$$\frac{1}{2}\|x_{k+1} - x^+\|^2 - \frac{1}{2}\|x_k - x^+\|^2 = \frac{1}{2}\|x_{k+1} - x_k\|^2 + \langle x_{k+1} - x_k, x_k - x^+\rangle.$$

Nosso objetivo é determinar um passo λ_k > 0 de modo que o lado direito da igualdade acima se torne não positivo, e consequentemente tem-se a monotonia do erro:

$$\|x_{k+1} - x^+\|^2 \leq \|x_k - x^+\|^2.$$

Observe que, como

$$x_{k+1} - x_k = -\lambda_k A^*(Ax_k - b),$$

temos que

$$\frac{1}{2}\|x_{k+1} - x_k\|^2 = \frac{1}{2}\|\lambda_k A^*(Ax_k - b)\|^2 = \frac{\lambda_k^2}{2} \|A^*(Ax_k - b)\|^2$$

e também,

$$\langle x_{k+1} - x_k, x_k - x^+\rangle = - \lambda_k \langle Ax_k - b, A(x_k - x^+) \rangle = - \lambda_k \langle Ax_k - b, Ax_k - b\rangle.$$

Então,

$$\frac{1}{2}\|x_{k+1} - x^+\|^2 - \frac{1}{2}\|x_k - x^+\|^2 = \frac{\lambda_k^2}{2} \|A^*(Ax_k - b)\|^2 - \lambda_k \|Ax_k - b\|^2.$$

Logo, a monotonia do erro ocorre se e somente se o lado direito dessa última igualdade é menor ou igual a zero, ou seja, se λ_k ≤ λ_max , com

$$\lambda_{\max} = 2\frac{\|Ax_k - b\|^2}{\|A^*(Ax_k - b)\|^2}. $$

Conclui-se assim, que se o passo do método do tipo gradiente satisfaz 0 < λ_k ≤ λ_max, então o método resultante tem um erro de iteração decrescente.

Principais métodos do tipo gradiente

O método do tipo gradiente mais simples é o chamado Método de Landweber, o qual consiste em escolher um passo λ_k constante. Observe que

$$\lambda_{\max} \geq \frac{2}{\|A^*\|^2} = \frac{2}{\|A\|^2},$$

e portanto, escolhendo um passo constante

$$\lambda_{LW} \leq \frac{2}{\|A\|^2},$$

tem-se λ_LW ≤ λ_max.

Outro método do tipo gradiente muito bem conhecido é o chamado Método da Máxima Descida (Steepest Descent em inglês). Esse método utiliza na iteração k, o passo λ_k que minimiza o funcional do resíduo na direção de -∇φ(x_k). Defina a função

$$f(\lambda) = \varphi(x_k - \lambda \nabla \varphi (x_k)),$$

e encontre o passo λ > 0 que minimiza essa função. Perceba que, como A é linear, tem-se

$$f(\lambda) = \frac{1}{2}\|A(x_k - \lambda \nabla \varphi (x_k)) - b\|^2 =\frac{1}{2}\|(Ax_k - b) - \lambda A\nabla \varphi (x_k))\|^2,$$

e daí,

$$ f(\lambda) =\frac{1}{2}\|Ax_k - b\|^2 - \langle Ax_k - b, \lambda A \nabla \varphi (x_k)\rangle + \frac{1}{2}\|\lambda A \nabla \varphi (x_k)\|^2.$$

Mas como

$$\nabla \varphi (x_k) = A^*(Ax_k -b),$$

segue que

$$f(\lambda) = \frac{1}{2}\|Ax_k - b\|^2 - \lambda\|\nabla \varphi (x_k)\|^2 + \frac{\lambda^2}{2}\| A \nabla \varphi (x_k)\|^2.$$

Logo,

$$f'(\lambda) = - \|\nabla \varphi (x_k)\|^2 + \lambda\| A \nabla \varphi (x_k)\|^2.$$

Como f é convexa e diferenciável, o seu mínimo é atingido quando a sua derivada se anula. Por consequência, o passo λ do método da máxima descida é dado por

$$\lambda_{SD} = \frac{\| \nabla \varphi (x_k)\|^2}{\|A\nabla \varphi (x_k)\|^2} = \frac{\| A^* (Ax_k - b)\|^2}{\|A A^* (Ax_k - b)\|^2} .$$

O Método do Erro Mínimo (Minimal Error em inglês) é o método do tipo gradiente que utiliza o passo λ_k que minimiza o erro de iteração. Assim no passo k, define-se o funcional

$$g(\lambda) = \frac{1}{2}\|(x_k - \lambda \nabla \varphi(x_k)) - x^+\|^2 = \frac{1}{2}\|(x_k - x^+)-\lambda \nabla \varphi(x_k)\|^2,$$

e tenta-se determinar o passo λ que minimiza g. Veja que

$$g(\lambda) =  \frac{1}{2}\|x_k - x^+\|^2 - \lambda \langle x_k - x^+, \nabla \varphi(x_k)\rangle + \frac{\lambda^2}{2} \|\nabla \varphi(x_k)\|^2.$$

Como

$$\langle x_k - x^+, \nabla \varphi(x_k)\rangle =  \langle A(x_k - x^+), Ax_k - b\rangle = \|Ax_k - b\|^2,$$

segue que

$$g'(\lambda) = -\|Ax_k - b\|^2 + \lambda\|\nabla \varphi(x_k)\|^2.$$

Portanto, impondo-se a condição de otimalidade g'(λ) = 0, encontra-se o mínimo do funcional g e por consequência, o passo do método do erro mínimo, dado por

$$\lambda_{ME} = \frac{\|Ax_k - b\|^2}{ \|\nabla \varphi(x_k)\|^2} = \frac{\|Ax_k - b\|^2}{ \|A^*(Ax_k - b)\|^2} .$$

Observe que

$$0 < \lambda_{LW} \leq \lambda_{SD} \leq\lambda_{ME} \leq \lambda_{\max}. $$

Portanto, qualquer um dos métodos acima rende um método do tipo gradiente com erro de iteração monotonamente decrescente, isto é,

$$\|x_{k+1} - x^+\|^2  \leq \|x_k - x^+\|^2.$$

Critério de parada

Quando há ruídos nos dados, isto é, quando δ > 0, um critério de parada adequado deve ser imposto à iteração a fim de evitar amplificação de erros. Isso significa que o algoritmo termina após iterar um número finito de vezes.

Possivelmente o critério de parada mais conhecido e mais aplicado na prática é o chamado Princípio da Discrepância de Morozov: fixe τ > 1 e encerre o algoritmo na iteração k = k_δ definida por

$$k_\delta = \min\{k \in \mathbb{N}: \|Ax_k - b^\delta\| \leq \tau \delta\}.$$

Desse modo, o vetor de índice k_δ aproxima uma solução x* do problema inverso. Mais precisamente, tem-se a propriedade de regularização:

$$\lim_{\delta \rightarrow 0}x_{k_\delta} = x^*.$$