Extrapolação de Richardson - Richardson extrapolation

Um exemplo do método de extrapolação de Richardson em duas dimensões.

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)fy0tStarth

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