Método de Newton

Teoria Completa

Introdução

Nós nos acostumamos ao longo da nossa vida acadêmica a trabalhar com sistemas de equações lineares. Isso porque eles têm uma série de propriedades que facilitam muito nossas contas (e vidas :P). O problema é que no mundo real os processos, de forma geral, não ocorrem de forma linear!

Assim, quando estamos solucionando um problema prático, tentamos fazer aproximações de um modelo real para que este se comporte de maneira linear. No entanto, muitas vezes isso não é possível e acabamos tendo que resolver um sistema de equações não lineares.

Mas afinal que diabos é um sistema não linear? É simplesmente um sistema onde as equações não são retas! Por exemplo:

x 1 2 + x 2 2 - 4 = 0 x 1 2 - x 2 2 4 - 1 = 0

Graficamente:

Nesse caso, como podemos ver, temos 4 soluções, onde as equações se encontram!

E pra resolver problemas desse tipo nós vamos ver métodos iterativos para a solução de sistemas não lineares. Mas antes, precisamos de um pouco de base teórica.

Primeira coisa, vamos resolver problemas do tipo F x = 0 . Assim oh:

f 1 x 1 , x 2 , … , x n = 0 f 2 x 1 , x 2 , … , x n = 0 ⋮ f n x 1 , x 2 , … , x n = 0

E vamos usar essa notação aqui:

F x = f 1 x f 2 x ⋮ f n x ; x = x 1 x 2 ⋮ x n

Onde cada função f i x é uma função não linear. Repare que no caso de sistemas lineares temos f i x = a i x + b i .

Agora nós vamos definir o vetor gradiente de f i x denotado por ∇ f i x :

∇ f i x = ∂ f i x ∂ x 1 ∂ f i x ∂ x 2 ⋯ ∂ f i x ∂ x n

E pra definir isso temos que assumir alguns detalhes chatos tipo que F x está definida em um conjunto aberto D ⊂ R n e que tem derivadas contínuas nesse conjunto (é aquele tipo de coisa que muito provavelmente nunca vai interferir em algum exercício, mas temos que mencionar assim mesmo haha).

E ainda vamos que supor que existe pelo menos um ponto x * ∈ D , tal que F x * = 0 (na linguagem dos mortais, estamos assumindo que o sistema tem solução).

Aí a gente acha a matriz Jacobiana definida assim:

J x = ∇ f 1 x ∇ f 2 x ⋮ ∇ f n x = ∂ f 1 x ∂ x 1 ∂ f 1 x ∂ x 2 ⋯ ∂ f 1 x ∂ x n ∂ f 2 x ∂ x 1 ∂ f 2 x ∂ x 2 ⋯ ∂ f 2 x ∂ x n ⋮ ⋮ ⋱ ⋮ ∂ f n x ∂ x 1 ∂ f n x ∂ x 2 ⋯ ∂ f n x ∂ x n

No nosso exemplo temos:

∇ f 1 x = ∂ f 1 x ∂ x 1 ∂ f 1 x ∂ x 2 = 2 x 1 2 x 2

∇ f 2 x = ∂ f 2 x ∂ x 1 ∂ f 2 x ∂ x 2 = 2 x 1 - x 2 2

Logo,

J x = 2 x 1 2 x 2 2 x 1 - x 2 2

E é isso aí! Agora que aprendemos esses conceitos vamos ver como funciona um método desses na prática.

Método de Newton

Então, o método de Newton é o método que é mais usado para resolver sistemas de equações não lineares (é isso aí, se não tem o nome de Gauss vai ter o de Newton, parece que eles competiam haha).

Então, sem mais delongas, o que vamos fazer é o seguinte. Como todo método iterativo, nosso método de Newton vai precisar de um chute inicial x 0 . Nós vamos aplicar esse chute inicial na nossa matriz Jacobiana J x e na nossa F x e depois vamos resolver o sistema:

J x 0 s 0 = - F x 0

Aí o nosso x 1 vai ser obtido:

x 1 = x 0 + s 0

De forma geral, x k + 1 é dado por:

x k + 1 = x k + s k ,

onde s k é solução do sistema:

J x k s k = - F x k

Vamos ver um exemplo. Resolva o sistema não linear F x = 0 tal que:

F x = x 1 + x 2 - 5 x 1 2 + x 2 2 - 25

Usando como aproximação inicial x 0 = - 1 6 T e ε = 0.1

Passo 1: Encontramos a matriz Jacobiana.

J x = ∂ f 1 x ∂ x 1 ∂ f 1 x ∂ x 2 ∂ f 2 x ∂ x 1 ∂ f 2 x ∂ x 2 = 1 1 2 x 1 2 x 2

Passo 2: Calculamos J x 0 e F x 0 :

J x 0 = 1 1 - 2 12

F x 0 = 0 12

Passo 3: Resolvemos o sistema J x 0 s 0 = - F x 0 :

1 1 - 2 12 s 1 0 s 2 0 = 0 - 12

Calculando isso aí você vai encontrar:

s 0 = 0.86 - 0.86 T

Então,

x 1 = x 0 + s 0 = - 0.14 5.14

Passo 4: Critério de Parada

Opa, chegamos numa parte importantíssima que eu não tinha comentado ainda.

Tem dois critérios de parada principais usados nesse método. Eles são, dado um erro ε :

F x k + 1 < ε

ou,

max   ⁡ x k + 1 - x k < ε

Se a questão não impuser nenhum critério você pode usar um desses, ou usar os dois juntos se quiser. Então:

F x 1 = 0 1.44 = 0 2 + 1.44 2 = 1.44 > ε

x 1 1 - x 1 0 = 0.86 > ε

Passo 5: Calculamos J x 1 e F x 1 :

J x 1 = 1 1 - 0.28 10.28

F x 1 = 0 1.44

Passo 6: Resolvemos o sistema J x 1 s 1 = - F x 1 :

1 1 - 0.28 10.28 s 1 1 s 2 1 = 0 - 1.44

Calculando isso aí você vai encontrar:

s 1 = 0.14 - 0.14 T

Então,

x 2 = x 1 + s 1 = 0 5

Passo 7: Critério de Parada

F x 2 = 0 0 = 0 < ε

Que beleza, achamos o resultado exato! Então paramos por aqui!

Já deu pra pegar o espírito da coisa né? O bom de métodos iterativos é que não tem nenhuma surpresa, é sempre repetição!

Vamos dar uma olhada agora no algoritmo.

Algoritmo

Passo 1. Dados iniciais (o que seu programa vai receber de você):

a. Vetor aproximação inicial x = x 1 , x 2 , … x n

b. Erro ε

Passo 2. Definimos um contador de iterações k = 1

Passo 3. Definimos a variável n como o número de elementos em x

Passo 4. Calcule F x e J x onde J x i j = ∂ f i x ∂ x j para 1 ≤ i , j ≤ n

Passo 5. Resolva o sistema linear n × n , J x y = - F x

Passo 6. x = x + y

Passo 7. Se y < ε então retornar x e FIM. Caso contrário,

Passo 8. k = k + 1

Passo 9. Para i variando de 1 a n , defina x i = 1 a i i b i - ∑ j = 1 i - 1 a i j ∙ x j - ∑ j = i + 1 n a i j ∙ x j 0

Passo 10. Se max 1 ≤ i ≤ n ⁡ x i - x i 0 < ε , FIM e retorne x 1 , x 2 , … , x n . Caso contrário, continue para o Passo 5

Passo 11. k = k + 1

Passo 12. Para i variando de 1 a n , defina x i 0 = x i

Passo 13. Volte para o passo 3

Repare que nesse algoritmo o único critério de parada usado é a diferença x k + 1 - x k . Se você quiser pode adicionar o outro critério que comentamos aqui no capítulo também. Outro critério interessante é estipularmos um número máximo de iterações como em todos os outros métodos iterativos.

Observações

Então galera, aqui vão algumas observações interessantes sobre o método de Newton!

Primeiro que para garantir a convergência precisamos de uma aproximação inicial próxima da solução do sistema. Quanto mais próximo o chute, mais rápida vai ser nossa convergência!

Outro ponto fraco do método é a necessidade de resolvermos um sistema matricial a cada iteração. Se esse sistema tiver muitas equações será necessário muito poder computacional (ou manual no caso da prova haha) e o método acaba sendo muito custoso.

Quando J x k é singular (tem o determinante igual a zero), o método de Newton pode não estar definido.

Expandir

Exercício Resolvido #1

Lista da Professora Andretta – USP – Questão 6

Dado o sistema não linear

x + y = 1 x 2 + 2 y = 2

aplique uma iteração do Método de Newton para encontrar uma solução do sistema, a partir do ponto x 0 , y 0 T = 0,0 T . Calcule os erros absoluto e relativo. O ponto calculado é uma boa aproximação para a solução do sistema?

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

-

Primeira coisa que temos que fazer é passar as constantes para o outro lado! Esse método é capaz apenas de encontrar o zero de funções não lineares! Assim, temos:

x + y - 1 = 0 x 2 + 2 y - 2 = 0

Onde,

F x = x + y - 1 x 2 + 2 y - 2

A matriz Jacobiana fica:

J x = ∂ f 1 x , y ∂ x ∂ f 1 x , y ∂ y ∂ f 2 x , y ∂ x ∂ f 2 x , y ∂ y = 1 1 2 x 2

Iteração 1:

Agora calculamos J x 0 e F x 0 com x 0 = 0