Math 2.0

Numerical analysis Ordinary differential equations Proposition

Backward Euler method

Builds on Numerical methods for ordinary differential equationsInitial value problemLipschitz conditionBanach fixed point theoremLocal truncation error

Statement

Let f ⁣:[t0,T]×ℝd→ℝdf \colon [t_0, T] \times \R^d \to \R^d be continuous and Lipschitz in yy with constant LL, and consider the initial value problem y′=f(t,y)y' = f(t, y), y(t0)=y0y(t_0) = y_0. The backward Euler method with step h>0h > 0 sets tn+1=tn+ht_{n+1} = t_n + h and defines yn+1y_{n+1} by the implicit equation yn+1=yn+h f(tn+1,yn+1).y_{n+1} = y_n + h \, f(t_{n+1}, y_{n+1}). Then:

  1. if hL<1hL < 1, the equation has exactly one solution yn+1y_{n+1} for each yny_n;
  2. if the exact solution yy is of class C3C^3, the local truncation error is y(tn+1)−y(tn)−h y′(tn+1)=−h22y′′(tn)+O(h3)y(t_{n+1}) - y(t_n) - h \, y'(t_{n+1}) = -\frac{h^2}{2} y''(t_n) + O(h^3), so the method has order 11;
  3. for the test equation y′=λyy' = \lambda y with λ∈ℂ\lambda \in \C, it gives yn+1=R(hλ)yny_{n+1} = R(h\lambda) y_n with R(z)=11−zR(z) = \frac{1}{1 - z}, and ∣R(z)∣<1\abs{R(z)} < 1 whenever Re⁡z<0\operatorname{Re} z < 0.

Remarks

Clause 1: the map z↦yn+hf(tn+1,z)z \mapsto y_n + h f(t_{n+1}, z) is a contraction with constant hL<1hL < 1, so the Banach fixed point theorem gives a unique fixed point, which fixed-point iteration finds. Clause 2 follows by Taylor expansion of y(tn)y(t_n) and y′(tn+1)y'(t_{n+1}) about tnt_n. Clause 3: if Re⁡z<0\operatorname{Re} z < 0 then ∣1−z∣>1\abs{1 - z} > 1; so the numerical solution decays whenever the exact one does, for every step size, and the method is A-stable. Example: for y′=−1000yy' = -1000 y and h=0.1h = 0.1, the explicit Euler method multiplies by 1−100=−991 - 100 = -99 at each step and explodes, while backward Euler multiplies by 1101\frac{1}{101} and decays like the true solution. For stiff problems hLhL is large, and the equation is solved by Newton's method rather than by fixed-point iteration. So the restriction hL<1hL < 1 of clause 1 is a feature of that proof, not of the method.

Going deeper

For a student

Backward Euler is the simplest implicit method and the prototype of methods for stiff equations. It is both the one-stage Radau IIA Runge–Kutta method and the first backward differentiation formula (BDF1). Its stability function R(z)=1/(1−z)R(z) = 1/(1-z) tends to 00 as z→−∞z \to -\infty, a property called L-stability, which damps fast transients strongly. Its accuracy is only first order, so in practice higher-order implicit methods such as the BDF family or the Gauss–Legendre methods are used, with backward Euler as their simplest relative.

Reading path

To understand this page from the ground up, read these 30 pages in order. The foundations come first.

Show the path as a graph
Element, definition, no evidence levelElementdefinitionExtended real number line, object, no evidence levelExtended real number …objectInitial value problem, concept, no evidence levelInitial value problemconceptLipschitz condition, concept, no evidence levelLipschitz conditionconceptLocal truncation error, concept, no evidence levelLocal truncation errorconceptNumerical methods for ordinary differential equations, concept, no evidence levelNumerical methods for…conceptProposition, concept, no evidence levelPropositionconceptReal numbers, object, no evidence levelReal numbersobjectSet bounded above, definition, no evidence levelSet bounded abovedefinitionSet, definition, no evidence levelSetdefinitionImplication, definition, no evidence levelImplicationdefinitionPredicate, definition, no evidence levelPredicatedefinitionSupremum, definition, no evidence levelSupremumdefinitionOrdered pair, definition, no evidence levelOrdered pairdefinitionExistential quantifier, definition, no evidence levelExistential quantifierdefinitionUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionCartesian product, definition, no evidence levelCartesian productdefinitionSubset, definition, no evidence levelSubsetdefinitionUniqueness quantifier, definition, no evidence levelUniqueness quantifierdefinitionBinary relation, definition, no evidence levelBinary relationdefinitionFunction, definition, no evidence levelFunctiondefinitionMetric space, definition, no evidence levelMetric spacedefinitionConvergence of a sequence in a metric space, definition, no evidence levelConvergence of a sequ…definitionLipschitz map, definition, no evidence levelLipschitz mapdefinitionDiameter of a set, definition, no evidence levelDiameter of a setdefinitionContraction mapping, definition, no evidence levelContraction mappingdefinitionEpsilon characterisation of Cauchy sequences, statement, no evidence levelEpsilon characterisat…statementComplete metric space, definition, no evidence levelComplete metric spacedefinitionBanach fixed point theorem, statement, no evidence levelBanach fixed point th…statementBackward Euler method, statement, no evidence levelBackward Euler methodstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Element definition
  2. Extended real number line object
  3. Initial value problem concept
  4. Lipschitz condition concept
  5. Local truncation error concept
  6. Numerical methods for ordinary differential equations concept
  7. Proposition concept
  8. Real numbers object
  9. Set bounded above definition
  10. Set definition
  11. Implication definition
  12. Predicate definition
  13. Supremum definition
  14. Ordered pair definition
  15. Existential quantifier definition
  16. Universal quantifier definition
  17. Cartesian product definition
  18. Subset definition
  19. Uniqueness quantifier definition
  20. Binary relation definition
  21. Function definition
  22. Metric space definition
  23. Convergence of a sequence in a metric space definition
  24. Lipschitz map definition
  25. Diameter of a set definition
  26. Contraction mapping definition
  27. Epsilon characterisation of Cauchy sequences statement
  28. Complete metric space definition
  29. Banach fixed point theorem statement
  30. Backward Euler method statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Backward_Euler_method
About this page
TagM7XKVNATFA
URIm2://M7XKVNATFA
Kindstatement, proposition
WritingW0 stub
MSC65L04, 65L05, 65L20
StatusThis copy of the site has no build data. Run m2 status M7XKVNATFA.
AboutNumerical methods for ordinary differential equations
UsesNumerical methods for ordinary differential equations, Initial value problem, Lipschitz condition, Banach fixed point theorem, Local truncation error
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.