I am trying to solve Problem 3 & 4 from Numerical methods of Bakhvalov, Zhidkov, Kobelkov from section 2.8 on Chebyshev polynomials.

If in the recursive formula $$ T_n(x) = 2xT_{n-1}(x)-T_{n-2}(x) $$ each calculation contains a round-off error: $$ T^*_0=1,\quad T_1^*=T_1+\delta_1,\quad T_n^*(x)=2xT_{n-1}^*(x) - T_{n-2}^*(x) + \delta_n $$ then

  1. To develop $$ T_N^*(x)-T_N(x) = \sum_{k=1}^N\delta_k\frac{\sin((N+1-k)\arccos{x})}{\sqrt{1-x^2}} $$
  2. And $$ |T_N^*(x)-T_N(x)|\leq \max|\delta_k|\cdot N\cdot \min\left\{N,\frac{1}{\sqrt{1-x^2}}\right\} $$

With the first problem, by calculating the first few terms I can see that the cumulative round-off is the sum of derivatives divided by the power: $$ \frac{T'_1}{1}+\frac{T'_2}{2}+\cdots+\frac{T'_N}{N} $$ and of course the derivative of $T_n(x)$ is $$ T'_n(x)=n\frac{\sin(n\arccos{x})}{\sqrt{1-x^2}} $$ So, then I can prove the formula by induction. But I can't claim that I have properly developed this formula.

For the second problem, I can easily prove $$ |T^*_N(x)-T_N(x)|\leq \frac{\max|\delta_k|\cdot N}{\sqrt{1-x^2}} $$ since $\sin(n\arccos{x})\leq 1$. But I can't get $$ |T^*_N(x)-T_N(x)|\leq \max|\delta_k|\cdot N^2. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.