Knowlpedia

Theorem

Residual update with a fixed linear inverse

A quadratic equation admits an exact residual formula when corrections use the derivative at one fixed reference point.

Statement

Let F(x)=c+Lx+B(x,x)F(x)=c+Lx+B(x,x) between normed spaces, with LL bounded linear and BB bounded symmetric bilinear. Fix x0x_0, put A=DF(x0)A=DF(x_0), and suppose a bounded linear RR satisfies AR=IAR=I. At x=x0+wx=x_0+w, let r=F(x)r=F(x) and choose h=−Rrh=-Rr. Then

F(x+h)=2B(w,h)+B(h,h).F(x+h)=2B(w,h)+B(h,h).

This is the residual update using the at the fixed point x0x_0.

Exact cancellation

The quadratic expansion gives F(x+h)=r+Ah+2B(w,h)+B(h,h)F(x+h)=r+Ah+2B(w,h)+B(h,h). Since Ah=−rAh=-r, the first two terms cancel. Therefore

∥F(x+h)∥≤2∥B∥∥w∥∥R∥∥r∥+∥B∥∥R∥2∥r∥2.\|F(x+h)\|\le2\|B\|\|w\|\|R\|\|r\|+\|B\|\|R\|^2\|r\|^2.

The reference derivative and inverse remain fixed. This formula holds for arbitrary input size; a gain estimate requires the displayed products to be small in the chosen scale.

Decay exponents

For a parameter ε\varepsilon, suppose ∥B∥=O(ε−b)\|B\|=O(\varepsilon^{-b}), ∥R∥=O(ε−ℓ)\|R\|=O(\varepsilon^{-\ell}), ∥w∥=O(εα)\|w\|=O(\varepsilon^\alpha), and ∥r∥=O(εβ)\|r\|=O(\varepsilon^\beta). The new residual is

O(εβ+α−ℓ−b)+O(ε2β−2ℓ−b).O(\varepsilon^{\beta+\alpha-\ell-b})+ O(\varepsilon^{2\beta-2\ell-b}).

Both improve on order β\beta if α>ℓ+b\alpha>\ell+b and β>2ℓ+b\beta>2\ell+b. These are sufficient conditions, not a guarantee for every nonlinear iteration. New residuals must be recomputed from the complete updated state, including the quadratic term.