Numerical Mathematics II: Summary of Lectures

April 13, 1st Lecture

Definition of explicit ODE of first order and of the corresponding initial value problem (IVP). Definition of the corresponding notion of solution. Equivalence between IVP and suitable integral equations. Theorem: If the right-hand side of and ODE is continuous and locally Lipschitz with respect to y (i.e. with respect to its second variable), then every IVP has a unique maximal solution. Gronwall's inequality. Theorem regarding the continuity in initial conditions.

April 15, 2nd Lecture

Definition of the partition (grid, mesh) of an interval with step sizes and a mesh size. Definition of a (general) m-step method (for the approximation of a K^n-valued function on an interval) given by m real parameters and a defining (or increment) function. Definition of corresponding notions of a local solution and of a global solution (given a partition). Definition of (general and standard) single-step and multistep methods, of explicit methods and implicit methods. Remark: The methods yield discrete approximations from which a continuous approximation is obtained via interpolation. Remark: If defined, an explicit method always yields unique local solutions and it is always equivalent to an implicit method. An implicit method might not be equivalent to an explicit method as it might have no or multiple local solutions. Definition of the explicit Euler method. As an explicit method, it always has unique local solutions, but might not have a global solution. Interpretation of explicit Euler as an approximation by piecewise affine functions.

April 20, 3rd Lecture

Definition of the order of convergence of an explicit single-step method, estimating its global truncation error. Definition of the local truncation error, of its well-definedness and of its uniform well-definedness. Definition of the consistency of the method as well as of its consistency of order p. Lemma: If the method is consistent of order p, then it is consistent. Lemma: If the method is consistent with respect to the approximation of a differentiable function, then this function is either constantly zero or the method must be a standard method. Equivalent consistency conditions for a standard method approximating the solution to an ODE in terms of a relation between the defining function and the right-hand side of the ODE. Theorem: Error estimate for an explicit single-step method, where the defining function is Lipschitz with respect to y, allowing for initial errors and rounding errors in addition to truncation errors; in particular, one obtains that consistency of order p implies order of convergence p.

April 22, 4th Lecture

A corollary to the previous theorem provides an optimal equidistant stepsize, where the error bound (given both truncation and rounding errors) becomes minimal. Lemma: A compact subset of an open set can be thickened such that the thickened set is still a subset of the open set. Theorem: If the right-hand side of an ODE is continuously differentiable, then the explicit Euler method is consistent of order 1 and it has order of convergence 1.

April 27, 5th Lecture

Definition of the classical explicit Runge-Kutta (RK) method. Theorem: If the right-hand side of an ODE has continuous partials up to fourth order, then the classical explicit RK method is consistent of order 4 (proof later) and it has order of convergence 4. Definition of general (explicit and implicit) s-stage RK methods as well as their corresponding Butcher tableaus, containing the method's weights, nodes, and its RK matrix (an RK matrix is explicit if, and only if, its RK matrix is strictly lower triangular, otherwise implicit). Definition of the consistency condition and of the node condition. Equivalence between k-form and u-form of RK methods.

April 29, 6th Lecture

Definition of what it means for an RK method to have unique local solutions and definition of the standard form of such methods. Recursion for RK methods in k-form and in u-form. All RK methods (both explicit and implicit) can be written as both explicit and implicit single-step methods. Examples of RK methods: Explicit Euler method, classical explicit RK method, implicit Euler method (Butcher tableau provided for each example). Theorem: For explicit RK methods, the auxiliary functions k_j and u_j are defined recursively, and these functions inherit continuity from the continuity of the right-hand side f of the ODE and the defining function is then also continuous; an explicit RK method has unique local solutions if f is continuous and defined on an open set; the local truncation error is then well-defined and (for nontrivial f) the method is consistent if, and only if, it satisfies the consistency condition. For explicit RK methods, the auxiliary functions and the defining function inherit Lipschitz continuity with respect to y and differentiability properties from f. Statement of Theorem: Explicit RK methods are defined in a neighborhood of a continuous function; if they are Lipschitz with respect to y and consistent of order p, then they are convergent of order p.

May 4, 7th Lecture

Proof of previous theorem. Parametrized version of the Banach Fixed Point Theorem.

May 6, 8th Lecture

(1) An RK method has unique local solutions if f is defined on an open set, continuous, and locally Lipschitz with respect to y; for small h, the solution depends continuously on h and it is even C^p if f is C^p; (2) If the RK method is in standard form, then the local truncation error is well-defined and (for nontrivial f) the method is consistent if, and only if, it satisfies the consistency condition; an RK method has unique global solutions if f is defined on the entire space, f is continuous and globally Lipschitz with respect to y.

May 11, 9th Lecture

If the right-hand side of an autonomous ODE is locally Lipschitz, but not globally Lipschitz, then, in case of nonuniqueness of solutions to an implicit RK method, the norm of additional solutions has to diverge to infinity for h to zero. An example, where this kind of behavior can be observed. Definition of autonomous ODE. Theorem: Each nonautonomous ODE is equivalent to an autonomous ODE.

May 13, 10th Lecture

Theorem: RK methods respect the equivalence between nonautonomous ODE and autonomous ODE if the RK methods satisfy the consistency condition as well as the node condition. Example: RK methods for one-dimensional linear autonomous ODE. Definition of the (scalar) stability function of an RK method. The stability function of an s-stage RK method is a rational function R=R/Q with polynomials P,Q of degree at most s with real coefficients, where one can choose P,Q in a unique way such that P(0)=Q(0)=1 and P,Q are mutually prime; if the RK method is explicit, then Q=1 and R=P is a polynomial.

May 18, 11th Lecture

Rational functions as maps between sets of quadratic matrices. Example: RK methods for general linear ODE with constant coefficients. Set of complex rational functions without removable singularities. Definition of an RK method's (scalar) stability function as a complex rational functions without removable singularities (that maps real numbers to real numbers), and its extension to quadratic matrices M such that the spectrum of M does not intersect the set of singularities of the scalar stability function. Examples for computations of stability functions: General formula for a 1-stage RK method; special cases yield the stability functions for the explicit Euler method, the implicit Euler method, and the implicit midpoint method (same as the 1-stage Gauss method). Stability function of the classical explicit RK method.

May 20, 12th Lecture

General formula for the stability function of a 2-stage RK method. Stability function of the implicit trapezoidal method. Theorem: If a rational function P/Q with polynomials P,Q approximates the exponential function with order of consistency p, then p is less than or equal to deg(P)+deg(Q). Theorem: If an s-stage RK method has order of consistency p for a nontrivial solution to y'=y, then p is less than or equal to 2s for implicit RK methods, p is less than s for explicit RK methods. Definition of multisets (also called unordered tuples),

May 25

No lecture due to the holiday.

May 27, 13th Lecture

Definition of the cardinality of multisets, definition of finite multisets. Definition of combinatorial function delta defined on finite multisets. Recursive definition of (finite unlabeled rooted) trees, in particular, of trees of depth d. Notation that represents trees as graphs. Recursive definition of a tree's order. Recursive definition of a tree's factorial and of a tree's weight. Definition of bushy trees (which are trees that have precisely depth 2). Lemma: For each k at least k, there exists precisely one bushy tree b(k) of order k; the factorial of b(k) is k, the weight of b(k) is 1/(k-1)!

June 1, 14th Lecture

Theorem: The depth of a tree is at most as large as its order (and there always exists a tree, where the order equals the depth). Partitions of the set of all trees with regard to the depths and/or order of the trees. The set of all trees with a fixed order is finite. The set of all trees with a fixed depth is infinite and countable (except for depth 1). The set of all trees is infinite and countable as well. Definition of higher-order total derivatives as (symmetric) multilinear maps. Relation between composition of such symmetric multilinear maps and trees. Recursive definition of derivatives with respect to trees. Example: Computation of all trees of order at most 4, each with factorial, weight, and corresponding derivative. Version of Taylor's theorem.

June 3, 15th Lecture

Theorem regarding the Taylor expansion of the solution of an autonomous ODE, where the terms up to order p can be written as a sum over the set of all trees of order at most p. Recursive definition of the function v_A that, depending on a matrix A, assigns a vector to each tree. Example, where this function is computed for each tree up to order 4 and for each bushy tree.

June 8, 16th Lecture

Theorem regarding the Taylor expansion of the defining function of an RK method, where all terms up to order p are written as a sum over the set of trees of order at most p. Definition of the consistency condition of order p for RK methods (for p=1, one recovers the consistency condition that the weights has to sum to 1). Butcher's theorem: Roughly, it states that an RK method is consistent of order p if, and only if, it satisfies the consistency condition of order p (plus the node condition for nonautonomous ODE) -- more precisely, a sufficient condition for the consistency condition of order p to be satisfied is that the method is consistent of order p with respect to all solutions to autonomous ODE with polynomial right-hand side.

June 10, 17th Lecture

Completion of proof of Butcher's theorem. Example: Formulation of all consistency conditions up to order 4. Examples: Explicit and implicit Euler method satisfy consistency condition of order 1; the implicit trapezoidal method satisfies the consistency conditions of order 2 (but not of order 3); the classical explicit RK method satisfies the consistency conditions of order 4. Example of a 2-stage implicit Gauss method that satisfies all consistency conditions of order 4.

June 15, 18th Lecture

Definition of Butcher's simplifying conditions B(alpha), C(beta), D(gamma). Lemma: For an s-stage RK method with distinct nodes, B(alpha) and C(s) and alpha=s+gamma implies D(gamma). Theorem: Each equation of B(alpha) plus the node condition is sufficient for the consistency condition with respect to the corresponding bushy tree to be satisfied. Theorem: If C(beta) holds and T1, T2 are trees such that T1 contains trees S_j plus trees U_i such that the sum of the order of the U_i is K, and T2 contains the same S_j plus K-many empty set trees, then the consistency condition with respect to T1 is satisfied if, and only if, the consistency condition with respect to T2 is satisfied. Theorem: If the k-th equation of D(gamma) holds plus the node condition and T1, T2, S are trees such that T1 contains S plus k-1 copies of the empty set tree, and T2 contains the same trees as S plus k copies of the empty set tree, then the consistency conditions with respect to T2 and S together imply the consistency condition with respect to T1.

June 17, 19th Lecture

Theorem: If an RK method satisfies (B(p) and C(beta) and p is at most beta+1) or (B(p) and C(beta) and D(gamma) and p is not more than 2beta+2 and not more than beta+gamma+1), then the method satisfies the consistency condition of order p. Example: The previous theorem yields another proof that the 2-stage Gauss method is consistent of order 4. Definition of the quadrature rule Q(b,c) defined by a weights vector b and by a nodes vector c. Theorem: An RK method with weights vector b and with nodes vector c satisfies B(alpha) if, and only if, Q(b,c) (on [0,1]) is exact for each polynomial of degree at most alpha-1. Definition of collocation polynomial and collocation method. Definition of the RK method defined via a vector of collocation nodes c and collocation; definition of the quadrature rule defined by c and collocation.

June 22, 20th Lecture

Theorem providing a bijective correspondence between collocation polynomials and solutions to systems of equations for corresponding RK methods. Theorem that states that both methods have the same defining function. Theorem: Collocation methods arising from a collocation vector c with s collocation nodes satisfy the simplifying conditions B(s) and C(s), i.e., in particular, the consistency and the node condition; the corresponding quadrature rule defined by c and collocation is exact for each polynomial of degree at most s-1. Theorem: A collocation method is always implicit, execpt if it is the explicit Euler method. Theorem that provides existence and (local) uniqueness of collocation polynomials if f is continuous and locally Lipschitz with respect to y.

June 24, 21st Lecture

Theorem: An s-stage collocation method satisfies the consistency condition of order q+1 if the corresponding quadrature rule defined by the same collocation vector and collocation is exact for each polynomial of degree at most q (where q is at least s-1). Theorem: An s-stage RK method is a collocation method if, and only if, its nodes are all distinct and it satisfies the simplifying conditions B(s) and C(s); and s-stage RK method that satisfies the consistency condition of order p (p bigger or equal s) is a collocation method if, and only if, its nodes are all distinct and it satisfies C(s). Examples: Both explicit and implicit Euler method are collocation methods, the implicit trapezoidal method is a collocation method as well, but the classical explicit RK method is no collocation method. Definition of Gauss methods, which are particular collocation methods, where the s-stage Gauss method satisfies the consistency condition of order 2s. Examples, where scalar linear initial value problems are solved via the explicit and implicit Euler method, comparing the asymptotic behavior of the respective exact solution with that of the respective discrete approximations, depending on the stepsize of the discrete solutions. Depending on certain parameters, one observes the phenomenon of stiffness, where, for the the explicit method, the stability of the exact solution is only inherited by the discrete solution for sufficiently small stepsizes.

June 29, 22nd Lecture

Python implementations and results of some RK methods. Numerical results regarding previous (stiff and nonstiff) problems computed via the shown Python implementations. Definition of matrix exponential function. Theorem: 0 is stable for y'=Ay if, and only if, all eigenvalues of A have nonpositive real parts and are semisimple if the real part vanishes. Theorem: 0 is asymptotically stable for y'=Ay if, and only if, all eigenvalues of A have negative real parts. Definition of 0 being stable (resp. asymptotically stable) for the map y->Ay. Theorem: 0 is stable for the map y->Ay if, and only if, the spectral radius of A is less than or equal to 1 and all eigenvalues with modulus 1 are semisimple. Theorem: 0 is asymptotically stable for the map y->Ay if, and only if, the spectral radius of A is strictly less than 1.

July 1, 23rd Lecture

Completion of proof of previous theorem. Theorem: For a stability function R and a quadratic matrix M, the spectrum of R(M) is R applied to the spectrum of M. Definition of an RK method's stability region. Definition of stepsize thresholds up to which (asymptotic) stability is inherited by an RK method from a given matrix. Basic properties of stability regions.

July 6, 24th Lecture

Representations of the stability regions for explicit and implicit Euler as well as for the implicit trapezoidal method. Definition of numbers that measure the length of the initial segment of rays emanating from the origin, which stays inside the (interior of) an RK method's stability region. Theorem that relates these numbers to the previously defined stepsize thresholds.

July 8, 25th Lecture

Computation of above-mentioned numbers and stepsize thresholds for the explicit and implicit Euler methods. Theorem: If an RK method has a nonconstant polynomial as stability function (which, in particular holds for nontrivial explicit RK methods), then its stability region is compact and the corresponding stepsize thresholds for stabilty are finite. Definition of A-stability for an RK method. Examples: The implicit Euler and implicit trapezoidal method are A-stable; a nontrivial explicit RK method can never be A-stable. Example, where two-dimensional linear initial value problems are solved via the explicit and implicit Euler method, comparing the asymptotic behavior of the respective exact solution with that of the respective discrete approximations, depending on the stepsize of the discrete solutions. Definition of upper Lipschitz conditions for functions, dissipative functions, and nonexpansive ODE. Remark: Nonexpansiveness of an ODE implies (forward) uniqueness of solutions, but not existence of solutions. Theorem: If f is dissipative and continuous, then the corresponding ODE is nonexpansive; if a nonexpansive ODE has solutions for each initial value problem, then its right-hand side is dissipative.

July 13, 26th Lecture

---

Send feedback concerning this page to
For spam control reasons, the e-mail address is only provided as an image.
Thus, you have to copy it manually. Sorry for any inconvenience.

Corrections (even minor ones) and suggestions for improvements are welcome.

Last update: Jul 6, 2026 Peter Philip.