Question

Consider the fixed point iteration \(x_{k+1}=g\left(x_{k}\right), k=0,1, \ldots\), and let all the assumptions of the Fixed Point Theorem hold. Use a Taylor's series expansion to show that the order of convergence depends on how many of the derivatives of \(g\) vanish at \(x=x^{*}\). Use your result to state how fast (at least) a fixed point iteration is expected to converge if \(g^{\prime}\left(x^{*}\right)=\cdots=\) \(g^{(r)}\left(x^{*}\right)=0\), where the integer \(r \geq 1\) is given.

Short answer

The order of convergence of a fixed point iteration depends on the number of vanishing derivatives of the function \(g\) at the fixed point \(x^*\). If the first \(r\) derivatives vanish, and the \((r+1)\)-th derivative does not vanish at \(x^*\), then the fixed point iteration has at least an order of convergence of \((r+1)\), and the rate of convergence will be superlinear.

Step-by-step solution

Expand \(g(x)\) using Taylor's series

Start by expanding the function \(g(x)\) around the fixed point \(x^*\) using a Taylor's series expansion up to the \((r+1)\)-th derivative term: \(g\left(x\right) = g\left(x^{*}\right)+\sum_{n=1}^{r}\frac{g^{(n)}\left(x^{*}\right)}{n!}(x-x^{*})^n+\frac{g^{(r+1)}\left(\xi\right)}{(r+1)!}(x-x^{*})^{r+1}\), where \(x^{*}\) is the fixed point and \(\xi\) is some point between \(x\) and \(x^{*}\). Since \(x^{*}\) is the fixed point, it satisfies the fixed-point equation \(x^{*}=g\left(x^{*}\right)\). Also, for \(1 \leq n \leq r\), it is given that \(g^{(n)}\left(x^{*}\right)=0\). Using these two facts, we simplify the Taylor's series expansion: \(g\left(x\right) = x^{*}+\frac{g^{(r+1)}\left(\xi\right)}{(r+1)!}(x-x^{*})^{r+1}\).

Rewrite the fixed point iteration equation

The fixed point iteration is given by: \(x_{k+1}=g\left(x_{k}\right)\quad\text{for }k=0,1,\ldots\). Substitute our simplified Taylor's series expansion for \(g\left(x_{k}\right)\): \(x_{k+1}=x^{*}+\frac{g^{(r+1)}\left(\xi_{k}\right)}{(r+1)!}\left(x_{k}-x^{*}\right)^{r+1}\), where \(\xi_{k}\) is some point between \(x_{k}\) and \(x^{*}\).

Derive the convergence properties based on vanishing derivatives of \(g\) at \(x = x^{*}\)

To find the convergence properties, rearrange the equation to isolate the error term \(e_{k}=x_{k}-x^{*}\): \(e_{k+1}=\frac{g^{(r+1)}\left(\xi_{k}\right)}{(r+1)!}e_{k}^{r+1}\). Taking the absolute value of both sides, we get: \(|e_{k+1}|=\frac{|g^{(r+1)}(\xi_{k})|}{(r+1)!}|e_{k}|^{r+1}\). As the iteration converges, the error term \(|e_{k}|\) goes to zero, so the ratio \(\frac{|e_{k+1}|}{|e_{k}|^{r+1}}\) approaches a constant value: \(\lim_{k\to\infty}\frac{|e_{k+1}|}{|e_k|^{r+1}}=\frac{1}{(r+1)!}|g^{(r+1)}(x^*)|\).

State the rate of convergence

We've found that the order of convergence of the fixed point iteration is at least \((r+1)\) if the first \(r\) derivatives of \(g\) vanish at \(x = x^*\), and the \((r+1)\)-th derivative does not vanish. The fixed point iteration is expected to converge superlinearly (faster than linear rate), and the order of convergence is at least \((r+1)\).

Key concepts

Order of Convergence

Order of convergence is a measure of how quickly a sequence approaches its limit. In the context of fixed point iteration, it describes how fast the iterative process converges to a fixed point. If we have a function \(g(x)\) and we use it to repeatedly update our estimate \(x_k\), the order of convergence tells us how the error decreases with each iteration.

• If a method has a linear order of convergence, the error decreases at a constant rate with each iteration.
• A higher order, like quadratic or cubic, means the error decreases much more rapidly.
• Superlinear convergence means the rate improves as the process unfolds.

This is crucial for understanding the efficiency of different iterative methods. If all derivatives up to the \(r\)-th order vanish at the fixed point \(x^*\), the process will converge with at least order \((r+1)\). This means for every iteration, the error reduces significantly faster than linear convergence.

Taylor Series Expansion

The Taylor series is a powerful tool in calculus that approximates functions using polynomials. By expanding a function like \(g(x)\) around a fixed point \(x^*\), we can express it as a series:

• Starts with the function value at \(x^*\)
• Involves the derivatives of the function at \(x^*\)
• Gives us an approximation of how the function behaves around that point

In this exercise, we expanded \(g(x)\) up to the \((r+1)\)-th derivative term, which is key to analyzing fixed point iterations. The higher derivatives tell us how sensitive the function is to changes near the fixed point. If several derivatives vanish, the function is smoother around that point, resulting in faster convergence of the iteration process.

Fixed Point Theorem

The Fixed Point Theorem is foundational in numerical methods. It states that under certain conditions, a function will have a fixed point where \(g(x^*) = x^*\). This is especially useful for iterative methods, allowing us to find solutions to equations by approximating these points iteratively.

• The theorem provides the necessary conditions for the existence of fixed points.
• It ensures convergence of the iteration under these conditions.
• Helps design iterative methods with predictable convergence.

In the context of our exercise, the assumptions of this theorem are fulfilled, which is why the iteration converges to \(x^*\). It allows us to apply tools like Taylor series expansion and study the behavior of derivatives to understand the speed and nature of convergence.

Vanishing Derivatives

Vanishing derivatives play a pivotal role in determining the speed of convergence in fixed point iterations. When multiple derivatives of a function \(g(x)\) vanish at the fixed point \(x^*\), it means:

• The function is extremely flat around that point.
• The iteration process takes bigger leaps towards the correct value.
• Convergence becomes quicker, enhancing computational efficiency.

For instance, if the first \(r\) derivatives vanish, the order of convergence becomes \((r+1)\). This means the error term decreases as a higher power of itself in each iteration, marking a significant jump in precision and speed. This property is leveraged to design rapid convergence methods, saving time and computational resources.