Tópicos Computação Científica - di.ubi.ptcbarrico/Disciplinas/ComputacaoCientifica... · - através de um sistema de equações lineares. - As funções associadas às equações

Tópicos Computação CientíficaTópicos

- Métodos numéricos- Métodos analíticos versus métodos numéricos- Necessidade de se usar métodos numéricos- Métodos iterativos- Resolução de problemas- Problemas com equações não lineares- Problemas com equações lineares- Interpolação polinomial- Aproximação polinomial

Capítulo 3. Métodos Numéricos Iterativos 1/11

Métodos numéricos Computação CientíficaMétodos numéricos

- Conduzem com eficiência - a soluções aproximadas de um modelo matemático (e de um sistema real)- São usados pelos modelos matemáticos para se obter soluções numéricas de problemas quando, - não se pode ou - não se deseja usar métodos analíticos.


Métodos analíticos versus métodos numéricos Computação CientíficaMétodos analíticos versus métodos numéricos

- Um método analítico para resolver um dado modelo matemático é qualquer método- baseado na análise matemática rigorosa, e - cuja aplicação conduz a uma solução verdadeira (exata) ou analítica do modelo.- Método numérico para resolver um dado modelo matemático é qualquer método- baseado na análise matemática rigorosa,- cuja aplicação, na maioria dos casos, conduz a uma solução aproximada (não exata) ou numérica.- Em alguns casos (mas raros) um método numérico pode dar uma solução exata.- Em resumo: - soluções analíticas são exatas, enquanto que- soluções numéricas são aproximadas


Necessidade de se usar métodos numéricos Computação CientíficaNecessidade de se usar métodos numéricos

- Porquê aprender métodos numéricos? - Os métodos numéricos são necessários?- A partir da distinção apresentada antes (método analítico vs método numérico), pode-se ser levado a concluir que - é suficiente usar métodos analíticos na resolução de modelos matemáticos, ou que- não há necessidade de aprender métodos numéricos pois eles conduzem apenas a soluções aproximadas. - Tal conclusão é enganadora.


Necessidade de se usar métodos numéricos Computação Científica- Precisamos de aprender métodos numéricos pelas seguintes razões: - Porque existem situações em que é preferível um método numérico ao analítico; por exemplo, se a soluçãopara um modelo envolve vários cálculos muito demorados.- Porque a maioria dos problemas reais são, em geral, complexos e envolvem fenómenos não lineares, peloque os conhecimentos matemáticos podem não ser suficientes para se obter uma solução do problema.- Porque quando os dados do problema requerem um tratamento que inclua, por exemplo, diferenciação ouintegração, terá de ser feito através de um método numérico.- Como em geral o problema real é demasiado complexo para ser tratado analiticamente, deve-se - construir modelos aproximados ou- obter soluções aproximadas.- Nos modelos aproximados, - implica alterar e simplificar o modelo por forma a torná-lo tratável e, assim, - obter uma solução exata de um modelo aproximado.- Para se obter soluções aproximadas, deve-se- usar métodos numéricos e assim - produzir soluções aproximadas para o sistema real.


Métodos iterativos Computação CientíficaMétodos iterativos

- Os métodos iterativos estão associados aos conceitos de- iteração e - aproximação local.- Iteração (ou aproximação sucessiva) significa a repetição sucessiva de um processo. - Aproximação local - consiste em aproximar uma função por outra que seja de manuseio mais simples;- exemplo: aproximar uma função não linear por uma função linear num determinado intervalo.- Um método iterativo caracteriza-se por envolver os seguintes elementos:- aproximação inicial, que consiste numa primeira aproximação para a solução do problema numérico, e- teste de paragem, que é o instrumento por meio do qual o procedimento iterativo é finalizado.- Define-se sequência de números, { xk } k = 1, 2, …, como uma transformação do conjunto dos inteiros

positivos no conjunto dos reais. - Sequência iterativa gerada por f é a sequência resultante: xk = f (xk−1,...)


Métodos iterativos Computação Científica- Este processo gera uma sucessão de aproximações xk, cada uma com erro associado:

ek = a - xk, sendo a um zero da função f; isto é, f(a) = 0.- A sequência iterativa diz-se convergente selimk∞

xk = α

ou seja,limk∞ek = 0.

- Um método iterativo - é definido por uma equação iterativa, - com a qual se constrói aproximações à solução do problema. - A implementação da equação iterativa obriga - ao conhecimento de uma aproximação inicial e - à definição de um conjunto de condições que garantam que a aproximação calculada, numa certa iteração,se encontra suficientemente próxima da solução. - Quando estas condições forem verificadas, pode-se parar o processo.


Métodos iterativos Computação Científica- Antes de se iniciar o processo iterativo, deve-se ter resposta para as seguintes questões:1. Interessa saber se o método iterativo converge ou não para a solução procurada. Devem-se analisar ascondições necessárias e suficientes de convergência do método.2. Tendo a garantia da convergência do método, deve-se saber qual a razão de convergência.3. A implementação de um método iterativo exige a realização de um número infinito de operações para sechegar à solução - critério de paragem.


Métodos iterativos Computação Científica- Razão de convergência:- seja {xk} uma sucessão convergente para a;

- se existirem constantes positivas P e C tais que,limk∞

∣α−xk+1 ∣∣α −xk ∣P = C

então diz-se que a sucessão {xk} é convergente para a de ordem P com uma constante de convergênciaassimptótica igual a C: - P = 1, linear/1ª ordem (C < 1); dígitos ganhos por iteração: constante. - P > 1, super-linear; dígitos ganhos por iteração: aumenta. - P = 2, quadrática/2ª ordem; dígitos ganhos por iteração: duplica.

- Quantomaior for a ordem de convergência de um método iterativo,menor será, em princípio, o número de iterações necessárias para atingir uma dada precisão.


Métodos iterativos Computação Científica- Critério de paragem:- Face aos recursos limitados disponíveis, o processo iterativo deve terminar após um número finito deoperações. - As condições de paragem, se verificadas, dão mais garantia de proximidade à solução.- O valor obtido na última iteração é a melhor aproximação calculada.


Resolução de problemas Computação CientíficaResolução de problemas

- Os problemas reais que podem ser resolvidos usando métodos numéricos podem ser modeladosmatematicamente das seguintes forma:- através de uma equação não linear;- através de uma equação linear;- através de um sistema de equações não lineares;- através de um sistema de equações lineares.- As funções associadas às equações matemáticas podem ser obtidas de 3 formas:- diretamente (já conhecidas);- por interpolação a partir de vários pontos conhecidos;- por aproximação a partir de vários pontos conhecidos.



- Forma geral do problema- Características do problema- Raízes e multiplicidade- Métodos iterativos- Localização e separação das raízes - Estimativa para o erro de truncatura- Critérios de paragem- Método da Bissecção- Método da Falsa Posição (ou da Corda Falsa)- Método do Ponto Fixo- Método de Newton-Raphson- Método da Secante

Capítulo 3. Métodos Numéricos Iterativos - Problemas com Equações Não Lineares 1/41

Forma geral do problema Computação CientíficaForma geral do problema

- Uma equação não linear na variável x é representada na formaf(x) = 0,em que f : R R é uma função contínua não linear em x R; a variável x diz-se independente, e a variável y = f(x) é a variável dependente. - Resolver a equação f(x) = 0 consiste em determinar - as raízes da equação f(x) = 0, ou- os zeros da função f(x). - Na representação gráfica da função f(x) no plano XOY, - os pontos de interseção da curva f(x) com o eixo dos XX definem as raízes reais de f(x) = 0. - As raízes podem ser- raízes reais e/ou- complexas.


Características do problema Computação CientíficaCaracterísticas do problema

- Existem dois tipos de de equações não lineares: - as algébricas e - as transcendentes.- As equações algébricas - envolvem apenas as operações aritméticas básicas, - um caso particular é a forma polinomial

pn(x) = anxn + an−1 xn−1 + ... + a1 x + a0 = 0, em que ai são números reais ou complexos.


Características do problema Computação Científica- As equações transcendentes - Envolvem funções - polinomiais- trigonométricas, - exponenciais, - logarítmicas, - ... - Exemplos:

- f (x) = x −e−x = 0,- f (x) = (2x + 1)2 −4cos(π x) = 0.


Características do problema Computação Científica- Um problema diz-se direto, - se para x = p, pretende-se calcular o correspondente valor de f(p);- problema que não oferece qualquer dificuldade- Um problema diz-se inverso, - se o objetivo é determinar os valores de x que satisfazem a equação f(x) = 0;- problema que requer, na maioria dos casos, a utilização dum método numérico.


Zeros (raízes) e multiplicidade Computação CientíficaZeros (raízes) e multiplicidade

- Se f(a) = 0 diz-se que a é - uma raiz da equação f(x) = 0 (ou um zero da função f(x))- um zero pode ser de três tipos: a) simples: f(a) = 0 b) duplo: f(a) = f'(a) = 0 c) triplo: f(a) = f'(a) = f''(a) = 0- Definição: A multiplicidadede um zero ada função f(x)é o supremo mdos valores ktais que,

Capítulo 3. Métodos Numéricos Iterativos - Problemas com Equações Não Lineares 6/41limxα

∣f (x )∣

∣x −α ∣k = c < ∞

Zeros (raízes) e multiplicidade Computação Científica

Se m = 1 o zero diz-se simples, se m = 2 o zero diz-se duplo, …- Teorema:Se a for um zero da função f(x) e se f(x) for m vezes diferenciável em a então a multiplicidade de a é m se e só se, f(a) = f'(a) = ... = f(m-1)'(a) = 0, mas f(m)'(a) ≠ 0.- Exemplos: - f(x) = sin(x), f(0) = 0 mas f'(0) 0, portanto m = 1.- f(x) = 1 - cos(x), f(0) = f'(0) = 0 mas f''(0) 0, portanto m = 2.


Utilização de métodos iterativos Computação CientíficaUtilização de métodos iterativos

- A maior parte dos métodos numéricos pertence à classe dos métodos iterativos.- Os métodos para resolver o problema f(x) = 0 podem ser classificados em dois grupos: - os métodos de encaixe e - os métodos de intervalo aberto.- Os métodos de encaixe caracterizam-se por - definir, em cada iteração, um intervalo que contém a raiz e - construir, para a iteração seguinte, um intervalo encaixado neste que contém a raiz. - Como os intervalos estão encaixados uns nos outros, têm amplitudes sucessivamente menores.- Exemplos de métodos de encaixe: da Bissecção e da Falsa Posição.- Nos métodos de intervalo aberto - não é necessário definir um intervalo que contenha a raiz.- O processo iterativo pode ser iniciado com uma única aproximação à raiz (ou duas). - A convergência destes métodos depende dos valores iniciais atribuídos na primeira iteração. - Exemplos: do Ponto Fixo, de Newton-Raphson e da Secante.


Utilização de métodos iterativos Computação Científica- Independentemente do método utilizado, muitas vezes é possível obter um majorante para o erro.- Teorema:Seja a a raiz exata e xk um valor aproximado da raiz da equação

f(x) = 0 com a, xk [a, b].Se f(x) for diferenciável em [a, b] e |f'(x)| ≥ m > 0, x [a, b] então,

∣α−xk ∣ ≤∣f (xk)∣m .


Localização e separação das raízes Computação CientíficaLocalização e separação das raízes

- Para se aplicar um método iterativo é necessário conhecer uma aproximação inicial. - Para certos métodos, para haver convergência, a aproximação inicial deve estar suficientemente próxima da raiz. - Deste trabalho de análise feito à priori depende do sucesso na resolução do problema. - Assim, antes de se aplicar um método iterativo, - é necessário obter uma aproximação inicial,- o que exige a separação das possíveis raízes em intervalos tão pequenos quanto possível.


Localização e separação das raízes Computação Científica- O método mais prático consiste em analisar - a representação gráfica de f(x), ou - a combinação dos termos que formam a sua expressão analítica. - Se o gráfico de f pode ser esboçado facilmente, então são obtidas geometricamente estimativas para os zeros da função. - Se a equação f(x) = 0 pode ser escrita na forma g(x) = h(x) onde g e h são facilmente representadas graficamente, então os pontos a tais que g(a) = h(a) verificam f(a) = 0.


Localização e separação das raízes Computação Científica- O processo consiste no seguinte: - escolher um intervalo [a, b] onde se estima estar um zero da função (ou seja, que contenha um ponto de interseção das duas funções);- verificar que existe um ponto de interseção das duas funções no intervalo (a, b). Confirmar esta observação, com base nos dois resultados seguintes:1. Se f(x) - é uma função real e contínua em [a, b], sendo a e b números reais, - tendo f(a) e f(b) sinais contrários, f(a).f(b) < 0, então - existe pelo menos uma raiz real entre a e b.2. Se f'(x) - existe, - é contínua e - mantém o sinal no intervalo [a, b], então - existe no máximo uma raiz em [a, b].Portanto, se estas duas condições se verificarem, então existe uma raiz em [a, b] e é única.


Localização e separação das raízes Computação Científica- Por exemplo, para f(x) = |x| - ex,

- escolher o intervalo (-1, 0) como contendo o ponto de interseção das duas funções;- verificar que existe um ponto de interseção de |x| com ex no intervalo (-1, 0), com base nos doisresultados mencionados:f(x) C((-1, 0))f(-1) = 0.632 > 0 e f(0) = -1 < 0f'(x) = -1 – ex < 0 em todo o intervalo (-1, 0)Capítulo 3. Métodos Numéricos Iterativos - Problemas com Equações Não Lineares 13/41

Localização e separação das raízes Computação Científica- Chamam-se números de Rolle da equação f(x) = 0, definida em D R, ao conjunto - dos pontos fronteira de D e - dos zeros da função derivada de f (ou seja, as raízes de f'(x)). - Quando ordenados por ordem crescente, - entre dois números de Rolle consecutivos existe no máximo uma raiz real da equação.


Estimativa para o erro de truncatura Computação CientíficaEstimativa para o erro de truncatura

- Seja { xk } k = 1,2,... uma sequência de aproximações convergindo para uma raiz real simples a de f(x) = 0. - Aplicando o TVM deduz-se uma expressão que dá um limite para o erro na aproximação xk para a :

k ≤∣f(xk)∣M1 ,

em que a constante M1 > 0 com |f'(x)| ≥ M1 para x Nr(a) = [ a - r, a + r ] [a, b]


Critérios de paragem Computação CientíficaCritérios de paragem

- Há duas possíveis interpretações computacionais para resolver a equação f(x) = 0:- calcular um valor xk muito próximo de a onde f(a) = 0;- calcular xk tal que |f(xk)| é muito pequeno (muito próximo de zero).

- Assim, o critério de paragem dos métodos iterativos contém três parâmetros: 1, 2 e kmax. - O objetivo é terminar o processo após o cálculo de xk quando

∣ xk −xk−1∣≤ 1 (ou ∣ xk −xk−1 ∣≤ 1 ∣ xk ∣) ou∣ f(xk)∣≤ 2 ou k = kmaxem que, - e1, serve para verificar a proximidade de xk em relação a a (um zero da função),

- e2, serve para verificar se f(xk) está próximo de 0 (f(xk) 0), e - k, serve para verificar se atingiu o máximo de iterações predefinido, kmax.


Método da Bissecção Computação CientíficaMétodo da Bissecção

- Método baseado no teorema do valor intermédio- Consiste no seguinte: - partir de um intervalo [a, b] que contém a raiz,- construir uma sucessão de intervalos, sendocada um deles é o semi-intervalo do anterior que contém a raiz.


Método da Bissecção Computação CientíficaSeja [a, b] D e f(a).f(b) < 0. Então (a, b) contém uma raiz real de f(x) = 0.Seja I0 = [a, b] e x0 o ponto médio de I0. Se f(a).f(x0) < 0 então (a, x0) contém uma raiz senão (x0, b) contém uma raiz. Suponha-se que f(a).f(x0) < 0. Seja I1 = [a, x0] e x1 o ponto médio de I1. Se f(a).f(x1) < 0 então (a, x1) contém uma raiz senão (x1, x0) contém uma raiz.


Método da Bissecção Computação Científica- Algoritmo para o método da Bissecção- Objetivo: Calcular uma raiz real de f(x) = 0 em [a, b], a (a, b)- Parâmetros de entrada: a, b, e1, e2 R+, kmax N; com f(a).f(b) < 0fa f(a)k 0repitam (a + b) / 2fm f(m)se fa.fm < 0 então { a (a, m) }b msenão { a (m, b) }a mfa fmfim_sek k + 1se (|a – b| < e1) ou (|fm| < e2) ou (k > kmax) entãoescolher a (a, b)interromperfim_sefim_repita{ a (a, b) e |a – b| < e1 ou |fm| < e2 ou k > kmax }


Método da Bissecção Computação Científica- Para um dado erro absoluto e1, em cada iteração k, utilizou-se o teste:

∣bk −ak ∣2 ≤ 1- de modo a que o erro cometido seja inferior à semi-amplitute do intervalo.

- Deste modo, sendo ck os sucessivos pontos médios, ∣ c1 −α ∣ ≤

∣b −a ∣2 ; ∣ c2 −α ∣ ≤∣b −a ∣22 ; ... ; ∣ cn −α ∣ ≤

∣b −a ∣2n- é possível estimar o número n de iterações necessárias, - para garantir uma aproximação da raiz com um erro absoluto máximo de e: b −a2n ≤ 1.- Ou seja,

2n ≥b −a1 ln(2n) ≥ ln((b−a)/1) n ≥

ln ((b −a) / 1)ln 2 .


Método da Bissecção Computação Científica- Exemplo: f(x) = |x| - ex, com e1 = 10-6 e tomando [a, b] = [-1, 0]:

k ak bk k ak bk1 -1.000000 0.000000 11 -0.567383 -0.5664062 -1.000000 -0.500000 12 -0.567383 -0.5668953 -0.750000 -0.500000 13 -0.567383 -0.5671394 -0.625000 -0.500000 14 -0.567261 -0.5671395 -0.625000 -0.562500 15 -0.567200 -0.5671396 -0.593750 -0.562500 16 -0.567169 -0.5671397 -0.578125 -0.562500 17 -0.567154 -0.5671398 -0.570313 -0.562500 18 -0.567146 -0.5671399 -0.570313 -0.566406 19 -0.567146 -0.56714210 -0.568359 -0.566406 20 -0.567144 -0.567142- A raiz da equação em estudo encontra-se no intervalo (-0.567144, -0.567142);- O ponto médio é -0.567143 que é um valor aproximado da raiz com um erro absoluto menor que 10-6;- O processo terminou na iteração k = 20, em que

b −a2n = 0.00000095, ou seja, n ≥ln ((b −a) / 1)ln 2 = 19.931569.


Método da Bissecção Computação Científica- As vantagens do método da Bissecção são:- converge sempre (desde que exista raiz no intervalo inicial);- possibilidade de prever um majorante para o erro cometido ao fim de um certo número de iterações;- custo computacional de cada iteração muito baixo.- As desvantagens do método da Bissecção:- a maior está na sua convergência, que é muito lenta (muitas iterações) relativamente a outros métodos: - a ordem de convergência do método da Bissecção é linear (P = 1), - a constante de convergência é igual a 1/2 (C = 1/2).


Método da Falsa Posição (da Corda Falsa) Computação CientíficaMétodo da Falsa Posição (da Corda Falsa)

- Pode ser encarado como um melhoramento do método da Bissecção. - Em vez de se determinar o ponto médio, é determinado um ponto ck resultante da interseção

- da secante que passa pelos pontos (ak, f(ak)) e (bk, f(bk)) - com o eixo dos XX.- A partir da equação da secante,

y −f (bk) =f (bk)−f(ak)bk −ak (x −bk)

e fazendo y = 0 obtém-se,ck = bk −

f (bk)f(bk)−f (ak) (bk −ak )


Método da Falsa Posição (da Corda Falsa) Computação CientíficaAlgoritmo para o método da Falsa PosiçãoObjetivo: Calcular uma raiz real de f(x) em [a,b], a (a,b)Parâmetros de entrada: a, b, e1, e2 R+, kmax N; com f(a).f(b) < 0fa f(a)k 0repita

m = b −f(b)f (b)−f(a)

(b −a)

fm f(m)se fa.fm < 0 então { a (a, m) }b msenão { a (m, b) }a mfa fmfim_sek k + 1se (|a – b| < e1) ou |fm| < e2) ou (k > kmax) então escolher a (a, b)interromperfim_sefim_repita { a (a, b) e |a – b| < e1 ou |fm| < e2 ou k > kmax }Capítulo 3. Métodos Numéricos Iterativos - Problemas com Equações Não Lineares 24/41

Método do Ponto Fixo Computação CientíficaMétodo do Ponto Fixo

- Pretende-se determinar a solução a de uma equação não linear da forma,x = g(x).- Dada uma equação na forma f(x) = 0 é sempre possível fazer,x = x + f(x), em que g(x) = x + f(x).- De uma forma mais geral pode-se considerar,g(x) = x + c(x).f(x)onde c(x) é uma função - contínua, - não nula e - limitada no intervalo [a, b], contendo a raiz a de f(x)


Método do Ponto Fixo Computação Científica- Definição:Um ponto fixo de uma função g(x) é um número real a tal que a = g(a).Dada uma aproximação inicial x0 [a, b], calcula-se uma sucessão { xk } a tal que,

xk+1 = g(xk) , k = 0, 1, 2, ...- Geometricamente os pontos fixos da função y = f(x)são os pontos de intersecção dey = g(x) com y = x.Assim, se f(x) = 0 x = g(x), então determinar a raiz de f(x) = 0 em [a, b] é procurar o ponto fixo de g(x) em [a, b].


Método do Ponto Fixo Computação Científica- Exemplo: o cálculo de √a consiste na sucessão de aproximações

xk+1 =12( axk + xk)

- Experimente-se para a = 16, começando com x0 = 10: 0 10.00000000 1 5.80000000 2 4.27931034 3 4.00911529 4 4.00001036 5 4.0000000

- O método utilizado tem por base a equação, x = g (x ) =

12( ax + x)- que é equivalente a x2 = a e - consiste na pesquisa de um ponto fixo da função g(x).


Método do Ponto Fixo Computação Científica- Para a = 16 a função g(x) tem dois pontos fixos, em x = 4 e x = -4.Ao partir-se de uma estimativa inicial negativa, o método encontra a raiz negativa de 16.0 -10.000000001 -5.800000002 -4.279310343 -4.009115294 -4.000010365 -4.00000000


Método do Ponto Fixo Computação CientíficaTeorema (quando existe ponto fixo) Seja g(x) C([a, b]). Se para todo o x [a, b], se verifica que g(x) [a, b] (isto é, g é uma contração)então g(x) tem pelo menos um ponto fixo em [a, b].Teorema (quando é único o ponto fixo):Se g'(x) está definida em [a, b] e existe uma constante positiva L < 1, tal que |g'(x)| ≤ L para todo o x [a, b], então g(x) tem um único ponto fixo em [a, b].Teorema do Ponto Fixo (quando converge o método do ponto fixo):Sejam g(x), g'(x) C([a, b]), tais que g(x) [a, b] para todo o x [a, b], |g'(x)| < 1 para todo o x [a, b], x0 [a, b].

Então a sucessão { xk } gerada por xk+1 = g(xk), k = 0, 1, 2, ... converge para o único ponto fixo a [a, b].


Método do Ponto Fixo Computação CientíficaAlgoritmo do método do Ponto FixoObjetivo: Calcular raiz real simples de f(x) = 0, a Parâmetros de entrada: x0, e1, e2 e kmax; garantia de convergência

k 0repitak k + 1x1 g(x0)se (|x1 - x0| < e1) ou (|f(x1)| < e2) ou (k = kmax) então a x1 { aproximação obtida }interrompersenãox0 x1fim_sefim_repita


Método do Ponto Fixo Computação CientíficaExemploDeterminar, com erro absoluto inferior a 5x10-5, o zero da função f(x) = 1 + x + ex no intervalo [-2, -1].

k xk xk+1 = g(xk) d0 -2.00000 -1.13534 +5.0 x 10-11 -1.13534 -1.32131 +1.1 x 10-12 -1.32131 -1.26678 +3.2 x 10-23 -1.26678 -1.28174 +8.7 x 10-34 -1.28174 -1.27756 +2.4 x 10-35 -1.27756 -1.27872 +6.8 x 10-46 -1.27872 -1.27839 +1.9 x 10-47 -1.27839 -1.27848 +5.2 x 10-58 -1.27848 -1.27846 +1.5 x 10-5


Método de Newton-Raphson Computação CientíficaMétodo de Newton-Raphson

- Em cada iteração xk - a curva y = f(x) é aproximada pela sua tangente,- a interseção da tangente com o eixo dos XX é a novaaproximação xk+1.- Equação tangente à curva no ponto (xk, f(xk)) éy = f(xk) + f'(xk) (x - xk)- A interseção da tangente com o eixo dos XX determina anova aproximação,

xk+1 = xk −f(xk)f '(xk)

- A partir de uma aproximação inicial x0 gera-se uma sucessão { xk } que deverá convergir para um zero da função.


Método de Newton-Raphson Computação Científica- Por exemplo, para a função f(x) = x2 – a,

xk+1 = xk −f(xk)f '(xk) = xk −

xk2 −a2xk =12( axk + xk)

para o caso particular de a = 16, e x0 = 10, a sucessão das aproximações tende para um zero de f(x) = x2 – 16.

k xk0 10.00000000 1 5.80000000 2 4.27931034 3 4.00911529 4 4.00001036 5 4.00000000


Método de Newton-Raphson Computação CientíficaTeorema (Critérios de convergência):Seja f C2([a, b]). Se (1) f(a).f(b) < 0 (2) f'(x) ≠ 0 para todo o x [a, b] (3) f''(x) não muda de sinal em [a, b]

(4) ∣ f(a)f '(a) ∣ < b −a e ∣ f(b)f '(b) ∣ < b −aEntão, para qualquer x0 [a, b], a sucessão { xk } gerada pelo método de Newton-Raphson converge para o único zero de f em [a, b].

Observações:(1) + (2) garantem a existência de uma só solução em [a, b];(2) + (3) garantem que a função é monótona, convexa ou côncava;(4) garante que as tangentes à curva em (a, f(a)) e (b, f(b)) intersetam o eixo dos XX em (a, b).


Método de Newton-Raphson Computação CientíficaAlgoritmoObjetivo: Calcular raiz real simples de f(x) = 0Parâmetros de entrada: x0, e1, e2, kmax e garantia de convergência

k 0f0 f(x0)repitax1 x0 – f0 / f'(x0)k k + 1f0 f(x1)se (|x1 – x0| < e1)) ou (|f0| < e2) ou (k = kmax) então a x1 { aproximação obtida }interromperfim_sex0 x1 fim_repita


Método de Newton-Raphson Computação Científica- Vantagens:- Quando converge, tem convergência quadrática.- Necessita apenas de um ponto, para estimativa inicial. - Desvantagens:- Exige uma boa aproximação inicial. Caso contrário pode divergir, ou encontrar outra raiz. - Exige o cálculo da derivada em cada iteração, o que pode ser lento ou mesmo impossível. - Exige que a derivada (no denominador) nunca se anule.


Método da Secante Computação CientíficaMétodo da Secante

- Baseia-se na aproximação de f(x) por uma reta, na vizinhança da raiz. - O ponto de interseção da reta com o eixo dos XX é uma aproximação à raiz de f(x) = 0. - Se ainda estiver longe da solução a, o processo é repetido iterativamente.- Para iniciar o processo iterativo são escolhidos dois pontos: x0 e x1. - O intervalo definido por eles não necessita de conter a raiz.


Método da Secante Computação Científica- O ponto de interseção da reta, que passa pelos dois pontos, com o eixo dos XX obtém-se a partir da equação iterativa, cuja forma geral é

xk+1 = xk −(xk −xk−1)f (xk)−f (xk−1) f (xk), k=1,2,....

- Embora sejam necessários dois pontos para iniciar oprocesso iterativo, em cada iteração são calculados- apenas um novo ponto, e - o correspondente valor da função


Método da Secante Computação CientíficaExemplo:- Determinar aproximações para a raiz real da função x3 – 2x – 5 = 0, tomando como aproximações iniciais os pontos x0 = 3 e

x1 = 2. - Foi calculada a seguinte sequência de iterações convergindo para a raiz real daquela função:x2 = 2.058824,

x3 = 2.096559,x4 = 2.094511,x5 = 2.094511,x6 = 2.094552,x7 = 2.094552.


Método da Secante Computação Científica- Para que a sequência gerada por este método convirja para uma raiz real simples de f(x) é, em geral, necessário que as aproximações iniciais, x0 e x1, estejam suficientemente próximas da raiz.Teorema:Seja f C2([a,b]) e a uma raiz simples de f(x) = 0 em [a,b]. Então existe r > 0 tal que a sequência { xk } k = 2,3,... gerada pelo método da Secante

converge sempre que |xi - a| < r (i = 0,1).Teorema:Seja f C2([a,b]). Se (i), (ii), (iii) e (iv) do teorema sobre convergência do método de Newton-Raphson se

verificam, então para x0, x1 [a,b] a sequência gerada pelo método da Secante converge para a únicozero de f em [a,b].

Teorema (Ordem de convergência do método da Secante):A ordem de convergência é 1+√52 = 1.618... (convergência superlinear).


Método da Secante Computação CientíficaAlgoritmoObjetivo: Cálculo de uma raiz real simples de f(x) = 0, a Parâmetros de entrada: x0, x1, e1 (limite do erro absoluto), e2 e kmax

k 0f0 f(x0)f1 f(x1)repitad x1 - ( (x0 – x1) / (f1 – f0) ) . f1 )x2 x1 – dk k + 1x0 x1 x1 x2 f0 f1 f1 f(x2)se (|x1 – x0| < e1) ou (|f1| < e2) ou (k = kmax) entãoa x1 { aproximação obtida }interromperfim_sefim_repitaCapítulo 3. Métodos Numéricos Iterativos - Problemas com Equações Não Lineares 41/41


- Resolução de um sistema de equações linear- Utilização de métodos iterativos- Método de Jacobi- Método de Gauss Seidel

Capítulo 3. Métodos Numéricos Iterativos - Problemas com Equação Lineares 1/17

Resolução de um sistema de equações lineares Computação CientíficaResolução de um sistema de equações lineares

- Pretende-se calcular a solução de um sistema de equações lineares, cuja forma geral é, {

a11 x1 + a12 x2 + ... + a1n xn = b1a21 x1 + a22 x2 + ... + a2nxn = b2...an1 x1 + an2 x2 + ... + ann xn = bnonde x1, x2, ..., xn são as incógnitas do sistema, aij (i, j = 1,2, ..., n) são os coeficientes do sistema, b1, b2, ..., bn são os termos independentes (ou segundos membros) do sistema.


Resolução de um sistema de equações lineares Computação Científica- Problema:- Pretende-se determinar valores para x1, x2, ..., xn de modo que as n equações do sistema sejam satisfeitas

simultaneamente.- O sistema pode também escrever-se na sua forma matricial A x = b, ouA = [

a11 a12 ... a1n... ... ... ...an1 an2 ... ann], x = [x1...xn], b = [

b1...bn]sendo A = (aij) a matriz dos coeficientes, b = (bi) o vetor dos termos independentes, e x = (xi) o vetor das incógnitas.


Resolução de um sistema de equações lineares Computação CientíficaDefinição:Diz-se que um sistema de equações lineares é determinado se tem uma única solução.Teorema: Um sistema de equações lineares (escrito na sua forma matricial) é determinado se e só se verificar qualquer uma das duas condições (equivalentes): - A-1 existir (A é invertível) - det A ≠ 0


Métodos diretos Computação CientíficaMétodos diretos

- Permitem calcular a solução exata com um número finito de operações aritméticas básicas.- Exemplos de métodos diretos:- Regra de Cramer, - Eliminação de Gauss, - Decomposição LU, e - Método de Choleski.


Métodos iterativos Computação CientíficaMétodos iterativos

- Teoricamente:- a solução é definida como um limite de uma sucessão (infinita) de vetores. - Na prática:- calcula-se apenas um número finito de vetores da sucessão, isto é, - calcula-se um número finito de iterações. - Exemplos de métodos iterativos:- método de Jacobi - método de Gauss Seidel. - Estes métodos são apropriados para sistemas de grande dimensão, cujas matrizes dos coeficientes são dispersas.


Métodos iterativos Computação Científica- Seja A x = b (1)um sistema de n equações em n incógnitas.- A matriz A pode ser escrita na formaA = M – N, (2)sendo - M e N matrizes de ordem n, e - M invertível.- Substituindo (2) na expressão (1), e mais alguns cálculos, obtém-sex = M-1 (N x + b) (3)- Assim, a solução de (3) é solução de (1).


Métodos iterativos Computação Científica- Teorema:

Se ∥M−1 N∥ < 1 então a sequência definida pela iteração xk+1 = M−1 (N x(k ) + b), (k = 0, 1, ...) (4)converge para a solução de (3) qualquer que seja x(0) Rn.

- Os métodos de Jacobi e de Gauss Seidel definem-se com escolhas especiais para M e N.


Método de Jacobi Computação CientíficaMétodo de Jacobi

- Considerando a matriz dos coeficientes de (1), A = (aij), definem-se- D = (dij) uma matriz diagonal, - L = (lij) uma matriz estritamente triangular inferior e - U = (uij) uma matriz estritamente triangular superior, tais que

dij = {aij, se i = j0, se i ≠ j , lij = {aij , se i > j0, se i ≤ j , uij = {aij , se i < j0, se i ≥ j (5)- Então, A = D + (L + U)- A escolha de M = D e N = L + U resulta no método de Jacobi.- Do teorema anterior conclui-se que (e assumindo que D é invertível), se

∥D−1 (L + U)∥ < 1 (6)então a sequência definida pela iteração x(k+1) = D−1 (−(L + U) x(k ) + b ), (k = 0, 1, ...) (7)converge para a solução de (1), qualquer que seja x(0) Rn.


Método de Jacobi Computação CientíficaTeorema: Se a matriz dos coeficientes do sistema Ax = b de n equações em n incógnitas é estritamente diagonaldominante, então o método de Jacobi converge. Isto é, se

∣aii ∣ ≥ ∑j≠i∣aij ∣- As componentes da iteração x(k+1) de (7) são dadas por

x(k+1) = −∑j=1j in a 'ij xj(k ) + b 'i , (i=0,1,2,...,n) (8)

onde, a 'ij =

aijaii , e b 'i =

biaii


Método de Jacobi Computação CientíficaAlgoritmoObjetivo: resolução de Ax = b supondo satisfeitas as condições de convergênciaParâmetros de entrada: x(0), e e kmaxpara i de 1 até n fazerxi xi(0) fim_parak 0repitapara i de 1 até n fazeryi xi fim_parapara i de 1 até n fazer

xi b 'i − ∑j=1; j in a 'ij y j

fim_parak k + 1 se ((∥x −y∥∞ < ∥x∥∞) ou (k=kmax)) entãoa x { aproximação obtida }interromperfim_sefim_repita


Método de Gauss Seidel Computação CientíficaMétodo de Gauss Seidel

- Considere-se novamente as matrizes D, L e U, definidas em (5). - Tem-se A = (D + L) + U. - A escolha M = D + L e N = U dá o método de Gauss Seidel.- Sendo (D + L) x(k+1) = -U x(k) + b, (k = 0, 1, …)obtém-se x(k+1) = D-1 (-L x(k+1) - U x(k) + b), (k = 0, 1, …) (9)- Se

∥(D + L)−1 U∥ < 1 (10) então a sequência definida por (9) converge para a solução de (1) qualquer que seja x(0) Rn.


Método de Gauss Seidel Computação Científica- Se A for estritamente diagonal dominante é garantida a convergência do método de Gauss Seidel qualquer que seja x(0) Rn.- As componentes de x(k+1) de (9) são dadas por

xi(k+1) = −∑j=1i−1 a 'ij xj(k+1) − ∑j=i+1

n a 'ij xj(k ) + b 'i , (i = 0, 1, ..., n) (11)- A diferença entre (11) e (8) é que no método de Gauss Seidel, no cálculo da componente i da iteração k+1 são usadas as primeiras i-1 componentes já “atualizadas”.


Método de Gauss Seidel Computação CientíficaAlgoritmoObjetivo: Resolução de Ax = b supondo satisfeitas as condições de convergênciaParâmetros de entrada: x(0), e e kmaxpara i de 1 até n fazerxi xi(0) fim_parak 0repitapara i de 1 até n fazeryi xi fim_parapara i de 1 até n fazer

xi b 'i −∑j=1i−1

(a'ij x j) − ∑j=i+1n

(a 'ij y j)fim_parak k + 1 se ((∥x−y∥∞ < ∥x∥∞) ou (k=kmax)) entãointerromperfim_sefim_repita


Método de Gauss Seidel Computação CientíficaExemplo- Considere-se o seguinte sistema de equações lineares

{7 x1 −3x3 + x5 = 12 x1 + 8 x2 = 1x3 = 13x1 + 5x4 = 1x2 + 4 x5 = 12 x4 + 6x6 = 1

- A matriz dos coeficientes é estritamente diagonal dominante;- Logo, haverá convergência para a solução do sistema usando - o método de Jacobi ou - o método de Gauss Seidel.


Método de Gauss Seidel Computação Científica- Tomando x(0) = [1/7 1/8 1 1/5 1/4 1/6]T foram obtidos os seguintes resultados:

Iteração xi Método Jacobi Método Gauss Seidel

1123456

0.6071430.0892861.0000000.2857140.2812500.233333

0.607143-0.0267861.0000000.5642860.2433040.354762

2123456

0.611607-0.0267861.0000000.5642860.2723220.354762

0.606186-0.0265471.0000000.5637120.2433630.354571Capítulo 3. Métodos Numéricos Iterativos - Problemas com Equação Lineares 16/17

Método de Gauss Seidel Computação Científica

3123456

0.610332-0.0279021.0000000.5669640.2433040.354762

0.606195-0.0265491.0000000.5637170.2433630.354572... ... ...

10123456

0.606195-0.0265491.0000000.5637170.2433630.354572

------------------



- Introdução- Polinómio interpolador- Interpolação polinomial de Lagrange- Fórmula de Lagrange- Fórmula de Newton

Capítulo 3. Métodos Numéricos Iterativos - Interpolação Polinomial 1/20

Introdução Computação CientíficaIntrodução

- Seja f uma função real definida em [a, b] R, sendo conhecidos os seus valores nos pontos x0, x1, …, xn [a, b]. - Suponha-se que se pretende calcular o valor não tabulado f(x), sendo x [a, b]. - Por exemplo, dada a tabela de valores da função log10 seguinte

x log10(x) x log10(x)2.1 0.32222 2.6 0.414972.2 0.34242 2.7 0.431362.3 0.36173 2.8 0.447162.4 0.38021 2.9 0.462402.5 0.39794

- Considere-se os seguintes problemas: - calcular log10(2.45) - determinar x tal que log10(x) = 0.4

- Qualquer um destes problemas pode ser resolvido por interpolação.Capítulo 3. Métodos Numéricos Iterativos - Interpolação Polinomial 2/20

Introdução Computação Científica- Este processo consiste em - obter uma aproximação para o valor que se pretende conhecer “representando” a função f por uma função“simples”, a função interpoladora, que assume os mesmos valores que f para certos valores do argumentoem [a, b].- Um caso particular de interpolação com grande número de aplicações é a- interpolação polinomial. - Os polinómios interpoladores - Constituem meios de aproximação de funções muito usados.- Fórmulas desenvolvidas estão na base do desenvolvimento de métodos numéricos para - o cálculo de integrais, e - a resolução de equações diferenciais.


Polinómio interpolador Computação CientíficaPolinómio interpolador

DefiniçãoSeja f C([a,b]) e xi [a, b] (i = 0, 1, …, n). Um polinómio p que assume os mesmos valores que f nos pontos x0, x1, …, xn, isto é, que satisfaz

p(xi) = f(xi), (i = 0, 1, …, n)chama-se polinómio interpolador de f nos pontos x0, x1, …, xn.

Problema:Dado um conjunto de pontos,(x0, y0), (x1, y1), ..., (xn, yn) com xi ≠ xj para i ≠ j, e com i, j = 0, 1, ..., ndeterminar uma função interpoladora f tal quef(xi) = yi, i = 0, 1, ..., n


Polinómio interpolador Computação Científica- Para um dado o conjunto de pontos

duas possíveis soluções seriam:


Polinómio interpolador Computação Científica- Terminologia associada a esta problemática:- Os valores x0, x1, …, xn chamam-se nós de interpolação e

- os respetivos y0, y1, ..., yn são os valores nodais.- O conjunto { (xi, yi), i = 0, 1, …, n } chama-se suporte de interpolação.- { f(xi) = yi , i = 0, 1, …, n } é a função de interpolação nesse suporte.

- Existem vários tipos de funções de interpolação, tais como:- Interpolação polinomialf(x) = an xn + ... + a1 x + a0 - Interpolação trigonométricaf(x) = a-M e-iMx + ... + a0 + ... + aM eiMx onde M é um inteiro igual a n/2 se n é par e (n-1)/2 se n é ímpar, i é a unidade imaginária- Interpolação racionalf (x) =

ak xk + ... + a1 x + a0ak+1 xn + ... + ak+n x + ak+n+1Capítulo 3. Métodos Numéricos Iterativos - Interpolação Polinomial 6/20

Interpolação polinomial de Lagrange - Fórmula de Lagrange Computação CientíficaInterpolação polinomial de Lagrange - Fórmula de Lagrange

Definição:Designam-se por polinómios de Lagrange associados aos nós x0, ..., xn , os polinómios de grau n dados por,Lk(x) = ∏i = 0i ≠ k

n x −xixk −xi , k=0,1,...,nTeorema:O polinómio interpolador pn de grau menor ou igual a n

que interpola os valores nodais y0, y1, ..., yn nos nós distintos x0, x1, ..., xn é dado por, pn(x) = ∑k = 0

n Lk(x) yk .Exemplo:- Construir o polinómio interpolador de grau menor ou igual a 3 que interpola os seguintes valores:

xi 0 1 3 4yi 1 -1 1 2


Interpolação polinomial de Lagrange - Fórmula de Lagrange Computação Científica- Os polinómios de Lagrange associados aos nós: x0 = 0, x1 = 1, x2 = 3, x3 = 4 obtêm-se diretamente da definição anterior, L0(x) =

(x −x1) (x −x2) (x −x3)(x0 −x1) (x0 −x2) (x0 −x3) = −

112 (x −1) (x −3) (x −4)

L1(x) =(x −x0) (x −x2) (x −x3)(x1 −x0) (x1 −x2) (x1 −x3) =

16 x (x −3) (x −4)

L2(x ) =(x −x0) (x −x1) (x −x3)(x2 −x0) (x2 −x1) (x2 −x3) = −

16 x (x −1) (x −4)

L3(x) =(x −x0) (x −x1) (x −x2)(x3 −x0) (x3 −x1) (x3 −x2) =

112 x (x −1) (x −3)

- Assim sendo, nas condições do teorema, o polinómio interpolador é dado por:p3(x )= ∑k = 0

3 Lk(x ) yk = L0(x )y0+L1(x)y1+L2(x)y2+L3(x)y3 =

= L0(x)−L1(x)+L2(x)+2.L3(x )=

= −112 (x −1) (x −3) (x −4)−

16 x (x −3) (x −4)−16 x (x −1) (x −4)+

212 x (x −1) (x −3)


Interpolação polinomial de Lagrange - Algoritmo (fórmula de Lagrange) Computação CientíficaInterpolação polinomial de Lagrange - Algoritmo (fórmula de Lagrange)

{ Objetivo: cálculo de pn(z) sendo pn interpolador de f nos pontos distintos x0, x1, ..., xn }q 0para i desde 0 até n fazerp 1para j desde 0 até n fazerse j ≠ i entãop p.(z – xj) / (xi – xj)fim_sefim_paraq q + p.yi fim_para


Interpolação polinomial de Lagrange - Fórmula de Newton Computação CientíficaInterpolação polinomial de Lagrange - Fórmula de Newton

Definição:A Fórmula de Newton para polinómios de grau n é dada por, pn(x) = a0 + a1 (x – c1) + a2 (x – c1) (x – c2) + … + an (x – c1) (x – c2) ... (x – cn)onde os parâmetros ci, i = 1, 2, ... , n são chamados centros do polinómio.Construção da Fórmula de Newton:Considerando os nós x0, x1, ..., xn-1 como centros do polinómio, temos:

pn(x) = a0 + a1 (x – x0) + a2 (x – x0) (x – x1) + … + an (x – x0) (x – x1) ... (x – xn-1)Os coeficientes a0, a1, ..., an vão ser determinados de modo que pn seja o polinómio interpolador nos nós x0, x1, ..., xn dos valores nodais y0, y1, ..., yn: pn(x0) = y0 ; pn(x1) = y1 ; ... ; pn(xn) = yn ou, se os valores nodais yi forem valores nodais de uma função f tem-se,

pn(xi) = f(xi), i = 0, 1, ..., nCapítulo 3. Métodos Numéricos Iterativos - Interpolação Polinomial 10/20

Interpolação polinomial de Lagrange - Fórmula de Newton Computação Científica- Partindo de,pn(x) = a0 + a1 (x – x0) + a2 (x – x0) (x – x1) + … + an (x – x0) (x – x1) ... (x – xn-1) e fazendo sucessivamente x = x0, x = x1, ..., x = xn obtém-se os coeficientes:

a0 = f(x0)a1 =

f (x1)−a0x1 −x0 =f (x1)−f (x0)x1 −x0

a2 =f (x2)−a0 −a1(x2 −x0)

(x2 −x0)(x2 −x1) =

f (x2)−f (x1)x2 −x1 −f (x1)−f (x0)x1 −x0x2 −x0. . .

an =f (xn)−a0 −a1(xn −x0)−a2(xn −x0)(xn −x1)−...−an−1(xn −x0)... (xn −xn−2)

(xn −x0)(xn −x1)...(xn −xn−1) = ...


Interpolação polinomial de Lagrange - Fórmula de Newton Computação CientíficaCada coeficiente ak (k = 0, 1, ..., n):

- pode ser calculado a partir dos ai (i = 0, 1, ..., k-1) já determinados.- depende exclusivamente - dos nós x0, x1, ..., xn e

- dos respetivos valores nodais y0, y1, ..., yn- ak = f[x0, x1, ..., xk] em que f[x0, x1, ..., xk] é a diferença dividida de ordem k (k ≥ 1) entre os k+1 nós x0, x1, ..., xk .


Interpolação polinomial de Lagrange - Fórmula de Newton Computação CientíficaDefinição:Para designar a diferença dividida de ordem k (k ≥ 1) entre os k+1 nós x0, x1, ..., xk , são utilizadas indistintamente duas notações:

Dk f(xi) f [xi , xi+1, ... , xi+k ]ondeDk f(xi) =

Dk−1 f (xi+1) −Dk−1 f(xi)xi+k −xiouf [xi , xi+1, ... , xi+k ] =

f [xi+1, ... , xi+k ] − f [xi , ... , xi+k−1]x i+k − xi


Interpolação polinomial de Lagrange - Fórmula de Newton Computação CientíficaTeorema:Os coeficientes ak (k = 0, 1, ..., n) do polinómio pn de grau menor ou igual a n, na forma de Newton que

interpola os valores f(x0), f(x1), ..., f(xk) nos nós distintos x0, x1, ..., xk são dados indutivamente pelaexpressão:

ak = f [x0 , x1, ... , xk ] =f [x1 , ... , xk ] − f [x0 , ... , xk−1 ]xk − x0

- O Polinómio Interpolador com Diferenças Divididas tem assim a forma:pn(x) = f [x0] + f [x0, x1](x −x0)+ f [x0, x1, x2](x −x0)(x −x1)++ ... + f [x0 , x1,... , xn](x −x0)(x −x1)...(x −xn−1)


Interpolação polinomial de Lagrange - Fórmula de Newton Computação Científica- Uma tabela de diferenças divididas de uma função f pode ser escrita da forma que segue (denotando-se por fi,i+j a diferença f[xi, ..., xi+j]).

x D0 / f[] D1 / f [ , ] D2 / f [ , , ] D3 / f [ , , , ] ...x0 f(x0) f0,1x1 f(x1) f0,2f1,2 f0,3x2 f(x2) f1,3 ...f2,3 ...x3 f(x3) ... ...... fn-3,n... ... fn-2,nfn-1,nxn f(xn)


Interpolação polinomial de Lagrange - Fórmula de Newton Computação CientíficaAlgoritmo (Diferenças divididas):{ Objetivo: construir uma tabela de diferenças divididas de f por diagonais ascendentes sucessivas }f0 f(x0)para i desde 1 até n fazerfi f(xi)para j desde (i-1) até 0 fazerfj,i (fj,i-1 - fj+1,i) / (xj – xi)fim_parafim_para


Interpolação polinomial de Lagrange - Fórmula de Newton Computação CientíficaExemplo:- Determinar o polinómio interpolador de Newton que interpola os seguintes pontos:

xi 0 1 3 4yi 1 -1 1 2

- A tabela de diferenças dividida para este caso é a seguinte:x D0 / f[] D1 / f [ , ] D2 / f [ , , ] D3 / f [ , , , ]

x0 = 0 1f0,1 = -2

x1 = 1 -1 f0,2 = 1f1,2 = 1 f0,3 = -1/4

x2 = 3 1 f1,3 = 0f2,3 = 1

x3 = 4 2


Interpolação polinomial de Lagrange - Fórmula de Newton Computação Científica- Cálculo dos coeficientes ak (k = 0, 1, ..., n) do polinómio interpolador na forma de Newton: f0,1 = f [x0 , x1] =

f (x1)−f (x0)x1 −x0 =−1 −11 −0 =

−21 = −2 f1,2 = f [x1, x2] =

f (x2)−f (x1)x2 −x1 =1 −(−1)3 −1 =

22 = 1 f2,3 = f [x2, x3 ] =

f(x3)−f (x2)x3 −x2 =2 −14 −3 =

11 = 1 f0,2 = f [x0 , x1, x2] =

f [x1 , x2] −f [x0 ,x1]x2 −x0 =f1,2 −f0,1x2 −x0 =

1 −(−2)3 −0 =33 = 1

f1,3 = f [x1, x2, x3 ] =f [x2, x3] −f [x1, x2]x3 −x1 =

f2,3 −f1,2x3 −x1 =1 −14 −(−1)

=05 = 0

f0,3 = f [x0 , x1, x2 , x3] =f [x1, x2, x3] −f [x0, x1 , x2]x3 −x0 =

f1,3 −f0,2x3 −x0 =0 −14 −0 = −

14


Interpolação polinomial de Lagrange - Fórmula de Newton Computação Científica- Depois de calculados os coeficientes do polinómio interpolador na forma de Newton, a0 = f[x0] = 1 a1 = f[x0, x1] = -2 a2 = f[x0, x1, x2] = 1

a3 = f[x0, x1, x2, x3] = -1/4- Determinar a fórmula geral do polinómio interpolador: p3(x ) = a0 + a1(x −x0)+ a2(x −x0)(x −x1) + a3(x −x0)(x −x1)(x −x2)

p3(x) = 1 + (−2)(x −0) + 1(x −0)(x −1)+ (−14)(x −0)(x −1)(x −3)

p3(x ) = 1 −2 x + x (x −1)−14 x (x −1)(x −3) .


Interpolação polinomial de Lagrange - Fórmula de Newton Computação CientíficaObservações:- A ordem pela qual os nós são tomados é arbitrária.- Se é necessário acrescentar mais algum nó aos anteriores, - basta colocá-lo no fundo da tabela e - calcular mais uma linha de valores (as diferenças divididas já obtidas mantém-se).- Se os valores nodais forem os de uma função, é possível estabelecer uma ligação importante entre - as diferenças divididas de ordem k e - a derivada da mesma ordem dessa função.



- Introdução- Conceitos e resultados básicos- Aproximação dos mínimos quadrados para dados discretos

Capítulo 3. Métodos Numéricos Iterativos - Aproximação Polinomial 1/19

Introdução Computação CientíficaIntrodução

- Em linhas gerais, aproximar uma função é representá-la por uma outra mais “simples”. - Há a necessidade de aproximar uma função quando a forma com ela é definida dificulta ou impossibilitaa resolução de problemas matemáticos envolvendo essa função. - São os casos de - funções conhecidas por uma tabela de alguns dos seus valores, - funções definidas como soluções de equações, ou - funções definidas explicitamente por expressões envolvendo funções transcendentes. - Pode-se estar interessado em - calcular o valor do integral da função e não conhecer a primitiva da função, ou - calcular um (ou mais) zeros da função não existindo uma fórmula que o permita fazer explicitamente,- ...- Uma forma de resolver estes problemas é - substituir a função dada por outra mais “simples” (por exemplo, um polinómio).


Introdução Computação Científica- As classes de funções mais importantes são as - dos polinómios (incluindo polinómios segmentados), - das funções racionais (quocientes de polinómios) e - das funções de Fourier ({sen(nx), cos(nx)}, n = 0, 1, …). - Neste texto será considerada apenas a aproximação de funções por polinómios.


Conceitos e resultados básicos Computação CientíficaConceitos e resultados básicos

- O teorema de Weierstrass estabelece que para uma certa classe de funções, as contínuas num intervalofechado de R, existe um polinómio que aproxima a função tão bem quando se queira.Teorema (da aproximação de Weierstrass):Seja [a, b] R e f C([a,b]). Então, qualquer que seja e > 0 existe n = n(e) tal que |f(x) – pn(x)| < e,

para todo o x [a, b].- É possível - construir aproximações polinomiais úteis sob o ponto de vista prático, e - estimar o erro de aproximação.


Aproximação dos mínimos quadrados para dados discretos Computação CientíficaAproximação dos mínimos quadrados para dados discretos

- Seja { (xi, yi) }, i = 1, 2, ..., m um conjunto de pares de números reais onde,yi ≈ f(xi), i = 1, 2, ..., m

- A partir deste valores, pretende-se construir uma função que seja a melhor aproximação de f(x).


Aproximação dos mínimos quadrados para dados discretos Computação Científica- Tome-se como exemplo o caso linear, isto é, quando a função aproximante pretendida for uma reta y = a x + b.- Para calcular os parâmetros a e b, podem ser estabelecidos diferentes critérios, tais como: - Minimizar o erro máximo, maxi=1,...,m ∣y i −(ax i+b)∣

- Minimizar a soma dos erros,∑i=1m

∣yi −(ax i+b)∣

- Minimizar o erro quadrático,∑i=1m

(y i −(a xi+b))2


Aproximação dos mínimos quadrados para dados discretos Computação Científica- Funções aproximantes e desvios- O problema consiste em determinar a função que melhor aproxima um dado conjunto de pontos { (xi, yi) }, i = 1, 2, ..., m.- A classe das funções aproximantes é caracterizada por um conjunto de parâmetros c1, ..., cn. - Cada função da classe é especificada pelos valores desses parâmetros, f(x) = F(x; c1, ..., cn)


Aproximação dos mínimos quadrados para dados discretos Computação Científica- Se pretender-se aproximar os pontos por uma reta, então- são dois os parâmetros (c1 e c2) e

- f(x) = F(x; c1, c2) = c1 + c2 x- Se pretender-se aproximar os pontos por uma parábola, então- são três os parâmetros (c1, c2 e c3) e

- f(x) = F(x; c1, c2, c3) = c1 + c2 x + c3 x2 - Para cada classe definem-se os desvios, em relação aos valores yi dos dados,

di = yi – F(xi; c1, c2, ..., cn), i = 1, 2, ..., m- Em função dos desvios, é necessário decidir qual o critério a estabelecer.


Aproximação dos mínimos quadrados para dados discretos Computação Científica- Cada critério define um problema de minimização.- Problema de minimax (minimização do desvio máximo), minimizar maxi=1,... ,m ∣yi −F(xi; c1, c2 ,... , cn)∣

- Problema de minimização (da soma) dos desvios absolutos, minimizar ∑i=1

m∣yi −F (xi ; c1 ,c2,..., cn)∣

- Problema de minimização do erro quadrático total, minimizar ∑i=1

m(yi −F (xi ; c1,c2, ..., cn) )2

- método de resolução deste problema chama-se método dos mínimos quadrados; - função que o minimiza chama-se aproximação dos mínimos quadrados.


Aproximação dos mínimos quadrados - Método dos Mínimos Quadrados Computação CientíficaAproximação dos mínimos quadrados - Método dos Mínimos Quadrados

- Considere-se uma classe de funções,F(x; c1, c2, ..., cn) = c1 f1(x) + c2 f2(x) + ... + cn fn(x) onde f1(x), f2(x), ..., fn(x) são funções dadas.

- A aproximação dos mínimos quadrados consiste na determinação dos parâmetrosc1, c2, ..., cn que minimizam a soma dos quadrados dos desvios,E(c1 ,... ,cn) = ∑i=1

m(yi −c1f1(xi)−c2f2(xi)−... −cn fn(xi) )2 = ∑i=1

m(yi −∑j=1

n cjfj(xi))2

- Sendo um problema de minimização, para E(c1, c2, ..., cn) ser mínimo é necessário que, ∇ E(c1, ... ,cn) = 0

∂E∂cj = 0, j = 1,...,n


Aproximação dos mínimos quadrados - Método dos Mínimos Quadrados Computação Científica- Donde se obtém um sistema de n equações a n incógnitas,

{c1 ∑i=1

m f1(xi) f1(xi)+ c2 ∑i=1m f1(xi) f2(xi) + ... + cn ∑i=1

m f1(xi)fn(xi) = ∑i=1m yi f1(xi)

c1 ∑i=1m f2(xi)f1(xi) + c2 ∑i=1

m f2(xi) f2(xi) + ... + cn ∑i=1m f2(xi)fn(xi) = ∑i=1

m yi f2(xi)...c1 ∑i=1

m fn(xi)f1(xi) + c2 ∑i=1m fn(xi) f2(xi) + ... + cn ∑i=1

m fn(xi)fn(x i) = ∑i=1m yifn(xi)

- Em certos casos, este sistema - tem solução única e - permite determinar univocamente os parâmetros c1, c2, ..., cn que caracterizam a melhor função

aproximante.


Aproximação dos mínimos quadrados - Reta dos Mínimos Quadrados Computação CientíficaAproximação dos mínimos quadrados - Reta dos Mínimos Quadrados

- No caso linear, o problema da minimização do erro quadrático, pretende determinar os valores de a e b em F(x; a, b) = a + b xque minimizam E (a ,b) = ∑i=1

m(y i − a − bx i)2

- Para que E(a, b) seja mínimo é necessário e suficiente que, ∇ E (a,b) = {

∂E∂a = 0∂E∂b = 0

ou seja que, {a m + b ∑i=1

m x i = ∑i=1m y i

a ∑i=1m x i + b ∑i=1

m xi2 = ∑i=1m x i yi


Aproximação dos mínimos quadrados - Reta dos Mínimos Quadrados Computação Científica- Assim tem-se um sistema linear - com duas equações (equações normais) e - as duas incógnitas a e b que caracterizam a reta pretendida (reta de regressão).- Os coeficientes de a e b, e os termos independentes, obtém-se pela construção de uma tabela,xi yi xi2 xi yix1 y1 x12 x1 y1x2 y2 x22 x2 y2... ... ... ...xn yn xn2 xn yn

xi yi xi2 xi yi


Aproximação dos mínimos quadrados - Reta dos Mínimos Quadrados Computação Científica- Exemplo:- Para se determinar a reta de regressão que aproxima os pontos,

xi 1 2 4 5 7 8 10yi 1 2 4 4 5 6 7

- constrói-se a tabelaxi yi xi2 xi yi1 1 1 12 2 4 44 4 16 165 4 25 207 5 49 358 6 64 4810 7 100 70∑ 37 29 259 194


Aproximação dos mínimos quadrados - Reta dos Mínimos Quadrados Computação Científica- Donde se obtém o sistema {a × 7 + b × 37 = 29a × 37 + b × 259 = 194 cuja solução é a = 0.75 b = 0.6418918918919 o que permite determinar a reta de regressão, y = 0.75 + 0.6418918918919 x


Aproximação dos mínimos quadrados - Parábola dos Mínimos Quadrados Computação CientíficaAproximação dos mínimos quadrados - Parábola dos Mínimos Quadrados

- Para aproximar o conjunto de pontos por uma parábola, pretende-se determinar os valores de a, b e c em F(x; a, b, c) = a + b x + c x2 por forma a minimizar o erro quadrático total, E (a ,b,c) = ∑i=1

m(yi − a − b x i − c xi2)2

- Para que ocorra o mínimo é necessário (e prova-se que também é suficiente) que, ∇ E (a,b ,c) = 0ou seja,

{a m + b ∑i=1

m x i + c ∑i=1m x i2 = ∑i=1

n y ia ∑i=1

m x i + b ∑i=1m x i2 + c ∑i=1

m x i3 = ∑i=1m x i y i

a ∑i=1m x i2 + b ∑i=1

m x i3 + c ∑i=1m x i4 = ∑i=1

m xi2 yi- Os coeficientes de a e b e os termos independentes, obtém-se pela construção de uma tabela.


Aproximação dos mínimos quadrados - Parábola dos Mínimos Quadrados Computação Científica- Exemplo:- Para o mesmo caso do anterior,

xi 1 2 4 5 7 8 10yi 1 2 4 4 5 6 7

- construindo a tabelaxi yi xi2 xi3 xi4 xi yi xi2 yi1 1 1 1 1 1 12 2 4 8 16 4 84 4 16 64 256 16 645 4 25 125 625 20 1007 5 49 343 2401 35 2458 6 64 512 4096 48 38410 7 100 1000 10000 70 700∑ 37 29 259 2053 17395 194 1502


Aproximação dos mínimos quadrados - Parábola dos Mínimos Quadrados Computação Científica- donde se obtém o sistema {a × 7 + b × 37 + c × 259 = 29a × 37 + b × 259 + c × 2053 = 194a × 259 + b × 2053 + c × 17395 = 1502 cuja solução é a = 0.28869047619 b = 0.890625 c = -0.02306547619 o que permite determinar a parábola, que se aproxima dos pontos, y = 0.28869047619 + 0.890625 x - 0.02306547619 x2


Aproximação dos mínimos quadrados - Algoritmo Computação CientíficaAproximação dos mínimos quadrados - Algoritmo

{ Objetivo: Construção das equações normais para dados discretos }{ Parâmetros de entrada: (xi, yi) i = 1,...,m; fk, k = 1, ..., n }para i de 1 até (n+1) fazerpara j de i até (n+1) fazeraij 0

para k de 1 até m fazeraij aij + fi-1(xk) fj-1(xk)fim_paraaji aij fim_parabi 0para k de 1 até m fazerbi bi + yk fi-1(xk)fim_parafim_para


Documents

Tópicos Computação Científica - di.ubi.ptcbarrico/Disciplinas/ComputacaoCientifica... · - através de um sistema de equações lineares. - As funções associadas às equações