2.11 Métodos iterativos para problemas não lineares

Em remoção

Supondo que $F$ é duas vezes diferenciável, a solução de (2.47) pode ser computada pela iteração de Newton:

onde $\gamma >0$ é o tamanho do passo escolhido,

denota a jacobiana de $F$, e $t=\mathrm{1,2,3},\mathrm{\dots }$.

Observamos que, em geral, a iterada de Newton (2.49) não é trivialmente paralelizável, devido a acoplamentos entre as $n$ equações. Por outro lado, podemos reescrever (2.49) como segue:

onde $s(t)$ é o passo de Newton, dado como a solução do seguinte sistema linear

Desta forma, a cada iteração de Newton $t$, devemos computar a solução do sistema linear (2.52). A aplicação da paralelização no método de Newton dá-se pela utilização de métodos paralelizáveis para a resolução de sistemas lineares. Na Seção 2.9 e, principalmente, na Seção 2.10, discutimos sobre a paralelização de métodos para sistemas lineares.

No caso de um sistema de grande porte e uma vez computada $s(t)$, a atualização (2.51) também pode ser trivialmente paralelizada. Ainda, as computações da função objetivo $F$ e de sua jacobiana $J_F$ também são paralelizáveis.

Em remoção

Em problemas de grande porte, o cálculo da jacobina $J_F$ é, em muitos casos, o passo computacionalmente mais custoso na aplicação do método de Newton. Uma alternativa é o chamado método do acorde, no qual a jacobiana é computada apenas na iteração inicial. Segue a iteração deste método

onde $t=\mathrm{0,1,2},\mathrm{\dots }$.

Enquanto a taxa de convergência do método de Newton é quadrática, o método do acorde tem convergência linear. Portanto, este só é vantajoso quando o custo de computar a jacobiana é maior que o custo de se computar várias iterações a mais.

Além das paralelizações triviais na computação de (2.54) e (2.60), vamos observar a computação da direção $s(t)$ (2.61). Como a jacobiana $J_{F\mathrm{,0}}$ é fixada constante, a utilização de métodos iterativos para computar $s(t)$ pode não ser o mais adequado. Aqui, a utilização de método direto, como a decomposição LU torna-se uma opção a ser considerada. Neste caso, a iteração ficaria como segue

onde $t=\mathrm{0,1,2},\mathrm{\dots }$.

Em remoção

Baseados em aproximações na computação do passo de Newton

uma série de métodos quasi-Newton são derivados. A aplicação de cada uma dessas tais variantes precisa ser avaliada caso a caso. Em todas elas, busca-se abrir mão da convergência quadrática em troca de um grande ganho no tempo computacional em se computar $s(t)$.

Uma das alternativas é uma variante do método do acorde. A ideia é estimar a taxa de convergência $p$ entre as iterações e atualizar a jacobiana quando a taxa estimada é menor que um certo limiar $p_l$ considerado adequado (este limiar pode ser escolhido com base nos custos computacionais de se recomputar a jacobiana versus o de se computar várias iterações a mais). A convergência é da ordem $p$ quando

com $K>0$, $\Vert F\left(x(t)\right)\Vert \to 0$ quando $t\to \mathrm{\infty }$. Assim sendo, é razoável esperar que

. Com isso, o pseudocódigo segue

1. 1.

   Aproximação inicial: $x(0)$, $t=0$.

2. 2.

   Jacobiana: $J_F=J_F\left(x(t)\right)$.

3. 3.

   Enquanto $\Vert F\left(x(t)\right)\Vert >tol$:

   1. (a)

      $J_{F}s(t)=-F\left(x(t)\right)$.

   2. (b)

      $x(t+1)=x(t)+\gamma s(t)$.

   3. (c)

      $p=\log \left(\Vert F\left(x(t+1)\right)\Vert \right)/\log \left(\Vert F\left(x(t)\right)\Vert \right)$

   4. (d)

      Se , então:

      1. i.

         $J_F=J_F\left(x(t+1)\right)$.

   5. (e)

      $t=t+1$.

Outra alternativa que pode ser considerada em determinados casos, é a de se computar $s(t)$ por

de forma aproximada. No contexto de métodos iterativos para sistemas lineares, pode-se truncar a resolução do sistema acima fixando um número pequeno de iterações. Desta forma, $s(t)$ não seria computada de forma precisa, mas a aproximação computada pode ser suficientemente adequada.

Do ponto de vista de paralelização em MP, estas variantes do método de Newton apresentam potenciais e requerem cuidados similares ao método original.

Em remoção