SISTEMAS LINEARES - INTERPOLAÇÃO POLINOMIAL DE LAGRANGE

Interpolação Polinomial de Lagrange

Seja a tabela abaixo:

X	x0	x1	x2	x3
Y	y0	y1	y2	y3

Deseja-se passar um polinômio de grau £ 3, pelos 4 pontos tabelados.

O método de Lagrange constrói 4 polinômios auxiliares do terceiro grau:

L₀(x) , L₁(x) , L₂(x) e L₃(x), onde:

L₀(x) vale zero nos pontos x₁ , x₂ , x₃ e vale 1 no ponto x₀ .

L₁(x) vale zero nos pontos x₀ , x₂ , x₃ e vale 1 no ponto x₁ .

L₂(x) vale zero nos pontos x₀ , x₁ , x₃ e vale 1 no ponto x₂ .

L₃(x) vale zero nos pontos x₀ , x₁ , x₂ e vale 1 no ponto x₃ .

Como serão esses quatro polinômios ?

Vejamos:

Repare que em L₀ , no numerador aparece (x-x₁)(x-x₂)(x-x₃), logo, para

x = x₁,  x = x₂ e x = x₃ , o polinômio vale zero.

Para x = x₀ , o numerador é igual ao denominador e o polinômio vale 1.

Afirmação semelhante pode ser feita para L₁ , L₂ e L₃ .

Assim, fica imediata a construção de L₀ , L₁ , L₂ e L₃.

O polinômio interpolante (de Lagrange)  será:

P(x) = y₀ L₀(x) + y₁ L₁(x) + y₂ L₂(x) + y₃ L₃(x)

pois:

P(x₀) = y₀ L₀(x₀) + y₁ L₁(x₀) + y₂ L₂(x₀) + y₃ L₃(x₀) = y₀

pois: L₀(x₀) = 1     L₁(x₀) = 0    L₂(x₀) = 0 e L₃(x₀) = 0 , por construção.

Da mesma forma, P(x₁) = y₁ , P(x₂) = y₂ e P(x₃) = y₃ .

Logo o polinômio passa pelos pontos tabelados, sendo o polinômio interpolante, pois a solução é única; isto é, há um único polinômio de grau menor ou igual a três que passa nos quatro pontos tabelados.

O polinômio P(x) sendo formado pela soma de quatro polinômios do terceiro grau será necessariamente de grau menor ou igual a três.

Um exemplo:

X	1	2	4	7
Y	3	6	8	12

Assim, P(x) = 3 L₀(x) + 6 L₁(x) + 8 L₂(x) + 12 L₃(x)

Para calcular, por exemplo, P(3), faz-se :

P(3) = 3.(3-2)(3-4)(3-7)/(-18) + 6(3-1)(3-4)(3-7)/10 +

+ 8(3-1)(3-2)(3-7)/(-18) + 12(3-1)(3-2)(3-4)/90

P(3) = - 12/18 + 48/10 + 64/18 – 24/90

P(3) = 7,422

SISTEMAS LINEARES - INTERPOLAÇÃO POLINOMIAL

Interpolação Polinomial

Seja a tabela abaixo:

x0	x1	x2	...	xi	...	xn
y0	y1	y2	...	yi	...	yn

formada por n+1 pontos ( x_i , y_i ).

Trata-se de passar por esses n+1 pontos um polinômio de grau n.

P(x) = a_n xⁿ + a_n-1 x^n-1 + … + a₂ x² + a₁ x + a₀

Para tanto, calculam-se os n+1 coeficientes do polinômio P(x), isto é:

a_n, a_n-1, ..., a₁, a₀ , de modo que o polinômio passe pelos n+1 pontos tabelados.

Assim: P(x₀ ) = y₀ , P(x₁ ) = y₁ , ... , P(x_n ) = y_n .

P(x₀ ) = a_n x₀ ⁿ + a_n-1 x₀ ^n-1 + … + a₂ x₀ ² + a₁ x₀ + a₀ = y₀

P(x₁ ) = a_n x₁ ⁿ + a_n-1 x₁ ^n-1 + … + a₂ x₁ ² + a₁ x₁ + a₀ = y₁

...

P(x_i ) = a_n x_i ⁿ + a_n-1 x_i ^n-1 + … + a₂ x_i ² + a₁ x_i + a₀ = y_i 

…

P(x_n ) = a_n x_n ⁿ + a_n-1 x_n ^n-1 + … + a₂ x_n ² + a₁ x_n + a₀ = y_n

Tem-se, assim, um sistema de n+1 equações a n+1 incógnitas, onde as incógnitas são, exatamente, os coeficientes  (a_n , a_{n –1} , ... , a₁ , a₀ ) do polinômio de grau n.

Matricialmente, podemos escrever:

Lembremos que as incógnitas são os a_i ‘s, isto é, os coeficientes do polinômio de grau n.

A matriz X, no caso, é um dado, assim como o vetor Y é também dado, formados, ambos, pela tabela, dada, (x_i , y_i ).

Mostra-se que o determinante da matriz X vale:

det X = (x₀ – x₁ ) (x₀ – x₂ )... (x₀ – x_n ) (x₁ – x₂ ).. (x₁ – x_n ).... (x_n-1 – x_n )

É o chamado determinante de Vandermonde. Pode-se mostrar que a matriz de Vandermonde é mal-condicionada.

Entretanto, sendo x_i ¹ x_j para i ¹ j , tem-se que o determinante de Vandermonde será ¹ 0. Logo tem-se um sistema de n+1equações com n+1 incógnitas com det ¹0.

Assim a solução é possível determinada, solução única.

Como conclusão, dados n+1 pontos (x_i , y_i ) , há um único polinômio de grau £ n que passa pelos n+1 pontos tabelados.

Observe que o grau do polinômio é ¹ n, podendo ser do grau 1, se todos os pontos estiverem em linha reta; pode ser do grau 2, se os pontos estiverem sobre uma parábola do segundo grau, etc...

SISTEMAS LINEARES

Convergência dos Métodos Iterativos

Quero lembrar que nos exemplos que apresentei as raízes estão sendo números inteiros e a convergência está se dando rapidamente, fatos que não ocorrerão necessariamente. Na imensa maioria dos casos reais, os valores das raízes x_i não serão inteiros. Precisaremos parar quando a precisão estiver dentro da desejada. Isso se dará quando a diferença entre os valores calculados para x₁ , x₂, x₃ , etc... estiverem dentro da precisão desejada.

Para tanto, comparamos os valores obtidos para duas iterações seguidas e vemos se esses valores variaram muito ou se estão quase que se repetindo. Nesse caso, estamos próximos das raízes desejadas.

Assim, abs(x_j⁽ⁱ⁾ – x_j^(i-1) ) deve ser menor que o erro permitido para todas as variáveis x_j , onde x_j⁽ⁱ⁾  é o valor calculado para a variável x_j após i iterações e x_j^(i-1) o valor da variável x_j após i-1 iterações.

Vejamos, agora, dois exemplos muito simples.

Primeiro exemplo:

5 x₁ + 2 x₂ = 9

2 x₁ + 4 x₂ = 10

Vamos resolver por Gauss-Seidel.

x₁ = (9 – 2 x₂)/5

x₂ = (10-2 x₁)/4

Seqüência de solução: (0,0) à (1,8 , 1,6) à (1,16 , 1,92) à (1,032 , 1,984) à

(1,0064 , 1,9968) à .......(1,0000 , 2,0000)

É clara a convergência para as raízes x₁ = 1   e   x₂ = 2.

Vamos, agora, resolver o mesmo sistema, simplesmente trocando as ordens das equações.

2 x₁ + 4 x₂ = 10

5 x₁ + 2 x₂ = 9

x₁ = (10 – 4 x₂) / 2

x₂ = (9 – 5 x₁) / 2

Partindo de (0,0) , temos a seqüência:

(0,0) à (5 , -8) à (21 , -48) à (101 , -248) .....

Como vemos não há convergência para as raízes 1 e 2 .

O que está acontecendo ?

É, que pena !!! Nem sempre há convergência.

Pode-se demonstrar, que a condição suficiente para convergência é que a matriz A seja Diagonalmente Dominante, o que significa que para cada linha o termo da diagonal principal seja, em módulo, maior ou igual à soma dos módulos dos demais termos dessa linha, garantido que, em pelo menos numa linha, o módulo seja maior.

Essa condição é suficiente mas não necessária, podendo ocorrer convergência sem que a matriz seja diagonalmente dominante.

Seja uma sistema

a₁₁x₁ + a₁₂x₂ +....+a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ +....+a_2nx_n = b₂

_.....

a_n1x₁ + a_n2x₂ +....+a_nnx_n = b_n    

_Isolemos x1 na primeira equação, x₂  na segunda, x₃ na terceira etc. Temos:

x₁  = (b₁  - (a₁₂ x₂ +....+a_1n x_n))/ a₁₁

x₂  = (b₂  - (a₂₁ x₁ +....+a_2n x_n))/ a₂₂

_.....

x_n = (b_{n – (}a_n1 x₁ + a_n2 x₂ +....+ a_{n n-1} x_{n-1 ))/} a_nn

Se colocarmos os valores exatos dos x_i ‘s no lado direito, obteremos os valores exatos dos x_i ‘s no lado esquerdo. Entretanto, estamos entrando com valores incorretos, com erros, logo, obteremos valores incorretos do lado esquerdo.

Assim, os x_i ’s com que se entra são x_i + e_i . Assim,

x₁ + e₁ = (b₁  - (a_{12 (}x₂ + e₂)+....+a_{1n (}x_{n + en))/} a₁₁

x₂ + e₂ = (b₂  - (a₂₁₍x₁ + e₁) +....+a_{2n (}x_{n + en)))/} a₂₂

_.....

x_n + e_n = (b_{n – (}a_{n1 (}x₁ + e₁)+ a_{n2 (}x_{2 + e2)} +....+ a_{n n-1 (}x_{n-1 + en-1)))/} a_nn

Assim,

e₁ = - (a₁₂ e₂ +....+ a_{1n en)/} a₁₁

e₂ = - (a₂₁ e₁ +....+ a_{2n en)/} a₂₂

_....

e_n = _{– (}a_n1 e₁ + a_{n2 e2} +....+ a_{n n-1 en-1)/} a_nn

_{Se tomarmos, no lugar dos ei ‘s o erro de maior valor absoluto, seja eM , teremos:}

|e₁|<|a₁₂ e_M +....+ a_{1n eM|/ |}a_11| < | e_M| . (|a_{12| + .... +|} a_1n|)/|a_11|

|e₂|<|a₂₁ e_M +....+ a_{2n eM)|/ |}a_22| < | e_M|.( |a_{21| + ...+ |} a_2n|)/| a_22|

_....

|e_n| <_|a_n1e_M+a_n2eM+....+a_{nn-1eM|/ |}a_nn| <

< | e_M|.(_|a_n1| +| a_{n2| + ... + |} a_{n n-1|)/|}a_nn|

_{Sendo |} a_ii | ³ |a_i1| +| a_{i2| + ... + |} a_{i i-1|}

_{para todos os i’s de 1 a n, temos que o erro de cada nova variável calculada é menor que o maior erro até então existente, mostrando que os erros estão diminuindo.}

_{Com facilidade, demonstra-se que os erros tendem a zero se}

_| a_ii | ³ |a_i1| +| a_{i2| + ... + |} a_{i i-1|}

_{para todos os i’s.}

SISTEMAS LINEARES - MÉTODO DE GAUSS-SEIDEL

Método de Gauss-Seidel

O método de Gauss-Seidel é uma variante do método de Jacobi, onde se busca acelerar a solução. Para tanto, aplica-se a aproximação inicial ao cálculo de x₁, isto é: x₁=f₁(0,0...0) e em seguida já se utiliza esse novo valor de x₁ no cálculo de x₂, isto é: x₂=f₂(x₁,0..0) e assim por diante. Em princípio esse método tende a convergir mais rápido que o de Jacobi, havendo casos em que isso não ocorre por compensação de erros.

Vejamos o mesmo exemplo anterior sendo resolvido pelo método de Gauss-Seidel.

Resolver o sistema abaixo pelo método de Gauss-Seidel

10 x₁ +  2 x₂ –  3 x₃ +  2 x₄ =  32

 2 x₁ – 15 x₂ +  3 x₃ –  2 x₄ = -59

 1 x₁ –  3 x₂ + 20 x₃ +  2 x₄ = -38

 2 x₁ +  2 x₂ –  1 x₃ + 30 x₄ = 160

Isola-se, da mesma maneira, em cada equação, uma variável.

x₁ = (32 – 2 x₂ + 3 x₃ – 2 x₄)/10

x₂ = (-59 - 2 x₁ –3 x₃ + 2 x₄)/(-15)

x₃ = (-38 – 1 x₁ + 3 x₂ –2 x₄)/20

x₄ = (160 – 2 x₁ – 2 x₂ + 1 x₃)/30

Sendo (0,0,0,0)^T o ponto de partida, calcula-se x₁ neste ponto.

x₁ = (32 – 0 + 0 – 0) / 10 = 3,2

Já se usa este valor de x₁ no cálculo de x₂, isto é:

x₂ = (-59 – 2 x 3,2 + 0 – 0)/(-15) = 4,36

x₃ = (-38 – 3,2 + 3 x 4,36 –0)/20 = -1,41

x₄ = (160 – 2 x 3,2 – 2 x 4,36 + (-1,41))/30 = 4,78

Chegamos ao valor (3,2 , 4,36 , -1,41 , 4,78)^T

Daí a seqüência de valores:

(0,0,0,0) à (3,2 , 4,36 , -1,41 , 4,78) à (0,95 , 3,14 , -1,95 , 5,00) à

(0,99 , 3,01 , -2,00 , 5,00) à (1,00 , 3,00 , -2,00 , 5,00)

(1,00 , 3,00 , -2,00, 5,00)

Como vimos houve convergência para a solução.

Devemos repetir as iterações até que os valores comecem praticamente a se repetir, sinal de que já chegamos aos valores desejados.

SISTEMAS LINEARES - MÉTODO DE JACOBI

Método de Jacobi

No método iterativo de Jacobi, busca-se isolar em cada equação uma variável e aplicar-se a todas elas a aproximação inicial proposta, no caso (0,0,0...0), chegando-se a outra aproximação, que se espera seja melhor que a anterior. Assim, isola-se x₁ na primeira equação, x₂ na segunda, ..., x_n na enésima equação.

x₁=f₁(x₂,x₃,...,x_n)

x₂=f₂(x₁,x₃,...,x_n)

.................

x_n=f_n(x₁,x₂,..,x_n-1)

Em seguida aplica-se no lado direito a proposta inicial (0,0,0...0) e chega-se a nova aproximação que será o ponto de partida da iteração seguinte.

Repetindo, este método chama-se Método Iterativo de Jacobi.

Vejamos um caso concreto.

Resolver o sistema abaixo pelo método de Jacobi.

10 x₁ +  2 x₂ –  3 x₃ +  2 x₄ =  32

 2 x₁ – 15 x₂ +  3 x₃ –  2 x₄ = -59

 1 x₁ –  3 x₂ + 20 x₃ +  2 x₄ = -38

 2 x₁ +  2 x₂ –  1 x₃ + 30 x₄ = 160

Primeiramente, isola-se, em cada equação, uma variável.

x₁ = (32 – 2 x₂ + 3 x₃ – 2 x₄)/10

x₂ = (-59 - 2 x₁ –3 x₃ + 2 x₄)/(-15)

x₃ = (-38 – 1 x₁ + 3 x₂ –2 x₄)/20

x₄ = (160 – 2 x₁ – 2 x₂ + 1 x₃)/30

Admitindo-se como ponto de partida o vetor (0,0,0,0)^T, aplica-se esse conjunto de valores às quatro equações dadas, buscando melhorar essa estimativa inicial. Com isso calculam-se os novos valores das variáveis.

Sendo x₂ = 0 , x₃ = 0 e x₄ = 0 , o novo valor de x₁ será x₁ = 32/10 = 3,2

Sendo x₁ = 0 , x₃ = 0 e x₄ = 0 , o novo valor de x₂ será x₂ = -59/(-15) = 3,933..

Sendo x₁ = 0 , x₂ = 0 e x₄ = 0 , o novo valor de x₃ será x₃ = -38/20 = -1,9

Sendo x₁ = 0 , x₂ = 0 e x₃ = 0 , o novo valor de x₄ será x₄ = 160/30 = 5,333...

Chegamos assim a uma nova estimativa do valor do vetor X, ou seja

(3,2 , 3,933... , 1,9 , 5,333...)^T . Repetindo-se as operações anteriores com esses novos valores prosseguimos na busca da solução do sistema linear dado.

(0,0,0,0) à (3,2 , 3,933... , 1,9 , 5,333...) à (0,78 , 3,27 , -2,00 , 4,79) à

(0,99 , 3,00 , -1,93 , 5,00) à (1,02 , 3,01 , -2,00 , 5,00) à

(1,00 , 3,00 , -2,00 , 5,00) à (1,00 , 3,00 , -2,00 , 5,00)

Assim a solução do sistema de equações é :

 x₁ = 1,00    x₂ = 3,00     x₃ = -2,00    x₄ = 5,00

Matriz inversa por Gauss-Jordan

Apresentação do cálculo da inversa de uma matriz não-singular como aplicação do Método de Gauss-Jordan.

Bons Estudos !

Método de Gauss-Jordan, escalonamento e sistemas lineares

O Método de Gauss-Jordan é a parte principal de um procedimento para a resolução sistemática de sistemas de equações lineares. Seu objetivo é o de escalonar uma matriz para obter a sua forma escalonada reduzida por linhas. O vídeo apresenta o método passo-a-passo através de um exemplo.

Bons estudos pessoal!