중첩 된 제품의 정확한 합계

Question

다음 계산에서 숫자 부동 소수점 오류를 줄이고 싶습니다. 가변 w가 [0,1] 및 b의 범위 [1,~1000000]에서 부동 소수점 상수를 나타내는 범위 내에서 어떤 부동 소수점 수를 나타낸다

b_3+w_3*(b_2+w_2*(b_1+w_1*(b_0+w_0))) 

:

는 I는 다음과 같은 형태의 식을 갖는다. b은 아래 첨자로 단조롭게 증가합니다 (중요하지는 않지만). 로이 재귀 적으로 정의 할 수 있습니다

b_4+w_4*(c_3+w_3*(b_2+w_2*(b_1+w_1*(b_0+w_0)))) 

:

func(x,n): 
    if(n==MAX) 
     return x 
    else 
     return func(b[n]+x*w[n],n+1) 

func(1,0) 

내가 온라인 요약을 수행한다면, 나는 Kahan 액수 알고리즘을 사용할 수 있습니다 (Kahan 당연히,이 용어의 수를 확장 할 수 1965), 또는 몇 가지 다른 방법 중 하나를 Higham 1993 또는 McNamee 2004, 내 오류의 크기를 제한합니다. 온라인 반복 제품을 사용하는 경우, 문제를 합계로 줄이기 위해 일종의 변환 기술을 사용할 수 있습니다.

그렇듯이이 특정 문제에 대해 어떻게 접근해야할지 모르겠습니다. 누구든지 생각을 가지고 있습니까 (그리고 그들과 함께 가기위한 인용문)?

감사합니다.

Higham 1993. "부동 소수점 합계의 정확도". 과학 컴퓨팅 저널 SIAM.

Kahan 1965. "실습 : 잘라 내기 오류 감소에 대한 추가 설명". CACM. "10.1145/363707.363723".

McNamee 2004. "정확한 합산을위한 방법 비교". SIGSAM Bull. "10.1145/980175.980177".

Answer 1

내 연산 그 대신 하나의 변수 x를 제외 호너 방식과 비슷, [I]가 각 단계에서 사용되는 승 상이한 가중치가있다.

당신이 당신의 목적에 적응할 수 있다고 생각하는 보상 된 호너 체계 알고리즘이 있습니다. 예를 들어 정리 3과 알고리즘 2를 다음 논문에서보십시오.

P. Langlois, 보상 된 호너 알고리즘을 사용하여 충실한 다항식 평가를 보장하는 방법. 컴퓨터 산술에 18 IEEE 심포지엄, 25 -. (27) 2007 년 6 월 ARITH 07 권, 141-149, http://www.acsel-lab.com/arithmetic/papers/ARITH18/ARITH18_Langlois.pdf

알고리즘이 당신이 TwoProd 교체하는 경우 (들 [I + 1], 배) TwoProd와 (들 [i + 1], w [i + 1]) 원하는 결과를 얻을 것으로 보이지만 시도하지 않았습니다.

Answer 2

당신이 func를 정의하는 방법, 그것은 다음과 같은 식으로 계산 :

For MAX = n+1, func(1,0) == 

    n  n 
    \--- ----- 
1 + >  | | w[j] 
    /--- | | 
    i=0 j=n-i 

그래서, 합계를 해결 할 방법은 다음과 같습니다

double s = 0.0; 
double a = 1.0; 
for (int i = 1; i <= MAX; ++i) { 
    a *= w[MAX-i]; 
    s += a; 
} 
return 1.0 + s; 

을 우리가 x을 치료하는 경우에도 입력 값을 func으로 변경하면 최종 용어에만 영향을 미칩니다. 하지만 그 범위 때문에, 당신은 그것을 계산에주의해야합니다.

double s = 0.0; 
double a = 1.0; 
double ax = x; 
for (int i = 1; i < MAX; ++i) { 
    a *= w[MAX-i]; 
    ax *= w[MAX-i]; 
    s += a; 
} 
ax *= w[0]; 
s += ax; 
return 1.0 + s;