Extrapolação de Richardson - Richardson extrapolation
Na análise numérica , a extrapolação de Richardson é um método de aceleração de sequência usado para melhorar a taxa de convergência de uma sequência de estimativas de algum valor . Em essência, dado o valor de para vários valores de , podemos estimar extrapolando as estimativas para . Seu nome é uma homenagem a Lewis Fry Richardson , que introduziu a técnica no início do século 20, embora a ideia já fosse conhecida por Christiaan Huygens em seu cálculo de π . Nas palavras de Birkhoff e Rota , "sua utilidade para cálculos práticos dificilmente pode ser superestimada."
As aplicações práticas da extrapolação de Richardson incluem a integração de Romberg , que aplica a extrapolação de Richardson à regra do trapézio , e o algoritmo Bulirsch-Stoer para resolver equações diferenciais ordinárias.
Exemplo de extrapolação de Richardson
Suponha que desejamos aproximar , e temos um método que depende de um pequeno parâmetro de tal forma que
Vamos definir uma nova função
onde e são dois tamanhos de etapa distintos.
Então
é chamada de extrapolação de Richardson de A ( h ) e tem uma estimativa de erro de ordem superior em comparação com .
Muitas vezes, é muito mais fácil obter uma dada precisão usando R (h) em vez de A (h ') com um h' muito menor . Onde A (h ') pode causar problemas devido à precisão limitada ( erros de arredondamento ) e / ou devido ao número crescente de cálculos necessários (ver exemplos abaixo).
Fórmula geral
Deixe ser uma aproximação de (valor exato) que depende de um tamanho de passo h positivo com uma fórmula de erro da forma
em que o um i são constantes desconhecidas e o k i são constantes conhecidas tal que h k i > h k i + 1 .
Além disso, k 0 é o comportamento do tamanho do passo da ordem principal do erro de truncamento como
O valor exato procurado pode ser dado por
que pode ser simplificado com a notação Big O para ser
Usando os tamanhos de etapa h e para alguma constante t , as duas fórmulas para A são:
Multiplicando a segunda equação por t k 0 e subtraindo a primeira equação dá
que pode ser resolvido para dar
Portanto, o uso do erro de truncamento foi reduzido para . Isso é diferente de onde o erro de truncamento é para o mesmo tamanho de etapa
Por esse processo, conseguimos uma melhor aproximação de A subtraindo o maior termo no erro que foi O ( h k 0 ). Este processo pode ser repetido para remover mais termos de erro e obter aproximações ainda melhores.
Uma relação de recorrência geral começando com pode ser definida para as aproximações por
onde satisfaz
- .
A extrapolação de Richardson pode ser considerada como uma transformação de sequência linear .
Além disso, a fórmula geral pode ser usada para estimar k 0 (comportamento do tamanho do passo da ordem principal do erro de truncamento ) quando nem seu valor nem A * (valor exato) são conhecidos a priori . Essa técnica pode ser útil para quantificar uma taxa desconhecida de convergência . Dadas as aproximações de A de três tamanhos de etapa distintos h , h / t e h / s , a relação exata
produz uma relação aproximada (observe que a notação aqui pode causar um pouco de confusão, os dois O que aparecem na equação acima indicam apenas o comportamento do tamanho do passo do pedido principal, mas suas formas explícitas são diferentes e, portanto, o cancelamento dos dois O termos é aproximadamente válido)
que pode ser resolvido numericamente para estimar k 0 para algumas escolhas arbitrárias de h , s e t .
Exemplo de código de pseudocódigo para extrapolação de Richardson
O seguinte pseudocódigo no estilo MATLAB demonstra a extrapolação de Richardson para ajudar a resolver a ODE , com o método Trapezoidal . Neste exemplo, dividimos pela metade o tamanho do passo a cada iteração e, portanto, na discussão acima, teríamos isso . O erro do método trapezoidal pode ser expresso em termos de potências ímpares, de modo que o erro em várias etapas pode ser expresso em potências pares; isso nos leva a elevar à segunda potência e a retirar potências no pseudocódigo. Queremos encontrar o valor de , que tem a solução exata de, pois a solução exata da ODE é . Este pseudocódigo assume que existe uma função chamada que tenta calcular executando o método trapezoidal na função , com ponto de partida e tamanho do passo .
Trapezoidal(f, tStart, tEnd, h, y0)
y(tEnd)
f
y0
tStart
h
Observe que começar com um tamanho de etapa inicial muito pequeno pode potencialmente introduzir erro na solução final. Embora existam métodos projetados para ajudar a escolher o melhor tamanho de passo inicial, uma opção é começar com um tamanho de passo grande e então permitir que a extrapolação de Richardson reduza o tamanho do passo a cada iteração até que o erro atinja a tolerância desejada.
tStart = 0 % Starting time
tEnd = 5 % Ending time
f = -y^2 % The derivative of y, so y' = f(t, y(t)) = -y^2
% The solution to this ODE is y = 1/(1 + t)
y0 = 1 % The initial position (i.e. y0 = y(tStart) = y(0) = 1)
tolerance = 10^-11 % 10 digit accuracy is desired
maxRows = 20 % Don't allow the iteration to continue indefinitely
initialH = tStart - tEnd % Pick an initial step size
haveWeFoundSolution = false % Were we able to find the solution to within the desired tolerance? not yet.
h = initialH
% Create a 2D matrix of size maxRows by maxRows to hold the Richardson extrapolates
% Note that this will be a lower triangular matrix and that at most two rows are actually
% needed at any time in the computation.
A = zeroMatrix(maxRows, maxRows)
%Compute the top left element of the matrix. The first row of this (lower triangular) matrix has now been filled.
A(1, 1) = Trapezoidal(f, tStart, tEnd, h, y0)
% Each row of the matrix requires one call to Trapezoidal
% This loops starts by filling the second row of the matrix, since the first row was computed above
for i = 1 : maxRows - 1 % Starting at i = 1, iterate at most maxRows - 1 times
h = h/2 % Halve the previous value of h since this is the start of a new row.
% Starting filling row i+1 from the left by calling the Trapezoidal function with this new smaller step size
A(i + 1, 1) = Trapezoidal(f, tStart, tEnd, h, y0)
for j = 1 : i % Go across this current (i+1)-th row until the diagonal is reached
% To compute A(i + 1, j + 1), which is the next Richardson extrapolate,
% use the most recently computed value (i.e. A(i + 1, j)) and the value from the
% row above it (i.e. A(i, j)).
A(i + 1, j + 1) = ((4^j).*A(i + 1, j) - A(i, j))/(4^j - 1);
end
% After leaving the above inner loop, the diagonal element of row i + 1 has been computed
% This diagonal element is the latest Richardson extrapolate to be computed.
% The difference between this extrapolate and the last extrapolate of row i is a good
% indication of the error.
if (absoluteValue(A(i + 1, i + 1) - A(i, i)) < tolerance) % If the result is within tolerance
print("y = ", A(i + 1, i + 1)) % Display the result of the Richardson extrapolation
haveWeFoundSolution = true
break % Done, so leave the loop
end
end
if (haveWeFoundSolution == false) % If we were not able to find a solution to within the desired tolerance
print("Warning: Not able to find solution to within the desired tolerance of ", tolerance);
print("The last computed extrapolate was ", A(maxRows, maxRows))
end
Veja também
Referências
- Métodos de extrapolação. Theory and Practice de C. Brezinski e M. Redivo Zaglia, North-Holland, 1991.
- Ivan Dimov, Zahari Zlatev, Istvan Farago, Agnes Havasi: Richardson Extrapolation: Practical Aspects and Applications , Walter de Gruyter GmbH & Co KG, ISBN 9783110533002 (2017).
links externos
- Métodos Fundamentais de Extrapolação Numérica com Aplicações , mit.edu
- Richardson-Extrapolação
- Extrapolação de Richardson em um site de Robert Israel (University of British Columbia)
- Código Matlab para extrapolação genérica de Richardson.
- Código de Julia para extrapolação genérica de Richardson.