{ "cells": [ { "cell_type": "markdown", "id": "81b1d2f0", "metadata": {}, "source": [ "---\n", "title: \"Higher Order Methods\"\n", "subtitle: \"Lecture 4\"\n", "date: 2026-02-02\n", "abstract-title: Overview\n", "abstract: | \n", " (1) Error estimates for one-step methods \n", " (2) Higher order Taylor methods \n", " (3) Intro to Runge Kutta methods \n", "format:\n", " html:\n", " other-links:\n", " - text: This notebook\n", " href: L4.ipynb\n", "---" ] }, { "cell_type": "markdown", "id": "63cf0867", "metadata": {}, "source": [ "::: {.callout-note}\n", "\n", "I encourage you to play around with the juptyer notebook for this lecture - you can copy the code with the ```this notebook``` button on the side of this page.\n", "\n", ":::\n", "\n", "::: {.callout-warning}\n", "\n", "These notes are mainly a record of what we discussed and are not a substitute for attending the lectures and reading books! If anything is unclear/wrong, let me know and I will update the notes.\n", "\n", ":::\n", "\n", "::: {.callout-tip}\n", "\n", "This lecture is mostly based on @Burden section 5.2, 5.3\n", "\n", ":::" ] }, { "cell_type": "code", "execution_count": 1, "id": "db6fe346", "metadata": {}, "outputs": [], "source": [ "#| echo: false\n", "\n", "using Plots, LaTeXStrings, OrdinaryDiffEq" ] }, { "cell_type": "markdown", "id": "5ea01014", "metadata": {}, "source": [ "Recall that we are considering IVPs: seek $u :[0,T] \\to \\mathbb R$ such that\n", "\n", "\\begin{align}\n", " &u(0) = u_0 \\nonumber\\\\\n", " &u'(t) = f\\big( t, u(t) \\big). \\tag{IVP}\n", "\\end{align}\n", "\n", "We will suppose that $f$ is continuous on $[0,T] \\times \\mathbb R$ and Lipschitz in the second argument and so the problem is well-posed and there exists a unique solution to $(\\text{IVP})$. Recall *Euler's* method: we approximate $u$ on the equispaced mesh $\\{t_j = j h\\}_{j=0}^n$ where $h := \\frac{T}{n}$ is the mesh size with the following difference equation\n", "\n", "\\begin{align}\n", " u_{j+1} = u_j + h f( t_j, u_j ).\n", " \\tag{Euler}\n", "\\end{align}\n", "\n", "We saw last week that, if $\\|u''\\|_{L^\\infty} \\leq M$, then we obtain the bound $| u(t_j) - u_j | \\leq \\frac{h M}{2L} \\left( e^{Lt_j} - 1 \\right)$. That is, the error decays with rate $O(h) = O(n^{-1})$ as $n \\to \\infty$. \n", "\n", "::: {#exr-1}\n", "\n", "Prove that Euler's method applied to $(\\text{IVP})$ converges with rate $O(h)$ in each of the following cases (these are the numerical experiments we saw last week):\n", "\n", "* *(i)* $u_0 > 0$, $f(t, u) = \\mu u$, $\\mu > 0$, \n", "* *(ii)* $u_0 = 1$, $f(t,u) = u( 1 - \\frac{u}{20})$, $T = 5$, \n", "* *(iii)* $u_0 = 0$, $f(t, u) = t^2 - u \\sin t$, $T = 20$, \n", "\n", "Write down the corresponding error estimates. Compare your error bounds with the true errors that we observed last week. How pessimistic are the error bounds?\n", "\n", ":::\n", "\n", "A natural question one may ask is \"how can we do better than $O(h)$ convergence?\": \n", "\n", "## General One-Step Methods\n", "\n", "We now consider the following *one-step* method:\n", "\n", "\\begin{align}\n", " u_{j+1} = u_{j} + h \\phi( t_j, u_j; h)\n", " \\tag{1-step}\n", "\\end{align}\n", "\n", "for some choice of $\\phi$." ] }, { "cell_type": "code", "execution_count": 2, "id": "1f847c0c", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "oneStep (generic function with 1 method)" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function oneStep( u0, ϕ, T, n )\n", " h = T/n \n", " t = 0:h:T \n", " u = zeros(n+1)\n", " u[1] = u0\n", " for j = 1:n\n", " u[j+1] = u[j] + h * ϕ( t[j], u[j], h )\n", " end\n", " return u\n", "end " ] }, { "cell_type": "markdown", "id": "ea83165d", "metadata": {}, "source": [ "::: {.callout-note}\n", "\n", "When $\\phi(t, u; h) := f(t, u)$, $(\\text{1-step})$ is simply Euler's method.\n", "\n", ":::" ] }, { "cell_type": "markdown", "id": "34ef4799", "metadata": {}, "source": [ "We first define the local truncation error for general one-step methods:\n", "\n", "::: {#def-LTE}\n", "# Local truncation error\n", "\n", "The *local truncation error* of the method $(\\text{1-step})$ is given by \n", "\n", "\\begin{align}\n", " \\tau_{j+1}(h) := \\frac{u(t_{j+1}) - u(t_j)}{h} - \\phi(t_j, u(t_j);h).\n", "\\end{align}\n", "\n", "We say $(\\text{1-step})$ is *consistent* if \n", "\n", "\\begin{align}\n", " \\max_j \\tau_{j+1}(h) \\to 0\n", "\\end{align}\n", "\n", "as $h\\to 0$.\n", "\n", ":::\n", "\n", "It turns out that bounds on the local truncation error lead to a global error bound: \n", "\n", "::: {#thm-global}\n", "\n", "Suppose that \n", "\n", "* *(i)* $|\\tau_{j+1}(h)| \\leq Ch^p$, \n", "* *(ii)* $\\left| \\frac{\\partial \\phi}{\\partial u} \\right| \\leq L$\n", "\n", "for all $(t,u) \\in[0,T] \\times \\mathbb R$. Then, we have\n", "\n", "\\begin{align}\n", " | u(t_j) - u_j | \\leq \\frac{Ch^p}{L} \\left( e^{L t_j} - 1 \\right).\n", "\\end{align}\n", "\n", ":::\n", "\n", "::: {#def-order}\n", "# Order of accuracy\n", "\n", "If $\\tau_{j+1}(h) = O(h^p)$ for some $p$, we say $(\\text{1-step})$ has *order of accuracy* $p$.\n", "\n", ":::\n", "\n", "::: {.callout-note}\n", "\n", "This is a more general version of the theorem we saw last week for Euler's method. In that case we assumed that $\\|u''\\|_{L^\\infty} \\leq M$ and showed $|\\tau_{j+1}(h)| \\leq \\frac{h M}{2}$, giving order of accuracy $1$.\n", "\n", "::: \n", "\n", "