Numerical Analysis I, Fall 2020 (http://www.math.nthu.edu.tw/˜ wangwc/)

Homework Assignment for Week 05

Goal: Study both theoretical and practical aspects of Newton’s method and its extensions.

1. Another way of computing π is given by the Wallis formula

\frac{π}{2} = ∏_{n=1}^{∞} (\frac{(2n)^{2}}{(2n − 1)(2n + 1)}) .

There are two ways of computing the N-term approximation, namely

\frac{π_{N}}{2} = (\frac{2 · 2}{1 · 3}) (\frac{4 · 4}{3 · 5}) (\frac{6 · 6}{5 · 7}) ⋯ (\frac{2N · 2N}{(2N − 1) · (2N + 1)}) or \frac{4^{N}(N!)^{2}}{( ∏_{n=1}^{N}(2n − 1)) · ( ∏_{n=1}^{N}(2n + 1))}

Which one is better in terms of the overflow issue? What is the rate of convergence?

Hint: The rate of convergence could be analyzed analytically using Stirling’s formula. This is not required in this problem, but you can use that to help you check your ’numerical rate of convergence’. To find out the rate of convergence numerically, it suffices to plot |π − π_{N}| as a function of N. For example, the two methods in problem 4 of section 1.3 give algebraic rate (N^{−k}) and exponential rate (q^{−N}), respectively. The difference can easily be observed by plotting the results. The former appears as a straight line in the ‘loglog’ plot on matlab and the latter appears as a straight line in ’semilogy’ plot.