Problem 2 - A First Course in the Numerical Analysis of Differential Equations

Question

The linear system \(y^{\prime}=A y, y(0)=y_{0}\), where \(A\) is a symmetric matrix, is solved by Euler's method. a Letting \(e_{n}=y_{n}-y(n h), n=0,1, \ldots\), prove that $$ \left\|e_{n}\right\|_{2} \leq\left\|y_{0}\right\|_{2} \max _{\lambda \in \sigma(A)}\left|(1+h \lambda)^{n}-\mathrm{e}^{n h \lambda}\right| $$ where \(\sigma(A)\) is the set of eigenvalues of \(A\) and \(\|\cdot\|_{2}\) is the Euclidean matrix norm (cf. A.1.3.3). b Demonstrate that for every \(-1 \ll x \leq 0\) and \(n=0,1, \ldots\) it is true that $$ \mathrm{e}^{n x}-\frac{1}{2} n x^{2} \mathrm{e}^{(n-1) x} \leq(1+x)^{n} \leq \mathrm{e}^{n x} $$ [Hint: Prove first that \(1+x \leq \mathrm{e}^{x}, 1+x+\frac{1}{2} x^{2} \geq \mathrm{e}^{x}\) for all \(x \leq 0\), and then argue that, provided \(|a-1|\) and \(|b|\) are small, it is true that \((a-b)^{n} \geq\) \(\left.a^{n}-n a^{n-1} b .\right]\) c Suppose that the maximal eigenvalue of \(A\) is \(\lambda_{\max }<0 .\) Prove that, as \(h \rightarrow 0\) and \(n h \rightarrow t \in\left[0, t^{*}\right]\) $$ \left\|e_{n}\right\|_{2} \leq \frac{1}{2} t \lambda_{\max }^{2} \mathrm{e}^{\lambda_{\max } t}\left\|y_{0}\right\|_{2} h \leq \frac{1}{2} t^{*} \lambda_{\max }^{2}\left\|y_{0}\right\|_{2} h $$ d Compare the order of magnitude of this bound with the upper bound from Theorem \(1.1\) in the case $$ A=\left[\begin{array}{rr} -2 & 1 \\ 1 & -2 \end{array}\right], \quad t^{*}=10 $$

Step-by-Step Solution

Answer

Maximum error at step \( n \) is bounded by \( \|y_0\|_2 \max_{\lambda \in \sigma(A)} |(1+h \lambda)^n - e^{nh\lambda}| \).\nFor given matrix, bounds adjust per its specific eigenvalues.

Step 1: Understanding the Problem for Part (a)

In part (a), we need to establish an upper bound on \( \|e_{n}\|_{2} \), where \( e_n = y_n - y(nh) \). The task is to show:\[ \left\|e_{n}\right\|_{2} \leq\left\|y_{0}\right\|_{2} \max_{\lambda \in \sigma(A)}\left|(1+h \lambda)^{n}-e^{n h \lambda}\right| \]We start by considering the propagation of errors in Euler’s method when applied to a linear system involving a symmetric matrix \( A \). We know that \( y_{n+1} = (I + hA)y_n \), while the true solution evolves as \( y(t) = e^{tA}y_0 \). The error vector at step \( n \) is the difference \( y_n - e^{nhA}y_0 \).

Step 2: Analyzing the Error Using Eigenvalues

For a symmetric matrix \( A \), it is diagonalizable with real eigenvalues. Let \( \lambda \) be an eigenvalue of \( A \). The expression \( y_n = (I + hA)^n y_0 \) can be expressed as \( (I + h \lambda)^n \) when projecting onto the eigenvectors. The true exponential solution is \( e^{nh\lambda} \). The error in one-step is magnified by the factor \( \left| (1 + h \lambda)^n - e^{n h \lambda} \right| \).

Step 3: Maximizing Over Eigenvalues

The error norm \( \|e_n\|_2 \) reflects contributions from all eigenvalues. The worst-case is the maximum deviation between the discrete and continuous exponential, giving:\[ \|e_n\|_2 \leq \|y_0\|_2 \max_{\lambda \in \sigma(A)} \left| (1 + h \lambda)^n - e^{n h \lambda} \right| \]

Step 4: Proving Part (b) Initial Boundaries

We need to show:1. \( 1 + x \leq e^x \)2. \( 1 + x + \frac{1}{2}x^2 \geq e^x \)for all \( x \leq 0 \). The exponential \( e^x \) has a Taylor series where this holds for \( |x| \ll 1 \). Consequently, these inequalities approximate the exponential behavior in small negative \( x \).

Step 5: Extending the Inequalities to (b)

Using the hint, involve the approximation of \( (1 + x)^n \) vs. \( e^{nx} \).- Recall a closeness result for small \( |a-1| \), \( |b| \): \((a-b)^n \geq a^n - na^{n-1}b \).- Use this with: \( a = 1 + x \), \( b = \frac{1}{2}nx^2e^{(n-1)x} \).Hence, we have \( e^{nx} - \frac{1}{2} nx^2 e^{(n-1)x} \leq (1+x)^n \leq e^{nx} \).

Step 6: Analyzing Error Bound in (c)

For \( h \to 0 \) and \( nh \to t \), with \( \lambda_{\max} < 0 \), derive\[ \|e_n\|_2 \leq \frac{1}{2} t \lambda_{\max}^2 e^{\lambda_{\max} t} \|y_0\|_2 h \]Satisfying the decreasing exponential due to \( \lambda_{\max} < 0 \), indicating the bound scales with \( h \).

Step 7: Implementing to Particular Matrix in (d)

Given an example with matrix:\[ A = \begin{bmatrix} -2 & 1 \ 1 & -2 \end{bmatrix} \]Determine eigenvalues (solve \( \det(A - \lambda I) = 0 \)). It computes to eigenvalues \( -3 \) and \( -1 \).Using these in the problem's conditions leads to calculating the error bounds and comparison as required with past Theorem values.

Key Concepts

Euler's Method

Euler's Method is a simple numerical technique used to approximate solutions of a first-order ordinary differential equation (ODE). It is particularly useful for solving linear initial value problems such as the system \( y' = Ay, \, y(0) = y_0 \). To understand why Euler's Method is handy, remember that it turns continuous problems into discrete steps.

Imagine you have a slope (the derivative of your function) and an initial point. Euler's Method approximates the next point by moving a small step in the direction of the slope. Mathematically, this means \( y_{n+1} = y_n + h f(y_n) \). Here, \( h \) is the step size of our approximation.

This method is straightforward but may introduce errors, which can be significant when step sizes are large. Smaller \( h \) means more steps and often a better approximation, but at the cost of more computations. This method is fundamental in numerical analysis because it illustrates how continuous systems can be studied in discrete time frames.

Symmetric Matrix

In numerical analysis, symmetric matrices are quite special. These matrices have the property that their transpose equals the original matrix, meaning \( A^T = A \). This symmetry leads to useful mathematical properties that make them easier to work with.

One significant advantage of symmetric matrices is that their eigenvalues are all real numbers. This is incredibly important when studying the behavior of solutions to differential equations, as it provides stability and predictability in the solutions.

Additionally, symmetric matrices are inherently diagonalizable. This means they can be expressed as \( A = PDP^{-1} \), where \( D \) is a diagonal matrix whose entries are the eigenvalues of \( A \). This ease of manipulation is often exploited in numerical methods, allowing for simplified calculations in algorithms like iterative methods used in the eigenvalue, eigenvector computations.

Eigenvalues

Eigenvalues essentially reveal the underlying behavior of a matrix. For a given matrix \( A \), the eigenvalues are solutions to the characteristic equation \( \det(A - \lambda I) = 0 \). They uncover essential insights into the matrix's operation.

Understanding eigenvalues becomes particularly vital when applying numerical methods to systems of differential equations. In a system \( y' = Ay \), the eigenvalues of the matrix \( A \) indicate the growth or decay rates of the solutions. Negative eigenvalues typically suggest exponential decay, while positive ones suggest exponential growth.

Studying eigenvalues can also highlight stability issues. If a numerical solution's eigenvalues have a large magnitude, it might 'blow up' over time (a scenario where the error grows unbounded). This is crucial for verifying whether a numerical method like Euler's can provide stable solutions over time.

Error Propagation

When using numerical methods like Euler's, understanding error propagation is essential. Error propagation refers to how small inaccuracies in computation can affect the results over many iterations. This is highly relevant in recursive methods, where each step's error can influence subsequent steps.

In the context of Euler’s Method, the error in one step can be magnified through successive operations, leading to significant inaccuracies if not monitored. For a linear system, this could result in a deviation \( e_n = y_n - y(nh) \).

By understanding the maximum error across all possible eigenvalues of a system, we can estimate the worst-case scenario, helping to strategize how to select a step size \( h \) for minimal error. Generally, smaller \( h \) leads to lesser errors but more computation. Thus, balancing accuracy with efficiency in numerical analysis is a constant challenge.